Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning
Authors: Haiyun He
Hanshu YAN
Vincent Tan
Venue: ICLR 2022 Submitted (2022)
Keywords: Generalization error
Information theory
Semi-supervised learning

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 {\em 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.

Under review as a conference paper at ICLR 2022
Information-Theeretic intoniiiationn 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- theooreti prin- ciples. To obtain bounds that are amenable to numerical evaluation, we first work with a simple model namelln the binary Gaussian mixture model. Our theoreti- cal results suggest that when the class conditional variances not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates. The theoretical results 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.
INTRODUCTION
In real-life machine learning applications, it is relatively easy and cheap to obtain large amounts of unlabelled data, while the number labelled data examples is usually small due the high cost of annotating them with true labels. In light of this, semi- supervise 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 classifiers. Among the plethora of SSL methods, greudo-labelling (Lee al., 2013) has been observed to be simple and efficient way to improve the generalization performance empirically. In this paper, we consider the problem of aseudo-labellimg 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 understand the impact of pseudo-labelling on the generalization error.
A learning algorithm can be viewed as randomized map from the training dataset to the output model parameter. The output is highly data-dependent and may suffer from overfitting 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 which the algorithms overfit the training data. In SSL problems, the unlabelled data are expected to improve the generalization performance certain manner and thus, it worthwhile to investigate the behaviour theoretically. In this paper, we leverage results in Bu et al. (2020); Wu et al. (2020) to derive an information- theoretic generalization error bound at each iteration for iterative SSL.
We state main theoretical contribution informally as follows.
Theorem [Informa]] For a d-variate binary Gaussian mixture model (bGMM) in which each component has variance o², the generalization error across the different semi semi-super supervised training iterations Igen,) can be bounded with high probability follows:
Dree boed
Igen,1 S const E
(1) Figure 1: Upper bound
Igen, function of t.

---

