# How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 15 Oct 2022.

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

- [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)
- [Pseudo-Labeling and Confirmation Bias in Deep Semi-Supervised Learning](https://mlsanity.com/paper/1908.02983/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [In Defense of Pseudo-Labeling: An Uncertainty-Aware Pseudo-label Selection Framework for Semi-Supervised Learning](https://mlsanity.com/paper/2101.06329/) (2021)
- [Label Propagation for Deep Semi-supervised Learning](https://mlsanity.com/paper/1904.04717/) (2019)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data](https://mlsanity.com/paper/2010.03622/) (2020)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [An Overview of Deep Semi-Supervised Learning](https://mlsanity.com/paper/2006.05278/) (2020)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [An Information-theoretical Approach to Semi-supervised Learning under Covariate-shift](https://mlsanity.com/paper/2202.12123/) (2022)
- [Distribution-Dependent Analysis of Gibbs-ERM Principle](https://mlsanity.com/paper/1902.01846/) (2019)
- [When can unlabeled data improve the learning rate?](https://mlsanity.com/paper/1905.11866/) (2019)
- [Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithm](https://mlsanity.com/paper/2111.01635/) (2021)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learning](https://mlsanity.com/paper/2110.00926/) (2021)
- [Semi-Supervised Learning: the Case When Unlabeled Data is Equally Useful](https://mlsanity.com/paper/2005.11018/) (2020)
- [Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets](https://mlsanity.com/paper/1906.11148/) (2019)
- [Learning Algorithm Generalization Error Bounds via Auxiliary Distributions](https://mlsanity.com/paper/2210.00483/) (2022)

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

- [Prediction-Powered Semi-Supervised Learning with Online Power Tuning](https://mlsanity.com/paper/2510.22586/) (2025)
- [Robust Semi-supervised Learning via f-Divergence and α-R'enyi Divergence](https://mlsanity.com/paper/2405.00454/) (2024)
- [Variations on the Expectation due to Changes in the Probability Measure](https://mlsanity.com/paper/2502.02887/) (2025)
- [On the Generalization Error of Meta Learning for the Gibbs Algorithm](https://mlsanity.com/paper/2304.14332/) (2023)
- [PTCL: Pseudo-Label Temporal Curriculum Learning for Label-Limited Dynamic Graph](https://mlsanity.com/paper/2504.17641/) (2025)

## Abstract (arXiv)

We provide an exact characterization of the expected generalization error (gen-error) for semi-supervised learning (SSL) with pseudo-labeling via the Gibbs algorithm. The gen-error is expressed in terms of the symmetrized KL information between the output hypothesis, the pseudo-labeled dataset, and the labeled dataset. Distribution-free upper and lower bounds on the gen-error can also be obtained. Our findings offer new insights that the generalization performance of SSL with pseudo-labeling is affected not only by the information between the output hypothesis and input training data but also by the information em shared between the em labeled and em pseudo-labeled data samples. This serves as a guideline to choose an appropriate pseudo-labeling method from a given family of methods. To deepen our understanding, we further explore two examples -- mean estimation and logistic regression. In particular, we analyze how the ratio of the number of unlabeled to labeled data λ affects the gen-error under both scenarios. As λ increases, the gen-error for mean estimation decreases and then saturates at a value larger than when all the samples are labeled, and the gap can be quantified em exactly with our analysis, and is dependent on the cross-covariance between the labeled and pseudo-labeled data samples. For logistic regression, the gen-error and the variance component of the excess risk also decrease as λ increases.