Variance-Based Subgradient Extragradient Method for Stochastic Variational Inequality Problems

In this paper, we propose a variance-based subgradient extragradient algorithm with line search for stochastic variational inequality problems by aiming at robustness with respect to an unknown Lipschitz constant. This algorithm may be regarded as an integration of a subgradient extragradient algorithm for deterministic variational inequality problems and a stochastic approximation method for expected values. At each iteration, different from the conventional variance-based extragradient algorithms to take projection onto the feasible set twicely, our algorithm conducts a subgradient projection which can be calculated explicitly. Since our algorithm requires only one projection at each iteration, the computation load may be reduced. We discuss the asymptotic convergence, the sublinear convergence rate in terms of the mean natural residual function, and the optimal oracle complexity for the proposed algorithm. Furthermore, we establish the linear convergence rate with finite computational budget under both the strongly Minty variational inequality and the error bound condition. Preliminary numerical experiments indicate that the proposed algorithm is competitive with some existing methods.