summaries: The paper considers a popular approach to semi-supervised learning based on iterative pseudo-labeling the unlabelled data and refining the model parameters thereafter. The paper is supported theoretically for the case of the Gaussian mixture model establishing a generalization error bound based on the KL divergence between the pseudo-labeled and true data distributions. The paper is also supported empirically for binary classification examples coming from CIFAR10 and MNIST datasets

summaries: This paper considers one common semi-supervised learning algorithm, pseudo labeling, and studies this problem from theoretical point of view. Specifically, it derives an information theoretic upper bound on generalization error in each iterative update of pseudo labeling. They separate the bound into two main parts: one depends on the mutual information between the data samples and model parameters, and the other depends on the KL distance between the underlying data distribution and pseudo labeled samples from previous iteration. Their main conclusion is that as the number of labeled and unlabeled samples grows, the first term vanishes, but the second term does not necessarily vanish.   In the rest of the paper, the authors rely on the simple example of binary Gaussian Mixture Model to give a more understandable and sensible calculation of the their upper bound. Namely, they calculate the KL distance and mutual information terms in the main theorem and study the behavior of generalization error for this model. The conclusion they made is that the iterative pseudo labeling can decrease the generalization error for only the first few iterations and after than has no effect on reducing the generalization error.

summaries: The paper considers the problem of semi-supervised learning where pseudo-labeling is used to iteratively assign labels for unlabelled data batches to enlarge the labelled dataset for subsequent re-training of the classification model. The paper first adapts the recent results of Bu et al (2020) and Wu et al (2020) to this set-up and provides a general information-theoretic upper bound for the generalization error of such a learning algorithm. The paper then specializes its set-up to a binary classification problem with Gaussian class conditionals and presents its corresponding generalization bound. Additional experiments are performed on the more practical datasets with deep neural network classifiers.

summaries: This paper provides a generalization error bound for iterative semi-supervised learning (SSL) algorithms using information-theoretic principles (see Theorem 1). To provide more intuitions, the authors first work with a simple model, i.e., the binary Gaussian mixture model (bGMM). It is shown in bGMM that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates. The theoretical results on the simple model are corroborated by experiments on MNIST and CIFAR datasets, where similar phenomena are observed, i.e., the generalization error improves after several pseudo-labelling iterations, but saturates afterwards.

abstractText: We consider iterative semi-supervised learning (SSL) algorithms that iteratively generate pseudo-labels for a large amount unlabelled data to progressively refine the model parameters. In particular, we seek to understand the behaviour of the generalization error of iterative SSL algorithms using information-theoretic principles. To obtain bounds that are amenable to numerical evaluation, we first work with a simple model—namely, the binary Gaussian mixture model. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates. The theoretical results on the simple model are corroborated by extensive experiments on several benchmark datasets such as the MNIST and CIFAR datasets in which we notice that the generalization error improves after several pseudo-labelling iterations, but saturates afterwards.

authors:
Stéphane Boucheron
Olivier Bousquet
Gábor Lugosi

title: Theory of classification: A survey of some recent advances

venue: ESAIM: Probability and Statistics,

authors:
Stéphane Boucheron
Gábor Lugosi
Pascal Massart

title: Concentration Inequalities: A Nonasymptotic Theory of Independence

authors:
Yuheng Bu
Shaofeng Zou
Venugopal V Veeravalli

title: Tightening mutual information based bounds on generalization error

venue: IEEE Journal on Selected Areas in Information Theory,

authors:
Kaidi Cao
Colin Wei
Adrien Gaidon
Nikos Arechiga
Tengyu Ma

title: Learning imbalanced datasets with label-distribution-aware margin loss

venue: In Proceedings of the 33rd International Conference on Neural Information Processing Systems,

authors:
Yair Carmon
Aditi Raghunathan
Ludwig Schmidt
Percy Liang
John C Duchi

title: Unlabeled data improves adversarial robustness

