The Impossibility of Parallelizing Boosting

Abstract

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.

References in corpus (4)

• Optimal Weak to Strong Learning
• Federated Functional Gradient Boosting
• Bagging is an Optimal PAC Learner
• A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustness