# Boosting in the Presence of Massart Noise

arXiv: https://arxiv.org/abs/2106.07779 · HTML: https://mlsanity.com/paper/2106.07779/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 52 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 8 of 8)

- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability](https://mlsanity.com/paper/2006.04787/) (2020)
- [A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2010.01705/) (2020)

## Built on by (most cited first, 10 of 10)

- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [Sample-Efficient Agnostic Boosting](https://mlsanity.com/paper/2410.23632/) (2024)
- [Sample-Optimal Agnostic Boosting with Unlabeled Data](https://mlsanity.com/paper/2503.04706/) (2025)
- [Smoothed Agnostic Learning of Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.17782/) (2025)
- [The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem](https://mlsanity.com/paper/2409.11597/) (2024)
- [What killed the Convex Booster ?](https://mlsanity.com/paper/2205.09628/) (2022)

## Abstract (arXiv)

We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each example x is independently misclassified with probability η(x) ≤ η, where η<1/2. The Massart model lies between the random classification noise model and the agnostic model. Our main positive result is the first computationally efficient boosting algorithm in the presence of Massart noise that achieves misclassification error arbitrarily close to η. Prior to our work, no non-trivial booster was known in this setting. Moreover, we show that this error upper bound is best possible for polynomial-time black-box boosters, under standard cryptographic assumptions. Our upper and lower bounds characterize the complexity of boosting in the distribution-independent PAC model with Massart noise. As a simple application of our positive result, we give the first efficient Massart learner for unions of high-dimensional rectangles.