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 -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 globally achieve the same rates as accelerated gradient descent in the Euclidean space with respect to L and (and 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 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.

Tasks

Reproductions