mlsanityData to 14 Oct 2026

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

arXiv 2606.17215 ↗First posted 15 Jun 2026cs.LG cs.DS stat.MLcited by 0

Not on the map. Why?

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."

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

34 of 63 references.

References · 34

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  3. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  6. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  7. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  8. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  9. 2019List-Decodable Linear Regressioncited by 42
  10. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  11. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  12. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
22 more
  1. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  2. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  3. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  4. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  5. 2018Efficient active learning of sparse halfspacescited by 13
  6. 2020Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerancecited by 12
  7. 2020On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecited by 11
  8. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  9. 2022List-Decodable Sparse Mean Estimationcited by 11
  10. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  11. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  12. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  13. 2016Sorting out typicality with the inverse moment matrix SOS polynomialcited by 6
  14. 2020On the Error Resistance of Hinge Loss Minimizationcited by 5
  15. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  16. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  17. 2018Data analysis from empirical moments and the Christoffel functioncited by 3
  18. 2023Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noisecited by 3
  19. 2025Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Ratecited by 2
  20. 2020The Moment-SOS hierarchy and the Christoffel-Darboux kernelcited by 1
  21. 2023Polynomial Optimization, Certificates of Positivity, and Christoffel Functioncited by 1
  22. 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifierscited by 1

Built on by

Not cited yet.