Halpern Iteration and Equilibria Problems
summary
Shows that Halpern iteration (anchored fixed-point updates plus a potential function) achieves the optimal 1/K rate for making the monotone operator norm small, giving last-iterate convergence and implicit regularization to the nearest solution. Extends to Lipschitz monotone via resolvents with only log losses, later removed by two-step Halpern variants. In stochastic settings, combining Halpern variants with recursive variance reduction (PAGE) cuts prior O(1/ε^4) bounds to O(1/ε^3) (near‑optimal).
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:57Min-Max (Saddle-Point) Optimization
- 4:29Abstractions of Min-Max; Equilibria Problems
- 7:11Hierarchy of Solutions
- 7:50Hierarchy of Approximate Solutions
- 11:44History Bits (up to 2020)
- 15:38Goal (Basic Version)
- 18:10Problem Classes: Assumptions about F
- 20:56Results and Related Work
- 23:28Basic Algorithm: Halpern Iteration
- 27:16Analysis: Main Ideas (Unconstrained Cocoercive Setup)
- 30:16Summary of Main Ideas & Results
- 32:55Implicit Regularization of Halpern Iteration
- 34:22Improvements to Cocoercive and Monotone Lipschitz Setups
- 37:51Beyond Monotone Setups
- 40:59Stochastic Setup and Prior State of the Art
- 44:20Summary and Open Questions
related talks
58mFirst-Order Stochastic Optimization
01h 18mOptimization I
27mTalk by Ali Kavis (UT Austin)
41mTransfer learning via local convergence rates of the nonparametric least squares estimator
32mRegularized Nonlinear Acceleration
58mContinuous Methods 2
29mImplicit Regularization in Nonconvex Statistical Estimation
01h 07mStochastic Second Order Optimization Methods I