  Hamilton and Moitra (2021) showed that, in certain regimes, it is not
possible to accelerate Riemannian gradient descent in the hyperbolic plane if
we restrict ourselves to algorithms which make queries in a (large) bounded
domain and which receive gradients and function values corrupted by a (small)
amount of noise. We show that acceleration remains unachievable for any
deterministic algorithm which receives exact gradient and function-value
information (unbounded queries, no noise). Our results hold for the classes of
strongly and nonstrongly geodesically convex functions, and for a large class
of Hadamard manifolds including hyperbolic spaces and the symmetric space
$\mathrm{SL}(n) / \mathrm{SO}(n)$ of positive definite $n \times n$ matrices of
determinant one. This cements a surprising gap between the complexity of convex
optimization and geodesically convex optimization: for hyperbolic spaces,
Riemannian gradient descent is optimal on the class of smooth and and strongly
geodesically convex functions, in the regime where the condition number scales
with the radius of the optimization domain. The key idea for proving the lower
bound consists of perturbing the hard functions of Hamilton and Moitra (2021)
with sums of bump functions chosen by a resisting oracle.

Optimization and Control;Computational Complexity;Numerical Analysis;Differential Geometry;Numerical Analysis