How Does Semi-supervised Learning with Pseudo-labelers Work? A Case Study
Authors: Yiwen Kou
Zixiang Chen
Yuan Cao
Quanquan Gu
Venue: ICLR 2023 poster (2023)

Abstract: Semi-supervised learning is a popular machine learning paradigm that utilizes a large amount of unlabeled data as well as a small amount of labeled data to facilitate learning tasks. While semi-supervised learning has achieved great success in training neural networks, its theoretical understanding remains largely open. In this paper, we aim to theoretically understand a semi-supervised learning approach based on pre-training and linear probing. In particular, the semi-supervised learning approach we consider first trains a two-layer neural network based on the unlabeled data with the help of pseudo-labelers. Then it linearly probes the pre-trained network on a small amount of labeled data. We prove that, under a certain toy data generation model and two-layer convolutional neural network, the semisupervised learning approach can achieve nearly zero test loss, while a neural network directly trained by supervised learning on the same amount of labeled data can only achieve constant test loss. Through this case study, we demonstrate a separation between semi-supervised learning and supervised learning in terms of test loss provided the same amount of labeled data.

Published as a conference paper at ICLR 2023
HOW DOES SEMI-SUPERVISED LEARNING PSEUDO-LABELERS WORK? A CASE STUDY
WITH
Yiwen Kou', Zixiang Chen', Yuan Cao2.3, Quanquan Gu
DDparrmeett of Computer Science, University of California, Los Angeles Department of Statistics and Actuarial Science, The University of Hong Kong "Department of Mathematics, The University of Hong Kong evankou@ucla edu, chenzx1 96cs ucla. edu, yuancao@hku. hk, qguêcs ucla.edu
ABSTRACT
Semi-supervised learning is a popular machine learning paradigm that utilizes a large amount of unlabeled data as well small amount of labeled data to fa- cilitate learning tasks. While semi-supervised learning has achieved great success in training neural networks, its theoretical understanding remains largely open. In this paper, we aim to theoretically understand semi-supervised learning ap- proach based on pre-training and linear probing. particular, the semi-supervised learning approach we consider first trains two-layer neural network based the unlabeled data with the help of pscudo-labelers. Then linearly probes the pre- trained network small amount of labeled data. We prove that, under certain toy data generation model and two-layer convolutional neural network, the semi- supervised learning approach achieve nearly zero test loss, while neural network directly trained by supervised learning on the same amount of labeled data only achieve constant test loss. Through this case study, demonstrate a separation between semi-supervised learning and supervised learning in terms of test loss provided the same amount of labeled data.
INTRODUCTION
With the help of human-annotated labels, supervised learning has achieved remarkable success in several computer vision tasks (Girshick al.) 2014 Long al. 2013 Krizhevsky al., 2012 Tran et al. 2013). However, annotating Harge-scale datasets (e.g.. video datasets with temporal dimensions) is consumnnn and costly. order reduce the number of labels used for training while maintaining good prediction performance. a variety of methods have been proposed. Among these methods, semi-supervised learning (Scudder 1965 Fralick 1967 Agrawala 1970), which leverages both small amount of labeled data and large amount of unlabeled data to improve learning performance, one of the most widely used approaches. It has been shown to achieve promising performance for wide variety of tasks, including image classification (Rasmus et al. Springenberg 2015 Laine & Aila 2016). image generation (Kingma et al. 2014; Odena Salimans et al.) 2016). domain adaptation (Saito al. 2017 Shu et al. 2018
2015
2016
Lee et al.
2019
and word embedding (Turian et al., 2010: Peters et al. 2017).
One of the popular semi-supervised learning approaches is pseudo-labeling (Lee et al. 2013). which generates pseudo-labels of unlabeled data for pre-training. This approach has been remarkably suc- cessful in improving performance on many tasks. For example, in image classification, one can first train a teacher network on a small labeled dataset and use it pseudo-labeler to generate pseudo-labels for large unlabeled datasets. Then one can train a student network on the combination of labeled and pseudo-labeled images (Xie et al. 2020 Pham al., 2021b Rizve et al., (021). In order to theoretically understand semi-supervised learning with rrcudo-labelers Oyyak & Gulcu 202T) considered learning a linear classifier the Gaussian mixture model setting. They are able to show that in the high dimensional limit, the predictors found by semi-supervised learning are cor- related with the Bayes-optimal predictor. Frei et al. (2022c) further proved that the semi- uumi-supervieed learning algorithm
provably converge to the Bayes-optimal predictor for mixture models. How- ever, their analyses are limited to linear classifiers, and cannot explain the success of semi semi-supervised learning with neural networks.

---

Published as a conference paper at ICLR 2023
In this paper, we attempt to theoretically explain the success of semi-supervised learning with pseudo-labelers in training neural networks. Specifically, we focus on a toy data model that con- tains both signal patches and noise patches, where the signal patch is correlated to the label while the noise patch is not. We consider semi-supervised learning with pre-training and linear probing. In the pre-training state, train two-layer convolutional neural network (CNN) dataset with pseudo-labels. We then fine-tune the pre-trained model using linear probing on a small amount of labeled data. We provide a comprehensive analysis of the learning process both pre- training and linear probing stages.
unlaheled
The contributions of our work are summarized as follows.
We theoretically show that with the help of pseudo-labelers CNN can learn the feature representa- tion during the pre-training stage. Moreover, the learned feature highly correlated with the true labels of the data, even though the true labels are unknown and not used during the pre-training stage.
Based on our analysis of the pre-training process, we further show that when finear-probing the pre-trained model the downstream task, the final classifier can achieve near-zero test loss and test error. Notably, these guarantees of small test loss and error only require very small number of labeled training data.
As comparison, we show that standard supervised learning cannot learn a good classifier under the same setting. Specifically, we show that, even when the training process converges to a global minimum of the training loss, the learned two-layer CNN can only achieve constant level test loss. This, together with the aforementioned results for semi-supervised learning, demonstrates the advantage of supi-super learning over standard supervised learning.
Notation. We use lower case letters, lower case bold face letters, and upper case bold face let- ters to denote scalars, vectors, and matrices respectively. For a scalar v, we use [x+]+ to denote max(# (x; 0}. For a vector v = (Ui, .. " Ta)T,
we denote by ||v||a == (Ei= vf) its &g norm, and use supp(v) := {j Uy # 0} to denote its support. For two sequences {as} } and {bu}, we denote a* = (bg) if |ay| < Clbbal for some absolute constant C, denote a (2(bb) if by O(ax), and denote ag = (b²) if axl I Clbba and a = l(bb)). We also denote ag = o(b;) if lim la /bgl = O.
Finally, we use (-),, (()) and (2-)) to omit logarithmic terms in the notations.
RELATED WORK
Semi-supervised learning methods in practice. Since the invention of semi-supervised learning in |Suuder] ( (1965); Fralick (1967); Agrawala (1970), wide range of semi-supervised learning ap- proaches have been proposed, including generative models (Miller Uyarl 1996; Nigam et al.]
2000), semi-supervised support vector machines (Bennett & Demiriz 1998| Xu et al. (007]20009
graph-based methods (Zhu al. 2003 Belkin et al., 2006 Zhou et al. 2003 3. and co- co-training (Blum
& Mitchell 1998), etc. For a comprehensive review of classical semi- -umei---peeeieed learning methods, please refer to Chapelle et al. (2010); Zhu & Goldberg (2009). In the past years, a number of deep semi-supervised learning approaches have been proposed, such generative methods (Odena 2016
Li al., 2019), consistency regularization methods (Sajjadi et al., 2016 Laine & Aila 2016
Ras-
mus et al. 2015 Tarvainen & Valpola, 2017) and pseudo-labeling methods (Lee al. 2013 Zhai
et al. 2019:; Xie et al. 2020: Pham et al. 2021a). In this work, we will focus on lecudo-labeling
methods.
Theory of semi-supervised learning. To understand semi-supervised learning. Castelli Cover (1993] 1996) studied the relative value of labeled data over unlabeled data under a parametric as- sumption on the marginal distribution of input features. Later, series of works proved that semi- supervised learning can possess better sample complexity or generalization performance than su- pervised learning under certain assumptions on the marginal distribution (Niyogi 2013 Globerson the ratio of labeled and unlabeled samples (Singh et al. [0088 Darnstädt 2015), while Balcan & Blum (2010) provided a unified PAC framework able to analyze both sample-come comple-complexity and algorithmic issues. Oymak & Gulcu (2021): Frei al.) (2022c) considered semi-supervised learning with pseudo-labers by learning a linear classifier for mixture models and convergence to Bayes-optimal predictor.
et al. (017) 2017)
2

---

Published as a conference paper at ICLR 2023
Self-supervised learning in practice. A closely related learning paradigm to semi- sumi-supee learning is called self-supervised learning, which creates suman-designe supervised learning prob- lems to leverage natural structures and learn representations from unlabeled data. Representative self-supervised learning approaches include contrastive learning and pretext-based self-supervised learning. Contrastive learning (Caron et al.] 2020 He et al. (2200] CCen al., (020) aims to group similar examples closer and dissimilar examples far from each other by utilizing a similarity metric, while pretext-based self-supervised tries learn good representation from pretext tasks generated from the unlabeled data to facilitate downstream learning tasks. In practice, various pretext tasks have been proposed, which include (1) generation based ones such as colorizing grayscale images (Zhang et al. 2)16). image inpainting (Pathak et al.) 2016), image and video generation with GAN (Goodfellow et al. 20144; Brook et al., 2018: Karras et al. 2019; Vondrick et al. 2016: (Tulykkvv et al. 2018); and (2) context-based ones such as image jigsaw puzzle (Noroozi & Favaro (016),
geometric transformation (Gidaris ct al. 2018 Jing et al. 2018), frame order verification and recog-
nition (Lee al. 2017 Misra al. 2016 Wei et al. 2018). The semi-supervised learning approach
with pseudo-labelers studied in this paper is related to pretext-based based supervsee learning because the unlabeled data with pseudo-labels can be seen particular pretext task.
Theory of self-supervised learning. In order understand self seef-suuereised learning, there is a line of work towards understanding contrastive learning (Saunshi et al. 2019: Tsai et al., 20200] Mitro-
vic al., 2020 Tian al., 2020; Wang & Isola 2020] Tosh et al. 2021b HaoChen et al. 2021
Wen & Li. 2021 |, Saunshi et al. (022). which is one of the most used sel supeevvvee learning ap-
proaches based on data augmentation. Unlike contrastive learning, the theoretical understanding of pretext-based self-supervised learning is still rather limited. The only notable works are Lee et al.
(2020) and Wei et al. (2020). Lee et al. (2020) proved generalization guarantees for self-supervised algorithms using empirical risk minimization on the pretext task under certain conditional indepen- dence assumptions. |Wei et al. (2020) proved that under an "exxansioon" assumption, the minimizer of the population loss based on self-training and input-consistency regularization will achieve high prediction accuracy. Since semi-supervised learning with pseudo-labelers can be seen as a special case of pretext-based self-supe learning (the pretext task is generated by the pseuuo-labelers), we believe the case study in the current paper and its theoretical understanding can shed light on pretext-based self-supervised learning well.
Feature learning by neural networks. Our work is also closely related to several recent works that study how neural networks learn the features. Allen-ZZhu & L.j (2020a) showed that adversar- ial training purifies the learned features by removing certain "dense mixtures" in the hidden layer weights of the network. Allen-Zhu & Li (202bb) studied how ensemble and knowledge distillation work in deep learning when the data have "muliiview" features. Zou et al. (20TT) studied an aspect of feature learning by Adam and GD and showed that GD can learn the sparse features while Adam may fail even with proper regularization. Notably, there are two concurrent works studying the be- nign overfitting phenomenon in learning neural networks: Frei et al. (2022a) established theoretical guarantees for benign overfitting of two-layer fully connected neural networks with zero training error and test error close to the Bayes-optimal error, while Cao et al. (022) studied the benign overfitting phenomenon in training a two-layer convolutional neural network (CNN), achieving ar- bitrarily small training and test loss. Our work studies a different aspect of feature learning afforded by remi-supervised learning versus supervised learning: given a small amount of labeled data, semi- supervised learning can learn the features with the help of pseudo-labelers, while supervised learning fails to leam the features and tends to overfit the noise in the training data.
3 PROBLEM SETUP AND PRELIMINARIES
In this section, we first give brief overview of the semi-supervised learning pipeline using pseudo- labelers. Then we will introduce our data model, the convolutional neural network, and the detail of the training algorithms considered in this paper.
3.1 SEMI-SUPERVISED LEARNING PIPELINE WITH PSEUDO-LABELERS
In this paper, we consider kind of semi- cumi-supereieed learning (Xie et al. 2020 Pham et al.) 202 Rizve et al. 2021), which leverages pseudo-labeler for pre-training. Such semi-supervised learn- ing method is related to a special kind of pretext-based self-supervised learning, whose pretext task
3

---

