Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
From MaRDI portal
Abstract: In this paper we first present a novel operator extrapolation (OE) method for solving deterministic variational inequality (VI) problems. Similar to the gradient (operator) projection method, OE updates one single search sequence by solving a single projection subproblem in each iteration. We show that OE can achieve the optimal rate of convergence for solving a variety of VI problems in a much simpler way than existing approaches. We then introduce the stochastic operator extrapolation (SOE) method and establish its optimal convergence behavior for solving different stochastic VI problems. In particular, SOE achieves the optimal complexity for solving a fundamental problem, i.e., stochastic smooth and strongly monotone VI, for the first time in the literature. We also present a stochastic block operator extrapolations (SBOE) method to further reduce the iteration cost for the OE method applied to large-scale deterministic VIs with a certain block structure. Numerical experiments have been conducted to demonstrate the potential advantages of the proposed algorithms. In fact, all these algorithms are applied to solve generalized monotone variational inequality (GMVI) problems whose operator is not necessarily monotone. We will also discuss optimal OE-based policy evaluation methods for reinforcement learning in a companion paper.
Recommendations
- New first-order algorithms for stochastic variational inequalities
- Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
- Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
- A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
- Convergence of the operator extrapolation method
Cites work
- Accelerated schemes for a class of variational inequalities
- Approximate policy iteration: a survey and some new methods
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- First-order and stochastic optimization methods for machine learning
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3862940 (Why is no real title available?)
- scientific article; zbMATH DE number 3534286 (Why is no real title available?)
- Interior projection-like methods for monotone variational inequalities
- Methodes itératives pour les équations et inéquations aux dérivées partielles non linéaires de type monotone. (Iteration methods for nonlinear equations and inequations with partial derivatives of monotone type)
- Monotone Operators and the Proximal Point Algorithm
- Non-Euclidean restricted memory level method for large-scale convex optimization
- On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
- On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems
- On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
- On the convergence of stochastic primal-dual hybrid gradient
- On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators
- Projected reflected gradient methods for monotone variational inequalities
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Random gradient extrapolation for distributed and stochastic optimization
- Robust Stochastic Approximation Approach to Stochastic Programming
- Solving strongly monotone variational and quasi-variational inequalities
- Solving variational inequalities with stochastic mirror-prox algorithm
- Statistical Inference via Convex Optimization
Cited in
(27)- New first-order algorithms for stochastic variational inequalities
- Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning
- Convergence of the operator extrapolation method
- Cyclic Coordinate Dual Averaging with Extrapolation
- Accelerated gradient methods with absolute and relative noise in the gradient
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
- Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities
- Smooth monotone stochastic variational inequalities and saddle point problems: a survey
- Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
- A Bregman projection algorithm with self adaptive step sizes for split variational inequality problems involving non-Lipschitz operators
- Dynamic stochastic projection method for multistage stochastic variational inequalities
- Convergence rate of the extrapolation from the past and operator extrapolation algorithms
- A stochastic Bregman golden ratio algorithm for non-Lipschitz stochastic mixed variational inequalities with application to resource share problems
- Perseus: a simple and optimal high-order method for variational inequalities
- Quantitative stability for stochastic tensor variational inequalities
- Generalized optimistic methods for convex-concave saddle point problems
- Accelerated stochastic approximation with state-dependent noise
- Intermediate gradient methods with relative inexactness
- The operator extrapolation method for variational inequalities and its application
- Mirror frameworks for relatively Lipschitz and monotone-like variational inequalities
- A modified Popov algorithm for non-monotone and non-Lipschitzian stochastic variational inequalities
- Stochastic Bregman extragradient algorithm with line search for stochastic mixed variational inequalities
- Improved guarantees for optimal Nash equilibrium seeking and bilevel variational inequalities
- A continuous-time perspective on global acceleration for monotone equation problems
- General inertial proximal gradient method with gradient extrapolation for nonconvex nonsmooth optimization problems
- VFOSA: variance-reduced fast operator splitting algorithms for generalized equations
- A simple uniformly optimal method without line search for convex optimization
This page was built for publication: Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097022)
