Open Access

Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm

Anatoli Juditsky
Anatoli Juditsky
[email protected]
LJK, Université J. Fourier, B.P. 53 38041 Grenoble Cedex 9, France
Search for more papers by this author
,
Arkadi Nemirovski
Arkadi Nemirovski
[email protected]
ISyE, Georgia Institute of Technology Atlanta, GA 30332, USA
Search for more papers by this author
,
Claire Tauvel
Claire Tauvel
[email protected]
LJK, Université J. Fourier, B.P. 53 38041 Grenoble Cedex 9, France
Search for more papers by this author

Anatoli Juditsky

[email protected]

LJK, Université J. Fourier, B.P. 53 38041 Grenoble Cedex 9, France

Search for more papers by this author

Arkadi Nemirovski

[email protected]

ISyE, Georgia Institute of Technology Atlanta, GA 30332, USA

Search for more papers by this author

Claire Tauvel

[email protected]

LJK, Université J. Fourier, B.P. 53 38041 Grenoble Cedex 9, France

Search for more papers by this author

Published Online:22 Aug 2011https://doi.org/10.1287/10-SSY011

Cited by
- Adaptive step-size extragradient algorithm with variance reduction for solving mixed variational inequality problems
  Communications in Nonlinear Science and Numerical Simulation, Vol. 158
- An Online Mirror Descent Learning Algorithm for Multiproduct Inventory Systems
  Sichen Guo,
  Cong Shi,
  Chaolin Yang,
  Christos Zacharias
  29 April 2026 | Operations Research, Vol. 0, No. 0
- Metric entropy-free sample complexity bounds for sample average approximation in convex stochastic programming
  20 April 2026 | Mathematical Programming, Vol. 2
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems
  20 February 2026 | SIAM Journal on Optimization, Vol. 36, No. 1
- A Randomized Block-Coordinate Primal-Dual Method for Large-Scale Stochastic Saddle Point Problems
  Erfan Yazdandoost Hamedani,
  Afrooz Jalilzadeh,
  Necdet Serhat Aybat
  25 February 2026 | INFORMS Journal on Optimization, Vol. 0, No. 0
- Zeroth-order methods for non-smooth stochastic problems under heavy-tailed noise
  2 February 2026 | Optimization Methods and Software, Vol. 79
- Distributed Optimal Robust GNE Seeking in Merely Monotone Games With Uncertain Coupled Constraints
  IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 73, No. 2
- A novel catalyst scheme for stochastic minimax optimization
  12 January 2026 | Mathematical Programming, Vol. 33
- First-Order Methods for Stochastic Variational Inequality Problems with Function Constraints
  Digvijay Boob,
  Qi Deng,
  Mohammad Khalafi
  6 January 2026 | Mathematics of Operations Research, Vol. 0, No. 0
- Variance-reduction for variational inequality problems with Bregman distance function
  2 February 2026 | Optimization Methods and Software, Vol. 41, No. 1
- Invariance and Concentration Properties of Gradient-based Learning in Games
- ExtraSAGA: Variance Reduction Hybrid Method for Variational Inequalities
  22 March 2026 | Doklady Mathematics, Vol. 112, No. 3
- Analysis of Tseng algorithm with inertial extrapolation step for stochastic variational inequality problem
  Applied Numerical Mathematics, Vol. 217
- An inertial-type stochastic self-adaptive algorithm for stochastic pseudomonotone variational inequality problem
  24 September 2025 | Optimization, Vol. 1
- Distributed saddle point problems: lower bounds, near-optimal and robust algorithms
  28 March 2025 | Optimization Methods and Software, Vol. 40, No. 5
- Proximal subgradient method for non-Lipschitz objective functions
  29 April 2025 | Optimization Methods and Software, Vol. 40, No. 4
- One-point feedback for composite optimization with applications to distributed and federated learning
  1 July 2025 | Optimization Methods and Software, Vol. 40, No. 4
