# Boosting Simple Learners

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2020.

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

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Local Borsuk-Ulam, Stability, and Replicability](https://mlsanity.com/paper/2311.01599/) (2023)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Being Properly Improper](https://mlsanity.com/paper/2106.09920/) (2021)
- [Boosting with Tempered Exponential Measures](https://mlsanity.com/paper/2306.05487/) (2023)
- [The Impossibility of Parallelizing Boosting](https://mlsanity.com/paper/2301.09627/) (2023)
- [Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Survey](https://mlsanity.com/paper/2303.06302/) (2023)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [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)
- [Revisiting Agnostic Boosting](https://mlsanity.com/paper/2503.09384/) (2025)
- [Uniform Laws of Large Numbers in Product Spaces](https://mlsanity.com/paper/2603.24493/) (2026)
- [What killed the Convex Booster ?](https://mlsanity.com/paper/2205.09628/) (2022)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [Boosting with List-Decodable Codes](https://mlsanity.com/paper/2607.05791/) (2026)

## Abstract (arXiv)

Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are "rules-of-thumbs" from an "easy-to-learn class". (Schapire and Freund~'12, Shalev-Shwartz and Ben-David '14.) Formally, we assume the class of weak hypotheses has a bounded VC dimension. We focus on two main questions: (i) Oracle Complexity: How many weak hypotheses are needed to produce an accurate hypothesis? We design a novel boosting algorithm and demonstrate that it circumvents a classical lower bound by Freund and Schapire ('95, '12). Whereas the lower bound shows that Omega(1/γ2) weak hypotheses with γ-margin are sometimes necessary, our new method requires only tildeO(1/γ) weak hypothesis, provided that they belong to a class of bounded VC dimension. Unlike previous boosting algorithms which aggregate the weak hypotheses by majority votes, the new boosting algorithm uses more complex ("deeper") aggregation rules. We complement this result by showing that complex aggregation rules are in fact necessary to circumvent the aforementioned lower bound. (ii) Expressivity: Which tasks can be learned by boosting weak hypotheses from a bounded VC class? Can complex concepts that are "far away" from the class be learned? Towards answering the first question we introduce combinatorial-geometric parameters which capture expressivity in boosting. As a corollary we provide an affirmative answer to the second question for well-studied classes, including half-spaces and decision stumps. Along the way, we establish and exploit connections with Discrepancy Theory.