Rare-Tail Statistics For Learning Biased Gaussian Halfspaces with Label Noise

We revisit the classical problem of learning general Gaussian halfspaces in the presence of label noise, with particular focus on the large-bias regime where information-computation gaps are conjectured in several standard label-noise models. Concretely, we present and analyse the rare-tail mean estimator, an extremely simple one-shot statistic that averages only the observed minority class. In the large bias regime, classical Averaging (Servedio, 1999), and related global first-moment statistics, are provably suboptimal, while the rare-tail mean estimator recovers the target halfspace direction at the information-theoretic sample rate (modulo log factors) under a broad class of label noise models, including probit noise and margin-monotone noise with very slow decay away from the boundary. Notably, our guarantees allow labels arbitrarily close to the decision boundary to be nearly random, yet still obtain strong directional recovery from a small number of samples. As an application, we show that in a two-stage curriculum learning setup, where an average-case margin-dependent noise mechanism precedes the uniform-noise target (the worst-case noise profile in the same family) with the same Bayes optimal separator, our estimator supplies the missing directional accuracy needed by existing refinement routines, yielding an end-to-end sample-optimal learner in the large-bias regime. The estimator also cleanly interpolates between the noiseless and noisy regimes. In low-noise settings, it retains the same sample complexity rates as classical separability-based methods for realizable halfspace learning, while continuing to admit meaningful guarantees even after linear separability has been destroyed by noise.