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

Abstract

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 $\gamma$-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 ${\lambda }_{t+1}(c)$. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error $\epsilon$ costs SoS degree $\Omega (\log (1/\epsilon ))$ or margin $\Omega (\sqrt{\log (1/\epsilon )}/\sqrt{d})$, so the $\log (1/\epsilon )$ margin of Shen (2025) is forced; a weighted-Chebyshev reduction makes the threshold $2t=\Theta ((|c|/s{)}^2)$ tight modulo one classical extremal estimate. A degree-2 outlier barrier: an explicit instance on which degree 2 is stuck at ${\eta }^{1/2}$ while degree 4 escapes, locating the small breakdown rate in the degree, not the analysis. A degree-$2t$ algorithm tracing the frontier ${\eta }^{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 $\eta /(2(1-\eta ))$, matched exactly from above; under a hard margin its two-point realizations provably require $\Theta (1/\eta )$ mixture components."

v2: Corrected proof of the breakdown floor (Prop. 4.11 -> 4.12): v1's two-point instance is inadmissible under a hard margin and v1's Fact 4.13 is false as stated (removed); the same eta/(2(1-eta)) floor is re-proved via a K = Theta(1/eta)-component construction, shown necessary