重加权铰链方法在鲁棒半空间学习中的平方和度数障碍：基于克里斯托费尔函数的刻画

# 重加权铰链法在鲁棒半空间学习中的平方和度障碍：一个 Christoffel 函数刻画 来源：https://arxiv.org/html/2606.17215 ###### 摘要 一个能够移除异常值的证书，仅通过数据的低阶矩来观察数据；而攻击者恰恰利用了这一点，将破坏隐藏在清洁数据已经看起来“典型”的区域——即任何有界度测试都无法分辨的盲区中。结果发现，这个盲区恰好有一个精确的大小：清洁边际分布的 Christoffel 函数——这个在现代数据分析中被用作*检测*异常值的阈值量——在此处从攻击者的角度被解读为一个有界度证书*无法移除*的破坏。我们将这种反转作为重加权铰链法在恶意噪声下鲁棒学习 间隔半空间（Shen25; ZengShen25）的组织原则：其核心资源是异常值移除证书的平方和（SoS）*度*，而*分辨率原理*指出，在点  处，一个度为  的证书所能隐藏的最大破坏质量恰好是清洁边际分布在该点的 Christoffel 函数 。由此得出三个推论，均针对证书方法（而非信息论）。**一个间隔-度权衡**：将密集煎饼区域的误差保证到  需要 SoS 度  或间隔 ，解释了为何 Shen25 中得到的  间隔是*被迫的*，通过一个加权 Chebyshev 归约使得阈值  紧，模一个经典的加权极值估计。**一个度- 异常值障碍**：分辨率原理具体实现为一个实例，其中度  被限制在 ，而度  可以逃脱，从而将该方法的微小崩溃率定位在度上，而非分析上。**一个度- 算法**：描绘了前沿 （当  时恢复 Shen25），其增益是一个明确的常数，受煎饼密度限制，并由度- 障碍证明不可改进。

这里  大：保留该点（它是典型的）小：异常值数据
分析：大 == 典型（保留点）*相同 ，**相反解读**
这里  大：攻击者可隐藏（无法清除）小：可认证（本文）
大 == 攻击者可以在此处隐藏

图 1：反转变换。相同的 Christoffel 曲线  承载两种相反的含义。在基于矩的数据分析中，大值标记了一个要保留的典型点；在这里，大值恰好是攻击者可以在  处隐藏且没有任何度为  的证书能够清除的破坏质量。同一个对象，左边解读为检测器，右边解读为障碍。

