The Cost of Parallelizing Boosting

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 Ad-aBoost algorithm produces an accurate hypothesis by interacting with the weak learner for O(1/γ 2 ) 1 rounds where each round runs in polynomial time. Karbasi and Larsen showed that "significant" parallelization must incur exponential blowup: Any boosting algorithm either interacts with the weak learner for Ω(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 Ω(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 O(1/(tγ 2 )) rounds, and only suffer a blow-up of exp(d • t 2 ). 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.

Our lower bound follows from a novel interpretation of parallel boosting as a variant of "coin game". The upper bound is inspired by the "bagging" technique in machine learning and draws a connection to differential privacy.