# Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 68 references that are in the map.
- First posted on arXiv 17 Mar 2022.

## Builds on (most cited first, 30 of 31)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions](https://mlsanity.com/paper/2110.08150/) (2021)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Optimal error bounds for nonexpansive fixed-point iterations in normed spaces](https://mlsanity.com/paper/2108.10969/) (2021)
- [Finding Local Minima via Stochastic Nested Variance Reduction](https://mlsanity.com/paper/1806.08782/) (2018)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)

## Built on by (most cited first, 19 of 19)

- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Asymptotic regularity of a generalised stochastic Halpern scheme](https://mlsanity.com/paper/2411.04845/) (2024)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [An Inexact Halpern Iteration with Application to Distributionally Robust Optimization](https://mlsanity.com/paper/2402.06033/) (2024)
- [How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond](https://mlsanity.com/paper/2609.08380/) (2026)
- [A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps](https://mlsanity.com/paper/2608.15966/) (2026)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)
- [Accelerated and Stable Convergence with Anchored Generalized Optimistic Method](https://mlsanity.com/paper/2606.21528/) (2026)
- [On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.06182/) (2026)
- [Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps](https://mlsanity.com/paper/2609.09524/) (2026)
- [Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities](https://mlsanity.com/paper/2609.15257/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)
- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)
- [Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding](https://mlsanity.com/paper/2609.36033/) (2026)
- [Optimal Oracle Complexity for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2610.05038/) (2026)

## Abstract (arXiv)

We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoercive -- and more generally Lipschitz-monotone -- setup, our algorithm attains ε norm of the operator with O(frac1ε3) stochastic operator evaluations, which significantly improves over state of the art O(frac1ε4) stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how to couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with O(fraclog(1/ε)ε2) stochastic operator evaluations under additional sharpness or strong monotonicity assumptions.