Search papers, labs, and topics across Lattice.
This paper introduces a dual-anchor mechanism that enables efficient stochastic root-finding without the need for variance reduction or regularization techniques, which typically hinder performance due to error accumulation. The authors demonstrate that their approach achieves an optimal complexity of \(O(ε^{-3})\) for stochastic root-finding problems and \( \widetilde{O}(ε^{-2})\) for strongly monotone operators, significantly improving upon existing methods. This advancement is particularly notable as it allows for iteration-independent batch sizes, enhancing practical applicability in stochastic settings.
Achieving \(O(ε^{-3})\) complexity for stochastic root-finding without the usual variance reduction techniques could revolutionize the efficiency of numerical methods in uncertain environments.
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 $\widetilde{O} (ε^{-2})$ complexity, nearly matching the lower bound in terms of $ε$-dependence.
