Curvature-Dependent Lower Bounds for Riemannian Online Convex Optimization

Abstract

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.