pith. machine review for the scientific record. sign in

arxiv: 2604.07319 · v1 · submitted 2026-04-08 · 🧮 math.OC · math.DG

Recognition: unknown

Negative curvature obstructs the existence of good barriers for interior-point methods

Christopher Criscitiello , Harold Nieuwboer , Michael Walter
Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:58 UTC · model grok-4.3

classification 🧮 math.OC math.DG
keywords interior-point methodsHadamard manifoldshyperbolic spacebarrier parametergeodesically convex optimizationscaling problemsnegative curvature
0
0 comments X

The pith

Negative curvature makes barrier parameters for interior-point methods grow polynomially with domain diameter

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that in hyperbolic space, the barrier parameter for natural domains such as geodesic balls and triangles grows polynomially as the diameter increases. Interior-point methods depend on these parameters to achieve their iteration bounds, so polynomial growth implies that the methods lose efficiency when domains become large. The result extends directly to the cone of positive definite matrices and other symmetric Hadamard spaces. It therefore rules out efficient use of barrier-based interior-point methods on scaling problems whose feasible regions can have diameter exponential in the input size.

Core claim

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.

What carries the argument

The barrier parameter of a domain on a Hadamard manifold, which governs the iteration complexity of interior-point methods for geodesically convex optimization.

Load-bearing premise

That the observed polynomial growth of the barrier parameter for geodesic balls and triangles cannot be avoided by choosing different barriers or different domains that still capture the scaling problems of interest.

What would settle it

An explicit self-concordant barrier for geodesic balls in hyperbolic space whose parameter remains bounded by a constant independent of diameter would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.07319 by Christopher Criscitiello, Harold Nieuwboer, Michael Walter.

