Sum-of-Squares Degree Barriers for Robust Halfspace Learning

This paper delves into the theoretical limitations of the reweighted-hinge method, a technique used for robustly learning halfspaces in the presence of malicious noise. The core insight is that an adversary can exploit the "blind spot" of low-degree outlier-removal certificates, hiding corruption where clean data already appears typical. The research establishes that the maximal corruption mass that can evade a degree-2t certificate at a given center is precisely quantified by the Christoffel function of the clean marginal. This characterization leads to several significant consequences. Firstly, a margin-degree tradeoff is identified, showing that achieving a certain error rate or margin requires a specific Sum-of-Squares (SoS) degree for the certificate. Secondly, a concrete degree-2 outlier barrier is demonstrated, illustrating an explicit instance where a degree-2 certificate fails while a degree-4 certificate succeeds, pinpointing the method's breakdown rate in terms of degree. Finally, a degree-2t algorithm is proposed that traces the frontier of achievable robustness, recovering prior results and showing explicit constant gains, bounded by pancake density and proven unimprovable by the degree-2 barrier.