研究否定重尾分布下受限特征值样本复杂度猜想，COLT 2015开放问题获否定答案
arXiv新论文系统性地否定了Banerjee等人在COLT 2015提出的开放问题：仅凭均匀小球条件无法推出高斯宽度形式的样本复杂度定律，核心障碍是“同时阈值占用”。
AI解读：这篇论文回答了一个困扰高维统计多年的理论问题：当数据不是高斯分布而是重尾分布时，稀疏恢复所需的样本量是否还能用经典的“高斯宽度”公式来刻画？答案是否定的。作者构造了一类特殊的优化锥（具有恒定宽度和固定小球常数的多面体下降锥），在这种锥上，即使数据满足各向同性和所有有限矩条件，重尾分布下前一半维度的样本路径上经验受限特征值都会归零；而同样的锥在高斯测量下只需O(1+log(1/δ)) 个样本就能成功。这意味着，Banerjee等人 2015 年在COLT提出的猜想——仅靠均匀小球条件就能推出维度无关的样本复杂度定律——在一般形式下不成立。对理论研究者而言，这项结果划定了重尾鲁棒估计的可行性边界，提示需要改用仿射维数乘以外接半径平方这样的分布无关备选度量；对应用者来说，它说明在数据存在重尾时，不能照搬高斯假设下的样本量经验法则。普通读者无需立即采取行动，但从事高维统计或机器学习理论的人应关注这一反例结构。
arXiv于 2026 年 9 月 3 日发布的一篇论文（编号 2609.03504）对Banerjee等人在COLT 2015开放问题中提出的猜想给出了系统性的否定回答。作者Shi Fu、Huibo Xu、Qixin Zhang和Dacheng Tao证明，仅从均匀小球条件出发，无法推出与高斯宽度相关的样本复杂度定律在完全维度无关、任意集合形式下成立；缺失的关键障碍是“同时阈值占用”（simultaneous threshold occupancy）。
反例：恒定宽度锥上的零经验RE与阈值编码
论文构造了一个具有恒定宽度和固定小球常数的多面体下降锥。在该锥上，对于不超过环境维度一半的样本路径，经验受限特征值（empirical RE）始终为零。
更一般地，作者证明每个有限值域空间都能在任意窄的球冠中实现精确阈值编码，并可提升为完整的多面体下降锥截面。对每个固定的阈值VC维数d，当 β 趋向 0 时，最坏情况样本复杂度的精确阶为 Θ(β⁻¹[d log(1/β) + log(1/δ)])。
- 该分离在精确各向同性和所有有限矩条件下依然成立：在同一个恒定宽度锥上，高斯测量只需O(1 + log(1/δ)) 个样本即可成功，而各向同性重尾设计在n ≲ √(p / log p) 时会在路径上失败。
- 高斯平滑可以产生处处为正的C∞ 密度，同时仍保持任意差的RE性质。
- 在各向同性条件下，由仿射维数乘以外接半径平方给出的分布无关备选界在此族上是紧的。