Research map / Learning theory and algorithms / Sample complexity
The Many Faces of Optimal Weak-to-Strong Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Majority-of-5, which runs AdaBoost on five disjoint size-m/5 partitions and takes a majority vote, achieving optimal expected sample complexity for weak-to-strong learning, and empirically compares sample-optimal boosting algorithms on five datasets.
Problem
Weak-to-strong learning with optimal sample complexity is known theoretically (Larsen-Ritzert, Larsen bagging), but those algorithms are slow or hard to use, and AdaBoost is provably suboptimal; it is unclear whether optimal learners are practical or how they compare empirically.
Approach
Partition the training data into 5 disjoint pieces, run AdaBoost on each, and combine via majority vote; a margin-based argument shows the expected error of this majority is O(d/(gamma^2 m)), matching the lower bound while keeping AdaBoost-level runtime.
Key results
- Majority-of-5 achieves expected error O(d/(gamma^2 m)), matching the optimal sample complexity, with AdaBoost-level runtime of O(gamma^-2 ln m) weak learner calls.
- In the pilot study on large datasets (Higgs, Boone, Forest Cover), Majority-of-X shows an advantage over AdaBoost, while LarsenRitzert and BaggedAdaBoost perform no better or worse than AdaBoost.
- On the small Diabetes dataset, BaggedAdaBoost outperforms classic AdaBoost, while Majority-of-X may perform poorly on small training sets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Majority-of-5 (partition data into 5 disjoint parts, run AdaBoost on each, majority vote) versus plain AdaBoost | Majority-of-5 weak-to-strong learner · large real-world datasets (Higgs, Boone, Forest Cover) | test accuracy | Mixed |
| Larsen-Ritzert and Larsen (Bagging-based) optimal learners versus plain AdaBoost | LarsenRitzert and BaggedAdaBoost · large real-world datasets (Higgs, Boone, Forest Cover) | test accuracy | No clear effect |
| Bagging (BaggedAdaBoost, 95% resampling with replacement) added to AdaBoost | AdaBoost on small datasets · Diabetes and Adversarial | test accuracy | Helped |
| Majority-of-X with many disjoint AdaBoost copies (X from 3 to 29) on small training sets | Majority-of-X · small datasets (Diabetes, Adversarial) | test accuracy | Hurt |
| Random subsampling of SubSample sub-sets instead of full set (LarsenRitzert) on large datasets | LarsenRitzert · large datasets (Higgs, Boone, Forest Cover) | test accuracy | No clear effect |
Surprising findings
- The two previously known optimal weak-to-strong learners perform no better, or even worse, than standard AdaBoost on large datasets.
- Combining a constant number of AdaBoost voting classifiers yields optimal sample complexity even though a single AdaBoost is provably suboptimal.
Limitations
- Guarantee is in expectation only, not high probability; the proof gives no 1-delta bound.
- Majority-of-X may perform poorly on small training sets, as each AdaBoost sees very little data.
- Empirical study is a pilot with a limited set of datasets and a single weak learner (depth-1 decision trees).
Experimental setup
Datasets: Higgs Boone Forest Cover Diabetes Adversarial (synthetic, from Høgsgaard et al. lower bound)
Benchmarks: Higgs Boone Forest Cover Diabetes Adversarial
Metrics: test accuracy
Baselines: AdaBoost Larsen-Ritzert (LarsenRitzert) BaggedAdaBoost
Builds on: AdaBoost Larsen-Ritzert optimal weak-to-strong learner Bagging Aden-Ali et al. realizable PAC learning analysis Hanneke SubSample
Closest papers by meaning
- AdaBoost is not an Optimal Weak to Strong Learner (ICML 2023 · similarity 0.92)
- Revisiting Agnostic Boosting (NeurIPS 2025 · similarity 0.89)
- Sample-Optimal Agnostic Boosting with Unlabeled Data (ICML 2025 · similarity 0.88)
- Optimal Parallelization of Boosting (NeurIPS 2024 · similarity 0.88)
- Robust Minimax Boosting with Performance Guarantees (NeurIPS 2025 · similarity 0.87)
- A Boosting-Type Convergence Result for AdaBoost.MH with Factorized Multi-Class Classifiers (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.