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

In deterministic optimization, acceleration techniques like Halpern-type methods are well-understood and achieve optimal convergence rates. However, these methods are notoriously brittle when applied to stochastic settings, where oracle noise accumulates and destroys the accelerated convergence rate. The authors investigate whether alternative, non-unique forms of deterministic acceleration can be leveraged to create more robust stochastic algorithms that avoid the need for variance reduction or complex double-loop regularization.

The authors focus on the Dual-OHM (Dual Optimal Halpern Method), a variant of accelerated fixed-point iteration that shares the same deterministic convergence rate as standard anchor-based methods but possesses a different update structure. By analyzing the error propagation of this dual-anchor mechanism, the authors demonstrate that it is intrinsically less sensitive to stochastic perturbations. They propose the Stochastic Dual-OHM (S-Dual-OHM) and provide a convergence analysis showing that it maintains optimal performance in the presence of noise using only constant mini-batch sizes.

• Efficiency: S-Dual-OHM achieves an O(ε⁻³) oracle complexity for stochastic root-finding problems under cocoercivity in expectation, without relying on variance reduction or recursive regularization.
• Strong Monotonicity: When the operator is strongly monotone, the algorithm achieves a sharper Õ(ε⁻²) complexity through early stopping, which is near-optimal.
• Robustness: The authors provide a theoretical explanation for why the dual-anchor mechanism is more stable than standard anchor-based methods: the accumulation of stochastic errors in the dual-anchor update is controllable and does not scale with the square of the iteration count, unlike standard Halpern-type methods.