Research map / Label-efficient and robust learning / Noisy labels
Don’t Label Twice: Quantity Beats Quality when Comparing Binary Classifiers on a Budget
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.
placeholder
Problem
How to allocate a fixed noisy-label budget between number of test samples and number of labels per sample (aggregated by majority vote) to maximize the probability of correctly identifying the better of two binary classifiers.
Approach
Proves that with a fixed budget, a single noisy label per data point maximizes the probability of identifying the better classifier, using a reduction to Cramér's theorem on large deviations; extends to correlated classifier/label errors under assumptions and gives tighter sample-size bounds than Hoeffding, enabling more classifiers to be ranked via union bound.
Key results
- For budget k=1500, Cramér-based guarantees allow testing more than 17 models with single labels, while Hoeffding cannot guarantee even two models at delta=0.05.
- Numerical grid search over nearly five billion parameter configurations found single-label collection consistently best (exceptions only at numerical instability level ~1e-12).
- Theorem: for sufficiently large budgets, m=1 maximizes the probability of identifying the better classifier, under assumptions of no biased label accuracy and no biased heterogeneity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use one label on more data points instead of aggregating m labels per data point | Binary classifier comparison · Classifier comparison under the paper's assumptions, sufficiently large label budget | probability of identifying the better classifier | Helped |
| Use one label per data point rather than m-label majority voting | Binary classifier comparison · Numerical parameter sweep | probability of identifying the better classifier | Helped |
| Use the Cramér-based bound rather than the Hoeffding-based bound | Benchmarking · k=1500, δ=0.05 | testable classifiers: >17 models; Hoeffding is too loose to provide a guarantee for two models | Helped |
| Aggregate multiple labels when label accuracy is biased against the better classifier | Binary classifier comparison · Correlated classifier and label errors violating q_b ≥ q_w | probability of identifying the better classifier | Helped |
Surprising findings
- Collecting multiple labels per data point is statistically suboptimal for classifier comparison, contrary to common benchmark practice of majority-vote aggregation.
Limitations
- Main theorem is asymptotic in sample size; small-n optimality is only conjectured and verified numerically.
- Requires assumptions (label accuracy above 0.5, no biased label accuracy/heterogeneity) that may fail in practice.
- Restricted to binary classification; multiclass extension is open.
Experimental setup
Metrics: probability of identifying the better classifier error probability bound number of testable classifiers
Baselines: Hoeffding bound majority vote with multiple labels (m=3)
Builds on: Cramér's theorem Hoeffding's inequality majority vote aggregation
Closest papers by meaning
- The Minimax Rate of Second-Order Calibration (NeurIPS 2026 · similarity 0.86)
- Uncertainty Herding: One Active Learning Method for All Label Budgets (ICLR 2025 · similarity 0.85)
- Information-theoretic Limits of Online Classification with Noisy Labels (NeurIPS 2024 · similarity 0.85)
- Leveraging Uncertainty Estimates To Improve Classifier Performance (ICLR 2024 · similarity 0.85)
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.85)
- Confidence Difference Reflects Various Supervised Signals in Confidence-Difference Classification (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.