Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers

Abstract

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 ℓ₁-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 ℓ₁-regularized formulations, demonstrating how the underlying optimization geometry is altered by the ℓ₂ 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.

Sharp stability for the second-order weighted Heisenberg Uncertainty Principle with explicit stability constants and optimizers
Xiao-Ping Chen
arXiv24 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
From Hermite Chaos to an Attractive Log-Gas: Explicit High-Rank Limits of Iterated-Logarithm and Tail Constants
Elina Moldavskaya
arXiv19 Oct 2026PreprintarXiv licenceFull textMathematical physics ProbabilityarXiv
Upper bounds for Jung constants of ℓ₁^d
Xiao Li
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
From Sidelnikov-Welch bounds to projection constants
Beata Deregowska, Barbara Lewandowska
arXiv24 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Fixed Convex-Lens Spectral Constants: Möbius Reduction, Sharp Model Theorems, and Angle-Dependent Bounds
Zijian Zeng
arXiv1 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{chaudhry2026explicit,
  title = {{Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers}},
  author = {Faris Chaudhry and Anthea Monod and Keisuke Yano},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15241},
  eprint = {2610.15241},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15241},
}

RIS

TY  - UNPB
TI  - Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers
AU  - Faris Chaudhry
AU  - Anthea Monod
AU  - Keisuke Yano
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2610.15241
UR  - https://arxiv.org/abs/2610.15241
AB  - 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.
ER  -

Abstract

Related

Cite