# Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities

arXiv: https://arxiv.org/abs/2002.08872 · HTML: https://mlsanity.com/paper/2002.08872/

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

## Built on by (most cited first, 30 of 61)

- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions](https://mlsanity.com/paper/2110.08150/) (2021)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [Asymptotic regularity of a generalised stochastic Halpern scheme](https://mlsanity.com/paper/2411.04845/) (2024)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)
- [On the Initialization for Convex-Concave Min-max Problems](https://mlsanity.com/paper/2103.00284/) (2021)
- [Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps](https://mlsanity.com/paper/2301.03931/) (2023)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)

## Abstract (arXiv)

We leverage the connections between nonexpansive maps, monotone Lipschitz operators, and proximal mappings to obtain near-optimal (i.e., optimal up to poly-log factors in terms of iteration complexity) and parameter-free methods for solving monotone inclusion problems. These results immediately translate into near-optimal guarantees for approximating strong solutions to variational inequality problems, approximating convex-concave min-max optimization problems, and minimizing the norm of the gradient in min-max optimization problems. Our analysis is based on a novel and simple potential-based proof of convergence of Halpern iteration, a classical iteration for finding fixed points of nonexpansive maps. Additionally, we provide a series of algorithmic reductions that highlight connections between different problem classes and lead to lower bounds that certify near-optimality of the studied methods.