“Structure in Min-Max Optimization
(and How to Use It!)”
Min-max
optimization problems have received significant recent renewed interest, due to
their applications in machine learning, and in particular in empirical risk
minimization (ERM) and adversarial training. Although deceptively similar to
standard (min) optimization, min-max optimization has unique features that
often lead natural approaches such as gradient descent-type updates to fail
even on relatively mild problem instances. Further, the types of guarantees
that can be established are generally more restricted than in the counterpart
setups of standard convex or smooth nonconvex optimization.
I will
discuss how introducing structure into min-max optimization or exploiting
structure already present in common problems can be utilized to surpass many of
the obstacles raised by the worst-case instances. The first example of
structure is a correspondence between smooth convex-concave optimization
problems and fixed-point equations with nonexpansive maps that leads to
near-optimal and parameter-free methods for broad classes of min-max problems.
The second is a novel structural condition for nonconvex-nonconcave setups that
is present in many problem instances and allows guaranteeing convergence of an
Extragradient-type method, surpassing the impossibility results that exist for
general smooth nonconvex-nonconcave min-max optimization. Finally, on the
positive side, I will discuss how the min-max perspective can be leveraged to
exploit the separable structure of convex ERM problems and obtain a faster
variance-reduced method, even surpassing the obstacles of existing lower bounds
for general composite optimization.
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.