  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 spaces. In a variety of settings (smooth or not; strongly
g-convex or not; high- or low-dimensional), known upper bounds worsen with
curvature. It is natural to ask whether this is warranted, or an artifact.
  For many such settings, we propose a first set of lower bounds which indeed
confirm that (negative) curvature is detrimental to complexity. To do so, we
build on recent lower bounds (Hamilton and Moitra, 2021; Criscitiello and
Boumal, 2022) for the particular case of smooth, strongly g-convex
optimization. Using a number of techniques, we also secure lower bounds which
capture dependence on condition number and optimality gap, which was not
previously the case.
  We suspect these bounds are not optimal. We conjecture optimal ones, and
support them with a matching lower bound for a class of algorithms which
includes subgradient descent, and a lower bound for a related game. Lastly, to
pinpoint the difficulty of proving lower bounds, we study how negative
curvature influences (and sometimes obstructs) interpolation with g-convex
functions.
