# Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning

**Anonymous authors**
Paper under double-blind review

ABSTRACT

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 prin-_
ciples. 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.

1 INTRODUCTION

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. 1918

**Theorem [Informal] For a d-variate binary Gaussian mixture model** 17
_(bGMM) in which each component has variance σ[2], the generalization_ 16
_error across the different semi-supervised training iterations_ gent _can_ 1514
_|_ _|_
_be bounded with high probability as follows:_ 13


_|gent| / const · E_ _Gσ(Fσ[(][t][−][1)](↵))_

h[q]


19

18

17

16

15

14

13

0 2 4 6 8 10


(1)


**Figure 1: Upper bound on**

gent as a function of t.
_|_ _|_


-----

_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.

2 PROBLEM SETUP

Let the instance space be Z = X ⇥Y ⇢ R[d][+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)}i[n]=1_ [drawn from][ Z][, where each][ Z][i][ = (][X][i][, Y][i][)][ is independently and identically distributed]

(i.i.d.) fromof features and PZ Y =i is a label indicating the class to which PX,Y 2 P(Z) and Xi is i.i.d. from PX X 2 Pi belongs. However, in many real-life(X ). For any i 2 [n], Xi is a vector
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 = {X1[0] _[, . . ., X]⌧m[0]_ _[}][, ⌧]_ _[2][ N][, where each][ X]i[0]_ [is i.i.d. generated from][ P][X][ 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
_Sintol are first used to learn an initial model parameter ⌧_ disjoint equal-size sub-datasets {Su,k}k[⌧] =1[, where] ✓0 2 ⇥[ S]. Next, we split the unlabelled dataset[u][,k][ =][ {][X]([0]k−1)m+1[, . . ., X]km[0] _[}][. In each] Su_

subsequent round t [1 : ⌧ ], based on ✓t 1 trained from the previous round, we use a predictor
_2_ _−_
_f✓t−1 : X 7! Y to assign a pseudo-label_ _Y[ˆ]i[0]_ [to the unlabelled sample][ X]i[0] [for all][ i][ 2][ [(][t][ −] [1)][m][ + 1 :]

_tm] := {(t−1)m, (t−1)m+1, . . ., tm}. Let_ _S[ˆ]u,t = {(Xi[0][,][ ˆ]Yi[0][)][}]i[tm]=(t−1)m+1_ [denote the][ t][th][ pseudo-]

labelled 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.

**Figure 2: Paradigm of iterative self-training with pseudo-labelling in SSL.**

Under the setup of iterative SSL, during each iteration t, our goal is to find a model parameter ✓t ⇥
that minimizes the population risk with respect to the underlying data distribution _2_

_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_ ⇥, the empirical risk of the labelled data is defined as
_2_ _n_

_LSl_ (✓t) := [1] _l(✓t, Zi),_ (3)

X


_i=1_


-----

and for t ≥ 1, the empirical risk of pseudo-labelled data _S[ˆ]u,t as_

_tm_

_L ˆSu,t_ [(][✓][t][) := 1]m _l(✓t, (Xi[0][,][ ˆ]Yi[0][))][.]_ (4)

_i=(t−X1)m+1_

We set L ˆSu,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 L ˆSu,t [(][✓][t][)][:]

_LSl, ˆSu,t_ [(][✓][t][) :=][ wL][S][l] [(][✓][t][) + (1][ −] _[w][)][L][ ˆ]Su,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}k[t] =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}k[t]_ =0[,][ {][f][✓]k _[}][t]k[−]=0[1]_ [) :=][ E][[][L][P][Z] [(][✓][t][)][ −] _[L]Sl,S[ˆ]u,t_ [(][✓][t][)]] (6)


E✓t [EZ[l(✓t, Z) _✓t]]_
_|_ _−_ _n[1]_


E✓t,Zi [l(✓t, Zi)]


= w


_i=1_


_tm_


E✓t [EZ[l(✓t, Z) _✓t]]_
_|_ _−_ _m[1]_


