Metraipolis › archive › dc_7b6c69e676dd
Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding — arXiv:2609.36033
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.36033
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T17:32:28.588Z
- SHA-256 of the archived text
db8e7bbc337f20cdad6d058117e1d64bd9de067e837bc04aaa9968f2fa2bd3bf- Stable URL of this page
https://metraipolis.com/documento/dc_7b6c69e676dd
How to cite
Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding — arXiv:2609.36033 — arXiv (en), https://arxiv.org/abs/2609.36033 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7b6c69e676dd (Metraipolis archive dc_7b6c69e676dd, sha256 db8e7bbc337f20cdad6d058117e1d64bd9de067e837bc04aaa9968f2fa2bd3bf)
BibTeX
@misc{dc7b6c69e676dd,
title = {Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding — arXiv:2609.36033},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.36033},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7b6c69e676dd; sha256 db8e7bbc337f20cdad6d058117e1d64bd9de067e837bc04aaa9968f2fa2bd3bf},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36033. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\tilde{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.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-30 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.36033 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T16:59:48.466Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).