Published as a conference paper at ICLR 2023
Task Head
Shared Feature Representation
Apretrain
-
Φ
Downstream
Adownstream
X
Figure 1: The general pipeline of semi-supervised learning with pre- pre-training and linear probing.
is designed by generating pseudo-labels for unlabeled data with the help of pseudo-labelers ZZhai al. 2019). The typical pipeline of this kind of semi-supervised learning is shown in Figure] | Moreover, the case study we carry out is shown in Figure 2 The pretext task trains a two-layer con- volutional neural network with the help of pseudo-labelers, and the downstream task trains linear probe using the pre-trained models.
3.2 DATA DISTRIBUTION
Inspired by recent work (Allen-Zhu & Li, 2020b Zou al. 2021 Shen et al. 2022 Cao et al., 2022). consider toy data model where each data input x consists of two patches and x(2), where each patch has d dimensions. We focus on binary classification task, and present our data distribution D the following definition.
Definition 3.1. Each data point (x. y) with Rademacher random variable;
[x(1), x E R2d and y {-1, is of x x(2) is
generated as follows: the label y is generated given by the feature vector y v, the other is given by noise vector & that is generated from a d- dimensional Gaussian distribution ((0, of (I-vV vv /llv[2)). We denote by DD the joint distribution of (x, y). and denote by Dx the marginal distribution of x.
The most natural way to think of our data model is to treat patches x(!) and (2) as the embedding of the image data: one of them signal which is label-dependent, and the other one is the noise that is habel-independent, For simplicity, we assume that the noise patch is generated from the Gaussian distribution N NO0, of -I-V vv |[v]l> to ensure that the noise vector is orthogonal to the signal vector v. and only consider the case where the data consists of signal patch and one noise patch. However, our results and proof techniques can be easily extended to cover the setting with non-orthogonal signal/noise and multiple signal/noise patches. With this simple data model, in this case study we aim to show the effectiveness semi-supervised learning and explain the mechanism behind semi-super learning with neural networks.
Since the positions of signal and noise sifier with a convolutional structure that applies the same function to each patch. More specifically, consider learning CNN with ni labeled examples S' {(x,, = generated from the dis- tribution D and n. unlabeled examples S {x generated from the marginal distribution Dx- where n; significantly smaller than the dimension d. we only use the labeled data, the CNN can easily overfit the training dataset by memorizing the noise patches &,, Consequently, the CNN will perform badly on the fresh test data. Therefore, our case hard learn without using unlabeled examples.
specified in Definition 3.1 It is natural to clas-
3.3 SUPERVISED LEARNING MODELS
For supervised learning, we consider a two-layer CNN whose filters are applied to the patches x (1) and (2)) respectively and parameters in the second layers are set to be +1. Then the CNN can be written fw(x) = (x) fw (x) where fw(x)+1 fw(x)-1 are formulated as
m f (x) Σ
xllw,, (1))) + ( x. x()))]
j=1
(3.1)
2m
(x) Σ
[o((w,,(1)) o x
j=++1
4

---

Published as a conference paper at ICLR 2023
Seml-supervised pretraining
Supervised downstream task training
Unlabeled Dataset With Psoudo Labels
Neurl Network
Output
Objective Punction
Labeled Dataset
(w(xt)
de (Fw: (ww (w2()))))))))))))) (e)
)4)
(x)
(w
loss(fW(aa).f3 (nal.ss)
Objective Function
82)
Fu(Fnu)
(oss(f((1..)..))
Ioxa (er (wrrtt)).x))) (1))
loss (fr-(tz))
K Different Pseudo Label Selection
fwt (X), fwr (x),... fwg
loss (s. (far(2..))
Figure 2: Illustration of our model. The left figure characterizes semi-supervisee pre-train schema: NN is trained by minimizing errors between pseudo-labels 7 and predictions fw (x). After semi-
supervised pre-training finished, the learned parameters { (W & serve as pre-trained models and are adapted to a downstream task using linear probing, as shown in the right figure.
Here is activation function ReLU (4 2). m is the width of the network, w, R denotes the j-th filter, and W is the collection of all filters {w, 1w1 Given labeled training dataset S' [x1x Dm) train the CNN model by minimizing the empirical cross-entropy loss
LS (W) =
(W(),
where L,(W) = {V/ fw())) with {(2) = log(1 (1 + exp(-2)) denotes the individual loss for the training example (x,, V1). We minimize the empirical function (W) with gradient descent as follows
w [++1) - V Ls (W(),, w NO of jE [2m].
where 7 > 0 is the learning rate and do defines the scale of random initialization.
3.4 SEMI-SUPERVISED LEARNING MODELS
For semi-supervised pre- mre-training we assume that we have access to K pseudo-labelers {f F
TR=1-
The accuracy of k-th pseudo-labeler ps. E (1/2, 1). Then we use K pseudo-labelers
generate K pseudo-labeled dataset {S*] where Sp { [xx Vn.a) Tk.. f (xx)) ) 1=1 Next we solve K pre-training tasks with two-layer CNN models [fw,, K defined in (3.T) using { respec- tively. Note that our result cover K 1 as special case. where there is only one pseudo-labeler.
We consider learning the model parameter We by optimizing the empirical loss of both pseudo- with weight decay regularization
labeled dataset S₂ and labeled dataset S' = {(x],, 1/)
m
LSEUS (Wa)
L.(W
Σ L. (Wws) + W ;==
Th + YAA
where À the regularization parameter, L, (WR) [(Tess (x:)) denotes the individual loss for the eseudo-labeled data (x,, M...) L. (W+) Elyl fw. (x()) denotes the individual loss for the labeled data (x), v(). Our result can cover 71 O, which corresponds to the case that there no labeled data during pre-training. In light of this, our semi-supervised learning framework will reduce to special kind of pretext-based self-supervised learning, where the pretext tasks are generated by pseudo-labelers.
We use gradient descent to minimize the regularized loss function LsSus (W+). Starting from initial W(U)
{w k.j. [2m]). gradient descent update rule is as follows
(U)
(++1) (t) kJ
k.j 17 V Twr, (W("), (0) (( jE [2m], A [K]
where 7 > 0 is the learning rate and do defines the scale of random initialization.
Downstream Task: Linear Model. The supervipe pre-training gives us K CNN models with parameters ( [Wi)k-- Based on them, for the downstream task, we consider linear model
K
Oa(x) = Σ Caffw
5

---

Published as a conference paper at ICLR 2023
where ag R denotes the trainable weight for the k-th pre-trained model. Then, given {fw; } and labeled training data 5 {(x] )/) consider learning the downstream linear model parameter a by optimizing the following empirical loss
(a)
Σ lih ga(x()) n
1
n
We initialize a as an zero vector and optimize the empirical loss by gradient descent with learning rate 1j. i.e.,
a (t (*) 17- (a a =
MAIN RESULTS
In this section, we present the main theoretical results in this paper. We start with a condition that is required by analysis.
Condition 4.1. The strength of the signal is ||v]lž (d), the noise variance is op O
where 0 < c < 1/8 small constant, and the width of the network satisfies m = polylog(d), We also assume that the size of the unlabeled dataset nh 22dd'), and labeled data For both supervise learning and semi-supervised learning settings, we initialize the weight with dp = (dd33/4). For semi-supervised learning, we require X = o(d3/4) and assume that there exists constant C' such that for all pseudo-labelers their test accuracy Pk 1/2 + C.
6(1).
Since generate the noise patch from the Gaussian distribution, the strength of the noise patch is Ik 1 Rs dl by standard concentration inequalities, which is larger than the strength of the signal patch |v112 (d). Therefore, Condition 4.1 defines a setting with large noises. The condition of d >> Ra > further ensures that learning is in sufficiently over vee-paaraeterizee setting. Here we only require the neural network width m to polylogarithmic in the dimension d and require the psudolablers to perform better than random guess.
Theorem 4.2 (Semi- supervisd Learning: Pre-training). Let k E [K] and consider the semi- supervised pre-training of fw, (x). For any test data point (x, y). denote y = 5 (x). Then un- der Condition 4.1 after To = 6(d- training iterations with learning rate v = O(d-11), the trained neural network can achieve nearly test error on the distribution D: P(x.))=oly- o(1).
( (x)
Theorem 4.2 characterizes the prediction power the feature representation learned the pre- trained models using unlabeled data. For any test data point (x, v). the sign of y can be predicted based on W (x) with high probability.
Theorem 4.3 (Semi-supervised Learning: Downstream). Let {ff w (r))) k==1 be the neural networks trained according the K pre-training tasks, and consider the learning of the downstream task (oto } Under Condition 4.1 after T" = O(d iterations with learning rate based in {f "
17 (1),, with probability 1 o(1,, the obtained (TT)) satisfies:
Training error is 0: n Σ [ys Parry (x,) S 0]
Test error and loss nearly 0: P(x.y)~Dly 9atr")) (x) <0 o(1), = o(1).
T shows that the feature representation learned based on the semi-supervised pre-training can ensure small training and test errors for the supervised downstream task. Notably, this result holds even though we assume that there are only a constant number of labeled data. This shows that semi-supervised learning can significantly reduce the need for large labeled training dataset. For comparison, we also have the following guarantecs on the performance standard supervised learning of CNNs.
Theorem 4.4 (Supervised Learning). Under supervised learning setting, after gradient descent for T D/dd0//ac0--3//11y" iterations with learning rate 7) Odd-1-2),, then there exists T such that with probability 1 o(1) the CNNs defined in (3.1 with parameter ()) satisfies:

---

Published as a conference paper at ICLR 2023
Training loss is nearly zero: L (W()) = o(1)
Test loss is high: LD (D((()) (1).
Theorem 4.4 shows that although standard supervised learning can train CNN model with nearly zero training loss, the obtained CNN model generalizes poorly to test data. Comparing Theorem 4.4 with Theorem 4.33mm4.wws shows that the generalization of semi-supervised learning and supervised learning are largely different. The reason behind this difference is that, the pre-training, with relatively large number of unlabeled training data, helps learn a feature representation that captures the feature in our data model, while direct application of supervised learning can only memorize the noises E, i E [n:] in the training dataset, which is independent of the labels of the data.
A recent line of work (Oymak & Gulcu 2021 Frei et al. 2022c) studies the semi-supervisce learning methods with pseudo-labelers. Our results different from theirs in several aspects: (i) considering learning with CNNs rather than a linear model, so the problem is highly non-convex with various local minima, which makes the optimization analysis more challenging; (ii) the Bayesian optimal predictor is no longer unique for CNNs. Therefore, we measure the quality of the learned features via downstream task instead of making a comparison with the Bayesian optimal predictor; (iii) They can only deal with the case where the teacher network (pseudo-labeler) is the same as the student network (Frei et al. 2022c) or the case where the teacher network ggeudo-labelery is at least as complex as the student network (Oymak & Gulcu| (021). However, our teacher network (pseudo-labeler) not specified and can be any structure, such as a linear network. Therefore we can handle the case where the student network is more complex than the teacher network, one of the most natural settings for supesiueee learning with pseudo-labeler (Xie al. 2020).
5 PROOF SKETCH
In this section, we present the proof sketch for the semi-supervised learning setting. And the proof sketch of the supervised learning setting is given in the appendix.
Semi-supervised Pre-training. We consider learning K functions fw, (x), k E [K] based on the pre-training. Since the learning process of these K functions be analyzed in exactly the same way, here we only focus on the learning of one of these functions. For simplicity of notation, we drop the subscript k in the following proof sketch.
Our study of the pre-training focuses two aspects of the training process: feature learning and noise memorization. Specifically, we aim to monitor how the filters the CNN model learn the feature vector v and the noise vectors & s. Therefore, introduce the following notations.
( = max (w) v), (1) max -(w,)) (1) v),
(1)
15)5m
15/5m
A := max
-(w) j v), 1 = max (w)) (t) m 15m52
(t)
v),
m 15m$2m
r := max (w E.), 1((t) max (w) <)) r(() 15752m
max r(t) (E(Rg)
max ((t))
}.
max
15j52m
[E(mu]
(5.1)
Based on the above definitions for r E [+1), larger 7 implies better feature learning along the positive feature direction v, while a larger (, implies better feature learning along the negative feature direction vv Moreover, a larger (1) implics a higher level of noise memorization.
Based on the update rule of gradient descent, for the inner products (w j v) and (w)") E)), for j E [2m]. E [r.]]. we can obtain iterative equations in (A.I). With the help of the iterative equations and definitions in (.I). can further show the following lemma.
Lemma 5.1. Assume we use both unlabeled data with pseudo-labels generated by the pseudo- labeler and labeled data for the training of our CNN model. Then for r {=1), let T, be the first iteration that { reaches (l1/m), then for t E T,], we have
A(+))= > (1 nA) 7 + n C. O(d) (A)))=- . (+1},
A((+1) < (1 - 1/A) X()) E (+1},
r((1)) < (1 - na) p(t) n .
7

---

Published as a conference paper at ICLR 2023
where C' is defined in Condition 4.1
Lemma 5.2. Assume we use only labeled data for the training of our CNN model. Then for i E [ma] let T be the first iteration that r((() reaches (11/m) then we have
A(+1) - (1 - n/) N + (dd) (()))))))()))))))))))))))))(,)))
(
A(+1) s (1 - ny> -A r {+1].
r((+") 2 (1 1 nA) r + ((d++2c) ( (T((0))0-1 [mi]. for E [0,
Based on the results in Lemma 5.1 we can observe that both pseudo-labeled and labeled data are used for training, the CNN will learn the positive direction of the feature vector v. while barely tending to fit the negative direction of the feature vector or memorize the noise. And if only labeled data are used, the CNN will fit noise faster than feature, which can be seen from Lemma 5.2
Leveraging Lemmas 5. and 5.2 we can obtaín following Lemmas 5.3 and 5.4 which characterize the magnitude of feature learning and noise memorization.
Lemma 5.3. If both pseudo-labeled and labeled data are used to train CNN, for r E {+1}, let T, be the first iteration that A reaches ((1/m) respectively, Let Th (a Then, it holds that (T)) @(1), A Ö(d and T ((d for all & [o]
Lemma 5.4. If only labeled data are used to train CNN, for i E [m]] let T be the first iteration that
r((0) reaches (11/m). Let Tj = maxiejmi Tv. Then, holds that A, = OOd t). A, = (d- for {=1} and r ((1) for i [mi].
The above results indicate the deviation between the two settings. The reason is that assume we consider a sequence {x,} with iterative equation Zt+1 = It + +-- C,2t If we only use labeled data, as shown in Lemma 5.2 r(()) has C, ((d++2)) while A has C. @(d), therefore I7(0)
increases faster than A In contrast, we use both labeled data and aseudo-labeled data, C. will be ((d"~2r) for r((() and ((d) for A leading to slower increasing speed of r((().
Downstream task. After the pre-training, we have obtained K CNN classifiers {f (rt)) ] k==1 Now
w we train the second-layer parameters a with the training data whose true labels are available. The following lemma shows that the / -ormm of will increase with a logarithmic order.
Lemma 5.5. For any learning rate 17 = (1), we have ||a(*) [| = log(t)/@(1) For any labeled data (x4, vl) S", we have with high probability that y/ fwis (x²) = | || @(1). For any newly generated data (xx, y) D, we also have with high probability that y fwi (x) aa Ō(1).
With the help of the above lemma and note that training error and test error are related to y- fwi (x) and test loss is related to ||a (2)7))),, we can prove that after T = (dd"-1/n) iterations with learning rate 1) = @(1), the model can achieve nearly zero training error, test error, training loss and test loss.
6 EXPERIMENTS
In this section, we perform numerical experiments on synthetic datasets, generated according to Definition 3.1 to verify our main theoretical results. The code and data for our experiments can be found on Github In particular, we set the problem dimension d = 10000, labeled training sample size n1 = 20 (10 positive samples and 10 negative samples), pseudo-labeled training sample size nu 20000 (10000 positive samples and 10000 negative samples), feature vector sampled from distribution (0, I) and noise vector sampled from distribution AO ofT) where o, = 1010
For semi-supervised learning task, we have a linear pseudo-labeler with test error 0.196 + 0.044. Then, we use this classifier to generate pseudo-labels for n, 20000 unlabeled samples in order to help semi-supervised learning. After that, for pre-training, we use these pseudo-labeled samples and ni labeled samples together to train CNN with network width
20, activation function
(=)) = [=]3 regularization parameter X = 0.1 and learning rate 7 = x 10-4 Besides, we
https//gittuuu.cc///aaam/SSS Pseudo Labeler
8

---

Published as a conference paper at ICLR 2023
1.75
155
Featue Learing PAR
0.75
0.33
Feat ane Loa F9N4 40 Natio Memon maa
203
6013
1000
20
300
Figure 3: Visualization of the feature learning and noise memorization in the training process. (Left: Semi-supervised, Right: Supervised)
Semi- supervisd
Supervised
trait
Downstream
Training error
0..055+
0
0 0.4982+ 0.0208
Test error
0
O
Training loss
0.0150=0.0022 0.415510.0448 0.2200=0.0886
(6.473315.031) 10 0.6931
Test loss
0.0182=0.0021
Table 1: Training error and loss, test error and loss for semi-supervised and supervised learning.
initialize CNN parameters from .V0 (f), where dg = 0.1 x d/4/4, After 200 iterations, we can obtain CNN model with training error close to the error of pseudo-labeler and zero test error, according to Table [ And for downstream task, we use my labeled samples to train linear probe. By applying learning rate 7) = 0.1 and after T 100 iterations, we can obtain final model with low training and test loss as well 100% training accuracy and test accuracy.
For supervised learning task, directly ny labeled data to train CNN with network width m = 20, activation function (=) = [z] learning rate 7) = 1 x 10-4, After 200 iterations, we obtain CNN with 0 training error and small training loss, about 0.5 test error and high test loss, which indicates supervised learning will give a model that behaves badly and even no better than a random guess.
Moreover, for synthetic data experiments, we also calculate the inner products maxye]m] (w,)) (2) v)
and max max (t) ( E.), maxie[nj (w } i.c. A and (()), representing feature learning and noise memorization respectively, to verify our key lemmas. The results are reported in Figure 3 It can be from Figure that under sumi-supe learning setting the algorithm will the feature learning will dominate the noise memorization though the noise patch has a larger norm than the signal patch, while under the supervised learning setting, the algorithm will entirely forget the feature but fit noise. This verifies Lemmas 5.3 and
7 CONCLUSION AND FUTURE WORK
In this paper, we study semi-supervised learning with pseudo-labelers and provide theoretical un- derstanding of the success of semi-supervised learning. We show the advantage of semi-supervised learning over supervised learning through a case study. By considering simple data model and two-layer CNN, we present a comprehensive analysis of the training procedure from a beyond-NTK feature learning perspective. We prove that the final classifier of a sumi-supervieed learning sce- nario can achieve near-zero test loss and error with only small number of labeled training data, while its supervised-leant learned counterpart fails to achieve the same performance with the same data complexity.
In the current paper, we only focus on the simplest possible data and neural network models to study semi-supervised learning. For example, the second layer the CNN fixed during the training. What if the second layer is trainable? In addition, the stride is the same as the filter size in the current CNN, and it reasonable to have the stride be smaller than the filter size. On the other hand, it would be interesting to consider linearly non-separable data (Shi et al.) 2022 Frei et al. 2022b Damian et al. 2022) and ReLU activation function with the help of pre-activation noise (Allen-hhe & Li 2020a). We leave these extensions future works.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their helpful comments. YK, ZC and QG are supported in part by the National Science Foundation IIS-2008981 and the Sloan Research Fellowship.
REFERENCES
A Agrawala. Learning with probabilistic teacher. IEEE Transactions Information Theory, 16 (4):373-379, 1970.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005 2020a.
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.09816, 2020b.
Maria-Florina Balcan and Avrim Blum. A discriminative model for semi-supervised learning, Jour- nal of the ACM (JACM), 57(3):1-46, 2010.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (11), 2006.
Kristin Bennett and Ayhan Demiriz. Semi-supervised support vector machines. Advances Neural Information processing systems, 11, 1998.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Pro- ceedings of the eleventh annual conference on Computational learning theory, pp. 92-100, 1998.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arXiv preprini arXiv::809. 1009, 2018.
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer con- volutional neural networks. arXiv preprint arXiv:2202.06556, 2022.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systems, 33:9912-9922 2020.
V. Castelli and T.M. Cover. The relative value of labeled and unlabeled samples in pattern recog- nition with an unknown mixing parameter. IEEE Transactions on Information Theory, 42(6): 1102-2117, 17, 1996. doi: 10. (0.1109/1..55600.
Vittorio Castelli and Thomas M. Cover. On the exponential value of labeled samples. Pattern Recognition Letters, 16(1):105-111, 1995. ISSN 0167-8655. doi: http:://do..rr//1.0001/// 0167-8665199))00744...
Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-supervised learning. The MIT Press, 2010.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference Learning Theory, pp. 5452. PMLR, 2022.
Malte Darnstädt. An investigation on the power of unlabeled data. PhD thesis, Bochum, Ruhr- Universität Bochum, Diss., 2015, 2015.
Fralick. Learning to recognize patterns without a teacher. Theory, 13(1):57-64, 1967. doi: 10.
IEEE Transactions on Information
10

---

Published as a conference paper at ICLR 2023
Spencer Frei, Niladri S Chatterji, and Peter L Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. arXiv preprint arXiv:2202..5592,, 2022a.
Spencer Frei, Niladri S Chatterji, and Peter L Bartlett. Random feature amplification: Feature learning and generalization in neural networks. arXiv preprini arXiv:2202.07622 2022b.
Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners to strong learners mixture models. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2022c.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv:1803.0777 2018.
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for ac- curate object detection and semantic segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 580-587, 2014.
Amir Globerson, Roi Livni, and Shai Shalev-Shwartz. Effective semisupervised learning on mani- folds. In Conference on Learning Theory, pp. 978-1003, PMLR, 2017.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for sulf-super deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-97338 2020.
Longlong Jing, Xiaodong Yang, Jingen Liu, and Yingli Tian. Self-supervised spatiotemporal feature learning via video rotation prediction. arXiv preprint arXiv:1811.11138 2018.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4401-4410, 2019.
Durk P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling, Semi-supervised learning with deep generative models. Advances in neural information processing systems, 27, 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Advances in neural information processing systems, 25, 2012.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint arXiv:1610.02244 022.6....222,2... 2016.
Dong-Hyun Lee al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges representation learning, ICML, volume 3, pp. 896, 2013.
Hsin- Ying Lee, Jia-Bin Huang, Maneesh Singh, and Ming- Yang. Unsupervised represen- tation learning by sorting sequences. In Proceedings of the IEEE International Conference on Computer Vision, pp. 667-676, 2017.
Jason Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo. Predicting what you already know helps:
Provable self-supervised learning. arXiv preprint 20x.i::2008.000666. 2020.
Seungmin Lee, Dongwan Kim, Namil Kim, and Seong-Gyun Jeong. Drop adapt: Learning discriminative features for unsupervised domain adaptation. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 91-100, 2019.

---

Published as a conference paper at ICLR 2023
Yang Li, Quan Pan, Suhang Wang. Haiyun Peng, Tao Yang, and Erik Cambria. Disentangled varia- tional auto-encoder for semi-supervised learning. Information Sciences, 482:73- 85, 2019.
Jonathan Long, Evan Shelhamer, and Trevor Dareel.. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-34400 2015.
David J Miller and Hasan Uyar. A mixture of experts classifier with learning based on both la- belled and unlabelled data. In M.C. Mozer, M. Jordan, and T. Petsche (eds.), Advances in Neural Information Processing Systems, volume 9. MIT Press, 1996.
Ishan Mísra, C Lawrence Zitnick, and Martial Hebert. Shuffle and learn: unsupervised learning using temporal order verification. In European Conference on Computer Vision, pp. 527-544. Springer, 2016.
Jovana Mitrovic, Brian McWilliams, Jacob Walker, Lars Buesing, and Charles Blundell. Represen- tation learning via invariant causal mechanisms. arXiv preprint arXiv:2010.07922 2020.
Kamal Nigam, Andrew Kachites McCallum, Sehastian Thrun, and Tom Mitchell. Text classification from labeled and unlabeled documents using em. Machine learning, 3932):103-134, 2000.
Partha Niyogi. Manifold regularization and semi-supervised learning: Some theoretical analyses. Journal of Machine Learning Research, 14(5), 2013.
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European conference on computer vision, pp. 69-84. Springer, 2016.
Augustus Odena. Semi-superviee learning with generative adversarial networks. arXiv preprint arXiv:1606.01583 2016.
Samet Oymak and Talha Cihad Gulcu. Statistical and algorithmic insights for semi-supervised learning with self-training. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2536-2544, 2016.
Matthew E Peters, Waleed Ammar, Chandra Bhagavatula, and Russell Power. Semi-supervised sequence tagging with bidirectional language models. arXiv preprint arXiv: 2017.
Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le. Meta pseudo labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11557-11568, 2021a.
Hieu Pham, Zihang Dai, Qizhe Xie, Minh- Maan-Thang Luong, and Quoe V. Le. Meta pseudo labels. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021b.
Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko. Semi- supervised learning with ladder networks. Advances in neural information processing systems, 28, 2015.
Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah. In defense of pseudo- labeling: An uncertainty-aware pseudo-label selection framework for semi-supervised learning. In International Conference on Learning Representations (ICLR), 2021.
Kuniaki Saito, Yoshitaka Ushiku, and Tatsuya Harada. Asymmetric tri-training for unsupervised domain adaptation. In International Conference on Machine Learning, pp.
PMLR,
2017.
Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transfor- mations and perturbations for deep semi-supervised learning. Advances in neural information processing systems, 29, 2016.
12

---

Published as a conference paper at ICLR 2023
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. Advances in neural information processing systems, 29, 2016.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Con- ference on Machine Learning, pp. 5628-5637. PMLR, 2019.
Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. arXiv preprint wrxxi:2202.140::3 2022.
H. Scudder. Probability of error of some adaptive patter-recoonition machines. IEEE Transactions Information Theory, 11(3):3633371, 1965. doi: 10.1 1..1109T..1955.00539..
Ruoqi Shen, Sehastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation.
In International Conference on Machine Learning, pp. 19773-19808, PMLR, 2022.
Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis on feature learning in neu- ral networks: Emergence from inputs and advantage over fixed features. arXiv preprint arXiv:2206.01717. 2022.
Rui Shu, Hung H Bui, Hirokazu Narui, and Stefano Ermon. A dirt-t approach to unsupervised 2018.
domain adaptation. arXiv preprint
Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now helps, now it doesn't. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (eds.). Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008.
Jost Tobias Springenberg. Unsupervised and semi-supervised learning with categorical generative adversarial networks. arXiv preprint arXiv: 1.0390, 2015.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged con- sistency targets improve sumi-supervised deep learning results. Advances neural information processing systems, 30, 2017.
Yuandong Tian, Lantao Yu, Xinlei Chen, and Surya Ganguli. Understanding self-super learning with dual deep networks. arXiv preprint arXi::2010.00577 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic
posterior information to linear models. Journal of Machine Learning Research, 22(281):1-31, 2021a.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. Journal of Machine Learning Research, 22(281):1-311 2021b.
Du Tran, Lubomir Bourdev, Rob Fergus, Lorenzo Torresani, and Manohar Paluri. Learning spa- tiotemporal features with 3d convolutional networks. In Proceedings of the IEEE international conference on computer vision, pp. 4489-4497, 2015.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. De- mystifying self-supervised learning: An enformatioonthhoretiiin framework. arXiv preprint wwxiv:2006.05576. 2020.
Sergey Tulyakov, Ming- Yu Liu, Xiaodong Yang, and Jan Kautz. Mocogan: Decomposing motion and content for video generation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1526-1535, 2018.
Joseph Turian, Lev Ratinov, and Yoshua Bengio. Word representations: simple and general method for semi- superviee learning. In Proceedings of the 48th annual meeting of the association for computational linguistics, pp. 314-3844444 2010.
13

---

Published as a conference paper at ICLR 2023
Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba. Generating videos with scene dynamics. Advances in neural information processing systems,
2016.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity the hypersphere. In International Conference on Machine Learning, pp. 9929-9939. PMLR, 2020.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622 2020.
Donglai Wei, Joseph J Lim, Andrew Zisserman, and William T Freeman. Learning and using the ar- row of time. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8052-8060, 2018.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference on Machine Learning, pp. 11112-11122. PMLR, 2021.
Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le. Self-training with noisy student improves imagenet classification. Proceedings of IEEF/CVE conference on computer vision and pattern recognition, pp. 10687-10698, 2020.
Zenglin Xu. Rong Jin, Jianke Zhu, Irwin King, and Michael Lyu. Efficient convex relaxation for transductive support vector machine. Advances in neural information processing systems, 20, 2007.
Zenglin Xu, Rong Jin, Jianke Zhu, Irwin King, Michael Lyu, and Zhirong Yang. Adaptive regu- larization for transductive support vector machine. Advances in Neural Information Processing Systems, 22, 2009.
Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S4I: Self-supervised semi- supervised learning. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 1476-1485, 2019.
Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In European confer- ence on computer vision, pp. 649-666. Springer, 2016.
Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
Xiaojin Zhu and Andrew B Goldberg, Introduction to semi-supervised learning. Synthesis lectures on artificial intelligence and machine learning, 3(1):1-130, 2009.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings the 20th International conference Machine learning (ICML-03), pp. 912-919, 2003.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108, //371, 2021.
14

---

Published as a conference paper at ICLR 2023
A PROOF FOR SEMI-SUPERVISED LEARNING SETTING
We consider learning K functions fw,, (x), k E [K] based on the pre-training. Since the learning process of these K' functions can be analyzed in exactly the same way, here we only focus on the learning of one of these functions. For simplicity of notation, we drop the subscript & in the following proof for Sections A.1 A.2 A.3
A.4 A.5
A.6 and A.7
A.1 GRADIENT CALCULATION
Lemma A.1 (Gradient Calculation). The gradient of loss function (s( with respect to weight parameters W, is
V Lsus (W) = q
Σ Gi
((
vit v kw,
-. EE:)
+
Σ ball (l(ww: v)[2 1/4 v I(w,, 401 E + x w,:
for 1 S S m; and
mn + nu Σ (KW3,, -v- v Ik Ei)
V w, Lsus (W)
bool ([(w)) 3/4 v)12 3/4 v [( +<w,, <
+ x wy:
for m + S S 2m, where- - l' (Mi fw (x:) = exp /w x )/(1 + exp (-ū; expl-ti
fx(x))) is
denoted by a and -y' fw(x)) expl-y/ (x))) expl-y/ fw(x(]) is denoted by by
Proof of Lemma
A.I. When 1 ك S m.
V w (Tr
fw(x;))
((ii Sw (x:)) Di Vw,
C. Di V fw(x))
-csii (d He v)) yf of ((w,, Eil) E.)
= qesse (lW,, yi v)14 1--1_ v + Ei .g))
Vw, (1/ fw(x())
E' (v/ fw fw(x')) 3/4 V fw,f((x))
bb 2.- (w(())
--butl (o'((w vi v)) 1/. o' ((w;, (1) E
= -qbbah (l(w,, v>1 ./6 v [ww,, 4014 <
and when m + +115 +isj 5 2m,
Vw, (ūi fw((x)) = qa (I(w), v)1 y/ v + &w 4 Ei)
V w, Cv/- fw(xx)) = qb.a/ (I(w). 1/4 vi1. 2/ v + 1019 13 EE) Note that V Vwy Iss (W)= = EnT,, V wy (Te (x))) + + V W (1/ (x) W.,, we have proved the lemma.
A.2 INNER PRODUCT UPDATE RULE CALCULATION
When the model is trained by gradient descent, the update rule can be formulated by
(++1) w.)
( 77 Lsw()))
[2m].
(A.1)
We study the performance of entire training process from two perspective: feature learning and noise memorization. Mathematically, we will focus on two quantities: (w/() v) and (w(), ..). And then have following lemma for the inner product update rule.
15

---

Published as a conference paper at ICLR 2023
Lemma A.2 (Inner Product Update Rule). The feature learning and noise memorization perfor- mance of gradient descent can be formulated by
(w) (++1) v) = (1 - naa) (w)
gT
Σ
yeTich 20 ((w)) Ui ->1+=~11v1
+ nu
v1
3/4 v 113
+
==1
(w) ((( E1) = (1 - ,7>)
n + nu (w) E1)
gm
Dic
12 (w] (0) " (i)
+ Kw 4MI (4% si))
(w) (++1) .1)== = (1- 1/)) (w) <
gra
Tidp" "oe "E; E/>
nu + nu
(0 kwwj 10) <01 (E) <n) + u/by
where j [2m], 1 [n.]] and Uj 1 [ssism] 1 Im [5)52m]
Proof of Lemma A.2 According to Lemma A. and gradient descent update rule (A. we have
Thi
w wett)) = =11-1A) n1a)-
(0 w/
+ ni + Au
grai
GDi (kw,, U: v)12 y/ v + ((w,, A -.)
+ Σ bey' (ko 1/ vM1 vl v [<w, - E!
Taking inner product with feature vector v and noise patch & and note that v is orthogonal to E: according to the data model, we have
nh 4T ([W,, i "
(w) (12)) v) = (1 1/A) (w/)) v)
qTjl ni + nu
vall + [w,,, 4/1 (5..v)
(1) vo (I(W)) v> V kw EN1 (597 vi))
+ 1=1
qmuu
nu Σ V /0
(1 - 17A) (w])
v)
+
.// 2>14 *1
1=1
(w) (11) Ei) = (1 177) (w) Eii + qr,
([(W,, v>12 "v. Ei) + '
+ nu
(1 w/ 2) - "v(v Ei) + 1( "4/ Ei)) )
(1 7aa (w/")) Ei) ni + nu
mu
> ai Kw)) (, Ei)
Σ v/ull
kw 90 - Ei)
16

