# No-go Theorem for Acceleration in the Hyperbolic Plane

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 14 Jan 2021.

## Builds on (most cited first, 16 of 16)

- [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)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices](https://mlsanity.com/paper/1507.02772/) (2015)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [Rigorous Guarantees for Tyler's M-estimator via quantum expansion](https://mlsanity.com/paper/2002.00071/) (2020)
- [Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing](https://mlsanity.com/paper/1804.01076/) (2018)
- [Integrated Principal Components Analysis](https://mlsanity.com/paper/1810.00832/) (2018)
- [Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes](https://mlsanity.com/paper/1910.12375/) (2019)
- [Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling](https://mlsanity.com/paper/1607.06711/) (2016)
- [Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvature](https://mlsanity.com/paper/1703.08167/) (2017)
- [Efficient algorithms for tensor scaling, quantum marginals and moment polytopes](https://mlsanity.com/paper/1804.04739/) (2018)
- [Projection-free nonconvex stochastic optimization on Riemannian manifolds](https://mlsanity.com/paper/1910.04194/) (2019)

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

- [Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transport](https://mlsanity.com/paper/2205.14173/) (2022)
- [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)
- [Understanding Riemannian Acceleration via a Proximal Extragradient Framework](https://mlsanity.com/paper/2111.02763/) (2021)

## Abstract (arXiv)

In recent years there has been significant effort to adapt the key tools and ideas in convex optimization to the Riemannian setting. One key challenge has remained: Is there a Nesterov-like accelerated gradient method for geodesically convex functions on a Riemannian manifold? Recent work has given partial answers and the hope was that this ought to be possible. Here we dash these hopes. We prove that in a noisy setting, there is no analogue of accelerated gradient descent for geodesically convex functions on the hyperbolic plane. Our results apply even when the noise is exponentially small. The key intuition behind our proof is short and simple: In negatively curved spaces, the volume of a ball grows so fast that information about the past gradients is not useful in the future.