Faster Empirical Risk Minimization

Wednesday, September 15, 2021 - 2:00pm to 3:00pm

Event Calendar Category

Uncategorized

Speaker Name

Jelena Diakonikolas

Affiliation

University of Wisconsin–Madison

Zoom meeting id

95607814981

Join Zoom meeting

https://mit.zoom.us/s/95607814981

Abstract

Empirical Risk Minimization (ERM) problems are central to machine learning, and their efficient optimization has been studied from different perspectives, often taking advantage of the finite sum structure present in typical problem formulations. In particular, tight oracle complexity bounds have been obtained under fairly general assumptions about the loss functions. In this talk, I will present a rather surprising and general result that takes advantage of the separability of nonsmooth convex loss functions with efficiently computable proximal operators -- such as, e.g., the hinge loss and the sum of absolute errors -- to obtain an algorithm that exhibits significantly lower complexity than what is predicted by the lower bounds for general nonsmooth convex losses. Crucial to this result is the use of proximal operators, which goes beyond the simple gradient oracle access to the function. The talk is based on joint work with Chaobing Song and Stephen Wright.

Biography

Jelena Diakonikolas is an assistant professor in the Department of Computer Sciences at UW-Madison. Prior to joining UW-Madison, she held postdoctoral positions at UC Berkeley and Boston University. She received her PhD from Columbia University. Her research interests are in efficient optimization methods for large scale problems and connections between optimization and other areas such as dynamical systems and Markov Chain Monte Carlo methods. Jelena is a recipient of a Simons-Berkeley Research Fellowship, the Morton B. Friedman Prize for Excellence at Columbia Engineering, and a Qualcomm Innovation Fellowship.