NeurIPS 2026 学习理论 Learning Theory 稳健协方差估计椭球分布散射矩阵空间符号平方和松弛

Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians¶

会议: NeurIPS 2026
arXiv: 2502.06564
论文: arXiv
领域: 学习理论 / Learning Theory
关键词: 稳健协方差估计, 椭球分布, 散射矩阵, 空间符号, 平方和松弛

一句话总结¶

针对强污染模型下高维椭球分布的散射矩阵与协方差估计问题，提出多阶段空间符号协方差滤波与 degree-4 平方和（SoS）松弛算法，在近乎最优样本复杂度下首次以多项式时间达到了匹配高斯情形的近最优误差上界。

研究背景与动机¶

高维稳健统计中的协方差估计长期存在一个理论与算法上的鸿沟：高斯分布下已有兼具近最优估计误差 $O(\varepsilon \log(1/\varepsilon))$ 与多项式时间复杂度的滤波算法，但这些突破严重依赖于高斯二阶矩与四阶矩之间的精确代数恒等式，以及极强的尾部集中性。一旦推广至次高斯（sub-Gaussian）或庞加莱（Poincaré）分布，基于低阶和（Sum-of-Squares, SoS）矩可证明性的算法通常需要准多项式时间与样本量，且无法触及相对 Frobenius 范数下的最优速率。

现实中的许多重尾及非高斯多变量数据（如多元 Student's $t$ 分布、Cauchy 分布、多元 Laplace 分布等）属于更具普适性的椭球分布族（Elliptical Distributions）。对于这类分布，其协方差甚至一阶矩都可能不存在，仅存在由仿射变换定义的散射矩阵（Scatter Matrix）$\Sigma$。先前关于椭球分布稳健估计的最优界限（如 Huber 污染模型下的结果）均依赖指数级计算复杂度的搜索（例如 Tukey 中位数或指数时间极小化），缺乏多项式时间的高效算法。

本文的切入角度是：椭球分布在几何上具备球对称分布的仿射拉伸结构，将其投影至单位球面所得到的空间符号（Spatial Sign）不仅完全消除了未知的径向重尾尺度扰动，而且其协方差矩阵与真实散射矩阵共享相同的特征向量。核心 idea：通过将散射矩阵估计归约至空间符号截断分布的有界方差估计，结合三阶段多项式时间滤波与 degree-4 平方和（SoS）松弛，成功在极弱有效秩假设下实现与高斯分布同阶的近最优相对范数误差，并拓展至次指数椭球分布的稳健协方差估计。

方法详解¶

整体框架¶

算法的整体目标是在强 $\varepsilon$-对抗污染模型下，输入样本 $z_1, \dots, z_n \in \mathbb{R}^d$，输出一个对称正定矩阵 $\hat{\Sigma}$，逼近真实的散射矩阵 $\Sigma$（或协方差矩阵）。整个处理流程分为预处理、三阶段级联滤波估计以及尺度恢复：首先通过成对差分消除未知位置参数 $\mu$，投影至球面上得到截断空间符号；随后依次执行谱范数粗估计（使有效秩饱和）、谱范数细估计（利用 degree-4 SoS 证书匹配四阶张量）、Frobenius 范数滤波，最终对于具备 Hanson-Wright 性质或次指数尾部的分布进行一维截断尺度校准。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入对抗污染样本 z_1,...,z_n"] --> B["成对差分与空间符号截断"]
    B --> C["阶段一：粗谱滤波<br/>SoS 获得初始 0.9·Id ⪯ Σ_1 ⪯ 1.1·Id"]
    C --> D["阶段二：细谱滤波<br/>degree-4 SoS 松弛对齐四阶矩"]
    D --> E["阶段三：Frobenius 范数滤波<br/>各向同性基下相对矩阵滤波"]
    E --> F["输出近最优散射矩阵估计 Σ_hat"]
    F -->|可选：Hanson-Wright / 次指数| G["一维截断均值估计恢复整体尺度"]

关键设计¶

