The Cost of Parallelizing Boosting

arXiv:2402.15145v1 Announce Type: new
Abstract: 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 $\gamma$ be the weak learner's advantage over random guessing. The famous \textsc{AdaBoost} algorithm produces an accurate hypothesis by interacting with the weak learner for $\tilde{O}(1 …

abstract algorithms arxiv boosting complexity cost cs.ds cs.lg parallelization prove results study training type work