mlsanityData to 13 Oct 2026

Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation

arXiv 2306.16617 ↗First posted 29 Jun 2023math.OC cs.GT cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

Equilibrium computation on Riemannian manifolds provides a unifying framework for numerous problems in machine learning and data analytics. One of the simplest yet most fundamental methods is Riemannian gradient descent (RGD). While its Euclidean counterpart has been extensively studied, it remains unclear how the manifold curvature affects RGD in game-theoretic settings. This paper addresses this gap by establishing new convergence results for textitgeodesic strongly monotone games. Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion, a key property for applications in machine learning. We extend this guarantee to stochastic and adaptive variants -- SRGD and FARGD -- and establish that: (i) the sample complexity of SRGD is geometry-agnostic and optimal with respect to noise; (ii) FARGD matches the convergence rate of its non-adaptive counterpart up to constant factors, while avoiding reliance on the condition number. Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings, underscoring the surprising power of RGD -- despite its simplicity -- in solving a wide spectrum of machine learning problems.

Key facts. Cited by 2 papers in the map (data through 13 Oct 2026). Builds on 53 of its 114 references that are in the map. First posted on arXiv 29 Jun 2023.

Builds on

53 of 114 references.

References · 53

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,379
  2. 2017Training GANs with Optimismcited by 217
  3. 2018Riemannian Adaptive Optimization Methodscited by 191
  4. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  5. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  6. 2017Cycles in adversarial regularized learningcited by 122
  7. 2013Manopt, a Matlab toolbox for optimization on manifoldscited by 112
  8. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  9. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  10. 2016First-order Methods for Geodesically Convex Optimizationcited by 92
  11. 2017Orthogonal Weight Normalization: Solution to Optimization over Multiple Dependent Stiefel Manifolds in Deep Neural Networkscited by 92
  12. 2020Minimax Estimation of Conditional Moment Modelscited by 83
38 more
  1. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  2. 2016Learning in games with continuous action sets and unknown payoff functionscited by 79
  3. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 72
  4. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  5. 2016Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifoldscited by 64
  6. 2016Global rates of convergence for nonconvex optimization on manifoldscited by 61
  7. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  8. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  9. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  10. 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
  11. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  12. 2018On Gradient-Based Learning in Continuous Gamescited by 47
  13. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  14. 2020Projection Robust Wasserstein Distance and Riemannian Optimizationcited by 45
  15. 2018Averaging Stochastic Gradient Descent on Riemannian Manifoldscited by 39
  16. 2019On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Gamescited by 35
  17. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  18. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  19. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  20. 2016Dimensionality Reduction on SPD Manifolds: The Emergence of Geometry-Aware Methodscited by 29
  21. 2020A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distancecited by 27
  22. 2015Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Methodcited by 24
  23. 2019Efficiently escaping saddle points on manifoldscited by 24
  24. 2022A unified stochastic approximation framework for learning in gamescited by 22
  25. 2017Riemannian Optimization via Frank-Wolfe Methodscited by 21
  26. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  27. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  28. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  29. 2021Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifoldcited by 18
  30. 2020Gradient Descent Ascent for Minimax Problems on Riemannian Manifoldscited by 16
  31. 2020An accelerated first-order method for non-convex optimization on manifoldscited by 15
  32. 2019Convergence of Gradient Methods on Bilinear Zero-Sum Gamescited by 12
  33. 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
  34. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 12
  35. 2022Accelerated Gradient Methods for Geodesically Convex Optimization: Tractable Algorithms and Convergence Analysiscited by 10
  36. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  37. 2020A novel embedded min-max approach for feature selection in nonlinear support vector machine classificationcited by 9
  38. 2022Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithmcited by 9

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year

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

2 papers.

  1. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  2. 2024Riemannian Bilevel Optimizationcited by 0