# Optimal Weak to Strong Learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 3 Jun 2022.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Near-Tight Margin-Based Generalization Bounds for Support Vector Machines](https://mlsanity.com/paper/2006.02175/) (2020)
- [Margins are Insufficient for Explaining Gradient Boosting](https://mlsanity.com/paper/2011.04998/) (2020)
- [Margin-Based Generalization Lower Bounds for Boosted Classifiers](https://mlsanity.com/paper/1909.12518/) (2019)
- [Optimal Minimal Margin Maximization with Boosting](https://mlsanity.com/paper/1901.10789/) (2019)

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

- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Your Weak LLM is Secretly a Strong Teacher for Alignment](https://mlsanity.com/paper/2409.08813/) (2024)
- [The Impossibility of Parallelizing Boosting](https://mlsanity.com/paper/2301.09627/) (2023)
- [AdaBoost is not an Optimal Weak to Strong Learner](https://mlsanity.com/paper/2301.11571/) (2023)
- [Improved Margin Generalization Bounds for Voting Classifiers](https://mlsanity.com/paper/2502.16462/) (2025)
- [Boosting, Voting Classifiers and Randomized Sample Compression Schemes](https://mlsanity.com/paper/2402.02976/) (2024)
- [The Many Faces of Optimal Weak-to-Strong Learning](https://mlsanity.com/paper/2408.17148/) (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)
- [Optimal Parallelization of Boosting](https://mlsanity.com/paper/2408.16653/) (2024)
- [The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem](https://mlsanity.com/paper/2409.11597/) (2024)
- [Revisiting Agnostic Boosting](https://mlsanity.com/paper/2503.09384/) (2025)
- [Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets](https://mlsanity.com/paper/2511.20407/) (2025)
- [Sample-Near-Optimal Agnostic Boosting with Improved Running Time](https://mlsanity.com/paper/2601.11265/) (2026)

## Abstract (arXiv)

The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We present a new algorithm that constructs a strong learner from a weak learner but uses less training data than AdaBoost and all other weak to strong learners to achieve the same generalization bounds. A sample complexity lower bound shows that our new algorithm uses the minimum possible amount of training data and is thus optimal. Hence, this work settles the sample complexity of the classic problem of constructing a strong learner from a weak learner.