Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities

We consider stochastic variational inequalities (VIs) with monotone operators where the feasible set is an intersection of a large number of convex sets. We propose a stochastic approximation method with incremental constraint projections, meaning that a projection method is taken after the random operator is sampled and a component of the feasible set is randomly chosen. Such a sequential scheme is well suited for large-scale online and distributed learning. First, we assume that the VI is weak sharp. We provide asymptotic convergence, infeasibility rate of O (1/ k ) in terms of the squared distance to the feasible set, and solvability rate of O ( 1 / k ) in terms of the distance to the solution set for a bounded or unbounded set. Then, we assume just a monotone operator and introduce an explicit iterative Tykhonov regularization to the method. We consider Cartesian VIs so as to encompass the distributed solution of multiagent problems under a limited coordination. We provide asymptotic convergence, infeasibility rate of O (1/ k ) in terms of the squared distance to the feasible set and, in the case of a compact feasible set (with possibly unbounded components), we obtain a near-optimal solvability convergence rate of O ( k δ / k ) in terms of the dual gap function for any small δ ∈ ( 0 , 1 2 ) .