mlsanityData to 7 Oct 2026

Optimal Weak to Strong Learning

arXiv 2206.01563 ↗First posted 3 Jun 2022cs.LG stat.MLcited by 14

Not on the map. Why?

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.

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

Builds on

6 of 29 references.

References · 6

  1. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  2. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 31
  3. 2020Near-Tight Margin-Based Generalization Bounds for Support Vector Machinescited by 19
  4. 2020Margins are Insufficient for Explaining Gradient Boostingcited by 10
  5. 2019Margin-Based Generalization Lower Bounds for Boosted Classifierscited by 9
  6. 2019Optimal Minimal Margin Maximization with Boostingcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 6; 2025: 4; 2026: 1.

14 papers.

Sort:

By area:

  1. 2022Bagging is an Optimal PAC Learnercited by 34
  2. 2024Your Weak LLM is Secretly a Strong Teacher for Alignmentcited by 20
  3. 2023The Impossibility of Parallelizing Boostingcited by 7
  4. 2023AdaBoost is not an Optimal Weak to Strong Learnercited by 6
  5. 2025Improved Margin Generalization Bounds for Voting Classifierscited by 4
  6. 2024Boosting, Voting Classifiers and Randomized Sample Compression Schemescited by 3
  7. 2024The Many Faces of Optimal Weak-to-Strong Learningcited by 3
  8. 2024Sample-Efficient Agnostic Boostingcited by 3
  9. 2025Sample-Optimal Agnostic Boosting with Unlabeled Datacited by 3
  10. 2024Optimal Parallelization of Boostingcited by 2
  11. 2024The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theoremcited by 2
  12. 2025Revisiting Agnostic Boostingcited by 2
2 more
  1. 2025Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Setscited by 2
  2. 2026Sample-Near-Optimal Agnostic Boosting with Improved Running Timecited by 1