Negative curvature obstructs the existence of good barriers for interior-point methods
Interior-point methods (IPMs) are a cornerstone of Euclidean convex optimization, due to their strong theoretical guarantees and practical performance. Motivated by scaling problems, recent work by Hirai and the last two authors (FOCS'23) extended IPMs to geodesically convex optimization on Hadamard manifolds. Crucially, the complexity of IPMs (both in Euclidean and Hadamard spaces) is governed by the \emph{barrier parameter} of the domain. Here we prove that already in hyperbolic space, several natural domains -- including geodesic balls and triangles -- have a barrier parameter that grows…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.07319
curl -X POST /api/v1/records/arxiv/2604.07319/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.07319/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'