The Power of Contrast for Feature Learning: A Theoretical Analysis
Authors: Wenlong Ji
Zhun Deng
Ryumei Nakada
James Zou
Linjun Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: contrastive learning
self-supervised learning
transfer learning

Abstract: Contrastive learning has achieved state-of-the-art performance in various self-supervised learning tasks and even outperforms its supervised counterpart. Despite its empirical success, the theoretical understanding of why contrastive learning works is still limited. In this paper, (i) we provably show that contrastive learning outperforms autoencoder, a classical unsupervised learning method, on both feature recovery and downstream tasks; (ii) we also illustrate the role of labeled data in supervised contrastive learning. This provides theoretical support for recent findings that contrastive learning with labels improves the performance of learned representations in the in-domain downstream task,  but it can harm the performance in transfer learning. We verify our theory with numerical experiments.

Under review as a conference paper at ICLR 2022
THE POWER OF CONTRAST FOR FEATURE LEARNING: A THEORETICAL ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
Contrastive learning has achieved state-of-the-art performance in various self- supervised learning tasks and even outperforms its supervised counterpart. De- spite its empirical success, theoretical understanding of why contrastive learning works is still limited. In this paper, under linear representation settings, (i) we provably show that contrastive learning outperforms autoencoder, a classical un- supervised learning method, for both feature recovery and downstream tasks; (ii) we also illustrate the role of labeled data in supervised contrastive learning. This provides theoretical support for recent findings that contrastive learning with la- bels improves the performance of learned representations in the in-domain down- stream task, but it can harm the performance in transfer learning. We verify our theory with numerical experiments.
INTRODUCTION
Deep supervised learning has achieved great success in various applications, including computer vision (Krizhevsky et al. (012), natural language processing (Devlin et al.] (2088), and scientific computing (Han al.] [0118). However, its dependence on manually assigned labels, which is usually difficult and costly, has motivated research into alternative approaches to exploit unlabeled data. supersupere learning is a promising approach that leverages the unlabeled data itself as supervision and learns representations that are beneficial to potential downstream tasks.
At a high level, there are two common approaches for feature extraction in self-supervised learning: generative and contrastive (Liu et al. 2021). Both approaches aim to learn latent representations of the original data, while the difference that the generative approach focused on minimizing the reconstruction error from latent representations, and the contrastive approach targets to decrease the similarity between the representations of contrastive pairs. Recent works have shown the benefits of
contrastive learning in practice (Chen et al. 2020a He et al. 2020 Chen et al.) c020b[c). However, why the contrastive approach outperforms the generative approach remains mysterious.
Additionally, recent works aim to further improve contrastive learning by introducing the label infor- mation. Specifically, Khosla et al.] (2020) proposed the supervised contrastive learning, where the contrasting procedures are performed across different classes rather than different instances. With the help of label information, their proposed method outperforms self-supervised contrastive learn- ing and classical cross entropy based supervised learning. However, despite this improvement on in-domain downstream tasks, Islam et al. (2021) found that such improvement in transfer learning limited and even negative for such supervised contrastive learning. This phenomenon motivates us to rethink the role of labeled data in the contrastive leamiigg framework.
In this paper, we first compare contrastive learning with representative method in the generative approach the autoencoders. Specifically, we initialize the investigation in the linear representa- tion setting, which has been widely adopted theory to shed light upon complex machine learn- ing phenomena such as in Du et al. (2020); Tripuraneni et al.) (202T). We provide a theoretical analysis of their feature learning performances on the spiked covariance model (Bai & Yao 2012 Yao et al. 2015 Zhang et al.) 2018) and theoretically justify why contrastive learning outperforms autoencoders contrastive learning is able to remove more noises by constructing contrastive sam- ples. Then investigate the role of label information in the contrastive learning framework and provide a theoretical justification of why labeled data help to gain accuracy in same-domain classi- fication while can hurt multi-task transfer learning.

---

Under review as a conference paper at ICLR 2022
Related works The idea of contrastive learning was first proposed in Hadsell et al. (2006) as an effective method to perform dimension reduction. Following this line of research, Dosovitskiy et al. (2014) proposed to perform instance discrimination by creating surrogate classes for each instance and Wu et al. (018) further proposed to preserve a memory bank as a dictionary of negative samples. Other extensions based this memory bank approach include (He et al. (2020); MMisra & Maaten (:020); Tian et al. (2020); Chen et al. (2020c). Rather than keeping a costly memory bank, another line of works exploits the benefit of mini-batch training where different samples are treated as negative to each other Ye et al.) (2019); Chen et al. (2020a). Moreover, Khosla et al.] (2020) explores the supervised version of contrastive learning where pairs are generated based on label information.
Despite its success in practice, theoretical understanding of contrastive learning still limited. Pre- vious works provide provable guarantees for contrastive learning under conditional independence assumption (or its variants) (Arora et al., 2019 [ee et al. 2020 Tosh et al.) 202T] sai al.) (020). Specifically, they assume the two contrastive views are independent conditioned on the label and show that contrastive learning can provably learn representations beneficial for downstream tasks. In addition to this line of research, Wang & Isola 2020); Graf et al. (2021) investigated the repre- sentation geometry of supervised contrastive loss, and HaoChen et al. (2021) provided analysis via a novel concept of augmentation graph with a new loss function that performs spectral decomposition on such graph. Moreover, Wen & Li (202T) considered the representation learning under the sparse coding model and studied the optimization properties on shallow ReLU neural networks. Different from all previous works, which aim to show that contrastive learning can learn useful representa- tion, our paper aim to explain why contrastive learning outperforms other representation learning methods and also shed light on the role of labeled data in contrastive learning framework, which is under-explored in prior works.
PRELIMINARIES
Notations In this paper, use O, θ to hide universal constants and we write ag X by for two sequences of positive numbers {ax} and {bx if and only there exists an universal constant C > 0 such that ag Cb& for any k. We use || |l. Il 112. ||e to represent the &g norm of vectors, spectral norm of matrices and Frobenius norm of matrices respectively. Let Od,r be a set
of d x r orthogonal matrices. i.e., Od,r & {U E R the cardinality of a set A. For any n E N+, let [n] = (1.2.... .n.. We use sin (U2, U2]] to refer to the sine distance between two orthogonal matrices U2 E Ca,,, which is defined by: Issin θ (U1, 12 A ||TL
U = I,). We use |A| to denote
More properties of sine distance can be found in Section A.1 We use {e to denote the canonical basis in d-dimennional Euclidean space Rd, that is, es is the vector whose i-th coordinate is and all the other coordinates are O. Let [AA be indicator function that takes when A is true, otherwise takes O. We write a V b and a A to denote max(a, (a, b) and min(a, (a, b), respectively.
2.1 SETUP
Given an input x E Rdd contrastive learning aims to learn a low dimensional representation = f(x;;) R" by contrasting different samples, i.e., maximizing the agreement between positive pairs, and minimizing the agreement between negative pairs. Suppose we have n data points X = (21, #2, ... , E R from the population distribution D. The contrastive learning task can be formulated to be an optimization problem:
" min L(8) min
Σ E(,,, BC,, Befoe,BBee : f(-,0)) + AR(O), B 72
(2.1)
where E(.) is contrastive loss and XR(0) is regularization term; BPooz ,B,Ne are the sets of positive samples and negative samples corresponding to Tú, which we will describe detail below.
Losses and Models. We then present the model setup considered in this paper.
(a). Linear representation and regularization term. We consider the linear representation function Wx where the parameter 0 is matrix W Rrxd Since regularization techniques
fax W)-
2

---

Under review as a conference paper at ICLR 2022
have been widely adapted in contrastive learning practice (Chen et al. 2020a He al. 2020 Grill
et al. 2020), we further consider penalizing the representation by regularization term R(W) ) =
[WW W 1 2 to encourage the orthogonality of W and therefore promote the diversity of w, to learn different representations.
(b). Triplet Contrastive loss. The contrastive loss is set to be the average similarity between positive pairs minus that between negative pairs:
(f(x,0),
f(x Pos, (()Pos,,))) B
(f f(x 0))
f(,,0) = ,N,,, Ex, Pos B Neg,
E aP EB
Σ
BNeg
(2.2)
where BP Bgeg are sets of positive samples and negative samples corresponding to x. This loss has been commonly used in constrastive learning (Hadsell et al., (206) and metric learning (Schroff) cct al., 2015; He et al., 2018). In Khosla et al. (2020), the authors show that it is an approximation of the NT-Xent contrastive loss, which has been highlighted in recent contrastive learning practice (Shn 2016 Wu et al. 2018 Oord et al. 2018 Chen et al. 2020a).
(c). Generation of positive and negative pairs. There are two common approaches to generate such pairs, depending on whether or not label information available. When the label information is not available, the typical strategy is generate different views of the original data via augmentation Hadsell et al. [006)] Chen et al.] 2020a). Two views of the same data point serve as positive pair as negative pairs.
for each other while those of different data
Definition 2.1 (Augmented pairs generation). Given two augmentation functions 91 92 Rd Rd
and n training samples B { ke(n)- the augmented views are given by: (1:), 92 (2:) (())))][m)) [ej])- Then for each view 9u (z;), 1,2, the corresponding positive samples and negative samples are defined by: _e {x,) E [2] \ {v}} and Biy (1,(),)) e [2].j [n] \ {i}}.
The loss function of self-supervised contrastive learning problem can be written as:
(Z)) W ga (x,)))
X [|W 1|..
(satCoo(W) 2T
2n
2
(2.3)
In particular, we adopt the following augmentation in our analysis.
Definition 2.2 (Random masking augmentation). The two views of the original data are generated by randomly dividing its dimensions two sets, that is, (x,) Ar, and g2(x;) (I A)z, where A = diag(a1.... .... ad) E Rdxd is the diagonal masking matrix with {a,) being i.i.d. random variables sampled from a Bernoulli distribution with mean 1/2.
A similar augmentation was considered in Wen & Li (202T). However, our primary interest lies in comparing the performance of contrastive learning against autoencoders and analyzing the role of labeled data, while their work focuses on understanding the training process of neural networks in contrastive learning.
When the label information is available, Khosla et al. (0220) proposed the following approach to generate pairs.
Definition 2.3 (Supervised pairs generation). In a K K-class classification problem, given samples for each class & E [K]: {x+ i [nm]] and let Σk= Akk the corresponding positive samples and negative samples for a/ are defined by B. {a/ j [ng] i and B,Nes {af s E [K] \ j E [m.]}. That is, the positive samples are the remaining ones in the same class with xf and the negative samples are the samples from different classes.
Correspondingly, the loss function of the supervised contrastive learning problem can be written as: (Wx,, W Wxz)) no ((K-))
CsapCon (W) kk
K
(Wa, W
Way)
A
[IWT [ (2.4)
n
k=
j=1 sy
(d). Spiked Covariance Model. We consider the following spiked covariance model Bai & Yao
2012 Yao al. 2015) ZZhng et al. 2018) to study the power of contrastive learning:
U² + Cov(z) r²,, Cov(E) = E,
(2.5)
3

---

Under review as a conference paper at ICLR 2022
where E IR' and E Rd are both zero mean sub-Gaussian random variables. In particular, U* E Od, and Σ = diag(of. ... T.). , The first term U* & represents the signal of interest residing in low-dimensional subspace spanned by the columns of U** The second term is the dense noise with heteroskedastic noise. Given that, the ideal low-dimensional representation is to compress the observed into a low-dimensional representation spanned by the columns of (?*.
In this paper, we aim to learn a good projection W E R2 onto a lower-dimensional subspace from observation Since the information of W is invariant with the transformation W OW for any invertible matrix O E Ry.,, the essential information of W is contained in the right eigenvector of W. Thus we quantify the goodness of the representation W by the sine distance || sin (U, IIF, where U is the top-r right eigenspace of W.
3 SELF-SUPERVISER CONTRASTIVE LEARNING VERSUS AUTOENCODER
Autoencoder and contrastive learning are two popular approaches for self-supervised learning. Re- cent experiments have highlighted the improved performance of contrastive learning compared with autoencoders. In this section, we rigorously demonstrate the advantage of contrastive learning over autoencoder by investigating the linear representation settings under the spiked covariance model Eq. (2.5) The investigation is conducted for both feature recovery and downstream tasks.
3.1
RECOVER FEATURES FROM NOISY DATA
Here we focus on the analysis of feature recovery to understand the benefit of contrastive learn- ing autoencoders. As mentioned above, target is to recover the subspace spanned by the columns of U*, which can further help us obtain information on the unobserved v that is important for downstream tasks. However, the observed data has covariance matrix of U² + E rather than the desired =*U*U*T which brings difficulty to representation learning. We demonstrate that contrastive learning can better exploit the structures of core features and obtain better estimation than an autoencoder in this setting.
We start with autoencoders, Formally, an autoencoder consists of encoder fAE 12 R' and a decoder _ I + R While the encoder compresses the original data into low dimensional features, and the decoder recovers the original data from those features. It can be formalized as the following optimization problem for samples {z; J (Ballard 1987
Fan et al. 2019)
10, 9 DE ( (x:))11
min (AE.gA TE
WAET DAE and DE WDEY + dDE. previous works (Bourlard & Kamp 1988 Plaut 2018) have shown that the autoencoder can be reduced to principal component analysis (PCA). That is, the optimal W AE is given by:
In the linear representation setting, where f AE
(
WAE = (U^EEARVil TT
(3.1)
where UAE is the top-r eigenvectors of matrix : : X (II-1n1T/n)X" EAE is a diagonal matrix consists of eigenvalues of M and VAE = ... 2, R can be any orthonormal matrix. In the noiseless case, the covariance matrix is u and autoencoder can perfectly recover the core features. However, in noisy cases, the random noises sometimes perturb the core features, which make autoencoders fail to learn core features. Such noisy cases very common in real applications such as measurement errors and backgrounds in images such as grasses and sky. Interestingly, we will later show that contrastive learning can better recover U despite the presence of large noise.
To provide rigorous analysis, we first introduce the incoherent constant (Candès & Recht 2009).
Definition 3.1 (Incoherent constant). We define the incoherence constant of U e Od,y as
I(U)) max |e_ 2]]
(3.2)
=E|d]
Intuitively, the incoherent constant measures the degree of the incoherence of the distribution of entries among different coordinates, loosely speaking, the similarity between U and canonical
4

---

Under review as a conference paper at ICLR 2022
basis fes)i-1- For uncorrelated random noise, the covariance matrix is diagonal and its eigenspace is exactly spanned by the canonical basis {=]]= (if the diagonal entries in E are all different), which attains the maximum value of incoherent constant. On the contrary, core features usually exhibit certain correlation structures and the corresponding eigenspace of the covariance matrix is expected to have lower incoherent constant.
We then introduce a few assumptions where our theoretical results are built on. Recall that in the spiked covariance model Eq. 2.5). r = U** + E, Cov(z) = I² and Cov(E) = diag(of. o9).
Assumption 3.1 (Regular covariance condition). The condition number of covariance matrix > = diag(ot, .................. ,o)) satisfies K := /a)) < C, where o( represents the j-th largest number among o.. .... og and C' > 0 is universal constant.
Assumption 3.2 (Signal to noise ratio condition). Define the signal to noise ratio p :- v/ we assume (1), implying that the covariance of noise is of the same order as that of core features. Assumption 3.3 (Incoherent condition). The incoherent constant of the core feature matrix U Od,r satisfies I(U** = O(r log d/d).
Remark 3.1. Assumption 3.1 implies that the variances of all dimensions are of the same order. For Assumption 3.2, we focus on a large-noise regime where the noise may hurt the estimation significantly. Here we assume the ratio lies in a constant range, but our theory can easily adapt to the case where p has a decreasing order. Assumption 3.3 implics a stronger correlation among coordinates of core features, which is the essential property to distinguish them from random noise.
Now are ready present our first result, showing that the autoencoder is unable to recover the core features in the large-noise regime.
Theorem 3.1 (Recovery ability of autoencoder, lower bound). Consider the spiked covariance model ( under Assumption 3.7 3.3 and > d >> let WAE be the learned representa- tion of autoencoder with singular value decomposition WAE = AUAEEAE VT Tx) (as in Eq.
If we further assume {o?] are different from euch other and L [oār) - ((+1)) < C. for some
universal constant Cg. Then there exist two universal constants Cp > 0, E (0, such that when
p < Cp. we have
E Isin θ (U*,UAE)]le eV..
(3.3)
Remark 3.2. The additional assumptions {a})d= are different from each other and /
o P(+1)) C. for some universal constant C₂ are for technical consideration. We need these condi- tions to guarantee the uniqueness of UAE As an extreme example, the top-r eigenspace of identity matrix can be any r-dimensional subspace and thus not unique. To avoid discussing such arbitrari- ness of output, we make these assumptions to guarantee the separability of eigenspace.
Then we investigate the feature recovery ability of the self-supervised contrastive learning approach. Theorem 3.2 (Recovery ability of contrastive learning, upper bound). Under the spiked covariance model Eq. 2.55, random masking augmentation in Definition 2.2 Assumption 3.1 3.3 n > d >>>>>>>>>>>' r, let W c1 be any solution that minimizes Eq 2.3), and denote its singular value decomposition as WeL (UcIEcLVer)) then we have
3/2 E Ilsin O (UCL))l S d log d
dr
(3.4)
Remark 3.3. In Eq. 3.4), the first term is due to the shift between the distributions of the augmented data and the original data. Specifically, the random masking augmentation generates two views with disjoint non-zero coordinates and thus can mitigate the influence of random noise on the diagonal entries in the covariance matrix. However, such augmentation slightly hurts the estimation of core features. This bias, appearing as the first term in Eq. (3.4). is measured by the incoherent constant The second term corresponds to the estimation error of the population covariance matrix.
E.2
Theorem 3.1 and 3.2 characterize the difference of feature recovery ability between autoencoder and contrastive learning. The autoencoder fails to recover most of the core features in the large-noise
'The order of I(U*) can be chosen to be any function that decreasing to 0 when d + oo and one can easily adapt the later results to this setting. Here we set it to O(r log d/) the order when U is drawn from uniform distribution on Oar (see the proof in Lemma B.T for simplicity to obtain an exact order in later results.
5

