Making first-order linear programming parameterized by circuit imbalance effective: computable parameters without guessing

The first-order method of Cole, Hertrich, Tao and Végh (2023/2025) solves a linear program LP$(A,b,c,u)$ to $\delta$-feasible and $\delta$-optimal accuracy in a number of gradient updates polynomial in the max circuit imbalance $\bar\kappa(\mathcal{X}_A)$ of the constraint matrix and only logarithmic in the right-hand side, cost, and capacity vectors — polynomial time for totally unimodular $A$, where primal-dual first-order analyses can be arbitrarily slow. The authors flag three effectiveness gaps; the first defines this problem. First, the algorithm must be given an upper bound $\hat\kappa\ge\bar\kappa(\mathcal{X}_A)$, but approximating the circuit imbalance within a $2^{\mathrm{poly}(m)}$ factor is NP-hard (Tunçel 1999; Dadush–Huiberts–Natura–Végh 2023); the published workaround restarts with a doubled guess after each certified failure, and no nontrivial efficiently computable a priori bound or alternative parameter is known. Second, the variable-fixing mechanism works from approximate solutions and may fix to $0$ variables that are positive in every exact optimal solution — a tradeoff the authors accept since the method targets approximate solutions. Third, guaranteeing a variable fixing in every outer iteration is possible only by projecting the cost vector onto $\ker(A)$ — an exact linear-system solve — as in strongly polynomial frameworks; the authors deliberately decline this preprocessing and proceed with 'lazier updates'. The problem asks for a first-order LP method with the same type of convergence guarantees that eliminates the first dependency on unavailable information — the guessed upper bound on $\bar\kappa(\mathcal{X}_A)$ — or for a proof that no polynomial-time computable parameter can support such guarantees.

Background

Linear programming (LP) asks to minimize a linear objective over a polyhedron. In the form used here, LP$(A,b,c,u)$ is the problem $\min\langle c,x\rangle$ subject to $Ax=b$, $\mathbf{0}\le x\le u$, with constraint matrix $A\in\mathbb{R}^{m\times n}$, right-hand side $b\in\mathbb{R}^m$, and cost and capacity vectors $c,u\in\mathbb{R}^n$.

First-order methods (FOMs) are iterative algorithms whose steps use only gradient evaluations, vector updates, and cheap projections — no matrix factorizations. For LP they are attractive on very large instances: primal-dual hybrid gradient (PDHG), a first-order method for the saddle-point formulation of LP, powers practical solvers such as PDLP. The known linear-convergence analyses of such methods are governed by Hoffman constants: for a polyhedron $P=\{x:Bx\le d\}$, the Hoffman constant $\theta(B)$ is the least number with $\mathrm{dist}(x,P)\le\theta(B)\cdot\|Bx-d\|$ for all $x$ — an error-bound constant measuring how much a feasibility residual forces distance to the feasible set. For primal-dual formulations the relevant Hoffman constant is that of a large matrix encoding both the primal and the dual systems, and it depends on $b$, $c$, and $u$; Cole, Hertrich, Tao, and Végh show it can be arbitrarily large even when $A$ is totally unimodular (TU; every square subdeterminant of $A$ is $0$, $\pm1$) — the class of network-like matrices for which LPs should be easy. Analyses based on restarts and sharpness (Applegate, Hinder, Lu, and Lubin) and restarted Halpern PDHG (Lu and Yang) refine this picture but stay within data-dependent parameters.

A different line of work asks for running times depending only on the constraint matrix. Tardos gave a strongly polynomial algorithm for LP — polynomial in the dimensions and the entries of $A$, independent of the encoding lengths of $b$ and $c$. Vavasis and Ye gave a layered-least-squares interior-point method (an interior-point method whose steps solve least-squares problems on nested subsets of variables) with iteration bound polynomial in the condition measure $\bar\chi(A)$, a measure of how far the columns of $A$ are from degenerate linear dependencies, and logarithmic in $b$ and $c$. Tunçel proved that approximating $\bar\chi(A)$ is NP-hard, and Dadush, Huiberts, Natura, and Végh proved the analogous hardness for the circuit imbalance measure: no $2^{\mathrm{poly}(m)}$-factor approximation unless $P=NP$. Their own scaling-invariant algorithm also copes with the unknown condition measure only through a Renegar-style guessing scheme with restarts.