+ (1 − _w)_ E✓t [EZ[l(✓t, Z) | ✓t]] − _m[1]_ E✓t,Xi0[,][ ˆ]Yi[0] [[][l][(][✓][t][,][ (][X]i[0][,][ ˆ]Yi[0][))]] _._ (7)

✓ _i=(t_ 1)m+1 ◆

_−X_

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?


+ (1 − _w)_


3 PRELIMINARIES

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 infor-_
mation (Negrea et al., 2019; Haghifam et al., 2020) between X and Y given U as IU (X; Y ) :=
_D(PX,Y_ _U_ _PX_ _U_ _PY_ _U_ ), and the disintegrated KL-divergence between PX and PY given U as
_|_ _k_ _|_ _⌦_ _|_
_DU_ (PX _PY ) := D(PX_ _U_ _PY_ _U_ ). These are σ(U )-measurable random variables. It follows imme_k_ _|_ _k_ _|_
_diately that the conditional mutual information I(X; Y |U_ ) = EU [IU (X; Y )] and the conditional
_KL-divergence D(PX_ _U_ _PY_ _U_ _PU_ ) = EU [DU (PX _PY )]._
_|_ _k_ _|_ _|_ _k_

Let ✓[(][t][)] = (✓0, . . ., ✓t) for any t [0 : ⌧ ]. In iterative SSL, we can upper bound the generalization
_2_
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 : ⌧_ ],

_n_

gent(PZ, PX _, {P✓k|Sl,Su}k[t]_ =0[,][ {][f][✓]k _[}][t]k[−]=0[1]_ [)] __ _[w]n_ E✓(t−1) 2R[2]I✓(t−1) (✓t; Zi)

_i=1_

' _tm_ ' X hp i
' '

+ [1][ −]m[w] E✓(t−1) 2R[2][)]I✓(t−1) (✓t; Xi[0][,][ ˆ]Yi[0][) +][ D]✓[(][t][−][1)] [(][P]Xi[0][,][ ˆ]Yi[0] _._ (8)

_i=(t_ 1)m+1 _[k][P][Z][)]_
_−X_ hq -  [i]


-----

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 PXi0[,][ ˆ]Yi[0] [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; Xi[0][,][ ˆ]Yi[0][)][ 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)_ (PXi0[,][ ˆ]Yi[0]

precisely in Remark 1 in Section 4.[k][P][Z][)][ and this term does not necessarily vanish as][ n, m][ ! 1][. We quantify this]

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.

4 MAIN RESULTS

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 R[d] 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) =_ [1]2 [, and]

**X|Y ⇠N** (Y µ, σ[2]Id), 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 Br[y] [:=][ {][x][ 2][ R][d][ :][ k][x][ −] _[y][µ][k][1]_ _[]_ _[r][}][, we see that]_

Pr(X _r_ [) =] 1 2Φ =: 1 _δr,d,_ (9)
_2 B[Y]_ _−_ _−_ _σ[r]_ _−_

✓ ⇣ ⌘[◆][d]

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µ = 12 _[N]_ [(][µ][, σ][2][I][d][) +]

1
2 _[N]_ [(][−][µ][, σ][2][I][d][)][. In the unlabelled dataset][ S][u][, each][ X]i[0] [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 ✓, σ[2]Id) ⌦ _PY . Let the loss function be the negative log-likelihood, which can be expressed as_

1 1

_l(✓, (x, y)) =_ log _PY (y)p✓(x_ _y)_ = log (10)
_−_ _|_ _−_ 2 (2⇡)[d]σ[d][ +] 2σ[2][ (][x][ −] _[y][✓][)][>][(][x][ −]_ _[y][✓][)][.]_

The minimizer of min✓2)⇥ E(X,Y )⇠N (Y* µ,σ2Id)⌦PY [pl(✓, (X, Y ))] is equal to µ. To show that ✓ is
bounded with high probability, define the set ⇥µ,c := **_✓_** ⇥: **_✓_** **_µ_** _c_ for some c > 0.
For any ✓ ⇥µ,c, we have _{_ _2_ _k_ _−_ _k1 _ _}_
_2_


1

and (11)
(2⇡)[d]σ[d][ =:][ c][1][,]

