Predicting What You Already Know Helps: Provable Self-Supervised Learning
Authors: Jason D. Lee
Qi Lei
Nikunj Saunshi
Jiacheng Zhuo
Venue: NeurIPS 2021 Poster (2021)
Keywords: statistical learning theory
approximate conditional independence
reconstruction-based self-supervised learning

Abstract: Self-supervised representation learning solves auxiliary prediction tasks (known as pretext tasks), that do not require labeled data, to learn semantic representations. These pretext tasks are created solely using the input features, such as predicting a missing image patch, recovering the color channels of an image from context, or predicting missing words, yet predicting this \textit{known} information helps in learning representations effective for downstream prediction tasks. This paper posits a mechanism based on approximate conditional independence to formalize how solving certain pretext tasks can learn representations that provably decrease the sample complexity of downstream supervised tasks. Formally, we quantify how the approximate independence between the components of the pretext task (conditional on the label and latent variables) allows us to learn representations that can solve the downstream task with drastically reduced sample complexity by just training a linear layer on top of the learned representation. 

Predicting What You Already Know Helps: Provable Self-Supervised Learning
Jason D. Leel,
Qi Lei',
Nikunj Saunshi',
Jiacheng Zhuo²
University of Texas at Austin (jasonleee, qilei0, nsaunshi ( princeton. edu, jzhuo@utexas.edi
Princeton University
Abstract
Self-supervised representation learning solves auxiliary prediction tasks (known as pretext tasks) without requiring labeled data to learn useful semantic represen- tations. These pretext tasks created solely using the input features, such predicting a missing image patch, recovering the color channels of an image from context, or predicting missing words in text; yet predicting this known information helps in learning representations effective for downstream prediction tasks.
We posit a mechanism exploiting the statistical connections between certain reconstruction-basee pretext tasks that guarantee to learn a good representation. Formally, we quantify how the approximate independence between the components of the pretext task (conditional on the label and latent variables) allows us to learn representations that can solve the downstream task by just training a linear layer on top of the learned representation. We prove the linear layer yields small approxima- tion error even for complex ground truth function class and will drastically reduce labeled sample complexity.
Introduction
Self-supervised learning revitalizes machine learning models in computer vision, NLP, and control problems (see reference therein [36, 38, 15, 63, 35]). Training a model with auxiliary tasks based only input features reduces the extensive costs of data collection and semantic annotations for downstream tasks. It is also known to improve the adversarial robustness of models [29, 11, 12). Self-supervised learning creates pseudo labels solely based on input features, and solves auxiliary prediction tasks (or pretext tasks) in a supervised manner. However, the underlying principles of self-supervised learning mysterious since it is a-priori unclear why predicting what we already know should help. We thus raise the following question:
What conceptual connection between pretext and downstream tasks ensures good representations? What is good way to quantify this?
As thought experiment, consider a simple downstream task of classifying desert, forest, and sea images. A meaningful pretext task is to predict the background color of images (known as image colorization [66]). Denote X,, X2, to be the input image, color channel, and the downstream label respectively. Given knowledge the label Y, one can possibly predict the background X₂ without knowing much about Xi. In other words, X2 is approximately independent of X, conditional on the label Y. Consider another task of inpainting [48] the front of building (X₂) from the rest (X,). While knowing the label "building"
(Y) is not sufficient for successful inpainting, adding additional latent variables Z such as architectural style, location, window positions, etc. will ensure that variation in X2 given Y, Z is small. We can mathematically interpret this as X being approximate conditionally independent of X₂ given Y, Z.
The main insight that exploit in this work is that with approximate conditional independence (as in the above examples), a method that predicts X, from X; will inadvertently implicitly encode and
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

learn to predict Y (and Z) from X1 as an intermediate step, and then predict X2 from Y Building upon this insight, we make the following contributions.
Contributions. The goal of this paper, as in statistical learning theory, is to investigate the statistical connections between the random variables of input features (in this paper (X,XX)) and downstream labels Y, and show how specific connections can guarantee a successful learning procedure. For self-supervised learning (SSL). success is measured using the following 2 notions, 1) expressivity. i.e. does the learned representation from SSL have the ability express the ground truth prediction function for labels Y. and 2) sample complexity, i.e. can it do so with way fewer labeled samples than what would be required without SSL.
In this work, we show such guarantees for a class of reconstruction--asse SSL methods under a statistical assumption of approximate conditional independence (ACI). In particular we show that under such an assumption, the learned representation from SSL will end up having the following properties, 1) it can express the ground truth label a linear function, thus guaranteeing expressivity, and 2) will also end up being low-rank (or low-dimensional), thus guaranteeing smaller labeled sample complexity. Note that such expressive and sample efficient (summarized good) representation is often not a a-priori available. For instance, the original input features themselves may not be able to express the ground truth function linearly, while kernel methods with a fixed kernel, while expressive, may not be sample efficient for many problems of interest. The strategy in modern machine learning is to find such a good representation as the output of complicated neural network. The benefit of SSL, as we formally show here, is that the complicated but good representation function can be learned using just unlabeled data, so that labeled data is just needed learn linear function.
The reconstruution--ban -bssed SSL method (differentiated from other SSL methods in Section 1.1) we consider is strongly motivated by empirical works [66, 48, 15, 25]. but is a simplification that captures the essence of the problem and is amenable to a precise theoretical amalysis. We consider a two-staged pipeline, where we first learn a representation function & (e.g. output of neural network) from input X1 and pretext target X2 using unlabeled data by minimizing [xxx In the second stage of downstream task, we learn linear layer on top of representation i using labeled samples (X1, Y), thus restricting to learning from a significantly smaller hypothesis class of He = {f : X1 + YIf is linear in Φ). The key non-trivial question of expressivity is now whether the ground truth predictor f = [E{ can be approximated well by this class H., and the question of sample complexity reduces to the understanding the sample complexity of learning Hyg Under appropriate statistical connections between input data X1. X2 and target Y. we prove both the desired properties, expressivity and low sample complexity, for the aforementioned SSL method.
[|] X2 - (x11))
Our statistical assumption based on approximate conditional independence (ACI) helps demon- strate how solving pretext tasks created from known information can learn useful representations. Specifically, we show that once the complicated representation function & is learned using an abun- dance of unlabeled data in the SSL stage, not only is & expressive enough, but it will also require only Ō(k) labeled samples to solve a k-way supervised learning task under exact conditional inde- pendence (CI). In contrast, solving the downstream task without any pretraining will require lot of labeled data to learn the representation function from scratch. Since the strong exact conditional independence assumption will likely not be satisfied in practice, our main contribution is to derive similar risk bounds when only approximate CI (ACI) is satisfied. We quantify the notion of ACI using the norm of certain partial covariance matrix (Definition 4. and our risk bound scales linearly with it. We verify this and other aspects of our main Theorem 4.2 using simulations and also find that pretext task helps when CI is approximately enforced in text domain. We further demonstrate on a real-world image dataset that a pretext based linear model performs at least as well as many baselines.
1.1 Related work
Self-supervised learning (SSL) methods in practice: There has been flurry of self-supervised methods lately. One class of methods reconstruct images from corrupted or incomplete versions of it, like denoising auto-encoders [61], image inpainting [48], and split-brain autoencoder [67]. Pretext
'This is formally demonstrated in the proof sketch of Lemma 3.1.
We note that since the representation & is the result of the SSL method and not something we have access to priory, we cannot make any direct assumptions on it.
2

---

tasks are also created using visual common sense, including predicting rotation angle [22], relative patch position [16], recovering color channels [66], solving jigsaw puzzle games [45]. and discrimi- nating images created from distortion [17]. We refer to the above procedures as reconstruction-basee SSL. Another popular paradigm contrastive learning [13, 14). The idea to learn representations that bring similar data points closer while pushing randomly selected points further away [63, 39, 5] or to maximize contrastive-based mutual information lower bound between different views [30, 46, 54]. A popular approach for text domain is based on language modeling where models like BERT and GPT create auxiliary tasks for next word predictions [15, 49]. The natural ordering or topology of data is also exploited in video- based [64, 43, 191, graph- bashh [65, 33] or sap-based [68] SSL. For instance, the pretext task is to determine the correct temporal order for video frames as in [43].
Theory for SSL: While we theoretically study reconstruction-bee based SSL, prior work has different flavors of theoretical results for different kinds of SSL methods. Most relevant are the guarantees for representation learning using SSL methods on downstream tasks that just learn a linear classifier on top of the learned representations. [5] shows guarantees for representations from contrastive learning objective: (. (x),).x))xx; [log(1 + e=*((x)" ((Xx)) (xxX))xxx)) Under class condi- tional independence assumption, i.e. Xi 1 X2 Y. they show that representation z that does well on contrastive objective, i.e. ( S will have (ee) linear classification loss on the average binary task involving pairs of classes (y1, 82). However, their analysis cannot handle the general case of approximate conditional independence. Recently, Tosh et al. [56] show that contrastive learning representations can linearly recover continuous functions of the underlying topic posterior under a topic modeling assumption for text. While their assumption bears similarity to ours, the assumption of independent sampling of words is strong and does not generalizable to other domains like images. Most relevant is a concurrent work [57] that shows guarantees for contrastive learning objective that
looks like I.g0 (v), n) = Xxxxxx)..xg log(1 + exx())) m(X2)) + log(1 + (x())) xx(x)))(xx)))]] with a multi-view redundancy assumptions that is very similar to our ACI assumption. We take a closer look at their assumption in Section F.2. All the above objectives are different from the simple icconstruction--asee objective we consider: L( Xx)) [||
(Xx, [2]. Saunshi al. [51] show guarantees for representations learned using language modeling on sentence classification tasks. Some more recent work [58, 44, 55, 62] provide theoretical understanding on SSL respectively based on causality, mutual information, gradient-descen representations, without explicit risk bounds for downstream tasks. There is mutual information maximization view of contrastive learning, but [59] points out issues with it. Previous attempts to explain negative sampling [42] based methods use the theory of noise contrastive estimation [27, 40] to show asymptotic guarantees, without explicit connections to downstream tasks. CI is also used in sufficient dimension reduction [21, 20). while CI and redundancy assumptions on multiple views [37, 2] are used to analyze a cnoorical-oorrllatoon based dimension reduction algorithm and also for self-supervised learning algorithms like co-training [10]. Finally, [1, 60] provide a theoretical analysis for denoising auto-encoder.
dynamies, and alignment/uniformity of
1.2 Overview of results:
Section 2 introduces notation, setup, and the self-supervised learning procedure considered in this work. In Section we analyze downstream sample complexity under exact CI and unlimited labeled data to highlight the key ideas. Section 4 presents our main result with relaxed conditions: under ACI with latent variables, and assuming finite samples in both pretext and downstream tasks, for various function classes, and both regression and classification tasks. Experiments verifying our theoretical findings are in Section 6. Proofs of most results are the Appendix.
2 Preliminary
2.1 Notation
We use lower case symbols (z) to denote scalar quantities, bold lower case symbols (x)) for vector values, capital letters (X) for random variables, and capital and bold letters X for matrices. Px denotes the probability law of random variable X, and the space of square-integrable functions with probability P is denoted by (.P. We use standard O notation to hide universal factors and Ô to hide log factors. || stands for mn-norm for vectors Frobenius norm for matrices.
3

---

Linear conditional expectation. [ denotes the prediction of Y with linear regression:
B a] == W'x + b", where W bb := arg min B||lY - WX b1 6
In other words, | [.x] denotes the best linear predictor of Y given X. We also note that E[y[ = -
arg min, [B[]| - [(x]] is the best predictor of Y given X.
(Partial) covariance matrix. For random variables X, Y. we denote Σ Xx to be covariance matrix of X and Y. For simplicity in most cases, we assume E[X] = 0 and E[ O; thus we do not distinguish E[XY] and Exy. The partial covariance matrix between X and Y given Z is:
ΣxyΙz cx - EX[X/Z) - E 2 Σxy - Σxz x 7z Σx Ezy,
(1)
which captures the correlation between X and Y setting aside the effect of Z.
sub-gaussian random vectors. X E Fd is 2--sub-gaussine if for every fixed unit vector v e R the variable
X is
i... BBe T (X-E[x]]] < 02 (Vs R).
2.2
Setup and methodology
We denote by X1 the input variable, X2 the target random variable for the pretext task, and Y the label for the downstream task, with X, E X1 C RR, X2 E X22 C Rdd and Y E y c RR If y is finite with | = k, we assume Y C. R$ is the one-hot encoding of the labels. Xxy denotes the joint distribution over X1 X X2 x V. Px,y,
Pxx "x,y,Px, denote the corresponding marginal distributions. Our proposed self-supervised learning aims to fulfill the following two steps:
Step I (pretext task): Learn a representation (i(x)) close to 1= == arg min E||X2 g(x1)11? where Ht can vary for different settings that we will specify and discuss later.
Step 2 (downstream task): Perform linear regression on Y with ( i.. f(x)) (W-) TTb())))) where W + arg minw Ex,, |||Y - W T ((X)))1)) Namely we learn f(-) E IY [+)).
We study this simplified version in the main text, where in practice, the SSL procedure may utilize an encoder-decoder structure, while the downstream task uses both X1 and X2 to predict Y. We incorporate these extensions in Appendix C.3 and G.
With finite samples, performance a learned representation to on the downstream task depends on the following quantities that capture expressivity and sample complexity respectively:
Approximation error indicates whether Y lineurly separable by the learned representation v thus measuring expressivity. We measure this by comparing W ah( X1) to the optimal predictor f := [ = 21). Denote (x)) = minw [x]]]=(XX,)
(X((,)) {))l This gives a measure of how well & can linearly predict Y when given infinite samples for the task.
Estimation error measure sample complexity of on the downstream task and assume access to n2 i.i.d. samples (ar (1)
..... (ar (m2)) (m2)) drawn from Px,-- We express the n2 sam- ples collectively as X-down E Raaxdd Y E Ru and overload notation to say ei (X((on)))) = ((x (1)
"e(",y(() y."))....
(((aa(")ll( (=x ) Iv(a (ma) E Reax We perform linear regression on the learned represen- tation z and measure excess risk, that incorporates both approximation and estimation errors.
+ (XX) ER W)) 1 B))r(())))) WT (Xx))
W arg arg min W
2nz
3 Guaranteed recovery with conditional independence
In this section, we focus on the case where the input X1 and pretext target X2 are conditionally independent (CI) given the downstream label Y. While this is a strong assumption that is rarely satisfied in practice, it helps us understand the role of CI with clean results and builds up to our main results with ACI with latent variables in Section
As a warm-up, we show how CI helps when (X1, X2, Y) are jointly Gaussian to give us a flavor for the results to follow in Appendix B. We then analyze it for general random variables under two settings:
(a) when the function class used for e is universal, (b) when v is restricted to be a linear function of given features. For now we assume access to a large amount of unlabeled data so as to learn the optimal 4* perfectly and this will be relaxed later in Section 4. The general recipe for the results is as follows:

