Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems

We consider stochastic variational inequality problems where the mapping is monotone over a compact convex set. We present two robust variants of stochastic extragradient algorithms for solving such problems. Of these, the first scheme employs an iterative averaging technique where we consider a generalized choice for the weights in the averaged sequence. Our first contribution is to show that using an appropriate choice for these weights, a suitably defined gap function attains the optimal rate of convergence of O(1 over √k). In the second part of the paper, under an additional assumption of weak-sharpness, we update the stepsize sequence using a recursive rule that leverages problem parameters. The second contribution lies in showing that employing such a sequence, the extragradient algorithm possesses almost-sure convergence to the solution as well as convergence in a mean-squared sense to the solution of the problem at the rate O(1 over k). Motivated by the absence of a Lipschitzian parameter, in both schemes we utilize a locally randomized smoothing scheme. Importantly, by approximating a smooth mapping, this scheme enables us to estimate the Lipschitzian parameter. The smoothing parameter is updated per iteration and we show convergence to the solution of the original problem in both algorithms.

I. Introduction

Variational inequality problems (VI) were first introduced in mid-1960s, motivated by the elastostatic equilibrium prob-lems. During the past five decades, this subject has been a powerful framework in modeling a wide range of optimization and equilibrium problems in operations research, engineering, finance, and economics (cf. [1], [2]). Given a set and a mapping , a VI problem, denoted by VI , requires determining an such that for any . In this paper, our interest lies in computation of solutions to VIs with uncertain settings. We consider the case where represents the expected value of a stochastic mapping , i.e., where is a -dimensional random variable and denotes the associated probability space. Consequently, solves VI if

$${\rm E}[\Phi(x^{\ast}, \xi(\omega))]^{T}(x-x^{\ast})\geq 0,\ {\rm for\ every}\ x\in X.\eqno{\hbox{(1)}}$$