Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding
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(ε−3) oracle complexity, leaving a gap to the near-optimal Õ(ε−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 σ2, where sample operators are monotone and uniformly L-Lipschitz, our algorithm finds a point with ε-residual with a near-optimal oracle complexity of O ( (LD / ε) ℓ + (σ2 / ε2) ℓ2), where ℓ = log (1 + LD / ε) 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.
Related
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
- Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration
- Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
- Single-call Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
- Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
BibTeX
@misc{yoon2026dualanchor,
title = {{Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding}},
author = {TaeHo Yoon and Nicolas Loizou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36033},
eprint = {2609.36033},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36033},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding
AU - TaeHo Yoon
AU - Nicolas Loizou
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.36033
UR - https://arxiv.org/abs/2609.36033
AB - 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(ε^−3) oracle complexity, leaving a gap to the near-optimal Õ(ε^−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 σ^2, where sample operators are monotone and uniformly L-Lipschitz, our algorithm finds a point with ε-residual with a near-optimal oracle complexity of O ( (LD / ε) ℓ + (σ^2 / ε^2) ℓ^2), where ℓ = log (1 + LD / ε) 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.
ER -