Towards Understanding Why Mask Reconstruction Pretraining Helps in Downstream Tasks
Authors: Jiachun Pan
Pan Zhou
Shuicheng YAN
Venue: ICLR 2023 poster (2023)

Abstract: For unsupervised pretraining, mask-reconstruction pretraining (MRP) approaches, e.g. MAE and data2vec, randomly mask input patches and then reconstruct the pixels or semantic features of these masked patches via an auto-encoder. Then for a downstream task, supervised fine-tuning the pretrained encoder remarkably surpasses the conventional "supervised learning" (SL) trained from scratch. However, it is still unclear 1) how MRP performs semantic (feature) learning in the pretraining phase and 2) why it helps in downstream tasks.  To solve these problems, we first theoretically show that on an auto-encoder of a two/one-layered convolution encoder/decoder, MRP can capture all discriminative semantics of each potential semantic class in the pretraining dataset. Then considering the fact that the pretraining dataset is of huge size and high diversity and thus covers most semantics in downstream dataset, in fine-tuning phase, the pretrained encoder can capture as much semantics as it can in downstream datasets, and would not lost these semantics with theoretical guarantees.  In contrast, SL only randomly captures some semantics due to lottery ticket hypothesis. So  MRP provably achieves better performance than SL  on the classification tasks.   Experimental results testify to our data assumptions and also our theoretical implications. 

Published as a conference paper at ICLR 2023
TOWARDS UNDERSTANDING WHY MASK RECON- STRUCTION PRETRAINING HELPS IN DOWNSTREAM TASKS
Jiachun 1.n Sea Al Lab pan.jiachun@u.nun @u.nus.euu
Pan Zhou
Shuicheng Yan!
National University of Singapore [aasupan.yanse) @ sea.com
ABSTRACT
For unsupervised pretraining, mask-reconstruction pretraining (MRP) approaches, egg. MAE (He et al., 2021) and data2vec (Baevski et al., 2022), randomly mask input patches and then reconstruct the pixels or semantic features of these masked patches via an auto-encoder. Then for a downstream task, supervised fine-tuning the pretrained encoder remarkably surpasses the conventional "supervised learning" (SL) trained from scratch. However, it is still unclear 1) how MRP performs seman- tie feature learning in the pretraining phase and 2) why it helps in downstream tasks. To solve these problems, we first theoretically show that on an auto-encoder of a twofone-layered convolution encoder/decoder, MRP can capture all discriminative features of each potential semantic class in the pretraining dataset. Then consider- ing the fact that the pretraining dataset of huge size and high diversity and thus covers most features in downstream dataset, in fine-tuning phase, the pretrained encoder can capture as much features as it can in downstream datasets, and would not lost these features with theoretical guarantees. In contrast, SL only randomly captures some features due to lottery ticket hypothesis. So MRP provably achieves better performance than SL on the classification tasks. Experimental results testify to our data assumptions and also our theoretical implications.
INTRODUCTION
Self-supervised learning (SSL) has emerged as popular and effective method to learn unsupervised representations, with great success witnessed by many downstream tasks, e.g. image classification (He et al., 201 6a), object detection (Girshick et al., 2015; Tan et al., 2020) and segmentation (Ronneberger et al., 2015; He et al., 2017). In SSI., one often needs to first create an artificial supervised learning problem, a.k.a. a pretext task, that can obtain pseudo data labels via well designing the task itself, and then train a network for learning how to capture useful data features from this artificial supervised task. For example, one representative SSL, contrastive learning (He et al., 2020a; Chen al., 2020b), constructs a supervised problem on an unlabeled dataset via regarding random augmentations of an image separate class, and then performs supervised instance discrimination. Owing to the unnecessity of manual annotations and its great success, SSL has already paved a new way to solve unsupervised learning problems, and also has attracted increasing research interests.
In this work, we are particularly interested in the recently proposed mes--reccnnttruttinn pretraining (MRP) of SSL families (Xie al., 2021; Dong et al., 2021), e.g. MAE (He et al., 2021) and data2vec (Baevski et al., 2022). The core idea of this MRP family is to randomly mask the patches of the input image and then reconstruct the pixels or semantic features of these masked patches via an auto-encoder. After pretraining on a large-scale unsupervised dataset, MRP fine-tunes the encoder on a specific downstream task to learn more task-specific representations. This pretraining mechanism generally enjoys remarkable test performance improvement on the same downstream task and also a much superior generalization ability on out-of-distrbution data than the standard end-to-end "supervised learning".. Actually, it also reveals better fine-tume fine-tuning performance than other sfate-of-the-art SSL approaches, including contrastive learning (He et al., 2020a; Chen et al., 2020b) and clustering learning (Caron et al., 2018; Wu et al., 2018). Because of its simplicity and strong
"qqual contribution. Pan Jiachun did this work during internship at Sea AT Lah.

---

Published as a conference paper at ICLR 2023
compatibility, MRP has attracted wide interests and is seeing increasingly more applications. However, theoretical analyses and understandings on MRP still largely lag their practical applications. To be specifie. it is not clear how MRP performs feature learning via the mask reconstruction task, though heavily desired. Moreover, the theoretical reasons for the superiority in test performance of MRP over end-to-end supervised learning
rarely investigated. Most existing theoretical works (Wen & Li, 2021; Arora et al., 2019 Tosh et al., 202 focus on analyzing contrastive learning, and few works study MRP which differs much from contrastive learning. Cao et al. (2022) analyzed the patch-based attention in MAE via an integral kernel but did not study the core questions in this work, i.e. what features does MRP learn and 2) why does MRP beat conventional supervised learning.
Contributions. In this work, we provide a theoretical viewpoint to understand the semantic (feature) learning process of MRP. Moreover, we analyze test performance of MRP to show its superiority over supervised learning on the downstream classification tasks. Our contributions are highlighted below.
Firstly, based on the multi- -iew data assumption from (Allen-Zhu & Li, 2020) where multi/single discriminative features exist in nulti-view/single-view data, we prove that a moo/one-layyeed convolution encoder/decoder, the pretrained encoder in MRP can capture all the discriminative features of each semantic class in the pretraining dataset. Moreover, convolution kernel in the encoder captures at most a feature. These properties benefit the downstream tasks. As the pretraining dataset is often much larger than downstream dataset, pretraining dataset (approximately) covers all the features in the downstream dataset. So the kernels of the pretrained encoder also well grab the features in downstream datasets. Besides, as kernel is associated with most feature, then the semantic features would not be fused together, allowing a network to easily establish the relation among kernels and semantic class labels in downstream classification task.
auto-encoder with
Secondly, we theoretically show that after fine-tuning on the downstream dataset, MRP enjoys superior test performance to that of end-to-end supervised learning on the downstream tasks by using classification as an example. Assuming pretraining and downstream datasets share the same distribution, we prove that after fine-tuning, MRP can classify the new samples correctly with high probability for both multi-view and single-view test data. This result is superior to (Allen-Zhu & Li, 2020), which shows the conventional SL only has a half test accuracy on single-view test data.
2 RELATED WORKS
SSL approaches. According the pretext tasks, the current SSL approaches can be grouped into contrastive learning, egg. (Hjelm et al., 2018; Oord et al., 2018), clustering learning, e.g. (Caron et al., 2018; Wu et al., 2018) and mask-reconttruuttinn pretraining (MRP) (He al., 2021; Baevski et al., 2022). Given random augmentations of an image, contrastive learning, e.g. MoCo (He et al., 2020a) and SimCLR (Chen et al., 2020a), brings the different crops of the same image together, and pushes the crops of different images far away from each other in the feature space. For clustering learning, aims to cluster similar samples into the same group. However, both contrastive learning and clustering learning heavily depend on the multi-crop augmentations. The recently proposed MRP is simpler SSL. This MRP family, e.g. MAE (He et al., 2021) and SimMIM (Xie et al., 2021), randomly masks image patches and then reconstructs the masked patches via an auto-encoder. Later, both MaskFeat (Wei et al., 2021) and data2vec (Baevski et al., 2022) empirically find better performance by reconstructing semantic feature. Now MRP has surpassed the end-to-end supervised learning on many downstream tasks, e.g. image classification (Dong et al., 2021) and object detection (He et al., 2021), and is seeing more applications because of its effectiveness and strong compatibility.
SSL amalysis. Despite its remarkable success in practice, the theoretical understanding of SSL is still largely absent. Arora et al. (2019) provided generalization guarantees for contrastive learning on linear classification models with the assumption that different positives belong to the same latent class. Wang & Isola (2020) showed that contrastive learning can trade-off the alignment and uniformity of features on a hypersphere. HaoChen et al. (2021) proposed and analyzed spectral version of contrastive loss with provable accuracy guarantees under linear probing evaluation. Tian et al. (2020) proved that SimCLR only captures feature variability across data points. However, these theoretical works mainly study contrastive learning which essentially differs from MRP. The most closely relevant work to ours is (Lee et al., 2021; Cao et al., 2022). Cao et al. (2022) analyzed the patch- attention in MAE via an integral kernel by showing the benefits of patchifying, the equivalence between the attention mechanism in MAE and a learnable integral kernel transform, etc. However, they did not reveal any feature properties of MRP and the superiority reasons of MRP over conventional supervised learnin.. Lee et al. (2021) showed the benefits of reconstruction partial
2

---

