Solving variational inequalities with stochastic mirror-prox algorithm

Abstract

In this paper we consider iterative methods for stochastic variational\ninequalities (s.v.i.) with monotone operators. Our basic assumption is that the\noperator possesses both smooth and nonsmooth components. Further, only noisy\nobservations of the problem data are available. We develop a novel Stochastic\nMirror-Prox (SMP) algorithm for solving s.v.i. and show that with the\nconvenient stepsize strategy it attains the optimal rates of convergence with\nrespect to the problem parameters. We apply the SMP algorithm to Stochastic\ncomposite minimization and describe particular applications to Stochastic\nSemidefinite Feasability problem and Eigenvalue minimization.\n