# Sample-Efficient Agnostic Boosting

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 31 Oct 2024.

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

- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [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)
- [AdaBoost is not an Optimal Weak to Strong Learner](https://mlsanity.com/paper/2301.11571/) (2023)
- [Online Agnostic Multiclass Boosting](https://mlsanity.com/paper/2205.15113/) (2022)
- [Variance-Reduced Conservative Policy Iteration](https://mlsanity.com/paper/2212.06283/) (2022)

## 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)

The theory of boosting provides a computational framework for aggregating approximate weak learning algorithms, which perform marginally better than a random predictor, into an accurate strong learner. In the realizable case, the success of the boosting approach is underscored by a remarkable fact that the resultant sample complexity matches that of a computationally demanding alternative, namely Empirical Risk Minimization (ERM). This in particular implies that the realizable boosting methodology has the potential to offer computational relief without compromising on sample efficiency. Despite recent progress, in agnostic boosting, where assumptions on the conditional distribution of labels given feature descriptions are absent, ERM outstrips the agnostic boosting methodology in being quadratically more sample efficient than all known agnostic boosting algorithms. In this paper, we make progress on closing this gap, and give a substantially more sample efficient agnostic boosting algorithm than those known, without compromising on the computational (or oracle) complexity. A key feature of our algorithm is that it leverages the ability to reuse samples across multiple rounds of boosting, while guaranteeing a generalization error strictly better than those obtained by blackbox applications of uniform convergence arguments. We also apply our approach to other previously studied learning problems, including boosting for reinforcement learning, and demonstrate improved results.