CS Paper Radar

On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation

Jonah Bondar, Stephen Vavasis

cs.CC math.OC ·submitted 2026-08-12 19:39 UTC · v2
theory

Abstract

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\barχ_A^*$. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\barχ_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number $\barχ_A^*$ as the maximum $\barχ_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) introduced the optimal circuit imbalance measure $κ_W^*$, which serves as a lower bound for $\barχ^*_A$. Instances with artificially large optimal circuit imbalance measures $κ_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $κ_W^*$ grows exponentially in the number of approximation steps. Since $κ_W^*$ lower bounds $\barχ_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

Closest papers

Nearest neighbours by meaning across the whole index.

Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves

cs.DS math.OC ·2026-09-25 ·Zhao Song
similarity 0.62
Abstract

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $ε$ using $O(\sqrt n\log^{13}m\cdot\log(mU/ε))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/ε))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/ε))$ such linear-system solves suffice.

0.26

Efficient Online Inverse Optimization with $O(d)$ Regret

cs.LG cs.DS ·2026-09-11 ·Yang Cai, Anupam Gupta, Vineet Gupta, Guru Guruganesh, Yanchen Jiang +5 more
highly cited similarity 0.60
Abstract

We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d^{2})$ time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs $T^{Θ(d)}$ a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.

0.45

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

cs.DS cs.CCmath.CO ·2026-09-09 ·Sergei Kudria, Jason Luo, Mahbod Majid
theory similarity 0.60
Abstract · 44 pages

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

0.45

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

cs.DS stat.MLcs.LG ·2026-09-22 ·Shinsaku Sakaue
theory similarity 0.60
Abstract

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

0.41

Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation

cs.LG stat.MLmath.NA ·2026-09-14 ·Aleksander Tankman
theory similarity 0.59
Abstract · 33 pages. Ancillary code reproduces the numerical constants of Appendix B. Complements arXiv:2604.26444, which constructs deep KAN represent…

Deep spline superposition networks face a tension between approximation order and stability across depth. We study approximation under a hard layerwise Lipschitz budget, and organise it around two quantities: the factorisation stability complexity of a given deep factorisation, and the budget-compatible approximation complexity of a discretisation operator. First, we solve exactly the finite-depth diagonal balancing problem for a fixed chain of nonnegative envelope matrices: the optimal uniform layer budget equals $\|M_{L-1}\cdots M_0\|_{\infty\to\infty}^{1/L}$, attained by an explicit one-pass minimiser, for rectangular layers, with a complete treatment of degeneracies and non-attainment. The optimum can be arbitrarily larger than the Lipschitz constant of the network itself, because passing to envelopes destroys sign cancellation. Second, we give a constructive spline discretisation theorem preserving the budget up to a controlled slack, with an explicit grid threshold. Conversely, for linear spline-valued operators that preserve the budget exactly, we prove budget-compatible minimax lower bounds on classes constrained simultaneously in the first and third derivative norms -- a constraint pair that is forced by the problem and that rules out the usual scaling escapes. Finally, we show that the corresponding layer errors need not cancel under composition: for every operator of the class there is a stable depth-$L$ tower realising a constant fraction of the accumulated error, so the linear-in-depth accumulation of the upper bound is not a proof artefact.

0.40

Product-Aware Deterministic Rounding for Quantized Matrix Multiplication

cs.LG cs.DScs.IT ·2026-09-11 ·Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal
similarity 0.58
Abstract · 30 pages, 7 figures

Scalar rounding decisions interact through matrix multiplication. We study deterministic product-aware rounding after scales, clipping bounds, and grids are fixed, with each active scalar choosing between adjacent levels. For dynamic activation rounding, null-space reduction preserves the relaxed product while leaving at most $r$ fractional decisions, where $r$ is the rank of the active gap-weighted weight block. Conditional-expectation completion gives a deterministic polynomial-time algorithm with squared product error at most $ \mathrm{OPT}_{\mathrm{dyn}}+rν_{\max}^2/4$, where $\mathrm{OPT}_{\mathrm{dyn}}$ is the best admissible error and $ν_{\max}$ is the largest row norm of that block. For reusable static weights, the exact expected product-loss metric is the uncentered input second moment with fixed output bias; free bias recalibration yields the centered covariance. Exact optimization is NP-hard even at rank one. In balanced blocks with $K=1024$ and $r=16$, conditional- expectation completion attains a dither-normalized median error of $0.010$, compared with $0.899$ for round-to-nearest. Clipping-aware initialization reduces median normalized error by a factor of $43.4$ at ten-percent clipping. Held-out Digits experiments show that retaining the input mean or correcting the output bias improves median product error over round-to-nearest in all four tested bit-width and calibration-size settings.

0.30

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

cs.DS cs.CCmath.NA ·2026-09-29 ·Jonathan A. Kelner
similarity 0.58
Abstract

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.

0.09

Computing Robustness to Sparse Diagonal Uncertainty

eess.SY math.OC ·2026-09-13 ·Christoffer Kjellson, Emma Tegling
theory similarity 0.57
Abstract

A new robustness metric $ν$ was recently proposed as a substitute for the structured singular value $μ$ to better capture robustness to sparse diagonal uncertainty, but its computation has remained an open problem. In this paper, we show that computing $ν$ is equivalent to maximizing the spectral radius of a nonnegative matrix product. This equivalence allows us to transfer existing results on spectral-radius maximization to $ν$, including a refined upper bound and conditions under which the bounds coincide. We then provide reformulations and structural results that enable an algorithm to solve the nonconvex optimization problem for nontrivial problems using global solvers. This also enables identification of the most fragile parts of the system. Our results do not yet provide a scalable solution for computing $ν$, but they are an important step toward computability and interpretability.

0.17