# Labels, Information, and Computation: Efficient Learning Using Sufficient Labels

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 70 references that are in the map.
- First posted on arXiv 19 Apr 2021.

## Builds on (most cited first, 30 of 37)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [MixMatch: A Holistic Approach to Semi-Supervised Learning](https://mlsanity.com/paper/1905.02249/) (2019)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Unsupervised Data Augmentation for Consistency Training](https://mlsanity.com/paper/1904.12848/) (2019)
- [Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy Labels](https://mlsanity.com/paper/1804.06872/) (2018)
- [Temporal Ensembling for Semi-Supervised Learning](https://mlsanity.com/paper/1610.02242/) (2016)
- [Virtual Adversarial Training: A Regularization Method for Supervised and Semi-Supervised Learning](https://mlsanity.com/paper/1704.03976/) (2017)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results](https://mlsanity.com/paper/1703.01780/) (2017)
- [Regularization With Stochastic Transformations and Perturbations for Deep Semi-Supervised Learning](https://mlsanity.com/paper/1606.04586/) (2016)
- [Combating noisy labels by agreement: A joint training method with co-regularization](https://mlsanity.com/paper/2003.02752/) (2020)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [Are Anchor Points Really Indispensable in Label-Noise Learning?](https://mlsanity.com/paper/1906.00189/) (2019)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [A Survey on Homomorphic Encryption Schemes: Theory and Implementation](https://mlsanity.com/paper/1704.03578/) (2017)
- [Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features](https://mlsanity.com/paper/1703.02507/) (2017)
- [Multi-class Classification without Multi-class Labels](https://mlsanity.com/paper/1901.00544/) (2019)
- [Learning with Biased Complementary Labels](https://mlsanity.com/paper/1711.09535/) (2017)
- [Masking: A New Perspective of Noisy Supervision](https://mlsanity.com/paper/1805.08193/) (2018)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Complementary-Label Learning for Arbitrary Losses and Models](https://mlsanity.com/paper/1810.04327/) (2018)
- [Learning with Multiple Complementary Labels](https://mlsanity.com/paper/1912.12927/) (2019)
- [Partial Label Learning with Self-Guided Retraining](https://mlsanity.com/paper/1902.03045/) (2019)

## Built on by (most cited first, 2 of 2)

- [Towards Sustainable Development: A Novel Integrated Machine Learning Model for Holistic Environmental Health Monitoring](https://mlsanity.com/paper/2308.10317/) (2023)
- [Effort-Optimized, Accuracy-Driven Labelling and Validation of Test Inputs for DL Systems: A Mixed-Integer Linear Programming Approach](https://mlsanity.com/paper/2507.04990/) (2025)

## Abstract (arXiv)

In supervised learning, obtaining a large set of fully-labeled training data is expensive. We show that we do not always need full label information on every single training example to train a competent classifier. Specifically, inspired by the principle of sufficiency in statistics, we present a statistic (a summary) of the fully-labeled training set that captures almost all the relevant information for classification but at the same time is easier to obtain directly. We call this statistic "sufficiently-labeled data" and prove its sufficiency and efficiency for finding the optimal hidden representations, on which competent classifier heads can be trained using as few as a single randomly-chosen fully-labeled example per class. Sufficiently-labeled data can be obtained from annotators directly without collecting the fully-labeled data first. And we prove that it is easier to directly obtain sufficiently-labeled data than obtaining fully-labeled data. Furthermore, sufficiently-labeled data is naturally more secure since it stores relative, instead of absolute, information. Extensive experimental results are provided to support our theory.