The Impossibility of Parallelizing Boosting
This addresses a fundamental limitation in machine learning optimization for researchers and practitioners, revealing that boosting is inherently sequential.
The paper investigates the possibility of parallelizing boosting algorithms and finds a strong negative result, showing that significant parallelization requires an exponential increase in total computing resources for training.
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.