Under review as a conference paper at ICLR 2022
where a represents the correlation between the optimal and estimated parameter vectors, Fe the iteraled composition of the function Fo (sketched in Figure D. and G. (sketched in Figure 5 represents the KL-divergence between the pseudo labelled and true data distributions.
As shown in Figure D the upper bound is monotonically decreasing in the iteration count t and converges at around 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 eтror across iterations The behaviour of the empirical generalization eπтоr for the bGMM coincides with the upper bound. The results suggest that the proposed upper bound serves as useful guide to understand how the generalization error changes across the suprrispe 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 lasulo-labelling iterations and saturates thereafter. For a more extensive literature review, please refer to Appendix A
with a sufficiently large amount of unlabelled data. In Section $ we also
2 PROBLEM SETUP
Let the instance space be 2 X x C Rd+1, the model parameter space be θ and the loss fucntion be : 2 x ④ + R, where d E N. We are given labelled training dataset S [Z,...., Zn, ((X,,))) drawn from 2, where each Z, = (X, ;, Y.) is independently and identically distributed (i.i.d.) from Pz - Px, E P(2) and X; is i.i.d. from Px E P(X). For any i [nl]. X; is vector of features and Y; is a label indicating the class to which X; belongs. However, in many real-life machine learning applications, we only have a limited number of labelled data while we have access to 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 remi-supervised learning (SSL). We are given an independent unlabelled training dataset S., = (X), X,m,, E N, where each X is i.i.d. generated from Px E P(X). Typically, >> n.
In the following. we consider the iterative self-training with pseudo-labelling
SSL setup, as shown in Figure 2 Let / [0: T] denote the iteration counter. In the initial round (I = 0), the labelled data Sj are first used to learn an initial model parameter 0g E O. Next, we split the unlabelled dataset S. into disjoint equal-size sub-datasets {S,,,)T=11 where S
(1 X% km In each subsequent round & E [1 T). based on 0,-1 trained from the previous round, we use a predictor fo... X + y to assign a pseudo-label V to the unlabelled sample X for all E [(t - 1)m + 1 tm] = (t- (t- 1-m-1mm+-- + L...., tm.]. Let S.,, {X}, fm (tt denote the t pseudo- labelled dataset. After
both the labelled data S and the pseudo-labelled data Su,t are used to learn new model parameter 0g. The procedure then repeated iteratively until the maximum number of iterations 7 is reached.
(X,, Y)
(X,, P.m
O
am
0g
(X))
(X))
(X) (aa)
Figure 2: Paradigm of iterative self-training with pseudo-lahelling in SSL..
Under the setup of iterative SSL, during each iteration t, our goal is to find a model parameter 9, E θ that minimizes the population risk with respect to the underfying data distribution
Lpz (0,) : Ez~ Pz [[(0,, Z)].
(2)
Since Pz is unknown, Lp (0c) cannot be computed directly. Hence, we instead minimize the em- pirical risk. The procedure is termed empirical risk minimization (ERM). For any model parameter 0, E O the empirical risk of the labelled data is defined as
Lg, n
10., 2,),
(3)
2

---

Under review as a conference paper at ICLR 2022
and for t 2 1, the empirical risk of pseudo- data Su,
tm
Ls., (0c) =
I(O,, (X,, K()).
(4)
m
i=(t-))m+t
We set Tss.. (0.) = 0 for For a fixed weight we E [0, 1], the total empirical risk can be defined as the following linear combination of Ls, (0t) and s., (6)):
L...... (0r) == wLs, (0.) + (1- w.. (0.).
(5)
An SSL algorithm can be characterized by a randomized map from the labelled and unlabelled training data S₁, Su to a model parameter & according to a conditional distribution Pajs,.s. Then at each iteration i, we can use the sequence of conditional distributions ( k== with Peols = 1s to represent an iterative SSL algorithm. The generalization error at 1-th iteration is defined as the expected gap between the population risk of O, and the empirical risk on the training data:
gen, (P', Px Poo 1k=oo (fe 31- = B[Lp2(0)) S, (0.)
(6)
1
= - LE, 2) |0:11 Ee, 1((,,, Zill
tm
Bo, (X, (X, 101)
+ (1 - w) Ro, 12 (1(O,, 2) 0:]]
[t-1]]m++
When & = 0 and w = 1, the definition of the generalization error above reduces to that of vanilla supervised learning. The generalization errоr gen, used to measure the extent to which the it- erative 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 gen, evolve as the iteration count increases? Do the unlabelled data examples in S, help to improve the generalization error?
PRELIMINARIES
Inspired by the information-theoreee generalization results in Bu et al. (000 Theorem 1) and Wu ctt al. 2020) Theorem 1), we derive an upper bound on the generalization error gen, for any e 10 terms of the mutual information between input data samples (either labelled or pseudo- labelled) and the output model parameter 0,, as well as the KL--divergence between the underlying data distributions and the joint distribution of feature vectors and pseudo-labels.
We denote an Desub-Gaussian random variable L E R [Vershynin] 2018) as L ~ subG(Rt. Fur- thermore, 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 ly (X; := D(Px.yIu & ). and the disintegrated KL-divergence between Px and Py given U as P Py v). These are a (U)) -U)-measurable random variables. It follows imme-
Du ( : ( diately that the conditional mutual information 1(X; (YU) = Ey [y (X:Y)] and the conditional KL-divergence D D(Px (IPpilPPPr (P)) Ev [Du (Px (Px| Py)]]
Let g(+) (fu.....6k) 0t) for any E [0 r]. iterative SSL, we can upper bound the generalization error as shown in Theorem
| to follow by applying the law of total expectation.
Theorem 1 (Generalization error upper bound for iterative SSL). Suppose 1(0, Z) subG(R) under Z ~ Pz for all 0 E O, then for any t E [0:
gen, (Pz, Px, (Po, Ss.s (fr
<
w
Ep ( (113
==1
w
22 1 (0,; X/. V!) + Doce 1 (Pxx.x:1122))
Egc
(8)
(t-11)mm 1)m+1
3

---

Under review as a conference paper at ICLR 2022
The proof of Theorem is provided in Appendix B in which we provide 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 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 D the mutual information between the individual input data sample Z; and the output model parameter O, measures the extent to which the algorithm is sensitive to the input data, and the KL-divergence between the underlying Pz and pseudo-labelled labelled distribution Px;X; measures how well the algorithm generalizes to the true data distribution. As + oo and + co, show that the disintegrated mutual information 1 (8,; X Y?) 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 Decc-n)
(1 and this term does not necessarily vanish as m + Do. We quantify this 8 x
precisely in Remark I iin Section 1
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 quantities on the output model parameters g(t-1) = {O...... (0.... from previous iterations, we 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 to derive tractable upper bound on the general- ization error as a function of iteration number that we can compute numerically.
the information-theoree
MAIN RESULTS
We now particularize the iterative seme-super classification setup the bGMM. We calculate the term in (8) to understand the effect of multiple self-training rounds on the generalization error.
Fix unit vector fe E Idd and scalar E R__ (0, o2). Under the bGMM with mean μa and standard deviation a (bGMM(J4, o)). we assume that the distribution of any labelled data example (1) 2. and X|Y N μr, La),), where L is the identity matrix of size d d. In anticipation of leveraging Theorem ! together with the sub- aab-Gaussianity of the loss function for the bGMM to derive gener- alization bounds in terms of information-tee -thorrrtttttttttcctcec quantities (just as in Russo & Zou (016); Xu & Raginsky (017)); Bu et al. (2020)) we find it convenient to show that X and (X, (). are bounded w.h.p.. By defining the Lox ball By- == {x E Red
(X,Y) is specified follows. Let ) [1], Y Py, where py (-
||x y/lll I r), we see that d
Pr(X E B - [ (1-20 24 (11-2(--)) +)
=: 1 -rrdd
(9)
where ((-) is the Gaussian cumulative distribution function. By choosing appropriately, the failure probability d,.d can be made arbitrarily small.
The random vector X is distributed according to the mixture distribution pn = N Ta) + WW(-,,
u4, (..). In the unlabelled dataset S., each X for i E [1 rm] is drawn i.i.d. from PH.
For any O E θ under the bGMM(0, σ). the joint distribution of any pair of (X E Z given by NY 0, o² ILI,) & Py. Let the loss function be the negative log-likelhood, which can be expressed as
1(0, (x, v))
log (v)
- log 2 (2 yod 20 (x y0) (x -y)) (10)
The minimizer of minøge (xx.))-N(Y [10 (X, Y))] is equal to μ. To show that 0 is bounded with high probability, define the set Ou,e == (0 E θ 110 ul/ S c} for some 0. For any 0 E θ jr.e, we have
min 1(0, (x,,)) = - -log 2/ (2 gd (x
C1, and
(11)
1
d(c
max 1(0, (x. (x. - -log xEB".
202 =: C2.
(12)
2 (2T)) 2 dad
4

---

Under review as a conference paper at ICLR 2022
For any (X,Y) from the bGMM(H, o) and any 0 E H... the probability that ((0, (X, belongs to the interval [c1, e2] (C1, 02 depend on 6r,d) can lower bounded by
Pr (X(0,(,)))))))) (X, E [ci, c2l) 2 1 - -
(13)
Thus, according to Hoeffding's ' lemma, with probability at least 1 - Sy,d, 1(0, (X, Y)) subG((e2 ei 3/2)) under (X,Y) ~ NYY μr, La) & Py for all E O i.e., for all A E R
A (2 c1
E [exp (A(1(O, (x, Y)) - Ex,y|((0, (X, (X,Y)) S exp
(14)
Under this setup, the iterative SSL procedure is shown in Figure 2 but the labelled dataset Sj is only used train in the initial round 0; we discuss the use of S in all iterations Corollary The algorithm operates in the following steps.
Step Initial round t with Si: By minimizing the empirical risk of labelled dataset S
n
(0)
Σ 100 (X, Y.)) -
X --,0 (X, Y,)),
(15)
202n i=1
where C means that both sides differ by constant independent of 0, we obtain the minimizer
1 Y;X,
On = arg min Ls, (0)
(16)
AEO
n2
Step 2: Pseudo-label data in S. At each iteration
7]. for any E [(1 1)m 1: Lm].
we use 0 to assign a pseudo-label for X that is, V fo._, (x)) ,gn(0,_,,)).
Step 3: Refine the model: We then use the pseudo-label labelled dataset Su,t to train the new model. By minimizing the empirical risk of Su.t
tyn
tym Σ
Lg... (A 1)
100 (X, 111)= 20
[ - X ( (X 9(0), (17)
i (t- 1ym+1
we obtain the new model parameter
tm
tm
0.
XX
1
Σ
sgn(0.,
(18)
m 1=(1-
m
1)m+1
i=(1-1)m+1
If t < r, go back to Step 2.
To state our result succinctly, we first define some non- standard notations and functions. From (6).
we know that Og ~ N(u, eaIa) and inspired by Oymak & Gulcu (021)) we can decompose Og as
0g (1+ Eo) Ju where &u (0, 1), μ NoO, I. uu and μ is perpendicular to μ and independent of Eo (the details of this decomposition are provided in Appendix C).
Given two vectors (a, b), define their correlation as p(a, b) = (a.b) a in [-1, The correlation
between the estimated parameter On and true parameter is given by
+ vn Eo
a(Eo, μ p000 11)
(19)
V(++ 3n 60)2
We abbreviate a(Ev, ) and B(Eo, 4 to and B respec- tively in the following. We can decompose the normalized vector 0 /lolllull as follows
Let ((500.1 V1- alLo, 1.2
0o
0
|0012 afe 30,
(20)
5

---

Under review as a conference paper at ICLR 2022
where pe / 11.. Let Ouj (2 2a:Bu)/o, which is vector perpendicular to 0u-
Define the KL KL-divereence between the aseudo-labelled data distribution and the true data distribu- tion after the first iteration Go :[-1, R R + [0, 00)
as
Gala, Eo, x )=):
Po+
@ Pg-+ + + Polse & Pg
2 Pg
(21)
(O, 0 g is independent of 9 and perpendicular to Ou- Note that Pa+ 2n lss -- is the Gaussian probability density function with mean 20 and variance truncated to the interval (-oc- - )) and similarly for P In general, when (a Eo, u+) is small, is the generalization error.
where (N 1). g
Let Q(-) ;= (-). Define the correlation evolution function F. |-1,1] 7 [-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 to +11
20 21-x"
exp
(x( = 1
(22)
-1-20- (0-2((#) +
20x exp(
2
10a
0.5
0.
0.1
0.2
0.5
0.5
16
0.7
-1
-0.5
Figure 3: F( (Ir) versus for different when 0.5.
Figure 4: Fo (z) versus for
Figure (a) versus for different ø.
0 = 0.3 and 0.5.
The tth iterate of the function Fg is defined as F == Fg o F( with F: (x) = x. As shown
in Figure for any fixed Ø,
that (() 2 Fo(x)
for
and F!2 (x)
(x( < x for æ < 0. It can also be easily deduced that for any t e [0 7]. F Fftt" (2) (x)
for any 2 0 and ((++1) (z: F( (z) for any x O. This important observation implies that if
the correlation a. defined in 19). is positive, F!!) (a) increases with t; and vice versa. Moreover, as shown in Figure 4 by varying dr,
that smaller a results in a larger FFo (z)
By applying the result in Theorem the following theorem provides an upper bound for the gener- alization error at each iteration for large enough.
Theorem 2. Fix any E R4, d E N, e E R+ and 8 E (0, 1). With probability at least 1 - 8, the absolute generalization error at can be upper bounded as follows
gen Pz, Px. Pools,.s))
[ VV
2d
log
n
(23)
4
For each t [1 r), for m large enough, with probability least 1 - 8.
gen, P2, Px, (Po 1S..s. ( (So. bb=b)
C2 2
[Vo. (
Ex
(a(Eu. μ }), Eor H1 te
(24)
The proof Theorem 2 is provided in Appendix
Several remarks are order.
First, to gain more insight, numerically plot (a, u when d 2 and μ (1, 0) in Figure 5 Under these settings, G, En, μ depends only on a and hence, we can rewrite
G~ (a).
(a) As shown in Figure for all 0 > 02, there exists on E [-1, such that for all

---

Under review as a conference paper at ICLR 2022
Emolroo crnn woooooooon 4TEVE
Upptr bound lom Upper lon.
Oper bound for Upper
12
Gemeralizatin ersrr
50
100
20
2 21
10
(a) 0 0.3
(b) 0 = 0.7
(c) n2 = 10, o = 0.6. Empir- (d) = 20, 0 =
ical simulation with d = 50.
Figure 6: (a) and (b): Upper bounds for generalization error at t = 0 and t 1 under different when d d= and j 0). (c) and (d): The comparison between the upper bound for |gen, and the empirical generalization error each iteration The upper bounds both for d = 2.
2 0g = a0(0 22), Go, (a) > Gayla). From 19 we can see that a is close to 1 of high probability, which means that (a) is monotonically increasing in with high probability. As a result, EE, (a increases as increases. This consistent with the intuition that when the training data has larger variance, it is more difficult to generalize well. Moreover, for a > O, (a) is increasing in t for a > then Go (a)) is
Ga(a) decreases as a increases. Since F! decreasing in f, which implies that the upper bound in 24 is also decreasing in t.
Remark 1. As n + oC, 0o - 4 and a = p(@a. (1) - almost surely, which means that the estimator converges to the optimal classifier for this bGMM. However, since there is margin between groups of data samples, the error probability Pr(Ý; + +Y;) -(1//) 0 (which is the Bayes error rate) and the disintegrated KL-divergence Doo.t (Px,s, between the estimated and underlying distributions cannot converge to O. We discuss the other extreme case in which a -1 in Remark 2 in Appendix C of the supplementary material.
Second, by letting + 0, we compare the upper bounds for |gengl and Igen,l. as shown in Fig- ures ((a) and 6(b) For any fixed a, when n sufficiently small, the upper bound for |gonol is greater than that for ge I- As increases, the upper bound for igen,l surpasses that of |gengl as shown in Figure 6(b) This is consistent with the intuition that when the labelled data is limited, us- ing the unlabelled data can help improve the generalization performance. However, 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 large overlap. This is because the labelled data is already effective in learning the unknown parameter 0g well and additional pseudo-labelled data does not help to further boost the generalization performance. Furthermore, by comparing Fig- ures 6(a) and 6(b) we can see that for smaller a,, the improvement from igengl to |gen, is more pronounced. The intuition 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 general- ization performance. Let examine the effect of n, the number of labelled training samples. By expanding a, defined in 19. using Taylor series, we have
o² 2n
a = 1
+
(25)
It can be seen that as n increases, converges to 1 in probability. Suppose the dimension d 2 and μ = (1. Then μ [0, مم where μu ~ (0, The upper bound for the absolute generalization error at t = 1 can be rewritten
(c2 22
nx² (G, - x2) dy.
gen
(26)
2
no
which is decreasing function of n, shown in Figures ((a) and 6(b)
Third, given any pair of (Co, بمر if a 4x+) > 0, F. (a<Co, -²)) > F!!
for all
t E [1 r). shown in Figure 3 This means that if the quality of the labelled data Si is reasonably good, by using Og which is learned from Sj. the generated pseudo-labels for the unlabelled data largely correct. Then the subsequent parameters 0,,t > learned from the large number of pseudo-labelled data examples can improve the generalization error. Therefore, the upper bound for Igen,/ decreases increases. In Figure b(c) plot the theoretical upper bound in (24 by
7

---

Under review as a conference paper at ICLR 2022
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 Igen,l decreases as t increases and finally converges to a non-zero constant. The gap between the upper bounds for increases and shrinks almost 0 for 2. The intuition is that as m + oo, there are sufficient data at each iteration and the algorithm can converge at very early stage. In the empirical simulation, we let d 50, l (I.0...., 0) and iteratively run the self- self-trainin procedure for 20 iterations and 2000 rounds. We find that the behaviour of the empirical generalization eтror (the red '-x' line) similar to the theoretical upper bound (the blue '-o' line), which almost converges to its final value at /. = 2. This result shows that the theoretical upper bound in 24 serves as useful rule-of-thumb for how the generalization error changes over iterations. In Figure b[d] we plot the theoretical bound and result from the empirical simulation based on the toy example for d = 2 but larger n and a.. This figure shows that when we increase and a, 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 a is larger, the data samples have larger variance and the classes have a larger overlap, and thus, the initial parameter 6, 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.
ggen,] and for [gen decreases
Fourth, we consider an "enhanced" scenario in which the labelled data in SJ are reused in each iteration. Set w ntm in (5) We can extend Theorem 2 to Corollary 3 as follows. Similarly to F,, let us define the enhanced correlation evolution function F Fo
|,,1] + [[1,, as follows:
F Pa.so.u! (x) (1 1+ (w[( + Co) (1 w) -2Q(#) +
(w T ll + (1 w)( I= exp( /25
x² ))
n
20t
(27)
2az v25
exp( 26
Corollary 3. Fix any E R2, dEN, 6 C R2 and 5 E (0, 1). For mn large enough, with probability
at least 5, the ahsolute generalization error at any t [1 r] can be upper bounded as follows
gen, (Pz, (Po, S..S. Nk {foz 1o & WV
(c2 - cd
n log n -1
4
+ (1 +(1-w) w
(c2 - 0 2
Be
(F0-1) Co (G a.Ea.uu (a(5o- (et(oo.-))) )), Eor 1x +c
(28)
The details are provided in Appendix D and the proof of Corollary is provided in Appendix F It can be seen from Figure 11 that the new upper bound for igen,l 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 [[c) which means that for large enough m. 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.
EXPERIMENTAL RESULTS
In Sections B and we theoretically analyse the upper bound of generalization error across the iter- ations 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 B to perform binary and multi-class classification tasks. In the first iteration, we only use the labelled data 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 subset of unlabelled data from the whole set and generate pseudo-labels for them via the model trained in the previous iteration. Then, update the model for small number of epochs with both the labelled and aseudo-labelled data.
8

---

Under review as a conference paper at ICLR 2022
Experimental settings: For binary classification, we collect pairs of classes of images, i..., "au- tomobile" and "truck", "horse" and "ship". from the CIFARIO (Krizheskyy) 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 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 & Bal 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 multi-class classification problem in which we train a ResNet-6 model with the cross-entropy loss to perform 10-class handwritten digits classifi- cation 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... 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- 7 The generalization errоr 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 it converges to around 0.4 after 10 iterations; in Figure g 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 B 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 g there is about a 10% increase; and in Figure / there is about a 3% increase. Thus, these numerical results suggest that via iterative self-training with geeudolabbellnng 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 "automobile- truck" pairs (that are relatively easy to distinguish based on the high classification accuracy and low loss as shown in Figures) 7 and B), we also perform another experiment (detailed in Appendix F) on hander-to-distingiitt pair, "cat" and "dog" (see Table 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 [(d] for the bGMM with large variance.
0.8
0.20
trun Juss
train loss
trua, loss
gea exoor
0.5
geb ozroe
0.15
gra ector
0.2
0.1
0.10
0.2
0.05
0.0
0.5
0.00
20
20
60
70
900
100
90
95
59
(8)
96
Anc
tect_acc
85-
text_ 300 train 800
97-
Inst_acc Erain acc
Erain J012
92
20
30
8D
20
30
40
600
70
10
20
30
310
650
Steratton
Iberation
(teraition
Figure 7: Binary classification on the "horse" and "ship" classes from the CIFAR 10 dataset.
Figure 8: Binary classification on the "automobile" and "truck" classes from the CIFAR 10 dataset.
Figure 9: 10-class classification on the MNIST handwritten digits dataset.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: Probability and Statistics, 9:323-375, 2005.
Stéphane Boucheron, Gábor 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, I(1): 121-130, 2020.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with aabel-distrbuttion-wwar margin loss. In Proceedings of the 33rd International Con- ference on Neural Information Processing Systems, pp. 1567-1578, 2019.
Yair Carmon, Aditi Raghumathan, 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. 1111-112203, 2019.
Olivier Chapelle, Bernhard Schlkopf, and Alexander Zien (eds.). Semi-Supervised Learning. The MIT Press, 2006. ISBN 9780262033589. URL http:///blp uni-trierretrr.. dedbb/
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. IEFE Transactions on Image Processing, 29:4337-4345 2019.
Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via Rényi-, f-divergenees and maximal leakage. IEEE Transactions Information Theory, 67(8): 4986-5004, 2021. doi: 10.1109/TT.22221333888 199.
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. cntematioonthhoreete bounds on transfer generalization gap based on Censen-Shannor divergence. arXiv preprint arXhv: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. URLhttp:
6980
A Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio. and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 96(11):2278-233 1998.
Dong- Hyun Lee al. Pseudo-label: The simple and efficient supi-supe learning method for deep neural networks. Workshop on Challenges in Representation Learning. ICML, volume 3, pp. 896, 2013.
10

---

Under review as a conference paper at ICLR 2022
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- 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 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- 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-Diiensional Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 10.1017/978 108231596.
Xuetong Wu, Jonathan Manton, Uwe Aickelin, and Jingge Zhu. Information -eformation-theoretic analysis for transfer learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pp- 2819-2822 IEFF, 2020.
Aolin Xu and Maxim Raginsky. Information -theoretic analysis of generalization capability of learn- ing algorithms. Advances in Neural Information Processing Systems, pp. 2524-2533, 2017.
Xiaojin Zhu and Andrew 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.
11


Reviews:
[{"review_id": "eWi_IfP89jT", "reviewer": "Reviewer_5JBw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Dear Authors, \n\nPlease find my review below. Sorry for submitting it late. \n\nThe reviewer likes the approach proposed in this paper; however, I would like to express several concerns regarding the theoretical power and limitations of the result. My main concern is about the results' impact and there how do they advance the state-of-the-art.  Please, find below some of the most crucial ones: \n1. Theoretical bounds are based on the KL divergence between the pseudo-labeled and true distributions, which is hard to measure/estimate unless the additional information is specified. Any computable upper bound?\n2. The loss function used for the generalization error computation is designed in such a way that even for a high misclassification rate on later stages the loss function would converge. (See Eq.~ 5 for the details)\n3. No lower bound is provided. Any bound known from the literature?\n4. Figure 1: the upper bound on the generalization error, which should be in between 0 and 1, is about 14 at convergence. Why is it so? A small number of objects? A similar concern regarding Figure 6. \n5. When one is talking about the generalization error, one derives the bound for a class of functions rather than for a single function. However, in the paper \n\nOverall, I believe the paper is interesting, but it can not be accepted as is unless the authors' resolve these comments. ", "summary_of_the_paper": "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\n", "summary_of_the_review": "The results are interesting; however, it is not clear to me how one can extend the results beyond the Gaussian mixture model considered in the paper. Furthermore, it is not clear how to get efficiently computable bounds from the statements of Theorems 1-3. The bounds are needed for model complexity penalization. Also, the following questions are needed to be addressed: \n\n- Theoretical bounds are based on the KL divergence between the pseudo-labeled and true distributions, which is hard to measure/estimate unless the additional information is specified. Any computable upper bound?\n- The loss function used for the generalization error computation is designed in such a way that even for a high misclassification rate on later stages the loss function would converge. (See Eq.~ 5 for the details). Could you advocate using this bound?\n- No lower bound is provided. Any bound known from the literature?\n- Figure 1: the upper bound on the generalization error, which should be in between 0 and 1, is about 14 at convergence. Why is it so? A small number of objects? A similar concern regarding Figure 6.\n- When one is talking about the generalization error, one derives the bound for a class of functions rather than for a single function. However, in the paper", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bXPNE_R0a1e", "reviewer": "Reviewer_8ena", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: The conclusions and observations about generalization error is made in the regime where n -> infinity and m->infinity and m >>n. The analysis seems sound and credible. I did not check the proof in the appendix, but the results and overall proof sketch in the main paper seems reasonable.\nWeakness: While the result is sound and theoretically valuable, it is not surprising at all in the regime studied (m and n large). The paper starts with the motivation that labeled data is limited, and pseudo labeling is shown to be helpful, but studying the regime where we have growing number of labeled samples does not completely intersect with that motivation. Also, the authors mention that after a few iterations, the accuracy might improve, but the generalization error does not, and I think it is worth elaborating on this point to see where this improvement is coming from.\n\nWeakness: In the last section, the authors show with experiments on MNST and CIFAR datasets that the generalization error only decreases for a few iterations of pseudo labeling and then saturates. However, this observation is not very obvious to me by just looking at figures. Based on Figures 7, 8, and 9, there is a sharp reduction in generalization error after only one iteration, but after that, it is not necessarily decreasing. The overall trend of vanishing generalization error until a saturation limit is acceptable based on the plots, but drawing conclusions that for the first iterations we have significant reduction and then the reduction vanishes is not quite clear to me. For example, in figure 9, we have reduction in generalization error for the first iteration, then we have a jump in the generalization error followed by another sharp decline. It would be helpful if authors could explain these ups and downs in the plots. \n\nWeakness: Also, the first iteration used a neural network that is well trained and converged to a good solution, then we use this well-trained network to predict labels for a subset of data, and fine-tune the network using the newly-labeled data. This is no surprise to me that more than a few rounds of fine-tuning will not improve the generalization error.\n\nStrength: The paper is overall very well written and well-organized with the exception of section 4 where the authors could have done a better job of further dividing the section into multiple subsections.\n\nMinor comments:\n\n- In the informal statement of Theorem 1, it is better to mention that this bound is for pseudo labeling algorithm and not any SSL algorithm. \n- In Equation 6, I could not find what f_{\\theta_{k}} is.\n- For section 4, it would be better to subdivide it into a few subsections. It was not smooth to follow the whole section. ", "summary_of_the_paper": "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. \n\nIn 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. ", "summary_of_the_review": "The analysis of the paper seems interesting and correct. It is novel to look at the generalization error at each iterative update. However, I do have concerns about the significance of the work. It is not clear to me and it was not made clear by the authors how we can make use of this analysis and conclusions to train better models for example.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OsRk6tYUVs4", "reviewer": "Reviewer_7Xsu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strength**\n\nThe paper presents a new general algorithm-dependent generalization bound for semi-supervised learning with iterative pseudo-labelling (Theorem 1) and an application of the bound to binary classification with Gaussian class conditionals (Theorem 2).  \n\n**Weakness**\n\nAlthough the work is interesting and has some merit, to this reviewer, the theoretical results (Theorems 1 and 2) are quite far from the setting in the real world in which deep neural nets are used as the classifier and the training is done via SGD. Specifically\n\n* Theorem 2 considers only a toy problem setting. In fact this setting is very well studied in Castelli and Cover (1996) (\"The Relative Value of Labeled and Unlabeled Samples in Pattern Recognition with an Unknown Mixing Parameter\") albeit not considering an iterative pseudo-labeling approach. Compared with Castelli and Cover (1996), the current paper does not seem to offer deeper insight or stronger results. -- Agreeably it may not be fair to compare the two papers, since the considered learning algorithms are different. But I invite the authors to study this classical paper on semi-supervised learning, which is missed in the reference list of this paper.  \n\n* Theorem 1 does have the potential for analyzing SGD-alike learning algorithms on deep neural nets. But the authors did not pursue further along this direction, while only studying such more practical settings via experiments. \n\nThe experimental results related to deep neural networks appear distant from the theoretical development. To this reviewer, they are inadequate to validate or support the theoretical development. \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper presents new generalization bounds for semi-supervised learning under iterative pseudo-labeling. But the results are distant from settings of practical interest.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "JqI00sWGK0k", "reviewer": "Reviewer_hqP3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have a question regarding to the SSL algorithm considered in the paper, splitting of the unlabeled dataset into \\tau disjoint part is something unnatural to me. I understand that making \\hat{S}_{u,k}  independent would simplify the analysis, but can you give more discussion on such a formulation compared to using the entire unlabeled dataset and update the pseudo-label in each iteration? Can we interpret it as a bias-variance trade-off, as more samples would reduce variance, but the low quality of the pseudo-label would increase the bias? \n\nThe organization of section 4 can be improved by using subsections and subtitles, which emphasize the main take-away message of each discussion and remark in words. There are so many new notations introduced in this section, and they are not well-explained, especially the G_\\sigma and F_\\sigma function. If we only care about the monotonicity of these functions, then a lot of technical details can be moved to the appendix, so that the discussion of related works can be incorporated in the main body of the paper.\n\nI feel like the experimental result is not very informative, as it only shows that similar generalization behavior (decrease and then saturate) can be observed in practice. However, such a phenomenon is expected, and something more useful would be how to use such bounds to predict the performance of SSL algorithm and further improve it. Maybe the authors could provide more discussion on the “cat” and “dog” result and talk about the influence of the label noise in real dataset.  \n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper provides a novel information-theoretic generalization bound for semi-supervised learning, which involves both disintegrated mutual information (characterizing the input output sensitivity) and the disintegrated KL-divergence (distribution mismatch for pseudo-label) conditioned on the previous outputs. To my knowledge, the bGMM results are quite novel and interesting. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the generalization error of semi-supervised learning, where the algorithm gradually pseudo-labels the data throughout the learning process. Theoretically, an upper bound on the generalization error is shown to decompose into a term that vanishes with successive labeling and another that does not, leading to a plateau in performance. This is studied analytically for a mixture of two Gaussians. Experimentally, similar behavior is also observed to occur in more realistic scenarios. What reviewers struggled with is to understand what part of the results are, to some extent, obvious, and what offer deeper insight. What is obvious: even if a Bayes classifier were available for pseudo-labeling, feature overlap means that there is a plateau of noise beyond which labeling cannot improve. What is not obvious: is it even worth pseudo-labeling, or could we make things worse? The merit of the paper is in elucidating the latter. There are several concerns that remain, however, even after discussions. First, there is whether the insight is substantial or not. Here, some comparison and contrast with existing literature suggests otherwise. Second, there is whether the experimentally observed behavior is an instance of the phenomenon described by theory. Here, better structured experiments are needed to tie in with the theory. Overall, although the paper presents compelling insight, it is not yet ready to disseminate. It needs a stronger argument for its added theoretical contribution and clearer experiments to support that the presented theory is indeed behind the empirical behavior of these iterative algorithms.
Decision: Reject