🔢 mathematics

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

This paper introduces a dual-anchor mechanism that achieves optimal $O(\epsilon^{-3})$ and nearly optimal $\widetilde{O}(\epsilon^{-2})$ convergence rates for stochastic root-finding problems without requiring variance reduction, regularization, or increasing batch sizes, thereby overcoming the error accumulation limitations of traditional anchor-based acceleration methods.

Original authors: TaeHo Yoon, Nicolas Loizou

Published 2026-08-13

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: TaeHo Yoon, Nicolas Loizou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to set up a campfire in a vast, foggy forest. You know the fire needs to be exactly where the ground is flat and the wind is calm, but you can't see the whole forest at once. Every time you take a step, you ask a local guide for directions. Sometimes the guide is perfect, but often they are a bit tipsy or distracted, giving you directions that are slightly off. This is the world of stochastic root-finding: a branch of mathematics and computer science where algorithms try to find a specific solution (the "root") to a complex equation, but they only have access to noisy, imperfect information.

For years, scientists have been building "accelerated" algorithms—super-fast runners designed to reach the solution in record time. In a perfect, noise-free world (where the guides are always sober), these runners use a clever trick called acceleration to zoom past the slow-and-steady methods. However, there's a catch: when you add the foggy, noisy guides back into the mix, these super-fast runners tend to trip over their own feet. The tiny errors from the noisy guides pile up, causing the runner to spiral out of control or move so slowly that the speed advantage disappears. To fix this, previous methods required the runners to stop frequently to "clean their glasses" (using complex variance reduction) or to take smaller, safer steps, which slowed them down again. The big question was: Is there a way to keep the super-fast speed even when the guides are noisy, without all that extra cleanup?

This paper introduces a new kind of runner called S-Dual-OHM that solves this problem. The authors discovered that while the traditional "fast runner" (known as the Halpern or anchor-based method) falls apart in the noise, there is a different, equally fast runner called the Dual-Anchor method that is intrinsically less sensitive to the chaos. Think of it like two different ways to balance on a tightrope. The old way (anchor-based) relies on holding a heavy pole that keeps you steady only if the wind is gentle; a sudden gust (noise) knocks you off. The new way (dual-anchor) is like a tightrope walker who uses a unique, self-correcting dance step. Even when the wind gusts, their specific rhythm absorbs the shock without losing balance, provided they use a constant batch size (taking a few samples at once to get a clearer direction) to dampen the initial gusts.

The researchers proved mathematically that this new S-Dual-OHM algorithm can find the solution with a level of accuracy called $\epsilon$ using roughly $O(\epsilon^{-3})$ steps. This is a massive improvement because it achieves this speed without needing the complex "cleaning" techniques (like variance reduction) or double-loop structures that previous methods required. Instead, it simply uses a constant batch size to keep the errors in check. It's like finding the campfire spot just as fast as the old super-runners, but without needing to stop and wipe the fog off your glasses every few seconds.

Furthermore, the paper shows that if the forest has a special property (where the ground slopes gently toward the fire, known as "strong monotonicity"), this new runner can be stopped even earlier, reaching the goal in roughly $O(\epsilon^{-2})$ steps. This is nearly the fastest speed theoretically possible.

To prove this wasn't just a lucky guess on paper, the authors ran computer simulations in three different "forests": one with a tricky, worst-case layout, one with a mix of random paths, and one with a complex game-like setup. In these tests, the old fast runners (like S-OHM) often got confused and their errors grew larger and larger, while the new S-Dual-OHM stayed steady and reached the target with the smallest error of all. The results suggest that by choosing the right "dance step" (the dual-anchor mechanism) and using a constant batch size to smooth out the noise, we can finally bring the speed of acceleration into the noisy, real-world problems that computers face every day, without needing to slow down to manage the noise.

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

Problem Statement
The paper addresses the stochastic root-finding problem for an operator $\mathbb{F}: \mathbb{R}^d \to \mathbb{R}^d$ , formulated as finding $x$ such that $\mathbb{F}(x) = 0$ . In the stochastic setting, the algorithm accesses an unbiased estimator $\hat{\mathbb{F}}(x; \xi)$ with bounded variance, where $\mathbb{F}(x) = \mathbb{E}[\hat{\mathbb{F}}(x; \xi)]$ . While deterministic acceleration methods (specifically anchor-based or Halpern-type methods) have achieved optimal convergence rates for root-finding and fixed-point problems, they are known to be brittle in stochastic settings. Previous attempts to extend these methods to the stochastic domain required diminishing variance (via increasing batch sizes), variance reduction techniques (e.g., PAGE), or double-loop regularization structures to prevent the accumulation of stochastic errors, which degrade the fast convergence rates.

