# Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2021.

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

- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transport](https://mlsanity.com/paper/2205.14173/) (2022)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)
- [Riemannian accelerated gradient methods via extrapolation](https://mlsanity.com/paper/2208.06619/) (2022)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties](https://mlsanity.com/paper/2305.16186/) (2023)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Quantitative Convergences of Lie Group Momentum Optimizers](https://mlsanity.com/paper/2405.20390/) (2024)
- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)
- [Mirror Descent on Riemannian Manifolds](https://mlsanity.com/paper/2603.17527/) (2026)

## Abstract (arXiv)

Hamilton and Moitra (2021) showed that, in certain regimes, it is not possible to accelerate Riemannian gradient descent in the hyperbolic plane if we restrict ourselves to algorithms which make queries in a (large) bounded domain and which receive gradients and function values corrupted by a (small) amount of noise. We show that acceleration remains unachievable for any deterministic algorithm which receives exact gradient and function-value information (unbounded queries, no noise). Our results hold for the classes of strongly and nonstrongly geodesically convex functions, and for a large class of Hadamard manifolds including hyperbolic spaces and the symmetric space SL(n) / SO(n) of positive definite n × n matrices of determinant one. This cements a surprising gap between the complexity of convex optimization and geodesically convex optimization: for hyperbolic spaces, Riemannian gradient descent is optimal on the class of smooth and and strongly geodesically convex functions, in the regime where the condition number scales with the radius of the optimization domain. The key idea for proving the lower bound consists of perturbing the hard functions of Hamilton and Moitra (2021) with sums of bump functions chosen by a resisting oracle.