Hoffman constants quantify the distance to the solution set of a polyhedral system in terms of its residual; they control error bounds, geometric conditioning, the convergence rate of first-order iterative algorithms, and the stability of regression estimators to target perturbations. Despite their importance, explicit values of Hoffman constants are rarely available due to their computational complexity. In this paper, we derive explicit bounds on the Hoffman constant for a class of structured polyhedral systems arising in sparse regularization. We show that the constants admit a decomposition into spectral, geometric, and interaction components, which together determine their scaling behavior. This framework explains the gap between worst-case dimension-dependent bounds and the favorable conditioning observed empirically in structured problems. As a primary application, we analyze ℓ1-regularized least squares, demonstrating that the effective constants depend on low-dimensional active subspaces rather than the ambient dimension. We then extend to the elastic net and adaptive ℓ1-regularized formulations, demonstrating how the underlying optimization geometry is altered by the ℓ2 penalty and reweighting scheme. Furthermore, we relate our results to classical statistical assumptions and show that the restricted eigenvalue condition bounds only the primal curvature of the active set, leaving the dual interaction geometry unconstrained and is thus insufficient alone for fast theoretical convergence rates. We further show standard ℓ∞ coherence conditions do not yield dimension-independent Euclidean bounds to close this gap. Our theoretical results show that Hoffman constants admit explicit, interpretable forms in structured regression settings and, in practice, provide actionable tools for post-hoc feature pruning and a priori optimal hyperparameter selection.
Figures & tables
Figure 1: Distribution of inactive cross-leverage scores for a Gaussian model. Probability density of cross-leverage scores for unselected features across varying regularization strengths λn . Higher regularization yields smaller active sets, which in turn usually reduces the geometric alignment of the remaining ambient features, shifting the mass of the distribution toward the origin.
Regularization ( λn )
Threshold ( ht )
Dropped
Sparsity ( s )
H2,2
Jaccard Sim.
Iters
Red. %
0.1
Baseline
0
177
349.56
1.00
2178
–
0.95
9784
174
157.24
0.98
1277
41.3%
1.0
Baseline
0
27
1.74
1.00
463
–
0.95
9934
27
1.64
1.00
63
86.4%
Table 1: Feature pruning on the ARCENE dataset ( d=10000,n=200 ). We compare the baseline LASSO solution to pruned models using a cross-leverage threshold ht=0.95 . Jaccard similarity measures support similarity with the baseline. H2,2 is the exact affine Hoffman constant. The number of iterations of an ISTA procedure and relative reduction in iterations required to convergence compared to the baseline are reported.
Figure 2: LASSO convergence on the spiked model. Estimator suboptimality for ISTA across varying correlation values ρ∈[0,0.95] . The population covariance has minimum eigenvalue 1−ρ , while the corresponding empirical designs satisfy the RE condition with high probability. Nevertheless, the observed ISTA convergence deteriorates as ρ increases and can be made arbitrarily slow as ρ→1 .
Figure 3: Elastic net phase transition map on a Gaussian design ( n=300,d=500,s=5 ). (Left) Exact support recovery (white) for varying regularization parameters against theoretical boundaries. The coupled λstat(λn,2) boundary correctly identifies the rightward shift in the noise floor caused by internal shrinkage bias. (Right) Empirical affine Hoffman constant of the true support for varying regularization parameters. Note the y -axis is log-scaled in both plots.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Design
d
n
s
HSA2,2 (Spectral)
HSA∞,∞ (Chebyshev)
HSA1,1 (Manhattan)
Gaussian
500
100
5
1.000 [1.000, 1.000]
1.000 [1.000, 1.000]
1.000 [1.000, 1.001]
500
200
20
1.001 [1.000, 1.001]
1.000 [1.000, 1.000]
1.001 [1.000, 1.003]
1000
100
10
1.000 [1.000, 1.000]
1.000 [1.000, 1.000]
1.000 [1.000, 1.001]
2000
400
40
1.000 [1.000, 1.000]
1.000 [1.000, 1.000]
1.000 [1.000, 1.001]
Spiked ( ρ=0.5 )
500
100
10
1.001 [1.001, 1.002]
1.000 [1.000, 1.000]
1.001 [1.000, 1.004]
1000
200
20
1.001 [1.001, 1.002]
1.000 [1.000, 1.000]
1.001 [1.000, 1.002]
Appendix
Table 2: Empirical tightness of affine Hoffman bounds in different norms. The table reports the ratio of the theoretical upper bound to the exact empirical value across 30 Monte Carlo trials per configuration. In each Monte Carlo trial, a design and s -sparse support are sampled. Values are reported as median [min, max].
Figure 4: Scaling of affine Hoffman constants and geometric decomposition with ambient dimension d for a Gaussian design ( n=200,s=10 ). (Left) Comparison of exact constants and theoretical upper bounds for H2,2 , H1,1 , and H∞,∞ as unrelated ambient features are added. Both the Euclidean and Manhattan measures scale with d , while the Chebyshev constant remains relatively dimension-independent. (Right) Decomposition of the H2,2 bound components. The growth in the Hoffman constant is driven entirely by the active-inactive interaction norm ∥GAcA∥2 , while the active curvature remains close to constant.
Linear convergence of first-order methods is typically characterized by global optimization conditions whose constants reflect worst-case geometry of the ambient space. In high-dimensional or structured problems, these global constants can be arbitrarily conservative and fail to capture the geometry actually encountered by optimization trajectories. In this paper, we develop a trajectory-restricted framework for linear convergence based on localized geometric regularity. We introduce restricted variants of the Polyak--Łojasiewicz inequality, error bound, and quadratic growth conditions that are required to hold only on subsets of the domain. We show that classical convergence guarantees extend under these localized conditions, and in key cases, we develop new arguments that yield explicit relationships between the corresponding constants. The resulting rates are governed by geometric quantities associated with the regions traversed by the algorithm. For polyhedral composite problems, we prove that convergence is controlled by restricted Hoffman constants corresponding to the active polyhedral faces visited along the trajectory. Once the iterates enter a well-conditioned face, the effective condition number improves accordingly. Our work provides a geometric quantification for fast local convergence after active-set or manifold identification and more broadly suggests that linear convergence is fundamentally governed by the geometry of the subsets explored by the algorithm, rather than by worst-case global conditioning.
Faris Chaudhry, Anthea Monod, Keisuke Yano
Imperial College London, UK · Institute of Statistical Mathematics, Japan
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 γ∈(0,1], there is no randomized polynomial-time algorithm that, with probability at least 2/3, returns a vector x such that, writing s=∥x∥0,
∥Ax−b∥22≤∥z∥0≤kmin∥Az−b∥22+εands=O(kκs+k1−γ),
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.
Honghao Lin, Vahab Mirrokni, David P. Woodruff
Google Research, Carnegie Mellon University / Texas A&M University. · Google Research. · Google Research and Carnegie Mellon University.
Weight decay is ubiquitous in training deep neural network architectures. Its empirical success is often attributed to capacity control; nonetheless, our theoretical understanding of its effect on the loss landscape and the set of minimizers remains limited. In this paper, we show that ℓ2-regularized deep matrix factorization/deep linear network training problems with squared-error loss admit a unique end-to-end minimizer for all target matrices subject to factorization, except for a set of Lebesgue measure zero formed by the depth and the regularization parameter. This observation reveals fundamental properties of the loss landscape of regularized deep matrix factorization problems: the Hessian spectrum is constant across all minimizers of the regularized deep scalar factorization problem with squared-error loss. Moreover, we show that, in regularized deep matrix factorization problems with squared-error loss, if the target matrix does not belong to the Lebesgue measure-zero set, then the Frobenius norm of each layer is constant across all minimizers. This, in turn, yields a global lower bound on the trace of the Hessian evaluated at any minimizer of the regularized deep matrix factorization problem. Furthermore, we establish a critical threshold for the regularization parameter above which the unique end-to-end minimizer collapses to zero.