Methodology
The authors propose the Stochastic Dual Optimal Halpern Method (S-Dual-OHM). This approach leverages the "dual-anchor" mechanism, a class of acceleration distinct from the standard anchor-based (Halpern) methods.

Algorithm Structure: Unlike the Halpern iteration (OHM), which is an "anytime" algorithm updating $x_{k+1} = \beta_k x_0 + (1-\beta_k)\mathbb{T}x_k$ at every step, Dual-OHM is optimized specifically for a fixed terminal iteration $N$ . The update rule is:
$x_{k+1} = x_k + \frac{N-k-1}{N-k} (\mathbb{T}_{B_k}x_k - \mathbb{T}_{B_{k-1}}x_{k-1})$
where $\mathbb{T} = \mathbb{I} - \alpha\mathbb{F}$ is a nonexpansive operator derived from the cocoercive $\mathbb{F}$ , and $\mathbb{T}_{B_k}$ is a mini-batch estimator.
Key Mechanism: The authors demonstrate that while deterministic OHM and Dual-OHM share the same optimal worst-case convergence rate, their behaviors diverge under stochastic noise. The analysis relies on an identity characterizing the error accumulation. In OHM, the weights associated with error terms sum to $\Theta(N^2)$ , leading to uncontrolled error accumulation unless variance is reduced. In contrast, for Dual-OHM, the sum of weights is $\Theta(N)$ , allowing the stochastic error to be uniformly bounded without requiring diminishing variance or complex variance reduction schemes.
Assumptions: The primary analysis assumes $\mathbb{F}$ is $1/L$ -cocoercive in expectation (Assumption 3.2) and utilizes a stochastic oracle with bounded variance (Assumption 3.1). For strongly monotone operators, the algorithm utilizes early stopping.

Key Contributions and Results

Complexity without Variance Reduction: The paper establishes that S-Dual-OHM achieves an expected residual bound $\mathbb{E}[\|\mathbb{F}(x_{N-1})\|] \leq \epsilon$ with:
- Iteration complexity: $N = O(\epsilon^{-1})$ .
- Batch size: Constant $B = O(\epsilon^{-2})$ .
- Total oracle complexity: $O(\epsilon^{-3})$ .
  Crucially, this is achieved without variance reduction techniques, double-loop regularization, or diminishing batch sizes, which were previously considered necessary for stochastic acceleration.
Strongly Monotone Case: When $\mathbb{F}$ is additionally $\mu$ -strongly monotone, the algorithm can be early-stopped. This yields a complexity of $\tilde{O}(\epsilon^{-2})$ , which nearly matches the known lower bound in terms of $\epsilon$ -dependence, though the dependence on the condition number remains suboptimal.
Robustness to Noise: Theoretical analysis and numerical experiments confirm that the dual-anchor mechanism is intrinsically more robust to stochastic perturbations than the standard anchor-based (Halpern) mechanism. While S-OHM (Stochastic OHM) with constant batch sizes fails to converge (exhibiting diverging residuals), S-Dual-OHM maintains stability.
Empirical Validation: Experiments on worst-case nonexpansive operators, finite-sum cocoercive operators, and strongly-convex-strongly-concave minimax problems demonstrate that S-Dual-OHM outperforms S-OHM and achieves competitive performance against state-of-the-art algorithms like Halpern-PAGE and RAIN, particularly in high-noise regimes.

Significance and Claims
The paper claims a conceptual shift in the understanding of acceleration in stochastic settings. It challenges the folklore view that deterministic acceleration is inherently incompatible with stochastic noise. The authors argue that the brittleness of methods like Halpern iteration is not a fundamental limitation of acceleration itself, but rather a specific vulnerability of the anchor-based representation. By identifying that distinct deterministic accelerations (specifically Dual-OHM) exist which share the same optimal deterministic rates but possess different stability properties under noise, the work enables the design of efficient stochastic algorithms that do not rely on the heavy machinery of variance reduction or recursive regularization.

The authors position this work as a baseline for future research, noting open questions regarding the extension of the dual-anchor mechanism to general monotone and Lipschitz operators (without cocoercivity) and whether the complexity can be further improved to the optimal $O(\epsilon^{-2} \log \epsilon^{-1})$ level.

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

More like this