---

1. Find a closed-form expression for the optimal solution 35* for the pretext task. Use conditional independence show that optimal f is linear in u², i.c., Eaps (x)") is small. 3. Exploit the low rank structure of a/" to show small estimation error downstream tasks.
Data assumption. Suppose Y (X1) N. where f [1 and E[N] 0. We assume N is oussubgausiian For simplicity, we assume non-degeneracy: Xx,x,, Eyy are full rank.
Assumption 3.1.
Let X2 E 1R X2 E d be random variables from some unknown distribution. Let label Y E y be discrete random variable with k = d2- We assume conditional independence: X1_X2
Here Y can be interpreted as the multi-class labels where ks the number of classes. For regression problems, one can think about Y as the discretized values of continuous labels. We do not specify the dimension for Y since Y could be arbitrarily encoded but the results only depend on k and the variance of Y (conditional on the input X1).
3.1 Universal function class.
Suppose we learn the optimal 1 among all measurable functions The optimal function 30* in this case is naturally given by conditional expectation: 35 (x1) = [[X2|XX = æ1). We show that CI implies that v² is good for downstream tasks, which is not apriori clear.
Lemma 3.1 (Approximation error). If random variables X1, X2, Y satisfy Assumption 1. and A E R2 with yy = E[Xg|Y = y) has rank k = | Then I = W i.e, Caps (v² =
This tells that although f could be nonlinear in 11, it is guaranteed to be linear in (x1).
Proof Sketch of Lemma 3.1. Lemma is proved by law of total expectation:
4つ = E[x] -E[E[[2 Lx, x] = [[][]/XX]]]]]
(uses CI)
Σ P(Y x = vl =: f(X,) A,
where f211y - P(Y y|X = m)). and A E R satisfies Ay:: E[X2|Y = w] One could see that through predicting X2, due to the CI assumption, vi" has implicitly encoded the information of Y|X, Finally due to the fact that matrix A is full rank, we get that f is linear in sh* as well. D
We see that besides CI, another important property is E[X, Y being rank k. This means X2 is correlated with every instance of Y, and thus captures information of every prediction class. This is naturally necessary assumption for X2 to be reasonable pretext task for predicting Y. Note that designed to predict X2.
this assumption does not trivialize the problem and that even though can still be a better representation than X₂ for downstream tasks. Note that Y does not have to be linear in X2 but is proven to be linear in v since & learns to ignore some information X₂ that is irrelevant to Y. We provide this simple example for better understanding:
Example 3.1. Let Y E {-1,1} be binary labels, and X1, be 2 2-mixture Gaussian random
variables with X1 ~ ~N(Y M1 1), X2 ~ NY pz 1). In this example, X, LX, Y. Although |E
and E X1] are not linear, E [ is linear: v1(21) = P(Y 1| X| = 2 [ P(Y 1|
21) and (x11 = P(Y 1|x, =1) P(Y = 1 x1 μور (xx1)//ll 1|
Given that 26* is good for downstream, we now care about the sample complexity. We will need to assume that the representation has some nice concentration properties. We make an assumption about the whitened data zi (X,) to ignore scaling factors.
Assumption 3.2. We assume the whitened feature variable U == :>=->// 1/1/2 (X1) is a p² -ubbaaaussi random variable, where Σg = Elg(( (X)x())))((
We note that all bounded random variables satisfy sub- -ob-gaussiin property.
Theorem 3.2 (General conditional independence). Fix a failure probability 8 E (0, 1), under the
same assumption as Lemma 3.1 and Assumption for vb", if additionally > pA(k + log(1/5)),
then the excess risk of the learned predictor æ W 3/-00(0 (x1) the downstream task satsifies
5

---

ER [ 22000 (
Remark 3.1. This analysis assumes we could perfectly learn &/" = xi] disregarding the number of samples the SSL phase (unlabeled data cheap to obtain). Here by sample complexity refer to the labeled data (X,,Y). We defer the effect of imprecise representation v in Section 4.
3.2 Function class induced by feature maps.
Given feature map Φ1 21 + PR, we consider the function class Hi = 116= X1 - Rd B
E
RdxxD: Di (x1) = B (x1))-
Claim 3.3 (Closed form solution). The optimal function in H is e6 (x1) Ex201 E $1 (x1)) where Σxp01 (X,) and Eœ10 =- (X1)
We again show the benefit of CI, but only comparing the performance of sh² to the original features Φ1 Since v0 is linear in Φ1, it cannot have smaller approximation error than Φ1 However CI will ensure that o has the same approximation error as @1 and enjoys better sample complexity.
Lemma 3.4 (Approximation error). If Assumption 3.1 is satisfied, and if the matrix A E X with gg == E[x2|Y y) is of rank k = [)]] Then (xp)((i) = (61))
We additionally need an assumption the residual a(x1) E ==1] (2
Assumption 3.3. (Bounded approx. error; Condition 3 in (321)) We have almost surely
Σ 1/2 bioo (X1))(()) 1l S bovk
Theorem 3.5. (CI with approximation error) Fix a failure probability (0, under the same assumption as Lemma 3.4, Assumption 3.2 for a/" and Assumption 3.3, if >> pA + log(1 /5)), then the excess risk of the learned predictor I1 W 2/- (I1) the downstream task satisfies:
ER W| S Capx (01) + Ô 0²)
Thus with SSL, the requirement of labels is reduced from complexity for D1 to O(k).
4 Beyond conditional independence
In the previous section, we focused on the case where we have exact CL. A weaker but more realistic assumption is that Y captures some portion of the dependence between X, and X₂ but not all. We quantify this notion of approximate ACI through quantity è (Definition 4.1), and show excess risk bounds for the representation learned from SSL4 In particular, the excess risk will have the
form δ ( d2 + c + - which suggests that only n22 (d2) labeled samples will be required
to get small error on downstream task, as long as approximate CI is satisfied (cc is small) and the pretext task is solved well enough (e is small). This is in contrast to not doing SSL, where many more labeled samples will be required to learn a solve the downstream task that learns complicated representation function from scratch. We now describe the SSL method on finite samples, followed by the definition of ACI which we use to discuss the main excess risk bound and its consequences.
SSL with finite samples and general function space: Let X!Te [I R xdi and X₂ = [x
[x(
(1.pre)
(n pre) IT
(mi)TT E R xda be 7n training samples for pretext task, where X,- The n2 labeled samples for the downstream task are defined as X-dowm E _ Y E R Given representation function space H X₁ + Rd, we learn v from H using the nı unlabeled samples and then use the na labeled samples to learn linear classifier on the learned representation e5( ((Xdown) to fit Y. This process is summarized below.
x2
(or (L.pr) (4) is sampled from Xx,x,-
m22
1) 3 = arg min
- -| 1(X )1 2) W arg min Y JER 71
( down W
(2)
w
2nz
We will use Ô to hide log factor (8) or log(d2/6).
4 Resulls for jointl-GGussiin variables is Appendix D.1; ACT is quantified by the partial covariance matrix. dd le and Y = dY) (one-hot encoding) refers multi-class classification task, da = 1 refers to regression.

---

In our main results, we consider two types of function spaces: H. E {M1, Hu.. Recall that H1 (v(()) = B (+); B E RddxDi) is a class of linear representations induced by feature map Φ1 X1 D. We use H, denote a function space with universal approximation power (e.g. deep networks) that ensures v0- = [[ E Ha. We define the optimal predictor in each case as (x)) = [ (X,)] when H1. JR f for H Ha. we define excess risk
16
ER, (W) = Ex, (x)) - W W T (x
Approximate conditional independence: Our new assumption will generalize Assumption 3.1 in two ways, 1) we allow for additional latent variables Z that together with Y could potentially make X1 and X2 independent, and 2) we allow this conditional independence to be approximate. Note that allowing for extra latent variable can trivially make X₃ and X₂ to be conditionally independent by picking large enough Z (e.g. Z (X1. X2)). However the following assumption, that needs the pretext target X2 to correlate with all instances of variable Y = [Y, Z| (analogous to Lemma 3.1), will impose this restriction on how large Z can be.
Assumption 4.1 (Correlation between X2 and Y, 7). Suppose there exists latent variable | = m that ensures X is full column rank and | |Σy M
X ll = 1/3, where Al is
psendo-inverse, and Øg is the one-hot embedding for Y [Y, Z].
Just in Section 3, this assumption will not assume away the problem (Example 3.1 can be suitably extended). The additional term 1/3 8 here captures both the "scale" of X₂ and also the strength of correlation between X2 and [Y, Z] that was discussed after Lemma 3.1. For Σggx, to be full column rank, it is essential that d2 > km, and this already gives an upper bound on the size of Z. Given this restriction on (and thus Y), we define the notion of approximate conditional independence.
Definition 4.1 (Approximate conditional independence with function space H). For Y = [Y, ZI.
1. For H Hi, define ECr 2 1/2 di Xaldy F. 2. For H = Hu. define & == Ex, | x Ey [X]]111111
Firstly we note that this is indeed an extension of exact CI, since exact CI in both cases will imply that 6CI = O. We present unified analysis in the appendix that shows the <cT for the second case is same as the first case, with covariance operators instead of matrices (A direct derivation is in Claim D.7). We also present more relaxed and general form of the above assumptions in Appendix F.1. With this assumption, we are ready to present our main bound.
Bound on excess risk: Recall that we assume that the residual term N := - X1] is mean zero and o² -7-subgaussian. Before showing our main result, analogous to Assumption 3.3, for the class H, with non-universal features d1, we will need an assumption on the residual = fH. = E|| - (
Assumption 4.2. (Bounded approximation error on pretext phase [32]) There exists universal 1/2 ||=-1/2 0id1 @1
constant by, such that ||
( (X1))(X,) S / almost surely.
Theorem 4.2. For fixed ā E (0, 1), under Assumptions 4.1.3.2 for & and a/² and 4.2 for non- universal feature maps, if n1, 72 >> (d22 + log 1/6), and we learn the pretext tasks such that: (X,) - 3/ (X1) S egn. Then the generalization error for downstream task w.p. 1 is:
ER ( S
E g2
Y12
B2
extimatiin evror
approximation error/
We defer the proof to the appendix. The proof technique is similar to that of Section 3. The difference is that now و X (down) E d2 will be approximately low rank matrix, where the low rank part is the high-signal features that implicitly comes from Y. Z that can linearly learn downstream task. The remaining part comes from 6CI and Gree and causes the approximation error. Again by selecting the top km (dimension of (g)) features we could further improve the bound:
'This rules out the failure if one chooses very simple function class to learn ||[x2| In practice we usually neural networks (with universal approximation power) and this bound should be very small.
7

---

Remark 4.1. By applying PCA on (( and keeping the top km principal components only, we can improve the bound in Theorem 4.2 to E (R)(W)
(W S O
0²2
fmm 112
We take a closer look at the different sources of errors in Lemma 4.1: 1) The first term is estimation eгror on learning with finite samples n2 with noise level x² in Y- (X,): 2) ea measures the approximate CI; and 3) épre is the error from not learning the pretext task exactly. The first term optimal ignoring log factors as we do linear regression on mk-dimensional features. The second and third term together form approximation error. They are non-reducible due to the fact that f" is not exactly linear in & and we use it as fixed representation. Fine-tuning the representations might be necessary to get rid of these terms when we have sufficient downstream labeled data. We leave this exploring this future work. Compared to traditional supervised learning, learning f requires sample complexity scaling with the (Kademacher/Gaussin) complexity of H (see e.g. [8, 52)), which is very large for complicated models such deep networks. Thus SSL can significantly reduce the labeled sample complexity down from this complexity measure of H to O (km). demonstrating the power of predicting what you already know using unlabeled data. In Section H. we consider a similar result for classification.
Example: Topic Modeling
In this section, we will demonstrate how framework can be instantiated for standard data model like topic modeling. Topic modeling for text that has a rich literature [47, 31, 9, 4, 3] and is used for analyzing and designing algorithms for information retrieval, dimensionality reduction and data analysis for large text corpora. We describe the basic setup below, followed by how our results for reconstruction-basee SSL can be instantiated learn such models.
For a set S. let As denote the set of all distributions on S. In the topic modeling framework, generation of a text document with a vocabulary set [V] {l..... V/ is governed by certain latent topics from the set [k]. where & is the total number of topics. Each topic E [k]] is associated with a distribution over the vocabulary [V] that is denoted by vector A, A [v]; stack these vectors into (.I,.... .n) E [V]N of length N is then
the columns of a matrix A RV A document sampled from mixture of the & topics μ E Am.- The generative process is described below:
1. Sample a topic mixture j ~ T. is some underlying distribution over As, i.e. T E AAp
2. For each E [N], sample a topic 14 ~ y and sample word x; Ar, from the topic
For the reconstruction SSL task, we evenly split the document as X = (X,, X2), where X1 and X₂ denote the first and second halves of the document; note that X1, E [V] We let X1 and X2 be the multiset of words in the two halves by using the normalized bag-of-words representation, Le. X, = A ofu-oof-ordd({e
E RV, E {1,2}7. The downstream task is chosen to be a linear function of the topic posterior distribution μ for given document X, i.e. Y = w T [[u][]] + N, where N is 0 mean and ou-subgaussian. The error of predictor f [V] + R is measured as E,,x (f(X) 1 JTTu ") the optimal predictor being (X) [Y X
crucial property of topic model described above that words in the document are sampled independently given the topic mixture μt, thus giving us the property: X, 1 X₂ I μ. Although the cardinality of μ E А (that implicitly shows up in Theorem 4.2) is infinite, we can still show the benefit of SSL using our theoretical framework. We will show appropriate bounds for ECr and B, that show up in Theorem 4.2, using the topic model generative process. We make the following standard assumptions about the topic modeling distribution, motivated by prior work [4, 3].
Assumption 5.1. Let E V* be the word-topic matrix and r Epprr [u be the topic covariance matrix, then the following hold
(Anchor word) The word-topic matrix A is p-separable for p 0, i.e. for every topic E [k] there is a word j such that Ax(J) Z p and (+) = 0 when if +
* I is full rank, so condition number Amaax
Amiu <
We only need X2 to be the bag-of word representation. Xı can be ordered sentence.
8

---

class
9 and non-lineer function clay
and non linear function class
0.0025
0:0004
2
0.0000
0.0020
0.0044
0.2002
6,0003
0.4 0.6
012
0.. 044
00
611
(a)
(b)
(c)
(d)
Figure/ I: Leftt two: how MSE scales with & (the dimension of Y) and ECI (Definition 4.1) with the linear function class. Right two: how MSE scales with k and with o and non-linear function class. Mean of 30 trials are shown in solid line and one standard error is shown by shadow.
Theorem 5.1. Let ecI be the definition (2) from Definition 4. and B as defined in Assumption and suppose the topic model satisfies Assumption 5, then there exists latent variable Y E Suchh that the following hold
1. Y takes k distinct values, i.e. |
2. X1 and X1 are uncorrelated given Y. which implies ECr = O.
3. [ [X]] a linear function of |
4. 9 S x||2/|12/ / (A) I K x2/ww///P
The proof for this is presented in Section E.1. Note that the p-separability is not necessarily needed, and the bound with Amin (min(A) can be invoked instead. Thus the upper bound from Theorem 4.2) will
look like ①
(02 + 2 xl|welz) thus requiring only (kk) samples for the downstream task.
pre
Experiments
In this section, we empirically verify our claim that SSL performs well when ACI is satisfied. More details for experiments can be found in Section J, including experiments in the text domain.
Simulations. With synthetic data, we verify how excess risk (ER) scales with the cardinality/fcature dimension of y (k), and ACI (ecr in Definition 4.1). We consider a mixture of Gaussian data and conduct experiments with both linear function space (H1 with d1 identity map) and universal function space Hu. We sample the label uniformly from (1.... k}. For i-th class, the centers μлı Rdd and fun E Rd are uniformly sampled from [0, 10). Given Y i, a E [o, 1], let X1 ~ ((1ss I), X2 ~ N( I), and X₂ = (1 - a) + ax1, Therefore a is a correlation coefficient: = 0 ensures X₂ being CI with X₁ given Y and when 1, X2 fully depends X1. (if d, # dz, we append zeros or truncate to fit accordingly).
We first conduct experiments with linear function class. We learn linear representation with nn samples and the linear prediction of from & with n2 samples. We set di 50, d2 = 40, ni 4000, n2 1000 and ER is measured with Mean Squared Error (MSE). As shown in Figure (b),,), the MSE of learning with vi( X,) scales linearly with & as indicated in Theorem 3.5, and scales linearly with ECI associated with linear function class as indicated in Theorem 4.2. Next we move on to general function class, i.e., 3 = | [X]] with closed form solution (see example 3.1). We use the same parameter settings as above. For baseline method, we use kernel linear regression to predict Y using X, (we use RBF kernel which also has universal approximation power). As shown Figure (c), the phenomenon is the same as what we observe the linear function class setting, and hence they respectively verify Theorem 3.2 and Theorem 4.2 with Hy.
Computer Vision Task. We verify if learning from eb is more effective than learning directly from X1. in realistic setting (without enforcing conditional independence). Specifically, we test on the Yearbook dataset [23], and try predict the date when the portraits are taken (denoted as YD), which ranges from 1905 to 2013. We resize all the portraits be 128 by 128. We crop out the center 64 by 64 pixels (the face), and treat it as X2, and treat the outer rim as X1 as shown in Figure 2. Our task is to predict Yp, which is the year when the portraits are taken, and the year ranges from 1905 to 2013. For vi, we learn X2 from X, with standard image inpainting techniques [48], and full set of training data (without labels). After that we fix the learned v and learn linear model to predict YD from v using smaller set of data (with labels). Besides linear model on X1, another strong baseline that

---

(linzar)
350
X, (Incar)
(liear)
K1 (Inear)
(lhezrr
Meen Error
500
((Xy) (inear)
W(Kg] (linear)
Mean Absolute
16
(reinetbe)
<50
400
15
300
250
12
1000 1500
2500 3000
1000 1500 2000
2500
3000
Number of labeled data
Number of labeled data
Figure 2: Left: Example of the X2 (in the red box of the 1st row), the X1 (out of the red box of the 1st row), the input to the inpainting task (the second row), (x(1)) (the row in the red box), and in this example Y 1967. Middle: Mean Squared Error comparison of yearbook regression predicting dates. Right: Mean Absolute Error comparison of yearbook regression predicting dates, Experiments are repeated 10 times, with mean shown in solid line and one standard deviation shadow.
we compare with is using ResNet18 [28] to predict YD from X1. With the full set of training data, this model is able to achieve Mean Absolute Difference of 6.89, close to what of-ec-of-thh-att can achieve [23]. ResNet18 has similar amount of parameters as our generator, and hence roughly in the same function class. We show the MSE result in Figure 2. Learning from d is more effective than learning from X1 or X₂ directly, with linear model as well as with ResNet18. Practitioner usually fine-tune & with the downstream task, which leads more competitive performance [48].
7 Conclusion
In this work theoretically quantify how approximate conditional independence assumption that connects pretext and downstream task data distributions can give sample complexity benefits of self-supervised learning on downstream tasks. Our theoretical findings are also supported by experiments on simulated data and also on real CV and NLP tasks. We would like to note that approximate CI is only sufficient condition for useful pretext task. We leave it for future work to investigate other mechanisms by which pretext tasks help with downstream tasks.
Acknowledgment
JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0301 the Sloan Research Fellowship, NSF CCF 2002272, NSF IIS 2107304, and an ONR Young Investigator Award. QL was supported by NSF #2030859 and the Computing Research Association for the CIFellows Project. NS is supported by NSF, ONR, Simons Foundation, DARPA and SRC. JZ acknowledges sponsorship of Army Research Office and support of Cooperative Agreement Number W91 19-2-0333 and NSF grant 2019844. The views and conclusions contained this document are those of the authors and should not be interpreted as representing the official policies, either expressed implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Guillaume Alain and Yoshua Bengio. What regularized auto-encoders learn from the data- generating distribution. The Journal of Machine Learning Research, 15(1):3563-3592 2014.
[2] Rie Kubota Ando and Tong Zhang. Two-view feature generation model for semi-supervised learning. In Proceedings of the 24th international conference on Machine learning, pages 25-32, 2007.
[3] Sanjeev Arora, Rong Ge, Yonatan Halpem, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. practical algorithm for topie modeling with provable guarantees. In International conference machine learning. PMLR, 2013.
10

---

[4] Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models going beyond svd. In 2012 IEEE 53rd annual symposium on foundations of computer science. IEEE, 2012.
[5] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. In Proceedings of the 36th International Conference on Machine Learning. 2019.
[6] Charles R Baker. Joint measures and cross- covsaroove operators. Transactions of the American Mathematical Society, 186:273-2888 289,2,, 1973.
[7] Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):93--945, 1993.
[8] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
(9] David M Blei, Andrew Y Ng, and Michael Jordan. Latent dirichlet allocation. the Journal of machine Learning research, 2003.
[10] Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proceedings of the eleventh annual conference Computational learning theory, 1998.
[11] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, pages 11 11199-112 11201, 2019.
[12] Tianlong Chen, Sijia Liu, Shiyu Chang, Yu Cheng, Lisa Amini, and Zhangyang Wang. Adversarial robustness: From self-supervised pre-training fine-tuning. arXiv preprini arXiv:2003.12862 2020.
[13] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning visual representations. arXiv preprint arXiv:2002.05709, 2020.
[14] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self-supervised models are strong cemi-supervised learners. arXiv preprint arXiv:2006. 10029, 2020.
[15] Jacob Devlin, Ming-Wee Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018.
[16] Carl Doersch, Abhinav Gupta, and Alexei A Efros. Unsupervised visual representation learning by context prediction. In Proceedings of the IEEE International Conference Computer Vision, pages 1422-1430, 2015.
[17] Alexey Dosovitskiy, Philipp Fischer, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with exemplar convolutional neural net- works. IEEE transactions on pattern analysis and machine intelligence, 38(9):133-1147,, 2015.
[18) Simon $ Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint (Bl::2002.094344 2020.
[19] Basura Fernando, Hakan Bilen, Efstratios Gavves, and Stephen Gould. Self-supervised video representation learning with odd-one-out networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3636-3645, 2017.
[20] Kenji Fukumizu, Francis R Bach, and Michael I Jordan. Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces. Journal of Machine Learning Research, 5(Jan):73-99 2004.
[21] Kenji Fukumizu, Francis R Bach, Michael Jordan, et al. Kernel dimension reduction in regression. The Annals of Statistics, 37(4):1871-190 2009.

---

[22] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint 180..078 2018.
[23] Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, and Alexei A Efros. A century of portraits:
A visual historical record of american high school yearbooks. In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 1-7, 2015.
[24] Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. In International conference on algorithmic learning theory, pages 63-77. Springer, 2005.
[25] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, al. Bootstrap your own latent: A new approach self-supervised learning. arXiv preprint arXiv:2006.07733, 2020.
[26] David Gross. Recovering low-rank matrices from few coefficients in any basis. JEEE Transac- lions on Information Theory, 57(3):1548-1566 2011.
[27] Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, 2010.
[28] 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, pages 770-778, 2016.
[29] Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self self-supervised learning can improve model robustness and uncertainty. In Advances in Neural Information Processing Systems, pages 15637-15648, 2019.
[30] R Devon Hjelm, Alex Fedorov, Samuel Marchi-Mar Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv:1808.0661 2018
[31] Thomas Hofmann. Probabilistic latent semantic indexing. In Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, 1999.
[32] Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on learning theory, pages 9-1, 2012.
[33] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zimik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks, arXiv preprint 1905. 2019.
[34] Tzee-Ming Huang. Testing conditional independence using maximal nonlinear conditional correlation. The Annals of Statistics, 38(4):2047-2991, 2010.
[35] Eric Jang, Coline Devin, Vincent Vanhoucke, and Sergey Levine. Grasp2vec: Learning object representations from self-supervised grasping. arXiv preprint 1xXiv:1811.0690 2018.
[36] Longlong Jing and Yingli Tian. Self-supervised visual feature learning with deep neural networks: A survey. IEEE Transactoons on Pattern Analysis and Machine Intelligence, 2020.
[37] Sham M Kakade and Dean P Foster. Multi-view regression via canonical correlation analysis. In International Conference Computational Learning Theory, pages 82-96. Springer, 2007.
[38] Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual representation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 1920-1929, 2019.
[39] Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence rep- resentations. In Proceedings of the International Conference on Learning Representations, 2018.
12

---

[40] Zhuang Ma and Michael Collins. Noise contrastive estimation and negative sampling for condi- tional models: Consistency and statistical efficiency. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018.
[41] Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, ((Deec):651-2667, 2006.
[42] Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed repre- sentations of words and phrases and their compositionality. In Advances in neural information processing systems, 2013.
[43] Ishan Misra, C Lawrence Zitnick, and Martial Hebert. Shuffle and learn: unsupervised learning using temporal order verification. In European Conference on Computer Vision, pages 527-544. Springer, 2016.
[44] Jovana Mitrovic, Brian McWilliams, Jacob Walker, Lars Buesing, and Charles Blundell. Repre- sentation learning via invariant causal mechanisms. arXiv preprint arXiv:2010.07922 2020.
[45] Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. European Conference on Computer Vision, pages 69-84. Springer, 2016.
[46] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprini arXiv: 1807. 307.03748, 2018
[47] Christos H Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala. Latent semantic indexing: A probabilistic analysis. Journal of Computer and System Sciences, 2000.
[48] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2536-2544, 2544, 2016.
[49] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. URL https://s3-us-weekt amazonaws. com/openai- understanding paper. pdf. 2018.
[50] Michael Reed. Methods of modern mathematical physics: Functional analysis. Elsevier, 2012.
[51] Nikunj Saunshi, Sadhika Malladi, and Sanjeev Arora. A mathematical exploration of why language models help solve downstream tasks. arXiv preprint arXiv:2010.03648, 2020.
[52] Shai Shalev-Shwartz and Shai Ben- Danidd Understanding machine learning: From theory to algorithmss. Cambridge university press, 2014.
[53] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, 2013.
[54] Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. arXiv preprint 1rXiv: 2019.
[55] Yuandong Tian, Lantao Yu, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning with dual deep networks. arXiv preprint 1rXi0:2010.00578, 2020.
[56] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv preprint arXiv:2003..02234, 2020.
[57] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. arXiv preprint (eXX::2008.10150, 2020.
[58] Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis- Philipp Morency. De- mystifying sele-super learning: An information-theorrttiaal framework. arXiv preprint arXiv:2006.05576. 2020.
13

---

[59] Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning, arXiv preprint SdVv:1907.136255 2019.
[60] Pascal Vincent. A connection between score matching and denoising autoencoders. Neural computation, 23(7):1661-160 2011.
[61] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pages 1096-1103, 2008.
[62] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity the hypersphere. arXiv preprint arXiv:2005. 2020.
[63] Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In Proceedings of the IEEE International Conference on Computer Vision, 2015.
[64] Donglai Wei, Joseph Lim, Andrew Zisserman, and William Freeman. Learning and using the arrow of time. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pages 8052-8060, 2018.
[65] Han Yang, Xiao Yan, Xinyan Dai, and James Cheng. Self-enhanced gnn: Improving graph neural networks using model outputs. arXiv preprint arXiv:2002.07516 2020.
[66] Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In European conference on computer vision, pages 649-666. Springer. 2016.
[67] Richard Zhang. Phillip Isola, and Alexei A Efros. Split-brane brain autoencoders: Unsupervised learning by cross-channel prediction. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 1058-1067, 2017.
[68] Zaiwei Zhang, Zhenxiao Liang, Lemeng Wu, Xiaowei Zhou, and Qixing Huang. Path-invariant map networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1008-11094, 2019.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to YYs]] [No], or [N/A]. You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questionss/answess below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section I, especially the contribution paragraph.
(b) Did you describe the limitations of your work? [Yes] See the Conclusion section and line 314-326.
(c) Did you discuss any potential negative societal impacts of your work? [No] This is mainly a theoretical work with simulations and should not cause much social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
14

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Every assump- tion is listed as a standalone block. Every theorem or lemma is self-contained.
(b) Did you include complete proofs of all theoretical results? [Yes] For every theorem, lemma, claim, and some technical remarks, we indicate where their proof is located in the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No] The codes will be made public after this work accepted for publish.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The details are provided in the sections and
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure Figure and Figure 2.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] The details provided in the Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6.
(b) Did you mention the license of the assets? [Yes] The details are provided in the
Appendix
(c) Did you include any new assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] All the portrait the Yearbook dataset are in
public domain. Please find the detailed discussion in Section 3 of the Yearbook dataset paper [23]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "xPRozjOrRiB", "reviewer": "Reviewer_f8xA", "summary": "This paper aims to theoretically explain and investigate the benefit of reconstruction-based self-supervised learning. This paper studies a specific problem with two input features and one downstream label and shows how the specific connection between them can guarantee successful self-supervised learning.  In particular, this paper quantifies how the approximation independence between two input features can be extracted to solve the downstream tasks. Results show that self-supervised learning can successfully learn the ground-truth with much smaller labeled sample complexity.\n", "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": "I have to say I am not familiar with self-supervised learning and its theory. From a general point of view, the theory established in this paper is rigorous and makes sense to me. The assumptions, theorems, claims are clearly presented.  \n\nHowever, my main concern is regarding the clarity of the paper. For example, from the proof sketch of Lemma 3.1, it is not clear why the matrix A has rank $k=|Y|$? Why sometimes the authors use the $\\arg\\min$ notation to denote $f^*$ and $\\psi^*$, and sometimes they are written using the expectation notations.\n\nThere are a bunch of notations used in the paper (e.g., $b_0$, $\\beta$, $\\alpha$, $k$, $m$, $\\rho$, etc). It would be better to summarize them somewhere. Besides, I am wondering whether the authors can briefly elaborate on which of them are typically large (e.g., $\\omega(1)$) and which of them are typically small (i.e., $o(1)$).\n\nLastly, does the conditional independence really hold in practice, or how small is their correlation? The authors should add more content to justify this (experimental justification could be better). \n\n=========================\n\nThanks for the authors' response. I agree the paper presentation can be improved after fixing the problems I mentioned. I would like to keep my evaluation marginally acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper has no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hrs"}, "extra_text": {}}, {"review_id": "SYi4DwDcA5i", "reviewer": "Reviewer_Y1dq", "summary": "- The paper theoretically analyzes self-supervision under some simplifying assumptions. They begin with a conditional independent setting, where X1 is conditionally independent of X2 given Y.\n- The high-level idea is to first pre-train a model that predicts X2 from X1. This can be done on unlabeled data. Then they can fit a model on top of representations learned by this model, to predict Y.\n1. Ground truth self-supervision: They show that if we learn E[X2 | X1], the ground truth self-supervision function, then under mild invertibility conditions, E[Y | X] is a linear function of E[X2 | X1]. Further, E[X2 | X1]'s effective dimension is the same as Y, so this linear function can be fit using very few examples. In contrast, the function from X1 or X2 to Y can be very complicated / non-linear and require many examples to fit.\n2. Linear self-supervision: They then examine what happens if we fit a linear function (on feature space) to predict X2 from X1. This can learn a useful lower dimensional embedding, and then we train a linear classifier to predict Y on top of this. They show this is more sample efficient than just training a linear classifier from X1 to Y.\n3. Relaxing conditional independence: They quantitatively examine how this degrades when we don't exactly have conditional independence. Their bounds will still be good if things are \"almost\" conditionally independent.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "After rebuttal: added comments below\n\n---------------------------------------------------------------------------------------\n\nStrengths\n- I think this is a strong paper. Result (1), that E[Y | X1] is a linear function of E[X2 | X1] under conditional independence, is already conceptually quite intriguing to me. It's easy to prove if someone told you the result was true and asked you to prove it, but it is nice and surprising. In fact, I mentioned the result to a couple people who are really good at ML theory and work in related areas, and they didn't believe the result at first - they figured it could be true for Gaussians under conditional independence, but not in general (for discrete Y).\n- I think results (2) and (3) make the paper even stronger, because they handle situations where we don't have exact conditional independence, or if we learn a linear model (even when the ground truth model is much more complicated).\n\nWeaknesses\n- Please label all equations for easy reference, both in the main paper and appendix\n- The quality of writing in the Appendices should be substantially improved. To be clear, I'm not saying anything is wrong. I sampled some proofs and read them carefully, and they do appear to be correct, but they're very hard to follow.\n- Focusing on the proof of Theorem B.3. In line 693, in the first step, I believe it should be <= -2<N, psi(X1) W* - psi(X1) \\hat{W}>\n- I'm not sure what P_{\\psi(X_1)} is, what are we projecting to? And why does that not change N?\n- In the last line of the equation array in line 697, you have an extra k in the denominator, it's not clear why that disappears?\n- In the first line to the second line of the equation array in line 697, how does a matrix vector product (which is a vector) transform into a scalar (frobenius norm)?\n- Unfortunately, it's hard for me to verify the results from Section 3.2 onwards, especially for Section 4. I did some basic sanity checks to see that they seem reasonable, and sampled some parts of the Appendix, and it looks likely correct overall.\n- Part of why the proof are hard to verify is because the results are somewhat complicated (which isn't a bad thing!). But the other more important issue is that there aren't substantial proof intuitions given in the main paper, and the proofs in the appendix don't seem to be written very well (for example, a large number of typos just between line 693 and 697). I only sampled a small proportion of proofs, so it's possible that I happened to sample the bad examples.\n- I'd personally err on the side of having fewer results, that are very clearly explained and proved, and that the reader can fully understand.\n\nI think it's worth comparing this framework much more carefully with co-training. Both co-training and self-supervision are essentially semi-supervised learning methods, and co-training also assumes conditional independence. How would the bounds compare between the two? The initial co-training paper assumed conditional independence, and later versions assume weaker properties such as expansion [1], inspired from spectral graph theory.\n\nI think it's worth noting that k often increases exponentially. E.g. if Z represents r 'semantic' features (like color, rotation, etc), each of which can take on one of s values, then k = s^r. Could be interesting for future work to avoid this blowup.\n\nOther comments\n- Why do we need to apply PCA in remark 4.1? E.g. in theorem 3.2, we didn't need PCA, because the complexity depends on the trace of some matrix so automatically improves if the data lies in a lower dimensional subspace.\n\nMinor comments:\n- Remark 3.2 uses m, which is defined later in assumption 4.1\n- Claim A.3 has typos, it says it's a concentration result for sub-Gaussians, but assumes the data is Gaussian. Also unclear what Sigma_X is if it's sub-Gaussian?\n- I think Theorem 3.2 should use n_2 instead of n in the theorem statement.\n- Line 274 appears to change the definition of excess risk - maybe use a different terminology?\n- In theorem 4.2, is assumption 3.2 actually not needed for universal feature maps?\n- In theorem 4.2, do you really need both a lower bound on n1 *and* an upper bound on the error of the pretext tasks, \\epsilon_pre^2?\n\n[1] Co-Training and Expansion: Towards Bridging Theory and Practice. Maria-Florina Balcan. Avrim Blum. Ke Yang.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Looks fine.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "NgGHl31NqWG", "reviewer": "Reviewer_BbkL", "summary": "This paper studies whether reconstruction-based pretext task can provide representations helpful for downstream tasks, which is a question of good interests in the community.\n\nThe authors give an affirmative answer that when (approximate) conditional independence holds, reconstruction as a pretext task provides representations such that 1) an additional linear layer is sufficient to ensure small approximation error on classification, and that 2) helps to reduce the sample complexity of the classification task from complexity of the function class (without pretraining) to linear in data dimension.\n\nThese theoretical results are empirically verified on synthetic, vision (inpainting), and NLP (sentiment classification) tasks.", "questions": "", "limitations": "", "rating": 7, "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": "**Significance and novelty of the contribution**: To the best of my knowledge, this paper is the first to provide a statistical connection on reconstruction-based self-supervised methods and downstream tasks. The setup and (approximate) conditional independence assumption is reasonable; for example, several recent works on multi-view redundancy adopt similar assumptions. \n - It's much appreciated that the theoretical results are verified by multiple experiments. However, it would be better if the authors could comment more on the practical implications of the assumptions required for theory.\n\n**Relation to prior work**: This paper is clearly situated in relation to prior work. The discussions on comparison to prior work (esp multi-view) are sufficiently detailed which is appreciated.\n\n**Clarity & writing**: This paper is well structured and easy to follow. Some minor notes:\n- Typo: Thm 3.2: $n$ should be $n_2$.\n- Line 235: $d_2 < km$: $m$ hasn't been introduced yet.\n- Line 239: on the RHS of $\\psi^*$, $x_1$ should be $\\phi_1(x_1)$ (otherwise $\\psi^*$ is linear in $x_1$).\n- Typo: line 321: remove the first word \"this\".\n\n====== \nPost-rebuttal update: I thank the authors for their responses and keep my score of recommending an accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Future directions pointed out by the authors include 1) analyze the effect of fine-tuning to bring down the approximation error terms; and 2) study other possible conditions under which pretext tasks are helpful for downstream learning, since CI is sufficient but likely not necessary.\n\nSocietal impact is not applicable since this work is theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5 (have seen the paper before)"}, "extra_text": {}}, {"review_id": "0sGQemoJ20W", "reviewer": "Reviewer_hGAR", "summary": "This paper suggests a theoretical model to capture\nwhy reconstruction-based self-supervised learning leads to good representations, and improved downstream performance.\nThe suggested model is that the pretext task \"factors through\" the supervised labels, i.e. that X_1 -- Y -- X_2 is Markov, where X_1-->X_2 is the pretext task, and X_1 --> Y is the supervised task.\nIn such a setting, it is shown that the optimal pretext function has certain good properties: it linearly separates the supervised task, and\nis \"low rank\", so can be used for efficient downstream learning.", "questions": "", "limitations": "", "rating": 4, "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": "## Strengths\n- The main realization of this paper is interesting: it gives a setting\nwhere learning an \"auxiliary\" task is actually linearly-related to the task of interest (without assuming any linear structure in the tasks themselves). This is the statement of Lemma 3.1, which I consider to be the main conceptual contribution of this paper.\nLemma 3.1 is technically straightforward, but the statement is interesting.\n\n- The problem studied is important: we do not have much theoretical understanding of why SSL methods work in practice.\n\n## Weaknesses\n\n- The primary weakness of this paper is that the statistical (Markov) assumption is extremely strong (even in its \"approximate\" formulation),\nand does not clearly connect to any situations in practice.\nThere are no experiments that support the assumptions, and the intuitions presented are not convincing. That is, although the claimed motivation\nof this paper is to study \"What conceptual connection between pretext and downstream tasks ensures good representations?\", the results in the paper do not clearly shed light on this question in realistic settings.\nIn particular, I do not think Assumption 4.1 will hold in practice, for reasonable values of $m$. More importantly, I do not think it captures the spirit of many pretext tasks: there could be very high mutual information between X_1 and X_2 in practice, even when conditioned on the supervised label (Y). This is especially the case when the supervised task is much \"easier\" than the pretext task.\n\n- I do not believe the technical contributions are strong enough to stand alone, without appropriate motivation from practice.\nMost of the technical results are essentially corollaries of\nLemma 3.1, expanded in straightforward ways.\nI do not think these results contribute significantly\nto the mathematical theory of learning (and they do not develop any new technical tools, as far as I am aware).\n\n- The empirical section is lacking. It would have been nice to see some attempts to empirically justify the theoretical assumptions made in this work. For example, by trying to approximately estimate the conditional independence in realistic settings.\nHowever, the experiments on real data do not attempt to probe the validity of the assumptions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impacts N/A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of four reviewers generally agree to recommend this paper for acceptance, and I agree with the strengths that they highlight, especially as reviewer Y1dq summarizes them.

Reviewer hGAR, who recommends rejection, makes a valid point as well: the experimental section and the discussion of assumptions leaves room for improvement. I encourage the authors to take the committee's suggestions about these parts into consideration when revising the draft.

For instance, two reviewers would have liked to see an empirical signal for whether the conditional independence assumption holds in a real data setting (not simulation). Even if the authors choose not to do this, it is natural to ask and it is lacking from the experiments, and so it is ultimately a limitation. It's best to be clear about whether the experiments are meant to closely verify theory (including its assumptions), or whether they are meant only to show that the analysis is at least not at odds with empirical observations. The latter seems to better describe this paper's experiments, but it is a weaker point than the former, and discussing limitations ultimately helps with clarity.

I will add that there are other ways to support an assumption than by experiment. One is to identify example mathematical constructions that satisfy them (e.g. topic models, HMMs). Another is to point to similar assumptions made in related prior work. The paper does the latter reasonably well. If it is easy enough to do, perhaps the authors can make use of an example construction or two as well.

Overall I second Y1dq's remarks in discussion that this is a field with little theoretical analysis, and that what constitutes a reasonable abstraction and assumption is not yet clear. Making assumptions for progress is fine, especially if similar ones have been make in related work. The validation and discussion of assumptions in this paper could be improved as hGAR emphasizes, but overall the support from the remaining reviewers leads me to recommend acceptance.

Decision: Accept (Poster)