Solving variational inequalities with stochastic mirror-prox algorithm
From MaRDI portal
Abstract: In this paper we consider iterative methods for stochastic variational inequalities (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel Stochastic Mirror-Prox (SMP) algorithm for solving s.v.i. and show that with the convenient stepsize strategy it attains the optimal rates of convergence with respect to the problem parameters. We apply the SMP algorithm to Stochastic composite minimization and describe particular applications to Stochastic Semidefinite Feasability problem and Eigenvalue minimization.
Recommendations
- Accelerated schemes for a class of variational inequalities
- Smooth monotone stochastic variational inequalities and saddle point problems: a survey
- Stochastic projection gradient algorithm for stochastic variational inequalities
- A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
- New first-order algorithms for stochastic variational inequalities
Cites work
- scientific article; zbMATH DE number 3862940 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 5057523 (Why is no real title available?)
- A sublinear-time randomized approximation algorithm for matrix games
- Accuracy certificates for computational problems with convex structure
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Large-scale semidefinite programming via a saddle point mirror-prox algorithm
- Non-Euclidean restricted memory level method for large-scale convex 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
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of non-smooth functions
- Weighted sums of certain dependent random variables
Cited in
(only showing first 100 items - show all)- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- On the computation of equilibria in monotone and potential stochastic hierarchical games
- Distributed algorithms for aggregative games on graphs
- A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
- A unified stochastic approximation framework for learning in games
- Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems
- Optimal analysis of method with batching for monotone stochastic finite-sum variational inequalities
- A stochastic primal-dual splitting algorithm with variance reduction for composite optimization problems
- Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
- A version of the mirror descent method to solve variational inequalities
- Accelerated gradient sliding for structured convex optimization
- Stochastic projection gradient algorithm for stochastic variational inequalities
- Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities
- New version of mirror prox for variational inequalities with adaptation to inexactness
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
- Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities
- Learning in nonatomic games. I: Finite action spaces and population games
- Primal-dual mirror descent method for constraint stochastic optimization problems
- Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- Extragradient sliding for composite non-monotone variational inequalities
- General procedure to provide high-probability guarantees for stochastic saddle point problems
- Almost sure convergence of the forward-backward-forward splitting algorithm
- Stochastic forward-backward splitting for monotone inclusions
- Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Improved guarantees for optimal Nash equilibrium seeking and bilevel variational inequalities
- The rate of convergence of Bregman proximal methods: local geometry versus regularity versus sharpness
- Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization
- Forward-reflected-backward method with variance reduction
- Unified convergence analysis for adaptive optimization with moving average estimator
- High probability and risk-averse guarantees for a stochastic accelerated primal-dual method
- Stochastic-constrained stochastic optimization with Markovian data
- A modified Popov algorithm for non-monotone and non-Lipschitzian stochastic variational inequalities
- Variance-based extragradient methods with line search for stochastic variational inequalities
- On the solution of stochastic optimization and variational problems in imperfect information regimes
- Stochastic Bregman extragradient algorithm with line search for stochastic mixed variational inequalities
- A unified analysis of variational inequality methods: variance reduction, sampling, quantization, and coordinate descent
- Two-stage stochastic variational inequalities: an ERM-solution procedure
- Learning in games with continuous action sets and unknown payoff functions
- Smooth monotone stochastic variational inequalities and saddle point problems: a survey
- A distributed stochastic forward-backward-forward self-adaptive algorithm for Cartesian stochastic variational inequalities
- Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
- Open problem: Iterative schemes for stochastic optimization: convergence statements and limit theorems
- Sublinear time algorithms for approximate semidefinite programming
- Compression and data similarity: combination of two techniques for communication-efficient solving of distributed variational inequalities
- CPC algorithm for semidefinite monotone variational inequalities
- Improved variance reduction extragradient method with line search for stochastic variational inequalities
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- On the initialization for convex-concave min-max problems
- Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
- Two steps at a time-taking GAN training in stride with Tseng's method
- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Gradient sliding for composite optimization
- Algorithms of inertial mirror descent in stochastic convex optimization problems
- On lower iteration complexity bounds for the convex concave saddle point problems
- Relative Lipschitzness in extragradient methods and a direct recipe for acceleration
- An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
- Golden ratio algorithms for variational inequalities
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems
- A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
- On the convergence of mirror descent beyond stochastic convex programming
- Ergodic convergence of a stochastic proximal point algorithm
- Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
- Saddle point mirror descent algorithm for the robust PageRank problem
- Dynamic stochastic projection method for multistage stochastic variational inequalities
- Analysis of Tseng algorithm with inertial extrapolation step for stochastic variational inequality problem
- A self-adaptive stochastic subgradient extragradient algorithm for the stochastic pseudomonotone variational inequality problem with application
- Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
- Mirror descent algorithms with nearly dimension-independent rates for differentially-private stochastic saddle-point problems
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- Variance-reduction for variational inequality problems with Bregman distance function
- Adaptive projection-free methods for constrained variational inequalities in machine learning
- Recent theoretical advances in decentralized distributed convex optimization
- 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
- Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control
- Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
- Stochastic approximation for estimating the price of stability in stochastic Nash games
- A method with convergence rates for optimization problems with variational inequality constraints
- On the adaptivity of stochastic gradient-based optimization
- An inverse-adjusted best response algorithm for Nash equilibria
- Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time
- Faster algorithms for extensive-form game solving via improved smoothing functions
- Accelerated schemes for a class of variational inequalities
- Individual confidence intervals for solutions to expected value formulations of stochastic variational inequalities
- On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
- Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
- An inexact first-order method for constrained nonlinear optimization
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
- Convergence analysis of the stochastic reflected forward-backward splitting algorithm
- Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
- A payoff-based policy gradient method in stochastic games with long-run average payoffs
- Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
- Distributed saddle point problems: lower bounds, near-optimal and robust algorithms
- One-point feedback for composite optimization with applications to distributed and federated learning
- Proximal subgradient method for non-Lipschitz objective functions
- Variance-based stochastic projection gradient method for two-stage co-coercive stochastic variational inequalities
- Minibatch forward-backward-forward methods for solving stochastic variational inequalities
This page was built for publication: Solving variational inequalities with stochastic mirror-prox algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168840)
