Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries

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. We develop variance-reduced anchored forward-backward (VRAF), an anytime and composite method that makes two oracle queries per iteration, both using the same sampled stochastic operator. VRAF attains $O(1/ϵ)$ oracle complexity, thereby achieving the optimal $O({\sigma }^2/ϵ)$ dependence on the stochastic operator variance for the first time, even among methods allowing an increasing number of queries. 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{ϵ}+{\sigma }^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.