The Impossibility of Parallelizing Boosting
Kasper Green Larsen (Aarhus University)Monday, April 22nd 2024, 2-3pm (canceled)
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.
This work was published at ALT’24 and is joint work with Amin Karbasi.
Speaker information:
Kasper Green Larsen is a Full Professor at Aarhus University, Denmark, where he heads the Algorithms, Data Structures and Foundations of Machine Learning research group. His research interests span many areas of theoretical computer science, including machine learning theory, data structures, algorithms and lower bounds. He is a recipient of the Presburger Award and has received best paper awards at COLT, CRYPTO and STOC as well as best student paper awards at STOC and FOCS.