# Efficient, Noise-Tolerant, and Private Learning via Boosting

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2020.

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

- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Being Properly Improper](https://mlsanity.com/paper/2106.09920/) (2021)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [Multiclass versus Binary Differentially Private PAC Learning](https://mlsanity.com/paper/2107.10870/) (2021)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Transfer Learning In Differential Privacy's Hybrid-Model](https://mlsanity.com/paper/2201.12018/) (2022)
- [Private Boosted Decision Trees via Smooth Re-Weighting](https://mlsanity.com/paper/2201.12648/) (2022)
- [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)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)
- [Differentially-Private Bayes Consistency](https://mlsanity.com/paper/2212.04216/) (2022)
- [Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning](https://mlsanity.com/paper/2505.24737/) (2025)
- [Fast-MWEM: Private Data Release in Sublinear Time](https://mlsanity.com/paper/2602.03732/) (2026)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-tolerant PAC learners. To demonstrate our framework, we use it to construct noise-tolerant and private PAC learners for large-margin halfspaces whose sample complexity does not depend on the dimension. We give two sample complexity bounds for our large-margin halfspace learner. One bound is based only on differential privacy, and uses this guarantee as an asset for ensuring generalization. This first bound illustrates a general methodology for obtaining PAC learners from privacy, which may be of independent interest. The second bound uses standard techniques from the theory of large-margin classification (the fat-shattering dimension) to match the best known sample complexity for differentially private learning of large-margin halfspaces, while additionally tolerating random label noise.