How unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis
Authors: Shuai Zhang
Meng Wang
Sijia Liu
Pin-Yu Chen
Jinjun Xiong
Venue: ICLR 2022 Poster (2022)
Keywords: Self-training
Semi-supervised learning
Convergence analysis
Generalization analysis

Abstract: Self-training, a semi-supervised learning algorithm, leverages a large amount of unlabeled data to improve learning when the labeled data are limited. Despite empirical successes, its theoretical characterization remains elusive. To the best of our knowledge, this work establishes the first theoretical analysis for the known iterative self-training paradigm and formally proves the benefits of unlabeled data in both training convergence and generalization ability. To make our theoretical analysis feasible, we focus on the case of one-hidden-layer neural networks. However, theoretical understanding of iterative self-training is non-trivial even for a shallow neural network. One of the key challenges is that existing neural network landscape analysis built upon supervised learning no longer holds in the (semi-supervised) self-training paradigm. We address this challenge and prove that iterative self-training converges linearly with both convergence rate and generalization accuracy improved in the order of $1/\sqrt{M}$, where $M$ is the number of unlabeled samples. Extensive experiments from shallow neural networks to deep neural networks are also provided to justify the correctness of our established theoretical insights on self-training.

Published as a conference paper at ICLR 2022
HOW DOES UNLABELED DATA IMPROVE GENERALIZA- TION IN SELF-TRAINING A ORETICAL ANALYSIS
HNE-HIDDEN-LAER ON
THE-
Shuai Zhang
Meng Wang
Rensselaer Polytechnic Institute Troy, NY, USA 12180 changs298rpi.. edu
Rensselaer Polytechnic Institute Troy, NY, USA 12180
wangm 0 @rpi. edu
Sijia Liu
Pin-Yu Chen
Michigan State University East Lansing, MI, USA 48824 MIT-IBM Watson AI Lab, IBM Research
IBM Research
Yorktown Heights, NY, USA 10562
Pin Yu, Chen@ibme com
liusiji5@mau edu
Jinjun Xiong
University at Buffalo
Buffalo NY, USA 14260
jinjunebuf falo.arl.. edu
ABSTRACT
Self-training, a semi- cemi-supervised learning algorithm, leverages large amount of unlabeled data improve learning when the labeled data are limited. Despite em- pirical successes, its theoretical characterization remains elusive. To the best of our knowledge, this work establishes the first theoretical analysis for the known iterative self-training paradigm and proves the benefits of unlabeled data in both training convergence and generalization ability. To make our theoretical analysis feasible, we focus the of mee-hddeen-lar layer neural networks. However, theoretical understanding low neural network. One of the key challenges that existing neural network landscape analysis built upon supervised learning no longer holds in the (semi- supervised) self-training paradigm. We address this challenge and prove that itera- tive self-training converges linearly with both convergence rate and generalization accuracy improved in the order of 1/VM M. where M is the number of unlabeled samples. Experiments from shallow neural networks deep neural networks are also provided to justify the correctness of our established theoretical insights on self-training.
iterative self-training is non-trivial even for a shal-
INTRODUCTION
Self- Self-training (Scudder 1965 Yarowsky 1995 Lee et al. 2013 Han et al. 2019). one of the most
powerful supeeveuee learning (SemiSI.) al algorithms, augments a limited number of labeled data with unlabeled data so as to achieve improved generalization performance on test data, compared with the model trained by supervised learning using the labeled data only. Self-training has shown empirical success in diversified applications such few-shot image classification (Su et al.] 2020 Xie et al.) 2020 Chen et al.] 2020a) Yalniz et al.) 2019 Zoph et al. 2020 objective detection 2005), robustnesssss awares model training against ad attacks (Carmon al. lifelong learning (Lee et al.) 2019), and natural language processing (He et al,
[Rosenberg et al.
2019), continual
2019
Kahn al.
2020). The terminology "self-training" has been used describe various SemiSI.

---

Published as a conference paper at ICLR 2022
algorithms in the literature, while this paper is centered on the commonly iterative self-training method in particular. In this setup, an initial teacher model (leaned from the labeled data) is applied to the unlabeled data to generate pseudo labels. One then trains a student model by minimizing the weighted empirical risk of both the labeled and unlabeled data. The student model is then used as the new teacher update the pseudo labels of the unlabeled data. This process is repeated multiple times to improve the eventual student model. We refer readers to Section 2 for algorithmic details.
Despite the empirical achievement of self-training methods with neural networks, the theoretical justification of such success is very limited, even in the field of SemiSL. The majority of the theo- retical results on general SemiSL are limited to linear networks (Chen al., 2020b, Raghunathan et al. 2020; Oymak & Gulcu 2020; Oneto et al. 2011). The authors in (Balcan & Blum 2010) show that unlabeled data can improve the generalization bound if the unlabeled data distribution and target model are compatible. For instance, the unlabeled data need to be well-chosen such that the target function for labeled data can separate the unlabeled data clusters, which, however, may not be able to be verified ahead. Moreover, (Rigollet 2007 Singh et al.) 2008) proves that unlabeled data can improve the convergence rate and generalization error under a similar clustering assumption, where the data contains clusters that have homogeneous labels. A recent work by Wei et al. (2020) analyzes SemiSL on nonlinear neural networks and proves that an infinite number of unlabeled data can improve the generalization compared with training with labeled data only. However, Wei et al. 2020) considers single shot rather than iterative SemiSI., and the training problem aims to minimize the consistency regularization rather than the risk function in the conventional self-training method (Lee et al. 2013). Moreover, Wei et al. (2020) directly analyzes the global optimum of the noncon- vex training problem without any discussion about how achieve the global optimum. To the best of our knowledge, there exists no analytical characterization of how the unlabeled data affect the generalization of the learned model by iterative self-trainin training on nonlinear neural networks.
Contributions. This paper provides the first theoretical study of iterative self-training on nonlinear neural net- works. Focusing on one-hidden me-hidden-layer neural networks, this paper provides a quantitative analysis of the gen- eralization performance of iterative self-training as
Test Test accuracy Improvement (%)
6.5
function of the number of labeled and unlabeled sam- ples. Specifically, our contributions include
Solf-training
Fitted curve of el 73r by Theorem
5.5
1. Quantitative justification of generalization im- provement by unlabeled data. Assuming the exis- tence of a ground-truth model with weights W that maps the features to the corresponding labels, prove that the learned model via iterative self-training moves closer W* as the number M of unlabeled data in- creases, indicating better testing performance. Specif- ically, we prove that the Frobenius distance W which is approximately linear in the generalization er- ror, decreases in the order of 1 1/VM. As an exam- ple, Figure shows that the proposed theoretical bound matches the empirical self-training performance versus the number of unlabeled data for image clas- sification; see details in Section
100K
200K 300K 400K 500K
Number of unlabeled data
Figure 1: The trend of test accuracy improvement (%) on CIFAR-10 by self- training CIFAR-10 (labeled) with dif- ferent amount of unlabeled data from 80 Million Tiny Images matches our theoret- ical prediction.
2. Analytical justification of iterative self-training over single shot alternative. We prove that the student models returned by the iterative self- self-training method converges linearly to a model close to W', with the rate improvement in the order of L/VM.
3. Sample complexity analysis of labeled and unlabeled data for learning proper model. We quantify the impact of labeled and unlabeled data on the generalization of the learned model. In particular, we prove that the sample complexity of labeled data can be reduced compared with supervised learning.
1.1 RELATED WORKS
Semi-supervised learning. Besides self-training, many recent SemiSL algorithms exploit either consistency regularization entropy minimization. Consistency regularization is based on the
2

---

