# The Cost of Parallelizing Boosting

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 23 Feb 2024.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [The Impossibility of Parallelizing Boosting](https://mlsanity.com/paper/2301.09627/) (2023)
- [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, 3 of 3)

- [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)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold: - First, we prove a tight lower bound, showing that even "slight" parallelization of boosting requires an exponential blow-up in the complexity of training. Specifically, let γ be the weak learner's advantage over random guessing. The famous textscAdaBoost algorithm produces an accurate hypothesis by interacting with the weak learner for tildeO(1 / γ2) rounds where each round runs in polynomial time. Karbasi and Larsen showed that "significant" parallelization must incur exponential blow-up: Any boosting algorithm either interacts with the weak learner for Omega(1 / γ) rounds or incurs an exp(d / γ) blow-up in the complexity of training, where d is the VC dimension of the hypothesis class. We close the gap by showing that any boosting algorithm either has Omega(1 / γ2) rounds of interaction or incurs a smaller exponential blow-up of exp(d). -Complementing our lower bound, we show that there exists a boosting algorithm using tildeO(1/(t γ2)) rounds, and only suffer a blow-up of exp(d · t2). Plugging in t = ω(1), this shows that the smaller blow-up in our lower bound is tight. More interestingly, this provides the first trade-off between the parallelism and the total work required for boosting.