Incremental constraint projection methods for monotone stochastic variational inequalities

Abstract

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