# The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 59 references that are in the map.
- First posted on arXiv 17 Sep 2024.

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

- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [Efficient, Noise-Tolerant, and Private Learning via Boosting](https://mlsanity.com/paper/2002.01100/) (2020)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021)
- [Improved Quantum Boosting](https://mlsanity.com/paper/2009.08360/) (2020)

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

- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)

## Abstract (arXiv)

Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. We study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to γ-advantage over smooth distributions with m samples, for which strong learning over the uniform distribution requires tildeOmega(1/γ2)· m samples. This matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting, for which the corresponding overhead is O(1/γ). Our work also sheds new light on Impagliazzo's hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function f that is mildly hard against size-s circuits, the hardcore theorem provides a set of inputs on which f is extremely hard against size-s' circuits. A downside of this important result is the loss in circuit size, i.e. that s' ll s. Answering a question of Trevisan, we show that this size loss is necessary and in fact, the parameters achieved by known proofs are the best possible.