1. 空间符号投影与渐近级数展开：消除重尾扰动并对齐特征谱 为摆脱样本对高阶矩存在的依赖，算法先通过随机成对差分 $z'_i = (z_i - z_{\lfloor n/2 \rfloor + i})/\sqrt{2}$ 消除未知位置向量 $\mu$，转化为中心化椭球分布。随后定义截断空间符号算子 $\mathcal{F}(x)$：当 $\|x\|^2 \in [d-\Delta, d+\Delta]$ 时为 $\sqrt{d} x / \|x\|$，其余离群区域施加线性平滑截断。由于椭球分布满足 $x = \mu + \xi A U$，空间符号在抵消随机标量 $\xi$ 后仅由 $A U / \|A U\|$ 决定。设 $\Sigma' = \Cov_{x \sim \mathcal{N}(0,\Sigma)}[\mathcal{F}(x)]$，它与 $\Sigma$ 共享正交特征基。为克服传统空间符号特征值失真无法趋近于零的缺陷，作者利用几何级数展开： $$ \frac{\lambda'j}{\lambda_j} = \mathbb{E}\left[ \frac{x_j^2 / \lambda_j}{\frac{1}{d}|x|^2} \right] = \sum\right) $$ 只要散射矩阵满足极弱的有效秩条件 }^{\infty} \mathbb{E}\left[ g_j^2 \left( 1 - \frac{1}{d}\sum_{i=1}^d \lambda_i g_i^2 \right)^k \right] = 1 + O\left(\frac{1}{\mathrm{erk}(\Sigma)$\mathrm{erk}(\Sigma) := \frac{\Tr(\Sigma)}{\|\Sigma\|} \gtrsim \log d$，空间符号协方差在相对谱范数下与 $\Sigma$ 的偏差即收敛至 $O(1/\mathrm{erk}(\Sigma))$，将无矩散射矩阵估计精确转化为空域单位超球上的次高斯协方差估计问题。

2. 基于广义稳定性的三阶段递进滤波架构 高维协方差滤波通常需要样本四阶张量具有与标准高斯相匹配的代数关系。然而在空间符号变换下，四阶张量 $T = \mathbb{E}[(\phi(g)\phi(g)^\top - \mathrm{Id})^{\otimes 2}]$ 与各向同性参考张量 $S = \mathbb{E}[(g g^\top / \|g\|^2 - \mathrm{Id})^{\otimes 2}]$ 存在非对角项偏差，若直接在全空间上优化，二者在一般矩阵方向上的二次型差异可达 $O(\|\Sigma - \mathrm{Id}\|)$。为此，算法引入基于线性空间 $\mathcal{V}$ 与凸集 $\mathcal{P}$ 的广义稳定性（Generalized Stability）定义，并设计了三步收敛框架： - 阶段一（粗谱估计）：利用空间符号的 $O(1)$-次高斯性，运行现有 degree-4 SoS 谱滤波算法，消耗新鲜子样本获取估计量 $\hat{\Sigma}_1$，使白化后的分布谱满足 $0.9 \cdot \mathrm{Id} \preceq \Sigma_1 \preceq 1.1 \cdot \mathrm{Id}$，从而强行将有效秩提升至饱和状态 $\mathrm{erk}(\Sigma_1) = \Omega(d)$； - 阶段二（细谱估计）：通过观察发现，张量误差在单位秩投影 $V = u u^\top$ 方向上由 $\sum_{i=1}^d V_{ii} \le 1$ 紧致控制。通过将张量多项式约束松弛至 degree-4 伪期望（Pseudo-expectation）集合 $\mathcal{P} = \{ \tilde{\mathbb{E}} v^{\otimes 4} \mid \tilde{\mathbb{E}} \|v\|^2 \le 1 \}$，并在每次迭代中高效求解半正定规划（SDP）分离超平面，成功剔除对抗离群点，将相对谱范数误差压缩至 $O(\varepsilon \log(1/\varepsilon))$； - 阶段三（Frobenius 范数滤波）：在谱范数极其接近各向同性后，四阶张量在全矩阵空间 $\mathcal{B} \otimes \mathcal{B}$ 上的漂移已被完全控制，直接运行基无关的标准二次滤波即可得到最终的 Frobenius 范数近最优估计 $\hat{\Sigma} = \hat{\Sigma}_1 \hat{\Sigma}_2 \hat{\Sigma}_3$。

3. 各向同性四阶张量的 degree-4 SoS 充分性松弛 为使滤波算法中的权值更新能够有效降低坏样本（离群点）的权重并保持好样本的主导地位，集合 $\mathcal{P}$ 必须相对于矩阵集 $\mathcal{V} = \{uu^\top \mid \|u\|=1\}$ 具备充分性（Adequacy）。作者在实代数框架下证明了 degree-4 伪期望满足广义柯西-施瓦茨不等式：对任意矩阵 $A, B \in \mathbb{R}^{d \times d}$ 与 $P \in \mathcal{P}$，不仅满足非负性 $\langle A^{\otimes 2}, P \rangle = \tilde{\mathbb{E}}(v^\top A v)^2 \ge 0$，更具备代数界限： $$ \langle A \otimes B, P \rangle^2 = \left( \tilde{\mathbb{E}} (v^\top A v)(v^\top B v) \right)^2 \le \tilde{\mathbb{E}}(v^\top A v)^2 \cdot \tilde{\mathbb{E}}(v^\top B v)^2 \le |A|^2 |B|^2 $$ 该性质允许在每次滤波迭代中通过凸优化精准捕获违例离群投影，确保总迭代步数不超过 $O(n)$，单步内仅需多项式时间求解 SDP 分离问题。

损失函数 / 训练策略¶

该算法为纯组合几何与凸优化滤波迭代，没有反向传播梯度训练过程。在阶段二和阶段三的滤波主循环中，算法维护样本权重向量 $w \in \mathbb{R}^n$，满足 $0 \le w_i \le 1/n$ 且 $\sum_{i=1}^n w_i \ge 1 - \varepsilon$。 - 分离检验条件：求解 $\lambda = \max_{P \in \mathcal{P}} |\langle P, Q - \Sigma_w \rangle|$。若 $\lambda > C(\delta^2/\varepsilon + \varepsilon r^2)$，则计算每个样本在极值方向上的二次残差得分 $\tau_i = \langle P^*, (x_i - \mu_w)(x_i - \mu_w)^\top \rangle$。 - 权重修剪规则：对得分降序排列，找到前缀累积权重大于 $2\varepsilon$ 的截断点 $N$，对 $i \le N$ 更新权重： $$ w_i^{(t+1)} = \left( 1 - \frac{\tau_i}{\tau_{\max}} \right) w_i^{(t)} $$ 该下调策略保证好样本减少的总权重严格小于坏样本减少的权重，保证循环在至多 $\lceil 2\varepsilon n \rceil$ 步内终止。

实验关键数据¶

主实验¶

论文重点关注不同数据分布假设与污染比例 $\varepsilon$ 下，相对误差指标与所需样本复杂度/计算时间复杂度的理论对比（主定理 Theorem 1.4, Theorem 1.8）。

分布类别 / 设定	范数度量	误差上界	样本复杂度 $n$	计算时间复杂度
一般椭球分布（本文）	相对谱范数 $\\|\Sigma^{-1/2}\hat{\Sigma}\Sigma^{-1/2} - \mathrm{Id}\\|$	$O(\varepsilon \log(1/\varepsilon))$	$\tilde{O}(d^2/\varepsilon^2)$	$\mathrm{poly}(n)$ 多项式时间
一般椭球分布（本文）	相对 Frobenius 范数	$O(\varepsilon \log(1/\varepsilon))$ (当 $\varepsilon \gtrsim \frac{\log d}{\sqrt{d}}$)	$\tilde{O}(d^2/\varepsilon^2)$	$\mathrm{poly}(n)$ 多项式时间
Hanson-Wright 椭球分布（本文）	协方差相对 Frobenius 范数	$O(\varepsilon \log(1/\varepsilon))$	$\tilde{O}(d^2/\varepsilon^2)$	$\mathrm{poly}(n)$ 多项式时间
次指数椭球分布（本文）	协方差相对谱范数	$O(\varepsilon \log(1/\varepsilon))$	$\tilde{O}(d^2/\varepsilon^2)$	$\mathrm{poly}(n)$ 多项式时间
椭球分布 (Chen et al., 2018)	相对谱范数 (Huber 污染)	$O(\varepsilon)$ (信息论最优)	$\Omega(d/\varepsilon)$	$\exp(d)$ 指数时间
次高斯分布 (DHPT24 / KS17)	相对谱范数	$O(\varepsilon \mathrm{polylog}(1/\varepsilon))$	$d^{\mathrm{polylog}(1/\varepsilon)}$	$d^{\mathrm{polylog}(1/\varepsilon)}$ 准多项式时间
庞加莱分布 (BKR+24)	相对 Frobenius 范数	$O(\varepsilon \mathrm{polylog}(1/\varepsilon))$	$d^{\mathrm{polylog}(1/\varepsilon)}$	$d^{\mathrm{polylog}(1/\varepsilon)}$ 准多项式时间
高斯基线 (DKK+16)	相对 Frobenius 范数	$O(\varepsilon \log(1/\varepsilon))$	$\tilde{O}(d^2/\varepsilon^2)$	$\mathrm{poly}(n)$ 多项式时间

消融实验¶

论文分析了估计流程中不同滤波阶段的输入条件、使用的技术工具以及达到的误差保障：

估计阶段	依赖技术 / 假设	输入状态	输出保障 / 误差指标	作用说明
阶段一：粗估计	[KS17] 次高斯 SoS 滤波	$\mathrm{erk}(\Sigma) \gtrsim \log d$	谱范数误差 $O(\sqrt{\varepsilon} + \frac{1}{\mathrm{erk}(\Sigma)})$	白化后使得特征值介于 $[0.9, 1.1]$，将有效秩提升至 $\Omega(d)$
阶段二：细谱估计	degree-4 SoS 广义稳定性滤波	$0.9 \cdot \mathrm{Id} \preceq \Sigma_1 \preceq 1.1 \cdot \mathrm{Id}$	相对谱范数误差 $O(\varepsilon \log(1/\varepsilon))$	消除全矩阵四阶张量 $O(\\|\Sigma - \mathrm{Id}\\|)$ 漂移，逼近各向同性
阶段三：最终滤波	基无关标准谱滤波 ($Q=S$)	相对谱范数误差 $\le O(\varepsilon \log(1/\varepsilon))$	相对 Frobenius 误差 $O(\varepsilon \log(1/\varepsilon))$	最终达到与高斯完全一致的最优相对 Frobenius 误差界
尺度恢复（可选）	一维中位数/截断均值估计	已知近最优散射矩阵方向	标量因子相对误差 $O(\varepsilon \log(1/\varepsilon)/\sqrt{d})$	将散射矩阵提升为真实协方差矩阵（仅需 Hanson-Wright 或次指数条件）

关键发现¶

打破高斯四阶矩代数绑架：以往高维稳健协方差高效算法必须利用高斯四阶矩与二阶矩的固定张量对称性，本文证明椭球分布的空间符号通过 degree-4 SoS 张量松弛可完全跨越该壁垒。
高维对重尾的结构免疫性：在低维情况下估计重尾次指数分布需付出 $O(\varepsilon \log^2(1/\varepsilon))$ 的代价；而在高维空间中，均匀球面随机向量与各向同性高斯向量在投影下的各向同性收敛使得一维模长平方具备类似高斯的严格集中性，奇迹般地保持了 $O(\varepsilon \log(1/\varepsilon))$ 的高斯同阶速率。
有效秩条件的极弱约束：只要条件数满足 $\kappa(\Sigma) \lesssim d / \log d$（甚至只需最小的一半特征值不产生奇异塌缩），有效秩即可大于 $C \log d$，算法即可保证高概率成功。

亮点与洞察¶

空间符号展开的高阶截断：通过对空间符号逆平方模长进行无穷几何级数展开，精巧地证明了其协方差与原散射矩阵的偏差受限于 $O(1/\mathrm{erk}(\Sigma))$，将几何投影的内在结构发挥到了极致。
SoS 松弛与张量滤波的有机融合：不仅停留在传统的 SoS 矩检验，而是将 degree-4 伪期望直接构造成稳健滤波中的凸投影搜索空间，既规避了非凸的四阶张量秩一检验硬度，又保持了算法的多项式求解时间。
下游任务即插即用：该散射矩阵估计量可直接应用于稳健主成分分析（Robust PCA），在特征值存在间隔 $\gamma$ 时直接获得误差为 $O(\frac{\varepsilon \log(1/\varepsilon)}{\gamma})$ 的主特征向量估计。

局限与展望¶

样本复杂度的多项式阶数：当前算法所需的样本量为 $\tilde{O}(d^2/\varepsilon^2)$，虽然在协方差估计上是近乎最优的，但在特定的 Robust PCA 任务中，相比针对高斯专门设计的样本复杂度仍有可优化空间。
位置参数估计的未决问题：本文的方法完全基于差分和中心化投影来绕过均值/位置向量 $\mu$ 的估计；如何以多项式时间和近最优误差同时稳健估计一般椭球分布的位置参数依然是一个开放难题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破高斯局限，在任意椭球分布下建立多项式时间近最优稳健散射估计。
实验充分度: ⭐⭐⭐⭐ 理论证明严密完整，包含完整的 SoS 证明与各向同性张量分析，无实证数值模拟代码。
写作质量: ⭐⭐⭐⭐⭐ 结构清晰，由浅入深层层递进，技术直觉与附录引理推导详实自洽。
价值: ⭐⭐⭐⭐⭐ 填补了高维算法稳健统计学中长期存在的理论空白，为非高斯稳健学习提供了全新的分析范式。

分布类别 / 设定	范数度量	误差上界	样本复杂度 \(n\)	计算时间复杂度
一般椭球分布（本文）	相对谱范数 \(\\|\Sigma^{-1/2}\hat{\Sigma}\Sigma^{-1/2} - \mathrm{Id}\\|\)	\(O(\varepsilon \log(1/\varepsilon))\)	\(\tilde{O}(d^2/\varepsilon^2)\)	\(\mathrm{poly}(n)\) 多项式时间
一般椭球分布（本文）	相对 Frobenius 范数	\(O(\varepsilon \log(1/\varepsilon))\) (当 \(\varepsilon \gtrsim \frac{\log d}{\sqrt{d}}\))	\(\tilde{O}(d^2/\varepsilon^2)\)	\(\mathrm{poly}(n)\) 多项式时间
Hanson-Wright 椭球分布（本文）	协方差相对 Frobenius 范数	\(O(\varepsilon \log(1/\varepsilon))\)	\(\tilde{O}(d^2/\varepsilon^2)\)	\(\mathrm{poly}(n)\) 多项式时间
次指数椭球分布（本文）	协方差相对谱范数	\(O(\varepsilon \log(1/\varepsilon))\)	\(\tilde{O}(d^2/\varepsilon^2)\)	\(\mathrm{poly}(n)\) 多项式时间
椭球分布 (Chen et al., 2018)	相对谱范数 (Huber 污染)	\(O(\varepsilon)\) (信息论最优)	\(\Omega(d/\varepsilon)\)	\(\exp(d)\) 指数时间
次高斯分布 (DHPT24 / KS17)	相对谱范数	\(O(\varepsilon \mathrm{polylog}(1/\varepsilon))\)	\(d^{\mathrm{polylog}(1/\varepsilon)}\)	\(d^{\mathrm{polylog}(1/\varepsilon)}\) 准多项式时间
庞加莱分布 (BKR+24)	相对 Frobenius 范数	\(O(\varepsilon \mathrm{polylog}(1/\varepsilon))\)	\(d^{\mathrm{polylog}(1/\varepsilon)}\)	\(d^{\mathrm{polylog}(1/\varepsilon)}\) 准多项式时间
高斯基线 (DKK+16)	相对 Frobenius 范数	\(O(\varepsilon \log(1/\varepsilon))\)	\(\tilde{O}(d^2/\varepsilon^2)\)	\(\mathrm{poly}(n)\) 多项式时间

估计阶段	依赖技术 / 假设	输入状态	输出保障 / 误差指标	作用说明
阶段一：粗估计	[KS17] 次高斯 SoS 滤波	\(\mathrm{erk}(\Sigma) \gtrsim \log d\)	谱范数误差 \(O(\sqrt{\varepsilon} + \frac{1}{\mathrm{erk}(\Sigma)})\)	白化后使得特征值介于 \([0.9, 1.1]\)，将有效秩提升至 \(\Omega(d)\)
阶段二：细谱估计	degree-4 SoS 广义稳定性滤波	\(0.9 \cdot \mathrm{Id} \preceq \Sigma_1 \preceq 1.1 \cdot \mathrm{Id}\)	相对谱范数误差 \(O(\varepsilon \log(1/\varepsilon))\)	消除全矩阵四阶张量 \(O(\\|\Sigma - \mathrm{Id}\\|)\) 漂移，逼近各向同性
阶段三：最终滤波	基无关标准谱滤波 (\(Q=S\))	相对谱范数误差 \(\le O(\varepsilon \log(1/\varepsilon))\)	相对 Frobenius 误差 \(O(\varepsilon \log(1/\varepsilon))\)	最终达到与高斯完全一致的最优相对 Frobenius 误差界
尺度恢复（可选）	一维中位数/截断均值估计	已知近最优散射矩阵方向	标量因子相对误差 \(O(\varepsilon \log(1/\varepsilon)/\sqrt{d})\)	将散射矩阵提升为真实协方差矩阵（仅需 Hanson-Wright 或次指数条件）