# Asymptotic regularity of a generalised stochastic Halpern scheme

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 57 references that are in the map.
- First posted on arXiv 7 Nov 2024.

## Builds on (most cited first, 15 of 15)

- [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)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [A Relaxed Inertial Forward-Backward-Forward Algorithm for Solving Monotone Inclusions with Application to GANs](https://mlsanity.com/paper/2003.07886/) (2020)
- [A quantitative Robbins-Siegmund theorem](https://mlsanity.com/paper/2410.15986/) (2024)
- [On modified Halpern and Tikhonov-Mann iterations](https://mlsanity.com/paper/2203.11003/) (2022)
- [Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces](https://mlsanity.com/paper/1609.01627/) (2016)
- [Quantitative results on a Halpern-type proximal point algorithm](https://mlsanity.com/paper/2001.10040/) (2020)
- [An Inexact Halpern Iteration with Application to Distributionally Robust Optimization](https://mlsanity.com/paper/2402.06033/) (2024)
- [Quadratic rates of asymptotic regularity for the Tikhonov-Mann iteration](https://mlsanity.com/paper/2107.07176/) (2021)
- [Rates of asymptotic regularity for the alternating Halpern-Mann iteration](https://mlsanity.com/paper/2206.02226/) (2022)
- [Linear rates of asymptotic regularity for Halpern-type iterations](https://mlsanity.com/paper/2303.05406/) (2023)

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

- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [An abstract effective convergence theorem for stochastic processes, with applications to stochastic approximation](https://mlsanity.com/paper/2504.12922/) (2025)
- [A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps](https://mlsanity.com/paper/2608.15966/) (2026)
- [Mean-square and sublinear convergence of a stochastic proximal point algorithm in metric spaces of nonpositive curvature](https://mlsanity.com/paper/2510.10697/) (2025)
- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)

## Abstract (arXiv)

We provide abstract, general and highly uniform rates of asymptotic regularity for a generalized stochastic Halpern-style iteration, which incorporates a second mapping in the style of a Krasnoselskii-Mann iteration. This iteration is general in two ways: First, it incorporates stochasticity completely abstractly, rather than fixing a sampling method; second, it includes as special cases stochastic versions of various schemes from the optimization literature, including Halpern's iteration as well as a Krasnoselskii-Mann iteration with Tikhonov regularization terms in the sense of Boct, Csetnek and Meier (where this stochastic variant of the latter is considered for the first time in this paper). For these specific cases, we obtain linear rates of asymptotic regularity, matching (or improving) the currently best known rates for these iterations in stochastic optimization, and quadratic rates of asymptotic regularity are obtained in the context of inner product spaces for the general iteration. We conclude by discussing how variance can be managed in practice through sampling methods in the style of minibatching, how our convergence rates can be adapted to provide oracle complexity bounds, and by sketching how the schemes presented here can be instantiated in the context of reinforcement learning to yield novel methods for Q-learning.