mlsanityData to 7 Oct 2026

No-go Theorem for Acceleration in the Hyperbolic Plane

arXiv 2101.05657 ↗First posted 14 Jan 2021math.OC cs.DS cs.LGcited by 4

Not on the map. Why?

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.

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

Builds on

16 of 40 references.

References · 16

  1. 2016First-order Methods for Geodesically Convex Optimizationcited by 92
  2. 2016Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifoldscited by 64
  3. 2018Averaging Stochastic Gradient Descent on Riemannian Manifoldscited by 39
  4. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  5. 2015Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matricescited by 24
  6. 2015Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Methodcited by 24
  7. 2019Efficiently escaping saddle points on manifoldscited by 24
  8. 2020From Nesterov's Estimate Sequence to Riemannian Accelerationcited by 24
  9. 2020Rigorous Guarantees for Tyler's M-estimator via quantum expansioncited by 10
  10. 2018Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testingcited by 8
  11. 2018Integrated Principal Components Analysiscited by 7
  12. 2019Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopescited by 7
4 more
  1. 2016Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scalingcited by 5
  2. 2017Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvaturecited by 4
  3. 2018Efficient algorithms for tensor scaling, quantum marginals and moment polytopescited by 4
  4. 2019Projection-free nonconvex stochastic optimization on Riemannian manifoldscited by 3

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 3.

4 papers.

  1. 2022Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transportcited by 10
  2. 2022Riemannian accelerated gradient methods via extrapolationcited by 5
  3. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  4. 2021Understanding Riemannian Acceleration via a Proximal Extragradient Frameworkcited by 3