Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries
Abstract
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/ε) complexity under these oracle assumptions and hence the optimal O(σ2/ε) variance dependence. This, however, leaves open whether the optimal O(1/√ε) 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/√ε+σ2/ε) 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.
Related
- Inexact Proximal Point and Tseng Algorithms with Nonsummable Errors to Solve Monotone Inclusions
- Distributed Fast Fixed-Point Algorithms for Composite Monotone Inclusions over Networks
- Accelerated Convergence of a Second-Order Dynamical System and its Application to Splitting Algorithms for Comonotone Inclusions
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Weak and strong convergence of a general splitting approach for monotone multioperator inclusions
BibTeX
@misc{lee2026accelerated,
title = {{Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries}},
author = {Sucheol Lee and Donghwan Kim},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35631},
eprint = {2609.35631},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35631},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries
AU - Sucheol Lee
AU - Donghwan Kim
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35631
UR - https://arxiv.org/abs/2609.35631
AB - 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/ε) complexity under these oracle assumptions and hence the optimal O(σ^2/ε) variance dependence. This, however, leaves open whether the optimal O(1/√ε) 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/√ε+σ^2/ε) 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.
ER -