1

=: c2. (12)

(2⇡)[d]σ[d][ +][ d][(][c]2[ +]σ[2][ r][)][2]


min

(x,y) _[l][(][✓][,][ (][x][, y][)) =][ −]_ [log]
_2Z_

max

**x** _r_ _[,y][2Y][ l][(][✓][,][ (][x][, y][))][ −]_ [log]
_2B[y]_


-----

For any (X, Y ) from the bGMM(µ, σ) and any ✓ ⇥µ,c, the probability that l(✓, (X, Y )) belongs
_2_
to the interval [c1, c2] (c1, c2 depend on δr,d) can be lower bounded by


1 _δr,d._ (13)
_≥_ _−_


Pr


_l(✓, (X, Y ))_ [c1, c2]
_2_

)


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 µ, σ[2]Id) ⌦ _PY for all ✓_ _2 ⇥µ,c, i.e., for all λ 2 R,_

_λ2(c2_ _c1)2_

EX,Y exp _λ_ _l(✓, (X, Y ))_ EX,Y [l(✓, (X, Y ))] exp _−_ _._ (14)

_−_ __ 8

✓ ◆

⇥ ) ) **⇤

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]


(Xi _Yi✓)[>](Xi_ _Yi✓),_ (15)

_i=1_ _−_ _−_

X


_l(✓, (Xi, Yi))_

_i=1_

X


2σ[2]n


where


c
= means that both sides differ by a constant independent of ✓, we obtain the minimizer


**_✓0 = arg min_** _LSl_ (✓) = [1]

**_✓2⇥_** _n_


_YiXi._ (16)


_i=1_



-  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 X[0]i[, that is,][ ˆ]Yi[0] [=][ f][✓]t−1 [(][X][0]i[) = sgn(][✓]t[>]−1[X][0]i[)][.]

-  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_


_tm_

_i=(t−X1)m+1_


_tm_

_i=(t−X1)m+1(X[0]i_ _[−]_ _Y[ˆ]i[0][✓][)][>][(][X]i[0]_ _[−]_ _Y[ˆ]i[0][✓][)][,][ (17)]_

_tm_


_L ˆSu,t_ [(][✓][)= 1]

_m_


_l(✓, (X[0]i[,][ ˆ]Yi[0][))]_


2σ[2]m


we obtain the new model parameter


_tm_

_i=(t−X1)m+1_


**_✓t = [1]_**


_Yˆi[0][X]i[0]_ [= 1]m


sgn(✓t[>] 1[X][0]i[)][X][0]i[.] (18)

_−_


_i=(t−1)m+1_


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 (µ, _[σ]n[2]_ **[I][d][)][ and inspired by Oymak & Gulcu (2021), we can decompose][ ✓][0][ as]**

**_✓0 = (1+_** _p[σ]n_ _⇠0)µ+_ _p[σ]n_ **_µ[?], where ⇠0_** (0, 1), µ[?] (0, Id **_µµ[>]), and µ[?]_** is perpendicular
_⇠N_ _⇠N_ _−_

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) := _kahka2,kbbik2_ [in][ [][−][1][,][ 1]][. The correlation]

between the estimated parameter ✓0 and true parameter µ is given by


1 + _pσn_ _⇠0_

(1 + _pσn_ _⇠0)[2]_ + _[σ]n[2]_ 2

_[k][µ][?][k][2]_


_↵(⇠0, µ[?]) := ⇢(✓0, µ) =_


(19)


Let β(⇠0, µ[?]) = 1 _↵(⇠0, µ[?])[2]. We abbreviate ↵(⇠0, µ[?]) and β(⇠0, µ[?]) to ↵_ and β respec
_−_

tively in the following. We can decompose the normalized vectorp **_✓0/k✓0k2 as follows_**

**_✓¯0 :=_** **_✓0_** = ↵µ + βυ, (20)

**_✓0_** 2
_k_ _k_


-----

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 distribu_tion after the first iteration Gσ : [−1, 1] ⇥_ R ⇥ R[d] _! [0, 1) as_

_↵_ _↵_

