This paper studies the computation of strong solutions of monotone variational inequalities (VIs) with Lipschitz continuous operators. Building on the idea of accumulative regularization, we develop a general framework for VIs, with particular emphasis on stochastic settings. Under unbiased stochastic oracles with uniformly bounded variance $ σ^2$, AR computes an approximate solution with expected operator residual bounded by $\varepsilon$ using at most $ \widetilde{O}\left(\tfrac{LD_0}{\varepsilon}+\tfrac{ σ^2}{\varepsilon^2}(\log\tfrac{LD_0}{\varepsilon})^3\right) $ stochastic oracle calls, where $L$ is the Lipschitz constant and $D_0$ bounds the initial distance to the solution. It substantially improves the existing $\mathcal{O}( σ^2/\varepsilon^4)$ complexity for residual reduction and matches the lower bound up to logarithmic factors. For strongly monotone VIs, measured by the distance to the solution, AR achieves the optimal oracle complexity when the strong monotonicity modulus is known. By treating the problem as merely monotone, AR still achieves nearly optimal complexity without knowledge of this modulus. We further introduce a state-dependent noise model applicable to general monotone VIs with potentially nonunique solutions, extending state-dependent noise analysis beyond the strongly monotone setting. Under this model, AR, when equipped with an enhanced stochastic operator extrapolation (SOE) method, achieves nearly optimal complexity with the stochastic term depending on the variance at a solution.
🌊