- A stochastic primal-dual splitting algorithm with variance reduction for composite optimization problems
  16 December 2024 | Applicable Analysis, Vol. 104, No. 10
- A Variational Inequality Approach to Independent Learning in Static Mean-Field Games
  12 July 2025 | ACM / IMS Journal of Data Science, Vol. 2, No. 2
- A Modified Popov Algorithm for Non-Monotone and Non-Lipschitzian Stochastic Variational Inequalities
  22 April 2025 | Journal of Optimization Theory and Applications, Vol. 205, No. 3
- A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
  6 May 2025 | Quantum, Vol. 9
- Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback
  Michael Jordan; ,
  Tianyi Lin; ,
  Zhengyuan Zhou
  23 May 2024 | Operations Research, Vol. 73, No. 3
- A distributed stochastic forward-backward-forward self-adaptive algorithm for Cartesian stochastic variational inequalities
  Applied Numerical Mathematics, Vol. 211
- A stochastic Bregman golden ratio algorithm for non-Lipschitz stochastic mixed variational inequalities with application to resource share problems
  Journal of Computational and Applied Mathematics, Vol. 459
- Stochastic Bregman extragradient algorithm with line search for stochastic mixed variational inequalities
  2 February 2024 | Optimization, Vol. 74, No. 6
- Unified convergence analysis for adaptive optimization with moving average estimator
  17 February 2025 | Machine Learning, Vol. 114, No. 4
- Zeroth-Order Learning in Continuous Games via Residual Pseudogradient Estimates
  IEEE Transactions on Automatic Control, Vol. 70, No. 4
- Accelerated Minimax Algorithms Flock Together
  13 January 2025 | SIAM Journal on Optimization, Vol. 35, No. 1
- Improved Guarantees for Optimal Nash Equilibrium Seeking and Bilevel Variational Inequalities
  18 February 2025 | SIAM Journal on Optimization, Vol. 35, No. 1
- Primal methods for variational inequality problems with functional constraints
  20 March 2025 | Mathematical Programming, Vol. 258
- Off-Policy Prediction Learning: An Empirical Study of Online Algorithms
  IEEE Transactions on Neural Networks and Learning Systems, Vol. 36, No. 3
- Unified Analysis of SGD-Type Methods
  14 May 2025
- Extragradient Sliding for Composite Non-monotone Variational Inequalities
  31 January 2025
- A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs
  30 June 2025
- Variance-based stochastic projection gradient method for two-stage co-coercive stochastic variational inequalities
  24 February 2024 | Numerical Algorithms, Vol. 98, No. 1
- Popov Mirror-Prox for solving Variational Inequalities
- Dynamic stochastic projection method for multistage stochastic variational inequalities
  26 July 2024 | Computational Optimization and Applications, Vol. 89, No. 2
- Method with batching for stochastic finite-sum variational inequalities in non-Euclidean setting
  Chaos, Solitons & Fractals, Vol. 187
- Universal methods for variational inequalities: Deterministic and stochastic cases
  Chaos, Solitons & Fractals, Vol. 187
- The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness
  9 July 2024 | SIAM Journal on Optimization, Vol. 34, No. 3
- Energy Optimization and Lightweight Design for Efficient Federated Learning in Wireless Edge Systems
  IEEE Transactions on Vehicular Technology, Vol. 73, No. 9
- Multiple Greedy Quasi-Newton Methods for Saddle Point Problems
- General Procedure to Provide High-Probability Guarantees for Stochastic Saddle Point Problems
  28 May 2024 | Journal of Scientific Computing, Vol. 100, No. 1
- Notes on random optimal control equilibrium problem via stochastic inverse variational inequalities
  11 March 2024 | Computational Management Science, Vol. 21, No. 1
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
  22 June 2023 | Mathematical Programming, Vol. 205, No. 1-2
- Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
  11 December 2023 | Journal of Global Optimization, Vol. 89, No. 1
- Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash Games
  8 April 2024 | ACM Transactions on Modeling and Computer Simulation, Vol. 34, No. 2
