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(DLT)\) 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\zeta  T, \) where \( \zeta=|\kappa|D/\tanh(|\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(DLT)\) regret, yet the additional \(\zeta\) factor is unavoidable for first-order feedback whenever either the geometric-span condition holds or the algorithm is deterministic.