Revisiting Inexact Fixed-Point Iterations for Min-Max Problems - Stochasticity and Cohypomonotonicity

Explore a 29-minute conference talk delivered at the Workshop on "One World Optimization Seminar in Vienna" held at the Erwin Schrödinger International Institute for Mathematics and Physics (ESI) in June 2024. Delve into constrained, L-smooth, nonconvex-nonconcave min-max problems satisfying rho-cohypomonotonicity or admitting solutions to the rho-weakly Minty Variational Inequality (MVI). Examine the conjecture that first-order methods can tolerate values of rho no larger than 1/L, and discover how the speaker achieves optimal or best-known complexity guarantees for rho smaller than 1/L using inexact variants of Halpern and Krasnoselskii-Mann (KM) iterations. Learn about algorithms and complexity guarantees in the stochastic case, and understand how the "conic nonexpansiveness" property of operators contributes to these improvements. Gain insights into the refined analysis for inexact Halpern iteration and a proposed stochastic KM iteration with a multilevel Monte Carlo estimator.