# Can semi-supervised learning use all the data effectively? A lower bound perspective

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 30 Nov 2023.

## Builds on (most cited first, 25 of 25)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Big Self-Supervised Models are Strong Semi-Supervised Learners](https://mlsanity.com/paper/2006.10029/) (2020)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Rethinking Pre-training and Self-training](https://mlsanity.com/paper/2006.06882/) (2020)
- [A Cookbook of Self-Supervised Learning](https://mlsanity.com/paper/2304.12210/) (2023)
- [Scaling and Benchmarking Self-Supervised Visual Representation Learning](https://mlsanity.com/paper/1905.01235/) (2019)
- [Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data](https://mlsanity.com/paper/2010.03622/) (2020)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Are Large-scale Datasets Necessary for Self-Supervised Pre-training?](https://mlsanity.com/paper/2112.10740/) (2021)
- [Self-training Avoids Using Spurious Features Under Domain Shift](https://mlsanity.com/paper/2006.10032/) (2020)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models](https://mlsanity.com/paper/1902.00194/) (2019)
- [Self-training Converts Weak Learners to Strong Learners in Mixture Models](https://mlsanity.com/paper/2106.13805/) (2021)
- [Barely-Supervised Learning: Semi-Supervised Learning with very few labeled images](https://mlsanity.com/paper/2112.12004/) (2021)
- [When can unlabeled data improve the learning rate?](https://mlsanity.com/paper/1905.11866/) (2019)
- [Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation](https://mlsanity.com/paper/1306.2035/) (2013)
- [Minimax Lower Bounds for Realizable Transductive Classification](https://mlsanity.com/paper/1602.03027/) (2016)
- [Improvability Through Semi-Supervised Learning: A Survey of Theoretical Results](https://mlsanity.com/paper/1908.09574/) (2019)
- [On the Semi-supervised Expectation Maximization](https://mlsanity.com/paper/2211.00537/) (2022)

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

- [Towards Understanding Why FixMatch Generalizes Better Than Supervised Learning](https://mlsanity.com/paper/2410.11206/) (2024)
- [Evaluating multiple models using labeled and unlabeled data](https://mlsanity.com/paper/2501.11866/) (2025)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data](https://mlsanity.com/paper/2409.03335/) (2024)
- [Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization](https://mlsanity.com/paper/2607.07513/) (2026)

## Abstract (arXiv)

Prior works have shown that semi-supervised learning algorithms can leverage unlabeled data to improve over the labeled sample complexity of supervised learning (SL) algorithms. However, existing theoretical analyses focus on regimes where the unlabeled data is sufficient to learn a good decision boundary using unsupervised learning (UL) alone. This begs the question: Can SSL algorithms simultaneously improve upon both UL and SL? To this end, we derive a tight lower bound for 2-Gaussian mixture models that explicitly depends on the labeled and the unlabeled dataset size as well as the signal-to-noise ratio of the mixture distribution. Surprisingly, our result implies that no SSL algorithm can improve upon the minimax-optimal statistical error rates of SL or UL algorithms for these distributions. Nevertheless, we show empirically on real-world data that SSL algorithms can still outperform UL and SL methods. Therefore, our work suggests that, while proving performance gains for SSL algorithms is possible, it requires careful tracking of constants.