###### 目录
1. 1 引言 (https://arxiv.org/html/2606.17215#S1)
   1. 1.1 技术概述 (https://arxiv.org/html/2606.17215#S1.SS1)
2. 1.2 相关工作 (https://arxiv.org/html/2606.17215#S1.SS2)
3. 2 预备知识 (https://arxiv.org/html/2606.17215#S2)
   1. 2.1 辅助结果 (https://arxiv.org/html/2606.17215#S2.SS1)
4. 3 Christoffel 函数与证书上限 (https://arxiv.org/html/2606.17215#S3)
   1. 3.1 证书上限是一个截断矩问题 (https://arxiv.org/html/2606.17215#S3.SS1)
   2. 3.2 Christoffel 函数决定分辨率 (https://arxiv.org/html/2606.17215#S3.SS2)
   3. 3.3 鲁棒性的度是 Christoffel 度 (https://arxiv.org/html/2606.17215#S3.SS3)
   4. 3.4 从障碍到定律：一个加权 Chebyshev 归约 (https://arxiv.org/html/2606.17215#S3.SS4)
5. 4 推论：障碍与匹配算法 (https://arxiv.org/html/2606.17215#S4)
   1. 4.1 间隔-度权衡 (https://arxiv.org/html/2606.17215#S4.SS1)
   2. 4.2 度- 异常值障碍 (https://arxiv.org/html/2606.17215#S4.SS2)
   3. 4.3 度- 重加权铰链 (https://arxiv.org/html/2606.17215#S4.SS3)
   4. 4.4 信息论下界 (https://arxiv.org/html/2606.17215#S4.SS4)
   5. 4.5 辅助引理 (https://arxiv.org/html/2606.17215#S4.SS5)
6. 5 讨论 (https://arxiv.org/html/2606.17215#S5)
   1. 5.1 背景与比较 (https://arxiv.org/html/2606.17215#S5.SS1)
   2. 5.2 开放问题 (https://arxiv.org/html/2606.17215#S5.SS2)
   3. 5.3 结论 (https://arxiv.org/html/2606.17215#S5.SS3)
7. 参考文献 (https://arxiv.org/html/2606.17215#bib)
8. A 符号与结果概览 (https://arxiv.org/html/2606.17215#A1)
   1. A.1 符号 (https://arxiv.org/html/2606.17215#A1.SS1)
   2. A.2 结果概览 (https://arxiv.org/html/2606.17215#A1.SS2)
9. B 延后证明 (https://arxiv.org/html/2606.17215#A2)
   1. B.1 间隔-度权衡 (https://arxiv.org/html/2606.17215#A2.SS1)
   2. B.2 小值归约与 Gauss 求积 (https://arxiv.org/html/2606.17215#A2.SS2)
   3. B.3 最大根界 (https://arxiv.org/html/2606.17215#A2.SS3)
   4. B.4 对数凹分位数与间隔几何 (https://arxiv.org/html/2606.17215#A2.SS4)
   5. B.5 度- 重加权铰链 (https://arxiv.org/html/2606.17215#A2.SS5)
   6. B.6 度- 异常值障碍 (https://arxiv.org/html/2606.17215#A2.SS6)
   7. B.7 崩溃下界 (https://arxiv.org/html/2606.17215#A2.SS7)
10. C 辅助结果 (https://arxiv.org/html/2606.17215#A3)
    1. C.1 鲁棒学习与对数凹输入 (https://arxiv.org/html/2606.17215#A3.SS1)
    2. C.2 正交多项式与矩问题 (https://arxiv.org/html/2606.17215#A3.SS2)
11. D 从平方和证书到半定规划 (https://arxiv.org/html/2606.17215#A4)
12. E 扩展到恶意噪声 (https://arxiv.org/html/2606.17215#A5)
13. F 更多相关工作 (https://arxiv.org/html/2606.17215#A6)
14. G 进一步审视 Shen25 (https://arxiv.org/html/2606.17215#A7)
    1. G.1 间隔-精度耦合 (https://arxiv.org/html/2606.17215#A7.SS1)
    2. G.2 度- 分析的崩溃常数 (https://arxiv.org/html/2606.17215#A7.SS2)
    3. G.3 重加权程序的自然重构 (https://arxiv.org/html/2606.17215#A7.SS3)

## 1 引言

问题在于，当训练数据中有一个常数比例被攻击者破坏时，如何高效地学习一个半空间。在 KearnsLi93 的恶意噪声模型中，攻击者观察到清洁样本，然后将  比例的（实例，标签）对替换为任意选择的数据点，完全了解学习器和清洁分布；目标是输出  在*清洁*内点上的误差最多为 。这是标准破坏模型中最强的，核心问题是一个多项式时间学习器能够容忍多大的噪声率。一条有影响力的研究路线通过一个单一的算法设备来回答这个问题：铰链损失最小化，随后通过重加权来抑制异常值。Talwar20 观察到，当清洁边际分布在每个点投影到分离方向上的周围放置密集质量（一个“煎饼”区域）时，简单的铰链损失最小化已经能够抵抗噪声。Shen25 通过*重加权*铰链将其转化为对数凹混合边际的常数噪声率保证：权重来自一个度- 异常值移除程序（一个方差约束），并且分析通过量  来控制脏点对铰链梯度的贡献。得到的算法可以容忍常数噪声率，但该常数带有两个限制，作者已明确说明。可容忍的速率很小（在已发表版本中 ），并且 Shen25 指出它“由于我们方法的固有局限性，无法接近最优崩溃点 ”；所需的间隔还带有一个额外的对数因子， ，这是一个“看似不那么自然”的 间隔依赖。同样的两个特征出现在 ZengShen25 的稀疏后续工作中。

间隔对  的依赖是一个先有鸡还是先有蛋的问题。间隔是数据分布的一个固定属性，而精度是学习者的目标，在问题确定后可以任意设定；要求  将两者反向耦合，要求*更好分离的数据*恰好是在学习者要求更小误差的时候，这是数据无法按需提供的。人们更希望固定几何，用计算换取精度，而不是用间隔换取精度。本文解释了这两个限制。我们认为它们不是特定常数或松散不等式的产物，而是控制整个方法的单一资源的后果：多项式，等价地平方和（SoS）*度*，即异常值移除证书的度。重加权铰链方法需要关于清洁边际分布的两个分布事实，两者都由仅读取低阶矩的证书提供：密集煎饼区域质量的*下界*（这样铰链才有信号），以及脏点重加权矩的*上界*（这样异常值程序才能收缩 ）。每个都是基于前  个矩的度为  的 SoS 证明。我们表明这些证明所需的度恰好控制了间隔因子和噪声率，并且 Shen25 的度- 程序处于一个紧前沿的角落。我们全程以度为框架来阐述贡献：度对于这个方法而言，就如同谓词的近似度对于算法设计中的多项式方法一样——它是同时保证和限制该参数的参数。我们的两个下界是度障碍；我们的算法是一个度- 程序，描绘了障碍所划出的前沿。

与任何此类障碍一样，其适用范围至关重要，我们提前说明：下界是针对*矩/SoS-证书方法*的——任何仅以清洁边际的度  认证矩作为分布输入的程序。它们不是信息论的，也不是无条件的统计查询难度。间隔-度障碍在每个方向上可以加强为真正的度- 平方和下界（注 3.1 (https://arxiv.org/html/2606.17215#S3.Thmtheorem1)）；将其提升到完整的  维重加权程序联合体对于  是开放的（第 5.2 节 (https://arxiv.org/html/2606.17215#S5.SS2)）。这正是一类 Shen25 的“我们的方法”所属的方法，这就是为什么这些障碍解释了该路线已知的局限性，而不是与之矛盾。

#### 间隔-度权衡。

我们的第一个结果（定理 4.1 (https://arxiv.org/html/2606.17215#S4.Thmtheorem1)）是关于认证波段质量的障碍。固定一个方向 ，令  为（中心化、对数凹）投影，标准差为 。考虑半宽度为  的波段，中心在 ，距离原点  。任何度为  的 SoS 证书，从  的前  个矩证明  ，需要 （亚高斯）， （亚指数）。一个达到误差  的证书学习器必须为所有但  比例的样本投影认证煎饼区域，其最坏情况是边际分布的  分位数，对于一般对数凹律的亚指数尾，这是一个离中心  的波段。代入得到二分法：这样的学习器必须支付*要么* SoS 度 ，因此运行时间 ，*要么*间隔 。因此，Shen25 间隔中的  是*守恒的*：它可以在 SoS 度之间进行权衡，但在一次性证书模型内无法消除。这就是间隔“看似不那么自然”的结构性原因。同样的计算解释了更精细的一点：为什么 Shen25 支付  而不是 。平方根只出现在真正的亚高斯边际分布中；对于一般对数凹混合的亚指数尾（ ），最坏波段位于 ，度界与  成线性关系，因此间隔支付完整的对数。

#### 度- 异常值障碍。

我们的第二个结果（定理 4.7 (https://arxiv.org/html/2606.17215#S4.Thmtheorem7)）是关于异常值移除程序本身的障碍，它将 Shen25 的度- 选择定位为瓶颈。存在一个清洁的对数凹混合（ ）和一个恶意速率为  的集合，在其上*每个与标签无关的度- （方差）重加权*（任何在没有真实标签的情况下产生的可行 ）在攻击者对脏点选择的期望下，得到 。因此，一个度- 异常值程序被限制在  的速率，恰好是 Shen25 的速率。该障碍在期望意义下是标签无关的，这是必要的：因为一旦移除预算 ，那么对于所有可行  的“字面”陈述就是假的，因为可行多面体包含一个  简单地使尖峰归零；没有标签无关的程序能*找到*那个 ，因为它无法区分同一位置上的脏点和真正的清洁点。该构造需要 ，以便两个真正的对数凹簇能够适应协方差预算；我们在定理中陈述了这一情形。

#### 度- 算法。

我们的第三个结果（定理 4.9 (https://arxiv.org/html/2606.17215#S4.Thmtheorem9)）表明两个障碍所划出的前沿是可以实现的，通过用度- 的 SoS 程序替换 Shen25 的方差程序。度- 重加权为每个可行  证明： ，因此可容忍  并且清洁内点误差 ，时间为 。当  时，这正是 Shen25 的  速率；随着  增长，指数  将移除度- *指数*损失。增益是指数的移除（在异常值瓶颈中 ），代价是亚指数可认证矩常数 ，而不是 ，对于一般的对数凹边际分布这是错误的（对于 Laplace 分布 底数是 ，而不是其平方根；速率受煎饼密度  限制，并且*不*接近 。因此，Shen25 的度- 程序是一个紧前沿的度- 角落：定理 4.7 (https://arxiv.org/html/2606.17215#S4.Thmtheorem7) 显示度  无法击败 ，而定理 4.9 (https://arxiv.org/html/2606.17215#S4.Thmtheorem9)