{"id":"arxiv/2610.26815","url":"https://arxiv.org/abs/2610.26815","tags":["math.OC","math.DG","math.NA"],"score":0,"title":"Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space","domain":"math.OC","source":"arxiv","authors":["Christopher Criscitiello"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-19","reactions":{}}