Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space

@misc{criscitiello2026tight,
  title = {{Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space}},
  author = {Christopher Criscitiello},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.26815},
  eprint = {2610.26815},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.26815},
}

TY  - UNPB
TI  - Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space
AU  - Christopher Criscitiello
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.26815
UR  - https://arxiv.org/abs/2610.26815
AB  - We determine the dimension-independent first-order query complexity of minimizing a Lipschitz geodesically convex (g-convex) function on hyperbolic space. Given a ball of radius r containing a global minimizer, we prove that Ω(ζ_r/ε^2) queries are necessary to attain accuracy εMr, where M is the Lipschitz constant and ζ_r=r/tanh r captures the effect of curvature. This matches the known O(ζ_r/ε^2) upper bound for the Riemannian subgradient method (Zhang and Sra, 2016). This is the first query-complexity result for g-convex optimization that is tight simultaneously in curvature and target accuracy. The standard Euclidean recipe of constructing hard instances as maxima of affine functions does not transfer to hyperbolic space, so the lower bound requires a new mechanism. Our starting point is the worst-function construction of Criscitiello and Boumal (2023, Appendix A). It gives the same lower bound for a subclass of algorithms, including the subgradient method, whose queries remain in prescribed g-convex regions. We retain this geometric setup and carefully tune and augment their hard function to accommodate every deterministic first-order algorithm. The key new mechanism is an advance-or-stall scheme: when a query lies in these regions, the oracle reveals at most one new information direction (advance); when a query leaves them, we show that the oracle can answer without revealing any new hidden direction (stall). Unlike earlier curvature-dependent lower bounds, the proof uses no ball-packing argument.
ER  -