Metraipolis › archive › dc_cecddc30acc6

Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries — arXiv:2609.35631

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35631
License (as archived)
CC0-1.0
Archived
2026-10-07T23:06:50.678Z
SHA-256 of the archived text
81433958b8ee32146e42c56c4613ae2220da568e0ef8bca5997aef7d28f67cd3
Stable URL of this page
https://metraipolis.com/documento/dc_cecddc30acc6

How to cite

Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries — arXiv:2609.35631 — arXiv (en), https://arxiv.org/abs/2609.35631 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cecddc30acc6 (Metraipolis archive dc_cecddc30acc6, sha256 81433958b8ee32146e42c56c4613ae2220da568e0ef8bca5997aef7d28f67cd3)
BibTeX
@misc{dccecddc30acc6,
  title = {Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries — arXiv:2609.35631},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35631},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cecddc30acc6; sha256 81433958b8ee32146e42c56c4613ae2220da568e0ef8bca5997aef7d28f67cd3},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35631. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study acceleration of stochastic first-order methods for monotone Lipschitz inclusions with a fixed number of oracle queries per iteration, measured by the expected squared residual. Existing methods either have suboptimal oracle complexity, require an increasing number of oracle queries per iteration, or both. Under same-sample oracle access and mean-square Lipschitz stochastic noise, we develop variance-reduced anchored forward-backward (VRAF), an anytime composite method that makes two oracle queries per iteration. VRAF attains the first log-free $O(1/\epsilon)$ complexity under these oracle assumptions and hence the optimal $O(\sigma^2/\epsilon)$ variance dependence. This, however, leaves open whether the optimal $O(1/\sqrt{\epsilon})$ deterministic term can also be attained. We establish an impossibility result by extending the lower bound of Foster et al. (2019) to stochastic oracles permitting repeated queries to sampled stochastic operators, showing that $O(LD/\sqrt{\epsilon}+\sigma^2/\epsilon)$ oracle complexity is unattainable in general. We therefore develop recentered regularized stochastic extragradient (RRSEG), which attains the near-optimal oracle complexity previously achievable only with an increasing number of queries per iteration, while using a fixed number of queries.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.35631 — 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-07T22:42:39.289Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).