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

arXiv: https://arxiv.org/abs/2305.16186 · HTML: https://mlsanity.com/paper/2305.16186/

## 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 (most cited first, 28 of 28)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds](https://mlsanity.com/paper/2010.06097/) (2020)
- [An accelerated first-order method for non-convex optimization on manifolds](https://mlsanity.com/paper/2008.02252/) (2020)
- [Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1811.08109/) (2018)
- [Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles](https://mlsanity.com/paper/2111.13263/) (2021)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing](https://mlsanity.com/paper/1804.01076/) (2018)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Projection-free nonconvex stochastic optimization on Riemannian manifolds](https://mlsanity.com/paper/1910.04194/) (2019)
- [A Riemannian exponential augmented Lagrangian method for computing the projection robust Wasserstein distance](https://mlsanity.com/paper/2211.13386/) (2022)
- [Convergence Rate of O(1/k) for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1906.01115/) (2019)
- [An Extragradient-type Algorithm for Variational Inequality on Hadamard Manifolds](https://mlsanity.com/paper/1804.09292/) (2018)
- [An inexact proximal point method for variational inequality on Hadamard manifolds](https://mlsanity.com/paper/2103.02116/) (2021)

## Built on by (most cited first, 4 of 4)

- [A Framework for Bilevel Optimization on Riemannian Manifolds](https://mlsanity.com/paper/2402.03883/) (2024)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Extragradient Type Methods for Riemannian Variational Inequality Problems](https://mlsanity.com/paper/2309.14155/) (2023)
- [Disciplined Geodesically Convex Programming](https://mlsanity.com/paper/2407.05261/) (2024)

## 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.