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

The paper addresses stochastic root-finding problems, stated as finding x ∈ R d such that F(x) = 0, where F is an operator. The authors note that while accelerated deterministic root-finding methods (specifically anchor-based or Halpern-type methods) achieve optimal convergence rates, 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.

The key insight is 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.

The paper proposes the Stochastic Dual Optimal Halpern Method (S-Dual-OHM) with the update rule:

xk+1 = xk + (N−k−1)/(N−k) [TBk(xk) − TBk−1(xk−1)]

where TBk = I − αFBk with mini-batched stochastic operator evaluations.

Under Assumptions 3.1 (unbiased stochastic oracle with bounded variance σ2) and 3.2 (cocoercivity in expectation), with step-size 0 < α ≤ 2/L and constant batch size B, the algorithm achieves:

E[∥F(xN−1)∥] ≤ 4∥x0−x⋆∥2/(α2N2) + 6σ2/B

This yields:

• O(ϵ−3) total oracle complexity with N = O(ϵ−1) iterations and B = O(ϵ−2) batch size

• Achieved without any variance reduction or double-loop recursive regularization

• This complexity has not been achieved in prior work without variance reduction or double-loop regularization techniques (see Table 1 comparison)

When F is additionally µ-strongly monotone, the same algorithm can be early-stopped in k = Õ(L/µ log ϵ−1) iterations to attain E[∥F(xk)∥] ≤ ϵ, yielding oracle complexity Õ(ϵ−2), which has near-optimal dependence on ϵ.

The paper provides intuition for why the dual-anchor mechanism is more robust than anchor-based methods:

1. Error accumulation analysis: For S-Dual-OHM, the net accumulation of error is proportional to ΣλN,j = α(N−1)/2 = O(N), which is controllable. In contrast, for stochastic OHM, the error terms get multiplied by weights summing to Θ(N2), making the error no longer controllable.

2. Anytime vs. fixed-horizon distinction: OHM is an anytime optimal algorithm, achieving the rate ∥F(xk−1)∥ ≤ 4∥x0−x⋆∥2/(α2k2) for all k = 1, 2,... This forces it to exploit the geometric property of F, i.e. cocoercivity, throughout the trajectory and makes it more easily disrupted by oracle noise. Dual-OHM, by contrast, is optimized only for the prescribed last iterate and does not suffer from the same accumulation of errors.

• Lemma 4.2: Provides an algebraic identity characterizing S-Dual-OHM that does not use any properties of F or stochastic assumptions

• Lemma 4.3: Isolates the dependence on stochastic errors at each iteration

• Lemma 4.4: Shows that error propagation to the last iterate is uniformly bounded by a constant independent of N

• Lemma 4.6 (Leave-one-out stability): Shows that replacing one minibatch with an independent copy changes the terminal iterate by at most α2σ2/B in expectation

• Lemma 4.7: Shows deterministic Dual-OHM converges linearly to its final iterate when T is contractive

The paper validates the theory on three problems:

1. Worst-case nonexpansive operator (from [40]): S-Dual-OHM achieves the smallest last-iterate residual, while S-OHM with constant batch size fails to converge and exhibits diverging residual

2. Finite-sum cocoercive operator: S-Dual-OHM outperforms its primal counterpart S-OHM

3. SCSC minimax problem with Huber-type regularizers: In low-variance regime (σ=0.05), S-Dual-OHM shows rapid early progress but stagnates; in high-variance regime (σ=1.5), mini-batching becomes effective and S-Dual-OHM exhibits comparable performance to classical methods and deliberately designed near-optimal algorithm RAIN

The paper states: "It challenges the folklore view that acceleration, as studied in deterministic optimization, is brittle and incompatible with stochastic noise. Equivalently, optimal deterministic methods can behave very differently under stochastic perturbations, and selecting the right representation of acceleration may enable the design of efficient stochastic algorithms."

Two limitations are noted:

1. Whether the dual-anchor mechanism extends to root-finding with monotone and Lipschitz operators (not just cocoercive)

2. Whether complexity can be improved to the optimal level O(ϵ−2 log ϵ−1) via dual-anchor acceleration

Based on this paper, I can improve AI systems in the following specific ways:

Improvement: Replace anchor-based acceleration (which accumulates errors under stochastic noise) with dual-anchor mechanisms in AI systems that rely on stochastic gradient-based optimization.

What the improved AI system can do:

• Maintain fast convergence rates (O(ε−3) oracle complexity) even when gradient estimates are noisy, without requiring variance reduction techniques

• Handle mini-batch stochastic updates with constant batch sizes without diverging, unlike current anchor-based methods

• Operate effectively in reinforcement learning and online learning settings where noise is inherent

Improvement: Implement the optimized for prescribed last iterate design principle, where the algorithm is tuned for a specific iteration horizon rather than being anytime-optimal.

Improvement: Use the leave-one-out stability lemma (Lemma 4.6) to design AI systems that are robust to individual batch perturbations.

Improvement: Apply the dual-anchor mechanism to SCSC (strongly-convex-strongly-concave) minimax problems with stochastic oracles, as validated in the paper's experiments.

Improvement: Exploit the cocoercivity-in-expectation assumption (Assumption 3.2) to design AI systems that leverage geometric properties of the loss landscape.

Improvement: Use the insight that dual-anchor methods have error accumulation proportional to O(N) rather than O(N2), making them suitable for long training runs.

Improvement: Implement a meta-learning framework that switches between anchor-based (anytime) and dual-anchor (fixed-horizon) methods based on measured noise variance.

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(epsilon-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 (epsilon-2) complexity, nearly matching the lower bound in terms of epsilon-dependence.