Extragradient Method with Variance Reduction for Stochastic Variational Inequalities

DOI10.1137/15M1031953zbMath1365.65179arXiv1703.00260OpenAlexW2593248927WikidataQ101496416 ScholiaQ101496416MaRDI QIDQ5737725

No author found.

Publication date: 30 May 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

convergencestochastic approximationvariance reductioncomplexity analysisextragradient methodpseudomonotonicitystochastic variational inequalities

Mathematics Subject Classification ID

Variational inequalities (49J40) Complexity and performance of numerical algorithms (65Y20) Existence of optimal solutions to problems involving randomness (49J55) Numerical methods for variational inequalities and related problems (65K15)

Related Items (48)

A variational inequality based stochastic approximation for estimating the flexural rigidity in random fourth-order models ⋮ New First-Order Algorithms for Stochastic Variational Inequalities ⋮ A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization ⋮ A self-adaptive stochastic subgradient extragradient algorithm for the stochastic pseudomonotone variational inequality problem with application ⋮ Distributed Variable Sample-Size Gradient-Response and Best-Response Schemes for Stochastic Nash Equilibrium Problems ⋮ Minibatch Forward-Backward-Forward Methods for Solving Stochastic Variational Inequalities ⋮ Two Steps at a Time---Taking GAN Training in Stride with Tseng's Method ⋮ An iteratively regularized stochastic gradient method for estimating a random parameter in a stochastic PDE. A variational inequality approach ⋮ 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 ⋮ Simple and Optimal Methods for Stochastic Variational Inequalities, I: Operator Extrapolation ⋮ Hybrid SGD algorithms to solve stochastic composite optimization problems with application in sparse portfolio selection problems ⋮ Data perturbations in stochastic generalized equations: statistical robustness in static and sample average approximated models ⋮ Improved variance reduction extragradient method with line search for stochastic variational inequalities ⋮ A framework of convergence analysis of mini-batch stochastic projected gradient methods ⋮ Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities ⋮ A new regularized stochastic approximation framework for stochastic inverse problems ⋮ Stochastic regularized Newton methods for nonlinear equations ⋮ A stochastic projection and contraction algorithm with inertial effects for stochastic variational inequalities ⋮ Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games ⋮ Modified Stochastic Extragradient Methods for Stochastic Variational Inequality ⋮ A random elastic traffic equilibrium problem via stochastic quasi-variational inequalities ⋮ On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes ⋮ Variance-Based Extragradient Methods with Line Search for Stochastic Variational Inequalities ⋮ String-averaging incremental stochastic subgradient algorithms ⋮ Forward-reflected-backward method with variance reduction ⋮ Infeasible interior-point algorithms based on sampling average approximations for a class of stochastic complementarity problems and their applications ⋮ On variance reduction for stochastic smooth convex optimization with multiplicative noise ⋮ Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging ⋮ A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints ⋮ An infeasible stochastic approximation and projection algorithm for stochastic variational inequalities ⋮ Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants ⋮ A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods ⋮ Inexact stochastic subgradient projection method for stochastic equilibrium problems with nonmonotone bifunctions: application to expected risk minimization in machine learning ⋮ On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems ⋮ Variance-based subgradient extragradient method for stochastic variational inequality problems ⋮ A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization ⋮ Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise ⋮ MultiLevel Composite Stochastic Optimization via Nested Variance Reduction ⋮ Stochastic generalized Nash equilibrium seeking under partial-decision information ⋮ A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization ⋮ A regularized stochastic subgradient projection method for an optimal control problem in a stochastic partial differential equation ⋮ On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization ⋮ Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces ⋮ Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization ⋮ Unnamed Item ⋮ A Hybrid Newton Method for Stochastic Variational Inequality Problems and Application to Traffic Equilibrium ⋮ Stochastic Approximation Methods for the Two-Stage Stochastic Linear Complementarity Problem ⋮ A random time-dependent noncooperative equilibrium problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual subgradient methods for convex problems
• Sample size selection in optimization methods for machine learning
• Equilibrium models and variational inequalities.
• Variable-number sample-path optimization
• Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming
• Enlargement of monotone operators with applications to variational inequalities
• Sample-path solution of stochastic variational inequalities
• On the existence of solutions to stochastic quasi-variational inequality and complementarity problems
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• Incremental constraint projection methods for variational inequalities
• Stochastic Nash equilibrium problems: sample average approximation and applications
• Stochastic Variational Inequalities: Residual Minimization Smoothing Sample Average Approximations
• Randomized Smoothing for Stochastic Optimization
• Self-Tuned Stochastic Approximation Schemes for Non-Lipschitzian Stochastic Multi-User Optimization and Nash Games
• On the Complexity of the Hybrid Proximal Extragradient Method for the Iterates and the Ergodic Mean
• Complexity of Variants of Tseng's Modified F-B Splitting and Korpelevich's Methods for Hemivariational Inequalities with Applications to Saddle-point and Convex Optimization Problems
• SAMPLE AVERAGE APPROXIMATION METHODS FOR A CLASS OF STOCHASTIC VARIATIONAL INEQUALITY PROBLEMS
• Lectures on Stochastic Programming
• Robust Stochastic Approximation Approach to Stochastic Programming
• Engineering and Economic Applications of Complementarity Problems
• Variable-sample methods for stochastic optimization
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Distributed Computation of Equilibria in Monotone Nash Games via Iterative Regularization Techniques
• Stochastic Approximation Approaches to the Stochastic Variational Inequality Problem
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
• Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
• A Stochastic Approximation Method
• Probability
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• On the maximal inequalities of Burkholder, Davis and Gundy

This page was built for publication: Extragradient Method with Variance Reduction for Stochastic Variational Inequalities