Computation of Strong Solutions to Stochastic Variational Inequalities
Abstract
This paper studies the computation of strong solutions of monotone variational inequalities (VIs) with Lipschitz continuous operators. Building on the idea of accumulative regularization (AR), 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 ε using at most $ \widetilde{\mathcal{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 D0 bounds the initial distance to the solution. This substantially improves the existing 𝒪( σ2/ε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. We apply these results to policy evaluation in reinforcement learning, where we show that estimators of the projected Bellman operator satisfy our state-dependent noise condition. To the best of our knowledge, the AR framework, the improved complexity under uniformly bounded noise, the state-dependent noise model and its guarantees, the adaptivity to an unknown strong monotonicity modulus, and the improved guarantees for FTD learning are all new in the VI literature.
Related
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Numerical approximation of probabilistically strong solutions to the stochastic harmonic map heat flow
- Sharp logarithmic Sobolev inequalities on free groups by variational comparison
- Lp-Integral Affine Surface Area-Variational Capacity Inequalities
- Some Properties of Mordukhovich Derivatives with Applications to Locally Variational Inequalities in Banach Spaces
BibTeX
@misc{ji2026computation,
title = {{Computation of Strong Solutions to Stochastic Variational Inequalities}},
author = {Yao Ji and Guanghui Lan and Jason Zhu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04188},
eprint = {2609.04188},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04188},
}
RIS
TY - UNPB
TI - Computation of Strong Solutions to Stochastic Variational Inequalities
AU - Yao Ji
AU - Guanghui Lan
AU - Jason Zhu
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.04188
UR - https://arxiv.org/abs/2609.04188
AB - This paper studies the computation of strong solutions of monotone variational inequalities (VIs) with Lipschitz continuous operators. Building on the idea of accumulative regularization (AR), 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 ε using at most $ \widetilde{\mathcal{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. This substantially improves the existing 𝒪( σ^2/ε^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. We apply these results to policy evaluation in reinforcement learning, where we show that estimators of the projected Bellman operator satisfy our state-dependent noise condition. To the best of our knowledge, the AR framework, the improved complexity under uniformly bounded noise, the state-dependent noise model and its guarantees, the adaptivity to an unknown strong monotonicity modulus, and the improved guarantees for FTD learning are all new in the VI literature.
ER -