Circuit imbalances. For a linear subspace $W\subseteq\mathbb{R}^n$, an elementary vector (or circuit) of $W$ is a nonzero vector of $W$ with inclusion-minimal support. The circuit imbalance measure $\kappa(W)$ is the largest ratio $|g_i|/|g_j|$ between two nonzero entries of an elementary vector $g$ of $W$; for rational $W$, the max circuit imbalance measure $\bar\kappa(W)$ is the smallest integer $k$ such that every elementary vector can be rescaled to integer entries in $[-k,k]$. For LP one uses $\mathcal{X}_A=\ker(A|-I_m)\subseteq\mathbb{R}^{n+m}$. Then $\bar\kappa(\mathcal{X}_A)=1$ if $A$ is TU, $\bar\kappa(\mathcal{X}_A)$ is at most the maximal absolute subdeterminant $\Delta(A)$ but often much smaller, and the Hoffman-type proximity bound satisfies $\theta_{1,\infty}(A)\le\kappa(\mathcal{X}_A)$. The survey of Ekbatani, Natura, and Végh recounts these measures and their roles in matrix-only LP running times, proximity theory, and circuit-diameter bounds (Dadush, Koh, Natura, and Végh).

The source result. Cole, Hertrich, Tao, and Végh gave the first first-order method for LP whose convergence is parameterized by circuit imbalance rather than by a Hoffman constant of the full data. The algorithm repeatedly applies R-FGM — a restarted accelerated projected-gradient method of Necoara, Nesterov, and Glineur for smooth functions satisfying quadratic growth ($f(x)-f^{*}\ge(\mu/2)\,\mathrm{dist}(x,X^{*})^{2}$, which yields linear convergence despite non-strong convexity) — to least-squares reformulations, inside an outer loop that gradually fixes variables to their bounds: an approximate analogue of the rounding in Tardos's framework, which Dadush, Natura, and Végh later developed into a black box converting approximate solutions into exact ones. The main theorem states that a $\delta$-feasible and $\delta$-optimal solution (approximately feasible and approximately optimal to relative accuracy $\delta$), or a conclusion of infeasibility, is obtained in

$O\big(n^{1.5}m^{2}\|A\|_{1}^{2}\cdot\bar\kappa^{3}(\mathcal{X}_A)\cdot\log^{3}((\|u\|_{1}+\|b\|_{1})\,nm\,\kappa(\mathcal{X}_A)\|A\|_{1}/\delta)\big)$

gradient updates: polynomial in the circuit imbalance, only logarithmic in $b$, $c$, $u$. For TU matrices this is polynomial time, whereas Hinder's analysis of restarted PDHG on TU programs is linear in $\|b\|_{\infty}+\|c\|_{\infty}$.

The authors flag three limitations; the first motivates this problem, while the second and third are tradeoffs the paper accepts or deliberately declines. First, the algorithm must be supplied an upper bound $\hat\kappa\ge\bar\kappa(\mathcal{X}_A)$, yet approximating $\kappa$ is NP-hard; the workaround runs the method with $\hat\kappa=1$ and restarts with the guess doubled after each certified failure. The doubling preserves the asymptotic bound, but no nontrivial, efficiently computable a priori bound or alternative parameter is known that would remove the guessing. Second, the fixing rule works from approximate primal-dual pairs and may fix to $0$ variables that are small but positive in every exact optimal solution — acceptable for approximate answers, but a robustness gap relative to the exact problem. Third, one can force a variable fixing in every outer iteration by replacing $c$ with its minimum-$\ell_{2}$-norm reduced cost $c-A^{\top}\pi$, i.e. the orthogonal projection of $c$ onto $\ker(A)$, as the strongly polynomial frameworks do; but computing that projection means solving a linear system, so the authors settle for 'lazier updates' with weaker per-iteration progress.

Problem Statement

Resolve the effectiveness gap that Cole, Hertrich, Tao, and Végh leave in their circuit-imbalance-parameterized first-order method for LP$(A,b,c,u)$: a first-order method whose convergence guarantee has the same type as their main theorem — a bound on the number of gradient updates that is polynomial in a parameter of the constraint matrix $A$ alone (as $\bar\kappa^{3}(\mathcal{X}_A)$ is there), polynomial in $n$, $m$, and $\|A\|_{1}$, and logarithmic in $\|b\|_{1}$, $\|c\|_{\infty}$, $\|u\|_{1}$, and $1/\delta$ (hence polynomial in the dimensions for totally unimodular $A$) — while eliminating the dependence on unavailable information in the form of the guessed upper bound $\hat\kappa\ge\bar\kappa(\mathcal{X}_A)$, i.e. without a doubling loop or restarts after certified failure. Whether this is attainable is the question: whether a polynomial-time computable bound $K(A)$ with $\bar\kappa(\mathcal{X}_A)\le K(A)$, or some other polynomial-time computable parameter of $A$, can replace $\hat\kappa$ in a method (possibly adapted) whose iteration bound is of the required type — polynomial in that computable parameter, with the same logarithmic data dependence and polynomial dimension dependence on totally unimodular $A$ — or whether, under an explicit standard complexity assumption, no polynomial-time computable parameter or bound can support guarantees of this type.

Trivial parameter choices do not qualify: the only obvious a priori bound, a Hadamard-style upper bound on the maximal subdeterminant $\Delta(A)$, is exponential in $m$ and makes a polynomial-in-$K$ guarantee vacuous, and retaining the doubling-guessing scheme is precisely what the question asks to remove.

