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

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. 

Under review as a conference paper at ICLR 2021
PREDICTING WHAT YOU ALREADY KNOW HELPS: PROVABLE SELF-SUPERVISED LEARNING
Anonymous authors
Paper under double-blind review
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 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. 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 top of the learned representation.
INTRODUCTION
Self-supervised learning revitalizes machine learning models in computer vision, language modeling. and control problems (see reference therein (Jing & Tian 2020 Kolesnikov et al.. 2019 Devlin let al. 2018 Wang & Gupta 2015 Jang et al., 2018)). Training model with auxiliary tasks based only on imput features reduces the extensive costs of data collection and semantic annotations for downstream tasks. is also known improve the adversarial robustness of models (Hendrycks et al.)
2019 Carmon et al. 2019] Chen et al. 2020a). Self-supervised learning creates pseudo labels solely based on input features, and solves auxiliary prediction tasks supervised manner (pretext tasks). However, the underlying principles of self-supervised learning are 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 a good way to quantify this?
As thought experiment, consider 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 (Zhang et al.] (0166). Denote X1,X2, Y to be the input image, color channel, and the downstream label respectively. Given knowledge of the label Y, one can possibly predict the background X₂ without knowing much about X,. In other words, Xx2 approximately independent of X1 conditional on the label Y. Consider another task of inpainting (Pathak et al. (0166) the front of a building (X2) from the rest (X1). 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 X₂ given Y, Z is small. We can mathematically interpret this as X, being approximate conditionally independent of X₂ given Y.
In the above settings with conditional independence, the only way to solve the pretext task for X, is to first implicitly predict Y and then predict X2 from Y. Even without labeled data, the information of Y is hidden in the prediction for X2.
We propose mechanism based approximate conditional independence (ACI) to explain why solving pretext tasks created from known information can learn representations that provably reduce downstream sample complexity. For instance, learned representation will
Contributions.

---

Under review as a conference paper at ICLR 2021
only require Olk) samples to solve k-way supervised task under conditional independence (CI). Under ACI (quantified by the norm of a certain partial covariance matrix), we show similar sample complexity improvements. We verify main Theorem (4.2) using simulations. We check that pretext task helps when CI is approximately satisfied in text domain, and demonstrate on a real-world image dataset that a pretext task-based linear model outperforms or is comparable to many baselines.
1.1 RELATED WORK
Self-supervised learning (SSL) methods in practice: There has been a flurry of self-supervised
methods lately. One class of methods reconstruct images from corrupted or incomplete versions of
it, like denoising auto-encoders (Vincent et al. 2008), image inpainting (Pathak et al.) 2016), and
split-brain autoencoder (Zhang al. (017). Pretext tasks also created using visual common sense, including predicting rotation angle (Giaris et al. 2018), relative patch position (Doersch
let al. 22155) recovering color channels (Zhang et al. 2016). solving jigsaw puzzle games (Noroozi
& Favaro 2016), and discriminating images created from distortion (Dosovitskiy et al.] (013).. We
refer the above procedures as reconstruction- based SSL. Another popular paradigm contrastive
learning (Chen et al., 2020b/c). c). The idea is to learn representations that bring similar data points
closer while pushing randomly selected points further away (Wang Gupta 2015 Logeswaran &
Lee 2018 Arora et al. 2019) or to maximize a contrastive- based mutual information lower bound
between different views (Hjelm et al., 2018 Oord et al., 2018 Tian et al. 2019), A popular approach
for text domain is based on language modeling where models like BERT and GPT create auxiliary tasks for next word predictions (Devlin et al. 2018 Radford et al. 2018). The natural ordering or
topology of data is also exploited in video- based (Wei et al. 2018 Misra et al. 2016; Fernando (et al., 2017). graph- based ( (Yang et al., 2020 Hu et al. 2019) or map-based (Zhang et al.] 2019)
self-supervised learning. For instance, the pretext task is to determine the correct temporal order for video frames as in (Misra et al., 2016).
Theory for self-supervised learning: Our work initiates some theoretical understanding on the reconstruction-basse SSL. Related to our work the recent theoretical analysis of contrastive learning. |Aroa et al.] (2019) shows guarantees for representations from contrastive learning on linear classification tasks using a class conditional independence assumption, but do not handle approximate conditional independence. Recently, Tosh et al. (2020a) show that contrastive learning representations can linearly recover any continuous functions of the underlying topic posterior under topic modeling assumption for text. While their assumption bears some similarity ours, the assumption of independent sampling of words that they exploit is strong and not generalizable to other domains like images. More recently, concurrent work by Tosh et al. (2020b) shows guarantees for contrastive learning, but not reconstruction-bass very similar to our CI assumption. (Wang & Isola 2020) theoretically studies contrastive learning on the hypersphere through intuitive properties like alignment and uniformity of representations; however there is no theoretical connection made to downstream tasks. There mutual information maximization view of contrastive learning. but (Tschannen et al. 2019) points out issues with it. Previous attempts to explain negative sampling (Mikolov et al. 2013) based methods use the theory of noise contrastive estimation (Gutmann & Hyvärinen 2010 Ma & Collins) 2018). However, guarantees are only asymptotic and not for downstream tasks. is also used in sufficient dimension reduction Fukumizu et al. (2009) 2004). CI and redundancy assumptions
SSL, with multi-view redundancy assumptions that
multiple views (Kakade based dimension
& Foster 2007] & Zhang 2007) are used to analyze a camonica-ccorelaan
reduction algorithm. Finally, (Alain & Bengio 2014 Vincent 2011) provide theoretical analysis for denoising auto-encoder.
1.2 OVERVIEW OF RESULTS:
Section 2 ilittroduces notation, setup, and the self-supervised learning procedure considered in this we analyze downstream sample complexity under CL. Section pressenssssssenss 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 theoretical findings are in Section 5
work. In Section 3
2

---

Under review as a conference paper at ICLR 2021
2 PRELIMINARY
2.1 NOTATION
We use lower case symbols (x) 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-integrale probability P is denoted by (P). We use standard O notation to hide universal factors and Ô to hide log factors. stands for E2-norm for vectors or Frobenius norm for matrices.
functions with
Linear conditional expectation. E | [ denotes the prediction of Y with linear regression:
E Y
a] W b", where W b' arg min B WX b
In other words, E [ [ denotes the best linear predictor of Y given X. We also note that E[y| = miny |=[ f( ] is the best predictor of Y given X.
(Partial) covariance matrix. For random variables X, Y. we denote xY to be covariance matrix of X and Y. For simplicity in most cases, we assume B[X] 0 and E[y] O; thus we do not distinguish E[XY] and Exy. The partial covariance matrix between X and Y given Z is:
E Σxyız covv (X X - (X -E = Exy Ex2 Zz
(1)
Sub-gaussian random vectors. A random vector X E Rd is sub-gaassian if for every fixed unit vector v E IRd, the variable X is pL-sub-gaussian, i.e., Efe (X-E[X]] S 02/22 (Vs RR)
2.2 SETUP AND METHODOLOGY
We denote by X₁ the input variable, X2 the target random variable for the pretext task, and Y the label for the downstream task, with X₁ E Xi C 1 X2 E A₂ C Rd2 and Y E y C IR* If y is finite with | = k, assume y C R$ is the one-hot encoding of the labels. X,, denotes the joint distribution over Xi X Nr x y. Px, Px, denote the corresponding marginal distributions. Our proposed self-supervised learning procedure is follows:
Step 1 (pretext task): Learn representation (xx)) through vi = arg min geN E x| g(Xx)) where H can be different for different settings that we will specify and diseuss later.
Step 2 (downstream task): Perform linear regression on with (xxx), i.e. ʃ (xx1 = (W*) (x())), where W + arg minw Ex,, |||Y W (x,))))))))))))))))))))())))(( Namely we learn f(-) = EY
Performance of the learned representation on the downstream task depends on the following quantities. Approximation error. We measure this for a learned representation & by learning a linear function on top of it for the downstream task. Denote (apx(t)) (w) = minw (X]] - W X, Il?), where ("( = E = æ1) is the optimal predictor for the task. This gives measure of how well v can do with when given infinite samples for the task.
Estimation error. We measure sample complexity of ab on the downstream task and assume access 722 i..d. samples (z) y ())),... (a (m(()) ("2))) drawn from Px,.. We express the n2 samples collectively as X.down Raaxdd Y E B and overload notation say ab( (x = [+<xx] [dd )]((((()))--- ... (a..--- (=(]")))]] E 1222xd, We perform linear regression on the learned representation v and are interested in the excess risk that measures generalization.
W + arg min
Y (XX))
ER = = (I)(()) W VTT(X)) (xx))
w
2n²
3 GUARANTEED RECOVERY WITH CONDITIONAL INDEPENDENCE
In this section, we focus the case when input X, and pretext target X₂ conditionally indepen- dent (CI) given the downstream label Y. While this is a strong assumption that is rarely satisfied in practice, it helps understand the role of CI with clean results and builds up our main results with
3

---

