# Sample-Optimal Agnostic Boosting with Unlabeled Data

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 44 references that are in the map.
- First posted on arXiv 6 Mar 2025.

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

- [Generalizing Skills with Semi-Supervised Reinforcement Learning](https://mlsanity.com/paper/1612.00429/) (2016)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [Optimal and Adaptive Algorithms for Online Boosting](https://mlsanity.com/paper/1502.02651/) (2015)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021)
- [Online Multiclass Boosting](https://mlsanity.com/paper/1702.07305/) (2017)
- [Communication Efficient Distributed Agnostic Boosting](https://mlsanity.com/paper/1506.06318/) (2015)
- [Online Agnostic Multiclass Boosting](https://mlsanity.com/paper/2205.15113/) (2022)
- [The Cost of Parallelizing Boosting](https://mlsanity.com/paper/2402.15145/) (2024)

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

- [Revisiting Agnostic Boosting](https://mlsanity.com/paper/2503.09384/) (2025)
- [Sample-Near-Optimal Agnostic Boosting with Improved Running Time](https://mlsanity.com/paper/2601.11265/) (2026)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

Boosting provides a practical and provably effective framework for constructing accurate learning algorithms from inaccurate rules of thumb. It extends the promise of sample-efficient learning to settings where direct Empirical Risk Minimization (ERM) may not be implementable efficiently. In the realizable setting, boosting is known to offer this computational reprieve without compromising on sample efficiency. However, in the agnostic case, existing boosting algorithms fall short of achieving the optimal sample complexity. This paper highlights an unexpected and previously unexplored avenue of improvement: unlabeled samples. We design a computationally efficient agnostic boosting algorithm that matches the sample complexity of ERM, given polynomially many additional unlabeled samples. In fact, we show that the total number of samples needed, unlabeled and labeled inclusive, is never more than that for the best known agnostic boosting algorithm -- so this result is never worse -- while only a vanishing fraction of these need to be labeled for the algorithm to succeed. This is particularly fortuitous for learning-theoretic applications of agnostic boosting, which often take place in the distribution-specific setting, where unlabeled samples can be availed for free. We detail other applications of this result in reinforcement learning.