Research map / Label-efficient and robust learning / Noisy labels
Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical
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 SCARCE, a risk-consistent complementary-label learning method under a Selected-Completely-at-Random assumption that needs neither uniform nor anchor-point ordinary-label data, using unbiased PU-style risk estimation with one-vs-rest and a risk-correction term.
Problem
Complementary-label learning needs consistent methods, but existing ones assume uniform complementary-label generation or require an ordinary-label set with anchor points to estimate a transition matrix for non-uniform cases.
Approach
Model complementary-label generation with a SCAR assumption (per-class selection probability independent of features given not-that-class), derive an unbiased risk estimator via the one-sample PU setting, show the OVR formulation reduces to negative-unlabeled binary problems, and add a non-negative risk-correction function to curb overfitting.
Key results
- SCARCE achieves best accuracy in 39 of 40 synthetic settings across MNIST, Kuzushiji-MNIST and Fashion-MNIST (e.g., MNIST MLP uniform 91.27% vs. GA 88.00%).
- On CLCIFAR-20 with ResNet, SCARCE reaches 20.08% vs. best baseline 8.10% (Phuber-CE), and 19.91% with DenseNet.
- Estimated class priors on MNIST etc. are close to true 0.1 values under the proposed BBE-based class-prior estimation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SCARCE instead of the compared methods | Complementary-label classification · MNIST, Kuzushiji-MNIST, and Fashion-MNIST; uniform, biased, and SCAR settings | accuracy | Helped |
| Use SCARCE instead of the compared methods | CLCIFAR-10 and CLCIFAR-20 · Real-world complementary-label datasets | accuracy | Helped |
| Use OVR loss rather than cross-entropy loss or VPU (ablation) | SCARCE · Uniform complementary-label generation; LeNet; multiple datasets | accuracy | Helped |
| Use cross-entropy loss instead of OVR loss (ablation) | SCARCE · Uniform complementary-label generation; LeNet; multiple datasets | accuracy | Hurt |
| Use VPU instead of OVR loss (ablation) | SCARCE meta-algorithm · Uniform complementary-label generation; LeNet; multiple datasets | accuracy | Hurt |
| Introduce risk correction for the unbiased risk estimator (ablation) | SCARCE · Complementary-label learning with deep neural networks | accuracy | Helped |
| Increase class-prior perturbation substantially (ablation) | SCARCE · Uniform generation process; LeNet | accuracy | Hurt |
Surprising findings
- Cross-entropy instantiation performs worse than the OVR loss, attributed to its unboundedness.
- Uniform-assumption consistent method GA outperforms SCARCE on CIFAR-10 uniform setting.
Limitations
- Method assumes instance-independent complementary-label generation (SCAR), not feature-dependent.
- Sharing representation layers across OVR heads may be infeasible for some PU methods, requiring extra storage and compute.
- Performance degrades when class priors are inaccurately specified or deviate strongly from true values.
Experimental setup
Datasets: MNIST Kuzushiji-MNIST Fashion-MNIST CIFAR-10 CLCIFAR-10 CLCIFAR-20
Benchmarks: MNIST Kuzushiji-MNIST Fashion-MNIST CIFAR-10 CLCIFAR-10 CLCIFAR-20
Metrics: classification accuracy pairwise t-test
Baselines: PC NN GA L-UW L-W OP CC PRODEN EXP MAE Phuber-CE LWS
Builds on: positive-unlabeled learning unbiased PU risk estimator one-vs-rest strategy best bin estimation
Closest papers by meaning
- Learning from Complementary Labels (NeurIPS 2017 · similarity 0.93)
- Learning with Partial-Label and Unlabeled Data: A Uniform Treatment for Supervision Redundancy and Insufficiency (ICML 2024 · similarity 0.88)
- Addressing Multi-Label Learning with Partial Labels: From Sample Selection to Label Selection (AAAI 2025 · similarity 0.88)
- Learning from True-False Labels via Multi-modal Prompt Retrieving (ICML 2025 · similarity 0.87)
- Imprecise Label Learning: A Unified Framework for Learning with Various Imprecise Label Configurations (NeurIPS 2024 · similarity 0.87)
- Adaptive Integration of Partial Label Learning and Negative Learning for Enhanced Noisy Label Learning (AAAI 2024 · similarity 0.86)
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.