On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems

DOI10.1007/S11228-021-00572-6zbMATH Open1473.90097arXiv1904.11076OpenAlexW3156816032MaRDI QIDQ2045192FDOQ2045192

Shisheng Cui, Uday V. Shanbhag

Publication date: 12 August 2021

Published in: Set-Valued and Variational Analysis (Search for Journal in Brave)

Abstract: Classical extragradient schemes and their stochastic counterpart represent a cornerstone for resolving monotone variational inequality problems. Yet, such schemes have a per-iteration complexity of two projections onto a convex set and require two evaluations of the map, the former of which could be relatively expensive if $X$ is a complicated set. We consider two related avenues where the per-iteration complexity is significantly reduced: (i) A stochastic projected reflected gradient method requiring a single evaluation of the map and a single projection; and (ii) A stochastic subgradient extragradient method that requires two evaluations of the map, a single projection onto $X$, and a significantly cheaper projection (onto a halfspace) computable in closed form. Under a variance-reduced framework reliant on a sample-average of the map based on an increasing batch-size, we prove almost sure (a.s.) convergence of the iterates to a random point in the solution set for both schemes. Additionally, both schemes display a non-asymptotic rate of $mathcalO(1/K)$ where $K$ denotes the number of iterations; notably, both rates match those obtained in deterministic regimes. To address feasibility sets given by the intersection of a large number of convex constraints, we adapt both of the aforementioned schemes to a random projection framework. We then show that the random projection analogs of both schemes also display a.s. convergence under a weak-sharpness requirement; furthermore, without imposing the weak-sharpness requirement, both schemes are characterized by a provable rate of $mathcalO(1/sqrtK)$ in terms of the gap function of the projection of the averaged sequence onto $X$ as well as the infeasibility of this sequence. Preliminary numerics support theoretical findings and the schemes outperform standard extragradient schemes in terms of the per-iteration complexity.

Full work available at URL: https://arxiv.org/abs/1904.11076

Recommendations

• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
• Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities

zbMATH Keywords

stochastic approximationstochastic optimizationvariational inequality problemsextragradient schemes

Mathematics Subject Classification ID

Convex programming (90C25) Stochastic programming (90C15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cites Work

• Variational Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• A Stochastic Approximation Method
• Robust Stochastic Approximation Approach to Stochastic Programming
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Generalized Nash equilibrium problems
• Title not available (Why is that?)
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Introduction to Stochastic Programming
• SAMPLE AVERAGE APPROXIMATION METHODS FOR A CLASS OF STOCHASTIC VARIATIONAL INEQUALITY PROBLEMS
• Title not available (Why is that?)
• Stochastic Approximation Approaches to the Stochastic Variational Inequality Problem
• The subgradient extragradient method for solving variational inequalities in Hilbert space
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• Equilibrium models and variational inequalities.
• Incremental constraint projection methods for variational inequalities
• Stochastic variational inequalities: residual minimization smoothing sample average approximations
• Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
• Lectures on stochastic programming. Modeling and theory.
• Incremental proximal methods for large scale convex optimization
• On the existence of solutions to stochastic quasi-variational inequality and complementarity problems
• Addressing supply-side risk in uncertain power markets: stochastic Nash models, scalable algorithms and error analysis
• Random algorithms for convex minimization problems
• Projected Reflected Gradient Methods for Monotone Variational Inequalities
• Stochastic first-order methods with random constraint projection
• Temporal Difference Methods for General Projected Equations
• Distributed Computation of Equilibria in Monotone Nash Games via Iterative Regularization Techniques
• On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators
• Accelerated schemes for a class of variational inequalities
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• Self-Tuned Stochastic Approximation Schemes for Non-Lipschitzian Stochastic Multi-User Optimization and Nash Games
• Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
• On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
• Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Convergence Rate of $\mathcal{O}(1/k)$ for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems
• Corrections to “A High-Order Internal Model Based Iterative Learning Control Scheme for Nonlinear Systems With Time-Iteration-Varying Parameters”

Cited In (13)

• Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities
• Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
• Self adaptive inertial subgradient extragradient algorithms for solving pseudomonotone variational inequality problems
• Dynamic stochastic projection method for multistage stochastic variational inequalities
• Two fast variance-reduced proximal gradient algorithms for SMVIPs -- stochastic mixed variational inequality problems with suitable applications to stochastic network games and traffic assignment problems
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• Stochastic approximation for estimating the price of stability in stochastic Nash games
• Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
• Simple and Optimal Methods for Stochastic Variational Inequalities, I: Operator Extrapolation
• Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
• Variance-based stochastic projection gradient method for two-stage co-coercive stochastic variational inequalities
• Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
• Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities

Uses Software

• Saga

This page was built for publication: On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045192)