mlsanityData to 14 Oct 2026

Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties

arXiv 2305.16186 ↗First posted 25 May 2023math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

In this work, we study optimization problems of the form minx maxy f(x, y), where f(x, y) is defined on a product Riemannian manifold M × N and is μx-strongly geodesically convex (g-convex) in x and μy-strongly g-concave in y, for μx, μy ≥ 0. We design accelerated methods when f is (Lx, Ly, Lxy)-smooth and M, N are Hadamard. To that aim we introduce new g-convex optimization results, of independent interest: we show global linear convergence for metric-projected Riemannian gradient descent and improve existing accelerated methods by reducing geometric constants. Additionally, we complete the analysis of two previous works applying to the Riemannian min-max case by removing an assumption about iterates staying in a pre-specified compact set.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 28 of its 42 references that are in the map. First posted on arXiv 25 May 2023.

Builds on

28 of 42 references.

References · 28

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2022Generative Adversarial Networkscited by 5,627
  3. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  4. 2017How to Escape Saddle Points Efficientlycited by 285
  5. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  6. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  7. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  8. 2016First-order Methods for Geodesically Convex Optimizationcited by 93
  9. 2016Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifoldscited by 64
  10. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  11. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  12. 2019Escaping from saddle points on Riemannian manifoldscited by 33
16 more
  1. 2019Efficiently escaping saddle points on manifoldscited by 24
  2. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  3. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  4. 2020Gradient Descent Ascent for Minimax Problems on Riemannian Manifoldscited by 16
  5. 2020An accelerated first-order method for non-convex optimization on manifoldscited by 15
  6. 2018Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifoldscited by 12
  7. 2021Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oraclescited by 12
  8. 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
  9. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  10. 2018Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testingcited by 8
  11. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  12. 2019Projection-free nonconvex stochastic optimization on Riemannian manifoldscited by 3
  13. 2022A Riemannian exponential augmented Lagrangian method for computing the projection robust Wasserstein distancecited by 3
  14. 2019Convergence Rate of O(1/k) for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problemscited by 2
  15. 2018An Extragradient-type Algorithm for Variational Inequality on Hadamard Manifoldscited by 1
  16. 2021An inexact proximal point method for variational inequality on Hadamard manifoldscited by 1

Built on by

Cited by year

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

4 papers.

  1. 2024A Framework for Bilevel Optimization on Riemannian Manifoldscited by 3
  2. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  3. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  4. 2024Disciplined Geodesically Convex Programmingcited by 1