mlsanityData to 14 Oct 2026

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

arXiv 2002.00057 ↗First posted 31 Jan 2020cs.LG math.OC stat.MLcited by 60

Not on the map. Why?

Abstract (arXiv)

In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of O(1/T) (Nemirovski, 2004). In this paper, we show that the last iterate of EG converges at a rate of O(1/√T). To the best of our knowledge, this is the first paper to provide a convergence rate guarantee for the last iterate of EG for the smooth convex-concave saddle point problem. Moreover, we show that this rate is tight by proving a lower bound of Omega(1/√T) for the last iterate. This lower bound therefore shows a quadratic separation of the convergence rates of ergodic and last iterates in smooth convex-concave saddle point problems.

Key facts. Cited by 60 papers in the map (data through 14 Oct 2026). First posted on arXiv 31 Jan 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

60 papers.

Sort:

By area:

  1. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  2. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 47
  3. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  4. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  5. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  6. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  7. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  8. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  9. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  10. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  11. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  12. 2021Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Taskscited by 16
38 more
  1. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  2. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  3. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  4. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  5. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  6. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  7. 2023Accelerating Value Iteration with Anchoringcited by 11
  8. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  9. 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 11
  10. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  11. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  12. 2024Constrained Sampling with Primal-Dual Langevin Monte Carlocited by 10
  13. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  14. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  15. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
  16. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  17. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  18. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  19. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  20. 2023Last-Iterate Convergence Properties of Regret-Matching Algorithms in Gamescited by 6
  21. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  22. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  23. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4
  24. 2022STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Gamescited by 4
  25. 2023Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Mapscited by 4
  26. 2022Solving Constrained Variational Inequalities via a First-order Interior Point-based Methodcited by 3
  27. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  28. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  29. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  30. 2023Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Gamescited by 2
  31. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  32. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  33. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  34. 2025Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Gamescited by 2
  35. 2022Continuous-time Analysis for Variational Inequalities: An Overview and Desideratacited by 1
  36. 2023ApproxED: Approximate exploitability descent via learned best responsescited by 1
  37. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  38. 2023A Specialized Semismooth Newton Method for Kernel-Based Optimal Transportcited by 1

50 most cited of 60 All 60 (JSON)