- Local AdaGrad-type algorithm for stochastic convex-concave optimization
  23 November 2022 | Machine Learning, Vol. 113, No. 4
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
  19 March 2024 | SIAM Journal on Optimization, Vol. 34, No. 1
- Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games
  4 December 2023 | Optimization Letters, Vol. 18, No. 2
- Certified Distributional Robustness on Smoothed Classifiers
  IEEE Transactions on Dependable and Secure Computing, Vol. 21, No. 2
- Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities
  Applied Numerical Mathematics, Vol. 196
- Randomized Gradient-Free Methods in Convex Optimization
  8 September 2023
- A unified stochastic approximation framework for learning in games
  4 August 2023 | Mathematical Programming, Vol. 203, No. 1-2
- An Inexact Primal-Dual Smoothing Framework for Large-Scale Non-Bilinear Saddle Point Problems
  22 December 2023 | Journal of Optimization Theory and Applications, Vol. 200, No. 1
- An Online Mirror Descent Learning Algorithm for Multiproduct Inventory Systems
  1 January 2024 | SSRN Electronic Journal, Vol. 70
- Evolution of Mixed Strategies in Monotone Games
  13 October 2023 | SIAM Journal on Optimization, Vol. 33, No. 4
- An Incremental Gradient Method for Optimization Problems With Variational Inequality Constraints
  IEEE Transactions on Automatic Control, Vol. 68, No. 12
- Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities
  25 March 2024 | Doklady Mathematics, Vol. 108, No. S2
- Improved variance reduction extragradient method with line search for stochastic variational inequalities
  11 February 2022 | Journal of Global Optimization, Vol. 87, No. 2-4
- Gradient-free Federated Learning Methods with l1 and l2-randomization for Non-smooth Convex Stochastic Optimization Problems
  13 October 2023 | Computational Mathematics and Mathematical Physics, Vol. 63, No. 9
- Gradient-free Federated Learning Methods with l1 and l2-randomization for Non-smooth Convex Stochastic Optimization Problems
  1 September 2023 | Журнал вычислительной математики и математической физики, Vol. 63, No. 9
- Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
  22 June 2023 | SIAM Journal on Optimization, Vol. 33, No. 2
- A stochastic variance reduction algorithm with Bregman distances for structured composite problems
  31 January 2022 | Optimization, Vol. 72, No. 6
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
  10 April 2023 | Computational Optimization and Applications, Vol. 85, No. 2
- Accelerated Primal-dual Scheme for a Class of Stochastic Nonconvex-concave Saddle Point Problems
- Multiagent Online Learning in Time-Varying Games
  Benoit Duvocelle,
  Panayotis Mertikopoulos,
  Mathias Staudigl,
  Dries Vermeulen
  1 July 2022 | Mathematics of Operations Research, Vol. 48, No. 2
- Blockchain Assisted Federated Learning Over Wireless Channels: Dynamic Resource Allocation and Client Scheduling
  IEEE Transactions on Wireless Communications, Vol. 22, No. 5
- Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
  7 October 2022 | Mathematical Programming, Vol. 198, No. 2
- On the computation of equilibria in monotone and potential stochastic hierarchical games
  23 November 2022 | Mathematical Programming, Vol. 198, No. 2
- A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization, and Coordinate Descent
  9 April 2023 | Computational Mathematics and Mathematical Physics, Vol. 63, No. 2
- SARAH-Based Variance-Reduced Algorithm for Stochastic Finite-Sum Cocoercive Variational Inequalities
  4 May 2023
- Stochastic Gradient Schemes
  1 February 2024
- EFFICIENCY BOUNDS FOR ALGORITHMS WITH BREGMAN DIVERGENCE
  1 January 2023 | Journal of Numerical and Applied Mathematics, No. 2
- Learning in Games with Quantized Payoff Observations
- Convergence analysis of the stochastic reflected forward–backward splitting algorithm
  31 January 2022 | Optimization Letters, Vol. 16, No. 9