authors:
Olivier Chapelle
Bernhard Schlkopf
Alexander Zien (eds

title: Semi-Supervised Learning

venue: URL http://dblp.uni-trier.de/db/

authors:
Nitesh V Chawla
Grigoris Karakoulas

title: Learning from labeled and unlabeled data: An empirical study across techniques and domains

venue: Journal of Artificial Intelligence Research,

authors:
Robert Dupre
Jiri Fajtl
Vasileios Argyriou
Paolo Remagnino

title: Improving dataset volumes and model accuracy with semi-supervised iterative self-learning

venue: IEEE Transactions on Image Processing,

authors:
Amedeo Roberto Esposito
Michael Gastpar
Ibrahim Issa

title: Generalization error bounds via Rényi-, f -divergences and maximal leakage

venue: IEEE Transactions on Information Theory,

authors:
Mahdi Haghifam
Jeffrey Negrea
Ashish Khisti
Daniel M Roy
Gintare Karolina Dziugaite

title: Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Sharu Theresa Jose
Osvaldo Simeone

title: Information-theoretic bounds on transfer generalization gap based on Jensen-Shannon divergence

venue: arXiv preprint arXiv:2010.09484,

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations,

title: Learning multiple layers of features from tiny images

venue: Master’s thesis, University of Toronto,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

title: Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks

venue: In Workshop on Challenges in Representation Learning, ICML,

authors:
Jian Li
Yong Liu
Rong Yin
Weiping Wang

title: Multi-class learning using unlabeled samples: Theory and algorithm

venue: In IJCAI,

authors:
Adrian Tovar Lopez
Varun Jog

title: Generalization error bounds using wasserstein distances

venue: IEEE Information Theory Workshop (ITW),

authors:
David McAllester
Karl Stratos

title: Formal limitations on the measurement of mutual information

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
Jeffrey Negrea
Mahdi Haghifam
Gintare Karolina Dziugaite
Ashish Khisti
Daniel M Roy

title: Information-theoretic generalization bounds for SGLD via data-dependent estimates

venue: In Advances in Neural Information Processing Systems,

authors:
XuanLong Nguyen
Martin J Wainwright
Michael I Jordan

title: Estimating divergence functionals and the likelihood ratio by convex risk minimization

authors:
Samet Oymak
Talha Cihad Gulcu

title: A theoretical characterization of semi-supervised learning with self-training for gaussian mixture models

title: Estimation of entropy and mutual information

venue: Neural Computation,

authors:
Ankit Pensia
Varun Jog
Po-Ling Loh

title: Generalization error bounds for noisy, iterative algorithms

venue: IEEE International Symposium on Information Theory (ISIT),

authors:
Daniel Russo
James Zou

title: Controlling bias in adaptive data analysis using information theory

venue: In Artificial Intelligence and Statistics,

authors:
Aarti Singh
Robert Nowak
Jerry Zhu

title: Unlabeled data: Now it helps, now it doesn’t

authors:
Thomas Steinke
Lydia Zakynthinou

title: Reasoning about generalization via conditional mutual information

venue: In Conference on Learning Theory,

authors:
Isaac Triguero
Salvador Garcı́a
Francisco Herrera

title: Self-labeled techniques for semi-supervised learning: taxonomy, software and empirical study

venue: Knowledge and Information Systems,

authors:
Jesper E Van Engelen
Holger H Hoos

title: A survey on semi-supervised learning

venue: Machine Learning,

title: The Nature of Statistical Learning

title: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics

authors:
Xuetong Wu
Jonathan H Manton
Uwe Aickelin
Jingge Zhu

title: Information-theoretic analysis for transfer learning

authors:
Aolin Xu
Maxim Raginsky

title: Information-theoretic analysis of generalization capability of learning algorithms

authors:
Xiaojin Zhu
Andrew B Goldberg

title: Introduction to semi-supervised learning

venue: Synthesis Lectures on Artificial Intelligence and Machine Learning,

title: Semi-supervised learning literature survey

heading: 1 INTRODUCTION

text:
In real-life machine learning applications, it is relatively easy and cheap to obtain large amounts of unlabelled data, while the number of labelled data examples is usually small due to the high cost of annotating them with true labels. In light of this, semi-supervised learning (SSL) has come to the fore (Chapelle et al., 2006; Zhu, 2008; Van Engelen & Hoos, 2020). SSL makes use of the abundant unlabelled data to augment the performance of learning tasks with few labelled data examples. This has been shown to outperform supervised and unsupervised learning under certain conditions. For example, in a classification problem, the correlation between the additional unlabelled data and the labelled data may help to enhance the accuracy of classifiers. Among the plethora of SSL methods, pseudo-labelling (Lee et al., 2013) has been observed to be a simple and efficient way to improve the generalization performance empirically. In this paper, we consider the problem of pseudo-labelling a subset of the unlabelled data at each iteration based on the previous output parameter and then refining the model progressively, but we are interested in analysing this procedure theoretically. Our goal in this paper is to understand the impact of pseudo-labelling on the generalization error.
A learning algorithm can be viewed as a randomized map from the training dataset to the output model parameter. The output is highly data-dependent and may suffer from overfitting to the given dataset. In statistical learning theory, the generalization error is defined as the expected gap between the test and training losses, and is used to measure the extent to which the algorithms overfit to the training data. In SSL problems, the unlabelled data are expected to improve the generalization performance in a certain manner and thus, it is worthwhile to investigate the behaviour theoretically. In this paper, we leverage results in Bu et al. (2020); Wu et al. (2020) to derive an informationtheoretic generalization error bound at each iteration for iterative SSL.
We state our main theoretical contribution informally as follows.
Theorem [Informal] For a d-variate binary Gaussian mixture model (bGMM) in which each component has variance 2, the generalization error across the different semi-supervised training iterations |gent| can be bounded with high probability as follows:
|gent| / const · E hq G (F (t 1) (↵)) i , (1)
where ↵ represents the correlation between the optimal and estimated parameter vectors, F (t) is the iterated composition of the function F (sketched in Figure 3), and G (sketched in Figure 5) represents the KL-divergence between the pseudo-labelled and true data distributions.
As shown in Figure 1, the upper bound is monotonically decreasing in the iteration count t and converges at around t = 2 with a sufficiently large amount of unlabelled data. In Section 4, we also show that when the number of labelled data or the variance is large enough, using the unlabelled data does not help to significantly reduce the generalization error across iterations t. The behaviour of the empirical generalization error for the bGMM coincides with the upper bound. The results suggest that the proposed upper bound serves as a useful guide to understand how the generalization error changes across the semi-supervised training iterations and it can be used to establish conditions under which unlabelled data can help in terms of generalization. Experimental results on the MNIST and CIFAR datasets corroborate the phenomena for the bGMM that with few labelled data and abundant unlabelled data, the generalization error decreases quickly in the early pseudo-labelling iterations and saturates thereafter. For a more extensive literature review, please refer to Appendix A.

heading: 2 PROBLEM SETUP

text:
Let the instance space be Z = X⇥Y ⇢ Rd+1, the model parameter space be ⇥ and the loss fucntion be l : Z ⇥ ⇥ ! R, where d 2 N. We are given a labelled training dataset Sl = {Z1, . . . , Zn} = {(Xi, Yi)}ni=1 drawn from Z , where each Zi = (Xi, Yi) is independently and identically distributed (i.i.d.) from PZ = PX,Y 2 P(Z) and Xi is i.i.d. from PX 2 P(X ). For any i 2 [n], Xi is a vector of features and Yi is a label indicating the class to which Xi belongs. However, in many real-life machine learning applications, we only have a limited number of labelled data while we have access to a large amount of unlabelled data, which are expensive to annotate. Then we can incorporate the unlabelled training data together with the labelled data to improve the performance of the model. This procedure is called semi-supervised learning (SSL). We are given an independent unlabelled training dataset Su = {X 01, . . . , X 0⌧m}, ⌧ 2 N, where each X 0i is i.i.d. generated from PX 2 P(X ). Typically, m n. In the following, we consider the iterative self-training with pseudo-labelling in SSL setup, as shown in Figure 2. Let t 2 [0 : ⌧ ] denote the iteration counter. In the initial round (t = 0), the labelled data Sl are first used to learn an initial model parameter ✓0 2 ⇥. Next, we split the unlabelled dataset Su into ⌧ disjoint equal-size sub-datasets {Su,k}⌧k=1, where Su,k = {X 0(k 1)m+1, . . . , X 0km}. In each subsequent round t 2 [1 : ⌧ ], based on ✓t 1 trained from the previous round, we use a predictor f✓t 1 : X 7! Y to assign a pseudo-label Ŷ 0i to the unlabelled sample X 0i for all i 2 [(t 1)m+ 1 : tm] := {(t 1)m, (t 1)m+1, . . . , tm}. Let Ŝu,t = {(X 0i, Ŷ 0i )}tmi=(t 1)m+1 denote the tth pseudolabelled dataset. After pseudo-labelling, both the labelled data Sl and the pseudo-labelled data Ŝu,t are used to learn a new model parameter ✓t. The procedure is then repeated iteratively until the maximum number of iterations ⌧ is reached.
Under the setup of iterative SSL, during each iteration t, our goal is to find a model parameter ✓t 2 ⇥ that minimizes the population risk with respect to the underlying data distribution
LPZ (✓t) := EZ⇠PZ [l(✓t, Z)]. (2) Since PZ is unknown, LPZ (✓t) cannot be computed directly. Hence, we instead minimize the empirical risk. The procedure is termed empirical risk minimization (ERM). For any model parameter ✓t 2 ⇥, the empirical risk of the labelled data is defined as
LSl(✓t) := 1
n
nX
i=1
l(✓t, Zi), (3)
and for t 1, the empirical risk of pseudo-labelled data Ŝu,t as
LŜu,t(✓t) := 1
m
tmX
i=(t 1)m+1
l(✓t, (X 0 i, Ŷ 0 i )). (4)
We set LŜu,t(✓t) = 0 for t = 0. For a fixed weight w 2 [0, 1], the total empirical risk can be defined as the following linear combination of LSl(✓t) and LŜu,t(✓t):
LSl,Ŝu,t(✓t) := wLSl(✓t) + (1 w)LŜu,t(✓t). (5)
An SSL algorithm can be characterized by a randomized map from the labelled and unlabelled training data Sl, Su to a model parameter ✓ according to a conditional distribution P✓|Sl,Su . Then at each iteration t, we can use the sequence of conditional distributions {P✓k|Sl,Su}tk=0 with P✓0|Sl,Su = P✓0|Sl to represent an iterative SSL algorithm. The generalization error at the t-th iteration is defined as the expected gap between the population risk of ✓t and the empirical risk on the training data:
gent(PZ , PX , {P✓k|Sl,Su} t k=0, {f✓k}t 1k=0) := E[LPZ (✓t) LSl,Ŝu,t(✓t)] (6)
= w ✓ E✓t [EZ [l(✓t, Z) | ✓t]] 1
n
nX
i=1
E✓t,Zi [l(✓t, Zi)] ◆
+ (1 w) ✓ E✓t [EZ [l(✓t, Z) | ✓t]]
1
m
tmX
i=(t 1)m+1
E✓t,X0i,Ŷ 0i [l(✓t, (X 0 i, Ŷ 0 i ))]
◆ . (7)
When t = 0 and w = 1, the definition of the generalization error above reduces to that of vanilla supervised learning. The generalization error gent is used to measure the extent to which the iterative learning algorithm overfits the training data at the t-th iteration. Instead of focusing on the total generalization error induced during the entire process, we are more interested in the following questions. How does gent evolve as the iteration count t increases? Do the unlabelled data examples in Su help to improve the generalization error?

heading: 3 PRELIMINARIES

text:
Inspired by the information-theoretic generalization results in Bu et al. (2020, Theorem 1) and Wu et al. (2020, Theorem 1), we derive an upper bound on the generalization error gent for any t 2 [0 : ⌧ ] in terms of the mutual information between input data samples (either labelled or pseudolabelled) and the output model parameter ✓t, as well as the KL-divergence between the underlying data distributions and the joint distribution of feature vectors and pseudo-labels.
We denote an R-sub-Gaussian random variable L 2 R (Vershynin, 2018) as L ⇠ subG(R). Furthermore, let us recall the following non-standard information quantities. Definition 1. For arbitrary random variables X , Y and U , define the disintegrated mutual information (Negrea et al., 2019; Haghifam et al., 2020) between X and Y given U as IU (X;Y ) := D(PX,Y |UkPX|U ⌦ PY |U ), and the disintegrated KL-divergence between PX and PY given U as DU (PXkPY ) := D(PX|UkPY |U ). These are (U)-measurable random variables. It follows immediately that the conditional mutual information I(X;Y |U) = EU [IU (X;Y )] and the conditional KL-divergence D(PX|UkPY |U |PU ) = EU [DU (PXkPY )].
Let ✓(t) = (✓0, . . . , ✓t) for any t 2 [0 : ⌧ ]. In iterative SSL, we can upper bound the generalization error as shown in Theorem 1 to follow by applying the law of total expectation. Theorem 1 (Generalization error upper bound for iterative SSL). Suppose l(✓, Z) ⇠ subG(R) under Z ⇠ PZ for all ✓ 2 ⇥, then for any t 2 [0 : ⌧ ],
gent(PZ , PX , {P✓k|Sl,Su} t k=0, {f✓k}t 1k=0)  w n
nX
i=1
E✓(t 1) hp 2R2I✓(t 1)(✓t;Zi) i
+ 1 w m
tmX
i=(t 1)m+1
E✓(t 1) hq 2R2 I✓(t 1)(✓t;X 0 i, Ŷ 0 i ) +D✓(t 1)(PX0i,Ŷ 0i kPZ) i . (8)
The proof of Theorem 1 is provided in Appendix B, in which we provide a general version of upper bound not only applicable for sub-Gaussian loss functions. Compared to Bu et al. (2020, Theorem 1) and Wu et al. (2020, Theorem 1), this bound focuses on the generalization error at each iteration during the learning process, which depends on the disintegrated mutual information and the disintegrated KL-divergence conditioned on the previous outputs. Intuitively, in the upper bound in Theorem 1, the mutual information between the individual input data sample Zi and the output model parameter ✓t measures the extent to which the algorithm is sensitive to the input data, and the KL-divergence between the underlying PZ and pseudo-labelled distribution PX0i,Ŷ 0i measures how well the algorithm generalizes to the true data distribution. As n ! 1 and m ! 1, we show that the disintegrated mutual information I✓(t 1)(✓t;X 0i, Ŷ 0i ) tends to 0 (in probability), which means that there are sufficient training data such that the algorithm can generalize well. On the other hand, the impact on the generalization error of pseudo-labelling is reflected in the KL-divergence D✓(t 1)(PX0i,Ŷ 0i
kPZ) and this term does not necessarily vanish as n,m ! 1. We quantify this precisely in Remark 1 in Section 4.
In iterative learning algorithms, it is usually difficult to directly calculate the mutual information and KL-divergence between the input and the final output (Paninski, 2003; Nguyen et al., 2010; McAllester & Stratos, 2020). However, by applying the law of total expectation and conditioning the information-theoretic quantities on the output model parameters ✓(t 1) = {✓1, . . . , ✓t 1} from previous iterations, we are able to calculate the upper bound iteratively. In the next section, we apply the iterated generalization error bound to a classification problem under a specific generative model—the bGMM. This simple model allows us to derive a tractable upper bound on the generalization error as a function of iteration number t that we can compute numerically.

heading: 4 MAIN RESULTS

text:
We now particularize the iterative semi-supervised classification setup to the bGMM. We calculate the term in (8) to understand the effect of multiple self-training rounds on the generalization error.
Fix a unit vector µ 2 Rd and a scalar 2 R+ = (0,1). Under the bGMM with mean µ and standard deviation (bGMM(µ, )), we assume that the distribution of any labelled data example (X, Y ) is specified as follows. Let Y = { 1,+1}, Y ⇠ PY , where PY ( 1) = PY (1) = 12 , and X|Y ⇠ N (Y µ, 2Id), where Id is the identity matrix of size d ⇥ d. In anticipation of leveraging Theorem 1 together with the sub-Gaussianity of the loss function for the bGMM to derive generalization bounds in terms of information-theoretic quantities (just as in Russo & Zou (2016); Xu & Raginsky (2017); Bu et al. (2020)), we find it convenient to show that X and l(✓, (X, Y )) are bounded w.h.p.. By defining the `1 ball Byr := {x 2 Rd : kx yµk1  r}, we see that
Pr(X 2 BYr ) = ✓ 1 2 ⇣ r ⌘◆d =: 1 r,d, (9)
where (·) is the Gaussian cumulative distribution function. By choosing r appropriately, the failure probability r,d can be made arbitrarily small.
The random vector X is distributed according to the mixture distribution pµ = 12N (µ, 2Id) + 1 2N ( µ,
2Id). In the unlabelled dataset Su, each X0i for i 2 [1 : ⌧m] is drawn i.i.d. from pµ. For any ✓ 2 ⇥, under the bGMM(✓, ), the joint distribution of any pair of (X, Y ) 2 Z is given by N (Y ✓, 2Id)⌦PY . Let the loss function be the negative log-likelihood, which can be expressed as
l(✓, (x, y)) = log PY (y)p✓(x|y) = log 1
2 p (2⇡)d d +
1
2 2 (x y✓)>(x y✓). (10)
The minimizer of min✓2⇥ E(X,Y )⇠N (Y µ, 2Id)⌦PY [l(✓, (X, Y ))] is equal to µ. To show that ✓ is bounded with high probability, define the set ⇥µ,c := {✓ 2 ⇥ : k✓ µk1  c} for some c > 0. For any ✓ 2 ⇥µ,c, we have
min (x,y)2Z l(✓, (x, y)) = log 1 2 p (2⇡)d d =: c1, and (11)
max x2Byr ,y2Y l(✓, (x, y))  log 1 2 p (2⇡)d d +
d(c+ r)2
2 2 =: c2. (12)
For any (X, Y ) from the bGMM(µ, ) and any ✓ 2 ⇥µ,c, the probability that l(✓, (X, Y )) belongs to the interval [c1, c2] (c1, c2 depend on r,d) can be lower bounded by
Pr l(✓, (X, Y )) 2 [c1, c2]
1 r,d. (13)
Thus, according to Hoeffding’s lemma, with probability at least 1 r,d, l(✓, (X, Y )) ⇠ subG((c2 c1)/2) under (X, Y ) ⇠ N (Y µ, 2Id)⌦ PY for all ✓ 2 ⇥µ,c, i.e., for all 2 R,
EX,Y ⇥ exp
l(✓, (X, Y )) EX,Y [l(✓, (X, Y ))] ⇤  exp
✓ 2(c2 c1)2
8
◆ . (14)
Under this setup, the iterative SSL procedure is shown in Figure 2, but the labelled dataset Sl is only used to train in the initial round t = 0; we discuss the use of Sl in all iterations in Corollary 3. The algorithm operates in the following steps.
• Step 1: Initial round t = 0 with Sl: By minimizing the empirical risk of labelled dataset Sl
LSl(✓) = 1
n
nX
i=1
l(✓, (Xi, Yi)) c =
1
2 2n
nX
i=1
(Xi Yi✓)>(Xi Yi✓), (15)
where c= means that both sides differ by a constant independent of ✓, we obtain the minimizer
✓0 = argmin ✓2⇥
LSl(✓) = 1
n
nX
i=1
YiXi. (16)
• Step 2: Pseudo-label data in Su: At each iteration t 2 [1 : ⌧ ], for any i 2 [(t 1)m+ 1 : tm], we use ✓t 1 to assign a pseudo-label for X0i, that is, Ŷ 0i = f✓t 1(X0i) = sgn(✓>t 1X0i).
• Step 3: Refine the model: We then use the pseudo-labelled dataset Ŝu,t to train the new model. By minimizing the empirical risk of Ŝu,t
LŜu,t(✓)= 1
m
tmX
i=(t 1)m+1
l(✓, (X0i, Ŷ 0 i )) c =
1
2 2m
tmX
i=(t 1)m+1
(X0i Ŷ 0i ✓)>(X0i Ŷ 0i ✓), (17)
we obtain the new model parameter
✓t = 1
m
tmX
i=(t 1)m+1
Ŷ 0i X 0 i =
1
m
tmX
i=(t 1)m+1
sgn(✓>t 1X 0 i)X 0 i. (18)
If t < ⌧ , go back to Step 2.
To state our result succinctly, we first define some non-standard notations and functions. From (16), we know that ✓0 ⇠ N (µ, 2
n Id) and inspired by Oymak & Gulcu (2021), we can decompose ✓0 as ✓0 = (1+
p n ⇠0)µ+ p n µ?, where ⇠0 ⇠ N (0, 1), µ? ⇠ N (0, Id µµ>), and µ? is perpendicular
to µ and independent of ⇠0 (the details of this decomposition are provided in Appendix C).
Given two vectors (a,b), define their correlation as ⇢(a,b) := ha,bikak2kbk2 in [ 1, 1]. The correlation between the estimated parameter ✓0 and true parameter µ is given by
↵(⇠0,µ ?) := ⇢(✓0,µ) =
1 + p n ⇠0
q (1 + p
n ⇠0)2 +
2
n kµ?k 2 2
. (19)
Let (⇠0,µ?) = p
1 ↵(⇠0,µ?)2. We abbreviate ↵(⇠0,µ?) and (⇠0,µ?) to ↵ and respectively in the following. We can decompose the normalized vector ✓0/k✓0k2 as follows
✓̄0 := ✓0
k✓0k2 = ↵µ+ , (20)
where = µ?/kµ?k2. Let ✓̄?0 := (2 2µ 2↵ )/ , which is a vector perpendicular to ✓̄0. Define the KL-divergence between the pseudo-labelled data distribution and the true data distribution after the first iteration G : [ 1, 1]⇥ R⇥ Rd ! [0,1) as
G (↵, ⇠0,µ ?) :=D
✓ ⇣ ↵
⌘ pg̃+ 2↵ |g̃ ↵ ⌦ pg̃?+✓̄?0 + ⇣↵ ⌘ pg̃|g̃↵ ⌦ pg̃? pg̃ ⌦ pg̃? ◆ , (21)
where g̃ ⇠ N (0, 1), g̃? ⇠ N (0, Id ✓̄0✓̄>0 ), g̃? is independent of g̃ and perpendicular to ✓̄0. Note that pg̃+ 2↵ |g̃ ↵ is the Gaussian probability density function with mean 2↵ and variance 1 truncated to the interval ( 1, ↵ ), and similarly for pg̃|g̃↵ . In general, when G (↵, ⇠0,µ ?) is small, so is the generalization error.
Let Q(·) := 1 (·). Define the correlation evolution function F : [ 1, 1] ! [ 1, 1] that quantifies the increase to the correlation (between the current model parameter and the optimal one) and improvement to the generalization error as the iteration counter increases from t to t+ 1:
F (x) := 1 +
2 2(1 x2) ⇡ exp( x2
2 ) 1 2Q x + 2 xp
2⇡ exp( x22 2 )
2
! 12 . (22)
-1 -0.5 0 0.5 1 -1
-0.5
0
0.5
1
Figure 3: F (t) (x) versus x for different t when = 0.5.
-1 -0.5 0 0.5 1 -1
-0.5
0
0.5
1
Figure 4: F (x) versus x for = 0.3 and 0.5.
The tth iterate of the function F is defined as F (t) := F F (t 1) with F (0) (x) = x. As shown in Figure 3, for any fixed , we can see that F (2) (x) F (x) x for x 0 and F (2) (x) < F (x) < x for x < 0. It can also be easily deduced that for any t 2 [0 : ⌧ ], F (t+1) (x) F (t) (x) for any x 0 and F (t+1) (x) < F (t) (x) for any x < 0. This important observation implies that if the correlation ↵, defined in (19), is positive, F (t) (↵) increases with t; and vice versa. Moreover, as shown in Figure 4, by varying , we can see that smaller results in a larger |F (x)|. By applying the result in Theorem 1, the following theorem provides an upper bound for the generalization error at each iteration t for m large enough. Theorem 2. Fix any 2 R+, d 2 N, ✏ 2 R+ and 2 (0, 1). With probability at least 1 , the absolute generalization error at t = 0 can be upper bounded as follows
gen0(PZ, PX, P✓0|Sl,Su)
r (c2 c1)2d
4 log
n
n 1 . (23)
For each t 2 [1 : ⌧ ], for m large enough, with probability at least 1 , gent(PZ, PX, {P✓k|Sl,Su} t k=0, {f✓k}t 1k=0)
 r
(c2 c1)2 2 E⇠0,µ? q G F (t 1) (↵(⇠0,µ?)), ⇠0,µ? + ✏ . (24)
The proof of Theorem 2 is provided in Appendix C. Several remarks are in order.
First, to gain more insight, we numerically plot G (↵, ⇠0,µ?) when d = 2 and µ = (1, 0) in Figure 5. Under these settings, G (↵, ⇠0,µ?) depends only on ↵ and hence, we can rewrite it as G (↵). As shown in Figure 5, for all 1 > 2, there exists an ↵0 2 [ 1, 1] such that for all
↵ ↵0 = ↵0( 1, 2), G 1(↵) > G 2(↵). From (19), we can see that ↵ is close to 1 of high probability, which means that 7! G (↵) is monotonically increasing in with high probability. As a result, E↵[ p G (↵)] increases as increases. This is consistent with the intuition that when the training data has larger variance, it is more difficult to generalize well. Moreover, for ↵ > 0, G (↵) decreases as ↵ increases. Since F (t) (↵) is increasing in t for ↵ > 0, then G (F (t) (↵)) is decreasing in t, which implies that the upper bound in (24) is also decreasing in t. Remark 1. As n ! 1, ✓0 ! µ and ↵ = ⇢(✓0,µ) ! 1 almost surely, which means that the estimator converges to the optimal classifier for this bGMM. However, since there is no margin between two groups of data samples, the error probability Pr(Ŷ 0j 6= Y 0j ) ! Q(1/ ) > 0 (which is the Bayes error rate) and the disintegrated KL-divergence D⇠0,µ?(PX0j ,Ŷ 0j
kPX,Y ) between the estimated and underlying distributions cannot converge to 0. We discuss the other extreme case in which ↵ = 1 in Remark 2 in Appendix C of the supplementary material.
Second, by letting ✏ ! 0, we compare the upper bounds for |gen0| and |gen1|, as shown in Figures 6(a) and 6(b). For any fixed , when n is sufficiently small, the upper bound for |gen0| is greater than that for |gen1|. As n increases, the upper bound for |gen1| surpasses that of |gen0|, as shown in Figure 6(b). This is consistent with the intuition that when the labelled data is limited, using the unlabelled data can help improve the generalization performance. However, as the number of labelled data increases, using the unlabelled data may degrade the generalization performance, if the distributions corresponding to classes +1 and 1 have a large overlap. This is because the labelled data is already effective in learning the unknown parameter ✓t well and additional pseudo-labelled data does not help to further boost the generalization performance. Furthermore, by comparing Figures 6(a) and 6(b), we can see that for smaller , the improvement from |gen0| to |gen1| is more pronounced. The intuition is that when decreases, the data samples have smaller variance and thus the pseudo-labelling is more accurate. In this case, unlabelled data can improve the generalization performance. Let us examine the effect of n, the number of labelled training samples. By expanding ↵, defined in (19), using a Taylor series, we have
↵ = 1 2
2n kµ?k22 + o
✓ 1
n
◆ . (25)
It can be seen that as n increases, ↵ converges to 1 in probability. Suppose the dimension d = 2 and µ = (1, 0). Then µ? = [0, µ?2 ] where µ?2 ⇠ N (0, 1). The upper bound for the absolute generalization error at t = 1 can be rewritten as
|gen1| / r
(c2 c1)2 2
Z p2
p 2
p np ⇡ e ny2 2 p G (1 y2) dy, (26)
which is a decreasing function of n, as shown in Figures 6(a) and 6(b).
Third, given any pair of (⇠0,µ?), if ↵(⇠0,µ?) > 0, F (t) (↵(⇠0,µ?)) > F (t 1) (↵(⇠0,µ?)) for all t 2 [1 : ⌧ ], as shown in Figure 3. This means that if the quality of the labelled data Sl is reasonably good, by using ✓0 which is learned from Sl, the generated pseudo-labels for the unlabelled data are largely correct. Then the subsequent parameters ✓t, t 1 learned from the large number of pseudo-labelled data examples can improve the generalization error. Therefore, the upper bound for |gent| decreases as t increases. In Figure 6(c), we plot the theoretical upper bound in (24) by
ignoring ✏. Unfortunately it is computationally difficult to numerically calculate the bound in (24) for high dimensions d (due to the need for high-dimensional numerical integration), but we can still gain insight from the result for d = 2. It is shown that the upper bound for |gent| decreases as t increases and finally converges to a non-zero constant. The gap between the upper bounds for |gent| and for |gent+1| decreases as t increases and shrinks to almost 0 for t 2. The intuition is that as m ! 1, there are sufficient data at each iteration and the algorithm can converge at very early stage. In the empirical simulation, we let d = 50, µ = (1, 0, . . . , 0) and iteratively run the self-training procedure for 20 iterations and 2000 rounds. We find that the behaviour of the empirical generalization error (the red ‘-x’ line) is similar to the theoretical upper bound (the blue ‘-o’ line), which almost converges to its final value at t = 2. This result shows that the theoretical upper bound in (24) serves as a useful rule-of-thumb for how the generalization error changes over iterations. In Figure 6(d), we plot the theoretical bound and result from the empirical simulation based on the toy example for d = 2 but larger n and . This figure shows that when we increase n and , using unlabelled data may not be able to improve the generalization performance. The intuition is that for n large enough, merely using the labelled data can yield sufficiently low generalization error and for subsequent iterations with the pseudo-labelled data, the reduction in the test loss is negligible but the training loss will decrease more significantly (thus causing the generalization error to increase). When is larger, the data samples have larger variance and the classes have a larger overlap, and thus, the initial parameter ✓0 learned by the labelled data cannot produce pseudo-labels with sufficiently high accuracy. Thus, the pseudo-labelled data cannot help to improve the generalization error significantly.
Fourth, we consider an “enhanced” scenario in which the labelled data in Sl are reused in each iteration. Set w = nn+m in (5). We can extend Theorem 2 to Corollary 3 as follows. Similarly to F , let us define the enhanced correlation evolution function F̃ ,⇠0,µ? : [ 1, 1] ! [ 1, 1] as follows:
F̃ ,⇠0,µ?(x) =
0
@1 +
w kµ ?k2 n + (1 w)( 2 p 1 x2p 2⇡ exp( x 2 2 2 ) 2
w(1 + p n ⇠0) + (1 w)(1 2Q
x + 2 xp 2⇡ exp( x22 2 ))
2
1 A 12
. (27)
Corollary 3. Fix any 2 R+, d 2 N, ✏ 2 R+ and 2 (0, 1). For m large enough, with probability at least 1 , the absolute generalization error at any t 2 [1 : ⌧ ] can be upper bounded as follows
gent(PZ, PX, {P✓k|Sl,Su} t k=0, {f✓k}t 1k=0)
 w r
(c2 c1)2d 4 log n n 1
+ (1 w) r
(c2 c1)2 2 E⇠0,µ? q G F̃ (t 1) ,⇠0,µ?(↵(⇠0,µ ?)), ⇠0,µ? + ✏ . (28)
The details are provided in Appendix D and the proof of Corollary 3 is provided in Appendix E. It can be seen from Figure 11 that the new upper bound for |gent| remains as a decreasing function of t. We find that when n = 10, m = 1000, the upper bound is almost the same as that one in Figure 6(c), which means that for large enough mn , reusing the labelled data does not necessarily help to improve the generalization performance. Moreover, when m = 100, the upper bound is higher than that for m = 1000, which coincides with the intuition that increasing the number of unlabelled data helps to reduce the generalization error.

heading: 5 EXPERIMENTAL RESULTS

text:
In Sections 3 and 4, we theoretically analyse the upper bound of generalization error across the iterations for iterative self-training and especially for the case of bGMM classification. In this section, we conduct experiments on real datasets to demonstrate that our theoretical results on the bGMM example can also reflect the training dynamics on complicated tasks.
We train deep neural networks via a iterative self-learning strategy (under the same setting as that for Corollary 3) to perform binary and multi-class classification tasks. In the first iteration, we only use the labelled data to optimize the deep neural network (DNN) and train the model for a relatively large number of epochs so that the training loss will converge to a small value and the model is initialized well. In the following iterations, we first sample a subset of unlabelled data from the whole set and generate pseudo-labels for them via the model trained in the previous iteration. Then, we update the model for a small number of epochs with both the labelled and pseudo-labelled data.
Experimental settings: For binary classification, we collect pairs of classes of images, i.e., “automobile” and “truck”, “horse” and “ship”, from the CIFAR10 (Krizhevsky, 2009) dataset. In this dataset, each class has 5000 images for training and 1000 images for testing. We use the whole set of images in the selected pair of categories and divide them into two sets, i.e., the labelled training set with 500 images and the unlabelled training set with 9500 images. We train a convolutional neural network, ResNet-10 (He et al., 2016), to minimize the cross-entropy loss via the self-learning strategy to perform the binary classification. The model is trained for 100 epochs in the first iteration and 20 epochs in the following iterations; we use the Adam (Kingma & Ba, 2015) optimizer with a learning rate of 0.001. In each iteration after the initial one, we sample 2500 unlabelled images assign them pseudo-labels. The complete training procedure lasts for 100 self-training iterations.
We further validate our theoretical contributions on a multi-class classification problem in which we train a ResNet-6 model with the cross-entropy loss to perform 10-class handwritten digits classification on the MNIST (LeCun et al., 1998) dataset. We sample 51000 images from the training set, which contains 6000 images for each of the ten classes. We divide them into two sets, i.e., a labelled training set with 1000 images and an unlabelled set with 50000 images. The optimizer and training iterations follow those in the aforementioned binary classification tasks.
Experimental observations: We perform each experiment 3 times and report the average test and training (cross entropy) losses, the generalization error, and test and training accuracies in Figures 7– 9. The generalization error appears to have relatively large reduction in the early training iterations and then fluctuates around a constant value afterwards. For example, in Figure 7, the generalization error converges to around 0.25 after 30 iterations; in Figure 8, it converges to around 0.4 after 10 iterations; in Figure 9, it converges to around 0.1 after 12 iterations. These results corroborate the theoretical and empirical analyses in the bGMM case, which again verifies the validity of the proposed generalization error bound in Theorem 2 and Corollary 3 on benchmark datasets. It also reveals that the generalization performance of iterative self-training on real datasets from relatively distinguishable classes can be quickly improved with the help of unlabelled data. We also show that the test accuracy increases with the iterations and has significant improvement compared to the initial iteration when only labelled data are used. In Figure 7, the highest accuracy has about a 4% increase from the initial point; in Figure 8, there is about a 10% increase; and in Figure 9, there is about a 3% increase. Thus, these numerical results suggest that via iterative self-training with pseudo-labelling, not only can we improve the generalization error as the iteration count increases, but we can also enhance the test accuracy. In addition, apart from the “horse-ship” and “automobiletruck” pairs (that are relatively easy to distinguish based on the high classification accuracy and low loss as shown in Figures 7 and 8), we also perform another experiment (detailed in Appendix F) on a harder-to-distinguish pair, “cat” and “dog” (see Table 1), whose results show that the generalization error does not decrease with the iterations even though the classification accuracy increases. This again corroborates the results in Figure 6(d) for the bGMM with large variance.

title: Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning