Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails
Shi Fu, Huibo Xu, Qixin Zhang, Dacheng Tao
cs.LG
Quick verdict
Negative answer to the COLT 2015 heavy-tailed RE open problem via pathwise constant-width counterexamples and a sharp VC occupancy law; rigorous theory.
Summary
This paper resolves, negatively, the COLT 2015 open problem of Banerjee et al., which asked whether the sub-Gaussian benchmark sample size n ≈ 1 + w(A)² for restricted eigenvalue (RE) conditions extends to heavy-tailed designs under a uniform small-ball condition alone. The authors identify 'simultaneous threshold occupancy' as the missing obstruction: a small-ball condition guarantees each fixed direction is detected with probability β, but no single finite sample need detect all directions at once. Four results support this. (1) Theorem 1 gives an explicit polyhedral descent cone of Gaussian width ≤ 2√(2/π) with fixed small-ball constants whose empirical RE is zero on every sample path for n ≤ m/2. (2) Theorems 3–4 encode every finite range space exactly as threshold events at arbitrarily small width and lift misses to kernel witnesses in a full descent cone. (3) Theorem 5 proves worst-case sample complexity Θ(β^{-1}[d log(1/β) + log(1/δ)]) for fixed threshold VC dimension d. (4) The separation survives exact isotropy, all finite moments, and C∞ smoothing (Theorem 7, Corollaries 8–9), while isotropy still yields a sharp dimension×radius fallback (Theorem 10). Limitations: the negative answer depends on the dimension-free reading of the open problem's constants; constructions are adversarial worst cases; the sharp fixed-d lower bound rests on a non-effective external ε-net result. No experiments; full proofs in appendices.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 1
● low 2
5 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The dimension-free Gaussian-width RE law posed in the COLT 2015 open problem does not follow from a uniform small-ball condition: it fails pathwise on a constant-width polyhedral descent cone (Theorem 1, Corollary 2).
- Every finite probability range space can be encoded exactly as threshold events at arbitrarily small Gaussian width and lifted to a full polyhedral descent-cone section (Theorems 3–4), so threshold occupancy is an intrinsic obstruction.
- For every fixed threshold VC dimension d, the sharp worst-case sample complexity is Θ(β^{-1}[d log(1/β) + log(1/δ)]) as β↓0 (Theorem 5).
- On one common descent cone of constant width, Gaussian designs succeed with O(1 + log(1/δ)) samples while an exactly isotropic heavy-tailed design with all finite moments has zero RE pathwise for n ≲ √(p/log p), and C∞ smoothing keeps the restricted energy of order τ² (Theorem 7, Corollaries 8–9).
- Under exact isotropy, a distribution-free RE bound with q(A)r(A)² replacing w(A)² holds and is sharp on the constructed family (Theorem 10, Corollary 11).
Strengths
Resolves a stated open problem with a probability-one counterexample
Theorem 1 constructs a polyhedral descent cone A_m of Gaussian width ≤ 2√(2/π) with small-ball constant ≥ 1/3 (at α = 1/(2√2)) where Λ_n = 0 on every sample path for all n ≤ m/2 — a deterministic obstruction, far stronger than a constant-probability failure; Corollary 2 then breaks the COLT display (3) for any fixed c1 > 0, c2 < ∞.
Structural, lossless lower bounds rather than ad hoc examples
Theorems 3–4 give an exact identity (eq. 10) equating truncated empirical energy with the minimum range frequency, and the injective transport T_ε a = (1⊤a, εa) makes Gaussian width arbitrarily small while threshold events are unchanged; Lemma 14 realizes any pointed polyhedral cone as a descent cone, so missed ranges become kernel witnesses intrinsically.
Sharp complexity characterization with matched upper and lower bounds
Separation robust to the standard objections
Honest scoping and attribution
Weaknesses
The negative answer hinges on an interpretation of the open problem
All negative instances are adversarial worst cases
Sharpness is qualitative in the constants
Universality lift and sharp VC law do not combine
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a pure theory preprint (arXiv:2609.03504v1, 34 pages, 'Preprint, 2026', NTU) addressing the COLT 2015 open problem of Banerjee, Chen and Sivakumar: does the sub-Gaussian benchmark n ≈ 1 + w(A)² for restricted eigenvalue (RE) conditions persist for heavy-tailed designs under only the uniform small-ball condition Q_α(P, A) ≥ β? The authors answer the 'full dimension-free, arbitrary-set' formulation negatively and name the obstruction: simultaneous threshold occupancy. The claimed results, all with proofs in Appendices A–J: (i) Theorem 1 — an explicit polyhedral descent cone A_m of width w(A_m) ≤ 2√(2/π) with small-ball constant ≥ 1/3 at α = 1/(2√2), whose empirical RE Λ_n = 0 on every sample path for all n ≤ m/2; (ii) Theorems 3–4 — exact representation of arbitrary finite range spaces as threshold events at width ≤ η, lifted to full descent-cone sections; (iii) Theorem 5 — worst-case complexity Θ(β^{-1}[d log(1/β) + log(1/δ)]) at fixed threshold VC dimension d as β↓0; (iv) Theorem 7 and Corollaries 8–9 — the separation survives exact isotropy, all finite moments, and C∞ smoothing; (v) Theorem 10 — under isotropy, q(A)r(A)² replaces w(A)², sharp on the constructed family.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 4 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What open problem does this paper solve?
It answers the COLT 2015 open question of Banerjee, Chen and Sivakumar, which asked whether the sub-Gaussian sample-complexity benchmark n ≈ 1 + w(A)² (Gaussian width of the descent cone) for restricted eigenvalues still holds for heavy-tailed data under only a uniform small-ball condition. The paper shows the dimension-free, arbitrary-set version of that statement is false, with explicit counterexamples where the empirical restricted eigenvalue is exactly zero on every sample for n ≤ m/2.
What is 'simultaneous threshold occupancy'?
It is the paper's name for the gap between per-direction and uniform visibility: a small-ball condition guarantees each fixed direction is detected with probability at least β by a fresh sample row, but a restricted-eigenvalue guarantee needs one finite sample to detect all directions in the set simultaneously. Without assumptions coupling nearby directions (as sub-Gaussian tails provide), this uniform coverage can fail outright, and the failures can be hidden in sets of arbitrarily small Gaussian width.
Does this mean heavy-tailed data breaks the Lasso?
Not in general. The negative results are worst-case constructions under the bare small-ball condition. The paper also proves a positive isotropic fallback (Theorem 10) where the required sample size scales with affine dimension times squared enclosing radius instead of Gaussian width, and prior literature shows sparsity-specific structure or moment assumptions restore recovery. The message is about which assumption carries the weight, not that recovery is hopeless.
Is there code or experiments for this paper?
No. It is a theory paper: all results are theorems with complete proofs in Appendices A–J. The constructions are explicit enough that small-dimensional numerical checks (for example, of the pathwise zero-RE counterexample in Theorem 1) are easy to run, but none are reported.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The abstract quoted in the task metadata is cut mid-sentence ('governed by af'), but the full extracted text contains the complete abstract and the body appears complete through Appendix J (p. 34); no truncation of the paper itself is assumed.
- Inline math is rendered ambiguously by PDF extraction in places (e.g., Theorem 4's 'Q1(P, Aε) ≥ β 2 − β' corresponds to β/(2−β) per its proof); formula readings were made from context.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.