_Gσ(↵, ⇠0, µ[?]):=_ _D✓Φ⇣_ _−σ_ ⌘pg˜+ [2]σ[↵] _[|]g[˜]_ _[−]σ[↵]_ _[⌦]_ _[p]g[˜][?]+ ✓[¯]0[?]_ [+ Φ]⇣ _σ_ ⌘pg˜|g˜ _[↵]σ_ _[⌦]_ _[p]g[˜][?]_ /pg˜ _[⌦]_ _[p]g˜[?]_ ◆, (21)

/

whereNote that ˜g ⇠N pg˜+ [2]σ(0[↵] _[|],g[˜] 1)_ _[−],σ ˜[↵]g[?]is the Gaussian probability density function with mean⇠N_ (0, Id − **_✓[¯]0✓[¯]0[>][)][,][ ˜]g[?]_** is independent of ˜g and perpendicular to/[2]σ[↵] [and variance]✓[¯][ 1]0.

_truncated to the interval (−1, −_ _[↵]σ_ [)][, and similarly for][ p]g[˜]|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:


_−_ 2[1]
!


2σ[2] x(1⇡−x[2]) exp(− _σ[x][2][2][ )]_ 2

1 − 2Q _σ_ + _p[2][σx]2⇡_ [exp(][−] 2[x]σ[2][2][ )]

) -  - 


(22)


_Fσ(x) :=_

1 1

10[0]

0.5 0.5

0 0 10[-10]

-0.5 -0.5

10[-20]

-1 -1

-1 -0.5 0 0.5 1 -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 +


**Figure 4: Fσ(x) versus x for**

_σ = 0.3 and 0.5._


**Figure 5: Gσ(↵) versus ↵** for

different σ.


The t[th] 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_


(c2 _c1)[2]d_ _n_

gen0(PZ, PX, P✓0 _Sl,Su_ ) _−_ log (23)
_|_ __ 4 _n_ 1 _[.]_

r _−_

' '

_For each t_ [1 : ⌧ ], for' _m large enough, with probability at least'_ 1 _δ,_
_2_ _−_

gent(PZ, PX, _P✓k_ _Sl,Su_ _k=0[,][ {][f][✓]k_ _[}][t]k[−]=0[1]_ [)]
_{_ _|_ _}[t]_
' (c2 _c1)[2]_ '
' _−_ E⇠0,µ? _Gσ_ _Fσ[(][t][−][1)](↵('⇠0, µ[?])), ⇠0, µ[?][*]_ + ✏ _._ (24)

__ 2

r q 4

)

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


-----

200 40 19 3.5 1

18 5 3 0.8

150 30 17 4 2.5

100 20 16 3 2 0.6

50 10 1514 21 1.50.51 0.40.2

00 20 40 60 80 100 00 20 40 60 80 100 130 5 10 15 200 00 5 10 15 200


(a) σ = 0.3


(b) σ = 0.7


(c) n = 10, σ = 0.6. Empir
ical simulation with d = 50.


(d) n = 20, σ = 3


**Figure 6: (a) and (b): Upper bounds for generalization error at t = 0 and t = 1 under different σ when d = 2**

and µ = (1, 0). (c) and (d): The comparison between the upper bound for gent and the empirical
_|_ _|_

generalization error at each iteration t. The upper bounds are both for d = 2.