Under review as a conference paper at ICLR 2021
ACI with latent variables in Section 4 As warm-up, we show how CI helps when (X1, X2, Y) are jointly Gaussian to give us a flavor for the results to follow. We then analyze it for general random variables under two settings: (a) when the function class used for & is universal, (b) when &i is restricted to be a linear function of given features. For now we assume access to a large amount of unlabeled data
to learn the optimal v/" perfectly and this will be relaxed later in Section 4 The
general recipe for the results is as follows:
Find a closed-form expression for the optimal solution i² for the pretext task. 2. Use conditional independence to argue that Eapx (v)" is small.
Exploit the low rank structure of g5* to show small estimation error on downstream tasks.
Data assumption. Suppose Y (X) + N, where f = [ and hence E[N] = 0. We assume N is -s-uugaausian For simplicity, we assume non-degeneracy. Σx,x., Eyy are full rank.
3.1 WARM-UP: JOINTLY GAUSSIAN VARIABLES
We assume X1, X2, Y are jointly Gaussian, and the optimal regression functions are all linear, i.e., [[Y[X]] = [Y|]]X,] We also assume data is centered: E[X,] 0 and E[y] 0. Non-centered data can easily be handled by learning an intercept. All relationships between random variables can then be captured by the (partial) covariance matrix. Therefore is easy to quantify the CI property and establish the necessary and sufficient conditions that make X₂ reasonable pretext task.
Assumption 3.1. (Jointly Gaussian) X1, X2, Y are jointly Gaussian.
Assumption 3.2. (Conditional independence) X1 XY
Claim 3.1 (Closed-form solution). Under Assumption 3.7 the representation function and optimal prediction that minimize the population risk can be expressed as follows:
(a1))) RB_L X2 X1 ==1] Σx,x, X,,, 21
(2)
Our target ("(x)) E x1 = Eyxx xi 11
(3)
Our prediction for downstream task with representation oi will be: g()) := E 1 (116=(()) Recall from Equation| that the partial covariance matrix between X1 and X2 given Y is Xx,X, =
Ex,x, Ex -xx,y E X. This partial covariance matrix captures the correlation between X₃ and X2 given Y. For jointly Gaussian random variables, CI is equivalent to Σx, x, = 0. We first analyze the approximation error based on the property of this partial covariance matrix.
Lemma 3.2 (Approximation error). Under Assumption 3.7 3.2 if Ex,y y has rank k. (ape(v") 0.
Remark 3.1. Ex,y being full column rank implies that X| has rank k, i.e., X2 depends on all directions of and thus captures all directions of information of Y. This is a necessary assumption for X2 to be a reasonable pretext task for predicting Y. Caps (vp"(t/") = O means f is linear in a Therefore ub" selects d2 out of di features that are sufficient to predict Y.
Next consider the estimation error that characterizes the number of samples needed to learn prediction function f(x1 W (x1) that generalizes.
Theorem 3.3 (Estimation error). Fix failure probability ō E (0, 1). Under Assumption 3.2 if
n2 >>>>>>> k: log(1/8) (8)), excess risk of the learned predictor æ1 W th" (x11 on the target task satisfies
(Tr(Eyr ( + log(k/)))
Tr
ER (.) SS
n2
with probability at least 1
Here Σyyix, = Eyr Σyx, Ex1x, Ex,y captures the noise level and the covariance matrix of tespeche residual term Y (Xi)= Σyx, xx N,xxx,, Xt. Compared to directly using X1 to predict Y, self-supervised learning reduces the sample complexity from Ö(d1) to Ö(k). We generalize these results even when only a weaker form of CI holds.
Assumption 3.3 (Conditional independence given latent variables). There exists some latent variable Z E m such that X, 1 X2 V, and Σx,8 of rank k + m, where Y [Y, Z).
4

---

Under review as a conference paper at ICLR 2021
This assumption lets introduce some reasonable latent variables that capture the information between X1 and X2 apart from Y. Σx,y being full rank says that all directions Y are needed to predict X2, and therefore Z is not redundant. For instance, when Z = X1, the assumption is trivially true but not the minimal latent information we want to add. Note it implicitly requires d2 2 k + m.
Corollary 3.4. Under Assumption 3.1 3.3 the approximation error Caps (15" is O.
Under CI with latent variable, generalize Theorem 3.3 by replacing by k + m.
3.2 GENERAL RANDOM VARIABLES
Next we move on to general setting where the variables need not be Gaussian.
Assumption 3.4. Let X, E R E R be random variables from some unknown distribution. Let label Y E y be a discrete random variable with k - d2. We assume conditional independence: X2_LX2\Y.
Here Y can be interpreted as the multi-class labels where k 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 since could be arbitrarily encoded but the results only depend on k and the variance of Y (conditional on the input X1).
Universal function class. Suppose we learn the optimal e³* among all measurable functions The optimal function vh in this case is naturally given by conditional expectation: (3x))) [x X1 21]. We now show that CI implies that 3² is good for downstream tasks, which is not apriori clear.
Lemma 3.5 (Approximation error). Suppose random variables X1, X2. Y satisfy Assumption 3.4 and matrix A E Xx22 with Ay. Y y) is of rank k DV. Then Eapr((") 0.
This tells us that although f could be nonlinear in I1. it is guaranteed to be linear in 30 (x1)). Note that Y does not have to be linear in X2. We provide this simple example for better understanding:
Example 3.1. Let Y E {-1,1] be binary labels, and X1, X2 be 2- -mixture Gaussian random variables with X1 ~ NNY 1, I), X2 ~ ~N(Yps I). In this example, X, X2\Y. Although f
[X]] is not linear, EE [6]] linear: (xx1) -PY 1|X1 = x ) P(Y =1|XX
2 21) and (x1) = P(Y = 1|X1 = xx)) P(Y = -| = 2) = μuz 20 (211///lll))
Given that 36 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 vi" (X1) to ignore scaling factors.
Assumption 3.5. We assume the whitened variable U := -/ 1/11))(()))) is a a -ubbaauussi random variable, where Σg = Elv((( (X)))))))
We note that all bounded random variables satisfy sub- sub-gaussian property.
Theorem 3.6 (General conditional independence). Fix a failure probability ö (0, 1), under the
same assumption as Lemma 3.5land and Assumption 3.5 for 2b", afditioon >> p* (k + log(1/5)),
then the excess risk of the learned predictor æι W 2b5 (x11) the downstream task satsifies:
1: log(k/)) 0²
ER [W]
0
122
Function class induced by feature maps. Given feature map Φ1 Xi D1, consider the function class Hi { 21 - d2 B 8 E Rd2xD, v(()) = B
Claim 3.7 (Closed form solution). The optimal function in H is 1/ (m)) = Σx D-1 b Lt. where Σx,e1 = (x)) and Eg,g, := Ed, (X,))
We again show the benefit of CI, this time only comparing the performance of / to the original features Φ1. Since e is linear in Φ1. it cannot have smaller approximation error than Φ1. However CI will ensure that e² has the same approximation emror as Φj and enjoys much better sample complexity.
5

---

Under review as a conference paper at ICLR 2021
Lemma 3.8 (Approximation error). If Assumption 3.4 satisfied, and the matrix A E RDxx with yg.: = _|X2|Y = y] is of rank k = (3). Then Capx( Eapx (01).
We additionally need an assumption on the residual a(x)) = B = 21) (Y
Assumption 3.6. (Bounded approx. error; Condition in Hsu et al. (012))) We have almost surely
Σ 1/2 01 &1 (X)) IF S bovk
Theorem 3.9. (CI with approximation error) Fix a failure probability 8 E (0.1), under the same
assumption as Lemma 3.8 Assumption 3.5 for 2/5 and Assumption 3.6 if 3 p* + log(1 (1))),
then the excess risk of the learned predictor σ1 - W ()²) on the downstream task satisfies:
ER [W] S Cape (01)+ + k log lo/(k/))
(
n22
Theorem 3.9 is also true with Assumption 3.3 instead of exact CI, if we replace k by kmm. Therefore with SSL, the requirement of labels is reduced from complexity for H to O(k) ( or (km)).
Remark 3.2. We note that since X₃ L2 ensures X1 for any deterministic function could replace X2 by (x2) and all results hold. Therefore we could replace X2 with h(X2) in our algorithm especially when d2 < km.
BEYOND CONDITIONAL INDEPENDENCE
In the previous section, we focused on the case where exact CI is satisfied. A weaker but more practical assumption is that Y captures some portion of the dependence between X1 and X₂ but not all. warm-up result with jointly- variables is defered Appendix [CTT] where ACI quantified by the partial covariance matrix. In the section below, we generalize the result from linear function space to arbitrary function space, and introduce the appropriate quantities to measure ACI.
4.1 LEARNABILITY WITH GENERAL FUNCTION SPACE
We state the main result with finite samples for both pretext task and downstream task to achieve good
generalization. Let X = [z] (1.pre
I (n) TTelt
E R xd1 and X₂ = [x] ... 22 (" e
Raixda be the training data from pretext task, where (a (i.pre) (z=().re)) 222 (i) is sampled from Xx,x,- We consider two types of function spaces: H E {H1, HuJ. Recall H, {vb X2 - B3 e Rd2x> Pj, (x1)) =
is induced by feature map Φ1 : X2 + R1. H. is a function space with universal approximation power (e.g. deep networks) that ensures 3 [X[2||11] E Hy, We learn representation from H by using n1 samples: v ;= arg min SEN6' ni
1 || fXx"") For
downstream tasks we similarly define X-dlown Ruaxd, Y E = d and learn a linear classifier trained on vi( ddown):
1 ||Y
W + arg mii
W/ ER (W) = Ex, (I W (()))
W
2n12
Here fa [Y ( (X1)) when H. Hi and fix f for 7 Hu. Assumption 4.1 (Correlation between X₂ and Y. 2). Suppose there exists latent variable Z e | = m that ensures ΣøgX, is full column rank and | I D' X200 llz 1/8, where At is pseudo-inverse, and dy is the one-hot embedding for Y = [Y, Z].
Definition 4.1 (Approximate conditional independence with function space H).
For H. = H4, define EcI = 8. Es, X2ldg ll..
1/2
2. For H = Hy, define 22 = Ex B - By [[,,1
Exact CI for both cases ensures 6cr = 0. We present a unified analysis in the appendix that shows the cai for the second case same as the first case, with covariance operators instead of matrices.
dg k and Y (Y) (one-hot encoding) refers multi-class classification task, dg refers regression.

---

Under review as a conference paper at ICLR 2021
Linear function class
Linear function closs
and non linear funct class
and nonn non-linnar function class
0.0000
(KA
0.0330
Xg
MAU
0.0006
0.0004
0.0003
0.015
0,0000
2.00002
0.0022
0.0001
0.0003
0.0000
0.2
0.4
0.5
0.8
0.2
0.3
0.4
0.
(b)
(d)
Figure/ I: Left two: how MSE scales with & (the dimension of Y) and ссi (ACI with the linear function class. Right two: how MSE scales with & and with 1 and non-linear function class. Mean of 30 trials are shown in solid line and one standard error is shown by shadow.
When H Hus the residual term Y subgaussian. When we use non-universal features Φ1, B fi, (X1) may not be mean zero.
E[ is mean zero and assumed be a²-
We thus introduce the standard assumption on == fi. x 1 (0) (X1)):
Assumption 4.2. (Bounded approximation error (Hsu et al. 2012 There exists a universal constant by. such that 1> Φ1 (x)()))((1)))) S V almost surely.
Theorem 4.2. For fixed ò (0, 1), under Assumptions 4.1 4.2 for & and v/= and 3.5 for non- universal feature maps, if 11, 722 >> pd(22 + log 1/5), and we learn the pretext tasks such that: E (X)))X)) 4/" (X1)ll? S 2me Then the generalization error for downstream task with probability 1 8 is:
ER WW) 0 22 + +og(d2/0))
ECI
pree
(4)
g2
ga
We defer the proof to the appendix. The proof technique is similar to that of Section 3 The difference now our (xX (down)) " will be approximately low rank matrix (low rank + small norm), where the low rank part is the high-signal features that implicitly comes from Y, Z that will be useful for downstream. The remaining part comes from <ạı and Cpre- Again by selecting the top km (dimension of (g) features we could further improve the sample complexity:
Remark 4.1. By applying PCA on o X down and keeping the top km principal components only,
can improve the bound in Theorem 4.2
km + log(km/88
2
2 +
ER W) 0
(5)
n22
82
g2
We take closer look the different sources of errors in (5) 1) the noise term Y (X(i with noise level o2: 2) ECI that measures the approximate CI; and 3) Epre the eгтor from not learning the pretext task exactly. The first is optimal setting ignoring log factors as we do linear regression on mk-ddimensional features. The second and third term are non-redueible due to the fact that f is not exactly linear in d while we use important to fine-tune when we have sufficient downtream labeled data. We leave this as future work.
fixed feature and learn linear function on it. Therefore
Compared to traditional supervised learning, learning fü requires sample complexity scaling with the (Rademacher/Gauussin) complexity of H (see e.g. Bartlett & Mendelson (2002): ; (Shalev-Shwarz/ Ben-David 2014)), ) which very large for complicated models such as deep networks.
In Section D we consider similar result for cross-entropy loss.
5 EXPERIMENTS
In this section, we empirically verify claim that SSL performs well when ACI satisfied.

