mlsanityData to 7 Oct 2026

Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization

arXiv 2206.08573 ↗First posted 17 Jun 2022math.OC cs.CC cs.GTcited by 4

Not on the map. Why?

Abstract (arXiv)

We consider the smooth convex-concave bilinearly-coupled saddle-point problem, minxmaxy~F(x) + H(x,y) - G(y), where one has access to stochastic first-order oracles for F, G as well as the bilinear coupling function H. Building upon standard stochastic extragradient analysis for variational inequalities, we present a stochastic accelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragradient and Nesterov's acceleration in general stochastic settings. This algorithm leverages scheduled restarting to admit a fine-grained nonasymptotic convergence rate that matches known lower bounds by both citetibrahim2020linear and citetzhang2021lower in their corresponding settings, plus an additional statistical error term for bounded stochastic noise that is optimal up to a constant prefactor. This is the first result that achieves such a relatively mature characterization of optimality in saddle-point optimization.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 31 of its 51 references that are in the map. First posted on arXiv 17 Jun 2022.

Builds on

31 of 51 references.

References · 31

  1. 2017Training GANs with Optimismcited by 217
  2. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  3. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  4. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  5. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  6. 2017The Numerics of GANscited by 104
  7. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  8. 2017Gradient descent GAN optimization is locally stablecited by 65
  9. 2018Negative Momentum for Improved Game Dynamicscited by 59
  10. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  11. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  12. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
19 more
  1. 2019Revisiting Stochastic Extragradientcited by 35
  2. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  3. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  4. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  5. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  6. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  7. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  8. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  9. 2020Accelerating Smooth Games by Manipulating Spectral Shapescited by 18
  10. 2020Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Accelerationcited by 18
  11. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  12. 2019ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problemscited by 16
  13. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  14. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  15. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  16. 2020An Optimal Multistage Stochastic Gradient Method for Minimax Problemscited by 12
  17. 2017Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithmscited by 8
  18. 2017DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimizationcited by 7
  19. 2021DIPPA: An improved Method for Bilinear Saddle Point Problemscited by 6

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 1.

4 papers.

  1. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  2. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  3. 2024SDEs for Minimax Optimizationcited by 6
  4. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2