- New Primal-Dual Algorithms for a Class of Nonsmooth and Nonlinear Convex-Concave Minimax Problems
  19 October 2022 | SIAM Journal on Optimization, Vol. 32, No. 4
- New First-Order Algorithms for Stochastic Variational Inequalities
  14 November 2022 | SIAM Journal on Optimization, Vol. 32, No. 4
- Simple and Optimal Methods for Stochastic Variational Inequalities, I: Operator Extrapolation
  16 August 2022 | SIAM Journal on Optimization, Vol. 32, No. 3
- A self-adaptive stochastic subgradient extragradient algorithm for the stochastic pseudomonotone variational inequality problem with application
  12 July 2022 | Zeitschrift für angewandte Mathematik und Physik, Vol. 73, No. 4
- On lower iteration complexity bounds for the convex concave saddle point problems
  7 June 2021 | Mathematical Programming, Vol. 194, No. 1-2
- 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
  Journal of Computational and Applied Mathematics, Vol. 408
- Accelerated gradient sliding for structured convex optimization
  12 April 2022 | Computational Optimization and Applications, Vol. 82, No. 2
- Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
  3 February 2022 | Mathematical Programming Computation, Vol. 14, No. 2
- Two Steps at a Time---Taking GAN Training in Stride with Tseng's Method
  23 June 2022 | SIAM Journal on Mathematics of Data Science, Vol. 4, No. 2
- Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems
  Renbo Zhao
  23 December 2021 | Mathematics of Operations Research, Vol. 47, No. 2
- Convex optimization algorithms in medical image reconstruction—in the age of AI
  23 March 2022 | Physics in Medicine & Biology, Vol. 67, No. 7
- An inexact first-order method for constrained nonlinear optimization
  15 January 2020 | Optimization Methods and Software, Vol. 37, No. 1
- Recent Theoretical Advances in Decentralized Distributed Convex Optimization
  5 April 2022
- A Nonasymptotic Analysis of Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
  SSRN Electronic Journal, Vol. 23
- Adaptive, Doubly Optimal No-Regret Learning in Games with Gradient Feedback
  SSRN Electronic Journal, Vol. 408
- Forward-reflected-backward method with variance reduction
  19 August 2021 | Computational Optimization and Applications, Vol. 80, No. 2
- Variance-Based Single-Call Proximal Extragradient Algorithms for Stochastic Mixed Variational Inequalities
  24 June 2021 | Journal of Optimization Theory and Applications, Vol. 190, No. 2
- Minibatch Forward-Backward-Forward Methods for Solving Stochastic Variational Inequalities
  Radu Ioan Boţ,
  Panayotis Mertikopoulos,
  Mathias Staudigl,
  Phan Tu Vuong
  25 February 2021 | Stochastic Systems, Vol. 11, No. 2
- On the Analysis of Variance-reduced and Randomized Projection Variants of Single Projection Schemes for Monotone Stochastic Variational Inequality Problems
  8 April 2021 | Set-Valued and Variational Analysis, Vol. 29, No. 2
- Algorithms for Solving Variational Inequalities and Saddle Point Problems with Some Generalizations of Lipschitz Property for Operators
  21 September 2021
- A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints
  31 August 2021 | SIAM Journal on Optimization, Vol. 31, No. 3
- Golden ratio algorithms for variational inequalities
  31 July 2019 | Mathematical Programming, Vol. 184, No. 1-2
- Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time
  Mengdi Wang
  16 October 2019 | Mathematics of Operations Research, Vol. 45, No. 2
- A modular analysis of adaptive (non-)convex optimization: Optimism, composite objectives, variance reduction, and variational bounds
  Theoretical Computer Science, Vol. 808
- Stochastic Convex Optimization
  16 May 2020
- Faster algorithms for extensive-form game solving via improved smoothing functions
  5 October 2018 | Mathematical Programming, Vol. 179, No. 1-2