---

Under review as a conference paper at ICLR 2021
beg-shwards
0.55
4g leareed uding SSt
0.00
2.0
Ag Hoarned ss bSt tie
0.50
2.40
of wordd
0.0
Ag/tri loored using 5S7 Ap, lourred using 5ST
5:55
50
328
203
250
302
110
35.0
300
Figure 2: Performance on SST of baseline @1 (z1), ), i.e. bag-of-words, and learned (b(x1) for the two settings. Left: Classification accuracy, Right: Regression MSE.
Simulations. With synthetic data, we verify how excess risk (ER) scales with the cardinality/feature dimension of y (k), and ACI (ccs in Definition 4. We consider a mixture of Gaussian data and conduct experiments with both linear function space (H₁ with Φ1 identity map) and universal function space H.. We sample the label Y uniformly from {1, k}. For i-th class, the centers MIi IRd and u22 E Rd are uniformly sampled from [0, 10). Given Y i, a E [0, 1]. let X1 ~ ((Is: I), X₂ ~ N(p2, I), and X₂ = (1 a) + ax,, Therefore a a correlation coefficient: = 0 ensures X2 being CI with X1 given Y and when 1, X2 fully depends on X1- (if d1 # d2, we append zeros or truncate to fit accordingly).
We first conduct experiments with linear function class. We learn linear representation & with n1 samples and the linear prediction of from e with n2 samples. We set d₃ = 50, d2 = 40, 71 = 4000, n2 1000 and ER is measured with Mean Squared Error (MSE). As shown in Figure [b)()), the MSE of learning with t ((1) scales linearly with & as indicated in Theorem 3.9 and
scales linearly with EC1 associated with linear function class as indicated in Theorem 4.2 Next
move on to general function class, i.e., v = [1] with a closed form solution (see example 3.1). We use the same parameter settings as above. For baseline method, we use kernel linear regression predict Y using X₁ (we use RBF kernel which also has universal approximation power). As shown Figure (igure[))cd) (d), the phenomenon is the same as what we observe the linear function class setting, and hence they respectively verify Theorem 3.6 and Theorem 4.2 with Hy.
NLP task. We look at the setting where both X1 and X are the set of sentences and perform experiments by enforcing CI with and without latent variables. The downstream task is sentiment analysis with the Stanford Sentiment Treebank (SST) dataset (Socher et al.) (013), where inputs are movie reviews and the label set Y/ is +=1) We use the representation class Hi, with features é1 being the bag-of-words representation (D) = 13848). For X₂ we use a d2 = 300 dimensional embedding of the sentence, that the mean of word vectors (random gaussians) for the words in the sentence. For SSL data we consider 2 settings, (a) enforce CI with the labels ) (b) enforce CI with extra latent variables, for which we use fine-grained version of SST with label set ) {1, 2, 4, 5 We test the learned & on SST binary task with linear regression and linear classification; results are presented in Figure 2 We observe that in both settings 1 outperforms Φ1, especially in the small mall-sample--ize regime. Also exact CI is better than CI with extra latent variables, as suggested by theory.
6 CONCLUSION
In this work we theoretically quantify how an approximate conditional independence assumption that connects pretext and downstream task data distributions can give sample complexity benefits of self-supervised learning 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.
Ratings (1, 2) correspond to y -1 and (4,5) correspond y
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Guillaume Alain and Yoshua Bengio. What regularized auto-encoders learn from the data data-generating distribution. The Journal of Machine Learning Research, 15(1):3563-3353 2014.
Rie Kubota Ando and Tong Zhang. Two-view feature generation model for semi semi-supervised learning. In Proceedings of the 24th international conference on Machine learning, pp. 25-32, 2007.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Charles R Baker. Joint measures and cross-covariance operators. Transactions of the American Mathematical Sociery, 186:273-289, 1973.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-945, 1993.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang, Unlabeled data improves adversarial robustness. In Advances Neural Information Processing Systems, pp. 11190-11201, 2019.
Tianlong Chen, Sijia Liu. Shiyu Chang, Yu Cheng, Lisa Amini, and Zhangyang Wang. Adversarial robustness: From self-supervised pre-training to fine-tuning, arXiv preprint 200:::200..28662 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint w:Xiv:2002.05709 2020b.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self-supervised models are strong semi-supervised learners. arXiv preprint arXiv:2006. 10029, 2020c.
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: / 1810004805 2018.
Carl Doersch, Abhinav Gupta, and Alexei A Efros. Unsupervised visual representation learning by context prediction. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1422-1430, 2015.
Alexey Dosovitskiy, Philipp Fischer, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with exemplar convolutional neural networks. IEEE transactions on pattern analysis and machine intelligence, 38(9) 2015.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint XiX.:220002200444... 2020.
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, pp. 3636-3645, 2017.
Kenji Fukumizu, Francis R Bach, and Michael Jordan. Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces. Journal of Machine Learning Research, 5(Jan): 73-99, 2004.
Kenji Fukumizu, Francis R Bach, Michael Jordan, et al. Kernel dimension reduction in regression. The Annals of Statistics, 37(4):181-1195, 2009.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv: 1803.07788 2018.

---

Under review as a conference paper at ICLR 2021
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 Computer Vision Workshops. pp. 2015.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-sshmidd norms. In International conference on algorithmic learning theory, pp. 63-77. Springer, 2005.
David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):1548-1666 2011.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.
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, 2016.
Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self-supervised learning can improve model robustness and uncertainty. In Advances in Neural Information Processing Systems, pp. 15637-15648, 2019.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie Marchilnar,,,,,n,, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 1808.06670, 2018.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference learning theory, pp. 2012
2012.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint ar0iv: 12265, 2019.
Tzee-Ming Huang. Testing conditional independence using maximal nonlinear conditional correlation.
The Annals of Statistics, 38(4):2047-2091, 2010.
Eric Jang, Coline Devin, Vincent Vanhoucke, and Sergey Levine. Grasp2vec: Learning object representations from self-supervised grasping. arXiv preprint (at:::18110666. 2018.
Longlong Jing and Yingli Tian. Self-supervised visual feature learning with deep neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Sham M Kakade and Dean P Foster. Multi-view regression via canonical correlation analysis. In International Conference on Computational Learning Theory, pp. 82-96. Springer, 2007.
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self supe-supe visual representa- tion learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 1920-1929, 2019.
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representa- tions. In Proceedings of the International Conference on Learning Representations, 2018.
Zhuang Ma and Michael Collins. Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing. 2018.
Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kemelss. Journal of Machine Learning Research, (6Dec):2551-2666 2006.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, 2013.
10

---

Under review as a conference paper at ICLR 2021
Ishan Misra, C Lawrence Zitnick, and Martial Hebert. Shuffle and learn: unsupervised learning using temporal order verification. In European Conference on Computer Vision, pp. 527-544. Springer, 2016.
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European Conference on Computer Vision, pp. 69-84. Springer, 2016.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: 2018.
Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2536-2544, 2016.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. URL https://s3-us-weet amazonaws. com/openai- aasstss/reearrchooeeeee http:///waaaaoooee//uou/uuueenrr
understanding paper. pdf. 2018.
Michael Reed. Methods of modern mathematical physics: Functional analysis. Elsevier, 2012.
Mark Rudelson, Roman Vershynin, et al. Hanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing. 2013.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. arXiv preprint 1rXiv:1906.0584, 2019.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv preprint arXiv:2003.02234, 2020a.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. arXiv preprint arXiv:2008. 10150, 2020b.
Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. arXiv preprint arXiv: 1907. 13625, 2019.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural compula- fion,
2011.
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, pp. 1096-1103, 2008
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. arXiv preprini arXiv:2005.10244 2020.
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In Proceedings of the IEEE International Conference on Computer Vision, 2015.
Donglai Wei, Joseph J Lim, Andrew Zisserman, and William Freeman. Learning and using the arrow of time. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 8052-8060, 2018.
Han Yang, Xiao Yan, Xinyan Dai, and James Cheng. Self-enhanced gnn: Improving graph neural networks using model outputs. arXiv preprint axXiv:2002.075/8. 2020.
Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In European conference on computer vision, pp. 649-666. Springer, 2016.
11

---

Under review as a conference paper at ICLR 2021
Richard Zhang, Phillip Isola, and Alexei A Efros. Split-brain autoencoders: Unsupervised learning by cross-channel prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1058-1067, 2017.
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, pp. 11084-11094, 2019.
12

---

Under review as a conference paper at ICLR 2021
A SOME USEFUL FACTS
A.1 RELATION OF INVERSE COVARIANCE MATRIX AND PARTIAL CORRELATION
For covariance matrix of joint distribution for variables X, Y, the covariance matrix is
Ex,x, Ex Σyx,
Ex,X, Ex,y Σxy Σyy
Exx Σxx
Exy Eyy
Ex,Xa Σx,y
Its inverse matrix Σ-1 satisfies
A
p]
Σ
E
p
B
Here A-1 Σxx= ExyEvy Eyx = cov(X - = ExxY, the partial covariance matrix of X given Y.
A.2 RELATION TO CONDITIONAL INDEPENDENCE
Proof of Lemma C.5
Fact A.1. When X, LX the partial covariance between X1, X2 given Y is O:
Xx, =co((x - (2 X2 - (x2/))
=Xxx, Ex,y Dy Exx, = 0.
The derivation comes from the following:
Lemma A.I (Conditional independence (Adapted from Huang (0100)). For random variables X1, X2 and random variable Y with finite values, conditional independence Xi YY is equiva- lent to:
(xx(()))(X2)) O.
sup
FEN..EEN
Here N; = (f: :f.:Rdd + R: EI = 0), 1,2.
Y b] [ with one-hot encoding of discrete variable Y. Therefore for any feature map also get that conditional independence ensures:
Notice for arbitrary function f.
(x))) : covv( - (x) -
(o) (X2)),)))
Here कi (X1) = 01 (X,) Elói (X,) , (Y)] ] is mean zero given Y, and vice versa for (X2). This
thus finishes the proof for Lemma C.5
A.3 TECHNICAL FACTS FOR MATRIX CONCENTRATION
We include this covariance concentration result that is adapted from Claim A.2 in Du et al. Claim A.2 (covariance concentration for gaussian variables), Let X [x1, x2, ..n] Raxd where each v; ~ NO, xx). Suppose >> + log(1/0) for â E (0, Then for any given matrix B E Rdxm that is of rank l and is independent of X, with probability at least 10 over X we have
2020
0.9B U B - E,
And we will also use Claim A.2 from Du et al. (2020) for concentrating subgaussian random variable. Claim A.3 (covariance concentration for subgaussian variables). Let X = [x1, Z2, ... ....' E Baa where each I4 (0, Ex). Suppose n > p* + log(1/8)) for ö E (0, 1). Then for any given matrix B E Rdxx that is of rank is and independent of X, with probability least 1 To over X we have
0.93 E
Ex
(8)
13

---

Under review as a conference paper at ICLR 2021
Claim A.4. Let Z Rank be matrix with row vectors sampled from i.i.d Gaussian distribution (O, Σz). Let P E IR be a fixed projection onto a space of dimension Then with a fixed
8 E (0,1), have:
|P &
log(k/6)),
with probability at least
Proof of Claim A.4 Each 1-th column Z is an n-dim vector that i.i.d sampled from Gaussian distribution N N(O, (0, mn).
|PZ
P
P 1|
t=1
zs Pz
Each term satisfy Σz P| 12 ~ (d), and therefore with probability at least 8' over Zt.
Eel 1 11 2 d log((/8").
Using union bound, take 8' 8/k and summing over E [k] we get:
PZ x Tr (d
Theorem A.5 Mhanson-Wrightt Inequality (Theorem 1.1 from Rudelson et al. (2013)). Let X = (X1,Xz X2, Xx,) TR. be random vector with independent components X1 which satisfy E [x,]
and [illl S. K. Let A be an n X n matrix. Then, for every t 2 0,
PXX AX] > t] 2exp
-emin
62
L K2|AA
K
Theorem A.6 (Vector Bernstein Inequality (Theorem 12 in Gross independent zero-mean vector-valued random variables. Let
(2011))) Let X1, Xm be
m
N
Xil12-
i=1
Then
-12
P[N 2 VV +1
exp
4V
where V == E|x,1 and & S V/(max I|x1l)).
Lemma A.7. Let E B be a matrix whose row vectors are n independent mean-zero (condi- tional P) ar-sub-Gaussian random vectors. With probability 1 5:
| S od (lg(d/))))/))
Proof of Lemma A.7 Write P UUT [ui,.. ua] where U is orthogonal matrix in gaxd
where UTU
3 = -UT 2
d = Σ
|| 2
1=1
= Σ
11
==1
14