Published as a conference paper at ICLR 2023
Figure I: Visualization of ResNet50 (He et al., 201 trained by conventional supervised learning. We use Eigen- Eigen-CAM CAM to localize class- image regions which show why the model predicts the image as the corresponding class. Though ResNet50 predicts all car images correctly, it actually locates different regions, e.g. front, side window, car nose, taillight, and wheel, for different images, indicating multiple independent features for each class and thus the "multi-view" data assumption.
data from another partial data on reducing sample complexity of the downstream tasks under the condition where two pieces are independent conditioned on their semantic label. But this independent condition is not the real cases where the two parts of the same image will share a significant amount of information not explained by the label (Bansal et al., 2020). Moreover, these works do not study how features are learned by networks, which is essential to understanding MRP in practice.
PROBLEM SETUP
Here we first introduce "multi-view" data assumption introduced in (Allen-Zhu & Li, 2020), and then present the pretraining framework of mask-reconstruction most MRP works, we use a k-classification task as a downstream task for analysis. In this work, we use O,2, θ to hide constants w.r.t. k and Ô, Ω2 Ô to hide polylogarithmic factors w.r.t. k. We use poly(k) (polylog(k) to denote O(:C)) (O(log k:)) with constant > 0. [n] denotes (1.2..... n).
pretraining (MRP). Finally, following
3.1 MULTI- VIEW DATA DISTRIBUTION
On realistic data, for each semantic class, there are actually several independent features being in effect during the classification process. As shown in Fig. 1, we adopt Eigen-CAM (Muhammad & Yeasin, 2020) to localize class-specific regions which tell us why a model predicts the image as the corresponding class. Here we test on ResNet50 (He et al., 2016b) trained by the Pytorch Team' in a supervised training manner. For all the car images in Fig. 1, though ResNet50 predicts them correctly, Eigen-CAM locates different class-specifee regions, e.g. car front, side window, taillight, and wheel, on different images. These results directly testify to the multiple independent discriminative features in a semantic class. Such a data structure is called "multi-view data" and firstly testified in (Allen-Zhu & Li, 2020). In the following, make the multi-view assumption the realistic data for analysis. The mathematical formulation is similar to (Allen-Zhu & Li, 2020).
Assume that there are k semantic classes, and each data pair is denoted by (X,y), where X = (I1, 22, ..) E (Rd)) has P patches (e.g. (non-)overlap image patches) in which each patch is dimensional, and y E [k] is the label of X. Then suppose there multiple discriminative features associated with each semantic class. For simplicity, here we say two features and define the two feature vectors as U5,1,00,2 Rd for each class i E [K]. Note, our analysis technique can also be extended to multiple features. We further assume feature vectors are orthonormal, i.e.,
Vi, i' E [k)) VI, E [2), || 1, and 1g 1 Uy when (i, # (1,
(1)
Denote the set of all discriminative features of the classes as [VL, 2
Now we introduce the multi-view distribution D,, and single-view distributions D.. where samples from D,, have multiple features, samples from D, has only single main feature. Let Cp be universal constant, s be universal parameter to control feature sparsity, op vāpolylog(k) be
parameter to control magnitude of random noise, and be a parameter to control the feature noise. Definition 3.1 (Multi-view data (Allen-Zhu & Li, 2020)). Data distribution D consists of data from milti-view data Dm with probability 1-p and from single-view data D, with probability p. We define (X,y) D by randomly uniformly selecting label y [k] and generating data X as follows.
visi visiionnreseett____
3

---

Published as a conference paper at ICLR 2023
1) Sample a features V uniformly at random from {M1,1, b.2bity each with probability k-
2) Denote (XX V U ( 2 as the set of feature vectors used in data X.
3) For each v V(X), pick Cp disjoint patches in [P] and denote it as Px(X) (the distribution of these putches can be arbitrary). We denote P(X) ((x)=Ueeee UxEV(x) (X()..
4) IfD D,, is the single-view distribution, pick a value i = i(X) E [2] uniformly random.
5) For each p PP(X)) for some E (.X),, given feature noise Oppy' E [0, 7). we set
=pp "vevy Ap.v2' Ep:
where E. (N is an independent random Gaussian noise. The coefficients 2p 2 0 satisfy For "multiiview" data (X,y) E Dm, EPEP.(X) Ep E [1,O(1)) and EpEp,(x) =8 11 1,)( for an integer 2 2, when u E (wy, Un.2h Ep is uniformly distributed over Cp patches and the marginal distribution of EpEP,(x) Zp left-close.
For "single-view" data (X, v) E DD,, when V
yy EpER. 3p E [1,0(1))
E Eppp,(x) og E [1,0(11) for q 2 2. When v 1113- EpEP,(X) up (()) (here set p= k 0.01 for simplicity). 2p is uniformly distributed over Cp patches.
E PxP),XX) E [Q(1), 0.4] when v E V(X) \ {uy,1, (,,2,, and the marginal distribution of E [PE),(X) Zp is right-close.
6) For each p [PIXP(X), with an independent random Gaussian noise Ep NO0, ?26² I).
Jpp = -veey Opper + Ep,
where each appoo E [0,7] 7 the feature noise.
Intuitively, multi-view data D,, refers to the data with multiple features distributed over patches plus some noise from other features and background noise, while only single main feature exists in single-view data D.. Their mixed distribution D can well characterize realistic data. Based on distribution D, in Sec. 4 we will define the datasets used for pretraining and downstream fine-tuning.
3.2
MASK-CONSTRUCTIUE PRETRAINING FRAMEWORK
As representative MRP. MAE (He et al., 2021) randomly masks the patches of an input image and then reconstructs the pixels of these masked patches via an auto-encoder. Recently, many works show that reconstructing the semantic features often achieves higher performance, where the semantic feature can be obtained by feeding the vanilla full input into teacher network, e.g. a pretrained network (Wei et al., 2021) the exponential moving average (EMA) of encoder in MAE (Dong et al., 2021; Baevski et al., 2022). In this paper, we analyze both Teacher-Student framework and MAE but will focus more the former one because of its slightly higher performance.
Network Architectures. Formally, as shown in Fig 2, we implement the encoder in student network by a two-layer convolution smoothed ReLU network with km kernels denoted by w, E IR r [km]]. for the encoder, its output is defined as
H(X) = [ha (X), (x),,...............)))))))))( Iomm (X)),
where hx,X)=
E
PE(P) ReLU zp))
Here ReLU is smoothed ReLU (Allen-Zhu & Li, 2020) and is defined as follows: for an integer q 2 2 and threshold e = polylog(k)) ReLU((2) = if S O, ReLU(2) = qea-1
2² if E [0, Ø) and
ReLU((2) = = (1 1/4)e if 2 g. The desirable properties of smoothed ReLU function is that when z large is linear with z and when small, will be much smaller. Thus, will make the low-magnitude feature noises much smaller to better separate the true features from feature noises. The decoder is a linear layer parameterized by b, (r E [km]]. and its output is
where (X(X) = (X),, E [km]] Following the practice in MRP (Baevski et al., 2022; Dong et al., 2021), teacher network shares the same architecture with student network, and is smoothed ReLU network parameterized by Wr r E [kem]. Its output is defined as ((X)= = [h (X), h2(X)..... hum (X),,
h'(x)= = [h (XX), ..... Mem (X)],
where h.(X)= = Σ PE[P] (eL
Pretraining of MRP on Pretext Task. Now we define the pretraining loss. Let E = (e1, . Ep): where e is independent Bernoulli variable with Pr(ee 1) 0. In the pretraining, for the linear
4

---

Published as a conference paper at ICLR 2023
Student Network
Teacher Network
ex
21
X
Encoder
60
B(eX)
Decoder
h.
Supervision
Figure 2: Teacher-Student framework studied in this work. Given an input X [21..... Tpl (image or text tokens) with P' patches, this framework randomly masks patches to obtain eX = (1711.....pp with Bernoulli variable Cp to mask, and feeds cX into student encoder H for latent vector (eX). Then, student decoder takes (cx)) as input and outputs h' of all patches to predict the output h of teacher with vanilla input X input. The encoder is two-layer CNN, and the decoder is linear layer. For MAE framework, it has encoder-decoder networks and the decoder have an additional layer to map output of the encoder to recover P patches (see Fig 6 in Appendix).
student decoder, we set its all parameters as b, c(0) a for simplicity, which is provably sufficient for improving downstream tasks. Now we define the empirical mean squared pretraining loss:
E(H::))
2N 2N Σ nE(N] X(II: 2N
Σ ME(N] Exe(amn (X,, (eX,,)
where N is the number of data points for pretraining and eX = (e1æ)1 62 ..... E.pE.. pp
Now we discuss how to pretrain it. Following MRP (Baevski et al., 2022; Dong et al., 2021), we use student update teacher by updating teacher kernel parameters vù, as uن, =ww; 1 + Co and Co C
(t) where we set
1-6 +
(+1) (247). Then we use gradient descent to update student encoder parameters:
- (((+1) w T2EE [V w, L(H::e]]
(2)
Fine-tuning of MRP on Classification Downstream Tasks. Here we consider classification downstream task. Specifically, we fine-tune the pretrained student encoder with an extra linear layer using N₂ labeled samples. We fine-ture mee-tune the network by minimizing the empirical cross-entropy loss:
Ldown (F) = 1 Σ EnEEN,, Ldown (Roow((F22)) Xn; vn),
where F((X)= = F(())=xEa) Us (X), e [k]].
N2
(F(( Here Ldown (F; X,y) - log Ene (xT and Usr,, [km]], i [k] denotes the weights of the extra linear layer. Then we adopt the gradient descent fine-tune the kernels w, of the pretrained encoder and update the parameters U
(++1) =
(t+1) (2) 7/2 V Iooonn FF, Wir u, 1/2 V us,r Iddowa (F),
where the learning rate 7 often much smaller than 7/2 in practice.
4 MAIN RESULTS
Here we first reveal the semantic feature learning process of resosreconitttttionn pretraining (MRP), and then theoretically show why MRP helps downstream tasks by taking the classification task as an example. Finally, intuitively discuss the benefits of MRP to other downstream tasks.
4.1 FEATURE LEARNING PROCESS OF PRETRAINING
Here we mainly show that pretraining can capture the whole features V (defined in (1)) in the pretraining dataset by showing that the correlation scores between the features and the kernels of the student encoder gradually increase during training process. For brevity, we first define
M0
(0) = fr E [lmm] (ww, v..)) 2 A (9) (1 0Q/ log k))}, where ! == max, (w +..))+
Here (1) denotes the r-th convolution kernel of the student encoder at the t-th iteration. ( denotes the highest positive correlation score between the 1-th feature v,, of the i-th class and all the km
kernels w( (0)
Larger (!()) means the network better capture the feature vaa- For M (0) it is
5

---

Published as a conference paper at ICLR 2023
composed of the kernels which have slightly smaller correlation scores than the maximum score ALi at the initial stage. For analysis, we pose some assumptions data and the network as follows.
Assumption 1. (1) The pretraining dataset 2 have N samples which are i.d. drawn from the distribution 'D defined in Definition 3.1 and let N 2 poly(k).
(2) Each kernel wt (r E [kml] is initialized by Gaussian distribution NO, ofT) with do O(1/VE). Moreover, m satisfies m E [polylog(k)) vEl.
Assumption 1 means that there are about (1 N "multi-view" samples and μN "single-view" data points in the pretraining dataset 2. According to Definition 3.1, a multi-view sample contains multiple discriminative features distributed over patches plus some noise from other features and background noise, while for a single- sample, it has only single main feature and some noises. We use Gaussian initialization as it is the standard initialization used in practice. Note, for pretraining, we do not use any labels. Theorem 1 states the feature learning process in MRP.
Theorem 1. Suppose Assumption I holds, learning rate 1 S polyty in gradient decent steps (2). After T poly(k) iterations, for sufficiently large k, the learned kernels (wf") }re(km] satisfy the following properties with high probability.
1) Under Teacher-Student framework, when q 2 3. for every Ua E V and every (X.y) E Z,
(a) A E (Noo), ((an)), A,77 E [1/polylog(k), Ö(1] and r' MM where r* argmax,e kom) wu,))..
(b) For each E MM (wf we,)) s 0(00) when (i,1) + (1,
(c) For each r & M.. (w/") v()) < ((ro).
2) Under MAE framework, when 2 4, the properties (a)-(c) also hold.
See the proofs of Seacher-Student framework in Appendix and of MAE framework in Appendix H. Theorem states that for both frameworks, the pretrained model can capture all features. But MAE needs slightly restrictive assumption, since 1) requires q 2 4 where q the smooth parameter in ReLU (see Sec. 3.2), and 2) larger q compresses small feature noises more heavily to better separate the true features from feature noises. This functionality is implemented by teacher in Teacher-Student framework, teacher can filter out feature noise and gives more clean targets.
Theorem (a) shows that for those kernels winning the lottery ticket at the random initialization stage (i.e. kernels wi (0) E _M!")) ), at least one of them would win out through the course of training and capture the feature Us... Specifically, at initialization, for any feature Uy in the whole features V of the pretraining dataset, its correlation score (0) with any kernel ue in (w,) at most ((1/V)).
After MRP pretraining, for any feature U1, there always exists at least a kernel w so that the correlation score A between 11 and wn(") is increased to at least 1/polylog(kk). So each feature in V is captured by at least convolution kernel in the student encoder. Besides, as the pretraining dataset is often much larger than the downstream dataset, the features in pretraining dataset actually (approximately) cover all the features in downstream dataset. So the kernels of the pretrained student encoder is able to capture as much features as possible in downstream datasets.
For Theorem (b) and (c), they mainly guarantee some kinds of corresponding relations among kernels and features: a kernel captures at most a feature. Specifically, from Theorem 1 (b) indicates that for these kernels w, in (! which mainly capture the semantic feature Ui,1 they actually only capture little information of other features uy.r where uy # Ug.,, since for any w. (M its correlation score with Uy is no larger than Ö(ro) and keeps small during the training phase. Theorem 1 (c) shows that for these kernels w/p & MM they keep losing the lottery ticket during training, and only capture little information of feature V;,1- Theorem 1 (b) and (c) together guarantee that a kernel mainly captures at most a feature and can only grab very little information of other features. So the multiple features captured by the encoder kernels is separated and not involved with each other. This property is very important for fine-tuning, since intuitively, kernel is only associated with at most a feature, and accordingly. a linear classifier can directly establish the relations among kernels and semantic class labels. See more discussion in Sec. 4.2.
i,

---

Published as a conference paper at ICLR 2023
4.2 BENEFIT JUSTIFICATION OF MRP ON DOWNSTREAM TASKS
Classification Downstream Task. Here we first analyze the performance of MRP on classification downstream task. After pretraining, following the practice in (Wei et al., 2021; Dong et al., 2021; He et al., 2021; Xie et al., 2021; Baevski et al., 2022), we only fine-tune the student encoder with an extra linear layer on the labeled training data of the downstream datasets. See the details of fine tuning in Sec. 3.2. Before analysis, we first make some mild assumptions.
Assumption 2. (1) The downstream dataset Zdown of N2 samples is i.i.d. drawn from the distribution D defined in Definition 3.1. Let N2 2 K.
(2) We initialize u. i E [l:], r E [km]] by 0 and initialize wi (0) by the pretrained encoder (T))
Assumption 2 actually assumes the pretraining and downstream datasets share the same distribution D. This data assumption accords with the practice many SSL works (Wei et al., 2021; Dong et al., 2021), e.g. MAF (He et al., 2021), SimMIM (Xie et al., 2021) and data2vec (Baevski et al., 2022), which pretrain and fine-tune on the same dataset, e.g. ImageNet, but with significant improvement over the conventional supervised learning. Then based on Theorem I, we analyze the test performance on the classification downstream task, and summarize the results in Theorem 2. We denote the fine-tuning network as function F()) RR which outputs k-dimensional prediction for is classes.
Theorem 2 (Test performance analysis). Suppose Assumption 2 holds. When F()) is either the student encoder in Teacher-Student framework or the encoder in MAE with an extra linear layer, by fine-tuning F-) with N2 labeled samples, for any new data point (X,9)~7] F()) satisfies
Pr(xanD (x)()) 2 maxi+y F2(X) + + 2 1 - e -O(log" k)
where (X) denotes the y-th element in F(X), i.e. the predicted probability for the class y-
See its proof in Appendix G. Theorem 2 guarantees that no matter for single-view or multi-view data (X,w) DD the fine-tuned classifier F()) always correctly predicts the label y with high probability. This is because intuitively, as proved in Theorem (a), after pretraining, for each discriminative feature U1 in the feature set V. at least a kernel w, in the pretrained student encoder can capture This means that even at the beginning of the fine tuning, the encoder in the function F(-) is already capable to discover and grab all features in V. Then as shown Theorem (b) and (c), kernel captures at most feature. In this way, for single-view sample containing a single feature denoted by Ve,i. the corresponding kernels in the encoder would capture it and output a large correlation score (
1/polylog(k)) at the corresponding positions and small correlation scores ( S Ó(L/Vk) at the remaining positions. Similarly, for multi-view samples including several features, the corresponding kernels have large correlation scores at some specific kernels while small ones for remaining kernels. For class, these positions of high scores would not change, because all features are captured and a kernel grabs at most a feature. Based on this, the last linear layer F-)) can easily establish the corresponding relation between large score positions and feature labels, and learns classify.
Then we compare the test performance with conventional end-to-end "supervised learning" (SL) on the same downstream dataset. Under the same data distribution and the same network F, Allen-Zhu & Li (2020) analyzed the test performance of SL (see Lemma 1).
Lemma 1. Suppose the data assumption in Assumption 2 holds and now let sample number N 2 poly(k). Let the learning rate 1) S poly(Ey) Then by training F after T = "
poly(k)
iterations with supervised training, with probability 1 -S0og" k), the supervised trained model FTT)) satisfies
Pr(X.))> 3i E [A] F St. (X) < (T) (x)) E [0.49,,0.51,p)
Lemma shows that the supervised trained model ( has only about 50% accuracy on single-view data whose ratio among all data is u. Both our Theorems and Lemma 1 are proved using lottery ticket hypothesis (Allen-Zhu & Li, 2020; Wen & Li, 2021; Allen-Zhu & Li, 2022: Frankle Carbin, 2019) and we discuss the detailed difference between our work and (Allen-Zhu & Li, 2020) in terms of network architecture, objective loss and fine-tuning on downstream tasks in Appendix C. For supervised training, when the convolution kernels are randomly initialized, for each class, feature correlates more with kernels than other features. With more training iterations, this feature become a winning lottery over other features. Thus, for those single-view data without the captured features, the classification will make an error and obtain only half accuracy for total dataset. By comparison, in MRP including both reacher-ttudent framework and MAE, all features are captured in the pretraining,
7

---

Published as a conference paper at ICLR 2023
and thus has stronger capacity to capture more kinds of features for each class. This also accords with our empirical observations in Sec. 5. Specifically, Fig. 3 visualizes the class-specific image regions for both models trained by SL and MRP. By comparison, MRP captures multiple discriminative features in an image, while SL. only captures single feature.
Discussion Other Downstream Tasks. Besides classification downstream task, our conclusion could intuitively generalize to other downstream tasks, e.g. transfer learning and detection, because in the pretraing phase, our encoder have provably captured all feature features in each images.
For transfer learning, the representative task is classification task Tels (He et al., 2020b; 2021) which pretrains a model on large-scale unlabeled data Prr and then fine-tunes the pretrained model on classification downstream dataset D Dine. Denote the feature set of dataset D Dine as V". We discuss this transfer learning in three cases: 1) the datasets D Dine and D pre share the same feature set V (i.e. V V) but can have different data distribution (e.g. different ratio of single- and multi view data); 2) V C V" 3) the pretraining and downstream tasks share the partial semantic set, i.e., VU V + O. For the case (1) and (2), following the similar proof process of Theorem 2, the fine-tuned model can also obtain high classification accuracy on downstream tasks. For the case (3), as our training networks are wver-parameterized i.e., m E [polylog(k), vkj and the size of the lottery ticket winning set is O(polylog(N) [k)) at the end of pre-training, the number of kernel weights that finally capture the features is much smaller than the total number of kernels. For the remaining kernels, they still can capture new features in the downstream fine-tuning phase. In this way, MRP still improves the overall transfer learning performance. The experimental results on transfer learning in Table 1 also support our above analysis. While the pretraining dataset, i.e. ImageNet, and the downstream dataset, VOCO7, share many different categories and thus have different features, MRP still performs better than the supervised case, which validates our analysis.
For object detection downstream task, it has two targets: 1) finding the bounding boxes of possible objects, and 2) classifying bounding boxes. For bounding box detection, since a) the encoder pretrained by MRP can grab all features and b) the desired bounding boxes should contain features, the encoder can detect the bounding boxes precisely, at least does not lose many bounding boxes of objects. In contrast, supervised learning often randomly captures feature features (Allen-Zhu & Li, 2020) and thus cannot well detect bounding boxes. For the second target, i.e. classification, we can draw similar results the transformer learning classification task that MRP often performs better than supervised learning. So by considering the advantages of MRP over supervised learning on the two targets in object detection, MRP should expect better performance than supervised learning.
Comparison to Other SSL Analysis. Only a few works have studied MRP. Cao et al. (2022) revealed the benefits of patchifying and the equivalence between the attention mechanism in MAE, etc. But they did not analyze any feature learning process of MRP and the superiority reasons of MRP over supervised learning. Lee al. (2021) showed that by splitting an input into two pieces, the pretext tasks of reconstructing one piece from another piece can decrease the sample complexity of the downstream tasks. Though promising, they require the two pieces to be approximately independent conditioned on their feature label, which contradicts many realistic cases where the two parts of the same image share a significant amount of information not explained by the label (Bansal et al., 2020). In contrast, under multi-view data assumptions verified by (Allen-Zhu & Li, 2020) and our experimental results, we reveal how features are learned by MRP, and also explicitly show the performance improvement on downstream tasks, which is essential to understanding MRP in practice.
Discussion on CNN Architectures. We analyze CNNs because of two reasons. One is for casy comparison with supervised results of same encoder network in (Allen-Zhu & Li, 2020). Another one is the difficulty of analyzing the feature learning process of Transformer due to its correlated manipulations and highly nonlinear attentions. But this work is the first one that analyzes the feature learning process of MRP on explicit non-linear networks. Moreover, as shown in (Jing et al., 2022: Fang et al., 2022) (see our Appendix B) and our Sec. 5, CNNs pretrained by MRP empirically surpass supervised one on various downstream tasks, e.g. classification, detection and segmentation. Finally, Appendix B shows that Transformers pretrined by MRP also captures more features than supervised one which accords with our observations on CNNs and validates our theory.
Table 1: Performance on Various Downstream Tasks. We use official MRP setting to train ResNet50.
Downstream Tasks
Acc. (%) on ImageNet|
Classification
Transfer learning APrs on VOC07+12 Classification Acc. (%) on VOCO7
Detection
Supervised Training
76.2
58.8
87.5
MRPs
78.0
63.2
91.1
8

