Halpern Iteration and Min-Max Optimization
Abstract
Halpern iteration is a classical iteration developed by Benjamin Halpern in 1967 as a method for solving fixed point operator equations. Over the past decades, the convergence of Halpern iteration has been studied in both asymptotic and nonasymptotic terms. However, its study was predominantly confined to operator equations. This trend changed a few years ago when the connection between fixed point equations and monotone inclusion problems was utilized to show that Halpern iteration leads to either optimal or near-optimal convergence guarantees for essentially all standard classes of problems with Lipschitz operators. The setting of monotone inclusion—which corresponds to finding (or approximating) a zero of a monotone operator—is of particular relevance here, as it generalizes variational inequality (equilibria) problems and provides guarantees in terms of both optimality gap and stationarity (norm of the gradient in unconstrained settings) in min-max optimization. Both variational inequalities and min-max optimization have undergone a renaissance in recent years due to their modeling power in applications such as adversarial training of machine learning models and distributionally robust optimization. In this talk, Jelena Diakonikolas will discuss recent developments related to the use of Halpern iteration, including settings where the operator is possibly non-monotone and can be accessed only via stochastic queries. To date, the guarantees that can be obtained with variants of Halpern iteration remain unmatched by any alternative algorithms and are all provided for the last iterate.
Bio
Jelena Diakonikolas is an Assistant Professor in the Department of Computer Sciences at UW-Madison. She received her Ph.D. from Columbia University and held postdoctoral positions at UC Berkeley and Boston 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.
