Curvature-Dependent Lower Bounds for Riemannian Online Convex Optimization

In Euclidean online convex optimization, first-order and full-information feedback share the minimax regret (\Theta(DL\sqrt{T})) over (T) rounds, as convex losses can be replaced by their linearizations. On Riemannian manifolds this reduction fails, because the corresponding first-order surrogate of a geodesically convex loss is generally not geodesically convex; we show that this failure has provable consequences. For online convex optimization on Hadamard manifolds with sectional curvature bounded below by (\kappa<0) and feasible diameter (D), we construct hard hyperbolic-space instances yielding first-order regret lower bounds at the scale ( DL\sqrt{\zeta\, T}, ) where ( \zeta=\sqrt{|\kappa|}D/\tanh(\sqrt{|\kappa|}D) ) is the curvature--diameter factor. Our first lower bound applies to all (possibly randomized) first-order algorithms satisfying a natural geometric-span condition, holding almost surely over the algorithm's internal randomness. Our second lower bound removes the geometric-span restriction for deterministic first-order algorithms, provided the feasible diameter satisfies (D=\Omega(\log T)); the proof rests on a new construction that confines the hidden comparator to a single horosphere in hyperbolic space. Combined with existing curvature-free full-information upper bounds, these results yield a feedback-model separation on Hadamard manifolds: full-information algorithms attain (O(DL\sqrt{T})) regret, yet the additional (\sqrt{\zeta}) factor is unavoidable for first-order feedback whenever either the geometric-span condition holds or the algorithm is deterministic.