Stochastic Linesearch Methods for Stochastic Variational Inequality Problems: Parameter-Free Schemes and Non-Monotone Variants
Abstract
Much of the existing convergence guarantees and rate statements for stochastic variational inequality (SVI) problems are limited to stochastic approximation schemes that employ constant or diminishing steplength sequences bounded by some reciprocal of the Lipschitz constant L of the map. This requires both knowing such constants and may lead to debilitatingly small steplengths, afflicting the scheme with potentially poor performance. We propose a parameter-free stochastic extragradient method with periodically restarted linesearch (\textbf{SEG-LS}) for solving pseudomonotone and monotone SVI problems. The resulting stepsize sequence is neither monotone nor requires prior knowledge of the Lipschitz constant L. We show that the iteration and sample complexities for computing a point whose residual has norm at most ε in expectation are 𝒪(ε−2) and 𝒪(ε−4), respectively. These results improve to 𝒪(ε−1) and 𝒪(ε−2) in the monotone setting. In addition, we propose a periodically restarted biased stochastic linesearch method (\textbf{B-SLAM}) for solving non-monotone SVIs under strict copositivity. The resulting iteration and sample complexities are 𝒪(ε−2) and 𝒪(ε−4), respectively. Preliminary numerics support these findings and display promise.
Related
- A Stochastic LineseArch Method (SLAM) for Minimizing Expectation Residuals: Weakening Boundedness of Gradient
- Dynamics of Stochastic Hamiltonian systems I - Wong-Zakai Variational integrators
- Geometry property of stochastic parabolic equations and Prékopa-Leindler inequality on bounded domains
- Bi-parameter local linearization for the stochastic wave equation with rough noise
- Exact temporal variations and parameter estimation for space--time fractional stochastic heat equations driven by multiplicative noise
BibTeX
@misc{xiao2026stochastic,
title = {{Stochastic Linesearch Methods for Stochastic Variational Inequality Problems: Parameter-Free Schemes and Non-Monotone Variants}},
author = {Zhuoyu Xiao and Uday V. Shanbhag and Yue Xie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41065},
eprint = {2610.41065},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41065},
}
RIS
TY - UNPB
TI - Stochastic Linesearch Methods for Stochastic Variational Inequality Problems: Parameter-Free Schemes and Non-Monotone Variants
AU - Zhuoyu Xiao
AU - Uday V. Shanbhag
AU - Yue Xie
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.41065
UR - https://arxiv.org/abs/2610.41065
AB - Much of the existing convergence guarantees and rate statements for stochastic variational inequality (SVI) problems are limited to stochastic approximation schemes that employ constant or diminishing steplength sequences bounded by some reciprocal of the Lipschitz constant L of the map. This requires both knowing such constants and may lead to debilitatingly small steplengths, afflicting the scheme with potentially poor performance. We propose a parameter-free stochastic extragradient method with periodically restarted linesearch (\textbf{SEG-LS}) for solving pseudomonotone and monotone SVI problems. The resulting stepsize sequence is neither monotone nor requires prior knowledge of the Lipschitz constant L. We show that the iteration and sample complexities for computing a point whose residual has norm at most ε in expectation are 𝒪(ε^−2) and 𝒪(ε^−4), respectively. These results improve to 𝒪(ε^−1) and 𝒪(ε^−2) in the monotone setting. In addition, we propose a periodically restarted biased stochastic linesearch method (\textbf{B-SLAM}) for solving non-monotone SVIs under strict copositivity. The resulting iteration and sample complexities are 𝒪(ε^−2) and 𝒪(ε^−4), respectively. Preliminary numerics support these findings and display promise.
ER -