Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization

技术摘要：重加权合页法（Reweighted-Hinge Method）在鲁棒半空间学习中的 Sum-of-Squares 度数障碍

问题陈述
本文研究了在恶意噪声存在下鲁棒地学习半空间（线性分类器）的问题。在 Kearns–Li 恶意噪声模型中，对手观察干净的训练样本，并将 $\eta$ 比例的实例-标签对替换为任意选择的点。目标是输出一个假设 $\hat{w}$，使得其在干净内点上的误差不超过 $\epsilon$。

研究的核心焦点是重加权合页法，这是一类具有影响力的工作，由 Talwar (2020) 发起，并由 Shen (2025) 以及 Zeng 和 Shen (2025) 进行了改进。这些方法通过最小化重加权合页损失来工作，其中权重由离群点移除程序（通常是度数为 2 的 Sum-of-Squares 或方差约束）分配，以抑制受损点。虽然这些方法在对数凹边缘分布（log-concave marginals）下实现了常数级的噪声容忍度，但它们也存在两个公认的局限性：

1. 极小的噪声容忍度： 可容忍的噪声率 $\eta$ 非常小（例如 Shen (2025) 中的 $2^{-32}$），且无法接近 $1/2$ 的最优崩溃点（breakdown point）。
2. 不自然的间隔依赖： 所需的间隔 $\gamma$ 随 $\Omega(\log(1/\epsilon)/\sqrt{d})$ 缩放，将目标精度 $\epsilon$ 与数据几何结构耦合在一起，这种耦合看起来是结构性强制而非自然的。

方法论与核心框架
本文通过 Sum-of-Squares (SoS) 度数和 Christoffel 函数的视角，重新审视了重加权合页法的局限性。

1. 作为障碍的 Christoffel 函数： 作者建立了一个“分辨率原理”（命题 3.3）。他们认为，一个仅依赖于干净边缘分布前 $2t$ 阶矩的度数为 $2t$ 的 SoS 证书，只能检测并移除位于中心 $c$ 处的质量 $\eta$ 的情况，前提是该干净边缘分布的 Christoffel 函数满足 $\lambda_{t+1}(c) < \eta$。

   • 在现代数据分析中，较大的 Christoffel 值通常标记了一个值得保留的“典型”点。
   • 在此对抗设定下，较大的 Christoffel 值代表了对手可以在该位置隐藏的最大破坏质量。
   • 因此，Christoffel 函数充当了一个“证书天花板”：如果破坏质量低于这个天花板，证书就无法将破坏与干净数据区分开来。

2. 矩问题与高斯求积（Gauss Quadrature）： 本文利用了截断矩问题与高斯求积之间的对偶性。度数为 $2t$ 的证书只能在满足以下条件时证明一个“带状区域”（投影周围的一个带状区域）的存在：该带状区域至少包含与前 $2t$ 阶矩相关的 $(t+1)$ 点高斯求积规则中的一个节点。如果该带状区域位于对应正交多项式最大根之外，证书将看到零质量，从而使破坏变得不可见。

3. 度数相关的权衡： 分析表明，控制该方法的“资源”是 SoS 度数 $t$。增加度数可以使证书“看到”更远的尾部（正交多项式的更大根），并解析更高阶的矩差异。

主要贡献与结果

1. 间隔–度数权衡（定理 4.1）
本文证明了间隔中对 $1/\epsilon$ 的对数依赖是证书方法的结构性必然，而非分析松散导致的伪影。

• 为了证明一个距离原点为 $|c|$ 的密集“薄饼”（band）的存在，度数为 $2t$ 的证书要求对于亚高斯边缘分布需满足 $2t = \Omega((|c|/s)^2)$，对于亚指数边缘分布需满足 $2t = \Omega(|c|/s)$（其中 $s$ 是标准差）。
• 由于实现误差 $\epsilon$ 需要证明达到 $\epsilon$-分位数（此处 $|c| \approx s \log(1/\epsilon)$ 对于亚指数尾部）的带状区域，学习者要么必须支付度数成本 $t = \Omega(\log(1/\epsilon))$（导致运行时复杂度为 $n^{\Omega(\log(1/\epsilon))}$），要么必须接受间隔 $\gamma = \Omega(\sqrt{\log(1/\epsilon)}/\sqrt{d})$。
• 这解释了为什么 Shen 的间隔在单次（one-shot）证书模型中是“被迫”产生的。

