Statistics > Machine Learning
Title:Rare-Tail Statistics For Learning Biased Gaussian Halfspaces with Label Noise
Abstract: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 analyze 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-dependent noise with very slow decay away from the boundary. Notably, our guarantees allow labels arbitrarily close to the decision boundary to be nearly random, while still giving strong directional recovery from a small number of samples. The estimator also cleanly interpolates between the noiseless and noisy regimes: without noise, it attains the same sample rate as classical separability-based methods for realizable halfspaces, and under low noise, or noise that decays away from the boundary, it keeps this rate even after linear separability has been destroyed. As an application, we consider a two-stage curriculum in which source samples, whose noise may be arbitrarily close to $1/2$ near the boundary and decay very slowly away from it, precede target samples, whose noise flips every label at the same rate, i.e., random classification noise (RCN). Since both stages share the same Bayes optimal halfspace, our estimator supplies the directional warm start needed by existing refinement routines, and together they learn the RCN target at the information-theoretic sample rate in the large-bias regime, up to log factors.
| Comments: | NeurIPS 2026, to appear |
|---|---|
| Subjects: | Machine Learning (stat.ML) ; Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST) |
| Cite as: | arXiv:2611.24181 [stat.ML] |
| (or arXiv:2611.24181v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2611.24181 arXiv-issued DOI via DataCite (pending registration) |
Submission history
Access Paper:
- HTML (experimental)
Current browse context:
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.