---

Published as a conference paper at ICLR 2023
Figure 3: Visualization of ResNet50 (He al., 2016b) respectively trained by supervised learning and MRP. We use Eigen-CAM to localize class-specific image regions. For each pair, the left figure is given by the supervised model, while the right figure comes from the pretrained model. By comparison, the pretrained model often captures more kinds of features than the supervised model.
EXPERIMENTS
Assumption Investigation. To verify our "multi-view" data assumption, we investigate whether there are multiple discriminative features for some classes in ImageNet (Deng al., 2009). To this end, we use the widely used Eigen-CAM (Muhammad & Yeasin, 2020) to visualize which part of an image plays a key role deciding its predicted class. We follow the default setting in Eigen-CAM and use the network parameters of the forth block to compute the project of image in ResNet50 (He et al., 2016b) released by Py PoTrch Team'. As shown in Fig. I of Sec. 3.1, though ResNet50 predicts all the images correctly, Eigen-CAM locates different class spessfcc regions, e.g. front, side window, car nose, taillight, and wheel, for different images. It indicates the existence of multiple independent discriminative features in semantic class and validates our "multi-view" data assumption.
Results on CNN. We investigate the performance of MRP on CNNs. We use the recently proposed SimMIM (Xie et al., 2021), representative MRP, on ResNet50. We use SimMIM rather than MAE (He et al., 2021), as MAE removes the masked patches before encoder but the convolution operations CNN encoder cannot handle masked input, while SimMIM replaces the masked patches by a mask token and can use CNNs. Then we use ResNet50 (4-layered transformer) to implement the encoder (decoder). Next, we pretrain for 300 epochs on ImageNet, and fine-tune pretrained ResNet50 for 100 epochs on ImageNet. Table 1 reports the top-1 accuracy on ImageNet, and shows that on ResNet50, MRP improves supervised training by a large margin. Moreover, we fine-tune our pretrained ResNet50 on transfer learning classification downstream task on VoCO7 and detection task on VoC07+12. The results show that CNNs pretrained by MRP generalizes well on various downstream tasks and indeed often surpasses supervised baselines. These results accord with our theoretical implications that MRP can help downstream tasks by enjoying superior performance than conventional SL. See more results downstream tasks in Appendix B.
Finally, we use Eigen- Eigen-CAM to localize class-specific image regions for both models trained by supervised learning (SL) and MRP. For each pair in Fig. 3, the left image is the visualization of SI., while the right one is from MRP. By comparison, MRP often captures several discriminative features in an image, e.g. front window and door handle in the first pair, while SL only grabs feature, e.g. front window in the first pair. See similar observations on transformer in Appendix B. These results accord with our theory that the advantages of MRP come from its stronger capacity to capture more kinds of class features in the pretraining.
6 CONCLUSION
In this work, we analyze the feature learning process of mask-reconstrruction pretraining (MRP) and show its superiority in downstream tasks. For pretraining, the pretrained encoder in MRP provably captures all discriminative features in the pretraining dataset. Because of its huge size and high diversity, the pretraining dataset covers the features in downstream dataset. So for fine-tuning, the encoder well grabs as much features as it can in downstream datasets, while supervised learning only randomly captures some features due to its random initialization. Thus, the fine-tuned encoder in MRP provably achieves better accuracy than supervised learning on the classification tasks. Experimental results validate our assumptions and also our theoretical implications.

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning, arXiv preprint arXiv:2012.09816, 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988, 2022. doi: O0L1000FOOS33999922100000
S. Arora, H. Khandeparkar, M. Khodak, O. Plevrakis, and N. Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In Proc. Inl'l Conf. Machine Learning, pp. 5628 0088-567, 2019.
Alexei Baevski, Wei-Ning Hsu, Qiantong Xu, Arun Babu, Jiatao Gu, and Michael Auli. Data2vec: A general framework for self-supervised learning in speech, vision and language. arXiv preprint 00Xi::2202.03555. 2022.
Yamini Bansal, Gal Kaplun, and Boaz Barak. For sulerviee learning, rationality implies generalization, provably. arXiv preprint arXiv:2010.088 085008 2020.
Hangbo Bao, Li Dong, and Furu Wei. Beit: Bert vre-training of image transformers. arXiv preprint 00Xiv:2106.08244, 2021.
Shuhao Cao, Peng Xu, and David Clifton. How to understand masked autoencoders. arXiv preprint arXiv:2202.03667, 2022.
M. Caron, P. Bojanowski, A. Joulin, and Matthijs M. Douze. Deep clustering for unsupervised learning of visual features. Proc. European Conf. Computer Vision, pp. 132-149, 2018.
T. Chen, Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning of visual representations. In Proc. Int't I Conf. Machine Learning, 2020a.
X. Chen, H. Fan, R. Girshick, and K. He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.00 04297, 2020b.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 248 255. Ieee, 2009.
Xiaoyi Dong, Jianmin Bao, Ting Zhang, Dongdong Chen, Weiming Zhang, Lu Yuan, Dong Chen, Fang Wen, and Nenghai Yu. Peco: Perceptual codebook for bert pre-training of vision transformers. arXiv preprint arxiv:2111.1277 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint MXX1:20100.11929 2020.
Yuxin Fang, Li Dong, Hangbo Bao, Xinggang Wang, and Furu Wei. Corrupted image modeling for self-supervised visual pre-training. arXiv preprint arXiv:2202.03382. 2022.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Region-based convolutional networks for accurate object detection and segmentation. IEEE transactions on pattern analysis and machine intelligence, 14:::1442158, 2015.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 770-778, 2016 6a.
10

---

Published as a conference paper at ICLR 2023
K. He. H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 9739,9738, 2020a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016b.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE international conference on computer vision, pp. 2961-2969, 2017.
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.
2020b.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. arXiv preprint MxXiv2211.06377 2021.
R. Hjelm, A. Fedorov, S. Lavoie-Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint 1rXiv:/808.00 2018.
Li Jing. Jiachen Zhu, and Yann LeCun. Masked siamese convnets. arXiv preprint arXiv:2206.07700, 2022.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable super-spe learning. Advances in Neural Information Processing Systems, 34, 2021.
Mohammed Bany Muhammad and Mohammed Yeasin. Eigen-cam: Class activation map using principal components, In 2020 International Joint Conference on Neural Networks (IJCN), pp. 1-7, IEEE, 2020.
A. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv preprint FrxXiv:807..032 2018.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241. Springer, 2015.
Mingxing Tan, Ruoming Pang, and Quoc V Le. Efficientdet: Scalable and efficient object detection. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 10781-10790, 2020.
Yuandong Tian, Lantao Yu, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning with dual deep networks. arXiv preprint arXiv:2010.00578 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 learning, multi-view redun- dancy, and linear models. In Algorithmic Learning Theory, pp. 1179-1206. PMLR, 2021b.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference on Machine Learning, pp. 9929-9939, PMLR, 2020.
Chen Wei, Haoqi Fan, Saining Xie, Chao- Yuan Wu, Alan Yuille, and Christoph Feichtenhofer. Masked feature prediction for self self-supervised visual pre-training. arXiv preprint arXiv:21 /2..9133,.009333.. 2021.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11112-11122, PMLR, 18-24 Jul 2021.
11

---

Published as a conference paper at ICLR 2023
Z. Wu, Y. Xiong, S. Yu, and D. Lin. Unsupervised feature learning via non- non-parametric instance discrimination. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 3733-3742, 2018.
Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu. Simmim: A simple framework for masked image modeling. arXiv preprint arXiv: 11.09866 2021.
12

---

Published as a conference paper at ICLR 2023
A OUTLINE OF APPENDIX
This supplementary document contains the main proofs for two main theorems. It is structured as follows. Appendix B first provides more experimental results to compare the learnt features between the conventional supervised learning and the reannstecnntr pretraining. We also provide the results on other downstream tasks under backbone. Moreover, we also visualize the results under Transformer backbone. In Appendix C, present the necessary assumptions and main results feature learning process of mask-reconttruction pretraining. In Appendix D, we introduce the main ideas prove our main results. In Appendix E,, show some technical results. Then we prove Theorem C.4 in Appendix F. Finally, we show the performance on downstream classification tasks (proof of Theorem G.2) in Appendix G. We prove the similar results under MAE framework and have a discussion on BEiT in Appendix H.
B MORE EXPERIMENTAL RESULTS AND DETAILS
(a) airplane
Do
(b) yawl
Figure 4: Class-specific visualization of ResNet50 (He et al., 2016b) trained by MRP For each pair, the left figure is given by supervised model, while the right figure comes from the pretrained model. By comparison, pretrained model often captures more kinds of features than supervised model.
In this section, we provide more visualizations to compare the learnt features by conventional supervised learning (SL) and the ress-recontttuction pretraining (MRP). Moreover, we provide more results on other downstream tasks.
More visualization results. Same in the manuscript (Sec. 5), here use Eigen- CAM to localize class-specific image regions for both models trained by SL and MRP. Note, since 1) CAM-alike methods all need well-trained classifier at the top of the backbone, and 2) the pretrained model for MRP has only encoder backbone but no a classifier, we visualize the fine tuned model instead of pretrained model for MRP.
For each pair in Fig. 4, the left image is the visualization of SL, while the right one is from MRP. By comparison, MRP can often capture several discriminative features in image, e.g. the airplane
13

---

Published as a conference paper at ICLR 2023
head and airplane tail in the first pair, while SL only captures feature, e.g. airplane tail in the first pair. These results also accord with our theory that the advantages of MRP come from its stronger capacity to capture more kinds of features for each class in the pretraining phase.
Results on other downstream tasks. Actually, some works, egg. (Jing et al., 2022; Fang et al., 2022), also empirically find that CNNs pretrained by MRP generalize well on various downstream tasks, e.g., detection and segmentation. Specifically, Fang et al. (2022) showed that on ResNet50, MRP achieves 38.0 mloU on ADE20K semantic segmentation task and greatly improves the 36.1 mloU of supervised learning baseline. See these results in its Table 3 (b). Indeed, Table 4 in work (Jing et al., 2022) also demonstrates that on VoC07+12 detection task, COCO detection task and COCO instance segmentation tasks, ResNet50 pretrained by MRP respectively achieves 64.4 AP75, 42.1 AP 75 and 36.4 AP while supervised ResNet50 respectively achieves 58.8 AP 41.2 AP and 35.2 APT5
Visualization under Transformer backbone. Besides ResNet, we further provide visualization results on Transformer (Dosovitskiy et al., 2020) to display the localize class-specific image regions for both models trained by SL and MRP. For each group in Fig. 5, the left image is the visualization of SL, while the middle one from MAE (He et al., 2021) and the right one is from data2vec (Baevski al., 2022). Here we directly use the official released ViT-base models (Dosovitskiy et al., 2020) of SL MAE and data2vec*.
Then one can observe that both MAE and data2vec usually capture several discriminative features in an image, while SL only captures a feature. For example, in the first comparison group, SL only captures side of car tail. In contrast, MAE grabs two sides of car tail, and data2vec locates both two sides of car tail and captures more, including the car wheel and car window. These results are consistent with the results ResNet50. All these results show the generality of the implication of our theory on MRP
LOUOR
DOOO
HOUDA
Figure 5: Class caesi-peecfiic visualization of ViT-base (Dosovitskiy et al., 2020) trained by MRP For each group, the left image the visualization of supervised model, while the middle one is from MAE and the right one is from data2vec. By comparison, the model trained by MAE and data2vec often captures more kinds of features than supervised model.
2 For official trained SL model, you can download it at https: wwtp.//ceoooooeeeeereeeeeo deit /bl ob/ma i i BRADME_dde t. md.
Foor official trained MAE model, you can download it https://githhbs fa racebookresearcchmaae htth///a///l////aaa ma In/FINTTUN NNTUNE.mO
'For official trained data2vec model, you can download it at htttps://gtthu..... wwwmplee/daaaaaaeee
facebookresearchh/ http://aaarrrgeeeeeeeeeeeee
14

---

Published as a conference paper at ICLR 2023
C MAIN RESULT ON FEATURE LEARNING PROCESS OF MASK-RECONSTRUCTION PRETRAINING
In this section, first show the main result feature learning process ing (MRP). To introduce our main result, we first characterize the kernels at random initialization and during the training process. We first define
pretrain-
A
= max [(of) vx,)) r [Amm]
where uy denotes the r-th convolution kernel of the student encoder at the t-th iteration. Here A the largest positive correlation score between the I-feature Vs.1 of i-th class and all the km kernels Wr
We also define
M = r
r [km] (m))) v..) 2 1 (1. O log k
Here the set M is formed by the kernels which have slightly smaller correlation scores than the maximum score A, at the intial stage. If a kernel w, is not in M it means that the magnitude of inside the random initialization wi is non-trivially lagging behind, comparing to other kernels. Later we will prove that through the course of training, those kernels w, will lose the lottery and not learn anything useful for feature 04
We also have some properties of kernels at initialization 0). The following lemma has been proved in (Allen-Zhu & Li, 2020, Fact B.1.).
Lemma C.1 (The size of M (0) at initialization). With high probability least - k),
have M S ma, where my == (log k).
Then show main result, need some assumptions the parameters and induction hypothesis.
Assumption C.2 (Parameter Assumption). The parameters introduced in the paper need to satisfy the following conditions:
e is the threshold for the smoothed ReLU activation. We assume polylog(E]
q 2 and o o0-2 S E.
y controls feature noise. 7 S Ô [da)
8 controls feature sparsity. 8 == -(polylog(k)))
N w b
v a/k/o 1, 5(k5/2 //99 and P oo -4+1/2
polylog(k) < S Vk.
n কলাo and pol
c()) 1
is the parameter controls the update of weights of Teacher network. 1
1- C
O ((pA4)) )
The following induction hypothesis is important as shows the main properties kernels during the training course.
Induction Hypothesis C.3. For every Us E V. for each r E M for every (X, v) Z,
(a) For every p Po,, we have
(1) r.p) (w.))) _u,,))p + Ō(0r)-
15

---

