# The Impossibility of Parallelizing Boosting

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

## Key facts

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

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [Margin-Based Generalization Lower Bounds for Boosted Classifiers](https://mlsanity.com/paper/1909.12518/) (2019)
- [A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustness](https://mlsanity.com/paper/2103.01276/) (2021)
- [Federated Functional Gradient Boosting](https://mlsanity.com/paper/2103.06972/) (2021)

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

- [Boosting, Voting Classifiers and Randomized Sample Compression Schemes](https://mlsanity.com/paper/2402.02976/) (2024)
- [The Cost of Parallelizing Boosting](https://mlsanity.com/paper/2402.15145/) (2024)
- [Optimal Parallelization of Boosting](https://mlsanity.com/paper/2408.16653/) (2024)
- [Statistical Inference for Gradient Boosting Regression](https://mlsanity.com/paper/2509.23127/) (2025)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## 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.