Stephen Wright

Stephen J. Wright is the George B. Dantzig Professor of Computer Sciences, Sheldon Lubar Chair of Computer Sciences, and Hilldale Professor at the University of Wisconsin-Madison, and serves as Chair of the Computer Sciences Department. His research is in computational optimization and its applications to machine learning, data science, and many other areas of science and engineering. Wright has held leadership positions in the Mathematical Optimization Society (including a term as Chair from 2007-2010) and SIAM (Board of Trustees, 2005-2014). He has won the Dantzig Prize from MOS and SIAM, the Khachiyan Prize from the INFORMS Optimization Society, the NeurIPS Test of Time Award, and the W.R.G. Baker Award from IEEE. He was elected to the National Academy of Engineering in 2024. He has served as Editor-in-Chief of the SIAM Journal on Optimization and Mathematical Programming Series B, and has served on editorial boards of other leading journals in optimization and numerical analysis. He is the author / coauthor of widely used text and reference books in optimization including "Primal Dual Interior-Point Methods" and "Numerical Optimization." He has published widely on optimization theory, algorithms, software, and applications.

Title of talk: Revisiting Inexact Fixed-Point Iterations for Min-Max Problems

We focus on constrained, L-smooth, nonconvex-nonconcave min-max problems either satisfying rho-cohypomonotonicity or admitting a solution to the rho-weakly Minty Variational Inequality (MVI), where larger values of the parameter rho>0 correspond to a greater degree of nonconvexity. Relevant problem classes include two player reinforcement learning and interaction dominant min-max problems. It has been conjectured that first-order methods can tolerate values of rho no larger than 1/L, but results until now have stagnated at the tighter requirement rho<0.5/L. We obtain optimal or best-known complexity guarantees with cohypomonotonicity or weak MVI conditions for rho<1/L, using inexact variants of Halpern and Krasnoselskii-Mann (KM) iterations. We also provide algorithms and complexity guarantees in the stochastic case with the same range on rho. Our improvements come from harnessing the recently proposed "conic nonexpansiveness" property of operators. Finally, we provide a refined analysis for inexact Halpern iteration and propose a stochastic KM iteration with a multilevel Monte Carlo estimator.