Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization
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 o...
| Authors | Xiaoyu Li |
|---|---|
| Primary category | cs.LG |
| Published | 15 June 2026 |
| Last updated at source | 17 August 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.