# Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

arXiv: https://arxiv.org/abs/2609.03504 · HTML: https://mlsanity.com/paper/2609.03504/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 3 Sep 2026.

## Builds on (most cited first, 6 of 6)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression](https://mlsanity.com/paper/1804.02605/) (2018)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [Estimation with Norm Regularization](https://mlsanity.com/paper/1505.02294/) (2015)
- [Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data](https://mlsanity.com/paper/2004.05361/) (2020)

## Abstract (arXiv)

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is 1+w(A)2, where w(A) is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension d, as βdownarrow0, the sharp worst-case sample complexity is Theta(β-1[dlog(1/β)+log(1/δ)]). The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with O(1+log(1/δ)) samples, whereas an isotropic heavy-tailed design fails pathwise for nlesssim√p/log p. Gaussian smoothing yields an everywhere-positive C^∞ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.