# On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data

arXiv: https://arxiv.org/abs/1808.10585 · HTML: https://mlsanity.com/paper/1808.10585/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2018.

## Built on by (most cited first, 30 of 43)

- [Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization](https://mlsanity.com/paper/2102.02414/) (2021)
- [Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2110.12911/) (2021)
- [Robust Imitation Learning from Noisy Demonstrations](https://mlsanity.com/paper/2010.10181/) (2020)
- [Is the Performance of My Deep Network Too Good to Be True? A Direct Approach to Estimating the Bayes Error in Binary Classification](https://mlsanity.com/paper/2202.00395/) (2022)
- [On the Robustness of Average Losses for Partial-Label Learning](https://mlsanity.com/paper/2106.06152/) (2021)
- [Easy Learning from Label Proportions](https://mlsanity.com/paper/2302.03115/) (2023)
- [Two-stage Training for Learning from Label Proportions](https://mlsanity.com/paper/2105.10635/) (2021)
- [Can Less be More? When Increasing-to-Balancing Label Noise Rates Considered Beneficial](https://mlsanity.com/paper/2107.05913/) (2021)
- [Binary Classification with Confidence Difference](https://mlsanity.com/paper/2310.05632/) (2023)
- [Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification](https://mlsanity.com/paper/2102.00678/) (2021)
- [Weakly Supervised AUC Optimization: A Unified Partial AUC Approach](https://mlsanity.com/paper/2305.14258/) (2023)
- [CCMN: A General Framework for Learning with Class-Conditional Multi-Label Noise](https://mlsanity.com/paper/2105.07338/) (2021)
- [Imprecise Label Learning: A Unified Framework for Learning with Various Imprecise Label Configurations](https://mlsanity.com/paper/2305.12715/) (2023)
- [Learning with Proper Partial Labels](https://mlsanity.com/paper/2112.12303/) (2021)
- [Positive-Unlabeled Classification under Class-Prior Shift: A Prior-invariant Approach Based on Density Ratio Estimation](https://mlsanity.com/paper/2107.05045/) (2021)
- [Reduction from Complementary-Label Learning to Probability Estimates](https://mlsanity.com/paper/2209.09500/) (2022)
- [A General Framework for Learning from Weak Supervision](https://mlsanity.com/paper/2402.01922/) (2024)
- [Multi-class Classification from Multiple Unlabeled Datasets with Partial Risk Regularization](https://mlsanity.com/paper/2207.01555/) (2022)
- [Unified Risk Analysis for Weakly Supervised Learning](https://mlsanity.com/paper/2309.08216/) (2023)
- [Making Binary Classification from Multiple Unlabeled Datasets Almost Free of Supervision](https://mlsanity.com/paper/2306.07036/) (2023)
- [Nearly Optimal Sample Complexity for Learning with Label Proportions](https://mlsanity.com/paper/2505.05355/) (2025)
- [On Symmetric Losses for Robust Policy Optimization with Noisy Preferences](https://mlsanity.com/paper/2505.24709/) (2025)
- [Multi-Class Classification from Single-Class Data with Confidences](https://mlsanity.com/paper/2106.08864/) (2021)
- [Labels, Information, and Computation: Efficient Learning Using Sufficient Labels](https://mlsanity.com/paper/2104.09015/) (2021)
- [Learning from Label Proportions with Instance-wise Consistency](https://mlsanity.com/paper/2203.12836/) (2022)
- [Learning from Aggregate responses: Instance Level versus Bag Level Loss Functions](https://mlsanity.com/paper/2401.11081/) (2024)
- [Self Iterative Label Refinement via Robust Unlabeled Learning](https://mlsanity.com/paper/2502.12565/) (2025)
- [Learning from Positive and Unlabeled Data with Augmented Classes](https://mlsanity.com/paper/2207.13274/) (2022)
- [Optimal Learning from Label Proportions with General Loss Functions](https://mlsanity.com/paper/2509.15145/) (2025)
- [A Symmetric Loss Perspective of Reliable Machine Learning](https://mlsanity.com/paper/2101.01366/) (2021)

## Abstract (arXiv)

Empirical risk minimization (ERM), with proper loss function and regularization, is the common practice of supervised classification. In this paper, we study training arbitrary (from linear to deep) binary classifier from only unlabeled (U) data by ERM. We prove that it is impossible to estimate the risk of an arbitrary binary classifier in an unbiased manner given a single set of U data, but it becomes possible given two sets of U data with different class priors. These two facts answer a fundamental question---what the minimal supervision is for training any binary classifier from only U data. Following these findings, we propose an ERM-based learning method from two sets of U data, and then prove it is consistent. Experiments demonstrate the proposed method could train deep models and outperform state-of-the-art methods for learning from two sets of U data.