No-go Theorem for Acceleration in the Hyperbolic Plane

Geodesically convex optimization is a natural generalization that replaces Euclidean space with a Riemannian manifold and we require that the function we want to minimize is convex along geodesics [1, 5, 31]. It turns out that many optimization problems of interest, while non-convex in the Euclidean view, become geodesically convex when equipped with the right geometry. Some notable examples: The fastest known algorithms for computing Brascamp-Lieb constants [3, 17], and solving related problems like the null cone problem [6-8], exploit geodesic convexity. In machine learning, it arises in matrix completion [9, 28, 33], dictionary learning [11, 26], robust subspace recovery [39], mixture models [18] and optimization under orthogonality constraints [14]. In statistics, some basic problems like estimating the shape of an elliptical distribution [16, 35] or estimation matrix normal models [4, 29] are best viewed through the lens of geodesic convexity.