2. 二次度数离群点障碍（定理 4.7）
作者构造了一个特定的实例，证明了二次重加权在本质上受限于噪声率 $\eta^{1/2}$。

• 构造： 一个“矩掩盖尖峰”（moment-cloaked spike），由位于 $\pm (\sigma/\sqrt{\eta})e_1$ 的两个真实的对数凹簇组成，对手添加了 $\eta n$ 个从相同簇中抽取的脏点。
• 机制： 这些脏点经过设计，恰好消耗掉干净分布的方差预算。因此，二阶矩（方差）保持不变，使得任何对标签不感知的二次程序都无法识别这种破坏。
• 结果： 每个二次重加权都会留下 $\Omega(\eta^{1/2})$ 的脏梯度贡献。相比之下，四阶程序能检测到膨胀的四阶矩，并实现 $\eta^{3/4}$ 的速率。这证实了 Shen (2025) 中的小常数是使用二次度的直接后果。

3. 度数为 $2t$ 的算法（定理 4.9）
本文提出了一个匹配算法，它追踪了由障碍定义的边界。

• 算法： 一种度数为 $2t$ 的重加权合页法，其中离群点移除程序通过证明关于 $2t$ 阶矩的界（可证的超收敛性/hypercontractivity）而非仅仅是方差来进行认证。
• 性能： 该算法可以容忍噪声率 $\eta \le \eta_0(t) = \Omega(\min(\rho/4, (\gamma\rho/((Ct)\bar{\sigma}))^{\frac{2t}{2t-1}}))$。
• 意义： 随着 $t$ 的增加，指数 $1 - 1/2t$ 向 1 逼近，消除了二次度的 $\eta^{1/2}$ 瓶颈。然而，该速率受限于“薄饼密度” $\rho/4$，并且不会趋向于信息论极限的 $1/2$。这种提升是显式的且为常数级的，而非渐近于 $1/2$。

4. 崩溃底线（命题 4.11）
利用两点法（Le Cam's method），本文确立了一个信息论下界：在带有 $\gamma$-间隔对数凹混合分布的恶意噪声下，没有任何算法能实现低于 $\eta/2$ 的内点误差。这证实了所提算法的 $\Theta(\eta)$ 依赖关系是速率紧致的，尽管确切的崩溃常数仍是一个开放问题。

意义与主张
本文声称提供了对重加权合页系列工作局限性的第一个严谨解释，并将 SoS 度数识别为核心的控制资源。

• 统一性： 它在单一框架下统一了间隔限制和噪声容忍度限制：即干净边缘分布的 Christoffel 函数。
• 视角反转： 它反转了 Christoffel 函数的标准用途。虽然通常用于检测典型点（大的 $\lambda$），但在本文中，它作为一个障碍，大的 $\lambda$ 表示对手可以隐藏破坏的位置。
• 特定方法的下界： 作者明确指出，其下界适用于矩/SoS 证书方法（基于低度矩的单次证书）。他们并未声称这些是针对所有高效算法的无条件信息论下界，也没有排除可能逃脱单次证书模型的迭代定位方案。
• 适度的提升： 本文对于算法改进的描述较为克制。度数为 $2t$ 的算法虽然改善了噪声容忍度的指数，但仍受限于薄饼密度，且并未达到 $1/2$ 的崩溃点。其主要贡献在于刻画了权衡边界，而非在实现最优噪声容忍度方面取得突破。

总而言之，本文证明了对于重加权合页法而言，“鲁棒性的代价”是 SoS 度数，而通过在间隔或噪声容忍度上付出的“价格”则由 Christoffel 函数在该度数下的分辨率能力所决定。