Where Bias Meets Near-Random Noise: The Complexity of Massart Halfspaces with an Intercept

A halfspace is the simplest classifier there is: draw a flat boundary and label everything on one side positive. Most theory assumes the boundary passes through the origin. Once it is allowed an offset, so that one class can be rare, and an adversary may flip each label with some probability below one half, efficient learning becomes much harder than learning from that many samples should be. Under Gaussian inputs, two endpoints are known. When the flip probability is bounded away from one half, the cost grows as $d^{\log(1/\gamma)}$, where $\gamma$ is the probability of the rare class. When flips can reach exactly one half, the cost becomes $d^{\log(1/\epsilon)}$ in the target accuracy instead. Nothing is known in between. This note proposes to map that in-between region: one formula for the cost as the noise approaches one half, with a matching lower bound and algorithm, and a numerical check that can confirm or kill the conjecture before any proof is written.

The question matters because the in-between regime is the realistic one. Annotators on rare classes are often barely better than chance, and the existing results say nothing about what happens there. It is also the regime the authors of the general-halfspace work flag as open. A clean answer would tell us exactly how much computation an offset costs, compared with a boundary through the origin, as a function of noise quality.

Setting and the gap being filled

The inputs are standard Gaussian in $d$ dimensions. The target is $\mathrm{sign}(\langle w^*, x\rangle - t)$ with minority-side mass $\gamma$. Labels carry Massart noise: each label of $x$ is flipped with an adversarially chosen probability $\eta(x) \le \eta = (1-\beta)/2$, so $\beta \in (0,1]$ measures how far the noise stays from pure coin-flipping. The goal is error $OPT + \epsilon$. Gaussian marginals make this target reachable, whereas distribution-free efficient learners stop at $\eta + \epsilon$.

Learning general halfspaces with general Massart noise under the Gaussian distribution gives an algorithm with cost $d^{O(\log(1/\gamma))}\mathrm{poly}(1/\epsilon)$ for constant $\eta < 1/2$, and $d^{O(\log(1/\epsilon))}$ at $\eta = 1/2$, each matched by Statistical Query (SQ) lower bounds. The SQ model covers algorithms that see only averages of bounded functions over the data, which includes nearly every practical method. Threshold Phenomena in Learning Halfspaces with Massart Noise builds the matching landscape. It uses an SDP-based certificate for $\eta<1/2$ and a biased random walk on Chow tensors at $\eta = 1/2$. Chow tensors are the label-weighted moment tensors $\mathbb{E}[y\, x^{\otimes k}]$. Both papers leave open how the exponent behaves as $\beta \to 0$, for example $\beta = 1/d$. That is the motivating gap.

Core Claim

We conjecture that the exponent interpolates as

$$ N(d,\gamma,\beta,\epsilon) = d^{\Theta(\min\{\log(1/(\gamma\beta)),\ \log(1/\epsilon)\})}\cdot \mathrm{poly}(1/\epsilon), $$

where $N$ is the sample and time complexity of efficient SQ or low-degree algorithms.

The heuristic comes from how the lower bounds are built. The adversary must hide the threshold behind a one-dimensional label pattern that matches the low-degree moments of a pure-noise pattern. The minority side has mass $\gamma$, and only a $\beta$-fraction of its label signal is guaranteed to survive. So the surviving signal has size about $\gamma\beta$. Matching Gaussian moments up to degree $k$ costs roughly $e^{-\Theta(k)}$ in signal, which suggests $k \approx \log(1/(\gamma\beta))$ until $\gamma\beta$ drops below $\epsilon$. Below that point, ignoring the minority side is already $\epsilon$-accurate, and the $\eta=1/2$ behavior takes over.

The formula recovers both known endpoints. It also predicts something checkable: for fixed $\gamma$, a phase transition at $\beta \approx \epsilon/\gamma$.

Research Program

There are three parts, and the cheapest comes first because it can falsify everything else.

A numerical moment-matching test. For each $(\gamma,\beta)$ we solve a linear program over one-dimensional distributions on a fine grid of the projection $z = \langle w^*,x\rangle$. Its variables are a Massart-feasible conditional label function, with $\eta(z) \le (1-\beta)/2$ and a true threshold at $t = \Phi^{-1}(1-\gamma)$. Its constraints force the label-weighted moments $\mathbb{E}[y z^j]$, for $j \le k$, to equal those of a threshold-free alternative. The output is the largest feasible $k^*(\gamma,\beta)$, which is the degree below which the instance is invisible to low-degree tests. This reuses the univariate moment-matching template of Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise. That paper does this for homogeneous halfspaces, with the error floor as the parameter. We make bias and $\beta$ the parameters. If $k^*$ does not scale like $\log(1/(\gamma\beta))$, the conjecture is wrong and we report the empirical law instead.

