Geodesically Convex Optimization in Hyperbolic Space: Matching Lower Bounds
Abstract
We establish matching lower bounds for deterministic first-order optimization of globally Lipschitz geodesically convex functions on hyperbolic space. A global minimizer lies within distance r of a known point, each query returns an exact function value and a selected Riemannian subgradient, and the target objective gap is ε Lr, where L is the Lipschitz constant. For sectional curvature −k2<0, let ρ=kr and ζ=ρ/tanhρ. The optimal worst-case query complexity Q⋆, taken uniformly over dimensions, satisfies Q⋆(ρ,ε)=Θ(ζε−2) for every ρ>0 and 0<ε≤1/64. The new lower bound covers arbitrary adaptive deterministic queries and arbitrary outputs, matching the projected-subgradient upper rate of Zhang and Sra (2016). It removes the geodesic-span and historical-halfspace restrictions of earlier matching lower bounds. The construction extends a radial source from a convex carrier with boundary. A small residual cut selects minimizer candidates while an exact hyperbolic persistence inequality keeps every historical contact valid under future carrier growth. One fixed globally convex objective and one fixed subgradient selection consequently realize all exact replies simultaneously. Each query consumes O(ε2) of a geometric potential whose available budget is Θ(ζ), yielding the product lower bound in a dimension linear in the query horizon.
Related
- Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space
- Region-Preserving Accelerated Gradient Methods for Geodesically Convex Optimization
- Pfaffian Positivity for Convex Kernels and Optimal Matching Bounds
- Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
- Quantum lower bounds for convex optimization and real matrix-vector query problems
BibTeX
@misc{wu2026geodesically,
title = {{Geodesically Convex Optimization in Hyperbolic Space: Matching Lower Bounds}},
author = {Wendao Wu and Haihan Zhang and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12184},
eprint = {2610.12184},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12184},
}
RIS
TY - UNPB
TI - Geodesically Convex Optimization in Hyperbolic Space: Matching Lower Bounds
AU - Wendao Wu
AU - Haihan Zhang
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.12184
UR - https://arxiv.org/abs/2610.12184
AB - We establish matching lower bounds for deterministic first-order optimization of globally Lipschitz geodesically convex functions on hyperbolic space. A global minimizer lies within distance r of a known point, each query returns an exact function value and a selected Riemannian subgradient, and the target objective gap is ε Lr, where L is the Lipschitz constant. For sectional curvature −k^2<0, let ρ=kr and ζ=ρ/tanhρ. The optimal worst-case query complexity Q^⋆, taken uniformly over dimensions, satisfies Q^⋆(ρ,ε)=Θ(ζε^−2) for every ρ>0 and 0<ε≤1/64. The new lower bound covers arbitrary adaptive deterministic queries and arbitrary outputs, matching the projected-subgradient upper rate of Zhang and Sra (2016). It removes the geodesic-span and historical-halfspace restrictions of earlier matching lower bounds. The construction extends a radial source from a convex carrier with boundary. A small residual cut selects minimizer candidates while an exact hyperbolic persistence inequality keeps every historical contact valid under future carrier growth. One fixed globally convex objective and one fixed subgradient selection consequently realize all exact replies simultaneously. Each query consumes O(ε^2) of a geometric potential whose available budget is Θ(ζ), yielding the product lower bound in a dimension linear in the query horizon.
ER -