Published as a conference paper at ICLR 2023
(b) For every p P(()) \ (X,,(X), we have
(wwP.xp) s ((oo)-
(c) For every p [P] P(X), we have
Kw(" ,xpil S ((oonk)
For every r & UietHneeee for every (X, Z.
(d) for every p E P(X), KW, xxp)l S Ö(ou).
(e) for every p E [P] P(X), (uo (0) xx)) s Ō(ookk).
Moreover. for every v.a V: (f) A ((oo)),(1)))
(g) for each r E M (wr" (9 vg)) 2 -((o).
(h) for each r & M! (w,), v.) < (ooo).
Now have the following result on the feature learning process of MRP.
Theorem CA4 (Feature learning process of MRP). Suppose Assumption C.2 holds. By running the gradient descent step in (2) with learning rate r) S poly(k), after T poly(k) iterations, for sufficiently large k > 0, Induction Hypothesis C.3 holds for all iterations = 0, ......TTT T with high probubility.
Differences from the work (Allen-Zhu & Li, 2020). We use the similar multi-view data assump- tion 3.1 as (Allen-Zhu & Li, 2020), since we find it is reasonable and practical assumption and it helpful in proving what we actually have learned in the masseedreconstructtin based pretraining. Besides, we also adopt the same network (two-layer CNNs with smoothed Rel.u activation function) in (Allen-Zhu Li, 2020) as our encoder. It is mainly for easy to compare the supervised learning results in (Allen-Zhu & Li, 2020) and self-supervise results proved by us. This can better illustrate the benefits self-supervised pretraining.
But there are three main differences between our works and (Allen-Zhu & Li, 2020), including network architecture, objective loss and teacher. For network architecture, MRP contains both encoder and decoder, while supervised learning in (Allen-Zhu & Li, 2020) only considers the encoder. As for objective loss, MRP a reconstruction loss of a masked input, while supervised learning in (Allen-Zhu & Li, 2020) uses distillation loss and cross-entropy loss of non-masked input. Finally, in terms of teacher, MRP uses an online teacher whose parameters are changed along with training and thus is more dynamic and complex, while supervised learning in (Allen-Zhu & Li, 2020) uses a well-trained teacher whose parameter is fixed and thus gives a fixed target of an image. These three big differences cause the different lottery tickets winning or losing process during the training courses. This point can be observed in different practical intuition from our Induction Hypothesis C.3 and from Induction Hypothesis B.3 of (Allen-Zhu Li, 2020). our Induction Hypothesis C.3, no semantic features will lose the lottery tickets, while in (Allen-Zhu & Li, 2020) some of semantic features will be missed during the training courses. Based on different Induction Hypothesis, analysis of reanstrccottttttioon pretraining is non-trivial which is one part of our novel contributions.
Another part of our contributions is that after pretraining, we further need to show the test performance on downstream classification task. In this part, we use the same cross-entropy loss (Allen-Zhu & Li, 2020), which is also popularly adopted in supervised training. But different from (Allen-Ze) & Li, 2020), which simply fixed the linear coefficients of output of convolution kernels of the encoder (backbone) by 1, here we need to train the weights of an extra linear layer and fine-tune the weights of convolution kernels of the encoder the same time (see (15) in Appendix G).
16

---

Published as a conference paper at ICLR 2023
D PROOF OVERVIEW OF THEOREM C.4
In this section, we introduce the main steps to prove Theorem C.4. The proof of Theorem C.4 includes two process. First, when & S To. where To O no0 2
x)) and when [To. T,, where
T - To S ( kTo /
7
D.I INITIAL STAGE
The initial stage of the training process is defined as the training iterations To, where To - ). In this stage, kernels in M will focus on learning feature Ug,-- More formally, we will
① 100
prove that at least one of kerelss in M will capture the feature vg i.e.,
max (w (T6) va,) 2 polylog(k)
rEM
This indicates that the maximum correlation between kernels inside M (0) and feature Us.t will grow.
Next, since the kernels inside M have captured the main correlations with feature vgA what about the kernels outside ! To answer this question, we will show that for w, & M!
(wf (T)) vaa) S 0(0p)= =0
which means that the correlations with feature Vi.t will keep small. For those kernels that the magnitude of 1 is lagging behind at initialization, it will loss the lottery and capture little feature v..
(0) Furthermore, will those kernels inside M. capture other feature Uy # und? The answer is no. So show this point, also prove that for M
(T) uz,² < Ö(oo), Yogr # u.l.
Besides, the kernels will also not be influenced by the noises, ie., for all r,r E [km], for every E (P).
(T) 2 ( pply((k)) (
D.2 CONVERGENCE STAGE
In this stage, when E [To, 7], since part kernels have won the lottery, its correlations with corresponding feature will continue hold in this stage. But in this stage, the gradient will become small which drives the learning process to converge.
The intuition here is that, when the correlation between weights and its corresponding features grows over the threshold the gradients will become to be small. That is when the kernels learned the corresponding feature, the increasing in the correlation will be small and thus drive the learning process to converge. We will show that after i 2 To.
) for w, E M! (0)
(V to L(I), v..) S
While the gradients with other features (features not captured by this kernels) keep to be smaller. In this way, the correlation between weights and its corresponding features will not grow too large and we will show that
max (T) ,,,))) S Ô())
rEM
(0)
17

---

Published as a conference paper at ICLR 2023
E SOME TECHNICAL RESULTS
In this section, we first show the gradient and its approximations. We also state some consequences from our Induction Hypothesis C.3. They all are useful in our later proof of the main results.
E.1 GRADIENTS AND ITS APPROXIMATIONS
Recall
I(H:X,c)
Σ
Σ
ReLU(((U, Σ
c(0) RcLUReLL ((wr:)pzp))) ppmp))
rE[km]
PE[P]
PE[P]
and
L(H;X)- Ee[1(H;
1 Σ
Σ
ReLU ((rr)
Σ
(eL.U
re]km]
pE[P
PETP
Σ
Σ
(3)
2 0
rE [km] PE[P)
The function of 0. As we make an expectation on the pretraining loss function L(H;; X, e) over when doing gradient descent, the expectation of here E[c] 8) really matters in the analysis. More specifically, based on (3) and from the definition of 6, when > 1, this means P(cp = 1) + 1, i.e. there is nearly no mask. Then according to choice of the teacher's network parameters, when 0 - 1, W. R3 wr, which means that the loss keeps small and so there is nearly no update of parameters of student and teacher models. In this case, the student model cannot learn the useful semantic features in the data. When 0 + 0 (i.c., we mask all the data), W. - oo and L(H; + co. In this case. the student model also cannot learn useful semantic features the data. Overall, there is tradeoff on the mask ratio 0. The analysis also holds under the MAE model in Appendix. H. When 8 0, L(H; X) + sc. When 0 - 1, there is trivial answer make L(H; X) - 0. In both above cases, semantic features will be learned.
The derivation of above loss function is shown as follows. For simplicity of clarification, we denote Dr.p RReLU((k, xp))) and Dr.p = ReI.U Rel.U((wr; (wrrrp)) Then the loss function is
L(H;X,c)
1 Σ 2
(
Dr.p
2 Σ Dr.p
Σ PEIP]
c(0)epBr.e +
Σ
c(0)cpUr.p)
27
rE [Am]]
PE[[]
PE[P
PE[PI
Because 1) we set c(0) and 2) each ep is i.i.d. Bernoulli and E[ep] 0, we obtain
E
Dr.p Σ
c(0)epBr.
2 Σ Dr.p
Σ Dr.p
PE(P)
PE(P)
PE[P]
PE[P)
18

---

Published as a conference paper at ICLR 2023
We also have
27
]
E
Σ
c(0)ppBr.p)
Be
Σ
Eptr.pp
Σ EpUrop)
02
PE[PI
pE[PI
pE[PI
Re
Cpltop
Σ W+
cp' Uripp
0
pEtry
+
Ee
Σ
Σ p'=p
epr Spr'r
O
PE(P)
1
Ee
Σ
eptp/yr.pthn Br.pdtri
+
BE
EpEy
02
DE(P)
p'Fp
DE[P] pr=p
(a)
Σ Ur.p
Σ
Σ Ur.p
Σ
Yru
Dr.pp
0
EP
p'PP
PE(PI
p'mp
Σ Vrw
Σ
Urryy
+
Σ
Vr.p
{
Vtr
B
PE[P]
Pe (P]
p'=p
Σ
Σ p'
Σ
Yr.p
Gr.p'
+
Dr.p
pE[PI
PE[P]
where (a) is because EE Pe(pper]] = 0 when p F p' as we assume the variable in e is independent Bernoulli variable with Pr(ep 1) results, we have
l and E. Eelepeyl= when p p'. Combining the above
L(I; x) [.H
1
Σ
Σ pE(PI
Ur.
Σ PE(P]
Yro
1 + 2
(1-1)
Σ
Σ
Kr.p
2
[km]
rE
re(im]] PP[
which is our result.
We define
2,(X) = Σ ((0,(((0;;))))) - Σ ReLU((w,,;p)) xp)).
PE(P]
ME[Pi
Fact 2.1 (Gradients). Given the data point (X,y) for every wr, E [km].
-V L(X) = Σ (x) ( - ReLU xp))) ReLU ((w,, xp)) Ep.
PE[P]
where ReLU' is the gradient of ReLU, Besides, we set wif Tw) (t)
We define several error terms that will be used in our proofs. Definition E.1. (X) = (0LLE0(X)
Σ
ReLU ((wry 2m
(x)
Vrx((X)= = [OLLE PEP (x)
Σ
ReLU ((W,)
Wra((X) = ( - -1))
ReLU )eLU ((w,,
PEP P (X)
Wr(((X)= = (2 - -1))(ccZEEM))))
Σ
ReLU ((W,(((,,, 2p)) ReLU ((w,, xp));
pEP,,, (X)
Ar,,(X)= = [)))
Σ
Rei. Rel,
(XP
UxJ(X) = [(LLEV(X) 0 12-
19

---

Published as a conference paper at ICLR 2023
We also define some small terms for easy of notation. Definition E.2.
(7 Op) ε = (() P. & = Ö(0 22 )) ((7 op)s,
& 0(0)0-1) (7 + op)s,
& (((00)tt)0-)))
& O(o))) (1+1), & = =(((o))))) P.
We have the following lemma to approximate the gradient. We first approximate the term (X)... Claim E.3 (Bounds on (X)). Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds at iteration Then for every Uiy V. for every every v E a for every (X,9) 2,
(X) A (X) & + Eg.
Proof of Claim E.3. Using the induction hypothesis C.3, for every 1s, E V, for every r E M for every (X, y) E 2,
Φ (X) = Σ
ReLU((ú,, -
(eLU((W,,zæ)))
PE[P]
PE[P]
(c,, ReLU((u,
(X)
Σ
ReLU xp)) ReLU
(cL,U(,,, [p)]]
pEP(X)(P
Σ
ReLU((10 xp)) ReL,((u,
PE(P))P(X)
(a) IoLev(())
ReL xp)) ReLUU((, zp))]
DEP,,,()) (X)
- Ō(og) (s + 1) (((n))))) P.
where (a) is as Cp is a universal constant.
Claim E.4 (Approximations of gradients). Suppose Assumption C.2 holds and Induction Hypothe-
sis C.3 holds al iteration I. Then for every Vaa V, for every ( (X,9) E 2,
(a)
(-V V m. L(X) = Vrai(X)A,,,)))
A... -X)))((XXWW... + + - -Eg - Es + (V,.. + (x.u(X)(7+ + Eg) + (Es + Ed) + E2)
= i, + or # i) (b) for Us # v4a (note that Uy # via means that when j =
|( (-V.,, L(x), (Vrsi(X)Ana W (x)((() (7 kp) = V..,,()) E6) + tp)) + Urg.(() A E2) + (Es + E6)(E +22) -
Es Es.
20

---

Published as a conference paper at ICLR 2023
Proof of Claim E.4. We first prove (a). Using the induction hypothesis C.3 and the fact Cp is universal constant, we have that for Us E V. for every r E M we have
(-Vw, w. L(X), U4,))
Σ
(X) - -1) ReLU)) ((wr, [p)) (() via)
PE[P]
(B-(2)- -(2-0)01010 -2-1) ( ReL.U ((wr: + apper + (vi,i,
E
(p,(X)- - ( (()))(((()))))))) Rece)) ReLU'((u, (()r,, + (oL,)
(EP(N))..,
E
(X) - ReLU(((w,) ReLU ((lp + (oL))E)))
(E(P)((())
Σ (Ana)(X) 1030)-(22 RcL,U(W, xp))) ReLU ((wr. xp))
(X)
E (X), + Es) + Vnsi(X)(Es +6) (t)
+ (X) + & E - -(og))
(1 (s+1)
(X)r)(X) & 1 k((oo))))) (((00k))* (p)
=Vau(X)AAs - (X),((X) + ( &2) + (X) + V.,,, + op))
Es) = (Es + (31 + E2) -Eg- Es
Now we show (6). Using the induction hypothesis C.3, for Un V, for every E M when VJ + Vi,, we have
Vw, w. L(X), Uzx)
Σ (X) - ( RcL(((() ReLU' PE[P]
((,,, RoL U5,z)
(D,(X) - ReLU ReLU ((wr, ((ur:,))) + (p),
(X) (X)
+ +1
(x,(X) -1)RooLT(( xp))) ReLU (wer, aprey + (U)11,p))
pEP))ir(X) (X)
Σ (x,(X) ( Rel.U((w. R ReT.U' ((ur; (VaN, Epl)
(X) (X)}
Σ (0,(X) - (2-1) Rel. Rel.U ReLU ((,,, + (1),155p))
PE(PI(P(X)
-Paul(X)A (x)s(x)) (X
+ op)) op) + Eo)(7 op)
+ UUNi (X) + An)))))))))(E + &g) = & + E2) E3 6--8 -
E.2
SOME RESULTS FROM INDUCTION HYPOTHESIS C.3
GROWTH OF (0)
E.2.1
The following claim shows about at which iteration (0)) will be greater than the threshold @ in the definition of smooth ReLU function.
21

---

