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

arXiv: https://arxiv.org/abs/2606.17215 · HTML: https://mlsanity.com/paper/2606.17215/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 63 references that are in the map.
- First posted on arXiv 15 Jun 2026.

## Builds on (most cited first, 30 of 34)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Efficient active learning of sparse halfspaces](https://mlsanity.com/paper/1805.02350/) (2018)
- [Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance](https://mlsanity.com/paper/2006.03781/) (2020)
- [On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise](https://mlsanity.com/paper/2012.10793/) (2020)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Sorting out typicality with the inverse moment matrix SOS polynomial](https://mlsanity.com/paper/1606.03858/) (2016)
- [On the Error Resistance of Hinge Loss Minimization](https://mlsanity.com/paper/2012.00989/) (2020)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Data analysis from empirical moments and the Christoffel function](https://mlsanity.com/paper/1810.08480/) (2018)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)

## Abstract (arXiv)

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 Omega(log(1/varepsilon)) or margin Omega(√log(1/varepsilon)/√d), so the log(1/varepsilon) 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 η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 Theta(1/η) mixture components."