Research map / Learning theory and algorithms / Sample complexity
Sample-Optimal Agnostic Boosting with Unlabeled Data
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 a computationally efficient agnostic boosting algorithm using a bivariate-decomposable Huber-based potential so that labeled samples scale as log|H|/eps^2 (matching ERM) given polynomially many extra unlabeled samples.
Problem
Agnostic boosting has sample complexity worse than ERM (log|H|/eps^3 or eps^4); the paper asks whether unlabeled data can close the gap to ERM's log|H|/eps^2 labeled sample complexity.
Approach
Use a potential phi(z,y)=psi(z)-yz (Huber psi) whose derivative splits into a label-only term and a feature-only term, so the feature part is estimated from unlabeled data and the label part from labeled data; relabeling via pseudo-labels from psi'. Labeled examples are reused across rounds without uniform convergence over the boosted class.
Key results
- With 0%-20% label noise on six UCI datasets (90% or 50% labels dropped), the proposed booster averages 0.89 accuracy vs 0.84 for PAB with no added noise.
- Theory: labeled sample complexity log|H|/(gamma^2 eps^2) (matching ERM) with TU = O(VC/(gamma^4 eps^4)) unlabeled samples; a reuse variant reduces unlabeled samples to log|H|/(gamma^3 eps^3).
- Covariate shift resilience: learner still reaches arbitrarily accurate classifier when unlabeled distribution Q has same support as D_X, with labeled complexity unchanged.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed unlabeled-data boosting algorithm instead of PAB | Decision-stump agnostic boosting · UCI datasets average, no added noise | accuracy: 0.84 -> 0.89 | Helped |
| Use the proposed unlabeled-data boosting algorithm instead of PAB | Decision-stump agnostic boosting · UCI datasets average, 5% noise | accuracy: 0.84 -> 0.88 | Helped |
| Use the proposed unlabeled-data boosting algorithm instead of PAB | Decision-stump agnostic boosting · UCI datasets average, 10% noise | accuracy: 0.81 -> 0.84 | Helped |
| Use the proposed unlabeled-data boosting algorithm instead of PAB | Decision-stump agnostic boosting · UCI datasets average, 20% noise | accuracy: 0.78 -> 0.81 | Helped |
| Use the proposed unlabeled-data boosting algorithm instead of PAB | Decision-stump agnostic boosting · Waveform, 5% noise | accuracy: 0.88 -> 0.87 | Hurt |
| Use the proposed unlabeled-data boosting algorithm instead of PAB | Decision-stump agnostic boosting · Waveform, 10% noise | accuracy: 0.86 -> 0.86 | No clear effect |
Surprising findings
- Labeled sample complexity matches ERM's log|H|/eps^2 despite prior agnostic boosters requiring eps^3 or eps^4 labeled samples.
Limitations
- Requires polynomially many additional unlabeled samples (TU = O(VC/(gamma^4 eps^4))), so unlabeled cost remains high in the main result.
- Reuse variant trades unlabeled samples for more weak-learner calls (log|B| factor), and the covariate-shift variant needs more unlabeled samples scaling with C_X^3.
- Experiments are small-scale UCI tabular datasets with decision stumps and a single baseline (PAB).
Experimental setup
Datasets: Ionosphere Diabetes Spambase German Sonar Waveform
Benchmarks: UCI Ionosphere UCI Diabetes UCI Spambase UCI German UCI Sonar UCI Waveform
Metrics: accuracy (50-fold cross-validated)
Baselines: Potential-based Agnostic Booster (PAB)
Builds on: AdaBoost MadaBoost Potential-based Agnostic Boosting (PAB) agnostic weak learning definition (Kanade/Kalai-style)
Closest papers by meaning
- Revisiting Agnostic Boosting (NeurIPS 2025 · similarity 0.92)
- The Many Faces of Optimal Weak-to-Strong Learning (NeurIPS 2024 · similarity 0.88)
- Robust Minimax Boosting with Performance Guarantees (NeurIPS 2025 · similarity 0.85)
- Boosting Methods for Interval-censored Data with Regression and Classification (ICLR 2025 · similarity 0.85)
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.85)
- Out-Of-Domain Unlabeled Data Improves Generalization (ICLR 2024 · 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.