Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding

arXiv:2609.36033v1 Announce Type: cross Abstract: Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee has two limitations: first, it requires cocoercivity in expectation, and second, it attains only O(epsilon^{-3}) oracle complexity, leaving a gap to the near-optimal ilde{O}(epsilon^{-2}) complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by sigma^2, where sample operators are monotone and uniformly L-Lipschitz, our algorithm finds a point with epsilon-residual with a near-optimal oracle complexity of O ( (LD / epsilon) ell + (sigma^2 / epsilon^2) ell^2), where ell = log (1 + LD / epsilon) and D is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.

Source: arXiv cs.LG | 2026-09-30

Related