Loading
Life sciences · Preprint
arXiv · September 3, 2026
Raises a question worth testing. It does not answer one.
This preprint provides a negative answer to a 2015 open problem in high-dimensional statistics, demonstrating that restricted eigenvalue (RE) bounds for heavy-tailed designs do not follow the same law as Gaussian measurements governed solely by Gaussian width. The work constructs explicit counterexamples and derives sharp sample complexity bounds involving threshold occupancy and VC dimension, showing a fundamental separation between Gaussian and isotropic heavy-tailed designs.
Preprint.
RE bounds under Gaussian measurements require sample size O(1 + log(1/δ)) whereas isotropic heavy-tailed designs fail pathwise for n ≲ √(p/log p) on the same constant-width cone Sharp worst-case sample complexity for fixed threshold VC dimension d is Θ(β⁻¹[d log(1/β) + log(1/δ)]) as β↓0 Constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension
Safety was not reported in the material analysed. Check the source before drawing any conclusion about harm.
The source did not state who this applies to in practice.
This is a theoretical mathematical work answering a 2015 open problem by constructing counterexamples and proving worst-case sample complexity bounds; it raises and resolves a question about high-dimensional statistics rather than testing an empirical claim.
Quoted from the source exactly as published.
Graded across the dimensions that decide whether you should act, each from what the source actually supports. There is no single score, and where a dimension was not assessed it says so.
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 $Θ(β^{-1}[d\log(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 $n\lesssim\sqrt{p/\log p}$. Gaussian smoothing yields an everywhere-positive $C^\infty$ 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.
Taken from the source record, never inferred. Follow any of these and new work involving them reaches your briefing.