Research map / Learning theory and algorithms / Sample complexity
Optimal Parallelization of Boosting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a parallel Boosting algorithm via bagging plus KL-divergence analysis that matches new lower bounds on the parallel rounds-vs-work tradeoff for weak-to-strong learning, closing the gap up to log factors.
Problem
Parallel complexity of Boosting: the tradeoff between the number of sequential training rounds p and the parallel work per round t for weak-to-strong learning, where previous upper and lower bounds left a large gap.
Approach
Uses bagging to produce many hypotheses in parallel, then searches among them to perform R Boosting steps per round; analyzes the distribution drift with KL divergence (via the Donsker-Varadhan duality) instead of max-divergence, and proves a matching lower bound that uses a biased-coin argument with larger bias when p is small.
Key results
- Algorithm achieves parallel complexity p = O(ln m / (γ² R)) and t = e^{O(dR)} · ln(ln m / (δγ²)) for any R, giving the tradeoff p ln t = O(d ln m / γ²) and matching AdaBoost's sample complexity up to logs.
- Lower bound: any weak-to-strong learner with parallel complexity (p,t) achieving expected loss m^{-0.01} must have p ≥ min{exp(Ω(d)), Ω(γ^{-2} ln m)} or t ≥ exp(exp(Ω(d))) or p ln t = Ω(γ^{-2} d ln m).
- The upper and lower bounds match across the entire p vs. t spectrum up to logarithmic factors, except the t ≥ exp(exp(Ω(d))) term.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KL divergence to track distribution drift in the bagging-based parallel Boosting algorithm | Parallel weak-to-strong learning · Parallel weak-to-strong learning | work per round t: e^{\bigO\Parens*{d R^2}} -> e^{\bigO\Parens*{d R}} | Helped |
| Use the proposed parallel Boosting algorithm | Parallel weak-to-strong learning · Parallel weak-to-strong learning | rounds-work tradeoff: p \ln t = \bigO\Parens*{\frac{d \ln m}{\gamma^2}} | Helped |
Surprising findings
- Previous lower bound claiming p = Ω(γ^{-2} ln m) regardless of t is circumvented by upper bounds because its restrictions on query distributions do not hold for bagging-based algorithms.
Limitations
- The matching holds only up to logarithmic factors and for near-optimal sample complexity.
- Theoretical only; no experiments reported.
Experimental setup
Metrics: parallel complexity (p, t) sample complexity / generalization loss bound
Baselines: AdaBoost Karbasi and Larsen parallel boosting Balcan et al. parallel boosting lower bound Lower bound of Karbasi and Larsen
Builds on: AdaBoost Breiman's min-margin bound Donsker-Varadhan duality formula advanced composition theorem
Closest papers by meaning
- The Many Faces of Optimal Weak-to-Strong Learning (NeurIPS 2024 · similarity 0.88)
- Complexity of Highly Parallel Non-Smooth Convex Optimization (NeurIPS 2019 · similarity 0.87)
- Revisiting Agnostic Boosting (NeurIPS 2025 · similarity 0.86)
- Sample-Efficient Agnostic Boosting (NeurIPS 2024 · similarity 0.86)
- Sample-Optimal Agnostic Boosting with Unlabeled Data (ICML 2025 · similarity 0.85)
- Statistical Inference for Gradient Boosting Regression (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.