Published as a conference paper at ICLR 2022
sumption that the learned model will return same similar output when the input is perturbed (Laine & Aila 2016; Bachman et al.] 2014 Sajjadi et al. 2016; Tarvainen & Valpola 2017; Reed et 20.15. (Grandvalet & Bengio 2005) claims that the unlabeled data are more informative if the pseudo labels of the unlabeled data have lower entropy. Therefore, a line of works (Grandvalet & BBngioo (0055 Miyato et al.. (018) adds regularization term that minimizes the entropy of the out- puts of the unlabeled data. In addition, hybrid algorithms that unify both the above regularizations have been developed like (Berthelot al. 2019a b. Sohn et al. 2020).
Domain adaptation. Domain adaptation exploits abundant data in the source domain to learn a model for the target domain, where only limited training data are available (Liebelt & Schmid,
2010 Vazquez et al.) 2013] Zhang et al. 2013: Long et al.) 2015] TTeng et al., 2014). Source and target domain are related but different. Unsupervised domain adaptation (Ganin & Lempitsky] 2015
Ganin et al., 2016 Gong et al. [013 BBousmalis et al. (016), where training data in target domain are unlabeled, is similar to SemiSI., and self-training methods have been used for analysis (Zou ct al. 2018 Tang al. 2012 French et al. 2018). However, self-training and unsupervised domain adaptation are fundamentally different. The former learns a model for the domain where there is limited labeled data, with the help of large number of unlabeled data from different domain. The latter learns a model for the domain where the training data are unlabeled, with the help of sufficient labeled data from different domain.
Generalization analysis of supervised learning. In theory, the testing error is upper bounded by the training error plus the generalization gap between training and testing. These two quantities are often analyzed separately and cannot be proved to be small simultancously for deep neural networks. For example, neural tangent kernel (NTK) method (Jacot et al.) 2018 Du et al. 2018: Lee et 2018) shows the training error can be zero, and the Rademacher complexity in (Bartlett & Mendelson
2002] bounds the generalization gap (Arora et al., 2019a). For me-hidden--lyer neural networks (Satran & Shamir 2018), the testing error can be proved to be zero under mild conditions. One common assumption is that the input data belongs to the Gaussian distribution (Zhong et al. [217
Ge et al. 2018 Kalai et al.) 2008 Bakshi et al. (2019: Zhang et al., [2066] Brutzkus & Globerson
2017 Li & Yuan 2017: Soltanolkotabi et al. 2018). Another line of approaches (Brutzkus et al,
2018
Li & Liang 2018
Wang et al. 2019) consider linearly separable data.
The rest of this paper is organized as follows. Section 2 introduces the problem formulation and self-training algorithm. Major results summarized in Section and empirical evaluations are presented in Section 4 Section (aatoon/jccooccee coneludes the whole paper. All the proofs are in the Appendix.
2 FORMALIZING SELF-TRAINING: NOTATION, FORMULATION, AND ALGORITHM
Problem formulation. Given N labeled data sampled from distribution P.. denoted by D (an; Yo JN n= and M unlabeled data drawn from distribution Pa, denoted by D (#em 1M m==1- The aim is to find neural network model g( (W) where W denotes the trainable weights, that minimizes the testing error on data sampled from Pt.
Table 1: Iterative Self-Training
(S1) Initialize iteration ع = 0 and obtain model (()) as the teacher using labeled data D only:
(S2) Use the teacher model to obtain pseudo labels 7m of unlabeled data in D;
(S3) Train the neural network by minimizing ( via T-step mini-bated gradient descent
method using disjoint subsets {D.)== and {D.}eo of D. Let ((+1) denote the obtained
student model;
(S4) Use (++11) as the current teacher model. Let l < + and go back to step (S2);
Iterative self-training. In each iteration, given the current teacher predictor g( ((W()), the pseudo- labels for the unlabeled data in D are computed as Gm. g( (( Z.m. The method then minimizes the weighted empirical risk f (WW(WWW))) of both labeled and unlabeled data through stochastic gradient
3

---

Published as a conference paper at ICLR 2022
descent, where
X 2N Σ (yn 9 W; ;.,)
(w)((W)=
Σ
Vmm 9 W; :B.))
2M
and A -+ The learned student model g ((+)) is used as the teacher model in the next iter- ation. The initial model g (W is learned from labeled data. The formal algorithm is summarized as in Table 1.
Model and assumptions. This paper considers regression where g is one-hidden-layer fully connected neural network equipped with K neurons. Namely, y, given the input æ E E and weights wx] E _ we have
W W1, W2
9 W: ax)
K Σ
(mun at),
where & is the ReLU activation function and d(=) max 22, 0} for any input R. Here, fix the top layer weights as for simplicity, and the equivalence of such a simplification is discussed in Appendix K
Moreover, we assume an unknown ground-truth model with weights W that maps all the features to the corresponding labels drawn from P1, i.e., y = =()"; where (æ, y) Pt. The generalization function (GF) with respect to ((W) is defined as
((((W) = B(aw))a (v - g(W; :))= E(a.)>a (o(W: g (W:x))
(3)
By definition [(g(W*) is zero. Clearly, W is not unique because any column permutation of W which corresponds to permuting neurons, represents the same function W and minimizes GF in (3 too. To simplify the representation, we follow the convention and abuse the notation that the distance from W W', denoted by || W"|[r, means the smallest distance from W to any permutation of W Additionally, some important notations are summarized in Table
We assume the inputs of both the labeled and unlabeled data belong to the zero mean Gaussian distribution, i.e., æ (N 82 Ia), and ø NN 8² The Gaussian assumption is motivated by the data whitening (LeCun et al. 2012) and batch normalization techniques (Ioffe & Szegedy) 2013) that are commonly used in practice improve learning performance. Morcover, training one- hidden-layer neural network with multiple neurons is NP-Complete (Blum & Rivest 1992) without any assumption.
The focus of this paper. This paper will analyze three aspects about self-training: (1) the gener- alization performance of ( the returned model by self-training after iterations, measured by (L) W (2) the influence of parameter À in (T) on the training performance; and (3) the impact of unlabeled data the training and generalization performance.
Table 2: Some Important Notations
D (Iin Un Numl
Labeled dataset with N number of samples;
W D @m m==1
Unlabeled dataset with M number of samples:
d
Dimension of the input
Ø;;
K
Number of neurons in the hidden layer;
Conditional number (the ratio the largest and smallest singular values) W";
W
Model returned by self- self-training after iterations; (" is the initial model;
W
Weights of the ground truth model;
W
w [ xw + (1 (0)
'The results can be extended to binary classification with a cross-entropy loss function. Appendix-I.
Please see
Beeaause ReLU is non-linear and non-smooth, ( is non-convex and non-smooth. which poses analytical challenges. results can be easily extended to smooth functions with bounded gradients. e.g., Sigmoid. We use this metric hecause (g(W)) is shown to be linear in WW()) W numerically when (LL) is close to W see Figure
4

---

Published as a conference paper at ICLR 2022
3 THEORETICAL RESULTS
Beyond supervised learning: Challenge of self-training. The existing theoretical works such [Zhong et al. 2017 Zhang al.) 2020a|bcc) verify that for one-hidden-layer neu- ral networks, If only labeled data are available, and æ are drawn from the standard Gaus- sian distribution, then supervised learning by minimizing [ with X 1 can return model with ground- truth weights W (up to column permutation), as long as the num- ber of labeled data N paper focuses on the low labeled-data regime when N is less than N Specifically,
least N*, which depends on K, and
contrast, this
(4)
Ofjective A without unlbblet data
Objective fontion with unlabeled catta
Intuitively, if N < N the landscape of the empir- ical risk of the labeled data becomes highly non- convex, even in neighborhood of W thus, the existing analyses for supervised learning do not hold in this region. With additional unlabeled data, the landscape of the weighted empirical risk be- comes smoother near W Moreover, M in- creases, and starting from a nearby initialization, the returned model (L) by iterative self-training converge local minimum that is closer to
Local mintmm.
Cenernttation function
W
Figure 2: Adding unlabeled data the em- pirical risk function drives its local minimum closer to W which minimizes the generaliza- tion function.
W (see illustration in Figure
Compared with supervised learning, the formal amalyses of self- training need to handle new techni- cal challenges from two aspects. First, the existing analyses of supervised learning exploit the fact that the GF and the empirical risk have the same minimizer, i.e., W This property does not hold for self-training as W* no longer minimizes the weighted empirical risk in (T). Second, the iterative manner of self-training complicates the analyses. Specifically, the empirical risk in each iteration is different and depends on the model trained in the previous iteration through the pseudo labels.
In what follows, we provide theoretical insights and the formal theorems. Some important quantities Å and y are defined below
2
A + X
À = A52 + X
and = ((8,0) = V Ap(r) + Ap(ō)
(5)
where p is positive function defined in 733 À an increasing function of A. Also, from Lemma
11 (in Appendix), p(8) is in the order of 8 when 5 < for ReLU activation functions. Thus, μ is
fixed constant, denoted by (", for all 6, < 1. When 5 and are large, / increases they increase.
The formal definition of N 4 is c(Ks) x3 q, where c(xs some polynomial function of
and can be viewed as constant.
3.1 INFORMAL KEY THEORETICAL FINDINGS
Fa
To the best of our knowledge, Theorems D and 2 provide the first theoretical characterization of tterative self-training on nonlinear neural net- works. Before formally presenting them, we summarize the highlights as follows.
4g
E,
M
K
(W000)
W(1
W0(0
W
Linear convergence the learned models. The learned models converge linearly to model close W Thus, the iterative approach re- turns model with better generalization than that by the single-shot method. Morcover, the con- vergence rate is constant term plus term in the order of 1/ /M (see A₁ in Figure 3 indi- cating a faster convergence with more unlabeled data.
140
(1-2)
I|W- W
Figure 3: Illustration of the (1) ground truth W (2) iterations / (3) convergent point
(L)), and (4) WI \w* + (1 ()

---

Published as a conference paper at ICLR 2022
2. Returning model with guaranteed generalization in the low labeled-data regime. Even when the number of labeled data is much less than the required sample complexity to obtain W in supervised learning, prove that with the help of unlabeled data, the iterative self self-training can return a model in the neighborhood of WIA1, where W is the line segment of W () = 0) and ground truth W () = 1). Moreover, Å is upper bounded by VN/N.. Thus W moves closer W N increases (En in Figure B indicating better generalization performance with more labeled data.
3. Guaranteed generalization improvement by unlabeled data. The distance between W( and W (&1 in Figure 3 scales in the order of 1//M. With a larger number of unlabeled data M. (L)) moves closer to W(A and thus W indicating an improved generalization performance (Theorem D. When N close N but still smaller defined in 12). both W)(L) and w converge to W and thus the learned model achieves zero generalization error (Theorem 2
3.2 FORMAL THEORY IN LOW LABELED-DATA REGIME
Takeaways of Theorem 1: Theorem 1 characterizes the convergence rate of the proposed algorithm and the accuracy of the learned model W(L) in low labeled-data regime. Specifically, the iterates converge linearly, and the learned model is close to W(A) and guaranteed to outperform the initial model (
Theorem 1. Suppose the initialization ( and the number of labeled data satisfy
[| W'
c(K))²3331 with Pe 0= (2.1),
W
(6)
2p 2p-11 112 N SNSN.. μvk
and max R
the value of \ in 5 and unlabeled data amount M satisfy
max {1 KK PVK
2p 1p-1, -1 sis min {v
N NO
2p 1 P
uv K f
(8)
and M 2 (2p 1) (2p-1))2c(k)pp² (1 X dogg.
(9)
Then, when the number T of SGD iterations is large enough each loop l, with probability at least 1 q the iterates (W(1)] M- converge to W(1 as
- -wol-wlllle 1 ((1 ((1+0(4)))) ()))))))))))))))) |W
w1 l2
(1+0( ((((-)))))
I|W -WiA
Vi
(10)
where WI iw" + +(1 (0) Typically, when the iteration number L is sufficient large, have
[W(L) W' s (1 (1+ 1 1(1
((( -a))) - VM
2(1-
-I w'00
(1I)
The accuracy of the learned model (L)) with respect to W* is characterized as (10), and the learning model is better than initial model as in (11) if the following conditions hold. First, the weights À in (T) are properly chosen as in (8) Second, the number of unlabeled data is sufficiently
large as in (
Selection of in self-training algorithms. When Å increases, the required number of unlabeled data is reduced from (9), and the convergence point (L) becomes closer to W from IT]. which indicates smaller generalization error. Thus, a large Á within its feasible range (8) is desirable. When the initial model (U) is closer W (corresponding labeled data N increases, the upper bound in (8) increases, and thus, one can select a larger Á.
larger p), and the number of
The initial model (0), The tensor initialization from Zhong et al. 2017) return (0) that satisfies (6) when the number of labeled data is N = p²N (see Lemma 3 in Appendix). Combining with the requirement in ( Theorem I applies to the case that N is least N*/4.

---

Published as a conference paper at ICLR 2022
3.3 FORMAL THEORY OF ACHIEVING ZERO GENERALIZATION ERROR
Takeaways of Theorem 2: Theorem 2 indicates the model retureed by the proposed algorithm con- verges linearly to the ground truth W Thus the distance between the learned model and the ground truth can be arbitrarily small with the ability to achieve zero generalization error. The required sam- ple complexity reduced by a constant factor compared with supervised learning. Theorem 2. Consider the number of unlabeled data satisfies
(1 - 1/(wVK))²
N N INSN'.
(12)
we choose Ả such that
1 1-1 SÁS VN/N=.
(13)
Suppose the initial model W and the number of unlabeled data M satisfy
I and M M2 2( 2)2
[| W <
(14)
d(x)p233/2
the iterates (W())) JE-n converge to the ground truth W follows.
( W' $ [1+ c(K) VN
nV pV - 20]"
-1]] ||
+
W' (15)
VM
The models WO'ss converge linearly the ground truth W 15 when the number of labeled data satisfies (12). In contrast, supervised learning requires at least N labeled samples to estimate W accurately without unlabeled data, which suggests self-training at least saves constant fraction of labeled data.
3.4
THE MAIN PROOF IDEA
Our proof builds upon and extends one recent line of works on supervised learning such as (Zhong et al. 2017, ZZhng et al., 2020b c 2021 The standard framework of these works is first to show that the generalization function Tgg ()) in (3) locally convex near W*, which is its global minimizer. Then, when M = 0 and N is sufficiently large, the empirical risk function using labeled data only can approximate 1 (g( W)) well in the neighborhood of W Thus, initialized this
local convex region, the iterations, returned by applying gradient descent approach on the empirical risk function, converge to W linearly.
The technical challenge here is that in self-training, when unlabeled data are paired with pseudo labels, W is no longer a global minimizer of the empirical risk fo.5 in (1). and fp.5 does not approach T [gg( (W) even when M and N increase to infinity. Our new idea is to design a population risk function f(W; X) in (17) (see appendix), which a lower bound of f. when M and N are infinity. f(W; X) is locally convex around its minimizer WIA, and W( approaches W as increases. Then we show the iterates generated by fp.5 stay close to f(W; and the returned model (L)) is close W(A], New technical tools developed bound the distance between the functions fo.5 and f(W; X).
EMPIRICAL RESULTS
4.1 SYNTHETIC DATA EXPERIMENTS
We generate a ground-truth neural network with the width K = 10. Each entry of W is uniformly selected from 2-,,5, 2.5]. The input of labeled data 2n are generated from Gaussian distribution AO La) independently, and the corresponding label yn is generated through (2) using W*. The unlabeled data 2m are generated from (0, 82 La) independently with 5 except in Figure is set as 50 except in Figure [ The value of is selected as d2 except in Figure We consider one-hideen-layer except in Figure The initial teacher model (0)) in self-training is randomly selected from [W]]|W- W W+ I 0.5) to reduce the computation. In
7

---

Published as a conference paper at ICLR 2022
each iteration, the maximum number of SGD steps T is 10. Self Self-training terminates if [W(++) |ll [ 10-4 reaching 1000 iterations. In Figures to 8 all the points the curves are averaged over 1000 independent trials, and the regions in lower transparency indicate the corresponding mne-saadaardddeviatio error bars. Our empirical observations are summarized below.
(a) GF (testing performance) proportional to I W' Figure illustrates the GF in against the distance to the ground truth W To visualize results for different networks together, GF is normalized in [0, 1]. divided by its largest value for each network architecture. All the results are averaged over 100 independent choice of W. One can see that for one-hidden-layer neural networks, large region near W GF almost linear | W* When the number of hidden layers increases, this region decreases, but the linear dependence still holds locally. This is an empirical justification of using IW- W to evaluate the GF and, thus, the testing error in Theorems 1 and 2.
(b) ( WF as a linear function of 1/VM. Figure shows the relative error | W /r/ || when the number of unlabeled data and labeled data changes. One can see that the relative error decreases when either M or N increases. Additionally, the dash-dotted lines represent the best fitting the linear functions of 1/V M using the least square method. Therefore, the relative
error is indeed a linear function of 1/ M, as predicted by our results in (II) and 15
4.3
Normalized Flot))
0.8
Relative anor (%)
131
Converguuzee rate
0,59955
500
Fiteel maao
0.6 04
6.99945
Nickkn layer hicakn layer [blithbeniiser So-litbkesliestt
3,5
0.9994
0.99935
0.98
0.1
0.2
0.3
0.4
U.
400
0.017
0.0L
IW
W
|e/[
Number of unlabeled data (M)
1/vl7
Figure 4: The generalization function against the distance to the ground truth neural network
Figure 5: The relative error against the number of unlabeled data.
Figure 6: The convergence rate with different M when N < N
(c) Convergence rate as linear function of L/VM. Figure illustrates the convergence rate when M and N change. We can that the convergence rate is linear function of 1 1/VM, as predicted by our results (1T) and (15). When M increases, the convergence rate is improved, and the method converges faster.
(d) Increase of 8 slows down convergence. Figure shows that the convergence rate becomes worse when the variance of the unlabeled data increases from 1. When less than 1, the convergence rate almost remains the same, which is consistent with our characterization in (10) that the convergence rate is linear in μ. From the discussion after (5). μ increases as 8 increases from and stays constant when ò is less than 1.
(e) (L) W ||F/ [ WI emrors of ((L) with respect to W' decrease almost linearly when increases, which is consistent with the theoretical result (TT). Moreover, when À exceeds a certain threshold positively correlated with N, the relative еттor increases rather than decreases. That is consistent with the analysis in (8) that À has an upper limit, and such limit increases as N increases.
is improved as a linear function of A. Figure shows that the relative
(f) Unlabeled data reduce the sample complexity learn W Figure 9 depicts the phase tran- sition of returning (I.), For every pair of d and N, we construct 100 independent trials, and each
trial is said to be successful if (L) W ||/|| < 1 The white blocks correspond to the successful trials, while the block in black indicates all failures. When increases, the required number of labeled data to learn W' is linear in d. Thus, the sample complexity bound in (12) is order-wise optimal for d. Moreover, the phase transition line when M 1000 is below the one when M 0. Therefore, with unlabeled data, the required sample complexity of N is reduced.
8

---

Published as a conference paper at ICLR 2022
Nunber of laboded dase (N)
M
M 1000
6.9
Converjence rale
Relative ertor (%)
6.5
Nazan
620
680
680
620
N-280
560
560
0.985
6.1
440
500
500
5.7
580
380
0.95
5.3
0.1
0.2
0.3
0.4
0.5
20 26 32 38 44 50
20 26 32 38 44 50
Dimeusion of Iaput
Dimensson inpus (4)
Figure 7: Convergence rate Figure 8:
[W W l|e
Figure 9: Empirical phase transition of the curves with (a) M and (b) M 1000.
[W 1
with different 8.
when Ā and N change.
4.2 IMAGE CLASSIFICATION ON AUGMENTED CIFAR-10 10 DATASET
We evaluate self-training on the augmented CIFAR-10 10 dataset, which has 50K labeled data. The unlabeled data mined from 80 Million Tiny Images following the setup in (Carmon et al. 2019
and additional 50K images are selected for each class, which is a total of 500K images, to form the unlabeled data. The self-training method is the same implementation that in (Carmon al. 2019).
and À is selected as N/MM + N) and M/(N + M). respectively, and the algorithm stops after 200 epochs. Figure 10 the dash lines stand for the best fitting of the linear functions of 1/vM via the least square method. One see that the test accuracy is improved by up to 7% using unlabeled data, and the empirical evaluations match the theoretical predictions. Figure shows the convergence rate calculated based the first 50 epochs, and the convergence rate is almost linear function of 1/ //VM, predicted by 10
Test accuracy (%)
0.962
Convergence male
0.96
85
0.958
0.956
0.954
N=15K
80
0.952
N-00K
100K
200K 300K
400K
500K
Number of unlabeled data (M)
5
6
7
8
9
10
N-
N-
N-30k
1/v M
x x10
N-J by Theoreer
euree 901v3T
Figure 11: The convergence rate against the Figure 10: The test accuracy against the number of unlabeled data
number of unlabeled data
5 CONCLUSION
This paper provides new theoretical insights into understanding the influence of unlabeled data in the iterative self trainini algorithm. We show that the improved generalization eтror and conver- gence rate is a linear function of 1/VM, where M is the number of unlabeled data. Moreover, compared with supervised learning, using unlabeled data reduces the required sample complexity of labeled data for achieving zero generalization error. Future directions include generalizing the anal- ysis to multi-layer neural networks and other semi-supervised learning problems such as domain adaptation.
ACKNOWLEDGEMENT
This work was supported by AFOSR FA9550-20-1-0122, ARO 1911NF-21-1-0255 NSF 1932196 and the Rensselaer-IBM AI Research Collaboration (http://aire.rii.edu) part of the IBM Al Hori- zons Network
'The codes are downloaded from http://ghhaaccmmmyicccmmmmmiimmh

---

Published as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. Advances neural information processing systems, pp. 6158-6169, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In 36th In- ternational Conference on Machine Learning, ICML 2019, pp. 477-502. International Machine Learning Society (IMLS), 2019b.
Philip Bachman, Ouais Alsharif, and Doina Precup. Learning with pseudo-ensembles Advances in neural information processing systems, 2014.
Ainesh Bakshi, Rajesh Jayaram, and David Woodruff. Learning two layer neural networks in polynomial time. In Conference on Learning Theory, pp. 195-268. PMLR, 2019.
Maria-Florina Balcan and Avrim Blum. discriminative model for semi-supervised learning. Jour- nal of the ACM (JACM), 57(3):1-46, 2010.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 2002.
David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel. Remixmatch: Semi-supervised learning with distribution matching and augmenta- tion anchoring. In International Conference on Learning Representations, 2019a.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: A holistic approach to semi-supervised learning. arXiv preprint arXiv: 190.:022500299 2019b.
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Avrim Blum and Ronald Rivest. Training 3-node neural network is np-complete. Neural Networks, 5(1):117-127, 1992.
Konstantinos Bousmalis, George Trigeorgis, Nathan Silberman, Dilip Krishnan, and Dumitru Erhan. Domain separation networks. In Proceedings of the 30th International Conference Neural Informtion Processing Systems, pp. 343-351, 2016.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning- Boaniing-Volumee Volume 70, pp- 605-614. JMLR. org, 2017.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. Advances in Neural Information Processing Systems, 32:
11192-11203, 2019.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. Advances in Neural Information Processing Systems, 33:22243-22255. 2020a.
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift, Advances in Neural Information Processing Systems, 33, 2020b.
10

---

Published as a conference paper at ICLR 2022
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representatiins, 2018.
Geoffrey French, Michal Mackiewicz, and Mark Fisher. Self-ensembling for visual domain adapta- tion. In International Conference on Learning Representations, number 6, 2018.
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Guaranteed recovery of cone-hidden-laye layer neural networks via cross entropy. IEEE Transactions on Signal Processing, 68:3225-3333 -2335, 2020.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning, pp. 1180-1189. PMLR, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversariaa training of neural net- works. The journal of machine learning research, 17(1))2096-200 2016.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning mne-hidden-layer neural networks with land- scape design. In International Conference on Learning Representations, 2018. URL https: //openreview. wewenreevew.net/fooorree
Boqing Gong, Kristen Grauman, and Fei Sha. Connecting the dots with landmarks: Discrimina-
tively learning domain-invariant features for unsupervised domain adaptation. In International Conference on Machine Learning, pp. 222-230. PMLR, 2013.
Yves Grandvalet and Yoshua Bengio. supersuper learning by entropy minimization. In Con- ference d' apppenttssagee CAp. pp. 281, 2005.
Jiangfan Han, Ping Luo, and Xiaogang Wang. Deep self- self-leamnng from noisy labels. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5138-5147, 2019.
Junxian He, Jiatao Gu, Jiajun Shen, and Mare' Aurelio Ranzato. Revisiting self-training for neural sequence generation. In International Conference Learning Representations, 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. volume 37 of Proceedings of Machine Learning Research, pp- 448-456 Lille, France, 07-09 Jul 2015. PMLR.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- cralization neural networks. Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Jacob Kahn, Ann Lee, and Awni Hannun. Self-training for end-to-end speech recognition. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7084-7088. IEEE, 2020.
Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 3776) 2008
Volodymyr Kuleshov, Arun Chaganty, and Percy Liang. Tensor factorization via matrix factoriza- tion. In Artificial Intelligence and Statistics, pp. 507-516, 2015.
Samuli Laine and Timo Aila. Temporal ensembling for semi supi-super learning. arXiv preprint arXiv:1610.02242. 2016.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Hlbur-Robert Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9- Springer, 2012.
Dong-Hyun Lee 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, 2013.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Representations, 2018.
11

---

Published as a conference paper at ICLR 2022
Kibok Lee, Kimin Lee, Jinwoo Shin, and Honglak Lee. Overcoming catastrophic forgetting with un- labeled data in the wild. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 312-321, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activa- tion. In Advances in Neural Information Processing Systems, pp. 597-607. 2017.
Joerg Liebelt and Cordelia Schmid. Multi-view object class detection with a 3d geometric model. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp- 1688-1695. IEEE, 2010.
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In International conference on machine learning, pp. 97-105, PMLR, 2015.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: regularization method for supervised and supervisd learning. JEEE transactions on pattern analysis and machine intelligence, 41(8):1979 1993, 2018.
Luca Oneto, Davide Anguita, Alessandro Ghio, and Sandro Ridella. The impact of unlabeled pat- terns in rademacher complexity theory for kernel classifiers. Advances in neural information processing systems, 24:585-593, 2011.
Samet Oymak and Talha Cihad Gulcu. Statistical and algorithmic insights for semi-supervised learning with self-training. arXiv preprint arXiv:2006. / /006, 2020.
Samet Oymak and Mahdi Soltanolkotabi. End-to-end learning of a convolutional neural network via deep tensor decomposition. arXiv preprint arXiv: 1805.06523, 2018.
Aditi Raghunathan. Sang Michael Xie, Fanny Yang. John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. International Conference on Machine Learming, pp. 7909-7919. PMLR, 2020.
Scott E Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. In ICLR (Work- shop), 2015.
Philippe Rigollet.
Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Leurning Reseurch, 8(7), 2007.
Chuck Rosenberg, Martial Hebert, and Henry Schneiderman. Semi supersupe self-training of object detection models. In Proceedings of the Seventh IEEE Workshops on Application of Computer Vision WAACMMOTION'0S -VVolum 1-Volume 01, pp. 29-36, 2005.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4430 4438, 2018.
Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transfor- mations and perturbations for deep supi-super learning. Advances in neural information processing systems, 1121-166111,11 2016.
Henry Scudder. Probability of error of some adaptive pattern-recognitioon machines. IEEE Transac- tions on Information Theory, 113):363,,7,, 1965.
Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn't. 't Advances in neural information processing systems, 21:1513-1520. 2008
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-super learning with consistency and confidence. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Published as a conference paper at ICLR 2022
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
Jong-Chyi Su, Subhransu Maji, and Bharath Hariharan. When does self-supervision improve few- shot learning? In European Conference on Computer Vision, pp. 645-666. Springer, 2020.
Kevin Tang, Vignesh Ramanathan, Fei-Fei Li, and Daphne Koller. Shifting weights: Adapting object detectors from image video. In Advances in Neural Information Processing Systems, pp- 647-655, 2012.
Antti Tarvainen and Harri Valpola. Mean teachers better role models: Weight-averaged consis- tency targets improve semi-supervised deep learning results. In Proceedings of the 31st Interna- fional Conference on Neural Information Processing Systems, pp. 1195-1204, 2017.
Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 434,, 2012.
Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell. Deep domain confusion: Maximizing for domain invariance. arXiv preprint arXiv:1412.3474, 2014.
David Vazquez. Antonio M Lopez, Javier Marin, Daniel Ponsa, and David Geronimo. Virtual and real world adaptation for pedestrian detection. IEEE transactions on pattern analysis and machine intelligence, 36(4):797-809, 2013.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Gang Wang, Georgios B Giannakis, and Jie Chen. Learning relu networks on linearly separable data: Algorithm, optimality, and generalization. IEEE Transactions on Signal Processing, 67(9): 2357-2370, 2019.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2020.
Qizhe Xie, Minh-Thame Luong, Eduard Hovy, and Quoc V Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10687-10698, 2020.
I Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan. Billion-scall semi- supervised learning for image classification. arXiv preprint arXiv: 00546, 2019.
David Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In 33rd annual meeting of the association for computational linguistics, pp. 189-196, 1995.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International Conference on Machine Learning, pp. 819-827. PMLR, 2013.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Guaranteed convergence of training convolutional neural networks via accelerated gradient descent. In 2020 54th An- nual Conference on Information Sciences and Systems (CISS), 2020a. URL :oi:10.1109/
CISS48834 2020. 1570627111
Shuai Zhang, Meng Wang. Sijia Liu, Pin-Yo Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizabillity.nne whw-hhidddddeee case. In 2020 International Confer- ence on Machine Learning (ICML), 2020b.
Shuai Zhang, Meng Wang. Jinjun Xiong, Sijia Liu, and Pin-Yt Chen. Improved linear convergence of training cnns with generalizability guarantees: A oae-hidden-layr case. IEEE Transactions Newral Networks and Learning Systems, (2(6))2622-266)) 2020c.
13

---

Published as a conference paper at ICLR 2022
Shuai Zhang, Meng Wang. Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Why lottery ticket wins? a the- oretical perspective of sample complexity on pruned neural networks. Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS), 2021.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer relu networks via gradient descent. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1524-1534 PMLR, 2019.
Yuchen Zhang, Jason D. Lee, and Michael I. Jordan. L1-regularized neural networks are improperly learnable in polynomial time. In Proceedings of The 33rd International Conference Machine Learning, volume 48, pp. 993-1001, 2016.
Kai Zhong, Zhao Song, Prateek Jain, Peter Bartlett, and Inderjit Dhillon. Recovery guaran- tees for one-hidden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning-Voin Volume 70, pp. 4140-4149. JMLR. org, http://axiv.org/abb///66...33 2017.
Barret Zoph, Golnaz Ghiasi, Tsung- Yi Lin, Yin Cui, Hanxiao Liu, Ekin Dogus Cubuk, and Quoc Le. Rethinking pre-training and self-training. Advances in Neural Information Processing Systems, 33, 2020.
Yang Zou, Zhiding Yu, BVK Kumar, and Jinsong Wang. Unsupervised domain adaptation for se- mantic segmentation via on computer vision (ECCV), pp. 289-305, 2018.
self-training. In Proceedings of the European conference
14

---

Published as a conference paper at ICLR 2022
Appendix
A OVERVIEW OF THE PROOF TECHNIQUES
We first provide an overview of the techniques used in proving Theorems and
Characterization of proper population risk function. To characterize the performance of the iterative self self-training algorithm via the stochastic gradient descent method, we need first to define population risk function such that the following two properties hold. First, the landscape of the population risk function should be analyzable near (W($) }/=0- Second, the distance between the empirical risk function in T and the population risk function should be bounded near (W(()) 1-=0- The generalization function defined in (3). which is widely used in the supervised learning problem with a sufficient number of samples, failed the second requirement. To this end, we turn to find a new population risk function defined in (17). and the illustrations of the population risk function and objection function are included in Figure 12
2. Local convex region of the population risk function. The purpose is characterize the it- erations via the stochastic gradient descent method the population risk function. To obtain the local convex region of the population risk function, we first bound the Hessian of the population risk function at its global optimal. Then, we utilize Lemma i2 Appendix H.. to obtain the Hessian of the global optimal. The local convex region of the population risk
the population risk function function is summarized in Lemmal T and the proof of Lemma is included in Appendix H.T
3. Bound between the population risk and empirical risk functions. After the characterization of the iterations via the stochastic gradient descent method in the population risk function, we need to bound the distance between the population risk function and empirical risk function. Therefore, the behaviors of the iterations via the stochastic gradient descent method in the empirical risk function can be described by the ones in the population risk function and the distance between these two. The key lemma is summarized in Lemma 2 (see Appendix H.2). and the proof is included in Appendix H2
Local comre region fo testi
Pepulaaioontsskkuuntttrr (WW:p)
ny f
Eejertivefuunctinn fo (W)
1pr0.30 1o
19
W
Figure 12: The landscapes of the objection function and population risk function.
In the following contexts, the details of the iterative self-training algorithm are included in Appendix We then first provide the proof of Theorem 2 in Appendix H which can be viewed special case of Theorem [ Then, with the preliminary knowledge from proving Theorem [ we turn to present the full proof of more general statement summarized in Theorem (see Appendix F.. which is related to Theorem [] The definition and relative proof' of and are all included in Appendix G The proofs of preliminary lemmas are included in Appendix
B ITERATIVE SELF-TRAINING ALGORITHM
In this section, we implement the details of the mini-batch stochastic gradient descent used in each stage of the iterative self-training algorithm. After number of iterations via mini-batch stochastic
15

---

Published as a conference paper at ICLR 2022
gradient descent at &-th stage of self toff-training algorithm, the learned model is denoted W(AA) One can easily check that ( in the main context is denoted as W in this section and the following proofs. Last, the pseudo-code of the iterative self self-training algorithm summarized in Algorithm
Algorithm Iterative Self-Training Algorithm
1M m= and gradient step size rp; Input: labeled D {(T,. yn) Wn) unlabeled data D {
Initialization: preliminary teacher model with weights W(0.0);
Partition: randomly and independently pick data from D and D to form I subsets {D:).mo 22-1 and (D.) respectively;
for é = 0, 1,,,,... -L do
Um g( ((c.)) mm) for m 1.2,-.. ,M
for t 0,,1. , do
W(G++)) W(e.)) - 17. V.D. (W(cd))+ + (Wiee) w((a-1)
end for
((+1000) W((T)
end for
C NOTATIONS
In this section, we first introduce some important notations that will be used the following proofs, and the notations are summarized in Table 1.
(e.0) denotes the learned model after number iterations via mini- batch stochastic gradient descent at ê-th stage of the iterative self-training algorithm. Given student model W, the pseudo label for DD is generated as
As shown in Algorithm ]
ì = 9 W; z).
(16)
Further, let Wh) PW + (1 p) W (0.0), we then define the population risk function as
f(W:p) = Ex y" (p) - s(W:z)) 2
+ Ea (T (ilp))g(WW:3) s(::a)) 2
(17)
2
N(0,821) and (p) g ( ll) with ã N(0,821) When p 1, we have W W and y (p()) y for data D.
where (p) g( W [pl; with
Moreover, we use a; to denote the i-th largest singular value of W Then, & is defined as 01 01/ak. and 7 = 11 a./ok. Additionally, to avoid high dimensional tensors, the first order derivative of the empirical risk function defined in the form of vectorized W as
vi(w) = as as
Øs Owk
"1" E R
T '1"
(18)
Own Owz
with W [w) W2 wx] E R Therefore, the second order derivative of the empiri- cal risk function is in dl Similar to (18). the high order derivatives of the population risk functions are defined based vectorized W as well. In addition, without special descriptions, a = aa" "" stands for any unit vector that in gd with a, E Rdd. Therefore, we have
of 2 α
)
2 f1l2 max ||a
a V max
(19)
ow
16

---

Published as a conference paper at ICLR 2022
Finally, since we focus on order- wise analysis, some constant numbers will be ignored in the major- ity of the steps. In particular, use h1(z) 2 (or (22)))()) to denote there exists some positive constant C' such that h (z) 2 (or S. =) (2(2) when E R is sufficiently large.
Table 3: Some Important Notations
D {an WnFne
Labeled dataset with N number of samples;
D {T m=
Unlabeled dataset with M number of samples;
D: (an, Yn I
subset of DD with N₂ number of labeled data;
D. f0 m==
subset of D with M, number of unlabeled data;
d
Dimension of the input æ ;;;
K
Number of neurons in the hidden layer;
W
Weights of ground truth model:
w
whr = pW'
p) Wr,00)
W(C,))
Model returned by iterative self-training after t step mini-batch stochastic gradient de- stage E; (000)) is the initial model;
fo or f)
The empirical function defined in (T)
f(W:p)
The population risk function defined
Å
The value of X62 162/(A8" + Xo");
The value of A32 4.84
Ap(8)=
d,
The i-th largest singular value of W
The value of 0//OK;
The value of II 01/OK:
7
4
Some large constant R+:
D PRELIMINARY LEMMAS
We will first start with some preliminary lemmas. As outlined at the beginning of the supplementary material, Lemma T illlustrates the local convex region of the population risk function, and Lemma
2 exxplains the error bound between the population risk and empirical risk functions. Then, Lemma 3 describes the returned initial model (0,0,) via tensor initialization method (Zhong et al. 2017) purely using labeled data. Next, Lemma 4 is the well known Weyl's inequality in the matrix setting. Moreover, Lemma 5 the concentration theorem for independent random matrices. The definitions of the sub-Gaussian and nab-exxonential variables are summarized in Definitions [nd Lemmas and serve as the technical tools in bounding matrix norms under the framework of the confidence interval.
Lemma 1. Given any W IRdxK let p satisfy
σk W'
P
(20)
μ2 W
Then, we have
Ap(0) + Xp(o)
7(X82 + X32)
1 2 f(W:p)
(21)
12
K
17

---

Published as a conference paper at ICLR 2022
Lemma 2. Let f and f be the functions defined in (7) and Q label is generated through (16) with weights W. Then, we have
respectively. Suppose the pseudo
A02 K
dlog
X82
d log
(Vf(W) -V(-))
IW W
IW
W12
N
K
M
(22)
A602.
(W
W + Ao=
(W*
W
2K
with probability at least 1 Lemma 3 (Initialization,, (Zhong et al. 2017) ) Assuming the number of labeled data satisfies
-q-
N 2 N²N
(23)
for some large constant and p E k 11, the tensor initialization method, which is summarized in Appendix outputs (0,00) such that
|| - W ||5 S
OK p. p-c(K)22K
(24)
with probability at least 1 1-
Lemma (Weyl's inequality, (Bhatia 2013)). Let B + Let (B) and )s(A) (A) be the i-th largest eigenvalues of B and A, respectively. Then, we have
+ E be matrix with dimension
(a(B) (,(A) & || A i [m].
(25)
Lemma ([Tropp 2012). Theorem 1.6). Consider a fintte sequence {Z&} } of independent, random matrices with dimensions d x d2. Assume that such random matrix satisfies
E 1b))
and 1 R. almost surely.
Define
82 = max {11
max
Σ B(ZzZA)) |
Σ 1ZZZ
}
k
Then for all t. 2 0, we have
12/2 82 Rt/3 )
Prob
Z Σ
2t I (d1 + d2) exp
k
Definition 1 (Definition 5.7, random variable if satisfies
(Vershynin 2010 A random variable X is called nub-Guussian
(E| s civp
(26)
for all p 2 1 and some constant e > In addition, we have
(X-xxx S e
(27)
for all R and some constant 02 >> where || oz is the sub-Gaussian norm of X defined as ||x supp21P (/2
Moreover, a random vector X E Rd belongs to the sub-Gaussian distribution if oneedimenso marginal a X is tub-Gaussian for any E Rd, and the sub-Gaussian norm of X is defined as
| = suP]|ll|a=1 ||a X
Definition (Definition 5.13, (Vershynin 2010). A random variable X is called a sub-exponential random variable if it satisfies
(E. (p cap
(28)
for all p 2 and some constant C3 > In addition, we have
E (xxx)xxx - "0
(29)
for S 1/1 and some constant C4 O. where || is the sub-exponential norm of X
defined as || ll, supp21 (
18

---

Published as a conference paper at ICLR 2022
Lemma 6 (Lemma 5.2, (Vershynin 2010). Let ((0, fallla|z 1, Rd denote
unit ball in RR. Then, a subset Sş called {-net of ((0, 1) if every point B(0, can be approximated to within & by some point a B(0, i.e, || all2 I &. Then the minimal cardinality of E-net Sg satisfies
S S (1 2/E)
(30)
Lemma 7 (Lemma 5.3, [Vershynin 2010 Let A be an d2 x d2 matrix, and let Sg(d) be E-net of Bf, 1) in R for some (0,1). 1). Then
| (1 -11-) E) on ((E
max
|a AA2)
(31)
Lemma 8 (Mean Value Theorem). Let U R be open and f U Rua be continuously differentiable, and x E U, h E Rn1 vectors such that the line segment x + th, 0 s t S remains in U. Then we have:
f(x + h) f(x) - (L V (1)d++ h.
where f denotes the Jacobian matrix of f.
E PROOF OF THEOREM 2
With p in 17 the population risk function is reduced as
7 En 2 (WW; x)) + Ex @W:
((W)
(32)
where y o(W*;a)) =) with ((00622) and 57" =(W; with T 820 In fact, (2) can be viewed as the expectation of the empirical risk function in (I given Fm g( W* x Moreover, the ground-truth model W is the global optimal to (32) as well. Lemmas and 10
are the special case of Lemmas and with = 1. The proof of Theorem is followed by the
presentation of the two lemmas.
The main idea in proving Theorem is to characterize the gradient descent term by the MVT in Lemma X as shown (36) and (37 The IVT is not directly applied in the empirical risk func- tion because of its non-smoothness. However, the population risk functions defined in (77 and
32.. which are the expectations over the Gaussian variables, are smooth. Then, as the distance (V(W) VS(W*)]l is upper bounded by a linear function of I| - W*IlF shown in 447)
W* and [/(e.))) - W"Il as shown in 50 Finally, by mathematical induction over l and f, one can characterize [[,0). - W by (0.0) W as shown in (5). which completes the whole proof.
can establish the connection between [e,++++
Lemma (Lemma 1wtth p = 1). Let f and i are the functions defined in and respectively.
Then, for any W that satisfies,
IW W || 5
OK
(33)
2
we have
Ap(8) + Tp(5)
F2F 1 7(X82 + X 12x²TK²
(34)
K
Lemma 10 (Lemma ( with 1). Let f and f be the functions defined in 32 and respectively.
Suppose the pseudo label is generated through (16) with weights W. Then, we have
X82
Idlog
(1 2
d
VV(() - vf(W)lle
I
W
K
N
K
M
(35)
2)8²
/d q
1
(V
W
K
M
5
with probability at least 1 -d--.
19

---

Published as a conference paper at ICLR 2022
Proof of Theorem From Algorithm!!
| in the l-th outer loop, have
(((++1) =W((.)) -n fV.. (w().)) + B( w((t-1)
=W(t.) f7V + B(W(L w((l-11
(36)
+ (V.(V (
Since V f is smooth function and W is local (global) optimal f, then have
v ) =VS(W())) VS(W")
L (w(ee + u- (W(6.) w (W(60) w
(37)
where the last equality comes from MVT Lemma For notational convenience, we use H(40 to denote the integration as
( = / v2 ( V2f(wWee
+u. (W(L.) - W
(38)
Then, we have
W((++1) W
I (H(.))
31 W - W
w((.)) W
I w((e-1) W*
(39)
Vf(W(C))
VID, (W(L)))
+
Let ((,0)) SAS"" be the eigen-decoopossition of H (4,)) Then, define
ST
0
S
7 +
I1
3I
AB3) =
A(
(40)
0
ST
0
S
0
S
ST
I
0
I A +
31
BI
Since
=
we know A(3) and
share the same
0
S
0
S
0
I
I
eigenvalues. Let 7i be the i-th eigenvalue of V V (()()), then the corresponding i-th eigenvalue of 440. denoted by %
(A) satisfies
(1) (B))2 (1 1771 -1-77 (A)
+ +17%%
(3) + 3 3 0.
(41)
By simple calculation, we have
if 2 (1 V
Vin
m7
(A))²
h (B))
(42)
1 m
(A) + B) + (1 17,
(A)
+ +)2 48
otherwise.
Specifically, we have
(0) > 7/1 (A) (9), for A3 E (0, (1 (m7,())2)))
(43)
and 7/ (A) achieves the minimum ?, (A)- = |1 v mm (1)) when B (1- Virz(a) 2
From Lemma
9 for any a Rd with ||l|| = 1, we have
(V((W((.)))) {' a" a' (722(w((Ht))
((()))) + (W().)) wo) adu < L/ 7max Pimax/aa|/ddu 7max:
a (/ a a'v2 (w(())) + (w(e.)) - w-) aduu 2 1-" Mmin 7minl|aal23 [|]dd 7
(44)
20

---

Published as a conference paper at ICLR 2022
+(86) K
Xp(ō) k²
where Y/mxx
and Tinin
Therefore, we have and
Ap(d) + Ax(5)
7(A82 + A
(A)
(A) max
(45)
min
12k2nK² K2
K
Thus, we can select
and |A(B)) can be bounded by
Jesin
Ap(d) + Xp(5) 12 )/(2 7(A02 + X53)
min
| 51
B
K
(46)
j((ā,)
=1
V /168822K K
where ((6,8)= +Ap()
1/2
4-24
From Lemma 10 we have
Ag2
dllgg 4
dlog
[V V(
K
N
+
K V Me
||
W
(47)
+
X82
dlogg
+ 2))
1)
||w()e.)
-
K
Mr
Given 0 and >> 0 with + < 1, let
A62
dlogg q
EH(6,, 5)
7 K
N₂
v /168k2
(48)
X
dlogg
E)((,88 V168k2yK
and
K
Mc
where we need
2
N₁ 2 E 2 12
2 >2n²n kddlog
A + X
(49)
X
and
Mj 2 E 2 2
2 16
2222k K3 dlogg
Xg2 282
Therefore, from (46), (47 and (48) we have
(((++1) W
< (1-5- =),(6)) (( W +n.
Xo
dlogg q
+ 1 ||
K (V
-W")
118822KK
Mr
< <(1 ()) [[(,)) W +
2
(1.00
W
168K27K
K
(50)
when M 2 log q. By mathematical induction on (50) over L, we have
(e.t) W 1/2
-)--))
W 1z
V 168
168K2
K
(51)
|| - W 1|2
+ (1 E)G 14(X02 + +X82)
K
(1 - e1--- -1---)) E)
V
) +
|
W
V168K2>K
(1-
()22 + 182)
21

---

Published as a conference paper at ICLR 2022
By mathematical induction (51)
over E, we have
[W(,TT) W1
(11 (1 - E)p1 T
V x222222
(52)
+
W
1188227
(1 -
8) E)) + 128))
F PROOF OF THEOREM 1
Instead of proving Theorem I we turn to prove stronger version, as shown in Theorem 3 One can verify that Theorem is a special case of Theorem by selecting \ in the order of and is in the order of (2p- 1).
The major idea in proving Theorem similar to that of Theorem 2 The first step is to characterize
the gradient descent term the population risk function by the MVT in Lemma as shown in
58) and (59 Then, the connection between [
Wir Ir and [ W i
characterized (64). Compared with proving Theorem 2 where the induction over & holds naturally
with large size of labeled data, the induction over l' requires proper value of p as shown in (69). By
induction over e on (64), the relative error [W,00) Wirl|| || can be characterized by [
Wbll| f shown in (7I)
Theorem 3. Suppose the initialization (0,0) satisfies with
2(1 E)p
p
(53)
pVK K
for some constant غ E (0, 1/2), where
A82
N
(54)
A52 + X82
122gK* k 22 oddllog log
and
X82 782
1 = ==((,,8)
(55)
Ap(0) Ap(
Then, if the number of samples in further satisfies
M 2 E 16 7p 2) dlogg
(56)
the iterates (L.t)
LT L.T J,,t= converge Wir with p satisfies 53
lim [ - w T-
(57)
S 1- (1-
|| w
E (1
[ (e.0)
wiel
with probability at least 1 gmdd
Proof of Theorem From Algorithm]
[ in the f-th outer loop, we have
(L++1) =W((0) f/ (W(C.)) + ((w().)) w((+-1)
-W(8., - (/V ((W().)) (((--11)
(58)
+ (VI(()().))) -/pp:/.0..//_././.....// (w(l.))
Since f is smooth function and lp is a local (global) optimal to f. then we have
V((W((:))=V/ =VS(W().)) - vs(Wlr)
= = v2 (P((w())) +u. (W(L.) - wlo)) ) du (W(e.) - Wll),,
(59)
22

---

Published as a conference paper at ICLR 2022
where the last equality comes from Lemma
8
Similar to the proof of Theorem we have
[W
wiel (pl la z ||A(3)]22 1
V.D.DD (W(l))))22 (60)
From Lemma
we have
| ((W(()))))
(f(W(()))) 1/2
A
dlogg
d dlogg
((())
W
[W - W((.0)12 (61)
K
N₂
K
V M,
A52
(W(0.0)
Wlr))- X52
(W'
W
When 8= 0, following the similar steps from (41
to 446
we have
||
[V
f((W(())))
l|2
A82
d dlogg
X
dlogg
|W
[
-Wirl|2
K
N₂
K
M,
A
dllog
d dloog !
(62)
| -w
[ w
+
K
V
N₂
+
K
V
Me
A5
(1 p)
X02 pl
|| W l|2
+
K
and
((+++) w1ll|2
1
[[
- w1/1
u(5,0) 8) 154n2nK
(6 p)
dlogg
A082 (1 - p) 252 pp ) ||
(63)
1
W
K
N₂
EX8² P
dlog
+ K
[w.0))) 10000--''12.
M₁
Therefore, we have
lim ((TT) wlll 1|2
+000
154R22K
17 [( (102(1 p)
dloog
A252 (1 (1-p) p) -x02 .b3)pl)
(1.0) -
1-8
K
N₂
K
EX8² p
dlog
V Mi
||
W'l1
K
NV 154m27K
K
[((
[(A00(]
p)
dlog q
1282. (1-p) 732 pl
+
1-
14(A82 + Ao2)
K
No
K
| W +
EX8²
p
d d q
(0.00 W1
V
K
Mr
1
(1- P VK (1 p)u - pM(1 2)])
||
W²
1-
EP
|| (0.0) 2
(1-8)
1
(1 p + Wv K A - pl) || - W +
Ep
[ W
-
(1-
(64)
where 2 = M2
252
23

---

Published as a conference paper at ICLR 2022
To guarantee the convergence in the outer loop, require
lim [ w - w
w/ (0.0)
w pl w 12
7-00
(65)
and
lim [W(CT) T-00
W 22 - W W2
Since we have
[W w
S W(LT) W | w I|2
(66)
=| - w + p) | - -
it is clear that 65 holds if and only
1 - (1-p+ Ep nV WK -
pl) +1 +1 p5
(67)
To guarantee the iterates strictly converges to the desired point, we let
8- (1 (1- p
Ep -p+
/VKj 2l) +1 aal--sl- -1-
(68)
for some larger constant C, which is equivalent to
pp X - 2(1 2)p- 1
(69)
WV K
To make the bound in 669 meaningful, we need
2 2(1 8)
(70)
When l > 1, following similar steps in 64 we have
lim [W((T) Wlel|12
T-000
(71)
1-E (1- (1-p+ pil) || 1 + Ep |W(.0) wlrl
Given (69) holds, from 71,, have
lim
((.T)) Wlr||12
L-x
$ 1
(1-p+uvAi uv - pl) || W
(72)
1
(1-p+ 4 pl) || W
< 1-
G DEFINITION AND RELATIVE PROOFS OF
In this section, the formal definition of p is included in Definition 3 and a corresponding claim about p is summarized in Lemma 11. One can quickly check that the ReLU activation function satisfies the conditions in Lemma
The major idea in proving Lemma 6" when ó is small.
show (1,(6) and (6) in Definition 3 are in the order of
Definition 3. Let H, = (e (d'(oxz)=*) and (,) (6 Then, p = p(8) is defined as
p(8) = min { (o(0) ( - HF()),, J2(5) - (6) H)) Ho(5) H2( H7( (73)
where o is the minimal singular value of W
24

---

Published as a conference paper at ICLR 2022
Lemma 11 (Order analysis of p). If p(ó) > 0 for ò (0,E) for some positive constant & and the
sub- gradient of p(8) at O can be non-zero, then p()) = (8)) when -00 Typically, for ReLU activation function, / P in (5) is fixed constant for all 6, 5 -
Proof of Lemma 1. From Definition 3 we know that (6) E. (1. Suppose
have (6) ()))) and (6) = (())), then from 77 we have
Jo(6) - (6) H}( ( - O(8²),
(2(6) - (6) H²( E O(0))
(74)
H) H2( -H((0) E E0(6²) - 0
Because p is a continuous function with p(=) > 0 for some > 0. Therefore, p + Jo(8)-11) (8) when + 0+, otherwise p(z) < 0 for any 2 > 0. When 5 + 0+, both J2(6) (ō)
(6) and (ō) (6) (6) are in the order of 82, which indicates that μ is a fixed constant when both d and are close to 0. In addition, (0) (8) (8) goes to +oo while both (o( (0) [ff(() and (o) H2(0) (0) go to when ó - too. Therefore, with
large enough 6, we have
( E 0(6-) - - or ( - -
(75)
which indicates that μ is strictly decreasing function when d and 8 are large enough.
Next, we provide the conditions that guarantee H, (6) = e(7*) hold, and the relative proof for (6)
can be derived accordingly following the similar steps as well. From Definition 3 have
lim 6++0+
(5) 8r
lim 8-0
d' d'(ox=)
(0)
1
7 dz
V2T0
t
lim 8-0
o'(grot)
dt
V2T
(76)
lim
d((xx0t)
1"
et- dt
+
lim
too
o'(oxôt)
dt
6-10
22T
6-0+
/
2T
=0'(0-
p dt D'(0))
t
dt,
2
where equality (a) holds by letting t = g. It is easy to verify that
1"
I 22T
di.
V2T
and both are bounded for a fixed r. Thus, as long either o' d'(0T) ) ø' d((0)) is non-zero, we have (ō) = (())) when + 0+.
If has bounded gradient as lo'| I C. for some positive constant Co. Then, we have
(5)
o
(5xx
1
e
dz
5"
V2n8
t
0'(okot)
= de
(77)
V2n
+00
SCp
e
dt
/2T
Therefore, have H,) (8)) for all 8 > 0 when & has bounded gradient.
Typiclly, for ReLU function, one can directly calculate that H, H,()) = 8" for 5 E R, and p(0) = C82 when 8 < 1 for some constant C 0.091. Then, is easy to check that μ is constant when 5,8 < 1.
25

---

Published as a conference paper at ICLR 2022
H
PROOF OF PRELIMINARY LEMMAS
H.1 PROOF OF LEMMA
The eigenvalues of 2 f(:P)) at any fixed point W can be bounded in the form of 180 by Weyl's
inequality (Lemma 4). Therefore, the primary technical challenge lies in bounding V ((W:P) :p) / (Pl p) 2, which is summarized in Lemma 12 Lemma 13 provides the exact calulation of
the lower bound of Ez وكز az a2' (un) x:) when x belongs to Gaussian distribution with
zero mean, which is used in proving the lower bound of the Hessian matrix in (81)
Lemma 12. Let f(W:p) ;p) be the population risk function defined in 17 with p and W safisfying
20
Then, we have
A52 (1-
W lol Wlle
IV (V)
(WW:plls
(78)
K
σK
Lemma 13 (Lemma D.6, (Zhong et al. 2017 For any {w, K E TRd, ler a TRoK be the unit
vector defined in 19). When the & ReLU function, we have
K Σ a zo 2 x))) p(())
min E (0) |a/2=1
(79)
jml
where p(a) is defined in Desinition! 3
Proof of Lemma !
Let Amax W) and Amin WW denote the largest and smallest eigenvalues of V²;(W;P)) at point W, respectively. Then, from Lemma 4 we have
Amax (W) I Amax (wle)) + || ((W:p) v²f(w lel p))
(80)
Amiu (W) Amin w -
v f(w :)]l2-
Then, we provide the lower bound of the Hessian matrix of the population function at Wlri, For any a b defined in (19p with ||a||2 L, we have
min a T f(Wbl: |a|==1
K
min
AE Σ
a no ( ==)) λE
Σ j=1
a 20 (w
1o/T )3) ']
K2
||]||=1
j=1
(81)
K Σ
K
min
AIE
a x (w)piT x)) + min
AE
a
T
2Φ (w)))))
K2
||a|||=1
|a
j=l
j=1
Xp(ō) + Ap(5)
11x2gK²
where the last inequality comes from Lemma 13
Next, the upper bound can be bounded as
max a T (Wir):p)e
||x||a==
K AlExp Σ
max
a
x (w 2))
+ AE
Σ
a
xe
(wwll x)) )²
|o|T lp(T=)) 2
K2
2=
(82)
j=1
1=1
max
AIE
Σ a x (wo,)) x²)²
max AE
Σ
a T 2 (w 11 )/)))
K2
1=1
12
26

---

Published as a conference paper at ICLR 2022
(E 2i=m oz a xu x:)
For Eg
we have
K
a x u 1p/2 x))²
Ex
)=1
K
() nal (10 (il x) T, add ad (n v)
12=1
Ban aa (10 1plz a.) no ao (w x)
1==11=11
pll " (a "Bn (ww lp'r m))² 1/1
(83)
Eyn x²) T (o'
K
K
35 10|100
cxjn ||2 02
1= f==
K
K
<68
Σ
(1105,13
+|10,
1=
12=1
=KK8
Therefore, we have
V
S (Wbb::
max
a 12
K Σ
K λE
max AE
a
xo (w
+ max
Σ
a
(w
(w
1/
x)
?
(84)
K2 ||a||=1
|a|==1
/=1
j=1
6(182 + X
Then, given we have
(0.0)) = -|
1r S OK
(85)
122K
Combining (85) and Lemmal 12 we have
Ap(5) Ap(ö)
|V v² p)112 S
(86)
132r2T12
Therefore, (86) and (0) completes the whole proof.
H.2 PROOF OF LEMMA 2
The task of bounding of the quantity between V - is dividing into bounding J1, T2, and 1 as shown in (89). 11 and 13 represent the deviation of the mean of several random variables to their expectation, which can bounded through concentration inequality, i.c, Chernoff bound. In and 14 come from the inconsistency of the output label and pseudo label ÿ in the empirical risk function in ( and population risk function in (7p. The major challenge lies in characterizing the upper bound I, and 14 as the linear function of W wirl and Wir W* which is summarized in (96).
27

---

Published as a conference paper at ICLR 2022
Proof of Lemma of Owk
2
From
we know that
N
M
1 K
(W)-
p xnn) yn xn )
1- x
Σ
Σ
2lw0
am)
)
N
K
M
K
K
(o(w) xm)) - =6(w0²" zm)) ) In
K2N
==1j=
M
K
+
Σ
Σ
(dlw) xm) xm) Tmm
KdM
(87)
From 32
we know that
af (W)
Ex
K
(d(w5x) )(w;TT)) +
x
Es Σ
K
[d(w)
- 60 x) ã.
Owy
K2
K2
j=1
j=1
(88)
Then, from
we have
os
0s
:)
Owk
Owk
(d(w) xn) - (n)))a)))),,.. Ex (0(10 x) (( xx)=x0
K
K
A
(((w) - ~6(0 Tm)) [x(d(w3 x) 2e / x) ãt
K
m=1
(M(w) x..) - Mnw15 xnn) x (x(wf))))) - "6wn x=)=)"=)))
R
1=1
n=
(89)
(d(wn)T)) x:) - -6 x))
+
K
A
(llwfFmm) Φ 21003 (m)) 3. E Ex x) (
((3 x) ) z
K2
.M
K 1- Σ
+
Exs
(0( x)- H(w (
K2
1=1
I 1n I3 I4.
For any 0j E Rd with ||az|12 I 1, we define a random variable Z()) = (6(w] [))] x) p(w;7 xx))a33 x
(uu;T)))aa
and (j) = (d( an))
(5 (wwTT am)) x., as the realization of 7(j) for = 1,2
1..... ....
NN. Then,
for any p E N we have
(ElZP) 1/v
Elobwy x) - clwo,² w))2 laff 1/p
< [[ - " ael2 xp)) 1/8
(90)
<C 82 w, - wwil2 p.
where C' is a positive constant and the last inequality holds since x ~ NN0 82). From Definition 2 we know that Z belongs to sub-exponential distribution with 2| lly S 52| w 2l Therefore, by Chernoff inequality, we have
N
<1) < C -
P
2., - - Σ n=
(91)
Net
28

---

Published as a conference paper at ICLR 2022
for positive constant C' and any R.
Let t 62 w 112 dlogg and
C8a we wel-willa .t for some large constant q 0, we have
dogg
N Z - -Z( S 1 will2
(92)
N
with probability at least
q d. From Lemma
we have
N
(dlw]a.) xn)) Dlw5" xn)) En En( x)) - (()
n=1
(93)
<28 w, - will2 / dllog
N
with probability at least 1 - (g/5)-4 Since q is a large constant, we release the probability as 1 q- for simplification. Similar to Z, we have
(d(w) xm)) 6600 Tm)) "n Ex(((w33)) [(
(94)
dlogg M
88 w
W. 1a
with probability at least 9-
II
I
8
W0
IV-A
Figure 13: The subspace spanned by wz and w!!!
For term Ez (d( blT x)) let us define the angle between w and w/// as 0,. Figure
13 shows the subspace spanned by the vector w and wj. We divide the subspace by pieces, where the gray region denotes area I, and the blue area denotes area II. Areas III and IV are the symmetries of II and from the origin, respectively. Hence, we have
Em ( w) - Aw!pi Ipix )x)
= -Eos area ceai((olun [o(e0 x)) 66w |T)T x))xz
+ ExE arca uI x) -(wplii x)) x
(0(20) TT xx) - (1w0) [p]T xx) x + Ene ureu (0((1) x)) slw Ipi x;))
+ Eee area iII
(95)
-Exs area (0(w;"" xx- d(w, Do/T x))xz² Ere area u [w;"xx]]] xxx]
ErE area m 10! xw]
-Ene area [(w) wobl [x[] + Eng area 11 [ww] w y (" axx]
Ex (w) lo!pl)7 x
29

---

Published as a conference paper at ICLR 2022
Therefore, we have
A
E (o(w)Tz) x)) - x))²0)
+ 1- A
Es
[d(20
K
K²
A
Eez (w03 - -w!pi>yaae xxx]
+ 2
Ex (20₃ - 20 )
(96)
2K
A182.
(wxj
2 w0) + (1 2)52...
(unz 211
2K
From 93
94 and
196.. we have
0f
Of
(W: :p)
(W)
dro
2
K
(b(w) æn) - =6(13" x,)) xn - Ex x) - ~((05" 28 2
Σ
(Ó(w) Tmm) xm)
Ex (0(2w) x)) 20 2 )
K2
M
+
(o(20)")x) xt) - -0(00))77 x))
+
1
Ex
(0(w) x)) oi m To| و))
K2
K²
2 (97)
dlog q
K
|20 - w33l2 + 1 x
d dlogg q
K
< K2
82
Σ
82
Σ 5=1
|20 - 1Uر12
N
x²
M
j=l
+
1
Σ
||
(io, - (wf) + xo²
(wj
m (?)) lll
2K²
1=1
A
dlog4
W W' l2 + 1 X
K3/2 52, dlog
82,
W Wll
K3/2
N
M
+
1882
(W- - wirl) + (1 - A)8². (w* wlel l|2
2K3/2
with probability at least 1 - पー
In conclusion, let a E Rd and oj E Rd with a - [Ia ... . of we have
[V =
vf(W))
af Own
os (W)
as Ow
(w))
oʃ (W)
0s (W) Owo
||0rxl12
Deck
d q
N W - + 1- >
dlog
82 V M
Wl lz
K
K
1A82. (W- - wli) + (1 1) (w" -wll) 11g
2K
(98)
with probability at least g- d.
H.3 PROOF OF LEMMA
The distance of the second order derivatives of the population risk function s(:p) at point W and W lel can be converted into bounding P,, Pz, Pa and Pl, which are defined in (TOT. The major
30

---

Published as a conference paper at ICLR 2022
idea in proving P1 is to connect the error bound to the angle between W and Wirl, Similar ideas apply in bounding the other three items as well.
Proof of Lemma [2 From 17 we have
0 3 220
-(W(r);))
X K2
loft (w0
32
x) ())((( loft x)xx"
j2
+ K2
1
Exd (uw(w)) (w 1rll
in
( x)
2) (w
Irlt
(99)
1
and
(W:p)
Band Padl(uf (wn a) (w] ( )xxx
+
Ead Ra a) af
Iw, Jwn
K2
K22
(100)
where w. is the j-th column of W
Then, we have
f
f
(W*) owi, Jruj2
(W)
Ow
Exe
(w))
IpiT
x) (w) PiT x) o' d(w), x0) xx²
K2
1
K
Ex 0d
- x)) xx"
K²
o (w] x)) ää
K
σ)) कl (www, at) )m
KP
+
1
X
Eg
w T () (w I x)
f'wf
Eu ( x) &' (ww x)) i="
K2
1- X +
Pi
P2)
(Pa P.).
K2
K2
(101)
For any a E Id with ||al|2 = 1, we have
T P a eE (w IrlT (d' (w lolT x) - -'ww x:) (a (a=x)²
(102)
IT'T x) d'(w (a" x²² It is easy to verify there ex- ists a group of orthonormal vectors such that B {a, b, e, at, ... a with {a, b, e) spans sub-
where a E Rd. Let = d' (w (d' (w)
space that contains a, W) and w/ Then, for any æ, we have unique = such that
21,
22,
2d
a + b2 + 23C + zaaz. Also, since a ~ N'0,8 82 I2), we have z ~ NO,08 82 Ia). Then, we have
I - (w x)) o' w [p]T xx) 1|a"=
pp x>)l la x=x fz(21, 22, 23) 22)d2nd22d2s. =/ 1 (w) o' (w)
where x = 21a + z2b + C and fz (21, 22, 23) is probability density function of (21, 22, 23). Next, consider spherical coordinates with 21 ReosØ1, 22 Rsingr sinØz, 2g Rsingr cos(2- Hence,
I |= is easy to verify that ø' (w x) only depends on the direction of x and
10 (wf - 6'(wo (plT x11-
| cos 0112 2. fz on 02) R² sin 01 dRdo
(103)
fz (RR 02)) 1
1
R2
(2m82)²
22
31

---

Published as a conference paper at ICLR 2022
only depends on R. Then, have
(12
- 0 (1o72 (o/ - of
=
(10 10/7
(z/R))I Roos (x sin ondd
= -f00 R IRRJR 1.- 10a 2t
cos
1p|T sin Φ1 | (w) (x/ (x/ - o' ('w
(a) R)) d dØz
j2
230 !n 0o
{-²² /
(R)RR
sin 10'
- ("w (1 (a/ R)) iddides
po/
-35²
Emn (00f x)) o (w x)1
52
<35² Emn o (10}.ar) o (ung
IoTT x)),
(104)
where the inequality (a) is derived from the fact that |cosØl| S and
0 R
R
R² 282
(2m02)²
e
202 dR
(2Td2)
3
d(e
0
00
R²
R
282
d
(105)
(2T82)
R2 dR.
=3
R²
(2
Define set A {z) (w [o]T ()
|p|T x)) < 0}. If a E A1, then w x and w have different
signs, which means the value of d' d'(w? æ) and o' d'(w f2 that
Io|T x) are different. This is equivalent to say
1 (0(w x) - o'(w j2
Ip x>) ={
1, E
(106)
0, if E Af
Moreover, if x A1, then we have
(w0 82
|p]T æe
/low bolT
f2 x w xl1 10 60
wi ||00||2.
(107)
Let us define set A2 such that
w
x
||w7 wyz ll } (arww cos A pa.
12
1pl
w lla }. (108)
A
mnl S
1
11
|207, ll2
ll2
12
Hence, we have that
Em 10' (1o x)) - 00'6 (1o
[o]T x²12 -Ea ل6 (w - 26 ((ww!
Io.T x))
-Prob(x [ E A1)
(109)
<Prob(x: A2).
Since (00, 0 m. belongs to the uniform distribution on [-T, x²). we have
wyy lla
arccos
||
||
w
1/2
Prob(w A2)
tan(T arccos
J2
n
| 12
cot
cot(arcca (arccos
Jo
[p]
w
lla
(110)
(p]
l|
/ (p)
20
fz
l|2
π
[p]
||2
ja
32

---

Published as a conference paper at ICLR 2022
Hence, (104) and 110) suggest that
6 I
|,
w l12
||a.2.
(111)
π
σK
The same bound that shown in 111 holds for P2 as well.
P3 and P4 satisfy except for changing 82 82. Therefore, we have
|V2 F2
a" T
VV (V2 |p] - v f(W:p))a
max |||||111
8f (Wlrl:
f²
Σ
(W:p) Orjz
Sun, Own
12=1
K
K
(112)
Al| + Pall2 + (1 - X) P3 + Pallz) ||a 1221 12
12
K
K
1/
[P] J2
wi ll2
4(A02 + (1 - (1-2)
0 125l122110 12
K2
OK
1=
W|12
$ K
(20² + (1 - 2)82)
σK
where a E I Kd and aj E Fd with a = [a , ,
I INITIALIZATION VIA TENSOR METHOD
In this section, we briefly summarize the tensor initialization in (Zhong al. 2017 by studying the target function class as
K K
y =
y (6ww w x))
(113)
where 85 E R. Note that for ReLU function, we have 05 of x) = (ogn(t))o(lu)lee x)) Without loss generalization, we can assume o² E [+1,-1}. Additionally, it is clear that the function studied in (2) is the special case of (113) when D = 1 for all j. In addition, Theorem 5.6 in (Zhong et al.) 2017) ) show that the sign of V can be directly recovered using tensor initialization, which indicates the the equivalence of and 1 when using tensor initialization.
We first define some high order momenta in the following way:
M = Fe [ya) E TRd,
(114)
M₂ E2 y(x 8 x - 621)] Raxd
(115)
M3 Eun 1x x r)
dddxdd
(116)
where Eyg is the expectation over x and 203 = 69 z 8 z The operator & is defined as
2 Z =
24
2 v)
(117)
1=1
for any vector E Rd: and Z E xddd
33

---

Published as a conference paper at ICLR 2022
Following the same calculation formulas in the Claim 5.2 (Zhong et al. 2017). there exist some known constants v),, i = 2,2,3, such that
K
Mi
=
||w ll w.j
(118)
K
M2
Σ
1/2 ||
|l2 unzanz"
(119)
j=1
M3
Σ
1/
||wj ||2 w 803
(120)
j=1
w l in (16) is the normalization of wz.. Therefore, we can see that the information of (w } are separated as the direction of wy and the magnitude of wy in M1, M2 and M3.
where w = =w ///llll22
Mi. M2 and M3 can be estimated through the samples {<e,, Mn) 1.N a=1" and let M,, M2. M3 denote the corresponding estimates. First, will decompose the rank- K tensor M3 and obtain the バ By applying the tensor decomposition method (Kuleshov et al. 2015) to M3, the outputs, denoted by w. are the estimations of {syw) ; } K where 8j is unknown sign. Second, will estimate sj, vÿ and ||we ll through Mi and M2. Note that M2 does not contain the information of 8j because sy is always 1. Then, through solving the following two optimization problem:
01 arg min
M
11
w
a ERE
j=l
(121)
0g2 arg min
M Σ
222 w w
QvERK
The estimation of s, can given as
8y = (
Also, we know that |ل., is the estimation of |//|| and
0j sign(ā sign (2.5))
Thus, (0) is given as
(ig 1), ",, sign(
Subroutine Tensor Initialization Method
Input: labeled data D {(I,, Fn )n))
2: Partition 'D into three disjoint subsets Di, D2. D3:
3: Calculate Mj, M2 following (144) (115) using Dı, D2, respectively;
4: Obtain the estimate subspace V of M2;
5: Calculate M2 V, V) through Dz;
6: Obtain { K via tensor decomposition method (uleshov et al. 2015) M&(V, V. v):
7: Obtain &1, ag by solving optimization problem [21]
Return: w (0) sign(ā2,)) Vū, and v
(0) sign (ggn(02.)).-- 1,...,K K.
8:
To reduce the computational complexity of tensor decomposition, can project M3 lower- dimensional tensor (Zhong et al., 2017). The idea is to first estimate the subspace spanned by {wj | and let V denote the estimated subspace. Moreover, we have
Ms(V, D, V) En (P(")
(V' 3 V x) x) x))) E Rxxx
(122)
34

---

Published as a conference paper at ICLR 2022
Then, one decompose the estimate M3 ( V. w lies in the subspace V, we have VV W Then, Váj is an estimate of wj The
V) to obtain unit vectors {8,} R Since
initialization process is summarized in Subroutine
J CLASSIFICATION PROBLEMS
The framework in this paper is extendable to binary classification problem. For binary classification problem, the output y given input is defined as
Prob = 1 (W"
(123)
with some ground truth parameter W To guarantee output is within [0, 1]. the activation function is often used as sigmoid. For classification, the loss function is cross-entropy, and the objective function over labeled data D defined as
fD(W)
Σ (#n.Bn)ED
-nn log g (W; 2.,) - -1 yn) log(1 +
(124)
N
The expectation of objective function be written
Epfp(W) = [a - log(g W; a.)) (1 - y) log(1 (()
=E, (v)=) - y
W; ( (1 - v) log(1 (W:
(125)
=Eg log
- ; log (1 - g W; x.))
Please note that 125) exactly the same as (32 with
when the loss function is squared loss.
For cross entropy loss function, the second order derivative of 125 is calculated as
(W)
Un
+
yn
o'( d'w3f x x) (i) x xx==
(126)
tw, N (w;
(1 - 9 (: x))²
when j + k. Refer to (88) in (Fu et al. 2020) or (132) in Zhang al. 2020b), we have
Un (wf x) (w x))
ø' ( x)) x)
S K2.
(127)
g² (w))
@fr(W) Following similar steps in 900 from Defintion we know that ar aw, or belongs to the sub- exponential distribution. Therefore, similiar results for objective function with cross-entropy loss can be established as well. One can check (Fu et al. 2020) or (Zhang al. (022b) for details.
K ONE-HIDDEN LAYER NEURAL NETWORK WITH TOP LAYER WEIGHTS
For general onddhidden layer neural network, the output of the neural network is defined
g (W, x; Σ u))(wffx)
(128)
where v =[11,02, 02. [u]] E RKK Then, the target function can be defined as
1
g W -2
.T
(129)
K
for unknown weights R and v"
In the following paragraphs, we will provide a short description for the equivalence 219 and 2 in theoretical analysis. Note that for ReLU functions, have u.o(wuf f x) sign(v, )o un? ar).
35

---

Published as a conference paper at ICLR 2022
Without loss of generalization, we assume Bj. uz E {+1,- -1} for j E [K] | From Appendix I we know that the sign of oz can exactly estimated through tensor initialization. There, we can
Tocus on analysis the neural network in the form as
1 K
g (W;
Σ
(130)
j=1
Considering the objective function in and population risk function in 17 7. we have
0ʃ
0S
(W)
(W;
Ourk
2
N
(d(nn] ax ( xn)) E (o((( x) - ((uuffl 1o12 x))) 2r
K2N
K
M
1
( Tmm) - -6103 Tm am (b( xt) - (10 1012 x)) 23
K
m=1
K
N
|191
Σ
(d(un)) x.m)) =b(1))Ta)))a xn)) Ea (0(en x)) - Φه ob xz) 22
K
Σ
[ 3mm (b am)) F. R m) $lun u 2τ) 2b 11
K2M
N
Σ
(olwz x..) -b((0]² xm)) xn)) (f(w)(aan))a
- E. (d(1o x)) - cb( 1000 x0)
K2N
A
Σ
(dlu)) 3m)
Tem
(100 am))) Fm Ex (x( x)) Hlun x3) अ
K2M
(131)
which is exact the same as 89 Similar results can be derived for Lemma 12
Therefore, the
conclusions and proofs of Lemma and Lemma@does not change at all.
Additionally, fixing the second-layer weights and only training the hidden layer is the state-of the art practice in analyzing two-layer neural networks (Arora et al.] 2019b al Allen-Zhu et al. 2019 Safran & Shamir 2018 Li & Liang] 2018 Brutzkus & Globerson [017] Oymak & Soltanolkotabij 2018 Zhang et al. 2019). Additionally, as indicated in (Safran & Shamir 2018). training a one- hidden-layer neural network with all f fixed as 1 has intractable many spurious local minima, which indicates that training problem is not trivial.
"To see this, one can view (e.] Jun as the new ground truth weights, and the goal for this paper is to recover the new ground truth weights.
36


Reviews:
[{"review_id": "K8pD102PYc3", "reviewer": "Reviewer_LAdw", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "EDIT: After the discussion, I have raised my score to 6. Thanks to the authors for patiently addressing the various concerns and adding required appendices.\n\n\nThe paper studies an important problem of theoretically understanding how and why self-training works. The paper makes a genuine attempt to connect theory and practical insights and tries to distill some main takeaways from their analysis in  order to simplify understanding. However, I find that the paper in its current form does not push the boundaries on our understanding of self-training.\n\n(1) My main criticism stems from the fast that several works have studied self-training in the linear setting (as rightly mentioned in the paper). This paper claims to study two-layer networks which are more challenging due to non-convexities. However, the assumptions of the theorem (which the proof heavily relies on) essentially study the problem in a \"locally linear\" region around the optimal solution. The paper claims novelty in introducing the quantity \\lambda (weighting between the loss on the labels and pseudolabels while self-training) and an associated bound on the weighted objective to enable analyses. However, I really struggled with understanding the quantity \\lambda and what it implies (more details below). \n(2) The main self-training description (Table 1) does not mention \\lambda. It is only described in-text in equation 1. How does one set \\lambda in practice? I saw that the CIFAR-10 experiments used the same heuristic as in Carmon et al., but how does that relate to the analysis?\n(3) The setting of the paper is slightly weird to me as well. (a) model family: they claim to study a two layer network but essentially freeze the top layer weights such that they are ones and there's only one matrix being learnt. I understand that the problem is still non-convex due to the non-linearities but this restriction of all ones seems to be pretty strong to me and its unclear how to generalize to multiple layers. One of the main complications in studying multilayer networks is the interaction between the parameters of each layer which the current version of the paper doesn't deal with. (b) Regression instead of classification: this paper really analyzes regression and not classification (square loss is analyzed both at train and test). I believe this significantly makes the analysis easier since one doesn't have to deal with training only on confident predictions and so on---one single \\lambda factor can balance things out. In classification, we typically need some other kind of regularization\n(4) Related works: The paper also seems to be missing some important related works  such as \n[1] Y. Grandvalet and Y. Bengio. Entropy regularization. In Semi-Supervised Learning, 2005.\n[2] P. Rigollet. Generalization error bounds in semi-supervised classification under the cluster\nassumption. Journal of Machine Learning Research (JMLR), 8:1369–1392, 2007.\n[3] A. Singh, R. Nowak, and J. Zhu. Unlabeled data: Now it helps, now it doesn’t. In Advances in\nNeural Information Processing Systems (NeurIPS), 2008.\nMore generally, self-training has a very rich literature and the current draft doesn't situate this work well in terms of connections to previous work. The main claim of dealing with non-convex two layer networks is not very satisfying to me for reasons above. Are there any other additional insights or takeaways from this work?\n\n(5) In terms of writing, I found the paper generally well-written except for routinely talking about terms that are introduced later. For example, the highlights of the theory section was very difficult to follow because all the main quantities were defined later. \n\n", "summary_of_the_paper": "The paper theoretically analyzes self-training in neural networks with one hidden layer. Self-training is a popular semisupervised learning algorithm where a model uses large unlabeled data by training on pseudolabels generated by a teacher model trained on some small set of labels. The paper studies the generalization performance of self-training on a two-layer network under a Gaussian assumption on the inputs, and has some synthetic and CIFAR-10 experiments to show that the predicted theoretical rates (1/\\sqrt{ size unlabeled data}) roughly match empirical performance. ", "summary_of_the_review": "Overall, the paper studies an important problem (self-training on multilayer networks) and tries to connect some theoretical takeaways to practice. However, both in terms of theory and experiments, I found that the paper does not broaden our conceptual understanding of the method, nor does it introduce interesting theoretical tools for analysis. However, I believe there is a lot of scope to build on this work (relaxing assumptions, choosing the right model family and loss functions) to get a more convincing publication. ", "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": "5LcrvcLIoZ3", "reviewer": "Reviewer_SoSg", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This is an impressive, technically solid and well-written paper with some intriguing results. The authors take particular care in explaining the general strategy of their proof, not just in the main paper, but also in various parts of the supplementary. There may be some things to improve (that I would like to see in the camera ready version), but overall this paper is of significantly above average quality amongst accepted papers. There are a couple of typos but far fewer than average for papers published at top tier conferences. \n\n/\n============================================\nComments/questions on the general mathematical content.\n============================================\n\n\n1. I think the results presented are a mathematical curiousity highly worthy of further study: it is worth noting that the number of labelled samples is assumed to be greater than a multiple of the number of parameters, and the paper studies a regime which is not data-sparse *statistically*, but which is data-sparse from the *optimization* standpoint. A priori, it is reasonable to assume that the global optimum of the supervised learning problem that ignores the unlabelled data would still approach the ground truth and perhaps outperform the current model. Furthermore, note that both the labelled and the unlabelled datapoints are assumed to come from gaussian distributions, with different variances, thus there is almost no statistical information coming from the unlabelled data (the only possible information it could contain is about the mean (0) or about the fact that the data is isotropic. Thus the self-training strategy appears to function only as an optimization trick that relies on some form of self regularisation/momentum. \n\nQuestions for the authors related to comment [1]: \n\n1.1. Do you agree that the effect is only on optimization, or do you believe that the mean of the data or the isotropicity being communicated by the unlabelled data play a role? \n\n1.2. Do you think the result would still hold if the unlabelled data was chosen from a different non istropic gaussian distribution? \n\n1.3.  Honestly, do you think it may actually be possible to show the same convergence rates for the *supervised* learning problem (without relying on the unlabelled data at all) by borrowing from your techniques and doing away with the unlabelled data altogether? \n\n1.4. Did you try applying such a model on real data (e.g. image data) where instead of also picking real data for the unlabelled dataset, you draw samples from a suitable Gaussian? \n\n\n2.   I guess it would be nice to go into more details about the relationship between the results here and those in reference [2]: it is briefly mentioned at the top of page 2, but more details about the proof techniques in the appendix would be nice. It seems that in that reference, the authors study a completely different effect: they study classification assuming the classes are well-separated. In particular, there unambiguously is statistical information contained in the unlabelled data in this case.  It would be nice to have a one page summary of the results and proof techniques in [2] in the supplementary. \n\n\n3. You mention in Lemma 3 that although your main theorem 2 requires an assumption about the initial guess not being too far away from the ground truth, any initial point chosen with the \"tensor method\" satisfies this assumption with high probability. Trying to understand this method requires going through the very long paper [1] and parts of other papers (including [3]). It would be nice to have an extra section in the appendix which explains the \"tensor method\" from first principles, with suitable pointers to the relevant results. \n\n//\n =================================\nSmall issues with the maths/presentation\n==================================\n\n\n1. I think there is a slight problem with the proof of lemma 1: I guess the lower bound only holds for any constant strictly less than 1/11, but doesn't necessarily hold for the constant 1/11 as is claimed here. Indeed, first of ll on page 26, equation (76), I think there should be a minus sign instead of a plus at the second line. Then on a related note, I agree that combining equation (79) with Lemma 11 yields equation (80) (with the \\simless sign indicating there is an unstated constatant which can be arbitrarily small since one chooses it in the interpretation of the condition on p in equation (19), but combining this with equation 76 only shows the a lower bound of the type \"$a-o(a)$\" where \"$a$\" is the lower bound claimed. Hence the constant  should be anything slightly smaller than 1/11. \n\n2. On page 27, you use Lemma D6 from [1]. It would probably be better to write down the lemma in full and announce its role in advance at the beginning of the proof of Lemma 1. \n\n\n3. Question: I am not sure I get how you go from the third line to the fourth line in equation (78). Could you elaborate? (I agree only that with an extra factor of 2 it would be trivial).\n\n\n4. $\\kappa$ used extensively in the main paper (starting on page 4) but is only defined in the appendix. Even the fact that $c(\\kappa)$ denotes \"a constant that is allowed to depend on $\\kappa$\" (I presume) is worth mentioning explicitly (currently not even mentioned in the supplementary). \n\n\n5. I think the definition of the population risk function (equation (17)) has squares missing (the rest of the calculations are indeed consistent with the formula with the squares present). \n\n\n6. The proof of Lemma 10 includes statements about the properties of $\\mu$ which are not stated in the lemma statement (though they are mentioned in the main paper with a pointer to the supplementary). The lemma statement should be enriched. \n\n7. A little bit after equation (94) on page 31,  there is a $\\bar{\\omega}_j$ which is not defined. \n\n8 At the second line of equation (95) on page 31, there is a $\\phi'(x)$ which should be $\\phi'$ $([w_{j_1}^{[p]}]^\\top x)$.\n\n9. On page 32, on the line that starts with \"Also, since $x\\sim....$ it is claimed that $z$ is an isotropic normal distribution with variance $\\delta^2\\|a\\|^2$. I guess this is only true if you force $b,c,...a_d^\\perp$ to be normed, and also replace the \"a\" in the basis by a normalised version (currently it is not even stated that the vectors are orthonormal). I mean it is clear what you are doing here but there are minor corrections to make in the notation. \n \n\n10. I think there are minus signs missing inside the exponents in the equation  between equations (97) and (98). Furtheremore I guess $x_1,x_2,x_3$ should be$ z_1,z_2,z_3$. \n\n\n11. Question: How do you go from the third to the fourth line inside equation (98)? I know it is just computation but still, I would like to see details. \n\n12.  Question: In the main paper at the bottom of page 6, \"the lower bound on p means that $W^0$ cannot be too faraway from $W^*$\" \nDo you mean the *upper* bound on p? It seems lower bounds on the distance between $W^0$ and $W^*$ correspond to upper bounds on p and vice versa. \n\n\n\n13.  I guess at the top of page 27 one shouldn't write \"for any $\\\\|\\alpha\\\\|=1$\" since $\\alpha$ runs in the min in the equations below. It would also be nice to remind people that $\\\\|\\alpha\\\\|^2=1$ refers inside the norm to the flattened version of $\\alpha$. \n\n\n14 . Page 25, equation (71): should the last two (out of three) right hand sides be swapped ?It seems that $H_2^2(\\delta)$ is $O(\\delta^4)$ so it is the second expression on the LHS that should be in $\\Theta(\\delta^2)-\\Theta(\\delta^4)$. \n\n\n\n//\n===================================\nMinor typos/minor grammatical errors\n===================================\n\n1. Title: =====>  \"How *does* unlabeled data improve...\"\n\n2. Beginning of section 2: \"the objective function is to find a neural network...\"  ====> \"the aim is to find a neural network...\"\n\n\n3. Bottom of page 8: \"the block in white depicts all the trials are successful...\" =====>\" the white blocks correspond to succesful trials, while...\"\n\n\n4. The typography of the title for the appendix could be improved. \n\n5. In point 2 at the top of page 15, \"Then, utilising lemma 11...to obtain...\" (there is no verb) =====> \"Then, we utilize lemma 11 to obtain...\"\n\n6. Statement of lemma 4 on page 18: \"suppose ...be a matrix\" ===> \"let....be a matrix\"\n\n\n7. Bottom of page 19 (beginning of the last paragraph): \"by intermediate value theorem\" ====>\"by the  intermediate value theorem\"\n\n8. Bottom of page 19: \"Final, by...\" ====> \"Finally, by...\"\n\n\n9.Beginning of section E on page 22: \"by intermediate value theorem\" ====>\"by the  intermediate value theorem\"\n\n10. Beginning of section F on page 25: ...\"check that ReLU activation function satisfies the conditions\" =====>\"check that the ReLU activation function satisfies the conditions\"\n\n11. page 25, last line: \"\\mu is strictly decreasing function\"===> \"\\mu is a strictly decreasing function\"\n\n12. First sentence of section G2. \"The error bound between $....$ is dividing into bounding $....$, $...$, $...$, and $...$.\"\n=====>\"The task of bounding of the quantity  $....$ is divided into bounding $....$, $...$, $...$, and $...$.\"\n\n\n\n\n\n//===============After Rebuttal============\n\nI am happy that the authors tried hard to address all of my concerns, I will keep my original score.\n\n\n\nHere are my takeaways by theme: \n\nTensor Method:   In particular, I am very glad to see that they have taken the trouble to write a general explanation of the tensor initialisation method. The simplification by introducing the Psi_i etc. is particularly useful to understand the main point (as opposed to the precise definition of the constants given in the reference). \nThat is very helpful. However, it could be made even better by introducing the method from Kuleshov et al 2015, which is currently missing. \n\n\nMVT:   I am very happy with the response from the authors regarding the MVT. \n\n\n\n\nSecond layer weights: I am reasonably happy with the answer in appendix K. However, more details are needed. The analysis given here only successfully explains how to fix the proof of Lemma 2, not lemma 1 (which contains second order terms. I think the authors should also redact the relevant part of the paper and appendix better. Currently, it is not unambiguously stated at the top of appendix K that the extension proposed does not actually suggest *training* the second layer weights. I know it is explained (defensively) at the end of the appendix, but things should be explained more straightforwardly from the beginning. \n\n\n\n\n\n\n\n// =====After rebuttal: minor typos introduced in the revision=============\n\nP 27: Typiclly, for Relu function ====> TypicAlly, for THE Relu function\n\nP 28: when phi is THE Relu function\n\nP 37 =====> The expectation of THE objective function \n.... Is THE squarE loss\n\n\nP 39 ...can BE estimated exactly through.... (Missing verb)\n\n\n\nP 40 Conclusions does not change at al ======> conclusions DO not change at all.\n\n\n\n\n\n\n\n\n\n\n//\n===============================\nReferences: \n===============================\n\n\n[1] Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon. \"Recovery Guarantees for One-hidden-layer Neural Networks\", JMLR 2017\n\n[2] Colin Wei, Kendrick Shen, Yining Chen, Tengyu Ma. \"Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data\", ICLR 2021\n\n[3] Volodymyr Kuleshov, Arun Chaganty, Percy Liang. Tensor Factorization via Matrix Factorization. AiStats 2015. \n\n\n\n", "summary_of_the_paper": "In this paper, the authors make first forrays into the study of the theoretical properties of the following iterative self-training algorithm in a semi-supervised regression setting where we have N labeled samples and M unlabeled samples (and the ground truth is realisable):\n\n(1)  train the model on the labeled data, obtain pseudo labels for the unlabeled data by feeding them through the trained model \n(2)  train an auxiliary loss (see equation (1)) on the augmented dataset the includes the unlabeled data with the corresponding pseudolabels (the loss is a convex combination of the empirical loss on the labelled and unlabeled datasets), and \n(3) iteratively apply step (2) until convergence. \n\nIt is assumed that the ground truth is realisable (though without overparametrization assumptions), the labels are observed exactly (without noise), the model is a simple two-layer neural network with the second layer weights all fixed to one, and the labeled and unlabeled datapoints come from two isotropic Gaussian distributions of variances $\\delta$ and $\\tilde{\\delta}$. \n\nIn theorem 2, the following surprising result is shown: under some reasonable assumptions on the initial point and the number of unlabeled datapoints, for a suitable choice of the convex combination parameter $\\lambda$, the model converges towards the ground truth with an assumption on the number of samples which is weaker (by a constant factor at best) than what is required in the case where no unlabeled data is provided (which is a particular case of the case studied in [1])\n\nIn the more general Theorem 1, it is shown that under much weaker condition (without a requirement on the number of labelled samples), the model still converges towards a given convex combination of the ground truth and the initial point, and is guaranteed to outperform the initial model. \n\n\nThe main idea of the proofs is to define an auxiliary loss referred to as the population risk function (which estimates the risk taking as \"labels\" the images of the points by a convex combination of the ground truth and the initial point, cf. equation (17)) and to show (1) that the optimization lanscape of this functions is mild  (mainly proved in Lemmas 1 and 11), and (2) that this auxiliary function is close to the empirical risk which is minimized by the model (mainly proved in Lemma 2). The proofs of the techincal content of lemmas 1 and 2 rely both on computational geometry arguments and on existing results from [1]. \n\n\nExperiments are provided which show: \n(1) an excellent match between the dependence of the bounds and that of the observed generalisation gaps on various parameters and\n(2) that the unlabeled data indeed improves performance in data-sparse regimes on some real data. \n\n\n\n=======================\nReference:\n=======================\n\n\n[1] Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon. \"Recovery Guarantees for One-hidden-layer Neural Networks\", JMLR 2017\n", "summary_of_the_review": "This is an impressive, technically solid and well-written paper with some intriguing results. There are only very minor issues. \nThe paper could perhaps be made even better by adding further reader-friendly discussions of some of the related works to make it appeal to a wider audience, as well as perhaps by discussing the main results and their implications in more details. \n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3k2kMoF_v1", "reviewer": "Reviewer_uV34", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Pros**\n\n- This paper tackles an interesting and important theoretical question behind the success of self-training where the model is repeatedly retrained on pseudo-labels generated on unlabeled data.\n- The experimental results seem to support the theoretical claims extremely well, and the preliminary experiments on realistic models and data also agree with some of the theoretical predictions.\n\n**Cons**\n\n- There may be significant technical flaws in the proof. Both the proof for theorem 1 and the proof for theorem 2 hinge on what the paper referred to as the “intermediate value theorem” (eq 36 and later eq 56). However, the theorem being invoked here seems to be a vector version of the *mean value theorem* applied to $\\nabla f$. Had it just been a naming mistake, it would be ok, but I believe that this particular MVT might not exist. I was able to find a version for functions of scalar input and vector output in Rudin [1] which can also be found on the wikipedia page (https://en.wikipedia.org/wiki/Mean_value_theorem#Mean_value_theorem_for_vector-valued_functions), but this is actually an *inequality* instead of an equality. Incidentally, the same wikipedia section states \"There is no exact analog of the mean value theorem for vector-valued functions.\" I also found another version of the theorem on stackexchange (​​https://math.stackexchange.com/questions/1397248/mean-value-theorem-for-vector-valued-multivariable-function) which is an equality but requires an additional vector $a$ and still does not apply to the vector version that is shown in the proof. If there is a reference for this particular version of MVT, it would be nice to have it in the paper since it is, in my opinion, highly non-trivial if it does exist. This error could be plausibly fixed by using Taylor expansion instead of MVT but the it would require some changes to the proofs.\n- Aside from the problem above, the paper also makes a somewhat strong assumption that makes the result much weaker than it appears. Specifically, the paper assumes that the nework is of the form $g(x) = \\frac{1}{k} \\sum_{i=1}^k \\phi(w_i \\cdot x)$. Note that this function is **convex** in $W$! This is not what we conventionally call a *one-hiden-layer neural network* but rather just a convex function which is much less expressive.  In contrast, [2] uses $g(x) = \\sum_{i=1}^k v_i \\phi(w_i \\cdot x)$ which is actually a neural network. Although the optimization land scape with squared loss is still non-convex, the function class is much less expressive than a neural network. I am not sure if this function class is representative of non-linear models' behaviors on much more complex data. Although the experiments seem to suggest that it somewhat predicts behaviors of actual models, I think this discrepancy is misleading to say the least, if not overclaiming.\n- some notations are not defined. For example, I cannnot find the definition of $c(\\kappa)$. If I missed it, please let me know.\n\n**Questions**\n- In the appendix, shouldn't the population risk function $f$ use squared difference?\n- The results suggest the unlabeled data can be drawn from different distribution with some constraints (i.e., $\\tilde{\\delta}$) but what do those constraints translate to for real world data?\n\n**Reference**\n\n[1] Principles of Mathematical Analysis. Rudin, Walter.\n\n[2] Recovery Guarantees for One-hidden-layer Neural Networks. Zhong et al.\n\n\n-------\n**Update**\n\nI thank the authors for the detailed response.\n\nMy concern regarding MVT has been fixed and that part of the paper is now technically sound.\n\nFurther, I believe that the authors' extension for two-layer models is technically sound insofar as you believe the tensor initialization method is indicative of what happens in the training dynamics of real models. On the other hand, personally, I am not convinced by the tensor initialization argument and I do not feel the analysis is adequate for explaining what happens in the self-training procedure of actual models. \n\nIn the light of these changes, I believe the paper is now sufficient for publication and I am increasing my score to 6.\n", "summary_of_the_paper": "This paper presents the first theoretical analysis of self-training on one hidden-layer neural network with gaussian input. The paper shows that under certain conditions (e.g., the initialization is neither too far or too close to the optimal), iterative self-training on the aformentioned setting can provably recover the ground truth labeling matrix and offers improvement in sample complexity over supervised learning with only labeled data. Experiments validate the theoretical results.", "summary_of_the_review": "The paper tackles a challenging and important problem. While the experimental results seem to match the theoretical predictions, there are potential significant flaws in the proofs of the main theoretical results. The paper would have been a pretty strong paper, but due to these potential errors, I unfortunatley cannot recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1CrUVbsmJ1r", "reviewer": "Reviewer_7chM", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n1. The theoretical analysis is rigorous and contains novel technical contributions.\n2. The empirical findings evaluate many interesting predictions of the theory.\n3. The exposition of the proof sketch is clear and informative.\n4. Comparisons with previous works are clear.\n\nWeaknesses:\n1. Self-training can hurt accuracy in some settings (confirmation bias). I wish the theory discusses when this happens.\n2. I wish the theory offers guidance on how to improve self-training algorithms in practice.\n3. Section 3.3 talks about '0 generalization error'. I'm confused by this term since there is always estimation error.", "summary_of_the_paper": "This paper theoretically analyzes the iterative self-training algorithm with 1-hidden layer neural network. When the labeled and unlabeled data is generated from zero-mean Gaussian distributions with variances of different scales, it is shown that both the convergence rate and the generalization error decreases at a rate of $1/\\sqrt{M}$ where $M$ is the number of unlabeled data. Experiments on synthetic data and augmented CIFAR-10 corroborate theoretical findings.", "summary_of_the_review": "This paper is theoretical rigorous and has novel technical contributions.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies self-training for a one hidden-layer architecture, showing that with proper initialization self-training will improve over standard supervision. The reviewers appreciated the analysis and thought the results make sense. However, they did comment that the paper does not provide sufficient insight about the effectiveness of self-training and this should be discussed in the final version. There were additionally comments about the architecture choice (e.g., fixed output weights), and the authors should also address this.
Decision: Accept (Poster)