_↵_ _≥_ _↵0 = ↵0(σ1, σ2), Gσ1_ (↵) > Gσ2 (↵). From (19), we can see that ↵ is close to 1 of high
probability, which means that σ _Gσ(↵) is monotonically increasing in σ with high probability._
_7!_
As a result, E↵[ _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,

p

_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.estimator converges to the optimal classifier for this bGMM. However, since there is no margin As n ! 1, ✓0 ! µ and ↵** = ⇢(✓0, µ) ! 1 almost surely, which means that the
_between two groups of data samples, the error probabilityis the Bayes error rate) and the disintegrated KL-divergence Pr( DY[ˆ]⇠j[0]0,µ[6][=]?[ Y](P[ 0]j_ **X[)][ !]0j** _[,][ ˆ]Yj[ Q(1][0]_ _[/σ][)][ >][ 0][ (which]_

_estimated and underlying distributions cannot converge to 0. We discuss the other extreme case in[k][P][X][,Y][ )][ between the]_
_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 Fig_!_ _|_ _|_ _|_ _|_
ures 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

_↵_ = 1 2 [+][ o] _._ (25)
_−_ 2[σ]n[2] _[k][µ][?][k][2]_ _n_

✓ ◆

It can be seen that as n increases, ↵ converges to 1 in probability. Suppose the dimension d = 2
andgeneralization error at µ = (1, 0). Then t µ = 1[?] can be rewritten as= [0, µ[?]2 []][ where][ µ]2[?] _[⇠N]_ [(0][,][ 1)][. The upper bound for the absolute]

(c2 _c1)[2]_ _[p]2_ _pn_

_|gen1| /_ r _−2_ Z−p2 _p⇡σ e[−]_ _[ny]σ[2][2][ p]Gσ(1 −_ _y[2]) 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 = _n+nm_ [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:
_−_ _!_ _−_

_p1_ _x[2]_ 2 _−_ 2[1]

_F˜σ,⇠0,µ?_ (x) = 01 + _w(1 +)pwσn[σ]⇠[k]0[µ]n) + (1[?][k][2]_ + (1 − _w −)(1w −)(_ [2]2Q[σ]p2− x⇡σ +exp(p[2][σx]2⇡−[exp(]2[x]σ[2][2][ )][−]* 2[x]σ[2][2][ ))] 2 1 _._ (27)

**Corollary 3. Fix any@** _σ_ ) R+, d N, ✏ R+ and δ (0, 1)) _. For*_ _m large enough, with probability*_ A
_2_ _2_ _2_ _2_
_at least 1 −_ _δ, the absolute generalization error at any t 2 [1 : ⌧_ ] can be upper bounded as follows

(c2 _c1)[2]d_ _n_

gent(PZ, PX, _P✓k_ _Sl,Su_ _k=0[,][ {][f][✓]k_ _[}][t]k[−]=0[1]_ [)] _w_ _−_ log
_{_ _|_ _}[t]_ __ 4 _n_ 1

r _−_

' '
' + (1 − _w)_ (c2 −2 _c1)[2]_ E⇠0,µ? _Gσ_ ' ˜Fσ,⇠[(][t][−]0[1)],µ[?] [(][↵][(][⇠][0][,][ µ][?][))][, ⇠][0][,][ µ][?][*] + ✏ _._ (28)

r q 4

)

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 _[m]n_ [, 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.

5 EXPERIMENTAL RESULTS

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., “au
tomobile” 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.


**Figure 7: Binary classification on**

the “horse” and “ship” classes from

the CIFAR10 dataset.


**Figure 8: Binary classification on**

the “automobile” and “truck”

classes from the CIFAR10 dataset.


**Figure 9: 10-class classification on**

the MNIST handwritten digits

dataset.


-----

REFERENCES

St´ephane Boucheron, Olivier Bousquet, and G´abor Lugosi. Theory of classification: A survey of

some recent advances. ESAIM: Probability and Statistics, 9:323–375, 2005.

St´ephane Boucheron, G´abor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp
_totic Theory of Independence. Oxford University Press, 2013._

Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information based

bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1):
121–130, 2020.

Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced

datasets with label-distribution-aware margin loss. In Proceedings of the 33rd International Con_ference on Neural Information Processing Systems, pp. 1567–1578, 2019._

Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data

improves adversarial robustness. In Proceedings of the 33rd International Conference on Neural
_Information Processing Systems, pp. 11192–11203, 2019._

Olivier Chapelle, Bernhard Schlkopf, and Alexander Zien (eds.). _Semi-Supervised Learning._