---

Published as a conference paper at ICLR 2023
and
(w) (w] (1+1) E2 = 01 (1)- (w."), (
g nu
Dic
(9) [w]] 9 EM1 (E: E/
m
j/6y [w 10wp/....1 4014 (E) (E%
+
which completes the proof.
A.3 ESTIMATE ( (O) (T)) (2
Let A
maxisiSm (w v), A = m8xm+15j$2m - -(w v). A
(0) v), which characterize the feature learning m/X (w) v). A maxigism -W
aspect of training process. An easy way to distinguish between ( and (1) is that A should be large while A should be small.
Let ( = max1gs52m (W., (w, E i E [m,]. M max (w,, +) [mi], which character- ize the noise memorization aspect of training process with respect to a particular sample.
gax I which characterize the noise memorization as- pect of training process regardless of the sample index.
Let ( max maxigjn.] D
We first provide the concentration inequality for 7 and A, in the following lemma.
Lemma A.3. With probability at least - 46 with respect to the randomness of initialization of w, have
A B|A
V 8 log ()))ollll2.
1 (t)
A 1|A V 18log Aollvll2
and
E v Vlog(m)oollv/// ll |[2 Vlog(m)oollvlle: (+1).
Proof of Lemma A.3 Note that A10) maxisism
Ao max -(w] v).
(0) maxx+1sis20 (w (0) v) and A = max - (w v), NO0, I1) and v is fixed vector. Therefore, (w) (0) v) ~ N (0) - (w, v) NO for all 1 < j S 2m and A A r E {+1} are identically distributed. Therefore, without loss of generality, we only need to discuss the concentration of ( By applying Lemma C.1 have
P( - E |[
> S 2e 20
By applying Lemma
C.2 we have
EA (0) /
Vlg(m)))
which completes the proof.
Then we provide concentration inequality for r in the following lemma.
Lemma A.4. Suppose that d *(loggm(n, m))/5), 2(log(1/6)) Then with probability at least 1 ō,
vo
< <T(())
< 2 22/og(16mmm, + mm)/5) Goop d, for all i [nu].
4
0o
Vd
< p((()) < 2m/log(16m(m + mm//)) Voo,Vd, for all E [n]]-
4
17

---

Published as a conference paper at ICLR 2023
Proof of Lemma A.4 By Lemma C.3 with probability at least 1 - 6/4,
pp v d/ 12 16 - v3/2- vd for i E [mu]: op a/v2 - || S /3/2 on vd, for E [m]].
(A.2)
Therefore, by Gaussian tail bound and union bound, with probability at least 8/4.
E.)1 S l2log(8m/8) oo 0ollE:112 for i [nu]. (w) (0) < I (ww (0) -11 S v (2log(8m/8) oo | for i E [mx].
(w; (0) E.) - (ww (0)
(A.3)
Note that (( V d/4 (w, {i) an absolute constant and therefore by the condition on m, have
BoOPVd
s (1:0)
BoopVd
max (w) (0)
E.i)
jE
@nop V
P
max (w (0) E.)
4
[mmm
2m
doop Vd
(w) (0)
3 <.)
5
and
Cnop Vd
21 8
IP
(1))
On the other hand, according to A.2 and A.3) we have
P(T 2 log( 16m nu + m))/o) Toop vd)
max (w) E.) - 22/log(16mmm/ + + 000, 000 jm
and
P(( S 2 (o0mmmmmmm,, + m))/5) Vdd 2 21 4'
which completes the proof.
A.4 STAGE GD: ON-DIAGONAL FEATURE LEARNING
In this stage, A((0) and A! respectively increase magnitude @(1/m) and (( A and r()) remain small, the same magnitude as initialization. In order to characterize the behaviour of feature learning and noise memorization during Stage we decompose the analysis into following three parts:
1. First, in Lemma A.9 we provide a lower bound of the update rules of on on-diagonal feature learning term of (00) A. lower-bound their increasing speed, and an upper bound of off-diagonal
feature learning term A A to indicate their decrease.
Second, in Lemma A. we provide upper bound of the update rules of noise memorization
term (t) to upper-bound its increasing speed.
Third, we provide useful lemma, which is derivation of Claim C.20 in Allen-Zhu & Li (2020b), which is called tensor power method. By applying tensor power method, we will prove that:
When 7(0) reaches ((1/m) at Tı, A()) and (1) remain a magnitude no more than initialization.
When (0) reaches ((1mm) at T- 1, A_ and (()) remain a magnitude no more than initializa-
tion.
18

---

Published as a conference paper at ICLR 2023
A.4.1 UPPER BOUND LOWER BOUND FOR X _ AND 1 ,
We first consider Stage of GD when (=1) {A A - (mm
In this stage, first prove following lemma:
Lemma A.5. As long as max,e(=1) (A,9, A// 2 ( we have c == = Swic (xi)
= and ( = = (1/: fwoo (x()) remains = o(1).
Proof of Lemma A.5 Note that {(z) = log(1 + exp (-z)) and -x(x) = exp (-=) (1+exp (-z)),
=
and without loss of generality assuming y: yi can express &f follow:
D lat(w) ())+o((w) E.))
1 = -f((e(() = Emilootiw w))+ &.i)l
-m e (ollww) ())++(((?) &())I
(t), v)) dominates o((w) ,)) for j E [m], which will proved later by using tensor power method, we have
Since ((W)))
2m 2m (Iw) (l)+ .6))] (.))]
E ((w))) v))+ (lower order temm)
+ 1 w))+o((w) .e)))) [e)i)]
2m
On the one side,
1
2 -o()
2 ((w) 5 +))+ (lower onder term)
(
(1 po-t +1 @( 12 +1 2 2+
+
On the other side, according to Lemma follows that
5.3 we have A = Ö(d- and p = ((dd)tt),
m (A +m(r(())0-
STh o((w)") (8) v) flower order term)
+ (
1 + (1)
ET- E + (lower tem)
+ +1+0(1)
1 o1) 1
o(1).
1+1+0(1) o(1)
Therefore, have cf") = 1/2 + o(1) if y1 yı 1 and other cases (0i 1/i -, Dt -yi ((2) can be proved a similar way.
By applying above lemma, can obtain following lemma:
Lemma A.6. For any 5 < 1/2, with probability at least 1 28 over pseudo-labed generated by the leeule-,,bller, we have
1 Phu
(t) Dance
-(p 1)
log g o(1),
V
8mm
i=1
where o(1) is with respect d.
If we denote {(x;, yi)ly; 1 E [nm]]} as St, ((x,, y/ 1lı -1, i [m.]]] S-1, 1S1] as nı and |S_1| as n. we have with probability at least 46 that
R1
(t) - (p- )
Danc
log z +0(1),
Th
8m1
and
1 8-1
Σ
Ceyce (t)
- -(p- 2) < <v
1
log + o())
8n_1
5
19

---

Published as a conference paper at ICLR 2023
Proof of Lemma A.6
First, according to Lemma
A.5
we have
1
Dilk
+
Dilk
yi = o(1)
(A.4)
Yhu
Ra
2
2nu
2na i=1
1=1
i=1
Then, according to Hoeffding's s inequality when =
=-1,bg bi = 1, we have
Ruu Dili
2n
2 21) S 2exp
-2exp (-2n
Tu
Vin (a. - b,)3
Note that the pseudo-label Ti generated by the pseudo-labeler takes y/s with probability p and - with probability 1 p, have E.
Σ thu Dillil
1
E [iiy 2p 1. It follows that
nm
1) 2 21)
Dilli P 2
S 2 exp ( (-8mm
2T
and therefore
Ru Dilli
p - 1 /
log
(A.5)
2n
8
holds with probability at least - 25. According to (A.4) and A..) we have
1
1
yeyss
p
2
log
+ o(1)
2n
8nu
8
which verifies the first statement of the lemma. And the other part of the lemma can be proved in similar way.
L
According to above lemma and note that Tuy 71, Th-1 = w(1), we have further that
Ra
G.ccc (t)
(p 2) o(1),
g (1)
- (p- 2) = o (+1), (A.6)
Tu with high probability.
7hp
Besides, we also need an approximation about n, and n- which is given as the following lemma: Lemma A.7. For (=1}, holds with probability least 1 25 that
nhu 2
nr
log
2
8'
where ny := [[(x,, yilly: = r, E [mn]]}]
Proof of Lemma A.7
Note that n, En 1 1x r),r E {+1) where X takes label +1 or -1 with equal probability 1/2, according to Hoeffding's 's inequality, we have
Σ
nh
1[x, =
[[x, = r1] 21) s 2exp (-
212
r E {+1}.
nn
and it follows that
P((n,
PP
nu
2t) < 2 exx
(-
2t
r {+1}.
2
n
leading to
na
n,
log
2
2
with probability at least 28.
For labeled dataset S' [(x/, " also have
20

---

Published as a conference paper at ICLR 2023
Lemma A.8. For {=1). it holds with probability at least 1 - 28 that
14
71 2
n
<
log
2
8'
where n2. := H[(x v/luy/ r, [mi]l
Then we are prepared to estimate a lower bound of increasing speed of (10) and an upper bound of decreasing speed (4) in the following lemma.
Lemma A.9. For A := maxig/Sm (w) v) and A == maxm+15js2m (w
(w,), 10, -v), we have
with high probability that
(++1)) 2 (1 nA) T( + 11 p (D-
1 2) O(d) rrE
2
For A := maxmm11552m (w)) / v) and A == maxisism (w) v), we have with high prob-
ability that
A(+)) S (1 naa A r
Proof of Lemma A.9 We first prove the former incquality. Let j = arg m (0) v) and 1, then we have
note that uj. Lisism) 1 [m+igig2m]
X (1+1) 2 { (1+1) .v)
(1 m/A) (w
v)
997 mn 7h
yone (1) (w We v
+ Σ Kw
09 144 1
Then we respectively estimate terms + and *.
For note the definition of j that A11) = (w) (2)
3- v) and note the increasing property of A and
A (0)
O with high probability, we have (w v) > 0. It follows that
Uobee (t) (8) (W Ui v>1 1w11 Σ
y
Σ
1 (9. v>12-11 1|v13
IES:
EES-1
y:
(1)
[( (t)
v ,,,
iES
Σ ViDic(")
-11113 (1()))--
i1
1
+ o(1) -Ivll (A(1))-1
n1
pp-
(A.7)
2
where Si : (xx v/) yy last equality is due to (..)).
1, E [nm]]. S-1 =
((x,, M1 11)lu = 1,, E [nm]]]- m [S] and the
For *, similarly we have
2/2 v)12
MM
Σ
(0) [( v
Σ
( -
iES
iES
v
jz
FS
Σ
((()) 1|v13 (A
iES
n4i (
- =(((
1| (1(1))--)
(A.8)
21

---

Published as a conference paper at ICLR 2023
where Si = [xxx v.llv = 1.1E E [mil), 8'11 = ((x2 = 1, E [mal]: n4 =|S|| and the last
equality is due to Lemma A.3
According to (A.7) and A.8) we have A(t1)
2 (1 - -)/)) A + 9n
1
+ =()) 11v13 (110) + +n, ( + ((]) 1|v1 (1(9)--1)
11
(p-
+ nu
2
(1 - 17/) A + qu
(p-
1
+ o(1)) 11113
(A
quna
( + b()) ||v| (A19)
+ nu
2
nu + nu
(1 -7))- A(0) + q7
n1
(p
1
=
ni
= (²= =()))) 1|v12 (1/9)--
n1 + nu
2
n + nu
(L n7)- A + qm
71
(p 2
1
nl
1
=
-1v (1 (A.9)
m2 + na
mu + nu
2
According to Lemma A.7 and Lemma A.8 and note that n =()) nuu w(d*),, we have for
that with probability at least 1 - 40
n2
1
n
1
uu
(p 2
11 1
+ 11 + Th
12 + n0
2
2(n + nu)
2(1 + nun)
2
[0
Ya 2
(p-
a |n
2
1
711 7u
11 Ylu
2
log
1
log
1/
1 2
p
11 + nu
2
m1 + 72u
θ
= ((1)
Therefore, note that ny = w(n) and ny = ((). we have
p mn + nh
n'
1
uu
1 (p-1)
+
71
+ o11)
111 + 14
2
2(m + na)
2(m + n.n)
1
1
p - 2) t 0(1)
(A.10)
2
Plugging A.10 into A.9 we have
1(+1) 2 (1 17))
1
(p- 2) =o(1)) 11v12 (A
+ qm
2
(1 .) A + r (p
1 (dd) (1
(A.11)
2
which verifies the first inequality of case r = 1 in the lemma
Let j argmaxm++55f5 (w -v) and note that uj.. ppsism) 1 11415/52m) -1, we have
A ((t1)² 2 (1] -v)
(1 (1-m)) mpd) (w/ v) +
97 n + nu
Σ /
[w jorr 2/4 -v)1 liv12
22

---

Published as a conference paper at ICLR 2023
For + note the definition of j* that _ (W -V v) and note the increasing property of Xo]
and _ with high probability, we have (w) ("., v) 0. According (A.6). it follows that
(t)
Σ Vr (w [w yor, Us vi1 livl =
Vi (1) ((w - v 1
iES
= Rn (p-2
+ o(l) 11v112 -A_)))
(A.12)
2
where S-1 = ((xx,))) vi)lia 1, [mo]], n- 1-1= m-1=11-11-
For *, according to Lemma A.5
similarly we have
(0) /
v/14 livl2
(0 -
1 =n'rr nn'r (1=() (1 9-1
LESL
(A.13)
where 5' = {(x] vlllol = 11, E [mil] and n²_ = 1S'-1/-
According to (2.12) and (A.13), we have
(1+1) 2 (1 - A) (e) + q7
n- (p 2
n'_1 1 TM
=0(1))
1Iv112 (1
71 7h
nu
2
(A.14)
According to Lemma A.7 and Lemma
A.8. and note that n
G(1), nu w(dr), we have for
that with probability at least 1 - 46
n-
1 p
n²___
1
nu
(p-1) 2
71
1
71 + P4
2)
+ 11) + Mu
2
2(n + nu)
2(m + nn))
2
Ry 1 2
(p 2
|n<1
mi
2
1
711 70
1i
2
log
1
log 1
1 2
p 2
T1 + nu
m1 + 7uu
θ
Tu
o(1).
Therefore, note that n, = w(n)) and n, = w(1. we have
(p- 1 n' 1
(p (p-2)
11 + 2(m + no,)
1
1
+ o(1)
11 + 17
2
ni + nu
2
2(m + na))
2
1
1
p - 2
+ o0
(A.15)
2
Plugging (A.15)
into A.14
we have
((+1) (1 m7)) A + qm
1
(p- } + =o(1)) ||v12 (1
1
2
= = (1- - mソ) 7 + n
(p- 2
1 ) (dd) (1))
(A.16)
which verifies the first inequality of case -1 in the lemma.
23

---

Published as a conference paper at ICLR 2023
Next, we prove the latter part of the lemma. L²tz²
(w) (c+1) v). then we have:
A 1(++1) (w (1+1) v)
(1 17)) (w (1)
v)
q7 m Y0u
Σ
(2) (2)
(( J yr +) 1v12
(t)
1/4 v314 11vl2
For according AA.6). we have
WDce 12 (Ww Jz yr v)1 1
Σ
V:Uic ((w
10 11vl2 + Σ
V:Dic ( -v>1- 11v12
VES,
$ES_1
Σ VrTic()) 1(///) v) +
Σ UiDic!!)
/ - |v12
iES1
iES-1
=n
- 2
=01) (
+ n (p =
[( -11 0,
and for * it's obvious that
j Jo 1vv22 2 0.
*
Therefore, it follows that
A(411) < (1-1)) f v) $ (1 (1-
Let j&ر arg maxi S (w// (1+1) -v), then we have:
x(t11 = (w/tt -v)
(1 1/A) (w/f) -v)
277
Σ 1=
((w jan: De ~
ni nu
+ 1 [(
1=1 jes 3/ - v)1 2 11v12
(1)
$ (1 T/A)
(w
(t)
Jetz
s (1 π7a (0) 1:
which verifies the second part of the lemma.
Although the accuracy of pseudo-labeler is larger than 1/2, which is used as assumption in the previous proof, we can also analyse the model with high label flipping probability and the accuracy of pseudo-labeler p is smaller than 1/2. In this case, the neural network for pre-training will turn to fit the opposite direction of feature vector, (t) will increase and ( will decrease, which is formulated as the following lemma.
24

---

Published as a conference paper at ICLR 2023
Lemma A.10. For 1 == maxisism (w) 10 v) and X max 1 ( -v). we have
with high probability that
A(41)) S (1 7) A0 r E (=1}.
For 1 == maxm maxm-1s/5mm v) and A = maxisism (w (1) vv), we have with high prob-
ability that
A 2 (1- A. + 17 (2 (dd) (A/9)- .re {+1).
Proof of Lemma
A.10 First, we prove the former part of this lemma. Let j
(172) v) and note that uy Ppsism]
arg s ( (w)
1, then we have
A(+tt=
(w j- .v
((+1)
= (1 .yA) {w (1) v) + my Du
qU
Σ
12)
(2) [(
+ kw 1/4 v M
For + according to (A.6). we have
(2) v 1v12
Σ 1
MiDic
11)
(w
(2) v> || 12 + Σ
UiDic (Ww - -v>1
EES_1
Σ UnDic(")
(/0 1| + Σ unDi(() 1(w -v>1
[(
VES_1
n1 p
1
+
o(1)) [( [( 1 + +n-
1 2 + =()) [(w/]) ||v1
2
2
For * according to (A.6). we have
3/4 v 1lv12
n [w wi | 1 +
Σ
[[ - |
iES
=ny ( =(1))
||
2 + n'.
It follows that
Σ V. (1) (k . v>1 || kw 10 Vl. v
1 n11 (p- (p- 2 = + +ni ( = =o)))) 1wwf0 v)1 1v
1 + n= (p- N/2 +o()) + +nir ( + o(1)) [(/52, 1|
25

---

Published as a conference paper at ICLR 2023
According to Lemma
A.7
and note that nu (m1), it holds with probability at least 1 - 85 that
n². (2 {())
7h
m1
( ( ol)) O(m)) =o(zu)
log
2
nu
au
1
1
p= =o(1)) s mi (2 - p o(1))
+
log
2
2
8
2
n'11 : 2 + (()
11
m
(2
1 + o(1)) = =m(m)) = o(m))
-
+
log
2
8)
Ru
Nu log
1
( p = =o(1)) S =n- ( 2 p
+
2
2
8)
leading to
* S 0. Therefore,
A(tD S (1 - (1-1))(w (1)
f v) S (1 - -n)) A,50
And we can prove in a similar way that ) S (1 17)) A
Next, we prove the second part of the lemma. Let j² = arg max +15mm1 v) and note that
Mya = 1 [ssssm] 1 [m+15/52m] = 11, then we have
A ((++1) 2 (w (w/f+!)
((+1) v)
=1 n7)) - (w (1) (wf..v) v)
qu ni + nu
Σ
v. ( (w yr v |v/
a
kw (0 jo
1/4 v
For + note the definition of ja that A = (w
(2) ja v) and note the increasing property of (t) in this
case and ( > O with high probability, we have (w(().
ja v) O. It follows that
nu
(00 [( (t)
3 Di v) |v12
Σ
Viuic
v:Dic
(W (0 1-
v>
5t
VES.
VES_1
Σ
y: (1) (2)
iE
Σ ViJic(") -1v1 (1
IES1
+ o(1) -Iv1 . (A(9)--1
nn p- 2
(A.17)
For *, similarly we have
jr
(t)
3/4
v)1
(( 1
Σ
1 (
3
1 1
iES
iES
1
jz
FS
Σ ((4)) -|v13 (A
iES
n4i : (2 - o(1)
1| (A
(A.18)
26

---

Published as a conference paper at ICLR 2023
According to Lemma
A.7 A.17
and (A.18). we have n/ o(n1) with high probability, therefore
n1 pp-
+ =1))
1|v1 (A
leading to
A ((+1) 2 (1 - 177) (w) ; v)
(1)
g
(p 2 + o(1) 11v1 (119)=1
n4 + nh
(1 n/) - +n ( P) ((d) (1
And we can prove in a similar way that
+ 1 ( -)) ( (A A ((+1) 2 (1 72) A
In this case (p < 1/2). given small amount of labeled data, downstream task parameter will learn the negative direction and the main theorems still hold.
A.4.2 UNIFORM UPPER BOUND FOR (+)
The following lemma provides an upper bound for the increasing rate of r'()) Lemma A.11. For r == maxje((m) (W,, & E [nul. r7 == ma (W,, E), [mi].
T(0 max I max)c(m) Il }. we have with high probability that
d=t2c
r((+1) 1 (1 π/ri r + n max
0(d
(1(9)o , [m]]
nu
d' d2
(((+1 < (1 n/)- - + n max
@(dt+2g +2r), H
(1(0)s i E [m]]
nu
and
(ō(att2g, o ( }
((+11 < (1 - -1) r + n max
(1(0)
nhu
where c < 1//8.
Proof of Lemma We first prove the former inequality. Let j = arg max (w) (w/+tt) Ei), where E [nu] is fixed. According to Lemma A.2 we have
(1+1)
r((+1) (w (w/+t"), Ex)
m
(1 (1-)))- (w (ww(.EE) E() + qr
Σ
(c) kw
E.1 (E)
Σ
j ( --) Ei)
my + Tu
$ (1 --m))= (w.2,
E n2 + nu
+
-
(5:
+))++
kw E0I - 135. Ei)
(A.19)
where the last inequality is due triangle inequality.
For a note that E [na]] and there exists an i [n.]] equivalent to 4, follows that
(( j 6 Ei)
Σ ((w .00.)))))++1111 ( Ei) + -c0 [( -
(A.20)
iE(mu]isst
(nu - 1) (
15-0 + ((())2)) (1(0))=1 + + E(dlt20). (1(9))=1 (
2
-na - 1) +())+29). (1()))=) + (())+2)) (
27

---

Published as a conference paper at ICLR 2023
where the inequality is due to Lemma
A.5 |
(ddo))
-(d I(E,, ((), o(d
(dd +2)) according to Lemma C.3 and the definition of r())
For *, we have
KKE &i) & m ( (1(0))-1
(r( = ny O(d (()())))))
(A.21)
Plugging (A.20) and A.2I into (A.19). we have
r((+2) $ (1 - (A) ( +n 2h + nn (In + + 11 G(d2+2r) + o(d))))) (r(a)e=
S (1 7) r + max ((db)22), ( (1(t))) }}
(1(0))=1
nu
which is the first part of this lemma.
Let j" argmaxisjsam (w, (++1) E(), where 1 [mi] is fixed. According to Lemma A.2 we have
1 p(t+1) = (w (ww(+t) (e+1) Eii
(1 - (1-1))- (w (( + q
Dic (w
(1) (6)
E:1 (E: +
(1% <i)
nj + nu
S (1 1/A) (w (w, < +
9n
- 16:
(6: +
[w frr
' </1
401 KKE,
+ uu
(A.22)
For c we have
(W 4NI (E:, &i
<
2 to(1)
) n. (((()))))((())))))) 4-1
(A.23)
where the inequality is due to Lemma A.5 (E E.) = @(dto)) = @dd and the definition of I(t.
For *. note that I [m]] and there exists an i [m]] equivalent to 1, it follows that
10 kw -M 4
Σ (w -.) (1 (w ( -
(A.24)
iE(m)).i7t
< (m) - 1) ( + o(1) @(d++2)) (1(t))==1 + ( + o(1)) +2) (110))0-1
= (m) - 1) G(dà +2c) + ((2)+2)) (1()) 9-1
Plugging (A.3)) and A.24 into A.22
have
p((++) < (1 - 72) M 1(++1) + n
(mm + m - 1) @(d++2c) -((+)))) (1(0)--
ni + nu
max @(db+22), ō( (( }} (10))r
< (1 π\ M (t+1)
+
which verifies the second inequality in this lemma.
28

---

Published as a conference paper at ICLR 2023
Note that [()
( |mi I(0)) j. without loss of generality, assume
r(0 max r (t) and assume 1" = [ 1(t+1) we have
dl+2r
p(++)) = r p((+2) < (1 - 171) r + r7 max
Old +20 θ
} (rit))
Thu
( 0
d=t22
} (
S (1 πd p + max
nu
which verifies the third inequality in this lemma.
A.4.3 TENSOR POWER METHOD: PROVING 1 = O(1(o)) DURING [0, T,] AND COMPUTING THE MAGNITUDE OF T,
In this section, we first show that off-diagonal correlation (A, for p > 1/2 and A for p < 1/2) remains initialization magnitude during [0, T.). If the accuracy of pseudo-labele
> 1/2, we have
{=1}, therefore, A (A, off-diagonal correlation A ((++1) S (1-nA) A for E
Ö(d- 2). If p < 1/2, we have off-diagonal correlation ((+1) s (1 - n)) A for E {=1},
therefore, A OA, Ō(d 4). In this paper, we mainly focus on p > 1/2.
According to Sections A.4.I and A.4.2 have obtained following upper bounds and lower bounds for feature learning term A, we have
[+1] and noise memorization term P(); When / E [0, T.).
1(+1) > ((() + (2p - 1) (dd) (A(0))0-1 and A(++1) S (1 - (1-1A)- A0 for E (+1};
0(d2+29) o 22 }
p(++)) < n/) (()) + . max
(1(0))-1
nu
(A.25)
According to Condition 4.1
assume nu = =[(ddt) and note that < <1/8, we have
max O 2e θ
d2+
max (0(d)+2)) ((d--22) ) Ō(1--29)
nu
leading to
r(++)= <( - [1) (()) -
By leveraging tensor power method introduced in Lemma C.4 we can prove following lemma about the magnitude of (()):
Lemma A.12. (() remains initialization magnitude during [0, (
Proof of Lemma A.12
Let T be the first iteration t in which ( > A for r E {+1}, let T be the
first iteration in which (() > A', then according to Lemma C.4
we know
C2 (1 + (-550-1( (1+
log (A/xo) log (1 + 8)
Σ 5
+
(1 - (1 + 8) 19 2) )100
C
120.5.A
8(1 (2o/Al A))-22
7. (1 (1+ (1
log (A/20) log (1 + 5)
Σ
n
(1+0)--1()) (1 + 8) 1)-2) )00
120,2
And it follows that
C2 C
(1 + 5)0-1 00
log (A/Ai²))
n T S
+
log (1 + 8) )
(1 -1- ( (10)) 1.
((1-(1o/A11)
n (1+8') (q-11) 1+ log (A' (A'/T(0)) log (1 + 8')
n- T
(1 + (1-
29

---

Published as a conference paper at ICLR 2023
where C1 C2 = (2p - 1) ((d) and C₁ C2 = Odd' 2r) according to (A.25 Taking = (1/m), A' = C. p()) where C a large constant and C @(), 8' 1/2 and
2
note that A @(ood)) a(d 2), p @(ooa)d)) = ((d- have
n T. S o 3) + @() ((d- #).
(A.26)
and
n.T" >
-1 -dd
(A.27)
Therefore, combining (A.26) and (A.27). we have 11- 2 @ + to T* T, for both r E (- + 1}. This indicates that when , reach ( [ remain the same magnitude as initialization.
o(d +) 2 n T,, leading
By leveraging tensor power method, we can also estimate the length of Stage I, i.e. T. T-,, by applying tensor power method. To use tensor power method, we need to upper- bound the increasing speed of ( We have the following lemma:
Lemma A.13. For E {+1], we have with high probability that
Ro+1) 2 (1 - (1)) 1000 + (p _/2 - -0(()) 1Iv12 (A,9)
2
A(+1) S (1- - (1- A,00 + +n. 9 + =o(1)) 11v12 (A())=-1
Proof of Lemma A.13 Let j arg max maxi (w ( vv and note that uj- Apsism]
[m+15/52m] 1, then we have
A((t1) (w v)
=(1 n7)) (w) v) +
T
Σ
y:Dac
(/ (0) v) 1 +
(-
(0
1
72 + nu
iES
ES
917 14 + Bu
b (( v) 1v1 +
1 (0)
w>
|
(A.28)
For + according Lemma A.6
we have
yeDic ((w v 1v + Σ
viOic [[(])" [.. |v
SES_.
= =n.
p
+ (1))
[(w vi || 12 + nー
(p + o(1) . 11 -) 1Ivl3
2
2
S mn
pp - 2 (1)
11v12 (A(1) 0-1 + +n-
(p-
2 + o(1)) ||v13 (A
-ni (p- - (1)) 1Iv (A(0)=+ 9-1
(A.29)
where the last equality is due to 7(00 w (A()))
30

---

Published as a conference paper at ICLR 2023
For *, according to Lemma A.5
we have
kW ( j", v 1
+
Σ
1
KES
KES
= =ny
1
(1) [kw... 11v + +n'-1-
2 = o(1)) . (1-(w].. 1 (A.30)
2
Sni n1 [
2 + (1)) -iv1l (A )- + nn'1 ( + o(1)) 1|v18 (A
= =n/ ( - (1)
| (A1)))-1
where the last equality is due to ( (1)
Plugging A.29 and A.30) into A. 28
we have
A
S (1 - -mA) A + 1 + nu
q7
1
+ o(1))
1Iv12 (A("))=) +m/ = 1|v| (1())--1)
71
p
2
(1 1/^) 1 + mi + nu
qm
(p- -
1
+ o(1)) 11v11
(A(0) + nn nuu (5 (()) 1|v1 (A(9)--1
qun
2
(1 17^) ( + qu
711
(p-
1
+
o(1)
+
ri
( # = | (A
mi + nuu
2
+ nu
(1 m/A) 1 + q7
m
1
n
1
=o(1)) 1|v13 (1/9)='
p 2
mi + nu
n1 + nu
2
(A.31)
Note that we have already proved in A.9 that
Al(t2) < (1 - n2 X + +
71
(p-3)
n2
1 (0(1)) 1Iv112 (A(0))-1
+ n + nu
m1 + Ru
2
2
(A.32)
Note we have already prove in A. that
72
n1
1
(p - 5/ o1)
[) + nu
(p-2)
p
2
+
m + nu
2
Therefore, we have
A(tt1) 2 (1 (1-1)). A((0) om (p- -0()) 1Iv11 (1(0)=-
((tt1 < - n) 1(0) + mm (p
+ 0(1) 1|v12 (1
2
In similar way, we can prove that
A A (1 m/A) (1) + qm (p
1
o(1) 1|v12 (A
2
A < (1 ma A + am
(p + o o(1) 1|vl2 (A%)=+
which completes the proof of this lemma.
Lemma A.14 (Length of pre-training). For r E [+1], let T, be the first iteration that 7000 reaches (1/m)) respectively. Then T, @(d ()d- for all (+1).
31

---

Published as a conference paper at ICLR 2023
Proof of Lemma
A.14
By leveraging tensor power method given in Lemma C.4
Σ 120,0
6
C2 (1 + ++88-11 8)0-1
(1
log (A/20) log (1 + 8)
+
(1 (1 + (1+6) (0 x
C
8(1 (xo/A)o-2
log (A/20) log (1 + 5)
Σ 2
77 (1 (1+0)
(1-1) (1+0)-(1-))
1+
(1 + 8)0- ( (1 + 8) 100000111000000 2)- x 22002
we have for r E {+1] that
5
C2 (1 + 8)0-1 (1+
log (A/T,O)) log (1 + 6)
TT
Σ
5
+ C1
(1 (1 + (1+8)- 8)- 2),A N, Ci
120,50 SA
(i)
(38)
8(1 - (xo/A)9-2)
log (A/ 10)
7. E 120,000 SA
2
17 (1 + (9- 50-
1 log (1 + 0))
(1+ 1++-)911(1 (1 + 5) -9 1 C2
(60)
(dis)
||v[[ and C2 is taken as q(p 2 + o(1) |M according to Lemma A.13 Taking k. A 0(1/m) and note that terms (it), (iv) are respectively dominated
where C1 is taken - (1))
by terms (2), (i)) when 17 is sufficiently small and letting h + oo, we have
1 N
flower order terms} sn T, S
+ flower order terms);
A C₂
for E {=1}. And it follows that
1
7 T
flower order terms).
(A.33)
q(p - 2) [v[l3 N
/log(mJoolvVbb) = 5(d-3/4) which And by Lemma A.3 we have f) T (11/((=-))1V))) M completes the proof.
The discussion in this section verifies Lemma 5.3 and provides a clear understanding about how X(9) A varies within the iteration range [0, T,] for E {=1}. Note that the iteration numbers when ( and ( reaches @(1/m) (Ti and T-1) are different, however, since T-1 and Ti have the same magnitude, it remains clear that although Ti * T-1 (wlog, assume T3- < T-1), we still have 1(4) = ((1) and A = Ö(d-t) within the iteration range [Ti, T-)] since off-diagonal feature learning also costs time no less than order ((L/nj | Vllg m). which is higher order than T T-1l = (11/noollv log m), according to (A.33) and Lemma A.3 Therefore, at
time To = max (Ti, T-1), off-diagonal {(t), A still remain initialization magnitude Ō(d-+) T(9, r()) remain initialization magnitude ((d- while on-diagonal ((4), _ reach and then
remain ((1)
A.5 PROOF OF LEMMA 5.2
If we only use labeled data S' for the optimization of CNN, according to Lemma B.1 we have
(++1) (t) V Ls (W)
w w
(1 (1) (1) +
Σ 1=1
(1) y/ (K( 1/4 v v/ v + [(w,, ED1 -!),,
n
where u, := Apsism) 11 [m+152m) [w(x)]])
6 ('v: fw -xxp-x/ (x))))((x()((xpppp)
32

---

Published as a conference paper at ICLR 2023
Notice that and Eú are orthogonal to each other, have
1/ +))1 11111. (w/(tt)) v) (1 -1-11 (1)) (w) T
10
[(w (2)
(w(t)) E = -(1 -1) (w/)) (.) +
v/ [ww) 101 (), [m]
Let T be the first iteration that r/0) reaches (11/m), then we have following lemma:
Lemma A.15. As long as r/(0 - (1/mm) 8 = (16 swo (x() will remain 1/2 + o(1)
Proof of Lemma A.15 Note that {() log(1+ (-2)) and -f' cxp -xp((=)) (-2)),
and without loss of generality assuming y = 1, we can express (/ follow:
mm 1 v))+o((w 4iIi
8 (f(o (oiioo to) <D0 -i (a( (l)) (()I"
Since a((w)"
(1) ( ()))) will dominate a(ww)) (9) v)), which will be proved later by using tensor power method, we have
E lo((w)) P ())+o((W))) (( .(101
( = - (fwioo))))
Ey o((w)) (oower order term
3mm ((w))) w))+o((w) .g)).
On the one side,
6(9 2 Em o((w))) +oower order term +
(m( yot Howeer order term)
1
2 - -0())
@m ( 1)
2 + o(1)
On the other side, according to Lemma
5,4 we have A Ō(( it follows that
(
(0) <
E. a((w)) e()) + flower order term]
+ (m)(((())+0(0))
+ o(1)
Er ol(wW)). (lower
flower order term
+ +1 + 0(1))
1+ 0(1
1+1+ o(1) +1()).
Therefore, we have b(0) = 1/2 o(1) and the other case of y; = -1 can be proved in a similar way.
With the help of above lemma, we now ready prove Lemma 5.2
33

---

Published as a conference paper at ICLR 2023
arg argiaxisjsm (( v) and note that dj 1, according to
Proof of Lemma 5.2
Let j
Lemma A.15 we have
(w (1t))) v)
= (1 - m1) ( /z
+
1/4
v 1
= (1 A)di (w) (8)
+ Q
M +
Σ
[(
-v)
LES
= (1 - nd) (w v) +
[[
100 1v
EE
Σ
-
1|v12 11v
2
m
iES'
(A.34)
For do we have
Σ
[ (1))
v = n² 2 + o(1)) [ww."vv)]=
KES
(A.35)
S Sny. ( 11112 (1
For *, we have
Σ $ES!
! +
(w. = nn_n- ( =(1)) -v>1
o(1))
[(w
(A.36)
S nn_, = 1iv12 (A
By plugging (A.55) and (A.36) in (A.34). and according Lemma A.8 we have with probability at
least 1 - 45 that
A((42) (1 -))) A(0)
n1
1
+ o(1))
1|v12 (1(9)=- +n', C + +(()))
11112 (A
2
(1 md) ((0)
m
m
( + ((1) 11111 (1(0)
+
log
2
2
2
mi
m log 1
1
(5 =((( || (aL))--)
+
+
2
= (1 - m72) A(t)_ + qm (1 = o(1) =01))
1|v112 (A())=-1
8-1 + C = 1Iv11 (11))-1)
= (1 nA) ((0) + O(d) (1) + (1())-1))
And we prove in the same way that with probability least 1 - 48 we have
パーーク < (1 - n7a No - O(d) (A + (-1))
34

---

Published as a conference paper at ICLR 2023
Let j arg maxx=mxx+mssse (w) (++1) v) and note that uj -1, we have
A ((+1)_ = (w/++t) v)
= (1 - -11) (w (
47
(w J- 3/ "1v
(A.37)
==1
< (1 777) (w) (w)
I (1 - 7)
And we can prove in the same way that A (1+1)
I (1- (1-nA)- A
Next, we consider the increasing rate of r where 1 [ma] is fixed. If y 1. let j
Miggaxisiim (w) Ei) and note that uj = 1, we have
(((+1) 2 (w (++1)
</)
jz
12
= (1 )) (w
97
[( J1 401
(E)
Th
= (1 A)
9T
Σ
6/2
(1) jz -101 (E),
(1 7) (w 4/)
97
lower order terms}
2 (1 A)7i 1((0 9m
1
o(1)
||61|
(1)
2
= (1 7) r + ((d)
(1
(A.38)
where the third equality holds if we properly choose the order of X.
If y = 11 let jf =
(w))) Ei)
(w
and note that uy = 11, 1, we have
(((+1) 2 (w y: (1+1) <
m
= (1 - -- (w
97
[(w
40
(E), Ei)
mi
= (1 A77i
(w
401
9n
Σ
(1)
(E),E)
M
(1 A)a (w (1 41)
99
1017111111 lower order terms)
m
2 (1 V/ai I((t)) 9m
o1))
||1/113 (1
= (1 π\ I(( + n (dd++2e)- (1)0))-1
(A.39)
where the third equality holds if we properly choose the order of A.
According to A.38) and (A.39,, we always have
1( 2 (1 n2) I: +n- 2n- -11(0))00-
A.6
PROOF OF LEMMA 5.4
By applying Lemma C.4 to (t) and taking Ci = @ 1=
= 1/2, = ((1mm))))m))))))mmm)))) we have
Σ n ((//C,1(9) = -
35

---

Published as a conference paper at ICLR 2023
And note the definition of T, we have
17 Od 3r.)
(A.40)
In Lemma 5.2 we have already prove that
Ritt1) (1 n2)) A + 1j O(d) +
(A.41)
k(+1) < (1 - -1))) Al A((+1) {#1}.
Define A(4 = (=11) (A,²) { according to (A.41) we have
((+1)) Σ (1 - n/>) (4) + 1 (dd) (A(0)0-1
By applying Lemma C.4 A(),, and taking C₁ ((d), 1/2, A C. A where A is large constant, we have
Σ 1 ((1CIA = ē(d
$2 SA
Let T' be the first iteration that (1) reaches C. A then we have
17 T' (d $).
(A.42)
According to (A.40) and A.42 we have T' = wT,)), which indicates that when ((()) reaches ((1/m), ( remains initialization magnitude (d-+t).
A.7 EMPIRICAL, TEST ERROR AND LOSS FOR EARLY STOPPED CLASSIFIER
Assume the accuracy of pseudo-labeler p is larger than 1/2. We first estimate the empirical loss for early stopped classifier /we.. where To ( [T+} and T, is defined as the first iteration that ( reaches (11/m). According to Section A.4.3 and Lemma A.12 we have A(To)
A() (T)) ( ,) O(d for E {=1}. We have the following lemma:
Lemma A.16. Early stopped classifier fwor.) (x) possesses following properties:
Training error of early stopped classifier fwor, (x) asymptotically pt nutn mm 10: Sway)( < 0] + Σ [v/ (wizo) - 0)) 1 - + o(1)
Test error is nearly P (xx.))DD.rryyB0)))
p. if we use pseudo-labe ÿ generated by pseudo-labeler as target: fwirs (x) - 0j = 1 o
3. Test error is nearly 0, if we use true label y as target: P(x,))D(y fwoe (x) < 0] = o(1) and hence sign /wr::: (x) = syg with high probability,
where p is the accuracy of the pseudo-labeler. We can regard p as the probability that x; is paired with true label yı. 1 is the probability that x; is paired with wrong label -ye.
Proof of Lemma A.16
Recall the definition of fw in 3.1 that
fw (x;)
Σ
(ww) (To)
Us v)) + ((w)) (T)) .Eai)]
2m
o ((w (To)
v)) + o ((w) (To) ..:)]
j=m+1
According to Section A.4.3 and Lemma A.12 we have (T) = Õ()), A (Ta) r
max { [max,e[m.]]
(t) max:e[m]] 1.00) O(d tt)) for r E {+1]. If ys 1, we have following
lower bound for fwor (x,)
fwon (x;) =
((w (76) v)) + @ ((w (T6) (To))
Σ
(( (T)) v)) + ((w (o)).))))
j=m+1
2 Aool + ( m (r(folle
(A A lower order terms).
36

---

Published as a conference paper at ICLR 2023
and following upper bound for fwin (x;):
2m
(x)) - Σ ((w (T6) v)) + o ((w, (T6) [.i)]]
Σ
(o(( (To) v))
v)) + ((w, (T)) (.,,(
j=m+1
S m ( (ubly + m(T
(A(rm))= - (o))
2 ( lower order terms].
If y = 1, we have following upper bound for fwir (x;):
m
2
fwiss) (xs)
Σ
0 (w) (To) v)) or ((w, (Tp) [
Σ
[ | (w, (T) v\) ((w, TT) ((T)TT))))))) {x))]]
==
S m A To)) & + m (r (A(P)) (r Tolg
- (A (A ) "[+ lower order terms);
and following lower bound for Swire: (xx):
172
2m
fwirg)
[ - (w, (Tb) v)) + ( (T)) [.I] [.1)
Σ
[o( (w, v/) + t
(T)) {.))
j=
2 (A 1 a + (T!To)))= m ( - m (1000
2 m (A (A lower order terms].
Therefore, for unlabeled data, we have ys- fwore (x,) E [(1 (L-- (A (m+o(1)) (A yo]
and hence sign (Swor (xx)) = sign( holds with high probability. We can also prove for labeled data (x1, 3() that s/ fwom (x() E [(1-o(1) (o)o), (m-+o(1) ((())))((A7))) (1% sign(u() in the same way.
(T(7)))9) y9]. yg)
sign (Swir)) (x()
Note that takes ys with probability p, Yi with probability p and m = o(n.), the first statement in this lemma follows obviously.
To prove the other two statement, we need to give an upper bound for the norm of wy. According to
the update rule of w) (1)
we have
w (((t)) (1 -n)
4Tp 111 + nu
([(w (t)
3: v> y v + [(w] 1 +
()) ", <.))
+ buol (((s( .// v11 vi
leading to
(1+1) 1 5(1 - 1//1) || (1) 1|2 +
(Iww)) - v- |vll2 + " -115/l2)
ni + nu
+ m
(I(w))) ) ./4 v)T ||v||2 + [(w + [1E)11)
1=1
(10) (wo+tma)) nw) MM22 ( max ((0))(1)))
$ <(1- MAA) . ||w 1|2 +
nu + nu
re(a1)
+ Σ
|5:1 12 + Σ [k (r(:))-1)
*E(m..]
(E(mg)
< |w 1|2 + 17 (0(dt) @(1) + (attt)) ( 0(d0-1)(-440))
|w (t) l|2 + n ē(tt).
(A.43)
37

---

Published as a conference paper at ICLR 2023
where the first inequality is by triangle inequality; the second inequality is due to the definition of 1 A,O) T(t), the last inequality due to Lemma 5.3
According to Lemma A.14 we know that 7 (dd 8), E {+1) and To (6-1)- 11 ( (Tr
? (d )). Note that w
O 1), we (0) N/ -بJ oo = O 2) and hence | 1l
know that
(T) 122 & Iw, | 12 + To = -( = [
Therefore, for any (x, y) sampled from distribution D where we have
1y v - and & (O, o/)),
(0 w (6) 1)), kw, ( - - (a,plw, (o)) (2]
t9) (A.44)
And this indicates that (w) (Tb) {) will still be dominated by (w) (Tp) v). therefore it holds for newly sampled (x. y) that
y fwo (x) [(1- (A (m + o(1) (A)
which means that
P(xx))=Dly - f (x) I 0] o(1)
This verifies the third statement that test error is nearly zero.
For the second statement, note that
P ((x.)))D.- 1 fwor (x) 5
(x 1T fwerD (x) S 0lū y] PP PiryyB(p) (T/ 1)
+ 10 fwins (x) I 0g -yl P Pgry B(n) (6 = v)
pp =p- .p.P(xa)-Dl fwor (x) s 0] (1 p) ((xx))DD fwo (x) 2
=p-o(l) + +1 (1-p) -1 (1- o(1)) (1))
= =
which verifies the second statement.
A.8 DOWNSTREAM TASK
For downstream tasks, we use early stopped classifiers, which are stopped when on-diagonal feature ( learned while off-diagonal feature A and noise ((t) are not memorized. Assume have learned early stopped classifiers J ( (x), ... If w erg (x) by using nu pseudo-labeled data
generated by ppeudo-labeler f f and ny labeled data.
Then, want design classifier the learned representation f (B)) (x),... if (rd5 (x) to fit w
woF
y. Here we consider training a downstream linear model
ga (x)
a (x), (x),
where ag E R denotes the weight as the k-th pre-trained model. Given labeled training data S' ((x), 1/ we want to optimize the empirical loss function
1 n1
(a)
Clll 9n (x()),
where {(=) = log(1 + exx((=2)) denotes the cross entropy loss. We initialize zero and optimize empirical loss function by gradient descent, i.e.
(++1) (1) n VaLs (0) 0.
In order estimate the training error and test error for downstream task, we first introduce following
lemma about the increasing rate of |
38

---

Published as a conference paper at ICLR 2023
Lemma A.17 (Logarithmic increasing rate). For any learning rate 1/ > 0g will always increase
(6)
for any k E [K] and hence ||a|0]|, E dx And it holds that |a()) ((lgg(t))
In order to give the increasing rate of ||a we introduce and prove the following lemma: Lemma A.18. Consider following sequence { with T++1 2t + C' ", xo - O,
where a > 1 and C' > 0 are constants, and it follows that log, [Ina- C t +) S S loga (Ina (lna-C-- C. +C,
and
It- 21 _ hhatt+1
Proof of Lemma A.18 Note that
13+1 3j a 22 > a (2i+ - xz) =C,
by adding up above equation from i = 0 i =1 --1 1, have
[-1 1
a Fi (ri+1 - x2) = C
(A.45)
1=0
d' 1.
ha C.
a² 2 haa
xt 2 loga (C In 1 + Z441 I2 a S C.no-t41'
where the first arrow is due to a" is monotone increasing. On the other hand,
#1+ #1+ =a C.a # S a (.C.CCCCtt))t))) < at c
which implies
t-1
a #i+1 (Ii+1 - xx)) S a Σ a
(xi41 - x;)
1=0
i=0
#it (sit1 - xz) s a. Ct
1=0
Rt
a dx < c Ct.
where the first arrow is due A.45 and the last arrow is due to a" is monotone increasing.
This leads to
21 I log, (Ina C. a n+1)
< log, C. a. a
= logo (ha-CC+++)+0
Therefore, we have
log, [na- C. C+ 1) S Eλ S log, (Ia C+++1 +C,
and
C
Ft- 2 v ha C.++1
39

---

Published as a conference paper at ICLR 2023
Now are ready to prove Lemma A.17
Proof of Lemma A.17
Note that we take downstream task linear model ya (x)
as
(T)) kJj .y v)) + o ((wb))) (TT) .5)]
[x(x)
km
2m
((((W y v)) + + (3 {
(T0)
1=m-1
(x).
w
Then, we have following update rule for model parameter a:
(1+1) Qk 0g
(16 Iato vhl wast (x)),
where we initialize d as zero for all & E [K].
(0)
Next, prove following statement by using induction method: when t 1,
ak vk E [K] is non-negative and increasing.
||a(1||1 Σ (t)
(1+1) d n 6(1) (exp ( (1 I1, ())1))) vk E [K].
d
Note that d
for all E [d] and therefore Iaco) (xx) = 0. el (v4 Iato: (x,)) = -((0) = -1/2.
(1)
(0)
1
(vl Jator (x4) vll cngo (x,)
dg
17 m
0g
+ 17
Haf (x() = -7. 2n
1
Σ skf w
mn (x() for all l E [K].
2ml
Note that the accuracy of the k-th pseudo-labeler pk 1/2. accoring the proof of Lemma A.16 16 we have
wo (xx)
a
(w k.j
U/ v)) o (ow (75) -
1=1
2m
Σ
o (((w ki 2// v\) + o ((w!7)) (T,) .<4)
(Tb)
5=++1
5/4 ((A(77)))))
for all & E [K]. Therefore
dg 17 2m1
Hll wath (x() > "
(((T)))))
> 0, AA E [K]
2
It follows that
K
K
(0) || = Σ
la
=
Σ
a
i=1
1=1
40

---

Published as a conference paper at ICLR 2023
Note that
K
v
Iat
1//
%
!1)
(x/3)(())
K
Σ
kk
K
(A.46)
(1)
(((A
a
k=
K
Σ
((1)
(1)
k=1
|a (
This leads to
exp(-u/ 1a(1) (x())
( (xan((()) = 1 + (-1/ Ia(1) (xx))
= (exp ( 3/ Ia(1) (x4))
= = exp ( (- ||aa51)/1 @(1)))
where the second equality is due to v Ia( (x+) > O, exp (-1/ (xm) < 1 and c (1/2, 1); the last equality is due to (A.46). follows that
m
0k m
(1)
Σ
e' Cvt (x vl5 Vlf (xx)
(1) 0g + n c. 6(1) (exp( (-11a (-(1))) wk E [K]
where e (1/2, 1). By then, we have already proved the induction hypothesis of t 1. Next, assume the induction hypotheses hold for For t 1, have
(1+1) 0g
(t)
(y) Iato (xx)) 1.f w
(x))(x))
(1) oof (x,) > ax > 0.
0%
And it follows that
||a
(++11)
111
Σ
a
(t+1)
and v gaten())) =
-1a))==((((()) (0+ -(()),
(A.47)
1=1
leading to
l' ('1 (n =-c- (exp ( [|t 6(1)) , . (1/2,1),
and
dx dz + @(1) exp (- (t+1) ē(1))) vk E [K].
(++2) (t+1)
This indicates that if induction hypotheses hold for t, then they holds for t + 1.
Adding le E [K], we can obtain
|a ((+1)) |a + ē(1) exp (-5(1)
5(1) ||a I1.)
(A.48)
According to Lemma A.18, we know that |a || log l/) lower order terms w.r.t. t].
The following lemma gives the convergence guarantee of downstream task:
41

---

Published as a conference paper at ICLR 2023
Lemma A.19. (Convergence Guarantee) For any learning rate r) 0,
6(1)
and V (s) ł 0 for any E IR, [VaIs v (() 1+1
which means within polynomial steps, gradient descent guaranteed to find a point with small gradient.
Proof of Lemma A.19 Note that
K IV (aabs((a())1 = Σ
Oay Lir (1
k=
Oas L (a (1)
km
((+1)
(1)
Oi
(++1)
|| ||
1
then according to Lemma A.18 and (A.48). we know
77 O(1)
a ((+1)
|||
(2)
<
(A.49)
"1 ((1) +t+1
And it follows that
((1)
VaLs (a (1)
17 0(1)
which shows that within polynomial steps, gradient descent is guaranteed find point with small gradient. Note that
1 n
On, Lg
Σ e' (16 (x(e())))) vis with (x)),
mi
Bag 0a, (a)
Σ
E" (2( Daco (x+)) (fwor8)(()) wwors (xi) for all k,j e [K],
Th 1=1
Denote [1 (x)) i wor (x() fw- (x(), then
VaLs(a) = Σ ("(1 (x(o(())))) (fw- (xx) fw- (w-(x))
Note that fw- (x() fw (x²) is non-negative definite matrix, ("(x) exp e-p(-2)/(1 +
exp (-2))² and the fact that sum of non-negative definite matrices is still non-negative definite
matrix, follows that Ls 2 0.
Theorem A.20 (Restatement of Theorem 4.3 Under semi-supervised learning setting, for down-
stream task, suppose K early stopped classifiers (Sw; are obtained after the pre-training of K CNN models finished, and after Ta: = 1 iterations with learning rate n = ((1), then we can find a linear model (Taa), which satisfies: Both test error and loss are nearly 0. ie. F(x.a) by fa( (x) 0) o(1), (ely Ia (x))) o(1).
42

---

Published as a conference paper at ICLR 2023
Proof of Theorem A.20
A.22
For test error, have
P P(x.))/Dy Iol (x) S 0] F(x.)))DD
(Tai)
(y (w:(x)) S
K
(Tai) 6(1) - 0/ = =(1)
= =
0k
k=1
where the last equality is due to dg For test loss, we have
(Tai) > O according to Lemma A.17
LD(E(y Ia (x))) E(x.)) Ia (x))],
Le., we estimate for newly generated data (x, y) the magnitude of Ely Iacel (x)). In order do we will first estimate Ely Jato (x;)). Then, we will show that f(y Iato (x)) and E(1l Jato (x,))
nearly equal to each other.
According to the update rule of (t)
0j we have
(f+1)
(1s (xtes V/ll
waat (x().
k
Adding up the above equation for ls [K], obtain
K
|a (1+1) 1|1 = ||a!0 Σ (vl ga(o(x()) 2 Σ
f woth (x²).
(x+).
And according to (A.49) we have
11 ((1)
|a |a(t+1)l -|a S
1 O(1) . 1++1
therefore it follows that
K m Σ Csll Jat (x)) vi
6(1)
Σ
wir (x²)
1) ((1) -t -t+1
k=1
Note that K = (1) and for all [K] we have v\ -f w
(38) (x() = ( it follows that
ē(1)
< n ((1)
Note that nı = @(1) and according to Lemma A.8 negative sample (X4 Vig) with the property that
there exists positive sample (Xi, Vi,) and
@(1)
ē(1)
-((,,, Iatt) (x,)) S n7 -
-' Pain (x(,)) 5
11 ē(1) t+1
Note that ((2) = log(1 + exp(-2)) and (2) - exp((2))(11 + exp(-2)) we know that for >>
[((x) c exp(-2)) {(2) < exp(-z) (iz)),,ce((/2.)))
It follows that
ē(1)
ē(1)
(1h,, Iato (x()) 17 -01))111))
{ Iates (x(x))
17 0(1)++4+
43

---

Published as a conference paper at ICLR 2023
Note that ((2) is I-Lipschitz, we have
fyy (x))(x)) - E(Vi, 9att (x,, )) - 1 Pate: (x) - Vi, Paie (x4 |
(A.50)
[(v (ates(x)) - EVV's 9att) (xx)) < |// Mate (x) - 1/12 Mates (x
If y = 1, we have
w Pato (x) 1/, Date (x
Iaat (x)
Date) (x1,))
(1)
w (x)
Σ
ak f
(0)
w w (x(1)
(A.51)
k=1
K
(f ( (x) - f w (x(1
0k
k=1
and
m
(o(rr)(2) - (w (x)) (x)))
o ((w, (TT) (Tt) v)) + o (o((w))
a (30) ((w(((),)))) [
2m
((w)) (T8) v)) + ((w 18)) _
j=++1
((w (T)) v/) + ( (T))
2m Σ (a(inn"0 (18) v)) + o ((w) (88) E
(A.52)
j j=m+1
Σ о ((w, (Td) ,,) - o ((w (76) .E(.))
2m
Σ
[o((w (16) .E4, ,.,))))),()))) o ((w
j m=+1
Od 2t0)
where the last equality is due to (A.44) and Lemma 5.3
Plugging A.52) into A.51
we have
y 9att) (x) V/ 9. (x(, Ö(d tto). ||a!
(A.53)
If y = 1, we can prove in a similar way that
y 9a(t) (x) - V/a Ia(t) (x(x) (t() (11 Plugging (A.53) and 4A.54p into (A.50). we have
(A.54)
{yy Iate (x)) S max 5/1 Jav (x 3,1///- Incos (x/)) + Ō(d )tt) (|a
According
to Lemma A.18 and
(A.48).
we
have
|a(t)]
log+/O(1)(++ lower order terms w.r.t. f), therefore
@(1)
fly Iate (x)) < 11 ((1) +
+ àtt) logt (+ lower order terms w.r.t. t}
Taking n = ((1) and Ta = (dd /n) where a > is a sufficiently small constant, we know that
(D(l(y (x)m)())))
= -E( ([yy (a (x))
6(1)
+ Ō(d log Ta (+ lower order terms w.n.t Ta } + o(1)
17 G(1) Ta +1
=0(1), which completes the proof.
44

---

Published as a conference paper at ICLR 2023
B PROOF OF SUPERVISED LEARNING SETTING
Here prove Theorem 4.4
First, we give following lemma to facilitate the proof.
Lemma B.I (Gradient Calculation). The gradient of loss function Ls(W) with respect to weight parameter W is
V wy L (W)
( v/ v)1 .//. v I k E.)
where Uj (1usssmm L fi ) and -l'(us fw(xx)) expl-s/ fw(())//11 +
s Jw (x(1))) denoted as b;-
Proof of Lemma B. When 1 i S m,
Vw, ((y fw(x()) ['(' fw (xx)) 3/4 [w,fw(xx)
--bi.u v/ V fw(()xx))
--beth (o' ((W, v)) 5/4 of ((w,, (1) 4
= ---b/// ([W,)]1 v)]2 1/ v + [
401 .
and when m S S 2m,
Vw, Mike [w((x)) = (lavi v/1 1/4 + ((w, 401 E.
Combining above cases, we have
Vw, (yyh fw(x)) - 4( [1sssmm - -1 ) bey/
(I(w,), V/: v11 4/ - E
quubuuii (((,,: v)1. .// v + [( <11 E
and therefore
1 a1
m
Vw, LS (W)
V Vw Li (W)
V ww lvl fw((x))
111
quu
bacl (l(w),
v)1 3/4
E.)
m
Proof of Theorem 4.4
Recall the definition of fw in 3.1 that
2m
(x(x) =
((W v)) + to ((w,
Σ
(w(W,, v\) + (((w),
j=++1
Define W, = m wj. we have
m
fw(x) = Σ
((mm 1/9 w..y v)) + +a((m 1/9 w, {))
1=1
Σ
(mm(m W,.y v)) + a amm 1// wy {
1=
2m
((ww,.V-v)) + E
fw (x).
Since the standard deviation of Gaussian initialization of w, is du and note that w, 1/9 W the standard deviation of Gaussian initialization of W is m m/ do-
45

---

Published as a conference paper at ICLR 2023
On the other hand, note that the update rule of w/)) is w ((41) -w 11 Vw,
(W()),, (W(()) and in
Lemma B.T we have
Vw, L (W)
Tu
ba (I( vi v)1 1/ v kww, E11+ -E))
n
follows that
((+1) (2) grpu
m Σ
vl (lWW v/ v)I v/4 ((w E. (B.1)
By plugging Wj = mn 1/9. w into
B.
we have
(++1)
w + gmpm ug
(1)
vV v/4 v (w) EMI- +
7
Assume 77 m 17, we have w
(++1)
(t) 7 Vw, Ls (W()). Therefore, our data model and
training algorithm is equivalent to the model and algorithm below:
1
( v\) + の (( {
(x)
= m j=1
2m
fw (x) = m
1
Σ
o
((WW).V v)) + (
j=m+1
fw(x) = fw (x)
f (x),
and we use gradient decent with learning rate rj and enssopy loss to optimize such a data model, i.e.
- n1
~ NNO Tb W = ww] 77 Vw, Ls (W))), Ls (()) = Σ Elul fw (x))).
where =(=)= = + (xx)(=2)). = m /9 Note that the new model meets the one used in Cao et al. (0022). To leverage their result, we introduce condition 4.3 from Cao et al. (2022) and verify that the new model meets the new condition.
Condition B.2 (Condition 4.2 in Cao et al. (2022) ). Dimension d is sufficiently large that (0mm22(/(0 (v((21 (2((2)2)/((-211), Training sample size and neural network width m sat- isfy n, m = ((polylogdd),, Learning rate 7) satisfies S Ó(min{[Ivlla" ))" The standard deviation of Gaussian initialization on is approximately chosen such that ((nd min min((apva)) ||v][= I oo S (0mm=2
min[( [v
Theorem B.3 (Theorem 4.4 in Cao et al. (2022). ). For any >> 0, let 7 = -m (ml=- 99. 2(1), =
T (4-2) + n - nm ?)) Under Condition B.2 if n1 SNR
|Ivll//a,v then with probability at least 1-d there exists 0 < t < T such that:
1. The training loss converges to 6, i..., Ls
Ls (W(1) S..
The trained CNN has constant order test loss: (D((()) = O(1)
Note that in our setting, (d 2) o, = (dd.01), ), 7 = m in and 7 = O it's not difficult to verify that Condition B.2 holds. Besides, SNR 0.001 n SNR ((d*)) = (1() Therefore, the conclusion of Theorem B. holds for
(ppoyylog( (d)), @(1), |v]|2 @ad)). 5, m 1/0000 On
T 6 m n( d) 0g ( 2) nmmed ''
O 1 (d //+ (d 3/4 / 1 () + + -22 -2 111-1d22
5( (11 t)g )) -322 11 1112
5(n / 3/2).
46

---

Published as a conference paper at ICLR 2023
C AUXILIARY LEMMAS
For the estimation of ( and (0)), we introduce the following lemma. Lemma C.1 (Borell-TIS inequality). Let X be a centered Gaussian on R and set ox = max]e(m] E(3 Then for each 0,
P max X; - E( max X²) ic/ml
>1)
S 2c x
sE/m]
For the expectation of ( and A we give the following lemma.
Lemma C.2. Let = mixisism Xa, where X; ~ ~N(00, o²) are iid. random variables. Then
Va log2 of Vlogm E S Vlggm
For the estimation of E:ll2 and (E,, E we introduce following lemma.
Lemma C.3 (Lemma B.2 in Cao et al. 2022)). Suppose that ō > 0 and d ((log(4n/65). Then with probability at least - 0,
o2 < |16:13 S $30dd/2.
(E+ s 2 /dlog(4n2/0)
for all i, E [m]. il
Besides, we introduce following lemma about tensor power method.
Lemma C.4. Consider an increasing sequence It 2 defined as T++1 32 + 11. C.al and
C S C S C2 for all & > 0, then we have for A > To. every > 0, and every 17 > 0:
C2 C
log (A/xo) log (1 + 8)
Σ
7
+
(1 + 18)
1+
(1 + 25-
120.0.54
8(1 (5t/ AA)0-2
log (A/2a) log (1 + 5)
Σ $20,I
2
7 (1 (1+ 1)+
|+
(1 + 8)9-1 (1 (1 + 8) (Q-2) Jz0C2
Proof of Lemma C.4 For = 0, 1,2, .,. let Tg be the first iteration such that x, 2 (1+6) 20-
Let be the smallest integer such that (1 + 8) 2 A. By the definition of Tg. we have Ie
[(1 + 8) (1 + pgt+zz)) for all E [Tg. Tg41) and T 2 (1 + 8) zo. IT,-1 < + 8)
leading to
Σ 1E(T):Tg-1)
7 +((1++)xza) S Ita
-T,
Σ
(*+11 - xz)
lE(Tgh7941)
Σ
n Crag-11 <
Σ " C.[(1 + 8)0-12017-1
following lower bound for Tryt1 FTz:
Drg+1 27g = Ztg+1 Dr -1 - 17 Cr 12 129-1 9-1
11
2 (1 + 11++)9+ 8)8t1 11 Tp (1 + 8) v0 - 17 C- -1 6)%20)=-1
= 8(1 + 5)
-1 (1+ 8) (1 (9-1)19 1)g 10 9-1
and following upper bound for IT,+1 Zzg:
Dtg+1 - 2r, = 2Tz41-1 + Or - 1 9-1
1 - IT,
< (1 + ++5)+++0 8) xo + 17 Cz (11 + 5) ()( (0)))=++)200)
(1 + 8) j-1
8(1 80 + C
Cr (1- g-1
47

---

Published as a conference paper at ICLR 2023
Therefore,
Σ n- Co((1 + 800001=11 -
= - n- 0)0+
Σ (E(
n. Ci((1 + 570 x)ot))o000 2 6(1 + 000 11 11
8)67 10000 16
These imply that
8
8
Σ n-Cos
+n -
+n C2(+-81))
(1 + 21000
(1 + 8)(0-2)900
6
Σ TElTu.To 1)
1. C 2
(1 + 8) 2) 11 11 + -0)-(-11) -
2))+ 11 C2(1 + 55--19-11
Recall b is the smallest integer such that (1 + 8)020 2 A, so we can calculate that
6
Σ C. 5
+ C2(1 + 88
(1 0)199222980
120
9=0
8(1 - (1+ (1+0)-(9-21)
+ + C2(1 + 6)0-16
(1 (1 + (1))) 20
8
S (1 - (1 + (1+ n
+ 02(22(1 + 6)
and
8
Σ n C.
77 C2(1+))
(1 + 8)(1 2) (1- 1)z0
120,
9=0
8(1 - (1 + 8) (8-
C2 + 88) -09-1
(1+ 8)5 (1 (1 + 8) 8) (2-2) 20
8(1 - (IO /////-)--11
17 17-(c(1 + 8) -(--2)
(1+ 8)5 (1 (1 (1 + 8) (9-2)) x
where the last inequality is due to (1 + 8) 2 A.
Note that (1 + 5)6-81)0000 To < i.e b 5 1 +
log (A/2o) log (1 (1+) therefore
8
+ n. C7CC(1 +=:11+660-1 (1+ (1+ log (A/mo)
log (1 - 8) )
Σ n.C
(1 - (1+ 8) (1 (1-2) 220
120,2.A
8(1 - ((1-x//A)
- 7. C2(1 + (4-11 (1 (1+
log (A/20) log (1 + 8)
Σ 1 C. (1+ 8)9-1111-0 1 (1 (1 + (10
120.0.5 SA
Note that C < C,5 < C2 we have
+ C2 (1 + 5y0-1 6)--((1+ log (A/zo)
(1+
Σ 3
log (1 + 8) )
(1 - (1+ 8)- (5 2) )ro
C
120.0.5A
8(1 (zo/ / A)
1+ (1+ log (A/zo) log (1 + 8)
Σ
n
- 7. (1 +1 6)-6)))) (1-1)
1 + 8)
[11 (1 + 8) 10-1111) (4-2) 11-2))2202
20
(20,255A
48


Reviews:
[{"review_id": "tiU616Z1qty", "reviewer": "Reviewer_eLuC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper theoretically analyse how self-supervised pretraining can achieve better performance than full supervised training in a synthetic setting, with fixed data, a fixed architecture, and a fixed self-supervised training scheme. More precisely, it looks at how, when a precise data generating process is assumed and a precise architecture is used, combining a form of self-supervised learning with supervised learning achieves zero test loss, while supervised learning achieves a non zero test loss.\n", "summary_of_the_review": "The paper at hand provides a clear and probably correct theoretical analysis of a synthetic self(/semi)-supervised learning setup. Based on this analysis, the paper makes broad claims about self-supervised learning. I believe those claims are too broad, and should be properly tamed down to account for the narrowness of the setting considered.\nAside from this claim problem, I am not sure the theoretical results presented here can translate into practical insights, given how far the setup considered is from practical setups of interests.\n\nGiven those points, I don't recommend accepting the paper for now, but I am willing to discuss my current rating with both authors and other reviewers.", "strength_and_weaknesses": "**Strengths:**\n- The paper is reasonably well-written.\n- Most of the hypothesis are clearly presented and the derivations look reasonable (even though I did not go through the full derivations in appendix).\n- While the data and architecture setups are synthetic, the paper analyses the full gradient descent dynamic.\n\n**Weaknesses:**\n- Starting from the title, the claims made by the paper are very strong compared to the restrictive setting presented. This paper does not answer the question asked in the title: 'How does self-supervised learning work?'. It only shows that, in a restrictive (and somehow convoluted, more on that below) setting, one can design a self-supervised learning method, which has only few similarities with existing competitive self-supervised methods, that succeeds in learning more efficiently than a supervised counterpart. I think the title, abstract, and conclusion should be significantly reworked to reflect the restrictions imposed on the setup.\n- The setting presented is very restrictive, and some of the restrictions/design choices diverge quite significantly with usual practical use cases. Without some proper motivations and explanations, it's hard to understand how generalizable the theoretical results provided by the paper are. Some examples of such restrictions/departure from practice:\n  - The paper uses a ReLU^3 activation. Most common activation function are linear when pre-activations grow big, and either saturate or decrease linearily when preactivations get low. How crucial is the use of this specific activation function?\n  - The generation process of the data is extremely simple, far from any practical setup.\n  - SSL methods often rely on 1 pretext task to build a representation, then learn a linear predictor on top of the representation. Here, the paper relies on K pretext tasks to build K features, then aggregate the features linearly. Can we relate this setting to the usual SSL setting?\n  - The architecture that is used is very ad-hoc, with features operating directly on the two separated parts of the data, and with only the input layer being trainable for the pretraining phase. The results obtained might be extremely dependent on this ad-hoc architecture. Would adding trainable features on the second layer break the analysis? Would removing the hard split in both data and architecture break the analysis?\n  While I fully understand that studying setups closer to practically reasonable setups is much harder and might render the analysis intractable, I still believe that the current analysis does not support the claims made.\n- While the paper aims to tackle self-supervised learning, the goal that is used to train the self-supervised model is a mix of pretext goal and supervised goal. This kind of mixing is usually considered semi-supervised more than self-supervised. Framing the paper in the context of semi-supervised learning might be a better fit.\n- There are a couple of hard coded numerical values in condition 4.1. that could probably be replaced by constants bounded by some less ad-hoc thresholds. My personal view would be that this would make the analysis more readable and general, but that is mostly a minor point.\n\n----\nPost rebuttal comments:\nI thank the authors for the efforts they put in the rebuttal. Many of my comments have been addressed and I am therefore raising my rating from 3 to 5. I think all the changes made are net positives. The reason I am not raising my rating further is that I still have my doubts on the practical insights that can be drawn from this analysis, which I already mentioned in my initial review.\n\nA couple of additional remarks/questions:\n- You mentioned in the rebuttal that working with K = 1 would recover a more standard SSL setup. If I am understanding things properly, the case K = 1 means that you are learning a single feature (the logits of a single pseudo-label predictor), then probing on this single feature (and thus learning a single weight a_0). I would still not consider this to be a standard SSL setup, where you would rather remove the final layer of your self-supervised network (here the untrained second layer), and replace it with a linear probe, working on the actual 'self-supervised' features. Am I misunderstanding something?\n- I thank the authors for mentioning the fact that the analysis also worked with n_l = 0 which is something I missed in my first read. I would argue in favor of adding an additional comment mentionning that the case n_l = 0 corresponds to usual self-supervised training, whille n_l > 0 corresponds to a semi-supervised training regime (which only adds some generality to the paper).\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YSOXGtrwtf", "reviewer": "Reviewer_jwNu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper theoretically studies optimization and generalization of self-supervised learning with pseudo labelers setting. The pseudo label and true label are correlated. It considers linear data setting (signal/noise ratio = $O(d^{0.01})$) and two-layer neural networks with ReLU^3 activation function. Comparing two settings (a) train networks on constant labeled data and $O(d)$ pseudo-labeled data (b) train on constant labeled data only, the setting (a) will have $o(1)$ test loss while setting (b) will have $\\Theta(1)$ test loss. The proof idea is to manipulate the gradient and try to give a bound on the signal growth rate and noise growth rate. ", "summary_of_the_review": "The paper is well-writing and has a non-trivial conclusion. However, I have a major concern about unfair comparison in settings (a) and (b). I may accept the paper if the author can fix my concern, otherwise, I tend to reject it. ", "strength_and_weaknesses": "Strength:\n1. In my understanding, the key idea is that pseudo labels with a positive correlation with true labels can provide more gradient projection on the effective directions. When the pseudo-label data number is much larger than the true-label data, there is a generalization gap between settings (a) and (b). The main results in Section 4 are non-trivial. \n2. The paper has clear motivation and good writing. The proof sketch section is comprehensive and insightful. \n\nWeakness:\n\nMy major concern is how to generate pseudo-labels in Condition 4.1. Based on my rough calculation, it needs $\\Theta(d)$ true labeled data to train a non-trivial teacher such that test accuracy can be larger than ½ with a constant margin with high probability (correct me if I am wrong). Then, here is an unfair comparison for setting (b) which only use constant true labels. If both setting (a) and (b) has $\\Theta(d)$ true labeled data, I think the guaranteed generalization gap may be small or even may vanish. Let me know how to fix it or I may misunderstand here. \n\nHere are other concerns:\n1. The paper considers linear data and it is acceptable. However, it is worth considering non-linear data settings such as XOR or low-degree polynomial in [1,2,3]. \n2. It seems the paper is considering neural networks (NN) rather than convolutional neural networks (CNN). \n3. I understand the authors need ReLU^3 in the proof so that the gradient has a better formulation and property. However, it is a good try to consider the ReLU activation function by using some feature purification tricks (Allen-Zhu & Li (2020a)). \n4. How large is $K$ in Section 3.4? Is it necessary to have a $K$ here rather than using $K=1$?\n\n[1] Shi, Zhenmei, Junyi Wei, and Yingyu Liang. \"A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features.\" International Conference on Learning Representations. 2021.\n\n[2] Frei, Spencer, Niladri S. Chatterji, and Peter L. Bartlett. \"Random feature amplification: Feature learning and generalization in neural networks.\" arXiv preprint arXiv:2202.07626 (2022).\n\n[3] Damian, Alexandru, Jason Lee, and Mahdi Soltanolkotabi. \"Neural networks can learn representations with gradient descent.\" Conference on Learning Theory. PMLR, 2022.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "R2Vo4ZBCUw5", "reviewer": "Reviewer_r8ze", "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": "", "summary_of_the_paper": "This is a theoretical paper that aims to prove the benefits of pretext-based self-supervised pretraining before supervised probing. To do so they consider a toy data generative process where the inputs are a concatenation of label-dependent features  (a linear function of the label) and some random features (Gaussian noise such that noise strength is larger signal). They then prove that an overparametrized 2-layer CNN that was pretrained will achieve near-zero downstream test error if the pretraining set is large, while a fully supervised model cannot if the number of labeled data because it will memorize the noise.\n", "summary_of_the_review": "Assuming that the authors modify (or explain why not) their use of the terms \"fine-tuning\" and \"self-supervised learning\" I think that it could be of interest to some theoretical researchers. I am nevertheless not sure whether ICLR is the right venue to reach such researchers. ", "strength_and_weaknesses": "**UPDATE**: I’m updating my score 5->6 given that the authors addressed some of my initial concerns. The main remaining issues with this theoretical paper is that there are no actionable insights and that the considered setting is far from practice.\n- - -\n\nStrength:\n- **theory is non-trivial** \n- **proof sketch is clear and useful**\n- **good review of related work**\n\nWeakness\n- (addressed in rebuttal) **Some lack of clarity in SSL nomenclature** multiple times when reading the paper the authors used terms that indicate that one setting was considered when actually it was not. For example:\n    - linear probing vs fine-tuning. You often say that the model is \"fine-tuned on small amount of labeled data\", which suggests that you are finetuning all the weights of your model (eg abstract or figure 2). In other places, you seem to suggest that you only train a linear probe but freeze the pretrained model (eg end of section 3.1). From section 3.2 it seems that you indeed only train a linear probe with weights $a_k$\n    - you use the term \"pretext task\" which in SSL typically means some task that is not directly related to the downstream task (eg predicting frames in a video, predicting the rotation of an image, predicting the order after a jigsaw transformation ...). Yet the paper is really about pseudo labeling in the sense that the pseudo labels are noisy labels of the downstream tasks\n   - The model seems to be a 2 layer neural network instead of a CNN? Or is that a CNN with stride $d$?\n- (addressed in rebuttal) **Not about self-supervised learning** as I just mentioned the paper is about pretraining to fit pseudo labels that are noisy versions of the downstream labels. This is not about self-supervised learning but semi-supervised learning (the pseudolabeler has to first be trained with some labels). To be clear there is nothing wrong with studying pseudo-labeling in semi-supervised learning but I think that the paper (especially the title) is misleading because of that.\n- **toy assumptions** the setting is very toy (2-layer CNN, toy data generating process, uncommon SSL setting ...). That being said I do think that the high-level idea might generalize to more realistic settings.\n- (addressed in rebuttal) **title and abstract are too grandiose** the title and abstract make it seem that the authors do much more than they actually prove. Authors need to be clear how constraint and limited the considered setting is.\n\n**Question**\n- **Is it really about representation learning?** the title and abstract seem to put much emphasis on \"a representation learning perspective\" but wouldn't a supervised learning model that is jointly trained on the pseudo labels and the real labels have the same performance gains? (with proper scheduling of the ratio of pseudo and actual labels\"", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster