揭示重加权铰链法在鲁棒半空间学习中的度数瓶颈，用克里斯托弗尔函数精确刻画抗噪极限。
Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization
- 以克里斯托弗尔函数为工具，定量分析低阶证书无法识别的恶意噪声盲区。
- 证明度数2时最多容忍η^{1/2}的污染，而度数4可突破此限制。
- 给出可恢复污染率随度数提升的精确边界，适合研究鲁棒学习理论者阅读。
一个仅依赖低阶矩的去噪证明，其检测能力存在固有盲区：对手可将污染隐藏于清洁数据本身已具典型特征的位置，而任何有界度数的检验都无法发现。该盲区的精确大小由清洁边缘分布的克里斯托弗尔函数决定，它既是数据分析中探测异常的阈值，也是从对手视角看证书无法消除的最大污染量。本文将此对偶关系作为重构重加权铰链法的核心原则，用于在恶意噪声下鲁棒学习γ-边际半空间（Shen 2025；Zeng-Shen 2025）：证书的Sum-of-Squares度数是关键资源，且在中心点c处，度数为2t的证书所能隐藏的最大污染质量恰好等于克里斯托弗尔函数λ_{t+1}(c)。由此导出三个结论：1）证明确保稠密饼状数据误差ε需Ω(log(1/ε))的SoS度数或Ω(√log(1/ε)/√d)的边际，强制了Shen (2025)的log(1/ε)边际；2）加权切比雪夫归约使阈值2t=Θ((|c|/s)^2)紧致，仅依赖一个经典极值估计；3）度数2存在污染屏障，显例显示度数2被卡在η^{1/2}，而度数4可逃脱；4）度数2t算法实现前沿η^{1−1/2t}（t=1时还原Shen 2025），并给出由饼状密度决定的显式常数增益；5）信息论下界η/(2(1−η))可被精确逼近，硬边际下两点实现要求Θ(1/η)混合成分。
原文摘要 · Abstract (English)
A certificate that removes outliers sees the data only through its low-degree moments, and an adversary exploits exactly this, hiding corruption where the clean data already looks typical, in the blind spot no bounded-degree test resolves. That blind spot has an exact size: the Christoffel function of the clean marginal, the quantity data analysis thresholds to detect outliers, here read from the adversary's side as the corruption a certificate cannot remove. We turn this inversion into the organizing principle of the reweighted-hinge approach to robustly learning $γ$-margin halfspaces under malicious noise (Shen 2025; Zeng-Shen 2025): the governing resource is the Sum-of-Squares degree of the certificate, and the resolution principle states that the maximal corruption mass hideable at a center $c$ from a degree-$2t$ certificate is exactly the Christoffel function $λ_{t+1}(c)$. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error $\varepsilon$ costs SoS degree $Ω(\log(1/\varepsilon))$ or margin $Ω(\sqrt{\log(1/\varepsilon)}/\sqrt{d})$, so the $\log(1/\varepsilon)$ margin of Shen (2025) is forced; a weighted-Chebyshev reduction makes the threshold $2t=Θ((|c|/s)^2)$ tight modulo one classical extremal estimate. A degree-2 outlier barrier: an explicit instance on which degree 2 is stuck at $η^{1/2}$ while degree 4 escapes, locating the small breakdown rate in the degree, not the analysis. A degree-$2t$ algorithm tracing the frontier $η^{1-1/2t}$ (recovering Shen 2025 at $t=1$), with an explicit constant gain capped by the pancake density. And an information-theoretic floor of $η/(2(1-η))$, matched exactly from above; under a hard margin its two-point realizations provably require $Θ(1/η)$ mixture components."
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。