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
- 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
- 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?)
- 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)- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Two-stage stochastic variational inequalities: an ERM-solution procedure
- 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
- Algorithms of inertial mirror descent in stochastic convex optimization problems
- On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
- Learning in games with continuous action sets and unknown payoff functions
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- New version of mirror prox for variational inequalities with adaptation to inexactness
- On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems
- Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities
- Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
- Convergence analysis of the stochastic reflected forward-backward splitting algorithm
- Learning in nonatomic games. I: Finite action spaces and population games
- Accelerated gradient sliding for structured convex optimization
- Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
- On lower iteration complexity bounds for the convex concave saddle point problems
- 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
- Golden ratio algorithms for variational inequalities
- Forward-reflected-backward method with variance reduction
- Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
- Faster algorithms for extensive-form game solving via improved smoothing functions
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
- Primal-dual mirror descent method for constraint stochastic optimization problems
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- 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
- Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
- On the computation of equilibria in monotone and potential stochastic hierarchical games
- Almost sure convergence of the forward-backward-forward splitting algorithm
- Ergodic convergence of a stochastic proximal point algorithm
- Distributed algorithms for aggregative games on graphs
- On the solution of stochastic optimization and variational problems in imperfect information regimes
- A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
- Stochastic forward-backward splitting for monotone inclusions
- Sublinear time algorithms for approximate semidefinite programming
- Gradient sliding for composite optimization
- CPC algorithm for semidefinite monotone variational inequalities
- On stochastic gradient and subgradient methods with adaptive steplength sequences
- Variance-based extragradient methods with line search for stochastic variational inequalities
- Stochastic projection gradient algorithm for stochastic variational inequalities
- An inexact first-order method for constrained nonlinear optimization
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- New first-order algorithms for stochastic variational inequalities
- Saddle point mirror descent algorithm for the robust PageRank problem
- Minibatch forward-backward-forward methods for solving stochastic variational inequalities
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- Two steps at a time-taking GAN training in stride with Tseng's method
- Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
- Open problem: Iterative schemes for stochastic optimization: convergence statements and limit theorems
- On the adaptivity of stochastic gradient-based optimization
- An inverse-adjusted best response algorithm for Nash equilibria
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time
- A method with convergence rates for optimization problems with variational inequality constraints
- Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
- A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
- On solving large-scale polynomial convex problems by randomized first-order algorithms
- Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
- Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
- On the convergence of mirror descent beyond stochastic convex programming
- Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control
- A unified analysis of variational inequality methods: variance reduction, sampling, quantization, and coordinate descent
- Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
- Improved variance reduction extragradient method with line search for stochastic variational inequalities
- Evolution of Mixed Strategies in Monotone Games
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- A stochastic variance reduction algorithm with Bregman distances for structured composite problems
- Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems
- A unified stochastic approximation framework for learning in games
- Optimal analysis of method with batching for monotone stochastic finite-sum variational inequalities
- 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
- Smooth monotone stochastic variational inequalities and saddle point problems: a survey
- Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
- Compression and data similarity: combination of two techniques for communication-efficient solving of distributed variational inequalities
- An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
- Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
- Recent theoretical advances in decentralized distributed convex optimization
- Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
- Achieving zero constraint violation for concave utility constrained reinforcement learning via primal-dual approach
- Notes on random optimal control equilibrium problem via stochastic inverse variational inequalities
- General procedure to provide high-probability guarantees for stochastic saddle point problems
- The rate of convergence of Bregman proximal methods: local geometry versus regularity versus sharpness
- Dynamic stochastic projection method for multistage stochastic variational inequalities
- Stochastic approximation for estimating the price of stability in stochastic Nash games
- Variance-based stochastic projection gradient method for two-stage co-coercive stochastic variational inequalities
- Accelerated minimax algorithms flock together
- A stochastic Bregman golden ratio algorithm for non-Lipschitz stochastic mixed variational inequalities with application to resource share problems
- A version of the mirror descent method to solve variational inequalities
- Analysis of Tseng algorithm with inertial extrapolation step for stochastic variational inequality problem
- Mirror descent algorithms with nearly dimension-independent rates for differentially-private stochastic saddle-point problems
- Variance-reduction for variational inequality problems with Bregman distance function
- Adaptive projection-free methods for constrained variational inequalities in machine learning
- A payoff-based policy gradient method in stochastic games with long-run average payoffs
- 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
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)
