The Condition-Number Barrier in Sparse Least Squares

In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed $γ\in(0,1]$, there is no randomized polynomial-time algorithm that, with probability at least $2/3$, returns a vector $x$ such that, writing $s=\lVert x\rVert_0$, \[ \lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0\leq k}\lVert Az-b\rVert_2^2+\varepsilon \quad\text{and}\quad s=O\!\left(k\,κ_{s+k}^{\,1-γ}\right), \] where $κ_r$ is the restricted condition number at sparsity level $r$. The result holds even on rational instances with $A$ of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.

Tubular Neighbourhoods of Pfaffian Sets and Applications to Neural Networks

We derive bounds for the volume of tubular neighbourhoods of smooth Pfaffian hypersurfaces, generalising known results for algebraic varieties. The bounds are given in terms of the Pfaffian format of the defining functions. As an application, we obtain tail bounds on the probability distribution of a condition number measuring the robustness of neural network classifiers with Pfaffian activation functions, in both the uniform and Gaussian settings. In the special case of single-hidden-layer sigmoid networks with rational weights, we derive polynomial-in-width bounds for tubular neighbourhoods of the decision boundary.

Restricted Dynamic Geometric Complexity: Certificates for Structured Preconditioning

Optimization geometrodynamics views optimizer state as evolving geometry. Its full positive-definite quadratic benchmark gives the least affine-invariant deformation needed to reduce condition number when arbitrary metrics are allowed. This paper records that benchmark in the present notation and develops restricted dynamic geometric complexity: an intrinsic certificate distance for reaching a target condition-number class when the metric is restricted to a specified family. The main proved results are monotonicity and submanifold-distance principles, diagonal and block reachability as linear matrix inequality feasibility problems, an exact two-dimensional diagonal complexity formula, and affine-invariant Kronecker projection theorems with normal equations, computable mismatch certificates, Armijo solver convergence, auxiliary self-conditioned K-target bounds, and Hessian-relative candidate certificates through an exact Kronecker Loewner-sandwich reachability condition, including a Kronecker expression threshold and a fixed-basis exact subproblem. Low-rank spectral models, curvature-proxy inflation, stochastic restricted complexity, discrete geometric length, and expression--estimation--flow--discretization accounting are presented as diagnostic interfaces rather than full optimizer characterizations. The resulting language turns structural preconditioner questions into geometric distance, reachability, and certificate problems. The repository includes deterministic toy and synthetic workflows that check diagonal expression gaps, block primal/dual certificates, Kronecker spectral width, and Hessian-relative Kronecker candidate certificates on small quadratic instances, together with low-rank spectral monotonicity.

On the Condition Number Upper Bound of the L-BFGS Inverse Hessian Approximation Matrix with a Two-Sided Geometric Envelope Safeguarding Mechanism

The limited-memory BFGS (L-BFGS) algorithm is a cornerstone of large-scale optimization due to its linear memory and computational costs. However, in ill-conditioned or non-convex landscapes, the implicit inverse Hessian approximation can suffer from an exploding condition number, leading to numerical instability and degraded convergence. To address this, we propose Two-Sided L-BFGS, a safeguarded variant that dynamically constrains the condition number of the inverse Hessian operator via a two-sided geometric envelope. Moreover, we show that Two-Sided L-BFGS preserves accumulated curvature information and maintains standard $O(mn)$ memory and per-iteration time complexities. We prove that this geometric envelope yields a uniform bound on the condition number of every inverse Hessian approximation generated by the algorithm. By tracking the algebraic evolution of the extreme eigenvalues through $m$ consecutive quasi-Newton updates starting from a scaled identity matrix, the resulting bound is expressed explicitly as a function of the memory depth, problem dimension, and envelope hyperparameters. Moreover, we show that Two-Sided L-BFGS preserves asymptotic global convergence in non-convex regimes under standard smoothness and strong Wolfe line-search assumptions, matching the theoretical guarantees of L-BFGS variants utilizing the Li-Fukushima cautious update rule. Numerical experiments on high-dimensional optimization problems demonstrate that the proposed method maintains well-conditioned inverse Hessian approximations and improves robustness and convergence behavior on ill-conditioned benchmarks.