mlsanityData to 13 Oct 2026

Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization

arXiv 2608.12043 ↗First posted 12 Aug 2026math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Acceleration for deterministic root-finding problems has been extensively studied in recent years; specifically, the anchor-based, or Halpern-type methods achieve optimal convergence rates with respect to the operator norm. However, acceleration via these methods does not directly carry over to stochastic setting due to accumulation of errors, unless one enforces diminishing variance via increasing batch sizes or variance reduction techniques. In this work, we show that another class of acceleration, namely the dual-anchor mechanism, extends to the stochastic setting without such error accumulation, in contrast to anchor-based algorithms. Consequently, we cleanly achieve O(ε-3) complexity with iteration-independent batch size, without any variance reduction or double-loop recursive regularization, for stochastic root-finding (resp. fixed-point) problems with cocoercivity (resp. square-nonexpansivity) in expectation. For strongly monotone operators, the same algorithm attains a sharper widetildeO (ε-2) complexity, nearly matching the lower bound in terms of ε-dependence.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Builds on 39 of its 58 references that are in the map. First posted on arXiv 12 Aug 2026.

Builds on

39 of 58 references.

References · 39

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,379
  2. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  3. 2017Training GANs with Optimismcited by 217
  4. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  5. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 134
  6. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  7. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 118
  8. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  9. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 72
  10. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  11. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  12. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
27 more
  1. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  2. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  3. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  4. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  5. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  6. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 24
  7. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 23
  8. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 20
  9. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  10. 2022From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problemscited by 19
  11. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 18
  12. 2019ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problemscited by 16
  13. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 12
  14. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  15. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  16. 2022Fast Optimistic Gradient Descent Ascent (OGDA) method in continuous and discrete timecited by 10
  17. 2023Accelerating Value Iteration with Anchoringcited by 10
  18. 2022Accelerated Minimax Algorithms Flock Togethercited by 9
  19. 2024Optimal Acceleration for Minimax and Fixed-Point Problems is Not Uniquecited by 7
  20. 2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
  21. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  22. 2023Continuous-time Analysis of Anchor Accelerationcited by 4
  23. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  24. 2026A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithmscited by 4
  25. 2025H-invariance theory: A complete characterization of minimax optimal fixed-point algorithmscited by 3
  26. 2019Cocoercivity, Smoothness and Bias in Variance-Reduced Stochastic Gradient Methodscited by 2
  27. 2023Moving Anchor Extragradient Methods For Smooth Structured Minimax Problemscited by 2

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0
  2. 2026Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexitycited by 0
  3. 2026Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Findingcited by 0
  4. 2026Optimal Oracle Complexity for Finite-Sum Monotone Inclusionscited by 0