Negative curvature obstructs the existence of good barriers for interior-point methods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914458556694528 |
|---|---|
| author | Criscitiello, Christopher Nieuwboer, Harold Walter, Michael |
| author_facet | Criscitiello, Christopher Nieuwboer, Harold Walter, Michael |
| contents | 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 polynomially with the domain's diameter. By extension, the same holds for the positive-definite matrices and other symmetric Hadamard spaces. This growth implies a fundamental limitation: interior-point methods relying on barriers for a ball cannot efficiently solve challenging scaling problems, such as tensor scaling, where the domain's diameter can be exponentially large in the input size. Our results are partially inspired by, and complement, lower bounds on the condition number of geodesically convex functions established by Hamilton and Moitra (NeurIPS'21). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07319 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Negative curvature obstructs the existence of good barriers for interior-point methods Criscitiello, Christopher Nieuwboer, Harold Walter, Michael Optimization and Control Differential Geometry 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 polynomially with the domain's diameter. By extension, the same holds for the positive-definite matrices and other symmetric Hadamard spaces. This growth implies a fundamental limitation: interior-point methods relying on barriers for a ball cannot efficiently solve challenging scaling problems, such as tensor scaling, where the domain's diameter can be exponentially large in the input size. Our results are partially inspired by, and complement, lower bounds on the condition number of geodesically convex functions established by Hamilton and Moitra (NeurIPS'21). |
| title | Negative curvature obstructs the existence of good barriers for interior-point methods |
| topic | Optimization and Control Differential Geometry |
| url | https://arxiv.org/abs/2604.07319 |