- On the Convergence of Mirror Descent beyond Stochastic Convex Programming
  27 February 2020 | SIAM Journal on Optimization, Vol. 30, No. 1
- An Inverse-Adjusted Best Response Algorithm for Nash Equilibria
  18 June 2020 | SIAM Journal on Optimization, Vol. 30, No. 2
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
  18 June 2020 | SIAM Journal on Optimization, Vol. 30, No. 2
- A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
  17 March 2020 | SIAM Journal on Optimization, Vol. 30, No. 1
- On the Adaptivity of Stochastic Gradient-Based Optimization
  27 May 2020 | SIAM Journal on Optimization, Vol. 30, No. 2
- Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
  10 September 2019 | Computational Optimization and Applications, Vol. 74, No. 3
- Discounted Mirror Descent Dynamics in Concave Games
- Open Problem—Iterative Schemes for Stochastic Optimization: Convergence Statements and Limit Theorems
  Afrooz Jalilzadeh,
  Jinlong Lei,
  Uday V. Shanbhag
  17 September 2019 | Stochastic Systems, Vol. 9, No. 3
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
  5 June 2018 | Mathematical Programming, Vol. 174, No. 1-2
- Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
  Alfredo N. Iusem,
  Alejandro Jofré,
  Philip Thompson
  18 September 2018 | Mathematics of Operations Research, Vol. 44, No. 1
- Learning in games with continuous action sets and unknown payoff functions
  12 March 2018 | Mathematical Programming, Vol. 173, No. 1-2
- Variance-Based Extragradient Methods with Line Search for Stochastic Variational Inequalities
  SIAM Journal on Optimization, Vol. 29, No. 1
- GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
  25 April 2019 | Asian Journal of Applied Science and Engineering, Vol. 8, No. 1
- On Stochastic Mirror-prox Algorithms for Stochastic Cartesian Variational Inequalities: Randomized Block Coordinate and Optimal Averaging Schemes
  20 March 2018 | Set-Valued and Variational Analysis, Vol. 26, No. 4
- Primal–Dual Mirror Descent Method for Constraint Stochastic Optimization Problems
  5 December 2018 | Computational Mathematics and Mathematical Physics, Vol. 58, No. 11
- Individual confidence intervals for solutions to expected value formulations of stochastic variational inequalities
  16 July 2016 | Mathematical Programming, Vol. 165, No. 1
- Two-stage stochastic variational inequalities: an ERM-solution procedure
  14 March 2017 | Mathematical Programming, Vol. 165, No. 1
- Accelerated schemes for a class of variational inequalities
  1 June 2017 | Mathematical Programming, Vol. 165, No. 1
- On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
  25 July 2017 | Mathematical Programming, Vol. 165, No. 1
- On the existence of solutions to stochastic quasi-variational inequality and complementarity problems
  22 August 2017 | Mathematical Programming, Vol. 165, No. 1
- Distributed Algorithms for Aggregative Games on Graphs
  Jayash Koshal,
  Angelia Nedić,
  Uday V. Shanbhag
  20 May 2016 | Operations Research, Vol. 64, No. 3
- Faster First-Order Methods for Extensive-Form Game Solving
  15 June 2015
- On Solving Large-Scale Polynomial Convex Problems by Randomized First-Order Algorithms
  Aharon Ben-Tal,
  Arkadi Nemirovski
  29 September 2014 | Mathematics of Operations Research, Vol. 40, No. 2
- On first-order algorithms for l1 /nuclear norm minimization
  2 April 2013 | Acta Numerica, Vol. 22

Volume 1, Issue 1

June 2011

Pages 1-208

Article Information

Metrics

Information

Received:August 01, 2010
Published Online:August 22, 2011

Cite as

Anatoli Juditsky, Arkadi Nemirovski, Claire Tauvel (2011) Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm. Stochastic Systems 1(1):17-58.

https://doi.org/10.1287/10-SSY011

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm

Volume 1, Issue 1

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News