---

Under review as a conference paper at ICLR 2022
regime, since || sin ((U,U*)) has trivial upper bound vr. In contrast, with the help of data augmentation, the contrastive learning approach mitigates the corruption of random noise while preserving core features. As and d increase, it yields a consistent estimator of core features and further leads to better performance in the downstream tasks, as shown in the next section.
3.2 PERFORMANCE ON THE DOWNSTREAM TASK
In the previous section, we have seen that contrastive learning can recover the core feature effec- tively. In practice, we are interested in using the learned features to downstream tasks. He et al. (2020) experimentally showed the overwhelming performance of linear classifiers trained on repre- sentations learned with contrastive learning against several supervised learning methods in down- stream tasks.
Following the recent empirical studies, here we evaluate the downstream performance of simple predictors, which take a linear transformation representation as an input. Specifically, we consider the regression setting with a class of predictors ów,w(2) (2r) = w Wa constructed upon the learned representations W WeL and WAE respectively. Given the observation F U independent of unsupervised data X, our prediction target is ğ generated from linear model j = (8, w w/)/"=>>>>> é, where N (0, y² 1²) is the low-dimensional core feature, term independent of & with zero mean and finite variance. w* E I' is a unit vector of coefficients. We can interpret this model as a principal component regression model (PCR) (Jolliffe 1982) under standard error-in ppoo--n-varreee variables setting: where we assume that coefficients lie in a -iwddmensional subspace spanned by column vectors of U* We either estimate or predict the signal based on observed samples contaminated by the measurement error É. For details of PCR in prror-in-varialle. settings, see, for example, Cevid
the scale of ă and é is the error
2020 Agarwal al. (2020); Bing et al. (2021).
Now we state our result on the downstream performance in prediction task. For any linear represen- tation W rx let R-) Fx innwee- l. (((w,)) be the risk of the best linear predictor, where (())
{()))² Theorem 3.3 (Upper Bound for Downstream Excess Risk of WcL). Suppose conditions in Theorem 3.2 are satisfied. Then we have
3/2 log d + S d
dr
- -(WeL)-R(UL
This result shows that the price of estimating U by contrastive learning on downstream prediction task can be made small in case where the core feature lies in relatively low-dimensional subspace, and the number of samples is relatively large compared to the ostensible dimension of data.
However, the downstream performance of autoencoders is not as good as contrastive learning. We obtain the following lower bound for the downstream prediction risk with the autoencoder.
Theorem 3.4 (Lower Bound for Downstream Excess Risk of W WAR). Suppose the conditions in Theorem 3.7 hold. Assume r < Te holds for some constant Te > O. Additionally assume that p +() is sufficiently small and n d > Then,
R(W AE) R(U+T) ( 2d
where d' is a constant independent of n and
we find that even when r/d and dd/n are small, the downstream performance of autoencoders not satisfying and has much larger downstream task rate than
Comparing theorems 3.3 and 3.4
that of contrastive learning. We note that the constant lower bound of Theorem 3.4 can be obtained without the assumption r re by assuming slightly stronger conditions p 0 log d) and
n >> dr. We also illustrate this phenomenon via numerical simulation in Fig I As predicted by
Theorem 3.1 and 3.2, the downstream task risk of contrastive learning decreases as d increases (Fig.
Left) and as increases (Fig. [ Center) while that of autoencoder remains large when n and d increase.
"In error-in- error-in-variables variables settings, the bias term from the measurement eтror appears in prediction and estima- tion risk. Since our focus lies in proving better performance of contrastive learning against autnencoders, ignore the unavoidable bias term here by considering the risk.

---

Under review as a conference paper at ICLR 2022
0.5
Contrastive Learning
0.5
Contrastive Leamling
0.06
T=
0.4
Autoencoder
0.4
Autoencoder
0.05
10
0.3
Syanstroum
0.3
0.04
0.2
0.2
0.03
0.1
0.1
0.02
0.0
0.0
10
30
50
70
110
2
-5
Dimension
Sample Size
x:00
log.
Figure The vertical axes indicate the prediction risk. Left: Comparison of downstreak task performance between contrastive learning and autoencoders the dimension d. The sample size n set as n 20000. Center: Comparison of downstreak task performance between contrastive learning and autoencoders the dimension n. The dimension d is set as d = 40. Right: Downstream task performance in transfer learning against penalty parameter a in log scale. T is the number of source tasks and r is the dimension of the representation function. We set the number of labeled data and unlabeled data as m = 1000 and n = 1000 respectively.
Remark 3,4. A similar results of upper and lower bound hold for linear predictors 8(x) [(F(w Wx) > 1/2} under binary classification settings, where label is generated from a binary response model ğ| Ber(F((2,, /v)) with known function F R -> [o, 1]. Our results imply that the learned representations by contrastive learning are also useful in downstream classification tasks, compared an autoencoder, thus supporting the empirical success of contrastive learning. A detailed results and proofs are deferred to Appendix B.2
THE IMPACT OF LABELED DATA IN SUPERVISED CONTRASTIVE LEARNING
Recent works have explored adding label information to improve contrastive learning Khosla al, 2020). Empirical results show that label information can significantly improve the accuracy of the in-domain downstream tasks. However, when domain shift (multiple sources) is considered, the label information hardly improves and even hurts transferability (Islam et al., (021). Motivated by those empirical observations, in this section, we aim to investigate the role of labeled data in contrastive learning and provide a theoretical foundation for such phenomena.
4.1 FEATURE MINING IN MULTI-CLASS CLASSIFICATION
We first demonstrate the role of label in the single-souredd case in contrastive learning. Suppose our samples are drawn from r + 1 different classes with probability phe for class k: [r + 1]. and Σtt Pk 1. For each class, samples are generated from class-specife Gaussian distribution:
x² = - + 5* ~ ~00,E,
Vk = 1,2, ., , 1.
(4.1)
To be consistent with the spiked covariance model Eq. 2.5 we assume || Vru, Vk E + 1]. We further assume E* diag(o?) x. .o denote (1) 1 of, and assume
Ek=l Ph/4kk 0, where the last assumption is added to ensure identifiable since the classification
problem 4.11 is invariant under translation. Denote A = x Paptiu we assume rank(A)
and Ciu² (A) (A) C2u² for two universal constants C1 and C2. We remark that this model is a labeled version of the spiked covariance model Eq. (2.5) since the core features and random noise are both sub- Gaussian. We use r classes ensure that μig 's span an r-dimensional space, and denote its orthonormal basis as U* Recall that our target is to recover U*.
As introduced in Definition 2.3 Khosla et al. 2020) proposed a novel approach named supervised contrastive learning, which allows us to discriminate instances across classes. When we have both labeled data and unlabeled data, we can perform contrastive learning based on pairs that are gener- ated separately for the two types of data.
Data Generation Process. Formally, let us consider the case in which we draw n samples as unla- beled data X [21.-. ... .....,,, .nn] E Rdxn from the Gaussian mixture model Eq. 4.14 with Pr P2
Pr-1- For the labeled data, we draw (r + 1)m samples, i.e., m samples for each of the r + classes the Gaussian mixture model, and denote them as X = [ 11(m+)mm E dd
We discuss the above for simplicity. More general versions are considered in Theorem C.2 (in
7

---

Under review as a conference paper at ICLR 2022
the appendix). We study the following hybrid loss to illustrate how label information helps promote
the performance over the self-supervised contrastive learning:
min W WE L(W) := min
LsetiCon (W) + aCSSppCo(W))
(4.2)
W
where a O is the ratio between supervised loss and self-supervised contrastive loss.
We first provide a high-level explanation of why label information help learn core features. When the label information is unavailable, no matter how much (unlabeled) data have, we can only take themselves (and their augmented views) as positive samples. In such scenario, performing augmentation leads to an unavoidable trade-off between estimation bias and accuracy. However, we have additional class information, we can contrast between data in the same class to extract more beneficial features that help distinguish particular class from others and therefore reduce the bias.
Theorem 4.1. Suppose the labeled and unlabeled samples are generated as the process mentioned above. If Assumption 3.7 hold, > d >> r and let WeL be any solution that minimizes the supervised contrastive learning problem in Eq. 4.2) and denote its singular value decomposition as WCL (UCLECL VoL) VCL)
then we have
/// E|| sin U')le ( (aa logd d + V dr
)
O dr
Moreover, if we have m labeled data for each class and no unlabeled data, then
dr
Bl| sin (UUcL, U)Il= S m
The first bound in Theorem 4.1 demonstrates how the effect of labeled data changes against the ratio a in the hybrid loss in Eq. 4..). In addition, compared with Theorem 3.2 when we only have labeled data (a + o0), the second bound in Theorem 4.1 indicates that with labeled data being available, the supervised contrastive learning can yield consistent estimation as m + 0o while the self-super contrastive learning consists of an irreducible bias term (rr log d/ At a high level, label information help gain accuracy by creating more positive samples for a single anchor and therefore extract more decisive features. One should notice a caveat that when labeled data is extremely rare compared with unlabeled data, the estimation of supervised contrastive learning suffers from high variance. In comparison, self-super contrastive learning, which can exploit a much larger number of samples, may outperform it.
4.2 INFORMATION FILTERING IN MULTI-TASK TRANSFER LEARNNING
Label information can tell us the beneficial information for the downstream task, and learning with labeled data will filter out useless information and preserve the decisive parts of core features. How- ever, in transfer learning, the label information is sometimes found to hurt the performance of con- trastive learning (Khosla al., 2020 Islam et al., (021). In this section, we consider two regimes In both regimes, we provide theories to sup-
of transfer learning - tasks are insufficient/abuna port the empirical observations and further demonstrate how to wisely combine the supervised and self-supervised contrastive learning to avoid those harms and reach better performance. Specifically, we consider a transfer learning problem with regression settings. Suppose we have T source tasks which share common data generating model (2.5). In order to study the case of transfer learn- ing, the labels are generated in a different way, that is, for the 1-th task, the labels are generated by y' (w,, =)/v, where We E IR"" is unit vector and different across tasks.
To incorporate label information, (Gretton al. 2005; Barshan et al. 201T), which has been widely used literature (Song et al. 2007a b Barshan et al. 2011)) HSIC is defined HSIC(X, y; W) = X W WXH H/(n- 1)a where W E R is linear representation to be learned and H I. (1/n)l,1,, is
maximize the Schhiit Independence Criteria (HSIC)
the centering matrix. A detailed discussion about its background, motivation and its connec- tion to the mean squared loss is presented in Appendix A..3 Suppose we have n unlabeled data
X = [.1,... xn)] E Rdxn and m labeled data for each source task X [+f..... A.m. y² [vi.... : 1m VI = 1, 1,...,77 T where x; 's and J.''s are independently drawn from spiked covariance
model Eq. (.5) we learn the linear representation via the joint optimization:
min L(W): We
min Laatican (W) HSIC(X', ('''('''':::) W)) W We2rxd
(4.3)
8

---

Under review as a conference paper at ICLR 2022
where > 0 is a pre-specified ratio between the self-supervised contrastive loss and HSIC. (A more general setting is considered in the appendix. see Section C.2 for details.) We now present a theorem showing the recoverability of W by minimizing the hybrid loss function (4.3).
Theorem 4.2. Suppose Assumption 3.7 3.3 hold for spiked covariance model Eq. (2.5) and n. d > r, if we further assume that > for some constant C, T r and w, 's are orthogonal to each other, and let WCL be any solution that optimizes the problem in E.3 and denote its singular value decomposition as WCL = (UCLECL VCLCL) )T, ,then we have:
E|| sin @UUcr, Ul SVT- T(" r log
(
d m 11) + NT
logd 1 ad VVV n
aT
+T
(4.4)
In Theorem
a goes to infinity (corresponding to the case where we only use the supervised loss), Eq. (4.4) is reduced vr- + T0/2 /d/m, which is worse than the /3/2 log d/d rate ob- tained by self-supervised contrastive learning (Theorem (32). This implies that when the model focuses mainly on the supervised loss, the algorithm will extract the information only beneficial for the source tasks and fail to estimate other parts of core features. As a result, when the target task has very different distribution, labeled data will bring extra bias and therefore hurt the transferability. Additionally, one can minimize the right-hand side of Eq. (..4) to obtain a sharper rate. Specifically, we can choose an appropriate a such that the upper bound becomes Vr²(r T) log d/d (when n. m + oc), obtaining a smaller rate than that of the self-supervised contrastive learning. These facts provide theoretical foundations for the recent empirical observations that smartly combining supervised and self-supervised contrastive learning achieves significant improvement on transfer- ability compared with performing each of them individually (Islam et al. (021).
When the tasks are abundant enough then estimation via labeled data can recover core features completely. Similar to Theorem 4.2 we have the following result.
Theorem 4.3. Suppose Assumptions 3.73.3 hold for spiked covariance model 2.3) and > and Mrr) Mir(E== w.w!") > c. c.ror some constant >> 0,
d >> T, if we further assume that T suppose WCL is the optimal solution of optimization problem eq. 4.33) and denote its singular value decomposition as Wc1. (Ucr. Ecr. V..V.... !hen we huve:
Vr Bl sin @(UcL, U $ sa4i log d v +T dr
(4.5)
Similar to Theorem Theorem 4.3 shows that in the case where tasks are abundant, as goes to infinity (corresponding to the case where we use the supervised loss only), (4.5 is reduced to T Tyrd/m. This rate can be worse than the 3/3 p/dd/++ /rd/u rate obtained by self-supervised contrastive learning when is small. Recall that when the number of tasks is small, labeled data introduce extra bias term Vr-T (Theorem 4.2 We note that when the tasks are abundant enough, the harm of labeled data is mainly due to the variance brought by the labeled data. When m suf- ficiently large, supervised learning on source tasks can yield consistent estimation of core features, whereas self-supervised contrastive learning can not. We also illustrate the different behaviors of the two regimes via numerical simulations in Fig. [ right panel. Consistent with our theory, it is observed that when tasks are not abundant, the transfer performance exhibit a U U-shaped curve, and the best result is achieved by choosing an appropriate a. are sufficient, the error remains small when we take large
When tasks are abundant and labeled data
5 CONCLUSION
In this work, we theoretically prove that contrastive learning, compared with autoencoders, can obtain a better low-rank representation under the spiked covariance model, which further leads to better performance in downstream tasks. We also highlight the role of labeled data in supervised contrastive learning and musk transfer learning: labeled data can reduce the domain shift bias in contrastive learning, but it harms the learned representation in transfer learning. To our knowledge, our result is the first theoretical result to guarantee the success of contrastive learning by comparing it with existing representation learning methods. However, in order to get tractable analysis, like many other theoretical works in representation learning (Du et al.) 2020 Lee al. 2020 Tripuraneni et al.) 2021I, our work starts with linear representations, which still provides important insights. Extending the results more complex models is interesting direction of future work.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Anish Agarwal, Devavrat Shah, and Dennis Shen. On principal component regression in a high- dimensional arror-in-variable setting. arXiv preprint arXiv:2010.14444 2020.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: 990.009299 2019.
Zhidong Bai and Jianfeng Yao. On sample eigenvalues in a generalized spiked population model. Journal of Mulfivariate Analysis, 106:167-177, 2012.
Dana H Ballard. Modular learning in neural networks. In AAAI, volume 647, pp. 279-284, 1987.
Elnaz Barshan, Ali Ghodsi, Zohreh Azimifar, and Mansoor Zolghadri Jahromi. Supervised principal component analysis: Visualization, classification and regression on subspaces and submanifolds. Pattern Recognition, 44(7):1357-11) 2011.
Xin Bing. Florentina Bunea, Seth Strimas-Macker and Marten Wegkamp. Prediction under latent factor regression: Adaptive per, interpolating predictors and beyond. Journal of Machine Learn- ing Research, 22(177):1-50. 2021.
Hervé Bourlard and Yves Kamp. Auto-association by multilayer perceptrons and singular value decomposition. Biological cybernetics, 59(4))291-294, 1988.
Hervé Bourlard and Yves Kamp. Auto-association by multilayer perceptrons and singular value decomposition. Biological Cybernetics, 59:291-294, 2004.
Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with appli- cations to high-dimensional statistics. The Annals of Statistics, 46(1):60 (000)996))99,) 89, 2018.
T Tony Cai, Rungang Han, and Anru R Zhang. On the non-asymptotic concentration of het- eroskedastic wishart-type matrix. arXiv preprint arXiv:2008. /2434, 2020.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 96):7117-77, 2009.
Domagoj Čevid, Peter Bühlmann, and Nicolai Meinshausen. Spectral deconfounding via perturbed sparse linear models. Journal of Machine Learning Research, 21:232, 2020.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020a.
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, 2020b.
Xinlci Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved basclines with momentum contrastive learning. arXiv preprint arXiv:2003.0442 042977 2020c.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04880, 2018.
Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discrimi- native unsupervised feature learning with convolutional neural networks. Advances in neural information processing systems, 27:766-774 774, 2014.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434 2020.
Carl Eckart and G. Marion Young. The approximation of one matrix by another of lower rank. Psychometrika, 1:211-218, 1936.
Jianqing Fan, Cong Ma, and Yiqiao Zhong. selective overview of deep learning. arXiv preprint 1rXivv/90440530 2019.
10

---

Under review as a conference paper at ICLR 2022
Gene H. Golub and Charles Van Loan. Matrix computations (3rd ed.). 1996.
Florian Graf, Christoph Hofer, Mare Niethammer, and Roland Kwitt. Dissecting supervised con- strastive learning. In International Conference Machine Learning, pp. 3821-3830. PMLR, 2021.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical de- pendence with hilbert-schmidt norms. In International conference on algorithmic learning theory, pp. 63-77. Springer, 2005.
Lean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint arXiv:2006.07733; 2020.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In 2006 IEFE Computer Society Conference on Computer Vision and Pattern Recogni- tion (CVPR 06), volume 2, pp. 1735-1742. IEEE, 2006.
Jiequn Han, Aruuff Jentzen, and E Weinan. Solving high- nigh-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34):8505-8510, 2018.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. arXiv preprint arXiv:2106.04155 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2020.
Xinwei He, Yang Zhou, Zhichao Zhou, Song Bai, and Xiang Bai. Triplet-center loss for multi-view 3d object retrieval. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1945-1954 2018.
Ashraful Islam, Chun-Fu Chen, Rameswar Panda, Leonid Karlinsky, Richard J. Radke, and Rogério Schmidt Feris. A broad study on the transferability of visual representations with con- trastive learning. ArXiv, abs/2103.13517 2021.
lan T Jolliffe. note on the use of principal components in regression. Journal of the Royal Statistical Society: Series C (Applied Statistics), (133:300--33,, 1982.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. arXiv preprint arXiv:2004. 1362, 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Jason Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008.01000 01064, 2020.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self- supervised learning: Generative contrastive. IEEE Transactions Knowledge and Data En- gineering, 2021.
George Marsaglia. Choosing point from the surface of a sphere. Annals of Mathematical Statistics, 43:645-646 646, 1972.
Ishan Misra and Laurens der Maaten. Self-supervised learning of pretext-invariant representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6707-6717, 2020.

---

Under review as a conference paper at ICLR 2022
Aaron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018.
Dan Pirjol. The logistic-normal integral and its generalizations. Journal of Computational and Applied Mathematics, 237(1):460-469, 2013.
Elad Plaut. From principal subspaces to principal components with linear autoencoders. arXiv preprint arXiv:1804 10253, 2018.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recogmition and clustering. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 815 2015.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In NIPS, 2016.
Le Song, Arthur Gretton, Karsten Borgwardt, and Alex Smola. Colored maximum variance unfold-
ing. Advances in Neural Information Processing Systems. 20: 10:1385-111 1392, 2007a.
Le Song, Alex Smola, Arthur Gretton, and Karsten M Borgwardt. A dependence maximization view of clustering. In Proceedings of the 24th international conference on Machine learning, pp. 415-822, 2007b.
Le Song, Alex Smola, Arthur Gretton, Karsten M Borgwardt, and Justin Bedo. Supervised feature selection via dependence estimation. In Proceedings of the 24th international conference on Machine learning, pp. 823-830, 2007c.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16. pp. 776-794. Springer, 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. In Algorithmic Learning Theory, pp. 1179-1206. PMLR, 2021.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In International Conference on Machine Learning, pp. 10434-10443, PMLR, 2021.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self- supervised learning from multi-view perspective. arXiv preprint arXiv:2006.05576 2020.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity the hypersphere. In International Conference Machine Learning, pp- 9929 9939. PMLR, 2020.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. arXiv preprint arXiv:2105.1513: 2021.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3733-3742, 2018.
Jianfeng Yao, Shurong Zheng, and ZD Bai. Sample covariance matrices and high-dimensional data analysis. Cambridge University Press Cambridge, 2015.
Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via in- variant and spreading instance feature. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6210-6219 6219, 2019.
Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the davis-kahan theorem for statisticians. Biometrika, 102(2):315-322 2015.
Anru R Zhang, T Tony Cai, and Yihong Wu. Heteroskedastic pea: Algorithm, optimality, and applications. arXiv preprint 1800v088 2018.
12

---

Under review as a conference paper at ICLR 2022
A BACKGROUND
A.1 DISTANCE BETWEEN SUBSPACES
In this section, will provide some basic properties of sin θ distance between subspaces. Recall that the definition is:
Issin θ (U1, U2 & 1211- Vill
(A.1)
where U1, U2 E Od, are two orthogonal matrices. Similarly, we can also define:
||sin θ (U2, U2) l2 - [| = || U1 U1
We first give two equivalent definition of this distance: Proposition A.1.
||sin θ (U1, U2) = |ITTU:ll
Proof. Write U = [U1, U11 Od,d we have
U12 = |
U2l
|o Uz
UJ U2 12
then by definition of sin O distance Proposition A.2.
obtain the desired equation.
||sin + (U1,
|0; - -2 1E
Proof. Expand the right hand and use Proposition
A.1 we have:
5 ||UgUT U22 1
[||U1U;
|
| 1b - 2 tr (211) (2U)))
2
2 U2U U)))
U2,
|sin e (U1, U2)
With Proposition A. and A.2 it's easy to verify its properties be a distance function. Obviously,
we have 0 < |sin + (U,, U2) r S /r and ||sin θ (Ui, U2) = ||sin O (U2, Un)ll by definition. Moreover, have the following results:
Lemma A.1 (Lemma
Cai & Zhang (2018)) For any U, V E Odr
sin ((U,V)) < inf OEG,,.
I1O - Vl2a < /2 sin θUU, V)
(A.2)
and
sin OUU V) S inf OEO..r
IU0 - - v v2| sin (U, V)
(A.3)
Proposition A.3 (Identity of indiscernibles).
|ssnn θ (U1, U2) = 0 30 e rexr s.t. 010 U2
Proof. It's straightforward corollary by definition:
||sin θ
< ||TTU2ll 0 + U2 LU
30 Oxxr s.t. U,0 U2.
Proposition A.4 (Triangular inequality).
||sin θ U2)ll & ||sin θ (U1, Ua) P + ||sin e (U2, Ua)l
Proof. By the triangular inequality for Frobenius norm we have: ||UU U2U, || < ||UUU UsU ||e + |U UUU
then apply Proposition A.2 to replace the Frobenius norm with sin distance we can finish the proof.
13

---

Under review as a conference paper at ICLR 2022
A.2 PRINCIPAL COMPONENT ANALYSIS AND AUTOENCODERS
Autoencoders are popular unsupervised learning methods to perform dimension reduction. Its basic idea is learn low dimensional representations for the original data while largely preserving its salient features. To achieve this goal, autoencoders learn two functions: encoder f R - R' and decoder g I2" Rd. While the encoder f compresses the high dimensional data the low dimensional space, we try to recover the original data based on this low dimensional representation via the decoder g. Formally, can be formulated be the following optimization problem:
min Eg (( (()))))
(A.4)
5.9
Intuitively speaking, optimization problem A.4 is trying to preserve the most essential features to recover the original data in the low dimensional representation. In practice, commonly used form to optimize the empirical loss function and choose the loss function to be mean squared error, that is:
min A a be
= 1|,, 5
DE (F (I:)), Vi [n]]
(A.5)
è to be both linear where fAB DD are usually two neural networks. Now if we take fAB g transformations, i.e.,
( WAET ( WDEF EDE,
where W E Rexd DAE E R WoE E Rdxr, :: bar E Rd, and denote X = Rdxn, the optimization problem A.5 can be reduced to be:
min W &A W.e.W.Weeeee besbog
X (WDE(WAEX + bo
It's shown in Bourlard & Kamp (2004) that the bias can be reduced by centeralize the data matrix X, that is, denote I sample matrix, then the optimization problem correspond WAE and WD can be transfromed to be:
2i=1 as the sample mean and Xg = X #1 as the centered
min W WAR.Wir W DE
| WDEW WDEWABXoOB3
By Theorem 2.4.8 in (Golub & Loan 1996), the optimal solution is given by the singular value decomposition of matrix Xo. iee, the eigenspace of X(I, n 1, 1 which is actually what PCA does. This fact indicates that PCA is actually a linear case of autoencoders, which is often
known as undercomplete linear autoencoders. (Bourlard & Kamp 1988
Plaut 2018
Fan et al.
2019
A.3 HILBERT-SCHMID INDEPENDENT CRITERIA
In Gretton et al. (2005). the Hilbert Schmidt Independent Criteria (HSIC) is proposed to measure the dependence between two random variables by computing the Hillbert-Schmidt norm of the cross- covariance operator associated with their Reproducing Kernel Hilbert Spaces (RKHSs). Such mea- surement has been widely used as supervised loss function in feature selection(Song et al. (007c). feature extraction(Song et al. 2007a), Mussering(Sonn et al. 2007b) and supervised PCA Barshan et al. 2011)
The basic idea behind HSIC is that two random variables, named X' and V, are independent if and only if any bounded continuous function of the two random variables are uncorrelated. Let F be separable RKHS containing all continuous bounded real-valued functions of from X' to R and g be that of y, likewise. To each point & E X, there corresponds an element Φ(x) E F such that (o(x), & (x'))= )) = At (x,x²)) n'), where X x X RR is unique positive definite kernel. Likewise, define the kernel ((-,)) and feature map & for G. Denote the joint measure of pz.g, then the empirical
HSIC defined to be:
Definition A.1 (Empirical HSIC (Gretton et al. 2005 Let Z
{(x1 (2...1).....) ....... ..... (Ims Fm.) C X' x Y be a series m independent observations drawn from Pzy- An estimator of HSIC, written HSIC(Z, F, is given by
HSTC(Z,F,9) (m 2
14

---

Under review as a conference paper at ICLR 2022
where H, K, Rm Ky le (z), , := (y), and H Im 141ml m
In problems, and label y E I" via HSIC, equivalently maximize tr(K (H) where K a kernel of W (e.g. X W W X) and L is kernel of (e.g. yy Then we obtain supervised loss corresponding to parameter W:
hope maximize the dependency between Iearned features WX -x"x"
HSIC y5 W) (n 1)2 tr(x W
gy H).
(A.6)
A.3.1 CONNECTION WITH MEAN SQUARED ERROR
In regression tasks, more commonly used loss function is mean squared error:
LMSE (6)
Σ 11f(x;;)) -
(A.7)
where 0 is model parameter. In our contrastive learning framework, where we first learn the repre- sentation via linear transformation and then perform linear regression to learn classifier w R" with learned representation. Assuming that both of X and y have been centered and we ignore the bias term, the model can be viewed as a two layer linear network:
f(x 0) = w T Wa.
Plug this formula back into mean squared error, have:
MSEE (0) = I T T1?
Since the label is scalar, the optimal W will be singular since we perform I-dimensional projec- tion via w. That is, the feature filtering discussed in the main body and if we jointly optimize this loss with unsupervised contrastive loss, the optimal W should be full rank in general.
On the other hand, the classifier w only involves in the supervised loss function and does not affect the contrastive loss, thus we can find the optimal solution for w and W sequentially. For any fixed W such that rank(W d, which can be achieved via joint optimization, the optimal solution of w is:
w- (WXX W W
And the optimal error is:
1
L(W)
|X T W (WXXT y11
n
1
x W (WXX
Ignoring the constant term y y and scalar, we can find that the only difference between this loss function and HSIC (A.6) is the inverse matrix (W X TW which can be viewed as normal- ization of W. In our contrastive learning framework, this normalization can be achieved by the regularization term |[WW I|2. Thus we can use the HSIC to replace the standard regression error which helps us avoid dealing with singularity and additional parameters in optimization.
B OMITTED PROOFS FOR SECTION 3
B. PROOFS FOR SECTION 3.1
In this section, we will prove Theorem 3.1 and 3.2 Section 3.1 The restatement and proof of them can be found in B.I and B.3 Before starting the proof, we first provide lemma to justify the order
of I(U*) in the Assumption 3.3
Lemma B.I (Expectation of incoherent constant over a uniform distribution).
E I(U*) = =0 log
(B.1)
15

---

Under review as a conference paper at ICLR 2022
Before starting the proof, give two technical lemmas to help the proof.
Lemma B.2 (Uniform distribution the unit shpere (Marsaglia 1972)). If 22." Dn i...d
(O. 1), then (a1 VVVVE> x/ :.. Inn/ v S/Ezi 2;)) uniformly distributed the unit sphere gd [10),- ... ..n) Rm 2i=1 1}.
Lemma B.3. If 11, 22, In i.d. (0, 1), then:
E max of S 2 log(n). 18i5n
Proof. Denote = maxigign 27 then we have:
exp(tEY) < Eexp((Y) S Σ exp((xxt) ní exp(tx²) (tx
Note that the moment- geneertngnn function of chi square distribution with v degrees of freedom is:
(1 = (1 - 2/)-
Then combine this fact with equation B. we have:
exp exp(tEY) S n21 - -2)
which implies:
log(n) ())
2t
EY
Vt <
t
2t
2
In particular, take - 1 yields:
EY S 2log(n)
as desired.
Proof of Lemma B.l
Denote the columns of U as U = [u1," ......, ,ur Od,rs we have:
(nj (UU) EU Unifoom(Css.))
max sEld
lo uzl
j=1
E UniiimiimCC..
max
le ugy
xE
max
e, u
[E|d]
By Le2 can transform this expectation on the uniform sphere distribution into normalized multivariate Gaussian variables:
maX x² Σ セ= 2
Ey Uuu.unitemm(.... r r and
(B.2)
where 21, Ø2 ... zy are i.i.d. standard normal random variables. Apply Chebyshev's inequality know that:
1 >1>>0))) ))
2
de
In particular, take 1 we have:
d
v d'
2
16

---

Under review as a conference paper at ICLR 2022
Then take it back into equation B.2 and apply Lemma B.3 we obtain:
2 max
d
d 2
Un- (Os,) (U)) =r
11
2j <
d
j=1
2j
d
maxie(d 27
+ r
11
24
Σj=1
2
1=1
d
2r
SrP
E
max 25 sE|d]
2
8r
4r log d
+
d
d
as desired.
Lemmal I.I demonstrates the expectation of incoherent constant over uniform distribution on Dd, takes the order of ( log d), thus in the main body we take the order to be the same as it. Again we need mention that the order can be chosen be other functions that decrease to 0 when d oc, and one can easily prove our results under more general assumptions.
Now, let's start proving our main results. In the mainbody and section A.2 have shown that in the linear representation setting, the autoencoder can be deduced to PCA. Here we briefly review the results again, for the autoencoder with an encoder fÂÆ Rd IR' and decoder nD RR" - Rd. it can be formalized as solving the following optimization problem for samples 1=
Σ |0 DB ( 1=1
min f.E. .A TI
In the linear representation setting, where fx)(z) WAET bAE and (F( WDEV + bDE, it has been shown that the optimal W AE is given by:
WAE (UARDARVTH AF
(B.3)
where UAE is top-r eigenspace of matrix M == - 1n11)11 EAE is a diagonal matrix consists of eigenvalues of M and VAE = [01,-.. Un]] Rexr can be any orthonormal matrix. Note that UAE is the top-r left eigenspace of the observed covariance matrix and U is that of core feature covariance matrix, and by Assumption 3.2 the observed covariance matrix is dominated by the covariance of random noise. The Davis- theorem provides technique to estimate the eigenspace distance via estimate the difference between target matrices. We will adopt this technique prove the lower bound of feature recovery ability of autoencoder in Theorem 3.1
Theorem B.1 (Restatement of Theorem 3.1 Consider the spiked covariance model Eq. 2.5 under WAE
Assumption 3.3 and n > d > r. let W AE be the learned representation of autoencoder with singular value decomposition WAE (UAE AVV.. AE) (as in Eq. If we further assume Ji=1 are different from each other and i (0 (o -o²rti) CCa for some universal constant Cz. Then there exist two universal constants C, 0, (0, 1). such that when p < Op we have
{of Ad
E ssin θ (U*, UFE)ll 2 cVF.
(B.4)
Proof. Denote M ~* to be the target matrix, x4 U E, i= 1,2, 2, to be the samples generated from model 2.5 and let X = [r1, ... xn. E Raxn 2 [2 ... Zn E grxn = I...... E.]] E _ddn to be the corresponding matrices. In addition, column mean matrix X E Ruxd of matrix X E gg to be X = _X111,1 1 that is, each column of X is the column mean of X. We denote the sum of variance of as o2 sum in B33 autoencoder finds the top-r eigenspace of the following matrix:
write the
Ein of. shown
M X(nn
1,,x, = (U*Z 2 (U* n2
(U 2 TT)
n
n
17

---

Under review as a conference paper at ICLR 2022
The rest of the proof is divided into three steps for the sake of presentation.
Step 1, bound the difference between Mj and Σ. In this step, aim to show that the data recovery of autoencoder is dominated by the random noise term. Note that > Cov(E) = E T we just need to bound the norm of the following matrix:
Mr Σ -u- + -- -- -
1 (V--+B)(U-2+E)
-E)
(B.5)
and we will deal with these four terms separately.
1. For the first term, note that EzzT = v² Ip. the first term can then be divided into two terms
U Zuzzzur = M + - (- zz Ezz J
(B.6)
Then apply the concentration inequality of Wishart-type matrices (Lemma D.3) we have:
Ezz 1l2 S (V / + n 'u
E| zz
Plug it back into [.6 obtain the bound for the first term:
|| 1 U 2 S M + ||U||211 zzt Eaz 12 1
1
T + r
D².
n
(B.7)
2. For the second term, since and E are independent, we must have ZT = 0, so apply Lemma D.2 twice we have:
E EZ
1²
Ez Eg EZ U 121
n
n
Ez [1| / 21122122000 (0 + 1/11
s1m + vFo
Ez [|] [12] (dd
(B.8)
71
(d (nr) 11
n
Vd
aa)
3. For the third term, apply Lemma
D.3 again yields:
d Σ) S (Va
EET
n n oà.
(B.9)
n
4. For the last term, note that each columns of 2 and E are the same, we can rewrite is as:
1 UU* 2 E) B) = +
where x = 4 НΣ 2; and ē = - Σー &.. Since z and & are independent zero mean
sub-Gaussian random variables and Cov(z) D2 L,. Cov(E) { = Σ, we can conclude that:
El ( B 1l2 < B 2l + 2E E 1l + ElIEE" l|
r Vd
do
18

---

Under review as a conference paper at ICLR 2022
To sum up, combine equations (B.) M.944) expectation of matrix M Σ:
together obtain the upper bound for the 2 norm
BIJM E112 S u2
T + m + t V n
d n
+
V an
(B.10)
Step 2, bound the sin @ distance between eigenspaces. As we have shown in step the target matrix of autoencoder close to the covariance matrix of random noise, i.e., E. Note that E is assumed to be diagonal matrix with different elements, hence its eigenspace only consists of canonical basis eş- Denote Uy to be the top-r eigenspace of l and Nec to be its corresponding basis vectors, apply the Davis-Kahan Kahan Theorem D. we can conclude that:
2/rL0|| 101--11p 2012
E sin @U AE: U
(n) -o (r+1)
SVF
1
22
+
+ (
V
d
d
V V
2 (1)
n
n
n
d
p² +
PV
n
Step 3, obtain the final result by triangular inequality. By Assumption 3.3 we know that the distance between canonical basis and the eigenspace of core features can be large:
|| sin ( Us>)l? = UT = E lle T u- = 1
Σ lle U
iE(d//C
IEC
2 log d
2 rーード 2r-r((U")=r-- =r
d
Then apply the triangular inequality sin distance (Proposition bound of autoencoder.
A.4 we can obtain the lower
E| sin OUAAE, U') 2 El sin OU", Uz)lle Eil sin OUUAE, U2)lF
2 zv - ( va log - covrr V PV
d
it implies that when n and d sufficient large and p sufficient small (smaller than given constant Cp 0), there exist universal constant e E (0, 1) such that:
By Assumption 3.2
El|sin sin AU, le 2 e/r.
On the other hand, recall that the optimization problem for self-supervised contrastive learning has been formulated to be:
(f(x W).f(z. Pos W))
(f(z,, (),,,,0,K f(,f(f)ee W))
min WERder
Σ
Σ No
+AR(W),
18 13
18,
1=1 a EB Pox
(B.11)
where (x,W)) WX. R(W)= |WW 1 To compare contrastive learning with autoencoder, now derive the optimal solution of the optimization problem BB.1 Let's start with the general result for self-supervised contrastive learning with augmented pairs generation (Definition 2.1). and then to the special case for random masking augmentation (Definition) 2.2)
Theorem B.2. For two fixed augmentation function g1,92 Rd + Rdd denote the augmented data matrices as X Igi (z1),... 99 (Ix) E dd and X2 [92(21), 99((xn)] E Rdxn, when the augmented pairs are generated as in Definition 2.7 the optimal solution of contrastive learning problem (B. is given by:
WeL = =C Σ un.ooo
19

---

Under review as a conference paper at ICLR 2022
where C > 0 is a positive constant, d; is the i-th largest eigenvalue of the following matrix:
X + X 2(n 1) (X1 + (2) - +
(B.12)
W; is the corresponding eigenvector and V [01, Unl E Rrrr can be any orthonormal matrix.
Proof of Theorem 8.2
When augmented pairs generation 2.1 applied, the contrastive loss can be
written as:
C(W) WW
(x:),
WW + W12(2;), W(()) + W12(1:))
4(n 1) j
-
1!W T 11
A
(t))
(x;) + (t)) + Wtz(a.))
4n(n 1)
i=1 J#i
||W
tr( (r(x| W WX2 + XX xXXx)
2n
1
(r((1 [x)( + X2) W(X, +22)
4n(n 1)
>IWW
1
tr
(X2X7 + XX,X
(X1 + (2) - -x) + X2) )WTW)
2n
2(n 1)
AWTR
1
X2XT + +X1X2
1
(Xi X2) In)(Xi + X2)
2
2nd
2(n - 1)
F
1 2nd
2(n 1) (X1 + (2, - IX) - xx2) ) 2
X2XI
X2X2
Note that the last term only depends X, and the first term implies that when Wer is the optimal solution, AWrrWhh, is the best rank-r approximation of In-1yx XHXT. Then apply Lemma D.4 we can conclude that Wel satisfy the desired conditions.
Theorem B.2 shows general result for augmented pairs generation with any augmentation. Specif- ically, if we apply the random masking augmentation 2.2 we can obtain a more precise result to characterize the optimal solution. To formally state the result, we need additional notations: for any square matrix A E Rdxd, we denote ((A) to be A with all off-diagonal entries set to be zero and D(A) be A with all diagonal entries set be zero. Then we have the following corollary for random masking augmentation.
((A)
Corollary B.1. Under the same conditions as in Theorem B.2, if we use random masking (Definition 2.2 as our augmentation function, then in expectation, the optimal solution of contrastive learning problem B. is given by:
WeL = =C( moooo)) i=1
where C > 0 is a positive constant, σ; is the i-th largest eigenvalue of the following matrix:
A(XXT) 1
n- X(1,1 IT)XT,
(B.13)
W4 is the corresponding eigenvector and V [vi,... Un) RR be any orthonormal matrix.
20

---

Under review as a conference paper at ICLR 2022
Proof of Corollary B.1 Following the proof of Theorem B.2
only need to compute the
expectation over the augmentation distribution defined in 2.2
X WW 1 2
L(W)
(Wti(z))+ WWb(()) Wt1(z,)) + +
4(n 1)
57
(B.14)
1 tr( + +
WW T |1
B B(
2
2n
2(n - (X1 + (1, (,) + X2) X2) X2)
Note that by the definition of random masking augmentation, we have X1 AX which implies X1 + X2 X. On the other hand, X1 and X2 has disjoint nonzero dimensions, hence the matrix X, + X only consists of off-diagonal entries and each of the off-diagonal entry, let's say Tzj. appears if and only if a, + aj = 1. Moreover, once it appears, we must have Jij equals to the ji element of XXT. With this result, we can then compute the expectation in equation (4.14):
((W)- |WW T B tr((XxX] + XXX22
2n
2(n 1) (Xr + x2)(1 Ix)( + X2) W)]
|WW 2n 1 (()x(XX))
2(n 1) X(1n1, - Ix W
JAWTW W And
(A(XX))
1
X X(In1 1 X, 1
4nd (A(XXT
1 X(I,1)
4,)x 11.
71
By similar argument as in the proof of Theorem B.2 can conclude that WeL satisfy the desired conditions.
Remark B.I. Note that the two views generated by random masking augmentation have disjoint non-zero dimensions, hence contrasting such positive pairs vields correlation between different di- mensions only. That's why the first term in equation (B.13) appears to be A(XXT) where the
diagonal entries eliminated.
With Theorem B.2 and Corollary B.1 established, we can find that the self-supervised contrastive learning equipped with augmented pairs generation and random masking augmentation can elimi- nate the effect of random noise the diagonal entries of the observed covariance matrix. Since Cov(E) = is a diagonal matrix, and by Assumption 3.3 we know that the diagonal entries Cov(U"z) 2) -~ only take small proportion of the total Frobenius norm. Thus contrasting augmented pairs will preserve the core features while eliminating most of the random noise, and give more accurate estimation of core features. To start the proof, introduce technical lemma first.
Lemma B.4 (Lemma 4 in Zhang et al. 20188) IfM E RRXP is any square matrix and ((M) is the matrix M with diagonal entries set to 0, then
| < 2|| Here, the factor "2 2 in the statement above cannot be improved.
Then we turn to prove Theorem 3.2
Under the spiked covariance model Eq. 2.5 Theorem B.3 (Restatement of Theorem 3.2
dom masking augmentation in Definition 2.2 Assumption 3.7 and n > d > r, let Wer be any solution that minimizes 2.3. and denote its singular value decomposition as W (Uc1 Eel Vor)) then we have
3/2 E e (UL))lL) I d log d + fār
dr
(B.15)
21

---

Under review as a conference paper at ICLR 2022
Proof. The proof strategy is quite similar to that of Theorem 3.2 and we follow the notation de- fined in the first paragraph that proof. As we have shown in Corollary [.II under our linear representation setting, the contrastive learning algorithm finds the top-r eigenspace of the following matrix:
M₂ = A(XXT) n-1 X(1n - IT)
+ E) E)T 1
カ- (U*Z+ + +)(**+++
n(n - 11 (0=+ ET
To prove the theorem, first we need to bound the difference between M2 and M. We aim to show that the contrastive learning algorithm is dominated by the core feature term. Note that Σ EU2+ 2z U we just need to bound the norm of the following matrix:
M2 M = A ZZ= MM + 1 ZE + +EZTUT) + 1 A(EE))
71
(B.16)
1 1U* EU n(n - 1) (U + E) Z + E)
1)
and we will also deal with these five terms separately.
1. For the first term, we can divide it into two parts:
A(U 27 u U M M A( U 22 U - M) 4 M.
(B.17)
Then apply Lemma B.4 and Lemma D.3
we have:
E| -IA--U-ZZUU M)Il s 2B| n
M1l2 s 21 n n U z2 T
n Using the incoherent condition ((U) O log d). we know that:
|M - A(M) ~0² max
||e U v² (AI( > 5 log du?
<
Combine the two equations above together obtain the bound for the first term:
1 AzuuzzzTut Mlla - E 1 -==uzzzuu T MMll + |M A(M)
E
72
nl
(B.18)
r / n n
S 1
logd log d
(B.19)
2. For the second term, apply equation B.8 yields:
1 EEIACUZEE + EZ
4 -
S Vd
la
EE U
Vn T1y.
(B.20)
n
3. For the third term, apply equation B.9 yields:
E n
B| = E
E)1
s 2|
2 FET n
d E112 $ V/2=
-
)o (B.21)
n
n n
4. For the fourth term, apply equation
yields:
1
12 SE
(UZ + EU + E
n
(B.22)
rv²
Vd
do
(1)
+
Vn
n
22

---

Under review as a conference paper at ICLR 2022
5. For the last term, by equations [B.7 B.8 8.8.B B.9
we know:
El n
(U* + E + F) 1l2
x ||1l + (1+v V _ n + = v² =)
d (1jut +
(v= d
n 10iir
og!
V n
Thus conclude that:
El n(n B B) 112 S d
(B.23)
To sum up, combine equations B. B.18 B.20 B.21 (.22 B.23 for the norm expectation of matrix M2 M:
together we obtain the upper bound
BJ M2 Mlla 2 v2 log
logd d
T V
+ = n
d n
d =
d
(B.24)
n
With the upper bound for || M11,, simply apply Lemma D.1 for sin O distance:
we can obtain the desired bound
2/rTEl NZz - M2
B| sin (UULLLU")I S
v2
SVF
2²
log d +
--
r
+ vn
V n
d
12
d
1
n
((2
1ogg +
r
xー
[ d
+ $ + am1
+
n
3/22
log d +
d
Moreover, there exists an orthogonal matrix Ô E Orxr depending on UCL such that:
B - -11== Eill== 5 2 - M112 3/2
dr
log d +
u2
d
which finishes the proof.
In the following, we will show that our results do not change if we applied the same augmentation for autoencoders, which indicates that our comparison is fair. As discussed in Section A.2 can ignore the bias term in autoencoders for simplicity, which only serves as centralization of the
data matrix. that case, we applied random augmentation t (z) Az and tz(x) (I A)æ to
the original data (r:) and the optimization problem can be formulated as follows:
min EA 11AX WWDEWAEAX + A)X WDDWWAE(T 1) (B.25)
WAE
2n
Then, similar to Theorem B.2 for contrastive learning, we can also obtain an explicit solution for this optimization problem.
Theorem B.4. The optimal solution of autoencoders with random masking augmentation B.25 is given by:
WAE WT. C C u,,oou))
i=1
where C' > 0 is a positive constant, a; is the i-th largest eigenvalue of the following matrix:
1 A(XXT) D(XXT),
(B.26)
2
W4 is the corresponding eigenvector and V [V1,... Un) RRrx be any orthonormal matrix.
23

---

Under review as a conference paper at ICLR 2022
Proof.
We first derive the equivalent form for this objective function:
EaallAx WDDEAEAXIIE I(1 A)X W WDEWAE - 1)
1
+ tr A A'WDEWAEAA + tx A W WE WE +tr(xT A) (T-
2n
(T ( ()xx)
+ +tr(X"(1-A) -1-4) " WE
Ealir(xTA AX) +XXXXXXXX A WDE W WAE) tt(AAXXT A W WeWEWanDeWar
2n
+ (1- + t1 AAXXX (1 (DEWAAD
+tr((1 AAXX (1 (1- We
1 (t + tr(MMDEWWas + t 2n
(B.27)
where M == AXX A + AXXX A)". Note that by Definition 2.2 we have A diag(a1, ... ad) and a, follows the Bernoulli distribution, so we have:
MAM = A(XXT) D(XXT)
(B.28)
Again, by Theorem 2.4.8 in (Golub & Loan 1996), the optimal solution B.25 is given by the eigenvalue decomposition of A XxXX +) up orthogonal transformation, which finishes the proof.
With Theorem B.4 established, we can now derive the space distance for autoencoders with random masking augmentation.
Theorem B.5, Consider the spiked covariance model Eq. under Assumption 3.1 3.3 and n d > r, let WAE be the learned representation of augmented autoencoder with singular value decomposition WAE (UAELAEVAL If we further assume
(i.e., the optimal solution of optimization problem B.25). { are different each other and L'yy / -(r+1)) C. for some universal constant C.. Then there exist two universal constants C, > 0, E (0, such that when p Cp. have
E sin θ (U=,UA))]l 2 eVF.
(B.29)
Proof. Stepl, similar to the proof of Thearem B.1 we first bound the difference between M A(XX)) 2 and Σ Cov( ). Note that:
|| 3112 = |XX - A llle < Xxx Elle 1 |AxxX =2 (|-))11
-
(B.30)
Since Σ is diagonal matrix, then by Lemma B.4 we have:
I
X 1)1
(B.31)
Now, directly apply equation B.7
B.
B.9 we can obtain that:
BJ - El12 S 2
1+
V
[ n
to (v
V
d -
(B.32)
Step 2, bound the sin θ distance between eigenspaces. As we have shown in step 1, the target matrix of autoencoder is close to the covariance matrix of random noise, i.e., E. Note that Σ is assumed to be diagonal matrix with different elements, hence its eigenspace only consists canonical basis e,- Denote Us to be the top-r eigenspace of Σ and {ei)ee to be its corresponding basis vectors, apply
24

---

Under review as a conference paper at ICLR 2022
the Bavis-Kahan Theorem D.1 we conclude that:
2vrBI M - 21
El sin (UAAE Un)
( - o ((+1)
SvF
U²
+
r
+ (
V n
d
d
+
(1)
n
n
n
n
d
Svr p² +
PV
Step 3. obtain the final result by triangular inequality. By Assumption 3.3 we know that the distance between canonical basis and the eigenspace of core features can be large:
|| sin O(U* = |US U- = E lee U
Σ
lle U
iE(d)/C
IEC
2 rr- ---rr()))--- n2
log
Then apply the triangular inequality sin distance (Proposition A.4 we can obtain the lower bound of autoencoder.
sin (UAAR, U*)|= 2 E| sin "(U*,,=))I B|| sin @ Us:)II
2 2 of
log - o
VF p² + (
d )
By Assumption 3.2 it implies that when n and d is sufficient large and p sufficient small (smaller than given constant Cp 0), there exist universal constant (0, 1) such that:
Ell sin @U U'Ille 2 cVr.
Compared with Theorem 3.1 we can find that random masking augmentation makes no difference to autoencoders, which justifies the fairness of our comparison between contrastive learning and autoencoders.
B.2 PROOFS FOR SECTION 3.2
In this section, will provide the proof of Theorem 3.3 and 3.4 with both regression and classifi- cation settings. The statement and detailed proof can be found in Theorem B.6 and B.7
Before going onto the proof, we clarify models and assumptions. Let WeL and WAE be the leamned representations based on train data X Raxd We observe new signal Ø U + E in- dependent of X following the spiked covariance model 2.5 For simplicity, assume ă ~ N 1,) and É Σ. We consider the two major types of downstream tasks: classification and regression. supervised sample following the binary response
For binary classification task, we observe model:
お| Ber(F
(B.33)
where F R + [0 any u E R. Notice that our model B.33 includes logistic models (when F(u) = 1/ and probit models (when F(u) = (uu). where 4 is the cumulative distribution function of standard nor- mal distribution.) We can also interpret model [B.3 as a shallow neural network model with width for binary classification. For regression task, we observe new supervised sample following the linear regression model:
is known monotone increasing function satisfying 1 - - F()) for
① (2, w) \
(B.34)
where غ (0, o2) ) is independent of z.
25

---

Under review as a conference paper at ICLR 2022
In classification setting, specify 0-1 loss, i... fc(6) - I 6())} for some predictor d tak- ing values in {0, For regression task, employ squared error loss (6) (ū 8(8))²
Based on some learned representation W, we consider a class of linear predictors, i.e., dw (3)
[(F(w] W 2 1/2] for classification task and ow, - T WW Ø for regression task, where Rd is a weight vector w E IR". Note that the learned representation depends only on un- supervised samples X. Let Ep!!! and Eg[:] the expectations with respect to (X, 2) and (ύ, c, &),, respectively.
For notational simplicity, define the prediction risk predictor 8 for classification and regression tasks as (c) == (d)] and R, (6) Ep (o)). respectively. Define Σ, VUU** + E. Since any representation W can be decomposed into W = VEw by singular value decompo- sition, where U < 02 {ów. with a slight abuse notation. Our goal as stated above is to bound the prediction risk of predictors {ōw, } constructed upon the learned representations WCL and WAB i.e., the quantity inrwER" Ee ((0weL, and inr Eg [c(6W,,,)))
IR') { w E R'). Thus write ó for ów.
Now state our result the downstream task.
Theorem B.6 (Excess Risk for Downstream Task: Upper Bound). Suppose the conditions in Theo- rem 3.2 hold. Then, for classification lask, we have
113/2
dr
Epl inf Be((c(@Woz.u)) inf Ee(Lo(du*... WER"
log d +
A1
WERT
and for regression task,
Epl inf Es [e inf Es (ōU. o (10/2 (pa log d +
dr
weR"
n
We obtain the lower bound for the downstream predction risk with autoencoders.
Theorem B.7. Suppose the conditions in Theorem 3.7 hold. Suppose S re for some constant
Te > O. Additionally assume that p = (1) I) is sufficiently small and n > d >> r. For classification task, assume F is differentiable at 0 and F0(0) >> 0. Then,
Epl inf E EelC.(SU.R,..). WERT
inf Eeleo ww)1 2 1.
WERT
For regression task,
Epl inf [e(e,(OU.R..)) inf Be (ele ww 1. WER
wERr
For two matrices A and of the same order, we define A B when A is positive semi-definite
The proofs of Theorem B.6 and B.7 relies on Lemma B.8 proved later in this section.
B.9
B. 10 B. and B.12 which are
Proof of Theorem B.G Classification Task Part. Lemma B.10 gives for any U Od
Ep inf Ro(ōv,w) inf (ōU+,,,) weRr
WERT
< ((x(1 + p² 1²)) + (1+ p (npp v 1) B> sin @ U+)
Substituting U +- UAE combined with Assumption 3.2 and ạ O(1) concludes the proof.
Proof of Theorem B.6 Regression Part. Note that under Assumption 3.2 and K O(1), (1 +
p 0-2)/(1 + x- 1 -7² O(). Lemma 1. gives for any U E Da,r.
Ep inf R2 (or, inf R, (ov-,,)))) = p sin @(U, U I22 I1?). wER
wesr
Theorem 3.2 with substitution U UAE gives the desired result.
26

---

Under review as a conference paper at ICLR 2022
Proof of Theorem B.7
Classification Part. Lemma B.9 gives that for C1 1 -1/(2 (0, 1),
we can take n > d and sufficiently small > so that Ep[l sin (UUAE, U*) 2 C17 holds.
By Lemma
B.11
Ep inf Re Re(bUARR.) WER
inf Re( WER
(1 p2)
1
x(r - -li (UAAE, U*) (1+)
(B.35)
(1 + kp2)
1 +
(1 + 2/)3/2
1
x(1 ci)r))
(B.36)
(1 k=22
I ++ p²
(1 + 02)3/2
1
1
(1 + kp2)3/2
1 μ² 2
(B.37)
where the last inequality follows since S Te. If we further take p @(1) < 1/2, the right hand becomes a positive constant. This concludes the proof.
Proof of Theorem B.7 Regression Part. From proposition B.1 we have
inf R₂ (ŌU
inf (oU- mw)
=w" ((I (1
-U UAE UAE (1/13)UXBEUAA UUAU"")'
Thus from Lemma B.8
inf Rr (ōUAA..))
inf Ro .w)) wERu
wERr
1+p=2 + p3x(11 sin @U U* -r) 110*1/..
1
Using Lemma B.9 and by the same argument the proof of Theorem B.7 Classification Part, conclude the proof.
Lemma B.5. For any U E Od
v2 (1 sin O U*)
Amin
2
1 + of
Proof. Since Amia (AC) 2 Amiu( (A) (C) for symmetric positive semi- matrices A and C,
Amin UUU -
2 Amin (U UTTT U)) (UT -
(UTT)_
1/2
2 Amin (1-U -
Amax (v2 U U + +0 +UTEU
12
22 2 (1- sin (())
where we used Weyl's inequality Amii (A+C) 2 Ami((A) - |[O||2 in the second inequality.
Lemma B.6. For any U E Oar
Xmax Xmax(112 -,0,,
< 17(1 sin O U (2) 02
27

---

Under review as a conference paper at ICLR 2022
Proof. Since ||AC||2 = ||A||//|C|l. Amax U " - s >max (1201))))))))
u²
Amiaa (v2U U.
U + +UE
v?
A ( v² U -UTUUU. EU)
v²
02 sin (UU + (dd)
where we used Weyl's inequality Amin (A + C) 2 Amin (A) - ||0||2 and Amin (v2 1 + + EV) x² + oay.
Lemma B.7. For any U E Dd,,
||²(UU Eng ". Ut)= (0-
1+ p
sin @U, U())))
sin
x 1
Proof. Observe that
S = (U -000000-00000~~-++11100 |IU --
E-U")-
== (71)- + (T2).
For the term (T1),
(TI) = ||U T ΣgU)
< I|(U <|((TE,U\> -.UU
Note
| ΣgU' - U Ex = 1 U yu
S sin |0 U + (U - U*) 2
S (U -0000000))))0+,,,VUVV -U-1
Also we have Amin T > + +00000 - U²212). -001) Amin (U- EUU+) 2 v2 + l.y Therefore
+ from the proof of Lemma B.6 and
1
(T1) S (v2 + gi (v2(1 sin O( +(()) (v")|sin(UU,U"))))
For the term (T2),
(T2) |I(U
= || - (U 1U110-10000000110000000001111111
-U*T(U- - -1)1111)))))(111111100100
22 || sin O )3) + (2| U*I12 + IU U+
From Lemma A.1 sin (U, S UU - U 1|2. Finally from these results and II - U S
2||U' -0- U22
,0 - E,
-0, l|2
2² + -2
=
(1)
IU - U 12
22(1 - sin QU U3) + o
v2 + 0 (d)
28

---

Under review as a conference paper at ICLR 2022
Since LHS does not depend the orthogonal transformation U < UO where O Or,r obtain
|| EnU
- U(UTTU,,))--
=0 1211-11 |i UU + oag v² + t 060,
22
v² + % inf
|100 - Um
Combined again with Lemma A.1
we obtain the desired result.
Lemma B.S. For any U E Od
Amin (
V²
v²
- l O(U,
2 0 (1)
02
(d)
Proof. Observe
Amin -,""""1-----0""""0""0""""""1"11"
2 Amiin ((I (1
Since UTU-U+TU 2 0, it follows that (UTU-U* ( -0 ΣU)- Thus
1 VIUTUUTT (1/1²) E0>-"U'01 (10"))100)~~00000
v3 Amxx
EU) "
v UUP
(d)
v2
(r ( II (U,
(d))
where we used Amax (UTT s 1/Dmin (UTE)) s 1/o and ||sin (U1, U2)
UUT U2 from Proposition A.1
Combined with Lemma B.6 we obtain
Amiu
(v²
(U
v2
v2
22 + 02
(d)
Lemma B.9. Suppose the conditions in Theorem 3.1 hold. Fix ea (0, 1). There exists constant 22 Osuch that if / log d/d v & v d/n < C2 then
Epll OUUAE, U 2 cr,
where E (0,1) is universal constant.
Proof. By Cauchy-Schward Schwartz inequality.
EpIl sin AE U
2 (Ep| sin (UAAE, U =²) -r
(Ep) sin (U U' - (Eol sin O(UAE, U*) + Vr).
From Theorem there exists constant > 0 such that
/ log d - -ooo 0² pV
Ep ||sin θ (U", (U*)UA=)lle" 2 VF
Va
29

---

Under review as a conference paper at ICLR 2022
Therefore combined with trivial bound ||sin (UAAE UN) S Vr.
11/2 Vlog d + p² + V pV d
ED| sin @UAAE U-) - r -rs
vd
2 r1/2
d
2 -res
Vlogd 6p² V V6r/
Vd
where we used p/d/nn p2 v2Vd/n S @AV v since This concludes the proof.
since d < n. Thus we can take 02 -((1cc)/e3
Lemma B.10. For any U E Od,r.
Ep inf Ro(ōu,,) inf Re(ōur,,u) WER"
wERn
S {(N(1 + p²))3 + xp² (1 + p 3/2 + (Np2 1)>")BBBll sin @ U²]]]
Proof. Recall that we are considering the class of linear classifiers {ōv,w (x) = T(F(# Uw) > 1/2). For notational simplicity, write B == Uw and 3r = U-.
E R., where
Re(ōuu,) = Pe (ōu, (8) + ū) = Pe = F( 3) > 1/2) + Po = 1, F(* B) < 1/2).
Since F(0) = 1/2 and F is monotone increasing, the false positive probability becomes
Pe (u 0, F(# F) > 1/2) Pū i 3 0)
= -E (1 = 0) L $11 3 > 0}]
= -Es((1- F -T 8))I(( 3 > 0H}.
Write w == T and wt == --1gTU-TT. From assumption, (w* (w) jointly follows normal distribution with mean Write 6²2 = Var(w*) = =w+ "w*, v² = Var(w) = 3 vg where Σg = TT + E. Let = Corlw", w) = -ww TU. (/(v")) By formula for conditional normal distribution, we have wlw" ~ N(row* /0 72)) This gives
P 0, F( 3) > 1/2)
Eg [11 F(w")) [0]
= Es [1 - F(w")) > 0WW'
Eg [1 - F(w"))FE(w > O[w")]
Tuw" /0" Eg (1 - FPF)) (w- w (W-Tww"/
u(1 - 72)1 w )
Tow* /0"
- 0(1-72)11
Eg [1 F(w*)) /u²)]
= Eg [11 - F(w*)) ())(")))(""" /0" (TW" > 0}] + Be((1= - F(w") (((=*))=a )) ( / < <0)],
where + cumulative distribution function of NOO. and a = 7/(1 72/1/2 We define V p as Fs := 20 [F [u)) > OH}. When F(u) = 1/(1+- v (s²) is called the logistic- normal integral, whose analytical form is not known Piijoll 2013)). Since a random variable wt is symmetric about mean 0 and Flu) 1- F(-u),
Ee((1 F()*)) /T') < <0)]
Re(((1 F(-w"))((1 Flow" /0 M) > 0}]
= [F( (1 D(ow" 1/20002)) / > =0]]
Hence
Pe = =
B) > 1/2)
Eel(D(ow' (www /v*) + F(w*)= (F((w))((aw) / 0Hl
1 ( (x((2F(w*) 1)b((w" /00 [1'] 0}}.
2
30

---

Under review as a conference paper at ICLR 2022
Note that the true negative probability is exactly the same the false positive probability under settings:
Pe = F( 1/2)
RE|F((' (") < 0)]
(1F((->T~))TE 3 0]] -E&((1 F(# (>))[(( 22
= -PE(0 = 0, F(=" B) > 1/2).
Therefore
Ro(bu..) = ()((t2)) - 2E (2x((2F(W*) 1) ((ww" /0" II= > 03}.
Let
sup vw* U UW/ T " w T Σg EgUw) WER"
Timax,U ==
Tmax,U* := sup vw" T w/www" w w ETT,,U"))??? wER
From Fauchy-Schward incquality,
max,U
v2 T w w
2 max,U" U-
w*
Define m == fmax,u/( - 72 )122 and U == Tmax,u= /(1 - - m 1/2, Then, since on the event where wt > 0, + D(ow" /v²) is monotone increasing and 2F (Fww) is non-negative, we have
max,U) 1/2
U++)
inf Ro(ōU,w) = - WER
1)0 Uw" (l')" > 0H1
inf Ro = v - -2Ex 1)0( max, Uix"" II[W" > 0}}. weRr
This yields
inf R. (oU,,,))) - inf Ro(dvs w
welr
WERR
= 2E (2F((2( - (1)())_(x))xmtttt (a-mmmxx /0")
/00) ④ UW" /v" \[WW > 0}}.
Note that for any a, b 2 0,
[b) - ((a) S 6(a A 6)16 al.
where @ is density function of standard normal distribution. Observe inf (o inf (ōU),,w)) wER-
wER-
22Ee((2F(W))) 1) Th (OmaxxU)-"" /v") T $(Omaax /u*) [T{=" 0H]
2
[ (2F(w*)) 1) 1)(amaxxU Umaxx w o( 6((Amaxx,U A ammax w / /ww))*)) /v²) dw"
['max - O 1 (2F(w*) -
2A
A Ormaax ) /u²) dw-
U*
(2F(w*)-1) -1) (xx((11(2(((mmma))) A O'max. 1)) 22 22t )wo
Omaxx Om
dw*
OmaxxU A Ouuax,
V2 A Ommax. 2
[Omax,U* Omax. U
( MP(((Amxx(T> A almax.tt) -2 - 1122),
Qmax,U A a'nax,
where we used sup,>o up(u) < co. Since (a - (a² -b2) + S (a² b2) ^ b) for b > O, and F < 1, we obtain
m a ul
inf Ro(ōv,w) inf Re(ōu=,,)) ) wERr
wERR
2max.U- Λ a m
31

---

Under review as a conference paper at ICLR 2022
When U=
U, since T (P/(1-1)) is increasing in 0,
a m - a 1 max.U
inf welt
Ro(ōv,.))
inf "ER"
Ro( mm) x
a amaxx
2
72
max,U'
"maxxU
(B.38)
maxx ) maxx
From Lemma B.5 and B.6 we have
v²
v²
(1-
sin ((U, S muxx S 22 || sin (U, U*) (
2² +
2
+ tod))
v²
122
S T
mmx S V2 + +0(
(B.39)
2² + o
Then, equation
B.38 becomes
inf (o(T)))))
inf (ov wekr
E
2² + +
v² + (1)
mmaxUU+ 2
1²(1 || sin (U, 1B3)
(d)
1/2 + P
v² + 0/))
-
U
u2 sin @ 113)
(d)
(kp² +
1)2
$ (1 p 2) sin (U, )
sin O(U,U*))
(p 1)
(1- sin OU, sin (U,
where the last inequality follows from Lemma B.7
On the event where || sin U(U,U*) 1|3 - 1/2,
inf Ro(ōv,w) - inf Rolōv- w/) S xp ( p- sin (U; U') WER
wElt
When U= < U, on the event where sin @UU 2-212
inf wetrr
Ro(,,,.)- inf (ŌU- wER-
22 + 22)) 12 || sin @ U)) + (d) (-2 maaxxU maax
2
V2
-n² sin (U, U' + +
(v² +11)
1
1²
- sin OU, UUU
TU"
(1 p 2)3
sin (U,('))l2
(- sin OUU, + -ー
2 (x + 1 sin (U, l2,
where we used Lemma B.7 again.
In summary, on the event where sin QU, U* ||2 S
1/2.
inf R.
inf Re (OT wERr
wE
< ((<( 02)) kp² (1 + p p- 2) sin ((U,U*))2
32

---

Under review as a conference paper at ICLR 2022
On the other hand, the event where sin (U.
222 22 A 1/2, we have trivial
inequality wer Ro(ōu,w) - inf Re(dv-,ul ww) S 1. This gives
Ep inf Ro(ōv,m) - inf Re( wERr
wEBr
$ ((x(1 + p²) p²)) + x (1 (1+ 2 sin ((U, +Po(I sin @ U >>>
$ (((x(1++ + kp (1 p1+ (xp² 1)) sin ((U
where the last inequality follows from Markov's inequality.
Lemma B.11. Suppose U Dd,r satisfies 1/(1 + +2) k(r sin O(U 0. Then, inf WER
Ro(ōv..)) inf (60
WERT
(1+ p2)3/2 (1+ k/2)3/22
p2 n(r sin |snn
Proof. We firstly bound the term 72
U= max,U- From Lemma B.8
max U+ - maxx 2 Amin (
2
(U*T) u² U(U EUUT-LUTU"
(r - sin
(B.40)
22 (1)
From assumption, RHS of equation B.40 is non-negative. Then using the inequality b (a²
(a) b) 2 (a² (2a) for a 2 O.
Om Omax,UU 2
(o
max,U m=
Omax U
T max, U. 1122
"max. U- 2
m
mmxx
(1
max,U )1
T maxx
From equation B.39 and equation BB40
U'
Umax,U
2 + 2
1/2
2
+0
3/2
v²
(r |i -I,
v2
1/2 + (1)
v2
v²
= =1+ 2// p-2
2/3222
(r- || O ((U,)))
(B.41)
V2 +
(1)
(a)
From the proof of Lemma B.10
inf WER- (ōu,w.)) inf (ov
wEBr
= 2E (2F
1)( ( w/0"" 4 Uma" |[W > 0}}.
Note that for any b > a 2 0, (bb) (aa) 2 (b - a). Since we assume RHS of equation B.40 positive, OmaxxU- U.nax,U. Thus the event where wt O, 0'mxx /v" 0max U / Observe
inf wesr
R. RoU,,w)) - inf Ro(ōv WERT > 2E (2F((WW - L)0(Amuxx,tr (O'))amx, w/0 amax, HOW 0Hl
2
1 (2F(w*) 1)w* /0w²/v*) Φl ((ammax U- //²)) dww
(amax, amax,U)
Omax, Omax,
(2F(w") - 1I exp (11/2) + a U+ )w 2//0/ /v+2) dw-
0max,U U. Umaxx
(2F((1 + a 2 11/2 111/ - 1) exp exp(( (-(1/2)cu+)) dw-
+ 2 m-
33

---

Under review as a conference paper at ICLR 2022
where in the last equality we transformed wt (1 amax )/22 /00 Since F(u) is differen- tiable at 0 and F(0) 1/2,
F(u) 1/2 F o(u)-
Thus there exists a constant c. only depending on such that 2(F(u) - 1/2) 2 F0)0uu for all E [0,c] since (0) > O. This gives
inf Ro(Ōv,)) inf Re(dv-...)
2V
O O'ax, F'(0)(1 + mmxxx.))) 1/22²* 1-1//
1 a maxxU
moL+ 12
u² (xpp-((12)w>* dw"
(1 a 11+ 1 1 wi exexp (xxp((112)w dw
A M
m Omax,UU
a max,
O Omax,U
(1 0 a max,U Ui+) 1 1/2
0 Um
The last inequality follows since o* ||w*| || = 1 by assumption. It noted that a max,U- 11210000 from equation [B.39] Therefore with equation B.41
inf R&(6ww))
inf wERr
Re(ovr,,)))
wER
p+p-2 -xp || ((U, ( (1 + 1- 2)) 2233/2
1
(1 + kp2)3/2
(1 + 2/33/2
1
x(r sin ((U,
(1+ kp2)3/23
1+
Proposition B.1. For any U Od,r.
inf (ōv, 2n= T (T- U -UU -U o². WER"
Proof of Proposition B.I Generate random variables (æ, following the model equation B.34 We calculate the prediction risk of òU, as:
R2 (ōu,ww)
EE x Uw)? Varg(u T w² +2)² OCove(u-1zTud +
+ TUTTTT Vara (U* + E\
1|00112 of 2vw" T U Uw w T U + U EV)u
= (w A Alw w 1 - 5T 6 + ||2 + o2
where A: U==VUTU*U+TT U T ΣU and b= vU U* From this, we obtain
inf (o = w² T - (1- + -1000000~0110000000000110 wERr
+0?
Lemma B.12. For any U Od,
Epl inf (ov., inf R, (0v w = (1 p| (()= sin 0(U,U")|2][0*"1 weRr
wERr
Proof of Lemma B.12
From proposition B.1
we have
inf R, (8 WER"
inf R, (6U. wER
w ( 1 1
34

---

Under review as a conference paper at ICLR 2022
Note that inf (ōU,,, inR R = infwex (6000,, inf ( w for any orthogonal matrix O E Dr,r. Take Ó E O,, such that | l7 S v sin 0)12 without loss of generality, since we can always take a sequence (mm)m2) such that I| 1 v sin (U, O)l 1/m from Lemma A.1
Lemma B.7 gives
inf R, (ōv,,)) WERE
inf (o on) weRr
1 o sin @(U, U+) +
1 p-
(l) 1+* sin U |12||1111
On the event where || sin @U, )+) ) 1/2
p inf R. (6U,,)) - inf R, (ōv ..) = 11+x~1p-2)) sin @U, (lll
WER
WER*
On the event where
|| sin (U, U* ) 11 2 1/2, we utlize the trivial upper bound
v² inf (ō0,)))) inf R, .m) - ( -~ 31*)~~11a|1w" 12 o(()) 1
weRe
weRr
Combining these results, we have
Ep inf WER"
(5v,),
inf R, (6u+,w)] WER
1 p-
EDll sin OUU ((U,0"))aa [12,\""))]]=="11 (1+ p 2)2
1 K 1 |w" PP sin @ UT) 2 1/v2)
1+p p 2
(p+ Epll sin OUU ((bl
where the last inequality follows from Markov's inequality.
C OMITTED PROOFS FOR SECTION 4
C.I PROOFS FOR SECTION 4.1
In this section, we will provide the proof a generalized version of Theorem 4.1 to cover the imbalanced setting, the statement and the detailed proof can be found in Theorem C.2 In the main body, we assume the unlabeled data and labeled data are both balanced for the sake of clarity and simplicity. Now allow them to be imbalanced and provide more general analysis. Suppose we have n unlabeled data X = [r,,.... ... , ,n,] E Rdx= and n, labeled data X = [ ........ , E Iddxn for class kt the contrastive learning task can be formulated as:
min C(W): min CSerrCon(W) + LSupCon (W). WER
(C.1)
We
In addition, we write generalized version of supervised contrastive loss function to cover the im- balanced cases:
(W Wxf)
Σ/ Σ a
X
CsupCon (W)
WWWT
T 1
T
Σijk Th
(C.2)
where a > is the weight for supervised loss class k. Again we first provide theorem to give the optimal solution of contrastive learning problem. Theorem C.1. The optimal solution of supervised contrastive learning problem C.. is given by
Σ Lacin
WCL =
35

---

Under review as a conference paper at ICLR 2022
where C > 0 is a positive constant, o; is the i-th largest eigenvalue of the following matrix:
1
((XXT)
1
X X -In)XT
4n
n1
ak
X (nn Ih )x Σiee n4
X
r
Tkk
Thk
U; is the corresponding eigenvector and V =[01,-. ..... Un] E RRr can be any orthonormal matrix.
Proof. Under this setting, combine with the result obtained in Corollary B.1 can be rewritten as:
the contrastive loss
L(W)
A WW
T |F
1 tr
(((A(XXT))
2(n X(1n1 - II)x WT w
2
2n
W22 Wxy)
1
ΣΣ
(W x Way)
R2
E1er t4
J#1
Then we deal with the last term independently, note that:
n2
Wayp)
1
ΣΣ
War Waif)
Eiere Th sØkj=1
1
Wa Wzy)
W (W Wxz)
71g
Eeee i= stkj=1
1=1 jfz
tr (x((1n T [
Σijte n agk
7k
Thus we have:
((W) - A
113
1 _ (T((((X)))) 1
n X(In1 - 1x)x (
4n
r+
ak
- tr(Xx(Ims 1T, (.T
r
tr tr(xxl11,, W W))
Eiere
agk
Then by similar argument as in the proof of Theorem B.2 WeL must satisfy the desired conditions.
we can conclude that the optimal solution
With optimal solution obtained in Theorem C.I we can provide generalized version of Theorem
to cover the imbalance cases.
Theorem C.2 (Generalized version of Theorem If Assumption 3.1 3.3 hold, n > d > r and
let Wor be any solution that minimizes the supervised contrastive learning problem in Eq. C.I and denote its singular value decomposition as Wct. = EUc V..) then we have
v2
( 3/2
dr
El sin O(UcL, S (T)
log d + V
d
1
r+1
Vn
d vF) + V
dr
a'k
Eesh The (V ni
Tik
where T 2 1
1
1 Erth P. + 1 Σ an (HuRT - -opp Eigu ne [HaHe + uell )).
r41
Re
36

---

Under review as a conference paper at ICLR 2022
Proof. For labeled data X [21.-.. Fn]] we write to be X M E, where M = [M1.... Mml and [5.. ... .5n] are two matrices consisting of class mean and random noise. To be more specific, if z; subject to the k-th cluster, then 14; n² and (0, E*). Since the data is randomly drawn from each class, 14 follows the multinomial distribution over 1r ,",,", , with probability Pt,"" 1- Thus 14 follows subgaussian distribution with covariance matrix N Ex+ Ck-1PPPMP5
As shown in Theorem the optimal solution of contrastive learning is equivalent PCA of the following matrix:
t 1 (A(XXT)
X(1 (x)
4n
n
Xx (m 1T Ing X
Tkk
Thk
k=1
[X + xxI.I[x)
Extt T4
2
Again we will deal with these terms separately,
For the first term, as we have discussed, X can be divided into two matrices M and E, each of them consists of subgaussian columns. Again can obtain the result in (B.24) (the proof is totally same):
1 1 (A(XX) E 71
X(L,1 1))X) N1l2 S log d
d / + oin
n
n
(C.3)
2. For the second term, notice that:
Xa(Ine-u -nn Dx Σ>
Σ
(u + ( + TT)
+ (nx 1) nk
1kk
=ny(nx 1)HAHE + (nx 1)pz(
5
ck
144e
(C.4)
and that:
Exere The EXIRII
1
ΣΣ
(mn + CN) Σ
(Ms + t5)
Eeen 14.
sott i=1
(C.5)
1k
B2
InnnapaPt + na
+ 11
T
Σijr T4. agf
j=1
Since &: E*), we can conclude that:
1 nhk
E
1/1
O1))
(C.6)
11k
Moreover, we have
72k
nu (nL
53
112 <
(
E
E
112
+
nh -
n4
E l
(C.7)
< d
(1))
n&
Take equation C.6 and C.7 back into
C.4 we can conclude:
d Xx n4 An Inn ) mapile ll2 S V oayyFi+ - oay (C.8)
E
n& (n
ni
Tik
37

---

Under review as a conference paper at ICLR 2022
On the other hand, by equation (.6) we know:
S
S 2
n4
d
(2)-
ttk s
Rei
2
nds
(C.9)
Notice that:
n12
E
ll2 S E||
11i
Ekgz ll2
Σ 1sf T4
Tik
j=1
(C.10)
11
E
1/2 S
21
2tth
Eisk
Vngns
(1)
sfk
syk
Thus take equations
C..9
and CC.10) back into equation
C.5 we have:
E
X
Σ
ns
Hale lle
(C.11)
T&k Σ
Eitk The
Exeh
ne
agth
Vngd
ni (1) + +a)
(C.12)
8 1it
Then combine equations
C.8
together, can obtain the following result:
E
T
N
a& (HaMi
Eeer ne 2 (Hett I + (spk )l22
k=1
d oin
Zuz
log d +
+ o
d
n
Vnsdd
(Vm oi + Vromyy) + V ng
oovvr d
oi
aAk
Eeer n4
r
n
ni
Since have assumed that rank > n+1 matrix:
PhopAppt)) can find that the top-r eigenspace of
T
+
O
Papk
11.
(Haug + matthe
Eejk ne
k=l
kmm
is spanned by U*, then apply Lemma D.I
again we have:
2/BBB Ñ N212
B|| sin OUsSCL U)IFs
(x)
VF
v/ + to
d
2
E log d +
(T)
1
r+1
Vn.d
vi
d Vraayu +V
d oi
ak
+
1gsk T4
n4
mi
k=1
Lock
v2
//3/2
log d + V. dr + r+1
logd+
Σ
r+1
ngdd
(Va n
+ vr)
+ V dr
(T)
d
1
Light
nee
n
km
Roughly speaking, since || Vrv and Σ Pk14 0, approximately we have (, minnett|[Laau]] Although we can not obtain the closed-form eigenvalue in general, in a special case,
38

---

we can find an event A such that Under review as a conference paper at ICLR 2022
where 01 easy to find that:
dr+1,
11
n2
1o and
P1 P2 Pr+1, it's
Σ
E
578
which further implies that:
a Mune 2,( = + 11(
T
PEPAAE
Σ
and we can obtain the result in Theorem 4.1
C.2 PROOFS FOR SECTION 4.2
In this section, we will provide the proof of generalized version of Theorem 4.2 and 4.3 to cover the imbalanced setting, the statement and detailed proof can be found in Theorem C.4 and C.5 First we prove a useful lemma to illustrate that supervised loss function only yields estimation along a 1-dimensional space. Consider single source task, where the data U²2 + is generated by spiked covariance model and the label is generated by
(w",
suppose we have collect n labeled data from this task, denote the data as X = 02, Raxn and the label y [y1, V2, .yn] E R", then we have the following result.
... Fnl E
Lemma C.1. Under the conditions similar to Theorem 3.2 and:
E
nn 1)2 XH T H -/- U+T T
[{}}
$ V aaje.
(C.13)
The proof strategy is to estimate the difference between the two rank-1 matrices via bounding the difference the corresponding the vector component. We first provide simple lemma to illustrate the technique:
Lemma C.2. Suppose a, B E Rd are two vectors, then we have:
||aa T 33 || S v2([|a]12 + 11 B112.
Proof. Denote a (an,..., ,aa), (B1, ... , Ba), then we have:
d d
||a0 T
-333 --T--83
113
0;00 - 33 < Ja,ay - a,,3,12 10,08; - -3,8,11
1=1 #=1
<2
B,12 +
18,17/as
B112 < 2( 11 311
=1
11
Take square root on both side we can finish the proof.
Now prove the Lemma C.I
Proof of Lemma C.I Clearly, we have:
1
X Hyy HXT -2"""" TT
1)2
n1
1
X Hyy" H 22'="" ( U 2n 1
<
1)2
(n- 1)2
1
X XHyy"
H 22'"""
T
2
n2
39

---

Under review as a conference paper at ICLR 2022
thus can replace the (m-1)² with in equation c.13 and conclude the proof. Denote Ñ - f XHyy HX", note that both of N and Uw""" w" U are rank-1 matrices. We first bound the difference between J Hy and Uw":
|| XHy v0 vU'w"1
=
1
(U Z + E)HZ' w" - vU" w
n
1
<
(U*Z+ + =)H2 - -1
n
) (11
-.zuzz r² + n
I 1l2 + [1=22
ll2 + - E2 l12).
n
(C.14)
We deal with the four terms in (C.14) separately:
1. For the first term, apply Lemma D.3 have:
1 U 7Z V 1l I E n
(-r n
Vo)
B||
Zz r
(C.15)
n
2. For the second term, apply Lemma D.2
twice we have:
EZ
112
E2 122EElll EZ |1 ZT]
72
7
Ez (122
r/4 (1) + vro()))
1
Ez Ex11 Exll
(C.16)
(1
+22
vd
vn u1).
3. For the third term and fourth term, from equation 4 we know:
B- 1Z 1l2 E EE-
S 1||
1l2
+
E
ll2
S
_2² + - (C.17)
11
Combine these three equations
(C.55)
C.16
together we have:
v0'1 / d -a)-
E
XHy
(C.18)
With equation (8.1)). we can now turn to the difference between N and Uw"w" TTT we know that:
UT. By Lemma
I - wn T U |P S (1 xHyll |v"'" "f DIII 1 DII vU* vU*""1 wIll
n
Using Markov's inequality, can conclude from (C.88 that:
PP[| -il-XHy - -U" 2) v)
E X "U""
1 -
n
Then denote (w || X
< m) have:
1 X + [+vUU=* w+||]l
EJi - TT=
SE([I
XHy vU* [[T{A}
n
1 SvB| X vt* w- 1 -
d
n
which finished the proof.
40

---

Under review as a conference paper at ICLR 2022
In the main body, assume the number of labeled data and the ratio of loss function is both balanced. Now we will provide a more general result to cover the imbalance occasions. For- mally, suppose have unlabeled data X [= Fnl E Rx and n, labeled data S X; = [x].... ",,",, Di = w.:.... .,, ", Vi = 1, for source task we learn the linear rep- resentation via joint optimization:
min
L(W): = min Lsarroon (W) WeBrxd
Σ a, HS
(C.19)
WEB
[=1
To investigate its feature recovery ability, we first give the following result.
Theorem C.3. For optimization problem [c.19 if we apply augmented pairs generation 2.1 with
random masking augmentation 2.2 for unlabeled data, then the optimal solution given by:
Σ
WCL =
where C' > 0 is a constant, is the i-largest eigenvalue of the following matrix:
1 (A(XXT) n - X(In1 - In)XT]
a; yol - X,Ho X,)).
T
4n
==1 nn. 1)2
Wi is the corresponding eigenvector, V= [",,,". Url E Rexr can be any orthogonal matrix and In; 1 is the centering matrix.
[
H I,
nu -1,
Proof. Under this setting, combine with the result obtained in B.I the loss function can be rewritten as:
F. 2n tr ((5A(xx)) 2(n-1) X(1n1 - Ix WTW.
((W) = |WW
1
Σ
tr tr(x, W WX; H)
ai
(n+ 1)2
E=1
X
1 WW 1 (((XTT)
n n X(111 x.)xTT
2
4nd
X(n4 1)2 X.Hn. H,,
a
1 [(XXT)
- _ X(In1) -1)
l,)x
4md
TI 1
0g X, X.Hn, Ha, XT
X(4: - 1)2
Then by similar argument as in the proof of Theorem WeL must satisfy the desired conditions.
B.2 we can conclude that the optimal solution
Then give the proofs of Theorem 4.2 and Theorem 4.3 under our generalized setting, one easily obtain those under balanced setting by simply setting a 01 =
Our and m = m nr, which is consistent with Theorem 4.2 and Theorem in the mainbody.
Theorem C.4 (Generalized version of Theorem 4.2 Suppose Assumption 3.7 hold for spiked covariance model Eq. 2.5) and > d >> we further assume that T < r and 's are orthogonal to each other, and let WCL be any solution that optimizes the problem in Eq. C.19) and denote its singular value decomposition as WCL = (UC1EcL VoL)". then we have:
T
VT
Bl sin(Q(Ucl, S(
)( log logd +
min (as, 1}
min a;
T
Vr 04 mine (a;, 1}
+ T at + min ai a1) d min as
(at,
n,
41

---

Under review as a conference paper at ICLR 2022
Proof. As shown in Theorem C- eigenspace of matrix
optimizing loss function (C.19) is equivalent to find the top-1"
1 [(Xx))
1 X(Ln1 [))TT
a X X,Hn, wayi Hn, X
4n
n
(n. - 1)3
Again denote M2 A (A(XXT)) n-1 X(LI)) x and Ñ; - (12 H.H HX..
By equation (B.24) we know that:
E B|IM M1l $ 12 ("1lodd+ /
= n +++ du
(v==m)
/ d n n)
+= =
/ /d
By Theorem C.I we know that for each task S,, we can find an event A, such that P(A.) = O(v ():
E| - 2² www U [P[[A S V T
The target matrix is N = V² + +iT U wiy! U., and we can obtain the upper bound for the difference between N and Ñ:
BIN - -IIITTTTE Bl| BlI M112 + Σ
03
Uwwa T U
(TTTT((A
4
i=1
(C.20)
SUZ log +
+ nn
V d + n
d
+
V
T
The
We divide the top-r eigenspace UCL of WoL Wr. into two parts: the top-T' eigenspace 0/22 and Cr. top-(T + 1) to top-r eigenspace UCL- Similarly, we also divide the top-r eigenspace U of N into two parts: U+(1) and (2) Then apply Lemma D.1 we have we can bound the sin Q distance for each parts: on the one hand,
El sin (O(UL), ( I|r
= - sin (LUCLLUMO) (000))I1TTT 111 A.) + BI| sin (OIUEL, (
19)
VTBJÑ - NIlaTInE + -VT(UUE
(an)(N) - (NT+
VT
22" 2 logg +ogo n
d Σ 1=1
d a
T
d
+
T
minteiT a01?
n4
12
d r "logd+ d
T
as + min ai
d
V n
+
min ai
min a;
74
On the other hand,
E|| sin (201) ||-
sin (Q(U Cl (-(21)) (l [I = El sin (e(U (
(2)
Vr- TEI - N112T(nE
+
- 149)
(min(Ar)( (V), ,
V
22 22 log + of +
d +
Σ aij
d
+ Vr T
minjelry {as, 1}v2
n
ni
n
Vr-T (T (1logd+
[1
d +
/r
T
T
min fa; 17 + +1)v/n d
a;
"mingemy (as, 13
(d
n,
42

---

Under review as a conference paper at ICLR 2022
Note that:
= |Von
1U ( -
(2) 11 10
S T - 1122L v 1|3 (r- - - u
sin (e(VE), v-w)) |1 + || sin (iUUE (wll)) 11?:
and the sin distance has trivial upper bounds:
|| sin (..) 11 ST, | ( (w 1133 r-
Thus we can conclude:
El| sin(O(UUL.
[i|| sin (O(UEL, (-())) (Q(UEL.U<()))I
sin (Q(V (n())) l|r
24
d minje(ri(an..1 1}
V
logg +
d
+
Vr Σ
T
ai + min ( 1}
vr -
minke (a 1}
n4
iml
VT
d
a2 min d4
d A ATT.
logd +
+
minie(Tr ai
min ag n
Theorem C.5 (Generalized version of Theorem 4.3 Suppose Assumptions 3.1 3.3 hold for spiked
covariance model Eq. 2.5) 2.5) and > d >>'>0 т, if we further assume that T 2 and E a,w,j is full rank, suppose WCL is the optimal solution of optimization problem eq,
C. 19 and denote its
singular value decomposition as WCL = (UCLECLVe VCL)" then we have:
VF
E siss@(UUc,, 2 1 + v2 (²)()
d log d +
a₁
d V
1 1+ aam
nz
Proof. The proof strategy is similar to that of Theorem here the difference is that each direc- tion can be accurately estimated by the labeled data and we don't need to separate the eigenspace. Directly applying Lemma and equation (C.20) we have:
B|| sin(O(UCL,, U'))
|S|| (in(O U U))))== Ai) + Ell (U()[(UC
VrEIIn - -NI2 + VIP(UL
(N)
VF
22 2 log
+
d
+
Oj
d
+
+r
Σ
d
22 22 (2)(r)
(Ein (
n
n;
1=1
Vr
Glog d + vr
+1
1 X(r) (Et1 (.wm))
1
A
T
a. w.w.
1=1
D USEFUL LEMMAS
In this section, we list some of the main techniques that have been used in the proof of the main results.
43

---

Under review as a conference paper at ICLR 2022
Lemma D.1 (Theorem 2 in Yu et al. (2015). Let E, Rexp be symmettic. with eigenval- A1 2 ... 2 Ap and d1 ... A respectively, Fix 1 min (Ar-1 - Ar. 2 Aot1) > where Ao = do and Apt1 = -00. Let == 1, and let V (Ur, 1r+1...... Us) E Rxxd and V = (6r, ,r+1,..., 02) ) E Rexd have orthonormal columns
- and assume that
satisfying Eng- = uj and Eûg X500 for r, rr++ 1,...... Then
2min (2/211$ E112, 11 EllF)
sin @(V, V)llE S min (Ay-1 by d lo+1)
Moreover, there exists an orthogonal matrix Ô E RRdx such that
23/2 min (d/21 - 2i11 || 2:llF)
IİO VIF 1 min (Ar-1 Ar 2, As+11
Lemma D.2 (Lemma in Zhang al. (2018). Assume that E TR xp2 has independent sub-
Gaussian entries, Var (Bij) 08 max, E, oi max; E3 oi Ti mmxi, oz.. Assume that
|ag/osslle max 1-ap--122200 q21
1/2 (T. ((ag) /0ss) 993 /os))
s k.
Let V E Opar be fixed orthogonal matrix. Then
x
22 2 2 + +x) - 2exp 5r min
E|EV oC + KT (0(1)0)) 1/2 + (1))-
Lemma D.3 (Theorem 6 in Cai al. (2020)). Suppose Pı pr-by- P2 random matrix with inde-
pendent mean-zero sub- Gaussian entries. If there exist o....... Sp 2 0 such that ||zz / S Ck for constant CK 0, then
E 12 EZZ
12 <
Σ
o
p2 Σ
o maxo;
Lemma D.4 (The Eckart- Young-ouuun-s Theorem (Eckart & Young 1936)). Suppose that A UEVT is the singular value decomposition of A. Then the best rank- k approximation of the matrix A w.rt the Frobenius norm, || [|,, is given by
k
A Σ ouuu?""
that is, for any matrix B of rank at most
|A - Asla S ||A Bllr.
E NUMERICAL EXPERIMENTS
E. SUPPORTING EMPIRICAL RESULTS IN RELATED WORKS
In this section, we list some recent empirical evidence that provides sound support to our theory:
Contrastive learning outperforms generative self-supervised learning. Figure of Chen et al. (2020a) and Figure of Liu et al. (2021), it's observed that contrastive learning has superior performance compared to the generative approach. These results are consistent with our theory in Theorem 3.1 3.4 where show that contrastive learning achieves better performance on both feature recovery and downstream tasks compared with autoencoder, a representative generative self- supervised learning method.
44

---

Under review as a conference paper at ICLR 2022
Supervised contrastive learning improves downstream accuracy. In Table 2 of Khosla et al. (2020) and the first column in Table 4 of Islam et al. (202I), supervised contrastive learning shows significant improvement with 7%-8% accuracy increase ImageNet and Mini- Mini-ImageNet. This ob- servation is consistent with our finding in Theorem 4.1 where we prove that supervised contrastive learning can achieve better upper bound in feature recovery compared with self-supervised con- trastive learning.
Label information may hurt transferability in contrastive learning. In Table of Khosla et al. 2020) and Table 4 Islam et al. (2021), where the supervised contrastive learning hardly increases the predictive accuracy compared to the self-supervised contrastive learning (the difference of mean accuracy is less than 1 1%) and can harm significantly 397 in Table 3 of Khosla et al. (2020)). These results indicate that some mechanisms in supervised contrastive learning hurt model transferability since the improvement on source tasks is significant. Moreover, in Table 4 of Islam et al. (202T), it is observed that combining supervised learning and self-supervised contrastive learning together achieves the best transfer learning performance com- pared with each of them individually. These findings are consistent with our theory in Theorem where we show that the error can increase a (the ratio between supervised learning loss and self-supervised learning loss) grows and the optimal error is achieved when choosing moderate o, ie., combining self-supervieed learning and supervised learning together.
some datasets (e.g. 5.5% lower for SUN
E.2 SIMULATION WITH SYNTHETIC DATA
To verify our theory, we conducted numerical experiments on the spiked covariance model 2.5 under a linear representation setting. As we have explicitly formulated the loss function and derive its equivalent form in the main body and appendix, simply minimize the corresponding loss by gradient descent to find the optimal linear representation W. For self-supervised contrastive learning with random masking augmentation, we independently draw the augmentation function by Definition 2.2 and apply them to all of the samples in each iteration. To ensure the convergence, we set the maximum number of iteration for (typically 10000 or 50000 depends on dimension d).
We report two criteria to evaluate the quality of the representation, downstream error and sine dis- tance. To obtain the sine distance for a learned representation W. we perform singular value decom- position to get W = (UEVT)T and then compute || sin (U, U+] To obtain the downstream task performance, in the comparison between autoencoder and contrastive learning, we first draw labeled data from spiked covariance model (2.5 with labels generated as in Section 3.2 then we train the model by using the data without labels to obtain the linear representation W, and learn a linear predictor using the data with labels and compute the regression error. In the transfer learning setting, we draw some labeled data on the source tasks and additional unlabeled data. The 1000 and the number of unlabeled data is set 1000. Then number of labeled data is set representation W, and draw labeled data from new source task train with them to obtain the linear to learn a linear predictor to compute the regression error. In particular, we subtract the optimal regression error obtained by the best representation U for each regression error and report the difference, or more precisely, the excess risk as downstream performance.
The results are reported in Fig. 02 and Table 2 As predicted by Theorem 3.1 and 3.2 the feature
recovery eтror and downstream task risk of contrastive learning decreases as d increases (Fig. D Left) and as n increases (Fig. [ Center) while that of autoencoder is insensible to the changes in d and n. The performance of transfer learning exhibits a U-shape type curve when the number of tasks is insufficient, which implies that the supervised training may hurt the transferability and we need to choose an appropriate ratio a to obtain the best performance. When tasks are abundant enough, the performance of transfer learning becomes better as we increase the weight of supervised loss.
(a)
-5
-3
-2
-1
0
5
T=8,== 10
0.0242
0.0231
0.0199
0.0141
0.0122
0.0125
0.0184
0.0345
0.0499
0.0535
0.0587 0.0079
T 20 10
0.0223
0.0163
0.0156
0.0096
0.0079
0.0055
0.0064
0.0064
0.0067
0.0070
Table I: Downstream performance in transfer learning against the penalty parameter a. T is the number of source tasks.
45

---

Under review as a conference paper at ICLR 2022
(g)
-5
-4
-1
0
3
2,0373
2.0371
2.0228
2.0021
2.0055
2.0010
2.0362
2.0699
2,0705
2.0113
T= 20,
2,0352
2,0292
2,0030
1.8711
1,9700
1,9990
1.9766
19702
1.7900
19714
19672
Table 2: Feature recovery performance in transfer learning against the penalty parameter a. T is the number of source tasks.
Contrastive Learning
Contrastive Learning Autoencoder
-0
2.050
Sine Destance
2.025
2.000
1.975
10
20
50
90
130
Dimension d
Sample Size
(oqu(a)
Figure 2: Left: Comparison of learned feature between contrastive learning and autoencoders against the dimension The sample size n set as n = 20000. Center: Comparison of fea- ture recovery performance between contrastive learning and autoencoders against the dimension The dimension is set as 40. Right: Feature recovery performance in transfer learning against penalty parameter in log scale. T is the number of source tasks. We set the number of labeled data and unlabeled data as m 1000 and n = 1000 respectively.
46


Reviews:
[{"review_id": "y_z-9LYeIuo", "reviewer": "Reviewer_TTCS", "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": "The main result of this paper sounds interesting, despite the analysis conducted on linear models.\nThe result shows that in some cases (large noise regime), the autoencoder cannot recover the core features and thus performs badly on downstream tasks, but the contrastive learned model has the ability to recover the core features due to the random augmentation.\nTherefore, we can see the strong power of contrastive learning, at least in the large noise regime.\nThe analysis of supervised contrastive learning is also novel and convincing.\n\nI have some detailed questions about the comparison between autoencoder and contrastive learning (Thm 3.2 and 3.3).\n- Does $c'$ in Thm 3.4 depend on $r$ or $r_c$? If so, can we say that $c'$ is worse than the bias term (first term) in Thm 3.3? If not, why do we need to assume that $r\\le r_c$ for all $r$? Sorry for that the proofs in the appendix are not clear for me to read.\n- Do we use data augmentations for autoencoder training in the analysis? If so, the comparison between autoencoder and contrastive learning is fair. If not, contrastive learning seems to involve more human knowledge for the training.\n\nMoreover, I wonder how much insight of this paper can be extended to non-linear models and other augmentations? Do you have any empirical studies to verify how many theoretical observations still hold for those cases?\n\nMinor comment: The appendix is not well organized. It is hard to see a clear one-to-one match between theorems in the main text and the proofs in the appendix.", "summary_of_the_paper": "This paper studies the generative power of contrastive learning from a theoretical perspective. To enable the analysis, this paper considers the linear model with random masking augmentation. Training data are assumed to be generated by the spiked covariance model. The main result is that contrastive learning can recovery the core features since the random masking augmentation can mitigate the influence of random noise on the diagonal entries in the covariance matrix, while the autoencoder is unable to recover the core features due to the large noise. Then this paper shows that downstream excess risk can be upper bounded by contrastive learning but cannot be less than a universal constant for an autoencoder. Beyond the unsupervised setting, this paper also studies the role of labeled data in supervised contrastive learning and gives the upper bound of sine distance between the supervised contrastive learned model and the true model.\n", "summary_of_the_review": "Overall, I think this paper is good and interesting. My main concern is 1) whether the comparison between autoencoder and contrastive learning is fair, and 2) how much insight can be extended to the more realistic scenarios.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "I4hnTLysJ6G", "reviewer": "Reviewer_R3zT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I appreciate the plentiful theoretical analysis in this paper. However, some concerns are preventing its acceptance.\n\n1). Theorem 3.1 and Theorem 3.2 provide the sin-distance error bounds, which measure the divergence between the optimal eigenvector U* and the solution U.  And it is good to see that the upper bound of CL is lower than the lower bound of AE (with the increase of d and n). However, I do not think such an inequality relation can really interpret the good generalization performance of CL. Firstly, this error bound is just based on training data which cannot be generalized to the unseen test data. Secondly, the recovered variable is merely U, but the optimization variable W contains U, S, and V.\n\n2). The generalization error bound in Theorem 3.3 is similar to existing work [R1, R2]. The authors can further elaborate on the difference or merit of their error bound compared with those existing works.\n\n3). For the supervised CL case (Theorem 4.2), I have the same concern as my first point. The error bound merely focuses on the training data, which cannot be generalized to unseen test data. Thus it does not really explain the effectiveness of the existing supervised CL model. Actually, we know that the supervised CL can also be regarded as a (supervised) similarity metric learning problem that has been widely studied in both theoretical and experimental aspects.\n\nGiven the above my concerns, I would like to vote for a weak reject. I will increase my score if I misunderstand something.\n\n[R1]. Saunshi N, Plevrakis O, Arora S, et al. A theoretical analysis of contrastive unsupervised representation learning, ICML'19.\n[R2]. Chen S, Niu G, Gong C, et al. Large-Margin Contrastive Learning with Distance Polarization Regularizer, ICML'21.", "summary_of_the_paper": "This paper presents theoretical results to explain the effectiveness of contrastive learning (CL). For the self-supervised model, the authors prove new sin-distance-based error bounds for autoencoder (AE) and CL. For the fully-supervised model, the generalization error bound is derived. Numerical experiments validate the theoretical finds.", "summary_of_the_review": "See the above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CBN_azt8A4o", "reviewer": "Reviewer_wN4s", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nThe theoretical results explaining various interesting phenomena about contrastive learning are novel to the best of my knowledge. Contrastive learning and its variants have enjoyed a lot of success recently, and theoretical understanding of these methods is appreciated. The simplicity of the data model used to understand these phenomena is good in some ways; more on its weaknesses later. The paper is well written and easy to follow for most part. The notations, assumptions, theorem statements and discussions that ensued are clearly presented. Simulations verify many of the theoretical findings, e.g. existence of optimal $\\alpha$ (relative strength of supervised learning and contrastive learning) when not enough source tasks available in transfer learning. The results seem mostly believable and a quick read of some parts of the Appendix did not raise any red flags; in fact the Appendix presentation also seemed clean.\n\n\n**Weaknesses**\n\nWhile the simplicity of the setting is not a huge weakness, it certainly raises the question of relevance of the analysis to practice. Evidence for a lot of empirical phenomena studied in this paper is provided by citing Khosla et al. and Islam et al. at various points in the paper. It would help to make these connections more explicit and present findings from prior work more clearly. One way to justify the setting would be to experimentally demonstrate relevance of some of the theoretical components on some real benchmark datasets. This would also increase the impact and visibility of the theoretical results.\n\nIt would also help to provide some more intuition for some of the results, for e.g. what is the reason for the extra bias term in contrastive learning compared to supervised contrastive learning? It seems like this arises from not learning the diagonal entries of $U^* {U^*}^{\\top}$ due to the augmentation, but it's not clear why this is not a big issue for supervised learning. Similarly it will help to include some more intuition for why transfer learning fails and how self-supervised contrastive learning can save from that.\n\n\n\n\n*Other comments/questions*\n\n- Abstract should clearly specify that theoretical results are shown for simplified linear representation setting for a particular data model. The current phrasing makes the results seem very general\n\n- It would be nice to present Theorem 3.1 and 3.2 for the same (or comparable) values of $\\rho$ (signal to noise ratio), or perhaps make the dependency more explicit. Although both work for $\\rho = \\Theta(1)$, the dependence is hidden.\n\n- The choice of augmentation (random coordinate subsets) is such that it aligns with independence structure of noise in data ($\\Sigma$ being diagonal). This seems important for the superiority of contrastive learning over autoencoders. Could this have any connection to its superiority in practice?\n\n- (Minor) The augmentation generation process from Definition 2.1 is different from what is done in practice, where the two views are typically independent of each other given an input $x$. In this paper the two views are dependent since they use complementary subset of coordinates. Perhaps the analysis could be extended to this independence case, e.g. two views can correspond to 2 random subsets of coordinates.\n\n- Is there any specific reason for choosing HSIC apart from ease of analysis?", "summary_of_the_paper": "This paper performs a theoretical study of various empirical phenomena regarding contrastive learning in a simplified setting, with a linear representation function, spiked covariance data model and linearized version of contrastive loss. In such a setting, the following results are shown theoretically (a) contrastive learning with a particular data augmentation can learn much better feature than an autoencoder by virtue of learning the underlying low rank signal as features, (b) supervised contrastive learning can do better than contrastive learning by getting rid some bias that data augmentation introduces, (c) for transfer learning, a combination of unlabeled contrastive loss and supervised learning can do better than either of them individually. Simulation experiments are used to verify many of these findings.", "summary_of_the_review": "Overall the theoretical results are quite interesting, for a very relevant problem of contrastive learning. The main negative point is about the relevance of the results to more practical settings.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers appreciated the theoretical analysis performed in this work, some concerns were raised during discussion, such as how relevant the obtained results are wrt current contrastive learning practices, and whether the comparison against a simple auto-encoder (basically PCA) is fair or insightful. The authors' response did not satisfactorily address these concerns. Overall, the current work appears to be preliminary, and important questions were left out: (a) how realistic the assumptions are (linear, spike covariance, Bernoulli random augmentation)? (b) performing better than PCA in a specifically designed setting may not be as impressive as it appears; what can we say about the optimality of CL against any algorithm? (c). validation on existing benchmark and CL algorithms would be welcome. The authors are encouraged to revise the current draft by incorporating the reviewers' comments and submit again. In its current form, we believe this work is not ready yet.
Decision: Reject