# Revisiting Agnostic Boosting

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

## Key facts

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

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

- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [Communication Efficient Distributed Agnostic Boosting](https://mlsanity.com/paper/1506.06318/) (2015)
- [Improved Margin Generalization Bounds for Voting Classifiers](https://mlsanity.com/paper/2502.16462/) (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)

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

- [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 is a key method in statistical learning, allowing for converting weak learners into strong ones. While well studied in the realizable case, the statistical properties of weak-to-strong learning remain less understood in the agnostic setting, where there are no assumptions on the distribution of the labels. In this work, we propose a new agnostic boosting algorithm with substantially improved sample complexity compared to prior works under very general assumptions. Our approach is based on a reduction to the realizable case, followed by a margin-based filtering of high-quality hypotheses. Furthermore, we show a nearly-matching lower bound, settling the sample complexity of agnostic boosting up to logarithmic factors.