ORIE Colloquium: Jelena Diakonikolas (Wisconsin) - Structure in Min-Max Optimization (and How to Use It!)

Description

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.

Bio:
Jelena Diakonikolas is an Assistant Professor at the Department of Computer Sciences, University of Wisconsin-Madison. Her main research interests are in the area of large-scale optimization. She is also interested in applications of optimization methods, particularly those pertaining to machine learning and networked systems. Prior to joining UW-Madison, Professor Diakonikolas was a Postdoctoral Fellow at UC Berkeley's Foundations of Data Analysis (FODA) TRIPODS Institute, where she primarily worked with Mike Jordan. In fall 2018, she was a Microsoft Research Fellow at the Simons Institute for the Theory of Computing, associated with the program on Foundations of Data Science. Prior to starting the postdoctoral position at UC Berkeley, she was a Postdoctoral Associate at the Department of Computer Science at Boston University, where she worked with Lorenzo Orecchia. Professor Diakonikolas completed her Ph.D. at the Department of Electrical Engineering at Columbia University, where she was co-advised by Gil Zussman and Cliff Stein. She received her undergraduate degree in electrical engineering and computing (with major in telecommunications and microwave engineering) from the School of Electrical Engineering, at the University of Belgrade,