The lower bound. Any one-dimensional moment-matching construction lifts to an SQ lower bound of $d^{\Omega(k^*)}$ through the standard hidden-direction argument used in the two Massart hardness papers. The new work is proving the LP's feasibility analytically. That requires an explicit Massart-feasible pattern built from Gaussian quadrature near the threshold, with flip rates saturating $(1-\beta)/2$.

The upper bound. We revisit the polynomial-shift certificate of Threshold Phenomena in Learning Halfspaces with Massart Noise. The goal is to show that degree $O(\min\{\log(1/(\gamma\beta)),\log(1/\epsilon)\})$ suffices, tracking the $\beta$-dependence that the constant-$\eta$ analysis treats as a constant. In the crossover region we switch to the Chow-tensor random walk.

The bias $\gamma$ plays two roles here. It is the parameter of the boundary-through-the-origin versus offset distinction, and it is the knob that drives the gap between samples and computation. The noise model sets the regime.

Baselines

The naive reference point is logistic regression with an intercept, trained on the same samples. Agnostic Learnability of Halfspaces via Logistic Loss shows that plain logistic regression can incur $\Omega(\sqrt{OPT})$ error on adversarially built isotropic distributions. We therefore expect it to fail on moment-matched instances. It shows what a practitioner gets without trying.

The next baseline is a threshold-then-orientation method. Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent estimates the threshold from the empirical label mean, then runs online gradient descent on ramp losses restricted to bands around the current boundary. It is the strongest polynomial-time method for offset halfspaces in the file. Its guarantee is $C\epsilon$ error under adversarial noise, not $OPT+\epsilon$ under Massart noise.

The strongest existing method is the degree-$k$ algorithm of Learning general halfspaces with general Massart noise under the Gaussian distribution, run at its prescribed degree $k \propto \log(1/\gamma)$.

The key ablation sweeps the polynomial degree of that same algorithm, and of our variant, from 1 up to $\log(1/\epsilon)$. This isolates the claim that the needed degree depends on $\gamma\beta$ rather than on $\gamma$ alone.

All methods receive identical sample sets: $d \in \{8,16,32\}$, a grid of $\gamma$ from $0.3$ down to $10^{-3}$, $\beta$ from $1$ down to $10^{-2}$, and both random Massart flips and LP-derived adversarial flips. Hyperparameters are tuned on a held-out split with the same budget of configurations for every method. Wall-clock time is capped equally.

No reported result was found on Lacuna for error on Gaussian Massart halfspaces with bias for any of these methods. The cited papers report only asymptotic rates, so the comparison is against those rates. Beating the strongest baseline means reaching $OPT+\epsilon$ at a degree, or sample count, that follows the $\log(1/(\gamma\beta))$ curve in the region where the baseline either needs a larger degree or fails.

Why not just…?

Why not just append a constant feature and use a homogeneous Massart learner? In the margin setting this is a real threat, and we concede it. With inputs in the unit ball, appending a constant coordinate costs at most a constant factor in margin, as the margin analysis of Online Learning of Maximum p-Norm Margin Classifiers with Bias implies. Combining that with the SGD method of A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise likely settles the offset margin case up to constants. For that reason we deliberately do not study it. Under Gaussian inputs, the appended coordinate has zero variance, which destroys the rotational symmetry that every $OPT+\epsilon$ algorithm relies on. We include the reduction in the experiments only to confirm that it stalls at the $\eta$ floor.

Why not just estimate the threshold from the label mean, then learn the direction? Under Massart noise the adversary controls how the label mean shifts, by up to about $(1-\beta)\gamma/2$. As $\beta\to 0$, the label mean says almost nothing about $t$. The baseline runs on LP-adversarial instances will measure how badly the threshold estimate drifts.

Why not just run the known algorithm at degree $\log(1/\gamma)$? Its analysis treats $1-2\eta$ as a constant. The conjecture predicts that it fails once $\beta \ll 1$, unless the degree grows. The degree ablation tests this directly.

Why not just take the minimum of the two known endpoint bounds? That guess, $d^{\min(\log 1/\gamma,\ \log 1/\epsilon)}$, ignores $\beta$ entirely. It makes a different, testable prediction from ours, and the LP separates the two.

Proposed Experiments

The decisive check is the LP output $k^*(\gamma,\beta)$ plotted against $\log(1/(\gamma\beta))$. Our conjecture predicts a linear relationship with a slope independent of $\gamma$, saturating at $\log(1/\epsilon)$. A $\beta$-independent curve would support the endpoint-minimum alternative instead.

The second check uses the LP's hard instances. It measures the smallest degree at which the polynomial learner reaches $OPT+\epsilon$, and asks whether that degree tracks $k^*+1$.

A real-data sanity check injects Massart flips into UCI Adult, where a nonzero bias is natural. This only tests whether the logistic baseline degrades as $\beta$ shrinks with a rare positive class. No offset-plus-noise number exists for Adult in the file. The file records only that the method of Online Learning of Maximum p-Norm Margin Classifiers with Bias converged "nearly twice as fast as the original ROMMA algorithm" on clean data, and this experiment carries no theoretical weight.