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

Xiaoyu Li

cs.LGJun 15, 2026

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

Authors: Xiaoyu Li

Organizations: University of New South Wales

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 $Ω(\sqrt{\log(1/ε)}/\sqrt{d})$ , explaining why the $\log(1/ε)$ margin Shen (2025) records is forced, with a weighted-Chebyshev reduction making the threshold $2t=Θ((|c|/s)^2)$ 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.

Explore similar work

Apr 29, 2026cs.LG

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals

We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples

(\mathbf{x}, \mathrm{y})

drawn from an unknown distribution on

\mathbb{R}^d\times\{-1, +1\}

, whose marginal distribution on

\mathbf{x}

is standard Gaussian and on

\mathrm{y}

is arbitrary. The goal of each problem is to output a homogeneous halfspace that approaches the best-fitting homogeneous halfspace in terms of its corresponding loss measure. We prove near-optimal computational hardness results for these problems under the widely believed hardness assumption of the Learning With Errors (LWE) problem. Prior hardness results for these problems were mostly established for general halfspaces; our findings extend some of these hardness results to homogeneous halfspaces. Remarkably, our lower bound strictly generalizes over prior works and narrows the gap between the upper and lower bounds for agnostically learning homogeneous halfspaces under Gaussian marginals.

Jizhou Huang, Brendan Juba

Optimal Sample Complexity Homomorphic Encryption Np-Hard Lipschitz Constant

Ask PDF

Sep 15, 2026cs.DS

Efficient Robust Learning at the Information-Theoretic Limit

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of

η+ \varepsilon

where

η

is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than

2η+ \varepsilon.

Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error

η+ \varepsilon

for any constant

\varepsilon

Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1

Empirical Risk Minimization Optimal Sample Complexity Learning-Augmented Algorithms Information-Theoretic Limits

Ask PDF

Jun 9, 2026cs.LG

Efficiently Learning Drifting Halfspaces with Massart Noise

We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error

η+ \tilde O(Δ^{1/3}/γ)

, where

η

upper bounds the Massart noise rate,

Δ

is the drift rate, and

γ

is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with

Δ^{1/2}

, we prove that

Δ^{1/3}

-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.

Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1

Optimal Sample Complexity Learning-Augmented Algorithms Scaling Laws

Ask PDF