Global Riemannian Acceleration in Hyperbolic and Spherical Spaces

Abstract

We further research on the accelerated optimization phenomenon on Riemannian manifolds by introducing accelerated global first-order methods for the optimization of $L$-smooth and geodesically convex (g-convex) or $\mu$-strongly g-convex functions defined on the hyperbolic space or a subset of the sphere. For a manifold other than the Euclidean space, these are the first methods to \emph{globally} achieve the same rates as accelerated gradient descent in the Euclidean space with respect to $L$ and $\epsilon$ (and $\mu$ if it applies), up to log factors. Due to the geometric deformations, our rates have an extra factor, depending on the initial distance $R$ to a minimizer and the curvature $K$, with respect to Euclidean accelerated algorithms As a proxy for our solution, we solve a constrained non-convex Euclidean problem, under a condition between convexity and \emph{quasar-convexity}, of independent interest. Additionally, for any Riemannian manifold of bounded sectional curvature, we provide reductions from optimization methods for smooth and g-convex functions to methods for smooth and strongly g-convex functions and vice versa. We also reduce global optimization to optimization over bounded balls where the effect of the curvature is reduced.

arXiv commentgreatly improved geometric constants in the rates

References in corpus (21)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Optimal Black-Box Reductions Between Optimization Objectives
• On Acceleration with Noise-Corrupted Gradients
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Efficiently escaping saddle points on manifolds
• A Riemannian trust-region method for low-rank tensor completion
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Momentum Improves Optimization on Riemannian Manifolds
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Matrix-Free Preconditioning in Online Learning
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds

Cited by in corpus (1)

• No-go Theorem for Acceleration in the Hyperbolic Plane