Curvature and complexity: Better lower bounds for geodesically convex optimization

Christopher Criscitiello, Nicolas Boumal

We study the query complexity of geodesically convex (g-convex) optimization on a manifold. To isolate the effect of that manifold's curvature, we primarily focus on hyperbolic spa…