The Cost of Parallelizing Boosting

Xin Lyu, Hongxun Wu, Junzhao Yang

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 prov…