# Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 3 Oct 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [The role of regularization in classification of high-dimensional noisy Gaussian mixture](https://mlsanity.com/paper/2002.11544/) (2020)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization](https://mlsanity.com/paper/2011.09148/) (2020)
- [Information-theoretic analysis for transfer learning](https://mlsanity.com/paper/2005.08697/) (2020)
- [Unsupervised Learning using Pretrained CNN and Associative Memory Bank](https://mlsanity.com/paper/1805.01033/) (2018)
- [Information-Theoretic Bounds on Transfer Generalization Gap Based on Jensen-Shannon Divergence](https://mlsanity.com/paper/2010.09484/) (2020)
- [Semi-Supervised Learning: the Case When Unlabeled Data is Equally Useful](https://mlsanity.com/paper/2005.11018/) (2020)

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

- [Semi-supervised Vision Transformers at Scale](https://mlsanity.com/paper/2208.05688/) (2022)
- [Toward Understanding Generative Data Augmentation](https://mlsanity.com/paper/2305.17476/) (2023)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?](https://mlsanity.com/paper/2210.08188/) (2022)
- [On Mesa-Optimization in Autoregressively Trained Transformers: Emergence and Capability](https://mlsanity.com/paper/2405.16845/) (2024)
- [Towards Understanding Why FixMatch Generalizes Better Than Supervised Learning](https://mlsanity.com/paper/2410.11206/) (2024)
- [Robust Semi-supervised Learning via f-Divergence and α-R'enyi Divergence](https://mlsanity.com/paper/2405.00454/) (2024)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [A Theory for Conditional Generative Modeling on Multiple Data Sources](https://mlsanity.com/paper/2502.14583/) (2025)
- [Error Bounds of Supervised Classification from Information-Theoretic Perspective](https://mlsanity.com/paper/2406.04567/) (2024)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)

## Abstract (arXiv)

Using information-theoretic principles, we consider the generalization error (gen-error) of iterative semi-supervised learning (SSL) algorithms that iteratively generate pseudo-labels for a large amount of unlabelled data to progressively refine the model parameters. In contrast to most previous works that em bound the gen-error, we provide an em exact expression for the gen-error and particularize it to the binary Gaussian mixture model. Our theoretical results suggest that when the class conditional variances are not too large, the gen-error decreases with the number of iterations, but quickly saturates. On the flip side, if the class conditional variances (and so amount of overlap between the classes) are large, the gen-error increases with the number of iterations. To mitigate this undesirable effect, we show that regularization can reduce the gen-error. The theoretical results are corroborated by extensive experiments on the MNIST and CIFAR datasets in which we notice that for easy-to-distinguish classes, the gen-error improves after several pseudo-labelling iterations, but saturates afterwards, and for more difficult-to-distinguish classes, regularization improves the generalization performance.