Figure 1
Figure 1. Figure 1: A hyperbolic equilateral triangle, see Section 3. Hyperbolic plane (Poincaré disk model) horoball 𝑫 𝑝∗ horoball [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Geometric construction in H2 for the proof of Theorem 1.3. See Section 4. By the definition of β, we conclude that there exists s ∈ [−d(p, q+), d(p, q+)] with (∇2F)γ(s) (γ ′ (s), γ′ (s)) ≥ r − 1 16R2 . We can transfer this lower bound on (∇2F)γ(s) to a lower bound on (∇2F)γ(0). We have two cases: • If (∇2F)p(sγ′ (0), sγ′ (0)) < 1 4 , then Property (P1) implies s 2 (∇2F)p(γ ′ (0), γ′ (0)) = (∇2F)p(sγ′ (0), … view at source ↗
Figure 4
Figure 4. Figure 4: Schematic representations of the points used in the proof of [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
read the original abstract

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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that in hyperbolic space, the barrier parameter for natural domains such as geodesic balls and triangles grows polynomially with the domain diameter. This lower bound extends to the manifold of positive-definite matrices and other symmetric Hadamard spaces, implying that barrier-based interior-point methods cannot efficiently solve scaling problems (e.g., tensor scaling) whose feasible domains have diameter exponential in the input size. The result complements prior lower bounds on the condition number of geodesically convex functions.

Significance. If the central lower-bound proof holds, the result identifies a concrete geometric obstruction (negative curvature) to the existence of efficient self-concordant barriers on large-diameter domains. This supplies a theoretical explanation for the practical limitations of IPMs on certain Hadamard-manifold problems and directly strengthens the complexity-theoretic picture initiated by the FOCS'23 extension of IPMs to geodesic convexity.

major comments (2)
  1. [Main theorem (likely Theorem 1 or 2)] The central claim that the barrier parameter grows polynomially with diameter is load-bearing for the negative result. The precise degree of the polynomial (and any dependence on dimension or curvature) must be stated explicitly in the main theorem, because only then can one verify that the growth is incompatible with the FOCS'23 complexity bound when the diameter is exponential in the input size.
  2. [Section on extension to symmetric spaces] The extension from hyperbolic space to the positive-definite matrix manifold (and other symmetric Hadamard spaces) is asserted by 'extension.' The precise reduction—how the barrier parameter on a geodesic ball in hyperbolic space maps to the corresponding parameter on the matrix manifold—needs to be spelled out, including any distortion factors introduced by the embedding or the Riemannian metric.
minor comments (2)
  1. [Introduction] The abstract states that the result is 'partially inspired by' Hamilton-Moitra (NeurIPS'21). A short paragraph in the introduction clarifying the precise technical relationship (e.g., whether the barrier-parameter lower bound implies or is implied by their condition-number lower bound) would improve readability.
  2. [Preliminaries] Notation for the barrier parameter (often denoted ν or θ in the IPM literature) should be fixed early and used consistently; the manuscript occasionally switches between 'barrier parameter' and 'self-concordance parameter' without explicit cross-reference.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation and constructive feedback. We address each major comment below and will revise the manuscript accordingly to improve clarity.

read point-by-point responses

  1. Referee: [Main theorem (likely Theorem 1 or 2)] The central claim that the barrier parameter grows polynomially with diameter is load-bearing for the negative result. The precise degree of the polynomial (and any dependence on dimension or curvature) must be stated explicitly in the main theorem, because only then can one verify that the growth is incompatible with the FOCS'23 complexity bound when the diameter is exponential in the input size.

    Authors: We agree that explicitly stating the precise polynomial degree and its dependencies will strengthen the main theorem. The proof of our central result (Theorem 1) establishes a quadratic lower bound: for geodesic balls in hyperbolic space of curvature -1, the barrier parameter ν satisfies ν ≥ c · diam² for a positive constant c independent of dimension. We will revise the theorem statement to include this explicit form (along with the general dependence on curvature), making the incompatibility with the FOCS'23 IPM complexity bounds immediate when the diameter is exponential in the input size. revision: yes

  2. Referee: [Section on extension to symmetric spaces] The extension from hyperbolic space to the positive-definite matrix manifold (and other symmetric Hadamard spaces) is asserted by 'extension.' The precise reduction—how the barrier parameter on a geodesic ball in hyperbolic space maps to the corresponding parameter on the matrix manifold—needs to be spelled out, including any distortion factors introduced by the embedding or the Riemannian metric.

    Authors: We acknowledge that the extension is currently stated concisely. We will add a dedicated paragraph (or short subsection) detailing the reduction. Using the standard embedding of hyperbolic space into the positive-definite matrix manifold, we will show that the barrier parameter on a geodesic ball maps with a multiplicative distortion factor bounded by a constant depending only on dimension and curvature (independent of diameter). The same argument applies to other symmetric Hadamard spaces, preserving the polynomial growth. This will be included in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes a mathematical lower bound on the barrier parameter for geodesic balls and triangles in hyperbolic space via direct geometric arguments, extending to symmetric Hadamard manifolds. This negative result does not reduce by construction to any fitted quantity, self-referential definition, or load-bearing self-citation chain; the cited FOCS'23 work supplies only the motivating complexity framework while the core proof remains independent and externally verifiable through hyperbolic geometry. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a mathematical proof relying on standard definitions from differential geometry and convex optimization; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions and properties of barrier functions and geodesic convexity on Hadamard manifolds
    Invoked implicitly when extending Euclidean IPM theory to hyperbolic space and positive-definite matrices.

pith-pipeline@v0.9.0 · 5499 in / 1305 out tokens · 72024 ms · 2026-05-10T16:58:47.289429+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

  1. [1]

    Cambridge University Press

    doi: 10.1017/9781009166164. (Cited on pgs. 4 and 5) J. van den Brand. A Deterministic Linear Program Solver in Current Matrix Multiplication Time. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259–

    work page doi:10.1017/9781009166164 2020

  2. [2]

    doi: 10.1137/1.9781611975994.16

    Society for Industrial and Applied Mathematics, 2019. doi: 10.1137/1.9781611975994.16. (Cited on pgs. 1) J. van den Brand, Y. T. Lee, A. Sidford, and Z. Song. Solving tall dense linear programs in nearly linear time. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 775–788, New York, NY, USA, June 2020. Associ...

    work page doi:10.1137/1.9781611975994.16 2019