Published as a conference paper at ICLR 2023
Claim E.5. Suppose Assumption C.2 holds and induction hypothesis C.3 holds at iteration t. For every vea, suppose (1 S Q. Then we have
(1+1) = 1 + O2 (1)
Proof of Claim E.5. Recall that A. == [a [w m.))]. We choose any r [km] that
makes (w) v.a) 2 ((0)) Now we show the updates. We know that
(w(tt2) v2,) (w(²), m2.1) + Ex [<- Vw, L(Xx, 2t1i
Using Claim E.4, have (-V L(X), v.1) = Vr.t(())nn... (X) - W Ar. ( &)) - - El + (V),,(X) (X) + (p)) E6) (Es + (6) &2)
Recall the definition of Vr,s,,, Ar,,, Wr,s.- As assume A and based smooth ReLU function, we could simplify the above inequalities by only keeping the main increasing term as
definition of
I(X), v1.) = Ar.i,(()) (X)a(()) (X).
This equation is obtained by setting (wr²) vi,i) (2((o)) and compare its order with the remaining term. It is indeed the main increasing term. For (X, 3) E Z, we have
(X) =I4 ev,x) ((w v,,1))
Σ
pEP (X)
=I1 (Ix vq,))
Σ
(79 - (1)2g
(5)
PEPoLi(X)
(X) -xn v..) ReLU ((w vara)) ((w)),,811)) wini))
(2
Σ
29
(6)
p
pEPo;,
Then
(n)x(x))() -X) =
Σ 1 P'EPo,, (X)
(79 - 1)29
-1)
pEP,, (X)
x ((L,LEV()) ReL.U mar) ReLU ((w)f) ((i)))
According to our choice of and &p is uniformly distributed over Cp patches, when (X, y) Zm and y or (X,y) E Zg and = y and i == L, we have
E (xx,)
Σ
Σ (7 1122
11)= I(nLEnoII {[(11)
pEPU
P'EPEL.
When (X,z) E Z, and
y and
i=3 3 - I, we have
(7" 10)2 ( - 1) [(C.
B(x,))
Σ 24
E [
(x)
When (X,y) E and f y, we have
(79- (0-1)))) [(m. 1
Exxa)ez
Σ
4 (1(1))
PEPPE (X)
P'EPaL.
Combining all above results, we have
(w((+1)) vx.1) = (we()) v.)) + (²"
ReLU((w ReLU ((w)9, m.)))
22

---

Published as a conference paper at ICLR 2023
Using Claim B.5, and (o0) A Ó(a)), have the following result:
Claim E.6. Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds for every iteration.
Define To = ① -- We have that when 2 To, satisfies A (0 θ polylog(R)
Proof of Claim E.6. Using the result in E.5 and beginning from A = @(ou), we have that
2q-2
100 ~ A
(1+
17 7
(7)
-
( Thus, when To = O (1 ///
we have
A09 ~ ((on))
which means
1 1, (polylog(k))
F PROOF OF THEOREM C.4
Before formally show Theorem C.4, need some lemmas. First, need prove that for every feature Vú E V. at least one of "diagonal" correlations (wl wa))r r E M (0) grows and the "off-diagonal" correlations (w (1) "yr"), * via decreases. To show these, we provide three lemmas about the lower and upper bound on (w vu))r M and upper bound on (we U33)), U3H1 # U1,. M,
F.1 DIAGONAL CORRELATIONS
The first lemma used to obtain upper bound on A
Lemma F.1. Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds for all iterations < t. We have
Vus, EV: A09 Ô(1)
Proof of Lemma F.I. Based on Claim E.4, we have that for every r !!! (0)
(w((+1), v1,)) (w/0), vn1) (B())) V.u(()))na Wx.,(X) + A),, + Ex)
- (Vr,L(()) + V)),(()(( o,) (E) Ex) + (Es + (E, + E2) Eg - E
When taking the positive part, we know there exists (t)) p. [0, 1] such that
[ww(t+)) v. k(wbt) v.,))++ + n,5 ", E(x,>~ V...( -X.,(() (),,((()(E + +22
(X) + + + & + ( (.) + &3) Es Ea
23

---

Published as a conference paper at ICLR 2023
Suppose are now some iteration l > To- In this stage, Al 2 1/polylog(k). As To
and - poly(kj. we have
800
A (x)ssx)))) - (x))(X)= =
E 2p
Σ (T- 1)2p' - -1)ccp
pEP
('EPv,,(X)
x (e,,)E(()))
ReRR ((uB) val) ReI.U ((w!!) ,(,1))))))))))))
= -0(11/)
[(.., ReLU (( 2a,) ReLU ((w v.))))
t1/g
Using Claim E.5 and we also keep the main increasing term, we have
[wf++) 1, _ra)l** & Kuff) ,,,,)1+ + +
7
ReLU vna) ReLU (lwff) e,,))
kT
$ ku w,,i +
1
ReLU((wF) v.))).
kT
Taking the maximum on both side and as we are at t >> To. we have
[w
vtail+ S max kwf vn,ii* (L+0
n
max rEM
kT
rEM.
When ST= To + ( //
we have
1 S Ō())
The second lemma is used to lower bound on (wr waa), r E M!! and indicates that the diagonal correlations are nearly non-negative. Lemma F.2. Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds for all iterations < We have
Vus, E V. M (wf vna) -Ō(oo).
Proof of Lemma F.2. We start with any iteration t that is va,)) (w.) -((o)) to how negative
the next iteration will be. Without loss of generality, we consider the case when (u v.a) - -(((r)) holds for every 2 I. Now based on Claim E.4, we have
(w (++1) ve,) (w("), (v,) + T (x V (xx(()) - (X) + Ant + E2) - Es E3
+ (Vr,,(X) + V.. (p))(E (p))(Es E6) = (Es E6)(E + Ea)
(0)
(w("), vn)) + BB - - Es (Es + EE)(E E2)
(wo()) v.) t Eg Es + (Es EE) + E2)
where (a) is because that as we assume (wit) vi.) < -((())) we have
W (X)
1/ 1) [(v.,vv(X)
Σ
ReLU((w,, ) (ww, x,))
pEPo..())
(1)
0 - [(LLEV(X))
ReLU up)) + R(oo)) ReLU (wwr, v.)) + 2(
pEPo. (X)
0,
24

---

Published as a conference paper at ICLR 2023
and similar results also hold for r,d, Vr,,d, V. This shows that when & $ To.
(uff+) () (.,)) 2 (w:") ug,1) - 10 1) (1 +o) . -00(((07)))0))) 20- (7 + op)
5²
-
2 Ö(oo) - 1/600000 22 (1 - -(060((0000))))))))))))))))))))) (7 + op)
(1k)))))
2 -0(00)- - 0 + hog - 0op +
koo
(z1))2-11
Vd
Vd
2 -(oo).
When E [To, T). we have
(wff), ....) 2 T un)) - (T (o) (20-11) (7 + - - (a--n((TTT)onn -7))(((07)))*)11) .07))).(7)7))) + o,)) p2 p2
(T)
.2
(T - (1)) (7 + 0p)
2 -0oo).
F.2 OFT-DIAGONAL CORRELATIONS
Lemma F.3. Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds for all iterations
< c. Then
Yegr E V, E M for Us + Peg: (io ..,0,,,,))111 Ō(oa).
Proof of Lemma F3. For every r E M using Claim E.4, we have
((o (t+1) ,1rr) S (m) , (3,r)) + 7 (x,))= ( (Vrss
(x)+ op)
(X) + E6)(7 op) + +Ur Ur)u(( + (
(Es + EE) + -
Stage I. We first consider the stage when & < To. In this stage, similar to the analysis in the proof of Claim E.5, have that
E(x,))= (VrruX))Ansii (x)((x) (r + op))
$0(,) (7 + op) ) (wi() (..)) (uwf), (,,)),
where Ô (t) is the probability of Di E V(X), and
(E1 + ReLU ((u(") ea)),, E Exx,)~ (xx(()((s++ + E6) op) < 20(²)
and
Exx UnSU(X) <o (
where Ô (2) ) is the probability u,, E V(X). Thus, when < To. we also keep the main increasin term and obtain that
(o0 (.,r)) (w, 2,,') +0 + (?) (7 + op) > RcLU ReLU (A
(8)
25

---

Published as a conference paper at ICLR 2023
From Claim E.5, we have that
To-l
To-1
To-1
+ 1
ReLU
R (A!))
Σ
(t+1)
Σ
A
4,1
1=0
1=
i, - -,
(Ta)
(0)
(9)
polylog(k)
Putting (9) into (8), we have that for every S To.
K U/r') & (w,f) 10,)+
( C0
+ + 0 "1
(7 op) RoLUUA (To)
ReLU (A
k Vd
k
< (Go))
Stage II. the second stage, when To, we have
B(xa))=
(
W (x)s(x)) t
<0 KT + op ReLU k.)) ((wff) vc)))
s 0 (7 +.))
KT
where the first inequality is from Lemma F.I. Thus, when t [To, T]
(T)) ugr + δ n(T ' TT))
(wo,", , v,,.)) & (wfff)
(7 tpp
kT///0
(wofT) wz(e) + ((oo/)) Ō(1/vā)
Ō(vo)
Combining all above results, we complete our proof.
F.3 LOTTERY WINING: KERNELS INSIDE M!
In this subsection, we prove that the feature vi captured by kernels not in M is negligible. To prove this result, we first need a lemma from (Allen-Zhu & Li, 2020, Lemma C.19) that compare the growth speed of two sequences of updates of the form T++1 + + CCx, Lemma F.4. Let q 2 be a constant and zo: yo = o(1). ) Let {xt, Me. Nezo two positive sequences updated as
T++1 2 3t -/a for some C. O())
Mt+1 S yt + n for some constant $ @())
Suppose No 2 SoS 1/(a22)) (1+ polylog(M) ). then we must have for every A = 0(1), ler T₃ be the first
iteration such that xt 2 A. then
yT, < O(yo polylog(k)).
Now we begin to prove our result.
Lemma E.5. Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds for all iterations Then
VUgi E V.Vr & M! (w. v.a) < Ö(oo).
Proof of Lemma F.5. When E M (1y,v # v.,). we have prove that (wf") va) S Ö(σv) in Lemma F.3. So we only prove the when MM
26

---

Published as a conference paper at ICLR 2023
We assume that there exists wy & Uee such that induction hypothesis C.3 (a)-(c) holds for every (X, Z. We want the sequence (w va,1) will increase more quickly than max rEM {w, 24,1). Under this assumption, we have that (here we also only keep the main increasing term),
(wp (t+1) vu.) = (we vaa) + (x, (xsx())),.xxX))))) (xss(
(0) S o. We define sequences. First, Stage We first consider when & S To- In this stage, A,
(w,
(0) v.,)) and define Iy == (w Us,1) 1/24 0120-1727 We also
we take wy- = argmax, (EM rEM
define = ( vai) (at) 1/2g 11/-11//4 oo.. From Claim E.5, when S To. we have that
(wp- (1+1)
r(,)) (w (0)
v(,)) + θ
ReLU vc)) ReLU ((W v4,))
2 (wo v(a) + +
81
20 )
k
Let S = ( [+C/(loR(A)-O)
CC> 1. We have
1+1/log(k)
(w, ((+1)
viii) (1 vi.1) + ReLU vc) (ww vw,))
817
(Tx
S (1 via)) +
81)
(KW -121))+)
k
9020-1
Set C2 = 1. Then we have that
F1+1 2 2í + C 2q
Vt+1 S yt + 1/ S/Syy 29-1
Besides, To = =A/_/ and yo I A ( log(k:))) based on the definition of M (0) Here we (0) assume yo S /A (1 C/ log( Thus, we have
log(k) - )) = So (1+
C
To 2 yo
1+
log(k))
So using the result from Lemma F.4, when (ur= (++1) iteration 2 To, we still have that
va.) reaches Ω(1), which necessarily is an
Y$ Ō(jo) = (w.).
m1)) & Ō(Øo).
Stage II We now consider when t E [To, T). In this stage, using the induction hypothesis C.3 (d) and (e), we have that
E(x,)~ (V., [(H; vnd) s0 =00
29-1)
ho
Thus,
(10 (1+1) via) S (10t)) vi.)) + +0
(7
17 2q-1)
s (woST) ,e() + +
'T[ - To)
24-11
0
k
5 {(0o))
27

---

