mlsanityData to 7 Oct 2026

The Impossibility of Parallelizing Boosting

arXiv 2301.09627 ↗First posted 23 Jan 2023cs.LG cs.CC cs.DScited by 7

Not on the map. Why?

Abstract (arXiv)

The aim of boosting is to convert a sequence of weak learners into a strong learner. At their heart, these methods are fully sequential. In this paper, we investigate the possibility of parallelizing boosting. Our main contribution is a strong negative result, implying that significant parallelization of boosting requires an exponential blow-up in the total computing resources needed for training.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 8 of its 35 references that are in the map. First posted on arXiv 23 Jan 2023.

Builds on

8 of 35 references.

References · 8

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,120
  2. 2022Bagging is an Optimal PAC Learnercited by 34
  3. 2020Boosting Simple Learnerscited by 16
  4. 2022Optimal Weak to Strong Learningcited by 14
  5. 2021A Boosting Approach to Reinforcement Learningcited by 12
  6. 2019Margin-Based Generalization Lower Bounds for Boosted Classifierscited by 9
  7. 2021A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustnesscited by 6
  8. 2021Federated Functional Gradient Boostingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 3.

7 papers.

  1. 2024Boosting, Voting Classifiers and Randomized Sample Compression Schemescited by 3
  2. 2024The Cost of Parallelizing Boostingcited by 3
  3. 2024Optimal Parallelization of Boostingcited by 2
  4. 2025Statistical Inference for Gradient Boosting Regressioncited by 2
  5. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  6. 2026Tight Generalization Bound for AdaBoostcited by 0
  7. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0