mlsanityData to 7 Oct 2026

Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm

arXiv 2102.07922 ↗First posted 16 Feb 2021math.OCcited by 71

Not on the map. Why?

Abstract (arXiv)

In this work, we study the computational complexity of reducing the squared gradient magnitude for smooth minimax optimization problems. First, we present algorithms with accelerated O(1/k2) last-iterate rates, faster than the existing O(1/k) or slower rates for extragradient, Popov, and gradient descent with anchoring. The acceleration mechanism combines extragradient steps with anchoring and is distinct from Nesterov's acceleration. We then establish optimality of the O(1/k2) rate through a matching lower bound.

Key facts. Cited by 71 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Feb 2021.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 16; 2023: 14; 2024: 7; 2025: 12; 2026: 17.

71 papers.

Sort:

By area:

  1. 2022Linear Adversarial Concept Erasurecited by 98
  2. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  3. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  4. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  5. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  6. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  7. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  8. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  9. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 20
  10. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  11. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 19
  12. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 19
38 more
  1. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  2. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  3. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  4. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  5. 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
  6. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 12
  7. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 11
  8. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  9. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  10. 2023Accelerating Value Iteration with Anchoringcited by 10
  11. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  12. 2022Optimal Gradient Sliding and its Application to Distributed Optimization Under Similaritycited by 9
  13. 2023Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problemscited by 9
  14. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  15. 2024Fundamental Benefit of Alternating Updates in Minimax Optimizationcited by 9
  16. 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 9
  17. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  18. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  19. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  20. 2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
  21. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  22. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  23. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  24. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  25. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  26. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  27. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 3
  28. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  29. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 3
  30. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  31. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  32. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  33. 2024An Inexact Halpern Iteration with Application to Distributionally Robust Optimizationcited by 2
  34. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 2
  35. 2025Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Gamescited by 2
  36. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  37. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 2
  38. 2022Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuitycited by 1

50 most cited of 71 All 71 (JSON)