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 turns out to have an exact size: the Christoffel function of the clean marginal, the very quantity modern data analysis thresholds to detect outliers, here read from the adversary’s side as the corruption a bounded-degree 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 and Shen, 2025): the governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center c from a degree-2t certificate is exactly the Christoffel function λ_{t+1}(c) of the clean marginal. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error ε costs SoS degree Ω(log(1/ε)) or margin Ω(√(log(1/ε)/d)), explaining why the √log(1/ε) margin Shen (2025) records is forced, with a weighted-Chebyshev reduction making the threshold 2t = Θ((|c|/s)²) tight modulo one classical weighted-extremal estimate. A degree-2 outlier barrier: the resolution principle realized as an explicit instance on which degree 2 is stuck at η^{1/2} while degree 4 escapes, locating the method’s small breakdown rate in the degree, not the analysis. And a degree-2t algorithm tracing the frontier η^{1−1/(2t)} (recovering Shen (2025) at t = 1), whose gain is an explicit constant, capped by the pancake density and shown unimprovable by the degree-2 barrier. An information-theoretic floor of η/(2(1 − η)) completes the picture: it is matched exactly from above, and under a hard margin its two-point realizations provably require Θ(1/η) mixture components.