Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.26815
curl -X POST /api/v1/records/arxiv/2610.26815/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.26815/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'