[The MIT Press, 2006. ISBN 9780262033589. URL http://dblp.uni-trier.de/db/](http://dblp.uni-trier.de/db/books/collections/CSZ2006.html)
[books/collections/CSZ2006.html.](http://dblp.uni-trier.de/db/books/collections/CSZ2006.html)

Nitesh V Chawla and Grigoris Karakoulas. Learning from labeled and unlabeled data: An empirical

study across techniques and domains. Journal of Artificial Intelligence Research, 23:331–366,
2005.

Robert Dupre, Jiri Fajtl, Vasileios Argyriou, and Paolo Remagnino. Improving dataset volumes

and model accuracy with semi-supervised iterative self-learning. IEEE Transactions on Image
_Processing, 29:4337–4348, 2019._

Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via

R´enyi-, f -divergences and maximal leakage. IEEE Transactions on Information Theory, 67(8):

4986–5004, 2021. doi: 10.1109/TIT.2021.3085190.

Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite.

Sharpened generalization bounds based on conditional mutual information and an application to
noisy, iterative algorithms. Advances in Neural Information Processing Systems, 33:9925–9935,
2020.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog
nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
770–778, 2016.

Sharu Theresa Jose and Osvaldo Simeone. Information-theoretic bounds on transfer generalization

gap based on Jensen-Shannon divergence. arXiv preprint arXiv:2010.09484, 2020.

Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua

Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR
_[2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:](http://arxiv.org/abs/1412.6980)_
[//arxiv.org/abs/1412.6980.](http://arxiv.org/abs/1412.6980)

A Krizhevsky. Learning multiple layers of features from tiny images. Master’s thesis, University of

_Toronto, 2009._

Yann LeCun, L´eon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to

document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.

Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for

deep neural networks. In Workshop on Challenges in Representation Learning, ICML, volume 3,
pp. 896, 2013.


-----

Jian Li, Yong Liu, Rong Yin, and Weiping Wang. Multi-class learning using unlabeled samples:

Theory and algorithm. In IJCAI, pp. 2880–2886, 2019.

Adrian Tovar Lopez and Varun Jog. Generalization error bounds using wasserstein distances. In

_2018 IEEE Information Theory Workshop (ITW), pp. 1–5. IEEE, 2018._

David McAllester and Karl Stratos. Formal limitations on the measurement of mutual information.

In International Conference on Artificial Intelligence and Statistics, pp. 875–884. PMLR, 2020.

Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy.

Information-theoretic generalization bounds for SGLD via data-dependent estimates. In Advances
_in Neural Information Processing Systems, pp. 11013–11023, 2019._

XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. Estimating divergence functionals

and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory,
56(11):5847–5861, 2010.

Samet Oymak and Talha Cihad Gulcu. A theoretical characterization of semi-supervised learning

with self-training for gaussian mixture models. In International Conference on Artificial Intelli_gence and Statistics, pp. 3601–3609. PMLR, 2021._

Liam Paninski. Estimation of entropy and mutual information. Neural Computation, 15(6):1191–

1253, 2003.

Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algo
rithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546–550. IEEE,
2018.

Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory.

In Artificial Intelligence and Statistics, pp. 1232–1240, 2016.

Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn’t. Advances

_in Neural Information Processing Systems, 21:1513–1520, 2008._

Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual

information. In Conference on Learning Theory, pp. 3437–3452. PMLR, 2020.

Isaac Triguero, Salvador Garc´ıa, and Francisco Herrera. Self-labeled techniques for semi-supervised

learning: taxonomy, software and empirical study. Knowledge and Information Systems, 42(2):
245–284, 2015.

Jesper E Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine Learn
_ing, 109(2):373–440, 2020._

V. Vapnik. The Nature of Statistical Learning Theory. Springer, 2000.

Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Sci
_ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press,_
2018. doi: 10.1017/9781108231596.

Xuetong Wu, Jonathan H Manton, Uwe Aickelin, and Jingge Zhu. Information-theoretic analysis

for transfer learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pp.
2819–2824. IEEE, 2020.

Aolin Xu and Maxim Raginsky. Information-theoretic analysis of generalization capability of learn
ing algorithms. In Advances in Neural Information Processing Systems, pp. 2524–2533, 2017.

Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Synthesis Lectures

_on Artificial Intelligence and Machine Learning, 3(1):1–130, 2009._

Xiaojin Jerry Zhu. Semi-supervised learning literature survey. 2008.


-----

