Research map / Learning theory and algorithms / Sample complexity
Revisiting Agnostic 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.
Proposes an agnostic boosting algorithm that reduces to realizable boosting via re-labelings, then filters hypotheses by margin, achieving near-optimal sample complexity for agnostic weak-to-strong learning under very general weak learner assumptions.
Problem
Weak-to-strong learning (boosting) in the agnostic PAC setting, where labels are arbitrary, and determining the optimal sample complexity of agnostic boosting.
Approach
Reduce agnostic boosting to the realizable case by running a modified AdaBoost on every re-labeling of one sample third, then filter the resulting bag of voting classifiers via margin-based empirical loss minimization on a second third, and select with a validation third; this yields a bound interpolating between agnostic and realizable settings and holds for any non-trivial weak learner (gamma >
Key results
- Algorithm achieves excess error sqrt(C err(f*) beta) + C beta with beta = d_hat/((gamma-eps0)^2 m) polylog, so sample complexity of order d/(eps^2 (gamma-eps0)^2) up to logs for constant advantage, improving prior bounds by a polynomial factor.
- A lower bound shows that agnostic boosting sample complexity is essentially tight up to logarithmic factors, with a matching Omega(d/(gamma^2 (1-L) L^2 ...)) style construction.
- Works for any non-trivial weak learner with gamma > eps0, removing the eps0 = O(eps gamma) requirement of prior agnostic boosting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use realizable boosting followed by margin-based hypothesis filtering and validation selection | Agnostic boosting algorithm · Agnostic learning | sample complexity | Helped |
| Allow any non-trivial weak learner with γ > ε₀, rather than requiring a tighter relationship between advantage parameters | Agnostic boosting algorithm · Agnostic learning | weak-learner applicability | Helped |
| Use the proposed agnostic boosting guarantee instead of the prior method requiring ε₀ = O(εγ) | Agnostic boosting · Agnostic learning | sample complexity: \bigOtilde\Par*{(1-\Corr_{\cD}(f^{\star})) \cdot \hat{d} / (\varepsilon^{2}\gamma^{2}) + \hat{d} / (\varepsilon\gamma^{2 | Helped |
| Use the proposed algorithm under general assumptions | Agnostic boosting algorithm · Agnostic learning | sample complexity | Mixed |
Surprising findings
- The algorithm is computationally inefficient (enumerates all 2^{m/3} re-labelings), so it is comparable to ERM in running time.
Limitations
- Computationally inefficient: runs over all 2^{m/3} re-labelings of a sample third.
- Logarithmic factors remain (conjectured removable).
- Bounds carry extra log factors from the fat-shattering dimension at scale theta/32 and log m union bound.
Experimental setup
Metrics: sample complexity excess error (correlation gap)
Baselines: Kanade-Valiant-style agnostic boosting (Ben-David et al. 2001) Arunachalam-style agnostic boosting (Arunachalam et al.) Brukhim et al. agnostic boosting Karbasi-Krause agnostic boosting
Builds on: AdaBoost agnostic boosting by re-labeling (Ben-David, Long, Mansour 2001) ERM agnostic learning framework (Benedek-Itai / Ben-David et al.) fat-shattering dimension margin bounds
Closest papers by meaning
- Sample-Optimal Agnostic Boosting with Unlabeled Data (ICML 2025 · similarity 0.92)
- The Many Faces of Optimal Weak-to-Strong Learning (NeurIPS 2024 · similarity 0.89)
- Optimal Parallelization of Boosting (NeurIPS 2024 · similarity 0.86)
- Statistical Inference for Gradient Boosting Regression (NeurIPS 2025 · similarity 0.86)
- Robust Minimax Boosting with Performance Guarantees (NeurIPS 2025 · similarity 0.85)
- Relating Misfit to Gain in Weak-to-Strong Generalization Beyond the Squared Loss (ICML 2025 · similarity 0.85)
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.