Small-Ball Marginals Do Not Control Restricted Eigenvalues by Euclidean Gaussian Width
Abstract
Banerjee, Chen, and Sivakumar asked at COLT 2015 whether a uniform small-ball condition on the rows of a random design matrix forces a restricted-eigenvalue lower bound whose sample complexity is governed by the ordinary Euclidean Gaussian width of an arbitrary spherical subset. We give a negative answer to the natural distribution-free formulation of that question. For every sample size n, we construct a centered, genuinely heavy-tailed row distribution in dimension p=4n+1 and a set A=C∩𝕊p−1, where C is a closed polyhedral convex cone, such that infv≠ 0ℙ ( |⟨ Z,v⟩| ≥ (lVert vrVert2)/√2 )≥ 1/12 and w(A)<2. Nevertheless, for the matrix X with n independent copies of Z as rows, ℙ ( infu∈ AlVert XurVert22=0 ) ≥ 1−exp(−2n). Thus no positive constants depending only on the fixed small-ball parameters can yield a lower bound of the proposed form c1n−c2w(A)2 with high probability. The construction isolates the obstruction: a marginal small-ball lower bound controls every fixed direction, but does not control the distribution-dependent complexity of searching over many directions. We state the quantifiers explicitly and discuss why isotropic or upper-tail assumptions lead to a different, still meaningful problem.
Related
- Sharp Gaussian Asymptotics for Marginals of Euclidean Balls
- Revisiting the Bobkov-Chistyakov-Götze theorem on approximately Gaussian marginals
- An optimal pinching theorem on compact minimal submanifolds in the Euclidean spheres via eigenvalues of fundamental matrices
- An optimal pinching theorem on compact minimal submanifolds in the Euclidean spheres via eigenvalues of fundamental matrices II
- Gaussian Flow Dynamics: Simulation-Free Neural SDE Learning Beyond One-Time Marginals
BibTeX
@misc{zhao2026smallball,
title = {{Small-Ball Marginals Do Not Control Restricted Eigenvalues by Euclidean Gaussian Width}},
author = {Jinze Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11795},
eprint = {2609.11795},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11795},
}
RIS
TY - UNPB
TI - Small-Ball Marginals Do Not Control Restricted Eigenvalues by Euclidean Gaussian Width
AU - Jinze Zhao
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11795
UR - https://arxiv.org/abs/2609.11795
AB - Banerjee, Chen, and Sivakumar asked at COLT 2015 whether a uniform small-ball condition on the rows of a random design matrix forces a restricted-eigenvalue lower bound whose sample complexity is governed by the ordinary Euclidean Gaussian width of an arbitrary spherical subset. We give a negative answer to the natural distribution-free formulation of that question. For every sample size n, we construct a centered, genuinely heavy-tailed row distribution in dimension p=4^n+1 and a set A=C∩𝕊^p−1, where C is a closed polyhedral convex cone, such that inf_v≠ 0ℙ ( |⟨ Z,v⟩| ≥ (lVert vrVert_2)/√2 )≥ 1/12 and w(A)<2. Nevertheless, for the matrix X with n independent copies of Z as rows, ℙ ( inf_u∈ AlVert XurVert_2^2=0 ) ≥ 1−exp(−2^n). Thus no positive constants depending only on the fixed small-ball parameters can yield a lower bound of the proposed form c_1n−c_2w(A)^2 with high probability. The construction isolates the obstruction: a marginal small-ball lower bound controls every fixed direction, but does not control the distribution-dependent complexity of searching over many directions. We state the quantifiers explicitly and discuss why isotropic or upper-tail assumptions lead to a different, still meaningful problem.
ER -