mlsanityData to 14 Oct 2026

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

arXiv 2002.08872 ↗First posted 20 Feb 2020math.OC cs.DS cs.LGcited by 61

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 10; 2023: 11; 2024: 8; 2025: 6; 2026: 21.

61 papers.

Sort:

By area:

  1. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  2. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  3. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 21
  4. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  5. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  6. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  7. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  8. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  9. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  10. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  11. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  12. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
38 more
  1. 2023Accelerating Value Iteration with Anchoringcited by 11
  2. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  3. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  4. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  5. 2022First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problemscited by 9
  6. 2023Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problemscited by 9
  7. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  8. 2022Perseus: A Simple and Optimal High-Order Method for Variational Inequalitiescited by 5
  9. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  10. 2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
  11. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  12. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 5
  13. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  14. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4
  15. 2023Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Mapscited by 4
  16. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  17. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  18. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 4
  19. 2022Solving Constrained Variational Inequalities via a First-order Interior Point-based Methodcited by 3
  20. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  21. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  22. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 3
  23. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  24. 2026An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascentcited by 3
  25. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  26. 2024An Inexact Halpern Iteration with Application to Distributionally Robust Optimizationcited by 2
  27. 2026On the Computational Complexity of Performative Predictioncited by 2
  28. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 2
  29. 2023Beyond first-order methods for non-convex non-concave min-max optimizationcited by 1
  30. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  31. 2025A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applicationscited by 1
  32. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 1
  33. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 1
  34. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1
  35. 2023Extragradient-Type Methods with O (1/k) Last-Iterate Convergence Rates for Co-Hypomonotone Inclusionscited by 0
  36. 2023First-order methods for Stochastic Variational Inequality problems with Function Constraintscited by 0
  37. 2024HPPP: Halpern-type Preconditioned Proximal Point Algorithms and Applications to Image Restorationcited by 0
  38. 2025A regret minimization approach to fixed-point iterationscited by 0

50 most cited of 61 All 61 (JSON)