“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.