超越高斯宽度的受限特征值：重尾条件下的阈值占用

# 重尾设计下超越高斯宽度的受限特征值：阈值占据性
来源：https://arxiv.org/html/2609.03504 \\jmlrpages\\coltauthor 与 和 新加坡南洋理工大学计算与数据科学学院 生成式AI实验室
###### 摘要
受限特征值 \(RE\) 界控制范数正则化估计器的稳定恢复。对于各向同性亚高斯测量，基准样本量为 \(1+w(A)^2\)，其中 \(w(A)\) 是归一化下降锥的高斯宽度。COLT 2015 的开放问题笔记（Banerjee 等人，2015 (https://arxiv.org/html/2609.03504#bib.bib1)）询问，仅凭均匀小球条件，相同的规律是否也适用于重尾设计。我们对该问题的一般形式给出了明确且系统的否定回答：所提规律在其完全无维数限制、任意集合的形式下失效，缺失的障碍是同时阈值占据性。具有固定小球常数的常宽多面体下降锥，在直至环境维度一半的所有样本路径上，其实证 RE 为零。更一般地，每个有限值域空间都可以在任意窄的球帽中实现精确的阈值编码，并提升至完整的多面体下降锥截面。对于每个固定的阈值 VC 维数 \(d\)，当 \(\beta \downarrow 0\) 时，最坏情况下的样本复杂度精确为 \(\Theta\left(\beta^{-1}[d\log(1/\beta)+\log(1/\delta)]\right)\)。这种分离在精确各向同性和所有有限矩条件下依然存在：在相同的常宽锥上，高斯测量以 \(O(1+\log(1/\delta))\) 个样本即可成功，而各向同性重尾设计在样本数 \(n \lesssim \sqrt{p/\log p}\) 时逐路径失败。高斯平滑产生处处为正的 \(C^{\infty}\) 密度，同时保留任意差的 RE。在各向同性下，由仿射维数乘以包围半径平方支配的、分布无关的后备方案在此类族上是紧致的。
††proceedings:预印本: 预印本††year:2026
###### 关键词
受限特征值; 重尾设计; 小球方法; 高斯宽度; VC维数
## 1 引言
许多高维估计器通过最小化服从数据拟合的范数来恢复结构化参数。Lasso 是典型例子：\(\ell_1\) 范数倾向于稀疏向量，但它无法将目标 \(\theta^\star\) 与那些同时保持测量值且不增加范数的扰动区分开来。更一般地，正则化器无法排除的扰动构成其*下降锥*。仅当测量矩阵在此锥上条件良好时，恢复才有可能。受限特征值 (\(RE\)) 量化了这一条件。设 \(X \in \mathbb{R}^{n \times p}\) 的行 \(Z_1,\ldots,Z_n\) 独立同分布，具有共同分布 \(P\)，且 \(A \subseteq \mathbb{S}^{p-1}\) 是相关方向的归一化集合，通常是下降锥的球形截面。我们记 \(\Lambda_n(X;A) = \inf_{u \in A} \frac{\|Xu\|_2^2}{n} = \inf_{u \in A} \frac{1}{n} \sum_{i=1}^n \langle Z_i, u \rangle^2\)。 (1)
如果 \(\Lambda_n(X;A) > 0\)，则没有相关方向位于核中。定量下界控制恢复对噪声的敏感性，在统计模型中也控制估计误差（Bickel 等人，2009 (https://arxiv.org/html/2609.03504#bib.bib3)；Chandrasekaran 等人，2012 (https://arxiv.org/html/2609.03504#bib.bib5)；Negahban 等人，2012 (https://arxiv.org/html/2609.03504#bib.bib4)）。对于中心化各向同性亚高斯行，一个简洁的几何规律在分布相关的常数范围内成立：基准样本量由 \(1+w(A)^2\) 控制，其中 \(w(A) = \mathbb{E} \sup_{u \in A} \langle g, u \rangle\) 是高斯宽度。\(w(A)^2\) 项充当锥的有效维数，而附加常数甚至覆盖零宽度集合。对于高斯测量，统计维数理论将图像细化为稀疏恢复、低秩恢复和许多其他凸逆问题的精确相变（Gordon, 1988 (https://arxiv.org/html/2609.03504#bib.bib19)；Chandrasekaran 等人，2012 (https://arxiv.org/html/2609.03504#bib.bib5)；Amelunxen 等人，2014 (https://arxiv.org/html/2609.03504#bib.bib6)；Tropp, 2015b (https://arxiv.org/html/2609.03504#bib.bib7)）。重尾测量激发了一条不同的路径。上尾集中可能不可用，但每个固定方向仍可能以非平凡概率可见。小球条件要求对于某个 \(\alpha,\beta > 0\)，\(\mathsf{Q}_{\alpha}(P,A) := \inf_{u \in A} P\{|\langle Z, u \rangle| \geq \alpha\} \geq \beta\)。 (2)
表面上的类比隐藏了量词的变化。小球条件说，对于每个固定方向 \(u\)，一个新的总体抽取以至少 \(\beta\) 的概率检测到 \(u\)。\(RE\) 界要求更多：以高概率，一个共同的样本必须同时检测到 \(A\) 中的每个方向。在亚高斯假设下，增量控制将附近方向耦合，而高斯宽度衡量剩余的均匀性成本。一个纯粹的小球条件不提供这种耦合。Banerjee 等人（2015）(https://arxiv.org/html/2609.03504#bib.bib1) 的 COLT 2015 开放问题询问，对于任意球面集合 \(A\)，是否仍可证明 \(\inf_{u \in A} \|Xu\|_2^2 \geq c_1(\alpha,\beta) n - c_2(\alpha,\beta) w(A)^2\) (3) 以高概率成立。我们阐明了该问题中“适当常数”的样本复杂度解释：\(c_1 > 0\) 和 \(c_2 < \infty\) 可能依赖于小球参数，但不依赖于环境维数或 \(A\)。没有这种无维数的均匀性，所提的高斯宽度规律将无法表达原始笔记中提出的同阶样本复杂度原则。肯定的答案本会使高斯宽度相图在高斯设计之外，远超出上尾集中或高阶矩假设的范围，变得普遍。
#### 我们的回答。我们表明，COLT 2015 笔记中提出的无维数高斯宽度规律，并不遵循纯粹的小球条件，即使设计是精确各向同性的。我们的结果将同时阈值占据性确定为一般障碍，确定了其精确的最坏情况复杂度，并描绘了各向同性能恢复和不能恢复什么。
#### 缺失的信息是同时覆盖。高斯宽度衡量方向间的欧几里得接近性，但小球假设无需耦合它们的可见性事件。想象许多潜在的行类型，每个类型子集对应一个方向。方向 \(u\) 可见当且仅当采样的行类型属于其关联的子集。所有方向可以放置在任意窄的球帽中，因此它们的高斯宽度很小，但有限样本仍必须在一个复杂的区间系统中命中每个子集。遗漏一个区间会使一个方向的经验能量为零。因此问题不是高斯过程几何，而是阈值覆盖。
#### 主要贡献。我们确立了四个互补的结果，揭示了障碍，量化了其复杂度，并确定了一个积极的边界。
- •*在常宽下的逐路径反例。*对于每个偶数 \(m\)，我们给出一个多项式范数和一个中心化、方向重尾的设计，满足 \(w(A) = O(1)\) 和固定的小球常数，但当 \(n \leq m/2\) 时，在每个样本路径上都有 \(\Lambda_n(X,A) = 0\)（定理1 (https://arxiv.org/html/2609.03504#Thmtheorem1)）。这是一个确定性的有限样本障碍，而非隐藏在尾界中的失败事件。
- •*值域空间普适性与精确低质量规律。*我们通过阈值事件，以任意小的高斯宽度，精确表示每个有限概率值域空间（定理3 (https://arxiv.org/html/2609.03504#Thmtheorem3)），然后将遗漏区间的见证提升至完整的多面体下降锥截面，同时保持锥上的均匀小球质量（定理4 (https://arxiv.org/html/2609.03504#Thmtheorem4)）。因此占据性是内在的。在阈值 VC 维数 \(d\) 下，均匀 \(RE\) 在 \(n \gtrsim \beta^{-1}\{d\log(2/\beta)+\log(1/\delta)\}\) 时成立，并且当 \(\beta \downarrow 0\) 时，对于每个固定的 \(d\)，这个阶数是必要的（定理5 (https://arxiv.org/html/2609.03504#Thmtheorem5)）。这个精确规律涉及一般球面集合；锥的提升并不声称保持生成值域空间的 VC 维数。
- •*在相同几何结构下的各向同性与平滑分离。*在一个共同的下降锥上，高斯测量在 \(O(1+\log(1/\delta))\) 个样本后成功，而具有所有矩的中心化各向同性重尾设计，在样本数 \(n \lesssim \sqrt{p/\log p}\) 时逐路径 \(RE\) 为零（定理7 (https://arxiv.org/html/2609.03504#Thmtheorem7) 和 8 (https://arxiv.org/html/2609.03504#Thmtheorem8)）。高斯平滑给出一个正的 \(C^{\infty}\) 密度，同时使受限奇异值保持任意小（推论9 (https://arxiv.org/html/2609.03504#Thmtheorem9)）。因此，无论是协方差归一化还是移除原子都无法恢复高斯宽度控制。
- •*在各向同性下的一个积极边界。*各向同性给出一个更粗糙的、分布无关的保证：如果 \(q(A)\) 是仿射维数，\(r(A)\) 是最小包围半径，那么 \(q(A) r(A)^2\) 在小球 \(RE\) 界中取代 \(w(A)^2\)（定理10 (https://arxiv.org/html/2609.03504#Thmtheorem10) 和 11 (https://arxiv.org/html/2609.03504#Thmtheorem11)）。锚定框架族与此尺度匹配。这是各向同性的一个真正积极后果，而非声称所有复杂度对的联合极小极大公式。
#### 与早期稀疏恢复构造的关系。Lecué 和 Mendelson (2017b) (https://arxiv.org/html/2609.03504#bib.bib12) 2014 年 arXiv 版本中的尖峰构造早于 COLT 笔记，并且可以回顾性地解释为对特定 \(\ell_1\) 相关稀疏恢复几何结构，完全均匀的高斯宽度蕴含的否定实例。COLT 笔记在讨论单位 \(s\) 稀疏方向时引用了该工作，并且在审阅了该工作以及 Koltchinskii 和 Mendelson (2015) (https://arxiv.org/html/2609.03504#bib.bib10) 的阈值 VC 方法之后，仍然声明已知结果仅涵盖“某些特殊的 \(A\) 情况”，并且在小球性质下对于一般 \(A\) 的问题仍然开放（Banerjee 等人，2015 (https://arxiv.org/html/2609.03504#bib.bib1), p. 1754）。我们的贡献是对那个任意集合公式的结构化处理：常宽逐路径失败、任意有限值域空间的精确编码、精确的占据规律，以及相同几何下的各向同性和平滑分离。第7节 (https://arxiv.org/html/2609.03504#S7) 给出了完整的比较。
#### 范围。我们的不可能性关注的是什么仅仅从边缘小球信息均匀地推导出来。矩或增量假设以及稀疏特定结构可以将附近方向耦合，从而排除我们不受限的编码。附录提供了所有常数、可测性约定和证明。
## 2 问题设置与证明思路
设 \(V\) 是一个有限维欧几里得空间，记 \(S(V) = \{v \in V : \|v\|_2 = 1\}\)，并设 \(A \subseteq S(V)\) 非空。对于范数 \(\mathcal{R}\) 和 \(\theta \neq 0\)，设 \(\mathcal{D}(\mathcal{R},\theta) = \{h : \mathcal{R}(\theta + th) \leq \mathcal{R}(\theta) \text{ 对于某个 } t > 0\}\)。以下所有锥都是闭的和多面体的。我们使用固定的径向变量 \(L = 1 + e^{G_0}\)，其中 \(G_0 \sim \mathsf{N}(0,1)\)。它具有所有有限阶的矩，但对于每个 \(s > 0\)，\(\mathbb{E} e^{sL} = \infty\)。独立的 Rademacher 符号使我们的设计中心化。我们称一个随机向量为*方向重尾*，如果对于每个 \(v \neq 0\) 和每个 \(s > 0\)，\(\mathbb{E} e^{s|\langle Z, v \rangle|} = \infty\)。 (4)
对于可能退化边缘的值域空间编码，“重尾径向乘数”指的是相同的 \(L\)。证明首先在窄帽中编码关联，然后将其提升至下降锥；各向同性的否定和肯定扩展完成了图景。
#### 窄帽关联编码。对于一个有限值域空间 \(\{C_1,\ldots,C_M\}\)，将每个 \(u_j\) 放置在一个共同锚点附近，并让一行存储 \((\mathbf{1}\{Y \in C_j\})_{j \leq M}\)。那么当且仅当 \(Y \in C_j\) 时，\(|\langle Z, u_j \rangle| \geq 1\)。缩小扰动宽度至零而不改变这些事件。
#### 从有限多个方向到下降锥。一个有限的球面集合尚不是正则化器几何。通过一个窄嵌入将正卦限传递，产生一个多面体范数，其锥方向是生成器的归一化混合。平均保留锥上的均匀小球质量，而一个遗漏的区间会湮灭一个极端射线。
#### 在不失见证的情况下恢复各向同性。从多项式数量的锚定 Rademacher 行类型开始，这些类型具有近似单位协方差、常数板质量以及条件良好的小子矩阵；白化给出一个紧框架。观察到类型 \(D\) 后，将锚点从其张成空间中投影得到的残差归一化。它湮灭每个观察到的行，并保持在锚点 \(O(\sqrt{|D|/p})\) 范围内。帽到锥的引理控制整个锥的宽度。
#### 为什么各向同性仍然产生一个肯定定理。对于一个中心化各向同性设计，将 \(A\) 按最小包围中心 \(a\) 平移，并将对称化过程投影到平行于 \(\operatorname{aff}(A)\) 的线性空间 \(\operatorname{span}(A-a)\) 上。其期望上确界至多为 \(r(A)\sqrt{q(A)}\)，给出维数-半径界。在我们的族上，\(q(A) = p\) 且 \(r(A)^2 \asymp k/p\)，与逐路径尺度 \(k\) 匹配。
## 3 一个常宽逐路径反例
第一个定理已经排除了 (3 (https://arxiv.org/html/2609.03504#S1.E3))。其作用是在通用编码之前，以基本形式揭示覆盖障碍。
###### 定理 1（显式常宽反例）。对于每个偶数 \(m \geq 2\)，存在一个维数为 \(m\) 的欧几里得空间 \(V_m\)，一个多面体范数 \(\mathcal{R}_m\)，一个点 \(\theta_m^\star\)，以及一个中心化、方向重尾的 \(Z_m \in V_m\)，其分布为 \(P_m\)。设 \(A_m = \mathcal{D}(\mathcal{R}_m, \theta_m^\star) \cap S(V_m)\)。则 \(\mathsf{Q}_{1/(2\sqrt{2})}(P_m, A_m) \geq \frac{1}{3}, \quad w(A_m) \leq 2\sqrt{2/\pi}, \quad \operatorname{VC}(\mathcal{T}_1(A_m)|_{\operatorname{supp} P_m}) \geq \frac{m}{2}\). (5)
此外，对于每个 \(n \leq m/2\) 和每个样本实现，\(\Lambda_n(X, A_m) = 0\)。 (6)
径向定律 \(L\) 在每个维度中相同。这里 \(\mathcal{T}_{\alpha}(A) = \{\{z : |\langle z, u \rangle| \geq \alpha\} : u \in A\}\)。