References

1. Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh: 'A first order method for linear programming parameterized by circuit imbalance', Mathematical Programming (available online 2025-08-19; print issue 2026). DOI: 10.1007/s10107-025-02264-7, https://doi.org/10.1007/s10107-025-02264-7
2. Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh: 'A First Order Method for Linear Programming Parameterized by Circuit Imbalance', IPCO 2024, Lecture Notes in Computer Science, pp. 57-70. DOI: 10.1007/978-3-031-59835-7_5, https://doi.org/10.1007/978-3-031-59835-7_5
3. Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh: 'A First Order Method for Linear Programming Parameterized by Circuit Imbalance', arXiv:2311.01959 (2023, v2 2024-03-27), https://arxiv.org/abs/2311.01959
4. Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh: 'A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix', Mathematical Programming (2023). DOI: 10.1007/s10107-023-01956-2, https://doi.org/10.1007/s10107-023-01956-2
5. Levent Tunçel: 'Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard', Mathematical Programming 86(1), 219-223 (1999). DOI: 10.1007/s101070050087, https://doi.org/10.1007/s101070050087
6. S. A. Vavasis, Y. Ye: 'A primal-dual interior point method whose running time depends only on the constraint matrix', Mathematical Programming 74(1), 79-120 (1996). DOI: 10.1007/BF02592148, https://doi.org/10.1007/BF02592148
7. Éva Tardos: 'A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs', Operations Research 34(2), 250-256 (1986). DOI: 10.1287/opre.34.2.250, https://doi.org/10.1287/opre.34.2.250
8. Daniel Dadush, Bento Natura, László A. Végh: 'Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers', FOCS 2020. arXiv:2009.04942, https://arxiv.org/abs/2009.04942
9. I. Necoara, Y. Nesterov, F. Glineur: 'Linear convergence of first order methods for non-strongly convex optimization', Mathematical Programming 175, 69-107 (2019). DOI: 10.1007/s10107-018-1232-1, https://doi.org/10.1007/s10107-018-1232-1
10. Farbod Ekbatani, Bento Natura, László A. Végh: 'Circuit imbalance measures and linear programming', Surveys in Combinatorics 2022, London Mathematical Society Lecture Note Series, pp. 64-114, Cambridge University Press (2022). arXiv:2108.03616, https://arxiv.org/abs/2108.03616
11. Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi, Thomas Rothvoss, Neta Singer: 'Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure', Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026). DOI: 10.1137/1.9781611978971.34; arXiv:2510.20301 (2025), https://arxiv.org/abs/2510.20301
12. Jonah Bondar, Stephen Vavasis: 'On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation', arXiv:2608.12550 (2026), https://arxiv.org/abs/2608.12550
13. Steffen Borgwardt, Nicholas Crawford, Sean Kafer, Jon Lee, Angela Morrison: 'On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems', arXiv:2512.05223 (2025), https://arxiv.org/abs/2512.05223
14. David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O'Donoghue, Warren Schudy: 'PDLP: a practical first-order method for large-scale linear programming', Mathematical Programming Computation (2026). DOI: 10.1007/s12532-026-00309-2; arXiv:2501.07018, https://arxiv.org/abs/2501.07018
15. Jakub Komárek, Martin Koutecký: 'Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization', Proceedings of the 22nd International Symposium on Experimental Algorithms (SEA 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 301, pp. 18:1-18:21. DOI: 10.4230/LIPIcs.SEA.2024.18, https://doi.org/10.4230/LIPIcs.SEA.2024.18
16. Satoru Fujishige, Tomonari Kitahara, László A. Végh: 'An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem', Mathematical Programming (2024). DOI: 10.1007/s10107-024-02077-0; arXiv:2211.02560, https://arxiv.org/abs/2211.02560
17. Javier Peña: 'An easily computable upper bound on the Hoffman constant for homogeneous inequality systems', arXiv:2302.02193 (2023), https://arxiv.org/abs/2302.02193
18. Oliver Hinder: 'Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs', arXiv:2309.03988 (2023), https://arxiv.org/abs/2309.03988
19. Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh: 'On circuit diameter bounds via circuit imbalances', Mathematical Programming (2024). DOI: 10.1007/s10107-024-02107-x; arXiv:2111.07913, https://arxiv.org/abs/2111.07913
20. David Applegate, Oliver Hinder, Haihao Lu, Miles Lubin: 'Faster first-order primal-dual methods for linear programming using restarts and sharpness', Mathematical Programming 201(1), 133-184 (2023). DOI: 10.1007/s10107-022-01901-9, https://doi.org/10.1007/s10107-022-01901-9
21. Haihao Lu, Jinwen Yang: 'Restarted Halpern PDHG for Linear Programming', arXiv:2407.16144 (2024), https://arxiv.org/abs/2407.16144