---

Under review as a conference paper at ICLR 2021
where each 2; R being the i-th of Z is centered independent sub- nub-Gaussian random
vectors. To use vector Bernstein inequality, we let X := >i= X, with X, := Jj We have X; is
zero mean: [[X;] Elue; B[z, us:s Blu 0] O.
E |xx:12
BluBe zyl
Σ Euy [u]e Elll zz |1110
So²
Euyi [u]i]]
=
Therefore by vector Bernstein Inequality, with probability at least 1-8/d, ||x||| 5 v
log(d/0)
Then by taking union bound, we get that | Σ | 2 z o² log(d/8)) with probability 1 - 5.
Corollary A.8. Let Z RRnk be a matrix whose row vectors are a independent samples from centered (conditioned on P) multinomial probabilities (p1. P2....P (where pt could be different across each row). Let P E Rnxx be a projection onto space of dimension (that might be dependent with Z). Then we have
|2 & d log(d/6).
with probability 1 6.
B
OMITTED PROOFS WITH CONDITIONAL INDEPENDENCE
Proof of Lemma 3.2
COV Xx Y, X2 Y) = Ex,x, - Σx, Eyy Eyx, =0.
By plugging it into the expression of R.- [X22/X11), we get that
(xx1) == E' xı = Ex.x, Σ x, 21
Ex,y Σyy Ey Σ Xx,x, 21
= Ex,r E (Y
Therefore, long as Σx,y of rank k. it has left inverse matrix and we get: E = x1] Ery Therefore there's i approximation error in using & to predict Y.
Proof of Corollary 3.4
Let selector operator Sy be the mapping such that S,y Y, overload it as the matrix that ensure S, Ey x Σyx for any random variable X as well.
we get that there exists W such that [ = W E [X,]), just plugging in Sy we get that E [Y|X]] = (S, [x,
From Lemma 3.2
Proof of Theorem 3.3
Since N is mean zero, f*( = EIY TA
B m1 Σ Ex,y E2)) Let W Eyy Σt
15

---

Under review as a conference paper at ICLR 2021
First we have the basic inequality,
1
1
Y
(XI
S
|| 1
2mz
2nz
||
2n2
Therefore
(X,)) W (()) ((X))W)
-2(Pv(x,) N. (X.) +(X.)))
22 P(( N FF ( - (XI)
+ -
P (x.) NII
Sv Tr (yrrx,
) (k+ log k/8).
(from Claim A.4)
The last inequality is derived from Claim distribution (0,, Eyrix,)- Therefore
A.7 and the fact that each row of N follows gaussian
Tr(ErrIx, + log k/6)
| (x),) (XX W1 x
n2
n22
Next we need to concentrate
1/nX, x1 to Σ x. Suppose [X, (x22X1) = B X1, i.. d(I1) =
B 21, and o(X,) B. With Claim A.2 we have 1/no (X) ((Xi) 1/nB X B
satisfies:
0.9 Σx 3 (x,) (x)) 1 1.1B E
Therefore we also have:
E((W- W) (2x1)
- BWWW-WWIF
Tr(rrr,,, + log k//0)
(x
0.9ngk
712
B.1
OMITTED PROOF FOR GENERAL RANDOM VARIABLES
Proof of Lemma
3.5
Let the representation function & be defined as:
wb-) = E[X,|XX [ E| X Y]]x]]
(uses CT)
Σ P(Y = x1Xx, = =v
=x(( A,
where f Rdd + Ay satisfies f(z1), P(Y = y|X = x1), and A X satisfies Ay.: E[X₂ Y y). Here As denotes simplex of dimension d, which represents the discrete probability density over support of size d.
Let B Al yxda be the pseudoinverse of matrix A, and get BA I from our assumption that is of rank [/]. Therefore fx1 = (x)x),, Vrg. Next we have:
E|y|X:
x1 Σ P(Y y|Xi =1) x
=YS(m))
Here denote by Y RkX Y. y that spans the whole support V. Therefore let W YB will finish the proof.
16

---

Under review as a conference paper at ICLR 2021
Proof of Theorem 3.6
With Lemma 3.5
know Capx 0, and therefore W W*((X,) (X1)..
Next from basic inequality and the same proof as in Theorem 3.3 we have:
( +h X1
W|
Notice N is random noise matrix whose vectors independent samples from centered
distribution. Also we assumed ||||N|2|| Xi] I o², i.e. |||ND] S o². Also, Po(X,) is
projection dimension c. From Lemma A.7 we have:
(x) - + (1) sovet loge/6.
Next, with Claim A.3 we have when n2 >> p²(c log(1/6)), since W WW E gdxi,
0.9(W* -W) E (W W)
1
( W) Σ Ma -W) 11(( - E. - W)
112
And therefore we could easily conclude that:
E H - (x1)) So²0 c+ log(c/0)
n1-
B.2 OMITTED PROOF OF LINEAR MODEL WITH APPROXIMATION ERROR
First we note that Y fX)) N, where E[N]X,] but Y (A") X not necessarily mean zero, and this is where additional difficulty lies. Write approximation error term a(X,) := (X,) (A*)T X1, namely
Proof of Theorem 3.9
a(X,) + (A') X1 + N. Also, (At) X1 =
(W*) ((11) with conditional independence.
Second, with KKT condition on the training data, we know that x[x(X))x]] = 0.
Recall = arg minw Y
(xxx) W 1 We have the basic inequality,
P S __ - Y X1A'13
Y
(X
2n²
2n12
I - -
2n12
1
i...
W" +a(X1) + +(X,)
||((X)) N
2nz
2m2
Therefore
1 (6(X))W> W - W1
2n²
(a(X1) + N. ((X, W - W)
112
- (a
1
(a((x)) v/ W. -x(x)) (N, (X,) ((X;) W)
122
With Assumption 3.6 and by concentration 0 Σx, 3 111 we have
1/2 1/2 S 1.1bo Σ x,
(10)
/n²
17

---

Under review as a conference paper at ICLR 2021
Denote (x11)
B, where B -xx ExxExxxx Exixa is rank & under exact CI since Ex1X2
Ex,y My Ny We have
1
(a (a())), (xX1) ((X))W)
1/22
1
(a(X)), X,BW BV
n2
(Ex,
1/2
X (1a(X)). E/, (BW BW))
n22
S
f2 X1
BW - BW))
(from Ineq. (0
712
Back to Eqn.
9 get
|
W
W
W11
2m2
BWW
BWI F + - |Px N X (BW - BW)
X1
Vk
|Px
| BF
24
112
112
h + log k/6
|0
(xx W
(XX)) S
f/2
Finally, by concentration we transfer the result from empirical loss to excess risk and get:
1 + log(k/6)
n12
B.3 ARGUMENT ON DENOISING AUTO-ENCODER OR CONTEXT ENCODER
Remark B.1. We note that since X, ensures X, 2x(X2) for any deterministic function b. we could replace X2 by ((2)) and all results hold. Therefore practice, we could use h()((x)) )) instead of to (X1) (X)..ff for downstream task. Specifically with denoising auto-encoder or context encoder, one could think about h as the inverse of decoder D (h D-1) and use D D-116 */ E the encoder
function as the representation for downstream tasks, which is more commonly used in practice.
This section explains what we claim Remark B.I For context encoder, the reconstruction loss targets to find the encoder E* and decoder D* that achieve
min E ||2 - D(E( D
(1I)
where X₂ is the masked part we want to recover and X2 is the remainder.
we naively apply our theorem we should use D (-) as the representation, while in practice we instead use only the encoder part E*(-) (.) as the learned representation. We argue that our theory also support this practical usage if we view the problem differently. Consider the pretext task to predict (D*)-1(X)) instead of X2 directly, namely.
E +- arg min [ID)) - E(X))
(12)
E
and then we should indeed use E(Xi) the representation. On one hand, when X 12 it also satisfies -D') since (D*)- -1 a deterministic function of X2 and all our theory applies. On the other hand, the optimization II (12 give similar result. Let
E = arg min X2 - D*
E
18

---

Under review as a conference paper at ICLR 2021
and E | - D'((E(()))) S e, then with pretext task as in (12 have that:
(X()))))(X2))
-x)) ( (D')
<1I(D')~> E [x2 D"
where I= 10==1-1>--111 Up is the Lipschitz constant for function (1)*)-1 This is to say, practice, we optimize over (TT), and achieves good representation (Xx) such that Epre S LV and thus performs well for downstream tasks. (Recall Gpre is defined in Theorem 4.2 that measures how well we have learned the pretext task.)
C OMITTED PROOFS BEYOND CONDITIONAL INDEPENDENCE
C.I WARM-UP: JOINTLY GAUSSIAN VARIABLES
As before, for simplicity we assume all data is centered in this case. Assumption C.1 (Approximate Conditional Independent Given Latent Variables). Assume there exists some latent variable Z E IR' such that
1xx, 1/2 E Ex,x,Iiyle 1I S ecr,
X₁
(E) m yp Xxx,) = B>> 1 and E X of rank + m, where V = [Y, Zj.
When X1 is not exactly CI of X2 given Y and Z. the approximation error depends the norm of [X Xx,xx//P112. Let W be the solution from Equation
Theorem C.I. Under Assumption
C.I with constant ECr and B, then the excess risk satisfies
è 8
+r(EEr)),) d2 + log(d2/0)
ERg- [W] [|[| W
3 (X1) (X
112
Proof of Theorem C.1 Let f X xix, Eir be our target direction. Denote the
optimal representation matrix by ; (X1) A (where A = ===>> Ex Xx Ex,x,)
Next we will make use of the conditional covariance matrix:
Ex, = Exix, Σx, Dg Σyx;:
and plug in into the definition of V::
V = =x X,X, Ex, D E px, X, Xixx Ex,x,
=: + E.
E Xx and E = X1E X,x Ex,x, We analyze these two where L = X X,,,, X, Ex,8 8 Dx terms respectively.
For L, we note that span(V) V) Cspan( L): LXT
X,8 x = X1 x,x, Ex,y. By right multiplying
the selector matrix Sy we have: LET
x.y x Egy = X, Exir, i.e. LW V, where W
E x28
Ex Eyy. From our assumption that or (E) Evx,) = 3, we have W 12 S
Σ x Eyl2
1/3. (Or we could directly define / as o
[Σ] y
E Exx,)= = (l1))
By concentration, we have E = X,Σ
x, E 8 converges to X,
E Ex,x, Specifically, E-1/2 1/2
when > k + log 1/5. E < 1.1/
1/2 Σ X,
Exixs|elr S 1. (by using Lemma A.2 )
Together we have |EW [[ 2 ECI/3.
Let W arg minw Y V2 We note that Y N V N V EW where V is our target direction and N is random noise (each row of has covariance matrix E
denotes k-th singular value of A, and A is the pscudo-inverse of A.
19

---

Under review as a conference paper at ICLR 2021
From basic inequality, we have:
V 1 S VW Y = IN E.
= W| V - EE S2(V - V EW, N EW)
= V/ -EW S NI |EWI|
= | - vli = + (V + Vlg 1/8) Tr Tr(Ery)x,). (from Lemma A.7
<a Synz
+ (Vd2 + Vog
olgg//)) 1/8) Tr Tr(Envix))
B
(from Assumption
Next, by the same procedure that concentrates get
x X1 to Σx,x, with Claim A.2 we could easily
n12
E + +T(EEviix)) 8
d2 + log 1/8
ER[W] = E (X1)
f*))
n22
C.2 TECHNICAL FACTS
Lemma C.2 (Approximation Error of PCA). matrix A L + where rank <size of A and E and (A) = B.. Then we have
sin ((A, L)ll2 S Se/3.
Proof. We use Davis Kahan for this proof. First note that ||A L|l
|E S c. From Davis- Kahin
we get:
E
sin ((A, < (A)
(L)
|
(A)
Se/B.
C.3 MEASURING CONDITIONAL DEPENDENCE WITH CROSS- COVARIANCE OPERATOR
(Px)x) denotes the Hilbert space of square integrable function with respect to the measure Px, the marginal distribution of X. We are interested in some function class H. C (Px))) that is induced from some feature maps:
Definition C.3 (General and Universal feature Map). We denote feature map ó b : + F that maps from a compact input space X the feature space F. F is Hilbert space associated with inner product: (d(x),, (((x))). The associated function class is: Hz = {h: X -> RRAw E F, ((x) =
(w, ((x)), dx E X). We call & universal the induced Her is dense in I.2 (Px).
Linear model is special case when feature map ø Id is identity mapping and the inner product is over Euclidean space. A feature map with higher order polynomials correspondingly incorporate high order moments (Fukumizu et al. 2004 Gretton al. 2005). For discrete variable Y we overload as the one-hot embedding.
Remark C.1. For continuous data, any universal kernel like Gaussian kernel or RBF kernel induce the universal feature map that require (Micchelli et al. 2006). Two-layer neural network with infinite width also satisfy it. i.e., Vx X' Rd NNN (w b) (Brrrnn 1993).
8 R - R, NNN (w,b,
20

---

Under review as a conference paper at ICLR 2021
When there's ambiguity, we overload Φ1 as the random variable Φ1 (X1) over domain Fi, and H1 as the function class over X1. Next we characterize CI using the cross-covarianee operator.
Definition C.4 (Cross-covariance operator). For random variables X E X,Y E y with joint distribution P X x y IR, and associated feature mups On and by we denote by Ca.e. (X) @ 0 (Y) = Sxxx (x(x) & (y)d y), the (un-centered) cross-covariance operator. Similarly denote by Cxe, B[x & (, Fg +
To understand what Co.o, is, we note it is of the same shape (x( @ 0y(2) for each in- dividual N. V. can be viewed as a self-adjoint operator: Cosdy Fu Fz Co.o, 1xxy(0p (x)))) y). Vf E Fg- For any f Hr and g E Hy. satisfies: (f. Co.o,gHn, = =xx (xX)))))((() Baker 1973 Fukumizu et al. 2004). CI ensures Co Xalo, =
for arbitrary Φ1.92
Lemma C.5. With one-hot encoding map oy and arbitnary é1, X1 Y ensures:
Co1Xele, == Co, Coior C-1 Pyyby Co O.
(13)
more complete discussion of cross-covariance operator and CI can be found in (Fukumizu et al. 2004). Also, recall that operator C F, + Fa is Hilbert-Schmidt (HS) (Reed] 2012) if for complete orthonormal systems (CONSs) {& of F₂ and {n:} of Fg.. ||Cl = Σn (c, Cn.) < co. The Hilbert-Schmidt norm generalizes the Frohenius norm from matrices to operators, and we will later use ||Co, Xalø, || to quantify approximate CI.
We note that covariance operators (Fukumizu et al. 2009 2004 Baker 1973) are commonly used to capture conditional dependence of random variables. In this work, utilize the covariance operator to quantify the performance of the algorithm even when the algorithm is not a kernel method.
C.4 OMITTED PROOF IN GENERAL SETTING
Claim C.6. For feature maps Φn with universal property, we have:
== :x))):== =E[xx]X]]]] = [x2
=xxs0, Co (X1).
Our target (X = X = E YY [1)
-Cro, C_1 Φ1 (Xi).
For general feature maps, we instead have:
40 40 (X1) = arg min Ex, N2 1| - f(Xi)11
SEN
Cx,o, Coroh d1 (X1)-
Our target (X1) = arg min Ex,y Y I - -( fEH
=Cy $101 Φ1 (X1).
To prove Claim C.6 we show the following lemma:
Lemma C.7. Let Φ X - Fr be universal feature map, then for random variable E y we have:
E| = (x())
Proof of Lemma C.7 Denote by E = x (xx). Since & is dense X, there exists linear I2 such that Juex a ( f(-) a.e Therefore the result comes directly
operator a X
from the universal property of Φ.
Proof of Claim C.6
We want to show that for random variables Y,X, where X associated with a (X)).
universal feature map d.., we have [ (x, (x)) (x
21

---

Under review as a conference paper at ICLR 2021
First, from Lemma C.7 have that [[ = E (Y)()x)))) Next, write A : Fe - y as the linear operator that satisfies
[| A oz (X)
A' arg min Bllly Axx
Therefore from the stationary condition we have A Ex 8 thn (x)) Exv(Y & (x())), Or
namely we get A = Cy C simply from the definition of the cross-covariance operator C. L
Claim C.8. 1C Xalog lias Ex, B[X Ey -x =
Proof.
|| 1/2 01 C Xalda Iii
Px, (x1,
1x (2)1
X2dpæs
dpæ.
px. (x1)
Px, (x1)
X1 X2
Ex, |II B[22 [X]]
Ey [[X
C.5 OMITTED PROOF FOR MAIN RESULTS
We first prove a simpler version without approximation error.
Theorem C.9. For fixed 8 E (0, 1), under Assumption 4.1
3.5
if there is approximation error,
ie., there exists linear operator such that f (X1) = A 1). if n1, n2 > p² + log 1/6), and we learn the pretext tasks such that:
E [l - 3² (X S Epre
Then we are able to achieve generalization for downstream task with probability -- 5:
BlIlA (X1) - W T ((x)II Ol02 d2 + log d
Spre
+
}.
(14)
g2
g
112
Proof of Theorem C.9 We follow the similar procedure Theorem approximation eπror, we have f -fi, and the residual term N zero random variable with [[[[N]| x o² according to our data assumption in Section 3 N = ('X is the collected n2 samples of noise terms. We write Y E Rds For classification task, we have E i [k]] c R (i.e, d3 k) is one-hot encoded random variable. For regression problem, Y might be otherwise encoded. For instance, in the yearbook dataset, Y ranges from 1905 to 2013 and represents the years that the photos are taken. We want note that our result is general for both cases: the bound doesn't 't depend on d3. but only depends on the variance of N.
For the setting of no (X1) is a mean-
Let V/ L, E, V be defined as follows:
Let f (xppom))= = Sū. (Xdowa)= = oi Xdown (/own)CC ---CCoy be our target direction. Denote the optimal representation matrix by
10" : (X (low
ddow
c-1
oi Co
down ) C Coros Co2 Eggx, + (( Co,, CaiXalee
=: E,
where L 6 Co,, Cor C-1 1
0g Co, and E x(xxtown)))) Co1X11P- 0101
In this proof, we denote Sy as the matrix such that Sy = Y. Specifically, Y of dimension dg. Sy is of size da 2) Therefore Sy EΦ,a Ey for any random variable A.
22

---

Under review as a conference paper at ICLR 2021
Therefore, similarly have:
LE Ly0, 20y0n Sy LE X2dg X2dg DadY LW V
where W = Exeo Egpy satisfies WW 1/B. Therefore span(V) Cspan( L) since have assumed that Ex203 Eøgy to be full rank.
the other hand,
x cio Xa18 concentrates to C 1/2 $1 Con Xalóg- Specifically, when
n > + log 1/6. || F & 1.11Ic 6101 calxaloul & 1.1EcT (by using Lemma A.3 ). Together we have
EW & E./3.
We also introduce the error from not learning 1h exactly: E 4- = 2 X down
3 (X down
With proper concentration and our assumption, we have that (|b((1)) 3 (X1)
S Epr and
down)
v down) I|? S (
Also, the noise term after projection satisfies V & d2 + log d2/óa as using Lemma Therefore v/ = V EF L E
A.7
Recall that W = arg minw (Iv down) W Y 1| And with exactly the same procedure as Theorem
also get that:
V VII <2
EW + 2|| E W + P.IV,,,,VEE. NI|
ECI + Epre
Zvn2
/ d2 + log(lz/) (2/
3
With the proper concentration we also get:
E +
mie
002 2dd + log(ds/8)
B||| W (XX)) 17, (X1))
12.2
Next we move on to the proof of our main result Theorem 4.2 where approximation error occurs.
Proof of Theorem 4.2 The proof is combination of Theorem 3.9 and Theorem C.9 We follow the
same notation as Theorem C.9 Now the only difference is that additional term a (ddww)) is included in Y:
Y = + f (xX down)
=N + v W + al (x down
-N + ( + E W + a a(X (owa)
-W + (N + E W + a X (dww)) ))
From re-arranging 2ng
1 Y
wW < 1 Y V
2nz
1
VWW W) (N + E a (X down )
V
N E W + down
(15)
2n1
2112
1
j(W - - < 1 (w(W -ww, N + Te + ((od)))))
(16)
2n1
23

---

Under review as a conference paper at ICLR 2021
Then with similar procedure as in the proof of Theorem 3.9 and write V as (( B, we have:
((W W), a (()m))
1/2
1
(B(W-
W), ( T (1
1/2
(c
B(W c) ( (((mnnn) Ta (o(X)
d2
| B(W - W)llF
12
712
d2
31.1
| ( ) - W
/n2
112
vd2
=1.1
|| [W W)l..
712
Therefore plugging back to
(16) we get:
1
(W
Will
(W
W).
E W + a (ow))
2mz
72
1
PN 1.1 vd2
(W
Will -
E W
2mz
2nl
2n
112
|| /WW
- fH. (X dodwn)
||
|EW||
-
(1.1V
d2 + E W|| + V + log(d2/6)))
2//12
Vn2
ECI + Spre d2 + log d2/6
VW
fi, [X x
n/12
112
Finally by concentrating
y to (Xi)(X)) ! we get:
E||l W (X,)) TT(,, - fi, (x=) d2 log d2/8
c + cp
g2
with probability 1 -
D THEORETICAL ANALYSIS FOR CLASSIFICATION TASKS
D.1 CLASSIFICATION TASKS
We now consider the benefit of learning vi from class Hi linear classification task for label set y = [k). The performance of classifier is measured using the standard logistic loss
Definition D.1. For a task with y [k)], classification loss for a predictor f : - R
ebu
ta(l) = Beleo (f(X)) Y)), where ling (Ú. v) log
Eyy eBuy
The loss for representation vb X1 + Rdd and linear classifier W E kx is denoted by Eoy (
We note that the function b I-Lipschitz in the first argument. The result will also hold for the hinge loss Ginng (ū. y) (1 Úy + max Dg + which is also I-Lipschitz, instead of llog-
We assume that the optimal regressor fit, for one-hot encoding also does well on linear classification.
Assumption D.I. The best regressor for 1-hot encodings in Hi does well on classification, i.e. ( S Cone-hot is small for some scalar 7.
Remark D.1. Note that if Ha is universal, then füt (z1) E|| æ1) and we know that fit. the Bayes-optimat predictor for binary classification. general one can potentially predict the label by looking at arg max 8ūc, (x1)s. The scalar 7 captures the margin in the predictor f
24

---

Under review as a conference paper at ICLR 2021
We now show that using the classifier W obtained from linear regression one-hot encoding with learned representations & will also be good linear classification. The proof is in Section D
Theorem D.2. For fixed 8 E (0, 1), under the same setting as Theorem 4.2 and Assumption we have:
D.
Eas (wWe) so (7// (x/0= d2 + log d2/0
e²
Gr Ba
g2
+
+
cone-hots
with probability
Proof of Theorem
D.2 We simply follow the following sequence of steps
fai ( 1b ElLwE () (X)) v))
(a) E blog (r (X1), Y) + + - Fi. (Xi)
(b) Eome-hot + 7V
E - (Xi)
Cone-hot V
ER [W]
where (a) follows because bog is 1-Lipschitz and (b) follows from Assumption D.1 and Jensen's
inequality. Plugging Theorem 4.2 completes the proof.
E FOUR DIFFERENT WAYS TO USE CI
In this section we propose four different ways use conditional independence to prove zero approxi- mation error, i.c.,
Claim E.1 (informal). When conditional independence is satisfied: X; Lx, Y, and some non- degeneracy is satisfied, there exists some matrix W such that x W E [1)
We note that for simplicity, most of the results presented for the jointly Gaussian case, where everything could be captured by linear conditional expectation E [Y[Y]X]] or the covariance matri- ces. When generalizing the results for other random variables, we note just replace X1, X2, Y by Φ1 (X1), (Y)) will suffice the same arguments.
E. INVERSE COVARIANCE MATRIX
Write Σ as the covariance matrix for the joint distribution Px,x2y-
Σ
Σ
xx
Exy
Σ-
A
Σ vY
Σyy
B
where E (d) +d2) p E R(d (d11+)2)xx xk
B
E kkk
Furthermore
A1
A12
A
P2
Az1
A22
for P: E geiikii=1. and Aij E Rdixds for i.j (1,2).
Claim E.2. When conditional independence is satisfied, A is block diagonal matrix, i.e., A12 and A21 are zero matrices.
Lemma E.3. We have the following
|[X]|Xa] (A11 -01P1) (p1p2 A12)
(17)
X X1] = (Azz -22p ) (p201
X1
(18)
E
E||| - X1 + po X2)
(19)
25

---

Under review as a conference paper at ICLR 2021
where P. PB for i (1,2). Also,
(A11 - -1pi)-'pPp11
Ani P1P2
1 pl A11 P1
(A22 p2p2) p2p1
Ar2 P2P1
1 P/2 A22 P2
Proof. We know that = Σ12 X2 and E [X = Σ2 11 21, where
Σ 1
Exx=
E1
Σ2
First using ΣΣー1 =,, I, get the following identities
AxxA+ Exyp" =
(20)
Exy + Eyyp² =0
(21)
Exxp + Exy
(22)
Σxyp + Bry I
(23)
From Equation 22
we get that Exy = ExxpB 11 and plugging this into Equation 20 we get
Σxx ExxpB-1 =
Exx = (A 1 1ppBBB11 -pB-1p
(A - -pp -p-)-1
Σ Σ1
12 Σga
A11 - P.0
A12 P1p2
A21 P2P1
Az2
P2p2
We now make use of the following expression for inverse a matrix that uses Schur complement:
M M/a 5 ya 3 is the Schur complement of for M defined below
If M = a 3
then, M- a + a 3 /a) ya
-a -a - (MMa))
?
8
-(M /a) y0
(M/a)-1
For M = (A- - po ). we have that Xxx = M -1 and thus
Eng a 3 /a) ((M)) (MM -1--1
-1
(AA1 ) A12)
This proves Equation
177 and similarly Equation (18) can be proved.
For Equation
19 we know that [ = (X1, = Ey x Exxxx By using
Equation
22 we get Σxy ExxpB- and thus
| (X1, BB- Σxx E
=-B-lp B B + P2 X2)
= -B Xi p
For the second part, we will use the fact that (I - ab ) = +
ab -a- Thus
I-aTo
(A11 piPT)~ 21p2 (I A |1 M18i
A T
1
= =(I+ + 1- p1
A
A
A
P1
1
- +
PIP1 A
11p1
P1 A
11 P1
Pi PIA
AA
p1P2)
1 P.
A P1
P A 11 P1
A T (1+
p A P1
1
A PIPT
1 PT A P1
26

---

Under review as a conference paper at ICLR 2021
The other statement can be proved similarly.
Claim E.4.
E [11] (Az2 - - X1. X - 1/2p2 1|
Therefore [[] is in the same direction as B[X2|Xi))
E.2 CLOSED FORM OF LINEAR CONDITIONAL EXPECTATION
Refer to Claim 3.1 and proof of Lemma 3.2
As this is the simplest proof we used in our paper.
E.3 FROM LAW OF ITERATED EXPECTATION
| = -B"BBBBBB Y]
Σx,x, Σxx,
Ex,r Eyy
X1 Y
=E [xxxx Ex,r|
X
AX + BE
Using block matrix inverse,
A = (Exxx, - Ex,y Exr Exx, (Exx. Eyx gdxdd
Exixi (Ex.xi)) B ExarIx, (Eyrix)) Rdxy
Therefore in general (without conditional independence assumption) our learned representation will be (1x)) Ar B (x1), where f*()) == {1]
It's easy to see that to learn f from representation th we need A have some good property, such as light tail in eigenspace, and B needs to be full rank in its column space.
Notice the case of conditional independence, Xx,X, O, and Therefore we could easily learn f from vb if X2 has enough information of Y such that Σx,yix, is of the same rank as dimension of Y.
E.4 FROM X Y| Y
Proof. Let the representation function v be defined as follows, and let law of iterated expectation:
wτ-) = | B X1, Y]
= 2EBB[X2|Y]JA
(uses CI)
= = P(Y = E[, = -1]
=:f(X))TA.
where f Rd + Ay satisfies f(x1) P(Y y| x1), and A g'xd satisfies Ay.: E[X, Y = y). Here Ag denotes simplex of dimension d, which represents the discrete probability density over support of size d.
Let B = At E Yx be the pseudoinverse of matrix A, and we get BA = I from our assumption that of rank ( Therefore f(x1) = (x)(z)), Vr, Next have:
E| = 01 = Σ P(Y = v/Xi 21) x
-(f(z))
-(YB). +
27

---

Under review as a conference paper at ICLR 2021
Here denote by Y R Y., y that spans the whole support V. Therefore let W YB will finish the proof.
28

---

Under review as a conference paper at ICLR 2021
0.0050
0.0034
((X1 (n) 1000)
v(Xi) (m. 1000)
0.0045
((xy (n, - 800)
0.0032
4XX,) (n;
0.0040
u(Xi (n, 600)
0.0030
90G)) (n, 600)
((X1 (0) 400)
0.0028
v(X1) (o. 100)
MSE
0.0035
X1
MSE
0.0026
0.0030
0.0024
0.0025
0.0022
0.0020
0.0020
20
40
80
100
0.01
0.02
0.03
0.04
0.05
0.06
number of samples
number samples
Figure 3: Left: MSE of using v to predict Y versus using X1 directly to predict Y. Using vi consistently outperforms using X₁. Right: MSE learned with different n The MSE scale with 1/nz as indicated by analysis. Simulations repeated 100 times, with the mean shown in solid line and one standard error shown in shadow.
(linwe)
550
(Inear)
X, (linar))
X1 (Inear)
(lines)
500
17
q(K;) (inear)
((K)) (lisear)
Voon Absoluta
16
(resnet18)
450
300
250
12
1000 1500
2000
2500
3000
1000 1500
2500
3000
Number labeled data
Number lobeled data
Figure 4: Left: Example the X₂ (in the red box of the 1st row), the X₁ (out of the red box of the 1st row), the input to the inpainting task (the second row), (XXi (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 the mean shown in solid line and one standard error shown in shadow.
F MORE ON THE EXPERIMENTS
In this section, we describe more experiment results.
Simulations. Following Theorem 4.2 we know that the Excessive Risk (ER) is also controlled by (1) the number of samples for the pretext task (n1), and (2) the number of samples for the downstream task (n2),, besides & and Egr as discussed in the main text. In this simulation, we enforce strict conditional independence, and explore how ER varies with nı and n2g. We generate the data the same way as in the main text, and keep to linear model. Hence z) is the linear model to predict X2 from X, given the pretext dataset. We use Mean Squared Error (MSE) as the metric, since it is the empirical version of the ER. As shown in Figure 3, vi consistently outperforms X, in predicting Y using a linear model learnt from the given downstream dataset, and ER does scale linearly with 1/ng, indicated by analysis.
0, h 2, d1 50 and d2 = 40 We restrict the function class
Computer Vision Task. We testify if learning from & is more effective than learning directly from X,, a realistic setting (without enforcing conditional independence). Specifically, we test on the Yearbook dataset (Ginosar et al. 2015). and try to predict the date when the portraits are taken (denoted as Yp), which ranges from 1905 to 2013. We resize all the portraits to 128 by 128. We crop out the center 64 by 64 pixels (the face), and treat it X2, and treat the outer rim X; as shown in Figure 4 Our task is to predict Yp. which the year when the portraits are taken, and the year ranges from 1905 2013. For v/ learn X2 from X, with standard image inpainting
29

---

Under review as a conference paper at ICLR 2021
1.2
7
Covariance conditian
L1-
Covariance condition gender Covariance
Mean Squared Etror
1.0-
5
0.9
(Xx) (linear) gender
4-
(X)
0.8
0.7
1-
0.6
800
1000
1200
Number labeled data
Top 10 elgen-values
Figure 5: Left: Mean Squared Error comparison of predicting gender and predicting date. Right: the spectrum comparison of covariance condition on gender and condition on date.
techniques (Pathak et al. 2016), and full set of training data (without labels). After that we fix the learned s and learn a linear model to predict Yn from vú using smaller set of data (with labels).
Besides linear model on X1, another strong baseline that we compare with is using ResNet18 (He)
al. 2016) to predict YD from X1. With the full set of training data, this model is able achieve Mean Absolute Difference of 6.89, close to what state-of-the-art can achieve GGiossar et al. 2015). ResNet18 has similar amount of parameters class. We show the MSE result as in Figure Learning from & more effective than learning from X; X2 directly, with linear model well as with ResNet18. Practitioner usually fine-tune v with the downstream task, which usually leads to more competitive performance (Pathak et al.) 2016).
generator, and hence roughly in the same function
Following the procedure, try to predict the gender Ya- We normalize the label (Ya, YD) unit variance, and confine ourself to linear function class. That is, instead of using a context encoder to impaint X2 from X1, we confine & to be linear function. As shown on the left of Figure the MSE
1/2 of predicting gender is higher than predicting dates. We find that | Σ XxIXa/Xa = 9.32,
while | Ex, l| = 8.15. Moreover, as shown on the right Figure conditioning on YD cancels out more spectrum than conditioning Yg. In this case, conjecture that, unlike Yp. YG does not capture much dependence between X1 and X2. And as result, ecr is larger, and the downstream performance is worse, we expected.
30


Reviews:
[{"review_id": "tsXGhnJ2IOd", "reviewer": "AnonReviewer5", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "__post-rebuttal__\nThe responses have been persuasive enough. I am raising my score, with an expectation that the authors will make additional textual revisions based on their responses to make it clear in the abstract and introduction that (1) authors only consider the \"reconstruction-based\" SSL, instead of SSL in general, and (2) address the discrepancy between the practice and the proposed framework. (I thought asking questions could make the authors revise the manuscript, but unfortunately that did not happen.)\n\n__summary of the paper__\nThe paper provides a mathematical framework to theoretically understand and quantify the benefit of self-supervision on the downstream tasks. The considered pipeline (which seems to be based on Arora et al. (2019)) is as follows. $X_1$ is the input variable, $X_2$ is the \"target\" random variable, and $Y$ is the label for the downstream task. Then, the learner solves two problems sequentially: (1) _pretext task:_ The learner looks for a representation $\\psi: \\mathcal{X}_1 \\to \\mathcal{X}_2$ such that $\\psi(X_1) \\approx X_2$. (2) _downstream task:_: The learner looks for a matrix $W$ such that $W^\\top \\psi(X_1) \\approx Y$. Based on this framework, the paper gives performance guarantees on the downstream task under various assumptions, e.g. unbounded sample for the pretext task or Gaussianity. The key underlying mechanism is what authors call the _approximate conditional independence._\n\n__Strengths__\n(1) The theoretical analyses appearing in the paper are concrete.\n(2) The manuscript overall is very easy to understand and comprehensive.\n\n__Weakness__\nThe biggest concern that I have is that the provided framework does not seem to incorporate most existing self-supervised learning paradigms. Although it is somewhat explicitly stated already in the paper that the discussion is confined to the **\"reconstruction-based self-supervised learning\"** instead of any self-supervised learning task, I still am not really sure if the provided framework covers those pretext tasks. Actually, the paper exemplifies the task of \"inpainting\" (Pathak et al. 2016) to motivate the theoretical framework. Here, $X_2$ is the cropped part of an image, $X_1$ is the remaining part, and $Y$ is the corresponding label. I am happy with how the framework handles the pretext task, but not with how it handles the downstream task. According to the framework, the learner aims to predict the label from the \"remainder of a cropped image,\" instead of the full image. While one can always imagine such an algorithm, I am not sure if this is what is typically done in self-supervision algorithms. The same may hold for image colorization tasks (which also motivates the framework). Actually, it seems to me that such discrepancy takes place because the paper did not want to step away too far from Arora et al. (2019), which is actually quite similar in spirit except that Arora et al. (2019) did not spell out \"approximate conditional independence.\"\n\nAlso, I am not sure if the framework is extendable enough to take care of other (perhaps more popular and well-performing) categories of self-supervision, such as rotation/jigsaw-based methods. If not, I think many statements and expressions appearing in the paper should be significantly down-toned, including the title of the paper.\n\n__nitpicks__\n(1) Although not absolutely mandatory, discussing the relationship to Bansal et al. (2020) may help the future readers.\n(2) In section 2, right before the paragraph **(Partial) covariance matrix,** the sentence \"We also note that $\\mathbb{E}[Y|X] = \\min_{f}\\mathbb{E}[\\|Y-f(X)\\|^2]$ is the best predictor of $Y$ given $X$\" does not make too much sense. Perhaps the authors meant argmin?\n(3) Is $X$ the random variable, or can it be a vector as well?\n(4) In section 2.2., I am not sure why the authors use the Frobenius norm in the definition of  $\\psi$. Shouldn't it be simply $\\ell_2$ norm, as $X_2$ seems to be a vector? Or are the authors already assuming a data matrix?\n\n\n[Bansal et al. 2020] For self-supervised learning, Rationality implies generalization, provably, arXiv 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "p923wcwgTMb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a mechanism based on approximate conditional independence (ACI) to explain why solving pretext tasks created from known information can learn representations that provably reduce downstream sample complexity, as a sufficient condition. In specific, they measure the downstream performance using the approximation error and estimation error, and establish their initial results under a strict condition -- conditional independence (CI) and linear function space in Section 3, then extend it to ACI and arbitrary function space in Section 4, resulting in the main contribution Theorem 4.2 that clearly quantifies the generalization error. The theorem is also verified in Section 5 using simulations on NLP tasks. \n\nOne concern is that, in terms of the theory for self-supervised learning, I am not sure how big is the proposed theorem contributes to the community, as there are works such as Tosh et al. (2020b) in contrastive learning also provide theoretical guarantees using assumptions similar to CI. So I would rather hear more comments from other reviewers.\n\nAnother point is that the authors spent around four pages to illustrate their results with lemmas and theorems, which is good. But for the benefit of a broader audience, I would suggest to include more intuitions and discussions at the beginning, include some proof steps and ideas only with limited but key lemmas and theorems, and move the rest of them into the appendix. For example, Section 3.1 is on jointly Gaussian variables and 3.2 is on general random variables, they are indeed different, but results are pretty same and kind of overlap with each other. I would suggest shrink them but add more discussions and intuitions for the audience. \n\nOverall, from my own point of view, the paper is clearly written and well-motivated. It addresses an important question that perfectly fits into the ICLR topics: what connection between pretext and downstream tasks ensures good representations? \n\n\n------\nUpdate after rebuttal\n\nThanks for the author's response. Combing the author's response (though the authors didn't upload new versions to address my comments -- include more intuitions and discussions) and other reviewer's comments and discussions. I suggested this paper being marginally above the acceptance threshold.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "i2IJns_QCwN", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\n  *  Summary of the paper.\n  The paper shows theoretical results to support the claim that (approximate) conditional independence is a good way to quantify the link between the downstream task and the pretext task in self-supervised learning. Doing so, the authors prove theoretical results showing that indeed self-supervised learning decrease the estimation error in a classification task when the downstream task and the pretext task are linked through conditional independence or the weaker approximate conditional independence showing that approximate conditional independence is a good quantification of the link that the downstream task and the pretext task must have in order for the self-supervised learning to be efficient. The authors also provide numerical illustrations.\n \n  * Strong points: theoretical guarantees in SSL (there are not a lot of those) while using approximate conditional independence which is more realistic than conditional independence.  The paper has some experiments that support its claim. The paper takes a gradual approach, first with jointly Gaussian variables and then with general (sub-Gaussian) random variables which helps the comprehension because at least in the Gaussian case, things are not so hard.\n   \n  * Weak points: Use of mean squared error for a classification task which negates most of the practical aspect of this paper. Not enough details in the proofs. The bounds are not optimal. The experiments are not reproducible and the presentation of those experiments is somewhat lacking. Overall problems with experiments.\n    \n  * Recommendation.\n    I vote to accept because this is one of the rare theoretical guarantees for SSL, the approximate conditional independence is very interesting as a way to quantify the link between downstream and pretext task and this gives more understanding on how to choose a pretext task in practice when doing SSL.\n\n\n  *  Questions:\n    * Why did you use MSE ? Why not Cross entropy for instance ?\n    * $Tr(\\Sigma_{YY})$ in Theorem 3.3 is of order k for instance in the case where $\\Sigma_{YY}$ is the identity matrix, the bound is $O(k^2)$ not $O(k)$, is it not? (contradiction with what you say in the text).\n\n\n  * Additional feedback.\n    * Please provide the minimax bound (i.e. optimal bound) in the \"not self-supervised\" context for us to compare with your bounds for self-supervised, below Theorem 3.3 you say that we gain from $O(d1)$ to $O(k)$ but you don't provide the bound that explain this $O(d1)$.\n    * Please include the results of the simulation study in the main text. In my opinion, a simulation study must firstly show that your method works as intended, a sanity check of sorts. You simulation study does not do this because we don't see the results of this study right away, it is hidden at the end of the appendix.\n    * Be careful, Theorem A.6 is only true for sub-Gaussian, please include this in the theorem, this is important in my opinion. \n    * Theorem A.6 can be improved, for now it is of order $\\sqrt{\\frac{Tr(\\Sigma)}{n}}(1+t)$ but it can be made of order \n$\\sqrt{\\frac{Tr(\\Sigma)}{n}}+\\sqrt{\\frac{||\\Sigma||_{op}t}{n}}.$\n  \n        The difference can be important when the dimension is large (for instance if Sigma is the identity matrix in $R^d$, $Tr(\\Sigma)= d$, $||\\Sigma||_{op}=1$). To obtain this for sub-Gaussian vectors, one can for instance use the article \"A tail inequality for suprema of unbounded empirical processes with applications to Markov chains\" by R. Adamczak. This is important because the dimension is important for your conclusion.\n    * Lemma A.7 is not true for any delta, please state in the lemma for which delta it is true (delta is at most $ke^{-n}$ if I am not wrong)\n    * Generally, when reading the proofs I would have appreciated if you included more details. The \"therefore\" in the proof of theorem 3.3 was not clear right away for me, there are numerous lines where you do a lot of manipulations that the reader has to guess to obtain the good results and this makes it very hard for us to check the results you claim.\n    * In the proof of Lemma C.2, please provide a reference for \"Davis kahan\", for those that are not familiar with this result.\n    * Typo: beginning of the first sentence of A1.\n    \n    \n    \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fhhB5fpr1pt", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper attempts to understand why self-supervised learning works in the following sense: will the sample complexity for a downstream task be decreased (compared to the standard supervised learning without pretraining) if it is pre-trained according to some related auxiliary task? The relation between tasks is formulated as the approximate conditional independence of the dependent variables. The main theoretical results show that the sample complexity (compared to supervised learning) can be decreased under Assumption 3.5, 4.1, and 4.2. \n\nClarity: \n\nGenerally, this paper is well organized. I have some comments to improve clarity. \n\ni) I'm not quite sure about the motivation of the conditional independence assumption in the introduction. In the colorization example used in the introduction, an algorithm with a general hypothesis (not CNNs) does not necessarily know the semantics of the images (even implicitly) to predict the background-color. It can focus on the cross channel information at the image border to make predictions and ignore the image semantics. Such a self-supervised learning method works (i.e., extracts semantic features) may simply because of the inductive bias introduced by the hypothesis (i.e., CNNs). Therefore, I can hardly say that the pretext tasks work because the \"only\" way is to implicitly infer Y first given the conditional independence assumption.\n\nii) It may be better to explain more about the assumptions and conclusions (lemmas and thms) considering both the theory and practice in self-supervised learning. \n\nFor instance, about theorem 4.2, the paper only mentions that the bound is independent of the complexity of the feature extractor. Why can you achieve this? I guess it is because of the two-stage training and a strong assumption on the feature extractor. Any technical contributions to achieve this should be highlighted? Do the results of traditional supervised learning rely on a similar assumption? Besides, around theorem 4.2, I didn't see a sample complexity comparison to supervised learning. Maybe it is well known, but this is the main claim of the paper. \n\nFurther, I wonder how good the sample complexity is, compared to the results in some related areas like transfer learning and semi-supervised learning (not just supervised learning). Self-supervised learning has outperformed other methods in transfer learning and semi-supervised learning and it would be better to at least discuss more.\n\nCorrectness:\n\nI'm not an expert in machine learning theory. I read the main text carefully and I understood the setups, assumptions, and main results. I quickly checked the proof in the appendix and didn't find flaws. I'm aware that I may underestimate the theoretical contribution of the paper since I'm not familiar with the related work. Welcome any feedback on this during rebuttal and discussion.\n\nAs for empirical validation, considering that the main result is Theorem 4.2 and the main \"baseline\" is supervised learning, it would be better to directly compare the sample complexities of supervised learning and self-supervised learning in experiments.\n\nGenerality: \n\nOne major concern is that the conditional independence assumption (even the approximate one) can be violated in practice. For instance, recently, the instance discrimination pretext has been extensively studied in self-supervised learning and achieved SOTA results in many benchmarks  (e.g., in MoCo and many recent papers). In that case, the random variable X2 is the index of the image (or the input generally). Since we can shuffle the index, it seems that we cannot say X2 (index) and X1 (image) are (approximately) conditionally independent conditioned on Y(label). Also, the paper mentions that some concurrent work does not apply to recontrsuction SSL in the related work. I think, in this case,  X1 = X2, and the conditional independence assumption does not hold as well. In such cases, does the analysis in this paper still apply? The generality of the analysis should be discussed somewhere in the paper because i) the title seems to cover all self-supervised learning methods and ii) the main difference of the paper from several recent papers is the generality as claimed in the related work.\n\nAnother issue is that the paper discusses two hypotheses H1 and H_u and also mentions that H_u includes deep neural networks. However, as far as I know, only infinitely wide or deep neural networks are in H_u.  In practice, self-supervised learning often uses networks with finite depth and width. Does the analysis in this paper apply in this case? If so, please also add detailed discussion and some validation experiments in such models. Otherwise, please clarify this since it can be misleading.\n\nRelated work: \n\nCompared to the existing work, the main contribution of the paper is to generalize the conditional independence based analysis via weakening the assumption. We may need to pay attention to that some concurrent work mentioned in this paper obtain similar results (with less generality as claimed in the related work but also see my comments in Generality).\n\nOverall, I think the theory of self-supervised learning is very important and I should not blame the authors too much since it is an early work on this topic. However, I hope the authors to address the above issues to improve paper quality. I give a rating of 6 currently but it is very borderline in my opinion.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YeFbdGJa5T", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The estimation error refers to the distance between the best function in some function class H, and the optimal estimator computed based on the given data. The definition at the end of page 3 may have some typos since f^* is the universal optimal predictor.\nLemma 3.5 seems trivial since \\psi comes from the universal function class; it is not surprised to get the zero approximation error.\nSome CI results may inspire this utilized ACI; however, the provided generalization bound seems more general with a weaker assumption.\nOverall, it is a good sunmision and offers much insight for SSL from the theoretical perspective.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a mathematical framework to theoretically understand and quantify the benefit of self-supervision on the downstream tasks. The theoretical analyses in this paper are concrete and the authors conducted experiments to support their claims. However, the current version still has the following weaknesses.  

- This paper would benefit from incorporating the reviewers' comments (which was complained by multiple reviewers) and the authors' responses if any.
- The authors need to make it clear in the abstract and introduction that (1) this paper only considers the *reconstruction-based* SSL, instead of the general SSL, and (2) addresses the discrepancy between the practice and the proposed framework.  
- In the post-rebuttal phase, Reviewer 2 pointed out "Lemma 3 seems much more meaningful after the clarifications. I also notice that R5 concerned about the discrepancy in downstream task setup and may doubt the mathematical framework in this paper. In fact, I agree with R5. There is indeed a gap between the proposed mathematical model and the practical SSL algorithms. There is still some work need the authors to complete, i.e., $\mathbb{E}[Y|X_1]\approx \mathbb{E}[Y|X_1,X_2]$."
Decision: Reject