Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
To resolve the trade-off between suboptimal oracle complexity and growing per-iteration query budgets in stochastic monotone inclusions, this work establishes accelerated methods operating with a fixed number of queries per step. The authors show that their variance-reduced anchored forward-backward (VRAF) algorithm achieves the first log-free $O(1/\epsilon)$ rate with optimal variance dependence, while proving via an extended lower bound that the ideal accelerated deterministic rate $O(LD/\sqrt{\epsilon} + \sigma^2/\epsilon)$ is fundamentally unattainable under same-sample oracles. Finally, they provide a recentered regularized stochastic extragradient (RRSEG) method that matches the near-optimal complexity previously restricted to growing-batch regimes using only fixed per-iteration queries.
Achieving the textbook $O(1/\sqrt{\epsilon})$ deterministic acceleration alongside optimal variance reduction is fundamentally impossible for stochastic monotone inclusions with fixed query budgets, overturning a standard assumption in non-convex min-max optimization.
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/\sqrtε)$ 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ε+σ^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.