No-go Theorem for Acceleration in the Hyperbolic Plane
arXiv:2101.05657
Abstract
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.
12 pages
References in corpus (12)
- Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
- Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
- Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
- Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
- Averaging Stochastic Gradient Descent on Riemannian Manifolds
- Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
- Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
- Riemannian adaptive stochastic gradient algorithms on matrix manifolds
- From Nesterov's Estimate Sequence to Riemannian Acceleration
- Rigorous Guarantees for Tyler's M-estimator via quantum expansion
- Integrated Principal Components Analysis
- Global Riemannian Acceleration in Hyperbolic and Spherical Spaces