Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities

• 成果类型: Article
• 署名作者: Iusem, Alfredo N.; Jofre, Alejandro; Thompson, Philip
• 署名单位: Instituto Nacional de Matematica Pura e Aplicada (IMPA); Universidad de Chile; Universidad de Chile
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0922
• 发表日期: 2019
• 页码: 236-263
• 关键词: approximation methods; CONVERGENCE; regularization; algorithm; schemes; systems

摘要

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/root 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(delta)/root K) in terms of the dual gap function for any small delta is an element of (0,1/2).