# First-order Methods for Geodesically Convex Optimization

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

## Key facts

- Cited by 93 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2016.

## Built on by (most cited first, 30 of 93)

- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry](https://mlsanity.com/paper/2106.00286/) (2021)
- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Universal Approximation Under Constraints is Possible with Transformers](https://mlsanity.com/paper/2110.03303/) (2021)
- [NRDF: Neural Riemannian Distance Fields for Learning Articulated Pose Priors](https://mlsanity.com/paper/2403.03122/) (2024)
- [Position: Beyond Euclidean -- Foundation Models Should Embrace Non-Euclidean Geometries](https://mlsanity.com/paper/2504.08896/) (2025)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold](https://mlsanity.com/paper/2303.09261/) (2023)
- [Guiding Neural Collapse: Optimising Towards the Nearest Simplex Equiangular Tight Frame](https://mlsanity.com/paper/2411.01248/) (2024)
- [Federated Learning on Riemannian Manifolds](https://mlsanity.com/paper/2206.05668/) (2022)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [Differentially private Riemannian optimization](https://mlsanity.com/paper/2205.09494/) (2022)
- [Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transport](https://mlsanity.com/paper/2205.14173/) (2022)
- [Horospherical Decision Boundaries for Large Margin Classification in Hyperbolic Space](https://mlsanity.com/paper/2302.06807/) (2023)
- [Learning with symmetric positive definite matrices via generalized Bures-Wasserstein geometry](https://mlsanity.com/paper/2110.10464/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Lifting Weak Supervision To Structured Prediction](https://mlsanity.com/paper/2211.13375/) (2022)
- [Geodesic Optimization for Predictive Shift Adaptation on EEG data](https://mlsanity.com/paper/2407.03878/) (2024)
- [Riemannian Optimization for LoRA on the Stiefel Manifold](https://mlsanity.com/paper/2508.17901/) (2025)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [On the Local Linear Rate of Consensus on the Stiefel Manifold](https://mlsanity.com/paper/2101.09346/) (2021)
- [Particle-based Online Bayesian Sampling](https://mlsanity.com/paper/2302.14796/) (2023)
- [Optimization without Retraction on the Random Generalized Stiefel Manifold](https://mlsanity.com/paper/2405.01702/) (2024)
- [Optimization on manifolds: A symplectic approach](https://mlsanity.com/paper/2107.11231/) (2021)
- [From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds](https://mlsanity.com/paper/2108.07406/) (2021)
- [Online Learning to Transport via the Minimal Selection Principle](https://mlsanity.com/paper/2202.04732/) (2022)
- [Shape And Structure Preserving Differential Privacy](https://mlsanity.com/paper/2209.12667/) (2022)
- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)

## Abstract (arXiv)

Geodesic convexity generalizes the notion of (vector space) convexity to nonlinear metric spaces. But unlike convex optimization, geodesically convex (g-convex) optimization is much less developed. In this paper we contribute to the understanding of g-convex optimization by developing iteration complexity analysis for several first-order algorithms on Hadamard manifolds. Specifically, we prove upper bounds for the global complexity of deterministic and stochastic (sub)gradient methods for optimizing smooth and nonsmooth g-convex functions, both with and without strong g-convexity. Our analysis also reveals how the manifold geometry, especially sectional curvature, impacts convergence rates. To the best of our knowledge, our work is the first to provide global complexity analysis for first-order algorithms for general g-convex optimization.