Published as a conference paper at ICLR 2023
F.4 NOISE CORRELATION
In this subsection, prove that the kernels correlate small with the random noise.
Lemma F.6. Suppose Assumption C.2 holds and Induction Hypothesis C.3 holds for all iterations (0)
< L. For every V E V, for every r E Ma for every (X,3) y) E Z, we have
(a) For every p E Pe,, (w, -pp) - 0(00).
(b) For every p E P(X) \ Pi..a (X), Kw .6>I S Ö(oo).
(c) For every p [P] \ P(X), (wlt .pحI s Ö(onk))
Moreover,for every r & M f. for every (X, v) E 2, we have
(d) for every p E P(X), kwy) (s)1 S Ö(0o).
(e) for every p E [P] P(X), (ur (8) EpKi s Ö(aonk).
Proof of Lemma F.6. For every E [km], for every (X*, E Z and every p* E [P], we have that
ReLU ((w,, xp)) ( (xpp Ep-) L(), = E (x)(x) - -0-11 Re]]ReLe (ww,, ReLL(((,,
PE[P]
When X + X*, we have (p:: Ö(op) S o(1/vd); and when X = X* but p + p², we have (0p, Ep. )1 s ( s o(1//d). Therefore, we have
E(x,)~z (-V,,,(X),
E(xwEz EXxwIEZ Ve, (-xx
For the first term.
E (xx)~~
I (- ((),
N (() 2 (x ReLU ((wr, Tp- (2p Ep-)
( - 1) (e., ReL.U ((w), (2 Spr) +
(
1
B(x- $ (X*)) ((Ur:x)))
N
1
1)
ReL.U
)eLU ((w,, to
0
E W22
ToLLEM(X))
ReLU ((w, ReL. ((Wr, [p))]
N
pEP
-1) (euTT(((wr, ReLU ((wr) Vi
x ReLU (Wrr
where (a) is because || 11 = Ô(). For the second term,
E(xa)~2 (Vw. to (11)
28

---

Published as a conference paper at ICLR 2023
Now we begin to prove (a). For every Va,1 E V, for every r E M. for every p" E Pons (X*, using the induction hypothesis C.3, when To]. have
E(X,))~
(-v,, (-V,,L(X), L(X):
E ((x)))> (Irnevexe) (XP)
(79 - 1)22 - -1)-1) ))
= 6
Σ
20-1
Σ
('EPo,,(X-))
1
x ReLU ((w,, vut)) ReLU ((wr, mua))
to
vdl
Thus, we have
(w ( 11 Ep-) S (w, (1) (p.) + + 0(*) 1 ReLU ReLU((Wr, vs ReLU ((w,, vci))) + ( 7
Vd
Now we use the results from Lemma F.1, when s To.
11T0
nTo
(w!") Epr S (w, Ep.) + Ō
+o
N
vd
So when N 2 80 ( and v 2 6(k/o) 1) we have (wt .Ep-) S Ō(ou). Then when
E [To, T]. we have
2(x,)e2 (-Vo. L())
- 1
E Exx (ueLevnx-, (, v. (( vail)) to (Nva)
NT//
Therefore, for E [To, 7j. we have
n(t n To)
n(t To) Vd
(wf), S (wfT)) Epr) ) +
o
S o(0o),
NT. 1/9
when vd 2 @(55/2 / 12).
Now we begin to prove (b). For every p" P(X)) (Xt, using the induction hypothesis C.3,
when E [0, Tol. we have
E(X,))
$
:0(1) 1 N
TeLJEv(x-)
Rel.U((w,, 0(0 + (10.
(22)
Va
(XP
00 N E W2
0(0(0-1)) to Vi
Thus, when To, have
nITo (q-1)
nTu
(w(") (w())Ee)) S (w(²) ) )+1))))) + Ô
0
to
Vd
< Ō(Go),
when N 2 & and Vd 2 k/00 2 Then when t E To, 77, we have
( < (T)) (T)) Ep. + Ō
nn(-(((i) To)
n(t
(q- 00 (0-1) +
n(t - To) ) Ö(ov).
N
We begin to prove (c). For p E [P] P(X), using the induction hypothesis C.3, when t E [0, To).
we have
(xx)) (-V,
B {0
)(((0))))(-1))== + Va
(x-,))>~
2)~~2
29

---

Published as a conference paper at ICLR 2023
Then the process to prove (c) is similar to the proof of (b).
To prove (d) and (c), for every p* E P(X*), using the induction hypothesis C.3, we have
B(x,)) Ix=x- (x,, 5p-) - ( |0105 (2 -)
Vd
and for every p" E EPl\ P(X*), using the induction hypothesis C.3, we have
E(Xw)z Ix=x (-V Vu, I(X), Ep.) s (x) [0((0078)(00))) +
1 vil
Following the similar process, we could also prove (d) and (e).
F.5 PROOF OF THEOREM C.4
In this subsection, will combine all lemmas and begin to prove Theorem C.4.
Proof of Theorem C.4. At iteration f, according to the data structure we defined in Definition 1, we
have
Vp E (X,,((): (w!"
xp)) xxp)
(1o(9) up) +
Σ
Opp (10 ,0) + (1f0 :pp),
(10)
V'EV
Vp (P)PP(S (w/") xp)) Σ N'EV
ap (w(f) v/) (w(()) -s))-
(11)
is easy verify the induction hypothesis C.3 holds at iteration / 0. Suppose induction hypothesis C.3 holds for all iteration < t. We have established several lemmas:
Lemma F.3
Vuga V, Vr M! for UgA * u.u 1(u59, ا.r' s Ō(pa)
(12)
Lemma F.2 and Lemma F.1
Tit V, Vr M (mf ..)) (-o o(1)
(13)
Lemma F.5
(0) (1f v.)) S Ö(o)). Vug e V. & M
(14)
To prove Induction Hypothesis C.3(a), we plug (12) and (13) into (10), and use 0'p,'' =6 2k and ((or &p & o(po) from Lemma F.6(a).
[0, 7]. M
* To prove Induction Hypothesis C.3(b), we plug (12) and (13) into (10), and use Opp.' =E (w,,", s, _ (ap) from Lemma F.6(b).
[0,>], 7). M/
2h and
To prove Induction Hypothesis C.3(c), we plug (12) and (13) into (11), and use ap, =E (wo," S,>l ((ank)) from Lemma F.6(c).
[0, 7). |/ 2k and
To prove Induction Hypothesis C.3(d), plug (14) into (10), and use ap, [0, (wrr Ep=il s ((n) from Lemma F.6(d).
| = 2k and
To prove Induction Hypothesis C.3(e), we plug (14) into (11), and use ap.a =E [0,
V = 2h and (w. (t) Ep>il < (auyk)) from Lemma F.6(e).
Induction Hypothesis C.3 (f), (g) and (h) are easily obtained from Lemma F.2, Lemma F.1 and Lemma F.5.
G TEST PERFORMANCE ON DOWNSTREAM CLASSIFICATION TASKS
In this section, we analyze the performance of reasssrecontt pretraining on downstream classification tasks show its superiority over supervised training.
30

---

Published as a conference paper at ICLR 2023
G.1 1 MAIN RESULTS
We add an extra linear layer on the pretrained encoder. We collect labeled data points Zdown {(X;, 9:) |e DD and use these labeled data points to update the weights Wa,r, å E [k:], E [km]] of the extra linear layer and fine-tune the kernels of the pretrained encoder uy, r E [km]. The output of linear layer is denoted as (X) = [re(km] (,, The loss function on downstream tasks is
Ldown (F)
Ldown Xi,
N2
<E[Na]
e's(x)
where Loown (F; (,,) v)
log
We define logit,(F;;X))
Enery e The gradient
of Ldown (F; X, y) is
uigr Loonn F; X.y) (T:-, (F;
We initialize ui 0, D E [k]. [km] and the initialization of wt E [km] is ( i.e. kernels of the pretrained encoder. We update the weights using gradient descent:
f.r i T/2 V Vurr Lowon XF;X, 3):
(1+1)
w (++1)
w(() mn1 Loown (F; Xx y).
(15)
We set 7h to be much smaller than 7/2-
The following lemma states that the induction hypothesis C.3 still holds in the training of classification tasks.
Lemma G.1. For N₂ 2 many samples, setting the learning rate 1/2 (kk) and m S @(k), after Tdown 2 poly(k) many iterations, for sufficiently large k > 0, Induction Hypothesis C.3 holds for all
Mat iterations with high probability.
Then we have the following theorem showing the performance of downstream classification test. Theorem G.2 (Performance downstream classification tasks). For N2 2 k many samples, setting
the learning rate 12 (k)) and 1 (k:)), after Tdown on v2 probability, we have
poly(k) many iterations, with high
(a) (training loss is small) for every (X, v) E Zdown i.e.
Laown (F) (x) Zaoun (doonn (F; (,;,,)]
poly(k)
(b) (test performance is good) for new data point (X, 3) ~ D, the test performance is
F2(X) 2 max F2(X) + +(1) 21 21-e-S(lo" -lllog k)
(X
G.2 FINETUNING OF DOWNSTREAM CLASSIFICATION MODELS
In this subsection, fine-tune the weights wy, E [km]] of pretrained encoder of Student network and update the weights of the linear layer Wi,r, E [k), r E [km]].
G.2.1
UPDATES OF ui.
We first define several terms which will used frequently. Definition G.3.
(x,(X) = LoL
Σ 2p1
PEP (X)
Vraa = U1))+ Vi,1= =
Σ
2
V
Σ
ViA--
reM
LE [2]
31

---

Published as a conference paper at ICLR 2023
When M, (0) 1 O, using the induction hypothesis C.3, we have
(x) = ())())
ReLU ((wr, + Ō(0o)) + O(f))) (s+ 1) + (((an))))) P
(x)
= =[(w, (exx))(
Σ
2p O(g)) 8 + P
(x)
= -rra (x) + Eg + E
When & [e
0, using the induction hypothesis C.3, we have
h, (X) = ((08)(s 2) (((oork)))) P.
The gradients with respect the output (X) include three types.
(1) Near zero gradients For us. when & ue (0)
(x) = Ö(ag) (s 2) (((ookk))) P.
which is very small. Thus, there is nearly no updates on those weights and they keep near zero, i.e.,
(4) Wir 0 when & UKE(H))EE(g-
(2) Negative gradients For Wi,,, when E Mi + show the gradients us L(F;X, for different type of data points:
(a) when i, for every (X, y) downs
V ((FXX.)) (1 (og
2p E [9(1).0.4)
PEPu,, (X)
(b) when # i but = j, for every (X, v) E Zdown, or (X,3) E Zowwn i i=1, I
vv,, ((F;X,y) logit, LoooooiifFFF.. (F: (P;x))a (X),
Σ
2p [1,)
DEP
(c) when # i but y = j. for every (X, 3) E Zdown, 8- 1= 3 1
vv., (FF 3) llgitt (F; (X),),,
Σ
2p E (p,)(p))
DEPo
(d) when + and y + j. for every (X, v) E Ztown.
V Vu,, L(F;X, logit, (F; (X),
Σ DEPrga(X)
2p [((1).
(3) Positive gradients For us.r. we now show the gradients - V Ms, L(F;X, when r E M! for different type of data points:
(a) when = i, for every (X, y) ~ Zdown. or (X,y) Zdown, i=1
V Vo,, L(F:X.y) (1 logit, (F)
Σ
2p E [1.)
(XPo,,(X)
(b) when = i, for every (X, v) ~ Zdown, 1-3-1.
-V.., L(F; X, y) (1 (F; (X)
Σ
2n 2 Ep (p,)())))
32

---

M2(Es + Eg) Published as a conference paper at ICLR 2023
(c) when y i, for every (X,z) y) E down.
-V u.,, L(F:X,))
E pEPo,, (X)
2 E [1()).
Now we begin to show the full gradients. As we assume the ratio of single-view data is μ poly has little influence on the update of weights. So we ignore single-view data and only focus on (X, 3) E 2down.m- Then when E j.t
SM j + i, we have
00.ss 1hh + Es + E
B ((,,))~ Zoown 1-V un L(F;X, v) (xx,)) Zaoun
[(- (1 (1-iit1 (F;
k:
(X,y)
logt) (O
Uria + Es + EGl
0.4s
( lortigrt)loiitt(FFF (F:it;(F:X))
Wess Es E6
h-
6-1
T0.ss
1
Vridd + Es + E6
Wrrda 0(1) + Es +
k2
k
k2
h: 2
T0.4s
P + Es + E6
12
k
where k 1 R-2 is the ratios for each type of data and at t O. we have logit, (F; (F: = k [K] because we initialize usr = Therefore, if we ignore the small term, at t = 1, we have
(1)
0.4(k 1)s
O(1)
0.4(k 2)s
12(Es + Es)
2 172
13
12
A3
k
0.4s k3
0(1)
172
<.
(16)
122
k
Using this weight, we could also obtain the bounds of loss function after the update of w,,r r E [kmm] (we will show the following inequality in (24) after we update w,))
(1)
0 < 1 - logit, (F:X) 2
k
1
0 < logit,(Fi <
Vi [K] \..
Thus, / 2, we have
(2)
0.4s
0(1)
br + 12(Es E6)
112
1)2(E6 + Eo)
u 1r
2 72
Vridl
43
12
k22
122
(2)
< 1/2
0.4s
0(1)
Vrijj +
12(Es E6)
+0
1/2
Vrijd
72(E8 + Eg)
133
122
k
k3)
222
So the approximation of
2rr
(2)
is
(2) 2.r ~ Ō (ma) thiga + 12(Es + E6)
k
Then for t 2, as we continue to train to minimize the loss function, 1 - logit, (F;X) 1, will become smaller and so as logit,(F",, (F); the first two updates and there is nearly order changes values of weights after the first two step of gradient descent. Thus, for simplicity of analysis, we could take
i E [k] y. So the main term in u,,,, E [kt,, r E [km]] is the term of
(1)
112 Kz
Virga
12(Es + Eo)
for / 2 2.
(17)
b
33

---

Published as a conference paper at ICLR 2023
Similar to the former case, when r E M have
k --1
R(X.g))2 [-V uirr I(F;X.1)
Wriil 0(1) Es En]
k.2
k
1
T0.4s
1r. + Eg + E6
k2
Then if we ignore the small term, at / = 1, we have
12 [()) (k 1) 0.4s(k
n2 + E6) 0.
(1)
Vr,ad +
(18)
A2
1.3
Similar to the former analysis, for simplicity of analysis, we also take that
72 Vrrad + M2(Es + E6)
for 2 2.
(19)
K
G.2.2 FINETUNING OF w, AND PROOF OF LEMMA G.1
After the update of Us,r. we then finetune wi-- We have the gradients:
-V ((F:X,)) (1 logit, (F; (F:X))
Σ
ReLU ((w,,z)))
PE[P]
logit, (F;X) Juir
Σ
ReLU ((wr, Tp) )xp
W
W
ME(P]
(1 logit (egit,(FF))) (F;X))uy
(F;
ReLU (wwr xp)))
JE
PE[P]
(0) Diagonal correlations. For r E M! as we initialize w, by the pretrained encoder, we have
Σ
ReLU ((wr v1)) (V,)E)(x))
Σ
ReLU ((w, (p),,, + 7 + op)
PE[P]
PEP
+ (1 t . (s+ 1)
(((o0)))))4) (1 + op) P.
Thus,
(- v. L(F; X,y), vc.) = (Vras + El + E2) (1 -1l-lggit, (F; UU)
Σ
logit, (F; X X)uj,r
JE
(20)
At t = 1, for every (X,v) ~ Zdown. when = put (16) and (18) into (20), we have
O(1)
0.4s
v-,,,, L(F; X,); v2a) = 1/2
(Vr,i, + E + E2 logit,, X))
h
22
(2(Es Ea)
+ (Vr,a, + E + 82)
k
Similarly, when +
(_0(1) +
0.4s
(-V L(F; X, v), = 1/2
(Vr + E, + Eg)logit, (F; X)braa
12
1a5Es Ea)
+ (Vr., + E + E2)
k
Denote Si,1 EpeP,,, (X) Zp- We have
O(1)
0.4s
Se,1 k-1
Exx, (xx.a)) KK- [(F;; X, y), ma,))
1/2
122
1e
1
((1)
0.4s
Ta(Es + E6) k Sipbraa
1/2
+
St,1 k22
l
122
k
(K:
1)s
O(1)
0.4s
12(Es + Es)
7/2
122
12
k
34

---

Published as a conference paper at ICLR 2023
Thus, at t 1, we have
(wef , Mad) = ( ((,)) +0
11722
Vrai +
m2 + E6)
(21)
k-2
k
A O
(2)
72 k2
(2)
MinelEs + EE) S Ö(1)
k
when 7/17/2 S Ō(.)). The lower bound on (w/") (5,1) can be easily obtained by similar methods.
Besides, for t > 1, for every (X, v) Zdown, when i = y, putting (17) and (19) into (20) and keeping the main term, we have
(-V w L(F X. v), vad) R Ô
112 k (Vigs + & + 82) - logit (F; x))
+ (Vrit + & + &2) 12(Es + Eg)
h
Similarly, when +
(-V n LGF; L(F - (T)
k (Vrig +1 + Eg)ogi,, (F; X)vva 72(Es + Es)
+ (Vrat El + +2)
Suppose induction hypothesis C.3 holds at time Now we have that
E(X.y)~ i [[- V W., L(F; (F; 3). vr,i
[(u=s) logit, S (F; (F; X))
k
-..4I pogii logit, (F::) + (Es + E6)
where (a) is because for y # i, Vr 0.4T (v. S 0.4, and
E (XX.))
((-V
V w. I. [(FFX,,)) v), U
(n)
112 v Exx Zaoman - (1 logit,, (F; (F:
0.44 (o) x3)
+ 12(55 + En)
Thus, using the result ohria, polylog(k]] we obtain
Σ (2u(+2)) v2.1) 2 (w v..)) ② 1117/2 E E(x,g)- Zoown kE(k]
(1 logit, (F: + m172(Es + E6).
(E(
As the induction hypothesis C.3 still holds in the training process, have A.0 Ō((). Thus,
Taown
(1 (1gi (F; (
+ +Ô ((TaommlES + E6)
R-2
E(x,))~
50
(22)
7/772
So, we assume induction hypothesis C.3 holds for all iteration < f, then
(w (u.) S (w v..)) +
7172
E (xx1)) Zeomu (1 - logit, (F; (F;X))
12
1=1
tn) Ex)
b < Ō(1).
35

---

Published as a conference paper at ICLR 2023
Off-diagonal correlations.
For E M. as initialize wo by the pretrained encoder, have
Σ
ReLU 2p)) 25r) = (x) + O(o &2.
PE(P)
Thus,
(-V w. (FF.
(X) op) + [1o,evvc))0000 1 E2)
x (1 - logit, (F; (F;))) - E
logit, (F; X)uji
(23)
JERRKT
At / = 1, for every (X, ~ Zoown, when = put (16) and (18) into (23), we have
L,,, U,y)) = ((7 + op) + EVxx
(0(1)
(1 - logit, y (F; M + 0.48
72(E5 + &6)
x
12
k
12
k
Similarly, when y but y j.
(-V,,, ,) إرر) = (I
+ (pp) + Ō
E + EZ)
O())
0.4s
logit, (FiX) + 72(Es + E6)
72
+
k
k22
When + i and y + j.
(-V n. L(F X, 1z,)
(4u) (1 top) + 101 + + Eg)
0(1)
0.4s
(F: + (E + E6)
122
k
122
Therefore,
((x.))>Zaomn 1( m. L[F;; X, X)F; 03,1')
1 ((7 + op) + :(300 0(s00)1/kk)mm
((11) 0.4s)
k
Urail
k
12
k
T. (7 (7 + 0p) + 0(08-11) 7/2
1 (8
O())
0.4s
+
k
1:2
k 8
( (7 + op) + 0(50000111100 1k)) 772
((1)
0.4s
1
+
h
k
k2
k
12(7 (Es + E6)
h
((r + op) + O 1))22 ((11)
0.4s
72(7 + op) + Ea)
Vr.a +
k
12
k
Thus, at t 1, we have
(w v...) & (") ).Nr + +
(1122 (y (1+
Ur.t + m7 + op)(Es + E6)
< Ō(
622
k
when 1172 5 Ōkk2). Suppose induction hypothesis C.3 holds for all iterations < L. We have
Tawwn
(w((), 22,r) S (w Uz, + +
(11122
(r ( (x+
E E(xay)
(1 - logit, (F; (Fg (F;
12
1=1
Taowa + op)(ES + Ea)
< Ō(ou)
k
36

---

Published as a conference paper at ICLR 2023
Kernels outside Les M. For & M as we initialize w, by the pretrained encoder, have
Σ
ReLU ((w,, (p)), v1s) 0(08 E1 E
PE[P]
which is very small and there is nearly increase (wy, vt.)) Thus, when induction hypothesis C.3 holds for all iterations < t, for r & M, we have (w, (1) v1,) S ((o)).
Noise correlations.
For every [km]], for every (X',y") E 2 and every p" [P), we have that
1
E (xxa)= [x==x V., (p-)) 0 N22 ] [xx))=
(ReLU xp-) + o(1/Va)
x [1 logit, (Fr
Σ
logit, (F; (F;)))
and
-xx - =o(1/V
For every Va E V, for every r M. (0) for every p' E Pu,, when v y. we have
((xw)~2l((imm) (- V L(F: L(F: Ep
=ō( 112
ReLU ((wr;
0(1)
0.48
(1 (1-1ogee logit,, X ))) Wr, (1/vaa)
N₂
122
12
(O(1)
0.4s
Vr.i11 + (1 + Eg)
+ o(12/Va))
N₂
122
N2k
where (a) is because
logit, (Fi; x))
k-1 x at ttt= = O. When i # y. we have
E Exx,))=(((it4)) (-
Ww --
(F;X, x,y),Ep-)
1
n72 (- (O11)
0.4s 122
12(Es Es) + o(n2/Va) N2k(k - 1)
= =6 (k: 1).22
+
Vrai
k
Thus, we have
(E + Eg)
B(x,a22 [(-V,,
Vw, [(F;
Ep-1 ())
+ o(12/Va),
N₂h22
and
11 + E6)
(w (w)))))))) (w Ep)
+ ((mnn//a)) s ō(0o)-
N₂k2
Thus, when induction hypothesis C.3 holds for all iterations < t, we have
(w."),,) S (wo(), + Thoon 71 (/ + E6)
+ o(T'donn s ō(0o).
Nok
Similarly, following the similar step as in the proof Lemma F.6, we can also prove other claims about the noise correlations in the downstream tasks. We skip the similar steps here.
Combining all above results, we can prove the Lemma G.I.
G.2.3 TRAINING Loss AND PROOF THEOREM G.2 (A)
We set 7/2 to be Ok)) The reason why we set the step size to O(k) is in the first step, the weights of negative parts (< 0) and positive parts (> 0) is well separated. Thus, by setting suitable step length 7/2 = Okk), we can obtain small loss in the first update of (15). We will show that the training loss small in the following.
37

---

Published as a conference paper at ICLR 2023
After one-step training, at t 1, for (X E mdwwn,m we have
- - (X)
2
Σ Σ
(Uja (yrr) ( (x) + Es + +66 +
(ujrr - Uyy)) (Wrov Zx,(()) + Es + E6)
1=1
TEM (0)
1=1 rEM,
Σ
Σ
(Ugr (yrr) (vr.or .0 2 + Eg E6)
MeIHMMA)) PEM
(ujrr my.r) (Wisse (x)(X) Es E6)
Σ Σ
(Ujrr Ug,r) ( (Vras Zy,(X) Es E6)
M
rEM!!
mE + EE)
12 Σ Σ
((1) (k- - 1)
0.4s(k- - 1)
0.4s
O(1)
(ohss Zzi(x))
122
133
k3
k2
FEM
+ 1/2 Σ
Σ
0.4s
((1)
((1) (k:
0.4s(k - 1)
Whrn.. Zyi(x)) + namoooss + E6)
33
222
k22
FEM
1/2
((1)
0.48
Σ Σ
2
2
Vriia (X)
Σ
+ namolEss + E6) Prae Zux(x))
1.2
1=1
rEM
1=1 rEM c
1/2
((1)
0.4s 12
0.4 Σ
Σ
Σ
2
Vr.gd
+ nemo(Es + Es),
k
where (a) is because the third term is nearly zero. We could show the similar result for single-view data. At L = 1, for (X,y) y) E Zdown,s, we have
FX( (X)
= 1/2 (011)
0.4s
2 0.4
Σ
Σ
2 rEM v.
Σ
122
ryyd
1=1
rEM!
P Σ
2/2 ( + mEmo + E6).
(
Thus, at 1, we have
[28 2s
2s²
1
5²
[(X, (1gi,,,;;;;0 2
kz
Σ
ΣieWN/ -0.4..11
k2
1
Lie
00.4V.-V
+ (1
8 2/2 2
k
1+
Σ
EiElA/y
2 1 - 0( (
(24)
where the last inequality using the result that v... 2 polylog(s] and Vr.a & Ô(1) from Lemma F.1 at initialization, |M s O(log" k) from Lemma C.I. We could obtain the similar results for single-view data.
38

---

Published as a conference paper at ICLR 2023
Finally, if we set Toown
poly(k) 12
according to (22), is easy to verify that
Tdown
exa(
Tdown
Tdown
Z().w)
log
EjEly eF2(x))
T Tdown
T (X..))-aavv
logit, (F;X)]
poly(k)
This implies that the training loss is small and so we prove Theorem G.2 (a).
G.2.4 PROOF OF THEOREM G.2 (B)
In this subsection, we prove Theorem G.2 (b). For v) ~ Dm, due to our definition of data structure in Definition 1, with probability at least e -nllg" k), it satisfies that for every j E [k] \
FxX) 0.4
Σ T (exe)v(v))
(25)
and for (X, ~ Dx,
2
0.4 ()))
F2(X) - (x( ~ 0(1)
/v 9.3-1 y11
(26)
1=1
To prove Theorem G.2 (b), we need a lemma: Lemma G.4. For every (X, Zdown.
logit (F: so δ
((x,))~ Z logit,, (F; X)).
82
(The same also hold with probability Furthermore, if [) Zeown [1 - logit, (F;X)] S E is sufficiently small, we have for every
22llg k) for every (X,y) D on the left hand side.)
j E [k]] V..
- F2(X) S -O(1).
Proof of Lemma G.4. The proof of Lemma G.4 for multi-view data has been shown in (Allen-Zhu & Li, 2020, Claim C.1 Now prove this lemma also holds for single-view data.
For a data point (X,y) v) E Zoown, let us denote by H(X) be the set of all i E [k] \ {v) such that
Σ
2 0.8 100 log K'
Σ
up S +1+p p+
1
100 100log k:
[E(2) pEp PEPE,, (X)
(2
PEP yy (X)
Now suppose logit, (F; ((X), then using min (1, 3} 2 (1- I+0 ). we have
11
min {1, Σ F((X)-F(())] < 2(((X).
By (26) and our definition of H(X),, this implies that
min {1, Σ
(00)-(0.41 v.1- 0M0: < 4((X)
(ER(())
Now we define o = E(x,)) ( Z
[1 logit y (F;X),, then
min {I,
E (xx.))= Baown,
S $4
(ER(())
-E (.)) Zaown.
Σ min I -W
< 56
(EH(X)
39

---

Published as a conference paper at ICLR 2023
It equals
ΣΣ (ist)) JE[K] RE(A]
((enn)))))))))))) min { 0(1) (a.4v. v31r 40.
Note that for every i o j [k), the probability of choosing single- view sample (X, y) from 2 Bioonn
with y = j and E H() is at least O ) This implies
min e (0. 3.3 i- 0.1 - Ō k3
Σ [E({] kE(M]
Σ
53
Finally, using - 1+8 I min B}, for every (X,y) ~ Zdown, we have
1- 1-logit,(F::X)) min {
Σ
2(1) (0.40 2.3 v.1
0 h-2
k Σ min k
0(1)-(0.1... -, v,)))
52 1).
This implies that when E Xx w) Zaown.
[[1 logit, (F;:)
15. we have
0.4V/ - pv v.3-1
V W/1 S -Ō(1).
As we have proved in Section G.2.3 that
1
E( logit (FFttt poly(k)
We could set Townn
Ô
and then based on Lemma G.4, have
(x)) 2 max (x) Ō(1) 2 1 2(0lg" k)
Pr (X.y)ED
3Fy
H EXTENSIONS ON OTHER MRP METHODS
We have prove that Theorem C.4 holds in the above sections, which means that under the Teacher- Student Framework, the pretraining phase can capture all features. In this section, we extend our proof methods to other popular maak-reconstruction pretraining methods. Here we mainly consider
the masked autoencoder (MAE) structure He et al. (2021). For simplicity of analysis, we set the weights of the decoder as the copy of encoder weights and add a linear layer with by = c(0), i E [P] to finally obtain the recovered patches. The explicit framework is shown in Fig. 6. Denote the position encoding of patch as e, E R.,,, where at position the element equal to 1, otherwise the element equal O. Recall that e (E1211 62222 pppp). Under this framework, the loss function is
((;:X,c) = Σ
1p c(0)
Σ rE[km]
Wy ReLU ((w,, xxxx)
PE[P]
Σ
1/2p c(0)
Σ
W. ReLU ((wr)
2
PE[P]
rE(km]
and
X(H:X) = [L, c)
Σ
1&
Σ
we Re.ReeUU Re,,
PE(P)
rE rE(km]
Σ
WP 2p)) ||
+
2
pE[P]
rE[km]
Denote
Axp(X) = RRR.U xp)) + ReLU ((w,,
We have that
40

---

Published as a conference paper at ICLR 2023
Encoder
Decoder
2
34'2
bp
km
8p
km
Figure 6: Masked Autoencoder
Fact 2.2. Given the data point (X, 3) E for every Wr E [km]]
- -V u. L(X)= = Σ
Ar.p
Fp
wy ReLUU
PE[P]
To prove that under MAE framework. the pretraining can also capture all features, we have the same induction hypothesis as Induction Hypothesis C.3 but now the parameter assumption is a little different. Our new assumptions are shown as follows:
Assumption H.1 (Parameter Assumption: MAE framework). The parameters introduced in the paper need to satisfy the following conditions:
o is the threshold for the smoothed ReLU activation. We assume polylog(E]
q 4 and 0g-2
y controls feature noise. 7 < Ô (m))
s controls feature sparsity. s = @(polylog(k)).
N 2 a Vd w(k/o and P S <000 -911/2
polylog(k) < m E VT.
1) 2 - and S poly(e)
-(0)=
Now we have the following result on the feature learning process of MAE.
Theorem H.2 (Feature learning process of MAE). Suppose Assumption H.1 holds. By running the gradient descent step based on gradient Fact. 2.2 with learning rate v poly(k] after T poly(k) iterations, for sufficiently large k. >> 0, Induction Hypothesis C.3 holds for all iterations
0, 0 0,1,..,,11 T with high probability.
See its proof in Appendix H.2.5. Similarly, we also have the result about the performance on downstream classification tasks shown as follows.
Theorem H.3 (Performance on downstream classification tasks under MAE pretraining). For N₂ 2 k many samples, setting the learning rate 122 O(k) and m ①(k), after Taown poly(k) many iterations, with high probability, have
11
41

---

Published as a conference paper at ICLR 2023
(a) (training loss is small) for every (X, y) Zoown i.e.,
Lowwn (F) = ()) (Tooon (F; x,)] S poly(k)
(b) (lest performance good) for new data point (X;1) DD the test performance is
Pr (X.))D
Fx(X) 2 max (2(X) + +01)]
2 21- - -200l0g R).
e-
See its proof in Appendix H.2.6. Theorem H.2 guarantees that under MAE pretraining, the pretrained convolution kernels can capture all discriminative features in the data and each convolution kernel only grab at most one discriminative feature. Such a result accords with the result of MRP in Theorem 1 of the manuscript. Please refer more detailed discussion and analysis of Theorem in manuscript. We also note that the assumptions under MAE framework are more strict than the assumptions of Stuuent framework. In the assumptions of MAE, we need q 2 4, which means we need to let the low-magnitude feature noises to be compressed much much smaller in order that we can separate the true feature from feature noises. Then Theorem H.3 shows that as we have captured all features in the MAE pretraining phase, we can also obtain very high accuracy with high probability in the downstream classification tasks. Therefore, compared with supervised learning, MAE also shows better performance on classification downstream task. This result shows the generality of our analysis framework.
To prove Theorem H.2 and Theorem H.3, mainly follow the similar framework used to prove Theorems and Theorem 2 in the manuscript. To begin with, we first prove some auxiliary theories based which can easily prove the desired results.
H.1 SOME RESULTS FROM INDUCTION HYPOTHESIS C.3 UNDER MAE
We first introduce some claims about the terms in the gradients. Claim H.4. Suppose Assumption H.1 and Induction Hypothesis C.3 holds at iterations I. Then for
every r E EM we have
(0)
if Po,,
(x) = EV + tex ((w,,
. if P(X) (X),
Axp(X) Ō(o)).
ifp E [P] P(X).
Axp(X) Ö((o0rk)))
We also denote
1 Σ
AX(X) Fp
wy ReLU ( ((Wp)
B
['((km]
Claim H.5. Suppose Assumption H.l and Induction Hypothesis C.3 holds at iterations t.
When p P PX..(X), have
(Ap(X), v,,) = zpHle,,
Σ
(wp, www.
Σ
Ö(ao)
r'MM
= =2ITu,,eV(X)
Σ
(wp, ReL + Ō -
0
M'M,
(0)
42

---

Published as a conference paper at ICLR 2023
When p (X) but Pey.r (X) (X) UA Vast have
(Ap(X), Ö 9- 9) +
Σ PEM
(wi (0),)))))000)) +
E
MEM (0)
When p [P] P(X), we have
(Ap(X), v..) - 7 (xk)))
Σ (we,
(()oo(()))))))
T'MM
Now we have some claims for the gradients. The proof just based on the result from Claim H.4 and Claim H.5.
Claim H.6. Suppose Assumption H.1 and Induction Hypothesis C.3 holds at iterations t. Then for every Via V. for every r E Mi for every (X, v) Z, we have
(a)
VV Ww ((X).
Σ Ang [plee,ev((x)-
(wr, wew spl))
(x)
N'M
+ + + 1/11 20t
())k)29). ((()))**))))))))))) P
(b) for 1/ # vi,b
-(V L(X), vz,1)
+ E
A + Ō( 4)) 1 70(08) 1-13) (7k))))))))))))))
(EPo,,(X)
Σ
Ō(og)
Σ
(wp, (wp,, Ugr) Ho ev(x) Re
PEP. DEPo, (x)
NEM! 31
Intuitions on Claim H.6. From Claim H.6, we can find that the positive-correlatoon gradient I()), 25,1) has non-small term that drive the correlation between Wr and U4,1 when r E M!l to increase during the training courses. How the correlation increase will be shown in Claim H.7 in the following. On the other hand, the negative correlations will keep small as the negative- correlation gradients - .V.,, L(X), (x,,),r) ugrr) L(X)) intuitions under Teacher-Studed Framework and thus could also prove that MAE pretraining could also capture all features.
always have small terms. These intuitions are same as the
Now we have the following claim shows about at which iteration Al will be greater than 0- Claim H.7. Suppose Assumption C.2 holds and induction hypothesis C.3 holds iteration t. For every U suppose (b) < o. Then we have
A
((+1)
+ θ
1 ( ReLU v,)r)
Proof of Claim H.7. Recall that 2o max,s [kmm] (1of)) +.,))++ We choose any [km]] that makes (w) v.)) 2 (l(o)). Now we show the updates. We know that (w((+1), vis) (w vi.)) + mlE 11- L(X), v.1i
43

---

Published as a conference paper at ICLR 2023
Using Claim H.6 and following the similar method in the proof of Claim E.4, have
(V w. L(X),
Σ
Arp zptineeiii - (wp,, Xx
1
ReLU xp))
PEPuz, (2)
r'EM
= ReRUR vtail)
1 (1/0)
Σ
(eLU(( (u)) va,)
r'MM
Σ
(1+ 2)
PEP.L, (X)
As the term (1/0) E Ee
ReLU (wo,, v()) small at the intial stage compared with
the constant 1, we have
A 1,1
(++1)
(1) + θ 7 ReLU((Wrr v.))).
Using Claim E.5, and ((0) S AA < ((o)). we have the following result:
Claim H.8. Suppose Assumption H.1 holds and Induction Hypothesis C.3 holds for every iteration.
We have that when 2 To, satisfies A θ 1 Define To = Ô (og-1)) )
(polylog(k) )
H.2 PROOF OF THEOREM H.2
H.2.1 DIAGONAL CORRELATIONS
Lemma H.9. Suppose Assumption H.I holds and Induction Hypothesis C.3 holds for iterations
< L. We huve
Vor E EV: A S min
θ
Ō(1)
|M (0)
Proof. Suppose now at some iteration t To- In this stage, A. 1/polylog(k). As
k non To = θ
1)
and 17 I poly(kj+ we have
- ,V, I(X),
Σ
Arp zpToL,Ev(X)
Σ
(Wr, Vi, ReLU (e ap))
PEP (X)
r'EM
Tw 1- (1/0)
Σ
(we, (ir))
Σ 227 (EP
r'MM
Then we have
[[oft++ [x,,) S Kwwl vn1il + Ô (+) [
Taking the maximum on both side and as we at t > To. we have
mx))+ (1 (1+0 max (w(tt)) +11)+ s max (e (wo())))a))++ reM!!
(1))
rEM! (0)
When t T To + (()), we have
1 s Ō(1).
44

---

Published as a conference paper at ICLR 2023
Besides, we also need
1 1- -1/0) Σ
(w,), 2 0,
r'MM
which means
M 1
This condition shows that when A,
the increase on the positive correlations tends to
IM
zero and the training process becomes to converge.
Lemma H.10. Suppose Assumption H.I holds and Induction Hypothesis C.3 holds for all iterations t. We have
VULa E V. : (1, .0.)) -O(oo).
Proof. We start with any iteration t that is (w) 1 v(,) & -M(() to see how negative the next iteration will be. Without loss generality, we consider the case when (wh") vu.)) I -(((0r) holds
for every t' Then based on Claim H.6 and when we assum (wf²) v1.)) S -(((o)). Are we have
(t')
(w) (w) viri) 2 (wf)), v,,) - -0(0))))00 -(000 11 - 0tt (7,h)) (7)0)))))>)))7)))) P.
When & S To. we have
(wf(+2),, vaa) 2 (w/()) v(.)) -Ō(0)) 000 ) P
2 - 776610(08) 0 1/- + 0((0)
(Tk))00) ((())=+)()))))))) P)
29+1
-((o))-
When t E [To, 2], we have
(wf(+)) vn,1) 2 (wfTT) v.,1) 7 +00 20+
P)
2 Ö(oo) n((T - -00 1 (7 (77)22)))))))))))))))))))))))))) P)
2 (
H.2.2 OFF-DIAGONAL CORRELATIONS
Lemma H.11. Suppose Assumption H.l holds and Induction Hypothesis C.3 holds for all iterations
< L. Then
Vou E V, Vr E
(0) for Usy # Auzi (w , u,,r)) S Ō(a)).
Proof. Stage I. We first consider the stage when S To. For every r E M! using Claim H.6, we
have
E E(x,))=2 (V W., I(X), "3rr
< E(x,)
Σ
Arp
(7+ + + + + Ō( (000000)))0000000 (()))) -P
pEPota(X) (X)
x ((xxa)=2
(pTo, - 1
Σ
"err) ReLU xxp)))
pEP (X)
(0)
<6 6
ReLU((W, vu)) Ō Ō
%
k
45

---

Published as a conference paper at ICLR 2023
From Claim H.7, we have that
To
ReLU
((0)) oa)) -177) -A v polylog(k)
t
Thus, when To.
Kwff, Uzoو $ ..,/) 0 ) ToO !
I Ō(o)).
Stage II. When & [To. T), we have
7(( (To) (1of) 0,,,)1 $ (o ,,,3} Ô
0("17
(ReLU((w, v.)) + 0(0g + (
b
s Oooo).
H.2.3 LOTTERY WINNING: KERNELS INSIDE M!!
Lemma H.12. Suppose Assumption H1. holds and Induction Hypothesis C.3 holds for all iterations L. Then
VUsa E V,Vr & M (w.f uz S Ō(oo).
Proof. When r E M (1y, # v.1), we have prove that (w ,(d) s Ō(o)) in Lemma H.1l. So we only prove the case when r & Uee(n)eeea)
We assume that there exists wy & MM such that induction hypothesis C.3 (a)-(c) holds for every (X,y) Z. We want to see if the sequence (w vi,s) will increase more quickly (t) va.).
than max rEM!! (wy
Stage I. We first consider when $ To. In this stage, A0 S o. We define two sequences. First, we
take wp-- = argmax, TEM (w, (0) v.,)) and define == (w u,,)) ( 1 We also define
Yt max (w v1,1) (($) 1/(8-1)
6¹ 5o.. From Claim H.7, when < To. we have that
(m (e-1)
vi.) = (m v(.) + θ
81) ReLU v(.))
2 (w vc.)) +
(T)
(
9oa-1
Let S = (14C/log(()) 0)
9-2 log(k)
C>> 1. We have
(1+1) (w
v1.) = (w v4.) + +
97
ReLU v..))
(t) S (w vc.)) +
sT)
goo-1 (1(w)) +.s.
Then following the same process as the proof of Lemma F.5, we have
(w v. < Ō(aa).
The proof of Stage II is also similar to Lemma F.5.
46

---

Published as a conference paper at ICLR 2023
H.2.4 NOISE CORRELATION
As our noise correlation result similar Lemma F.6, we don't 't repeat it here but just prove it holds under MAE framework and under our new parameter assumptions.
Proof of Lemma E.6 under MAE framework. For every E [km]] for every (X*, E Z and every p" [P). we have that
V m. L(X) = ΣAA Arp
(Ep:
1
Σ (w Sp Reee)
PE(P]
r'E[km]
When X + X", we have (stp. Ep-) S Ö(pp) o(1/vd); and when X X but p + p", we have 10pps Spr < Ō(Ø o(1/v/ Therefore, have E(x,))
= Exxwee [x=x vv, (x
(0) Now we begin to prove (a). For every Vi, E V, for every r E M for every p" E Pot,( using the induction hypothesis C.3, when & E [0, Tol. we have that for the first term,
B(x,0) Tx-x- (-V Vu, I(X),xx))
. B(x Arp (0))
Σ
(wpr ((r) #o (32) = o (cL!U(A!!
r'E[km]
For the second term,
E(x,)m (- ((), (vm, = ( + o( ReLU
Thus, have
(pp) < (1((), (p-) + + ( o( ReL +o
" Vd
+ o(10O) Rel.U(A))))
Now the results from Lemma H.9, when t - To.
(wft), ) I (w(t-1), Epr) + o(10) ReLU) +o
7
Vd.
Ta
YTo
s (w/ (p:) + o(11))
ReLU
Vd.
I ō(ou)-
So when N 2 a
k o and vd 2 w(k/o8-1) ) we have (w (1) Ep-) S Ō(0o). Therefore, for
I E [To, Tj. we have
( n(t (n(t-
n(t nltt- n(b) To)
(w(") Ep-) S (T) (T)) Exr) +
< <o(00)
N
Vd
when Vd 2 (k). Following the similar process, we could also prove (b)-(e).
H.2.5 PROOF THEOREM H.2
Theorem H.2 can be easily obtained following the similar steps in the proof of Theorem C.4 when we have Lemma H. 1.10--emmma 1.12.
47

---

Published as a conference paper at ICLR 2023
H.2.6 PROOF OF THEOREM H.3
Theorem H.3 can be easily obtained following the same steps in the proof of Theorem G.2 in Section G.
H.3 DISCUSSION ON BEIT METHODS
We have proved that the pretraining phase can capture all features both under Teacher-Student framework and MAE framework. Now we have discussion BEiT framework (Bao et al., 2021). For BEiT, if we regard the pretrained encoder of BEiT as a fixed teacher and stuck an additional layer to map the patch token feature of BEiT encoder discrete pseudo label, then this setting becomes very similar to our setting. The only different is the BEÎT encoder (teacher) is fixed, while our teacher encoder is learned online (updated along with the weights of the student). Since there are lot of similarities between these two frameworks, our proof methods can naturally extend to BEiT with the suitable choices of additional layers.
48


Reviews:
[{"review_id": "tBgMeh-ujU4", "reviewer": "Reviewer_TnqJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is overall a quite interesting paper. Based on an abstract teacher-student framework with simple network architecture, the authors explore how a masked reconstruction pre-training architecture performs feature learning and becomes beneficial for downstream tasks by modeling \"semantics\" as attribute vectors associated with different annotation labels. With the above analysis, the authors further conduct a MRP pre-training with ResNet and demonstrate more superior performance compared with supervised pre-training. \n\n", "summary_of_the_review": "This is overall an interesting paper solid theoretical analysis, which will provide good insights for future researches and algorithm development.", "strength_and_weaknesses": "- Strength:\n  - The authors provide a very detailed theoretical analysis based on the proposed teacher-student MRP framework.\n  - The idea of modeling \"semantics\" as several attribute vectors associated with classes is interesting.\n  - After theoretical analysis, the authors further conduct implementations to support their analysis.\n\n- Weakness:\n  - In the MRP architecture proposed in Sec. 3.2, are there any requirements of the teacher model parameters, like they should be the EMA of the parameters of the student model?\n  - The analysis heavily bases on the assumption that the \"semantics\" of the downstream dataset should be a subset of the pre-training dataset. Does it suggest that the downstream dataset should have similar distribution with the pre-training one, which is actually a very strong and unrealistic assumption? If not, what is the difference?\n  - The authors claim that the MRP pre-trained models would contain all the semantics of the downstream tasks, each at least corresponding to one kernel. Does it suggest to do transfer learning, if I can find the specific wining ticket of a given downstream task, pruning can actually replace fully fine-tuning?\n  - I wonder whether the MRP pre-trained models would be worse when the pre-training dataset does not contain all the semantics in the downstream datasets compared with supervised pre-training, since the latter replies on partial semantics matching while MRP might response to more semantics according to Fig. 3.\n- Could you further explain what the role of masking \\epsilon is, since it seems not to appear in your analysis in Sec. 4?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ITE90WNo9q", "reviewer": "Reviewer_1jPb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 introduces a theoretical analysis to understand why mask reconstruction pre-training (MRP) works well in downstream tasks. It's found MRP can capture all discriminative semantics of each class in the pre-training dataset and thus utilize them to help downstream tasks. It provides solid proof, straightforward visualization and experiment result.", "summary_of_the_review": "Overall, this paper targets an intriguing problem and provides solid proof. I'd lean to accept it.", "strength_and_weaknesses": "Strengths:\n1. The problem of why MRP works so well and is much better than supervised learning is quite interesting and important for the community. This paper is a pioneer in studying how semantic features are learned under the above problem.\n2. The theoretical analysis covers both multi-view data and single-view data. It also covers both MAE-like methods, Teacher-Student MRP methods, and supervised learning methods. It also discusses different downstream tasks. \n\nWeaknesses:\n1. In this paper, it assumes the encoder in the student network is just a two-layer convolution + Smoothed ReLU network. I understand that this setting is easier to analyze. But in real-world applications, people usually use deeper models. And we know that some conclusions found in a simple model don't necessarily generalize to deeper models. So I wonder if it's possible to generalize the analysis to deeper models?\n2. I am a bit confused about the definition of whether one semantic is captured by the kernel. In 4.1, If I understand correctly, when the correlation score is increased to `1/polylog(k)`, it means matched. Why would the threshold be set as that?\n3. The experiments mainly cover visualization and accuracy. But those two proxies cannot indicate whether all discriminative semantics are captured in MAE/MRP. Is there any way we can quantitatively measure how many semantics in each class are captured by kernels?\n4. As you mentioned in section 4.2, Transformer is not discussed because of its correlated manipulations and highly nonlinear attention. Is that possible that we remove the nonlinear part and make it analyzable?\n5. Some typos such as `The pretraining dataset Z has` in Assumption1. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Go2IL8Zz7g7", "reviewer": "Reviewer_GkZ3", "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 provides a theoretical analysis that explains the benefit of MRP in SSL. Utilizing the multi-view data distribution and certain assumptions about the model architecture, the paper shows that the encoder trained with MRP can capture *all* the discriminative semantics of each semantic class in the pretraining dataset. This gives an advantage to the SSL+SL compared the SL only model since in SL training the model only captures *some* semantics due to lottery ticket hypothesis.", "summary_of_the_review": "Recent works have shown practically that supervised fine-tuning of the encoder learned via MRP remarkably surpasses the SL training from scratch but I am not aware of any theoretical work that supports the benefit of MRP. The paper provides new theoretical justification for the success of MRP in practice. Overall, the theoretical contributions of the paper are significant and novel.", "strength_and_weaknesses": "Strength:\n\n1) The paper provides a strong theoretical analysis, supporting the benefit of MRP for SSL.\n\n2) It is really hard to pick a minimal set of assumptions about the data and model that are just sufficient to prove the advantage of MRP in SSL. I like how the paper mathematically defines multi/sing-view distributions and picks a simple network architecture and manages to prove the benefit of MRP over SL.\n\n\nWeaknesses:\n\n1) There are several limiting assumptions in the multi-view data distribution and network architectures that do not apply in practice. However, I understand that these restrictions are required for a sound theoretical analysis. \n\n2) The theoretical analysis in the paper does not result in a new practical approach, instead it supports the success of the existing methods in a limited setting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0luB9RKGXm", "reviewer": "Reviewer_J85J", "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": "The authors study the mask-reconstruction pretraining (MRP) approach and its ability to generalize well for downstream tasks. They show that under certain dataset and task assumptions, MRP can perform well for downstream classification tasks whereas supervised learning cannot. ", "summary_of_the_review": "The theory is both correct, novel, and matches the empirical results of MRP, which is an important problem to study. While there are important results, the dataset assumptions cast some doubt on how generally applicable the results are. ", "strength_and_weaknesses": "Strengths\n- The problem is clearly an important one to study, and hasn't been adequately addressed by the existing literature. \n- The use of the multi-view data assumption from  (Allen-Zhu & Li, 2020) is clever. \n- The empirical results match the theoretical findings, from multi-view data assumption to test performance on downstream tasks. \n\nWeaknesses\n- The assumption that pre-training and downstream datasets follow the same distribution is in some ways limited. While the authors discuss how this framework is useful, it would be nice to see more analysis of \"transfer learning\", since this is much of the appeal of pre-training approaches. \n- Dataset assumptions are fairly strict, though the authors reason about how these assumptions are justified. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster