From Nesterov's Estimate Sequence to Riemannian Acceleration
arXiv:2001.08876
Abstract
We propose the first global accelerated gradient method for Riemannian manifolds. Toward establishing our result we revisit Nesterov's estimate sequence technique and develop an alternative analysis for it that may also be of independent interest. Then, we extend this analysis to the Riemannian setting, localizing the key difficulty due to non-Euclidean structure into a certain ``metric distortion.'' We control this distortion by developing a novel geometric inequality, which permits us to propose and analyze a Riemannian counterpart to Nesterov's accelerated gradient method.
30 pages
References in corpus (9)
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- Optimized first-order methods for smooth convex minimization
- A Lyapunov Analysis of Momentum Methods in Optimization
- Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
- The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
- On Symplectic Optimization
- R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
- Accelerated Optimization With Orthogonality Constraints
- Riemannian stochastic variance reduced gradient on Grassmann manifold
Cited by in corpus (7)
- Distributed Certifiably Correct Pose-Graph Optimization
- Momentum Improves Optimization on Riemannian Manifolds
- No-go Theorem for Acceleration in the Hyperbolic Plane
- Variance reduction for Riemannian non-convex optimization with batch size adaptation
- Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
- Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
- A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast