mlsanityData to 7 Oct 2026

Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization

arXiv 2210.17550 ↗First posted 31 Oct 2022math.OC cs.GT cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Descent Ascent -- for separable convex-concave minimax optimization. The main idea of our algorithm is to carefully leverage the structure of the minimax problem, performing Nesterov acceleration on the individual component and optimistic gradient on the coupling component. Equipped with proper restarting, we show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings, including bilinearly coupled strongly convex-strongly concave minimax optimization (bi-SC-SC), bilinearly coupled convex-strongly concave minimax optimization (bi-C-SC), and bilinear games. We also extend our algorithm to the stochastic setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings. AG-OG is the first single-call algorithm with optimal convergence rates in both deterministic and stochastic settings for bilinearly coupled minimax optimization problems.

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

Builds on

32 of 57 references.

References · 32

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  4. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  5. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  6. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  7. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  8. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  9. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  10. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  11. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  12. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
20 more
  1. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  2. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  3. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  4. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  5. 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
  6. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  7. 2018Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexitycited by 28
  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. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  13. 2018A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methodscited by 14
  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. 2021Robust Accelerated Primal-Dual Methods for Computing Saddle Pointscited by 10
  17. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  18. 2021DIPPA: An improved Method for Bilinear Saddle Point Problemscited by 6
  19. 2022Decentralized Saddle-Point Problems with Different Constants of Strong Convexity and Strong Concavitycited by 4
  20. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024Accelerated Preference Optimization for Large Language Model Alignmentcited by 5
  2. 2024Generalized Continuous-Time Models for Nesterov's Accelerated Gradient Methodscited by 0