Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities

Alfredo N. Iusem (), Alejandro Jofré () and Philip Thompson ()
Additional contact information
Alfredo N. Iusem: Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, RJ, Brazil
Alejandro Jofré: Centro de Modelamiento Matemático (CMM and DIM), Universidad de Chile, Santiago de Chile, Chile
Philip Thompson: Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, RJ, Brazil

Mathematics of Operations Research, 2019, vol. 44, issue 1, 236-263

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 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 ) .

Keywords: stochastic variational inequalities; projection method; stochastic approximation; incremental methods; randomized algorithms; weak sharpness; Tykhonov regularization (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0922 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:44:y:2019:i:1:p:236-263

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().