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 c...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2402.15145 http://arxiv.org/abs/2402.15145 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
Ejemplares similares: The Cost of Parallelizing Boosting
- The Impossibility of Parallelizing Boosting
- A framework for boosting matching approximation: parallel, distributed, and dynamic
- Approximating Random Walks in $\widetilde{O}(\log n + \log^2 κ)$ Space for $κ$-Conditioned Graphs
- Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem
- Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
- Multicalibration as Boosting for Regression