Year: 2021

Abstract:
Contrastive learning has achieved state-of-the-art performance in various selfsupervised learning tasks and even outperforms its supervised counterpart. Despite 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 unsupervised 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 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.

heading: 1 INTRODUCTION
text: Deep supervised learning has achieved great success in various applications, including computer vision (Krizhevsky et al., 2012), natural language processing (Devlin et al., 2018), and scientific computing (Han et al., 2018). However, its dependence on manually assigned labels, which is usually difficult and costly, has motivated research into alternative approaches to exploit unlabeled data. Self-supervised 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 is 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., 2020b;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 information. 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 learning 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 is limited and even negative for such supervised contrastive learning. This phenomenon motivates us to rethink the role of labeled data in the contrastive learning framework.
In this paper, we first compare contrastive learning with a representative method in the generative approach – the autoencoders. Specifically, we initialize the investigation in the linear representation setting, which has been widely adopted in theory to shed light upon complex machine learning phenomena such as in Du et al. (2020); Tripuraneni et al. (2021). 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 samples. Then we 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 classification while can hurt multi-task transfer learning.
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. (2018) further proposed to preserve a memory bank as a dictionary of negative samples. Other extensions based on this memory bank approach include He et al. (2020); Misra & Maaten (2020); 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 is still limited. Previous works provide provable guarantees for contrastive learning under conditional independence assumption (or its variants) (Arora et al., 2019; Lee et al., 2020; Tosh et al., 2021; Tsai et al., 2020). 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 representation 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 (2021) 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 representation, 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.

heading: 2 PRELIMINARIES
text: Notations In this paper, we use O,Ω,Θ to hide universal constants and we write ak . bk for two sequences of positive numbers {ak} and {bk} if and only if there exists an universal constant C > 0 such that ak < Cbk for any k. We use ‖ · ‖, ‖ · ‖2, ‖ · ‖F to represent the `2 norm of vectors, spectral norm of matrices and Frobenius norm of matrices respectively. Let Od,r be a set of d × r orthogonal matrices. i.e., Od,r , {U ∈ Rd×r : U>U = Ir}. We use |A| to denote the cardinality of a set A. For any n ∈ N+, let [n] = {1, 2, · · · , n}. We use ‖ sin Θ(U1, U2)‖F to refer to the sine distance between two orthogonal matrices U1, U2 ∈ Od,r, which is defined by: ‖sin Θ (U1, U2)‖F ,
∥∥U>1⊥U2∥∥F . More properties of sine distance can be found in Section A.1. We use {ei}di=1 to denote the canonical basis in d-dimensional Euclidean space Rd, that is, ei is the vector whose i-th coordinate is 1 and all the other coordinates are 0. Let I{A} be an indicator function that takes 1 when A is true, otherwise takes 0. We write a∨ b and a∧ b to denote max(a, b) and min(a, b), respectively.

heading: 2.1 SETUP
text: Given an input x ∈ Rd, contrastive learning aims to learn a low dimensional representation h = f(x; θ) ∈ Rr 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 = [x1, x2, · · · , xn] ∈ Rd×n from the population distribution D. The contrastive learning task can be formulated to be an optimization problem:
min θ L(θ) = min θ
1
n n∑ i=1 `(xi,BPosi ,B Neg i ; f(·, θ)) + λR(θ), (2.1)
where `(·) is a contrastive loss and λR(θ) is a regularization term; BPosi ,B Neg i are the sets of positive samples and negative samples corresponding to xi, which we will describe in 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 f(x,W ) = Wx, where the parameter θ is a matrix W ∈ Rr×d. Since regularization techniques
have been widely adapted in contrastive learning practice (Chen et al., 2020a; He et al., 2020; Grill et al., 2020), we further consider penalizing the representation by a regularization term R(W ) = ‖WW>‖2F /2 to encourage the orthogonality of W and therefore promote the diversity of wi 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:
`(x,BPos,BNeg, f(·, θ)) = − ∑
xPos∈BPos
〈f(x, θ), f(xPos, θ)〉 |BPos|
+ ∑
xNeg∈BNeg
〈f(x, θ), f(xNeg, θ)〉 |BNeg| ,
(2.2) where BPos,Bneg are sets of positive samples and negative samples corresponding to x. This loss has been commonly used in constrastive learning (Hadsell et al., 2006) and metric learning (Schroff et 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 (Sohn, 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 is available. When the label information is not available, the typical strategy is to generate different views of the original data via augmentation (Hadsell et al., 2006; Chen et al., 2020a). Two views of the same data point serve as positive pair for each other while those of different data serve as negative pairs. Definition 2.1 (Augmented pairs generation). Given two augmentation functions g1, g2 : Rd → Rd and n training samples B = {xi}i∈[n], the augmented views are given by: {(g1(xi), g2(xi))}i∈[n]. Then for each view gv(xi), v = 1, 2, the corresponding positive samples and negative samples are defined by: BPosi,v = {gs(xi) : s ∈ [2] \ {v}} and B Neg i,v = {gs(xj) : s ∈ [2], j ∈ [n] \ {i}}.
The loss function of self-supervised contrastive learning problem can be written as:
LSelfCon(W ) = − 1
2n n∑ i=1 2∑ v=1 [ 〈Wgv(xi),Wg[2]\{v}(xi)〉− ∑ j 6=i 2∑ s=1 〈Wgv(xi),Wgs(xj)〉 2n− 2 ] + λ 2 ‖WW>‖2F .
(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 to two sets, that is, g1(xi) = Axi, and g2(xi) = (I − A)xi, where A = diag(a1, · · · , ad) ∈ Rd×d is the diagonal masking matrix with {ai}di=1 being i.i.d. random variables sampled from a Bernoulli distribution with mean 1/2.
A similar augmentation was considered in Wen & Li (2021). 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. (2020) proposed the following approach to generate pairs. Definition 2.3 (Supervised pairs generation). In a K-class classification problem, given nk samples for each class k ∈ [K]: {xki : i ∈ [nk]}Kk=1 and let n = ∑K k=1 nk, the corresponding positive samples and negative samples for xki are defined by BPosi,k = {xkj : j ∈ [nk] \ i} and B Neg i,k = {xsj : s ∈ [K] \ k, j ∈ [ns]}. That is, the positive samples are the remaining ones in the same class with xki and the negative samples are the samples from different classes.
Correspondingly, the loss function of the supervised contrastive learning problem can be written as:
LSupCon(W ) = − 1
nK K∑ k=1 n∑ i=1 [∑ j 6=i 〈Wxki ,Wxkj 〉 n− 1 − n∑ j=1 ∑ s6=k 〈Wxki ,Wxsj〉 n(K − 1) ] + λ 2 ‖WW>‖2F . (2.4)
(d). Spiked Covariance Model. We consider the following spiked covariance model (Bai & Yao, 2012; Yao et al., 2015; Zhang et al., 2018) to study the power of contrastive learning:
x = U?z + ξ, Cov(z) = ν2Ir, Cov(ξ) = Σ, (2.5)
where z ∈ Rr and ξ ∈ Rd are both zero mean sub-Gaussian random variables. In particular, U? ∈ Od,r and Σ = diag(σ21 , · · · , σ2d). The first term U?z represents the signal of interest residing in a 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 x into a low-dimensional representation spanned by the columns of U?.
In this paper, we aim to learn a good projection W ∈ Rr×d onto a lower-dimensional subspace from observation x. Since the information of W is invariant with the transformation W ← OW for any invertible matrix O ∈ Rr,r, 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,U?)‖F , where U is the top-r right eigenspace of W .

heading: 3 SELF-SUPERVISED CONTRASTIVE LEARNING VERSUS AUTOENCODER
text: Autoencoder and contrastive learning are two popular approaches for self-supervised learning. Recent 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.

heading: 3.1 RECOVER FEATURES FROM NOISY DATA
text: Here we focus on the analysis of feature recovery to understand the benefit of contrastive learning over autoencoders. As mentioned above, our target is to recover the subspace spanned by the columns of U?, which can further help us obtain information on the unobserved z that is important for downstream tasks. However, the observed data has covariance matrix of ν2U?U?> + Σ rather than the desired ν2U?U?>, 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 an encoder fAE : Rd → Rr and a decoder gDE : Rr → Rd. 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 {xi}ni=1 (Ballard, 1987; Fan et al., 2019):
min fAE ,gAE
1
n n∑ i=1 ‖xi − gDE(fAE(xi))‖22.
In the linear representation setting, where fAE(x) = WAEx+ bAE and gDE(y) = WDEy + bDE , previous works (Bourlard & Kamp, 1988; Plaut, 2018) have shown that the autoencoder can be reduced to principal component analysis (PCA). That is, the optimal WAE is given by:
WAE = (UAEΣAEV > AE) >, (3.1)
where UAE is the top-r eigenvectors of matrixM := X(I−1n1>n /n)X>, ΣAE is a diagonal matrix consists of eigenvalues of M and VAE = [v1, · · · , vn] ∈ Rr×r can be any orthonormal matrix. In the noiseless case, the covariance matrix is ν2U?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 are 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 (Candès & Recht, 2009). Definition 3.1 (Incoherent constant). We define the incoherence constant of U ∈ Od,r as
I(U) = max i∈[d] ∥∥e>i U∥∥2 . (3.2) Intuitively, the incoherent constant measures the degree of the incoherence of the distribution of entries among different coordinates, or loosely speaking, the similarity between U and canonical
basis {ei}di=1. For uncorrelated random noise, the covariance matrix is diagonal and its eigenspace is exactly spanned by the canonical basis {ei}di=1 (if the diagonal entries in Σ 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 a 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), x = U?z + ξ, Cov(z) = ν2Ir and Cov(ξ) = diag(σ21 , · · · , σ2d). Assumption 3.1 (Regular covariance condition). The condition number of covariance matrix Σ = diag(σ21 , · · · , σ2d) satisfies κ := σ2(1)/σ 2 (d) < C, where σ 2 (j) represents the j-th largest number among σ21 , · · · , σ2d and C > 0 is a universal constant. Assumption 3.2 (Signal to noise ratio condition). Define the signal to noise ratio ρ := v/σ(1), 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). 1 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 ρ has a decreasing order. Assumption 3.3 implies a stronger correlation among coordinates of core features, which is the essential property to distinguish them from random noise.
Now we are ready to 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 Eq.(2.5), under Assumption 3.1-3.3 and n > d r, let WAE be the learned representation of autoencoder with singular value decomposition WAE = (UAEΣAEV >AE)
> (as in Eq.(3.1)). If we further assume {σ2i }di=1 are different from each other and σ2(1)/(σ 2 (r)−σ 2 (r+1)) < Cσ for some universal constant Cσ . Then there exist two universal constants Cρ > 0, c ∈ (0, 1), such that when ρ < Cρ, we have
E ‖sin Θ (U?, UAE)‖F ≥ c √ r. (3.3)
Remark 3.2. The additional assumptions {σ2i }di=1 are different from each other and σ2(1)/(σ 2 (r) − σ2(r+1)) < Cσ for some universal constant Cσ are for technical consideration. We need these conditions 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 arbitrariness 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.5), random masking augmentation in Definition 2.2, Assumption 3.1-3.3 and n > d r, let WCL be any solution that minimizes Eq.(2.3), and denote its singular value decomposition as WCL = (UCLΣCLV > CL) >, then we have
E ‖sin Θ (U?, UCL)‖F . r3/2
d log d+
√ dr
n . (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 Eq.(3.2). The second term corresponds to the estimation error of the population covariance matrix.
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
1The order of I(U?) can be chosen to be any function that decreasing to 0 when d→∞ and one can easily adapt the later results to this setting. Here we set it to O(r log d/d), the order when U is drawn from a uniform distribution on Od,r (see the proof in Lemma B.1) for simplicity to obtain an exact order in later results.
regime, since ‖ sin Θ(U,U?)‖F has a trivial upper bound √ r. In contrast, with the help of data augmentation, the contrastive learning approach mitigates the corruption of random noise while preserving core features. As n 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.

heading: 3.2 PERFORMANCE ON THE DOWNSTREAM TASK
text: In the previous section, we have seen that contrastive learning can recover the core feature effectively. 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 representations learned with contrastive learning against several supervised learning methods in downstream tasks.
Following the recent empirical studies, here we evaluate the downstream performance of simple predictors, which take a linear transformation of representation as an input. Specifically, we consider the regression setting with a class of predictors δW,w(x) = w>Wx constructed upon the learned representations W = WCL and WAE respectively. Given the observation x̌ = U?ž+ ξ̌ independent of unsupervised data X , our prediction target is y̌ generated from a linear model y̌ = 〈ž, w?〉/ν + ̌, where ž ∼ N(0, ν2Ir) is the low-dimensional core feature, ν is the scale of ž and ̌ is the error term independent of ž with zero mean and finite variance. w? ∈ Rr is a unit vector of coefficients. We can interpret this model as a principal component regression model (PCR) (Jolliffe, 1982) under standard error-in-variables settings2, where we assume that coefficients lie in a low-dimensional 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 error-in-variables settings, see, for example, Ćevid et al. (2020); Agarwal et al. (2020); Bing et al. (2021).
Now we state our result on the downstream performance in prediction task. For any linear representation W ∈ Rr×d, let R(W ) := EX [infw∈Rr Ey̌,x̌[`(δW,w)] be the risk of the best linear predictor, where `(δ) = (y̌ − δ(x̌))2. Theorem 3.3 (Upper Bound for Downstream Excess Risk ofWCL). Suppose conditions in Theorem 3.2 are satisfied. Then we have
R(WCL)−R(U?>) . r3/2
d log d+
√ dr
n .
This result shows that the price of estimating U? by contrastive learning on a downstream prediction task can be made small in a case where the core feature lies in a 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 WAE). Suppose the conditions in Theorem 3.1 hold. Assume r ≤ rc holds for some constant rc > 0. Additionally assume that ρ = Θ(1) is sufficiently small and n d r. Then,
R(WAE)−R(U?>) ≥ c′, where c′ > 0 is a constant independent of n and d.
Comparing theorems 3.3 and 3.4, we find that even when r/d and √ d/n are small, the downstream performance of autoencoders is not satisfying and has a much larger downstream task error rate than that of contrastive learning. We note that the constant lower bound of Theorem 3.4 can be obtained without the assumption r ≤ rc by assuming a slightly stronger conditions ρ = O(1/ log d) and n dr. We also illustrate this phenomenon via numerical simulation in Fig.1. As predicted by Theorem 3.1 and 3.2, the downstream task risk of contrastive learning decreases as d increases (Fig. 1: Left) and as n increases (Fig. 1: Center) while that of autoencoder remains large when n and d increase.
2In error-in-variables settings, the bias term from the measurement error appears in prediction and estimation risk. Since our focus lies in proving a better performance of contrastive learning against autoencoders, we ignore the unavoidable bias term here by considering the excess risk.
Remark 3.4. A similar results of upper and lower bound hold for linear predictors δ(x) = I{F (w>Wx) > 1/2} under binary classification settings, where label is generated from a binary response model y̌|ž = Ber(F (〈ž, w?〉/ν)) with a known function F : R→ [0, 1]. Our results imply that the learned representations by contrastive learning are also useful in downstream classification tasks, compared to an autoencoder, thus supporting the empirical success of contrastive learning. A detailed results and proofs are deferred to Appendix B.2.

heading: 4 THE IMPACT OF LABELED DATA IN SUPERVISED CONTRASTIVE LEARNING
text: Recent works have explored adding label information to improve contrastive learning (Khosla et 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., 2021). 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.

heading: 4.1 FEATURE MINING IN MULTI-CLASS CLASSIFICATION
text: We first demonstrate the role of label in the single-sourced case in contrastive learning. Suppose our samples are drawn from r + 1 different classes with probability pk for class k ∈ [r + 1], and∑r+1 k=1 pk = 1. For each class, samples are generated from a class-specific Gaussian distribution:
xk = µk + ξk, ξk ∼ N (0,Σk), ∀k = 1, 2, · · · , r + 1. (4.1) To be consistent with the spiked covariance model Eq.(2.5), we assume ‖µk‖ = √ rν,∀k ∈ [r+ 1].
We further assume Σk = diag(σ21,k, · · · , σ2d,k), denote σ2(1) = max1≤i≤d,1≤j≤r+1 σ 2 i,j and assume∑r+1
k=1 pkµk = 0, where the last assumption is added to ensure identifiable since the classification problem (4.1) is invariant under translation. Denote Λ = ∑r+1 k=1 pkµkµ > k , we assume rank(Λ) = r and C1ν2 < λ(r)(Λ) < λ(1)(Λ) < C2ν2 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+1 classes to ensure that µk’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 generated separately for the two types of data.
Data Generation Process. Formally, let us consider the case in which we draw n samples as unlabeled data X = [x1, · · · , xn] ∈ Rd×n from the Gaussian mixture model Eq.(4.1) with p1 = p2 = · · · = pr+1. For the labeled data, we draw (r + 1)m samples, i.e., m samples for each of the r + 1 classes in the Gaussian mixture model, and denote them as X̂ = [x̂1, · · · , x̂(r+1)m] ∈ Rd×(r+1)m. We discuss the above case for simplicity. More general versions are considered in Theorem C.2 (in
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∈Rr×d L(W ) := min W∈Rr×d LSelfCon(W ) + αLSupCon(W ), (4.2)
where α > 0 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 we have, we can only take themselves (and their augmented views) as positive samples. In such a scenario, performing augmentation leads to an unavoidable trade-off between estimation bias and accuracy. However, if we have additional class information, we can contrast between data in the same class to extract more beneficial features that help distinguish a 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.1-3.3 hold, n > d r and let WCL be any solution that minimizes the supervised contrastive learning problem in Eq.(4.2), and denote its singular value decomposition as WCL = (UCLΣCLV > CL) >, then we have
E‖ sin Θ(UCL, U?)‖F . 1
1 + α (r3/2 d log d+ √ dr n ) + α 1 + α √ dr m .
Moreover, if we have m labeled data for each class and no unlabeled data, then E‖ sin Θ(UCL, U)‖F . √ dr
m .
The first bound in Theorem 4.1 demonstrates how the effect of labeled data changes against the ratio α in the hybrid loss in Eq.(4.2). In addition, compared with Theorem 3.2, when we only have labeled data (α → ∞), the second bound in Theorem 4.1 indicates that with labeled data being available, the supervised contrastive learning can yield consistent estimation as m → ∞ while the self-supervised contrastive learning consists of an irreducible bias term O(r3/2 log d/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-supervised contrastive learning, which can exploit a much larger number of samples, may outperform it.

heading: 4.2 INFORMATION FILTERING IN MULTI-TASK TRANSFER LEARNING
text: 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. However, in transfer learning, the label information is sometimes found to hurt the performance of contrastive learning (Khosla et al., 2020; Islam et al., 2021). In this section, we consider two regimes of transfer learning – tasks are insufficient/abundant. In both regimes, we provide theories to support 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 a common data generating model Eq.(2.5). In order to study the case of transfer learning, the labels are generated in a different way, that is, for the t-th task, the labels are generated by yt = 〈wt, z〉/ν, where wt ∈ Rr is a unit vector and different across tasks. To incorporate label information, we maximize the Hilbert-Schmidt Independence Criteria (HSIC) (Gretton et al., 2005; Barshan et al., 2011), which has been widely used in literature (Song et al., 2007a;b;c; Barshan et al., 2011). HSIC is defined as HSIC(X, y;W ) = X>W>WXHyy>H/(n− 1)2, where W ∈ Rr×d is linear representation to be learned and H = In − (1/n)1n1>n is the centering matrix. A detailed discussion about its background, motivation and its connection to the mean squared loss is presented in Appendix A.3. Suppose we have n unlabeled data X = [x1, · · · , xn] ∈ Rd×n and m labeled data for each source task X̂t = [x̂t1, · · · , x̂tm], yt = [yt1, · · · , ytm],∀t = 1, . . . , T where xi’s and x̂tj’s are independently drawn from spiked covariance model Eq. (2.5), we learn the linear representation via the joint optimization:
min W∈Rr×d L(W ) := min W∈Rr×d
LSelfCon(W )− α T∑
t=1
HSIC(X̂t, yt;W ), (4.3)
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.1-3.3 hold for spiked covariance model Eq.(2.5) and n > d r, if we further assume that α > C for some constant C, T < r and wt’s are orthogonal to each other, and let WCL be any solution that optimizes the problem in Eq.(4.3), and denote its singular value decomposition as WCL = (UCLΣCLV >CL) >, then we have: E‖ sin Θ(UCL, U?)‖F . √ r − T (r log d d + √ d n + αT √ d m ∧ 1 ) + √ T (r log d αd + 1 α √ d n + T √ d m ) .
(4.4)
In Theorem 4.2, as α goes to infinity (corresponding to the case where we only use the supervised loss), Eq.(4.4) is reduced to √ r − T + T 3/2 √ d/m, which is worse than the r3/2 log d/d rate obtained by self-supervised contrastive learning (Theorem 3.2). 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 a 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.4) to obtain a sharper rate. Specifically, we can choose an appropriate α such that the upper bound becomes √ r2(r − T ) log d/d (when n,m → ∞), 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 transferability compared with performing each of them individually (Islam et al., 2021).
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.1-3.3 hold for spiked covariance model Eq.(2.5) and n > d r, if we further assume that T > r and λ(r)( ∑T i=1 wiw > i ) > c for some constant c > 0, suppose WCL is the optimal solution of optimization problem eq.(4.3), and denote its singular value decomposition as WCL = (UCLΣCLV >CL) >, then we have:
E‖ sin Θ(UCL, U?)‖F . √ r
α+ 1 ( r d log d+ √ d n ) + T √ dr m . (4.5)
Similar to Theorem 4.2, 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), Eq.(4.5) is reduced to T √ rd/m. This rate can be worse than the √ r3 log d/d+ √ rd/n rate obtained by self-supervised contrastive learning when m is small. Recall that when the number of tasks is small, labeled data introduce extra bias term √ r − 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 is sufficiently 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. 1 right panel. Consistent with our theory, it is observed that when tasks are not abundant, the transfer performance exhibit a U -shaped curve, and the best result is achieved by choosing an appropriate α. When tasks are abundant and labeled data are sufficient, the error remains small when we take large α.

heading: 5 CONCLUSION
text: 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 multi-task 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 et al., 2020; Tripuraneni et al., 2021), our work starts with linear representations, which still provides important insights. Extending the results to more complex models is an interesting direction of future work.

heading: A BACKGROUND

heading: A.1 DISTANCE BETWEEN SUBSPACES
text: In this section, we will provide some basic properties of sin Θ distance between subspaces. Recall that the definition is:
‖sin Θ (U1, U2)‖F , ∥∥U>1⊥U2∥∥F = ∥∥U>2⊥U1∥∥F . (A.1)
where U1, U2 ∈ Od,r are two orthogonal matrices. Similarly, we can also define: ‖sin Θ (U1, U2)‖2 , ∥∥U>1⊥U2∥∥2 = ∥∥U>2⊥U1∥∥2 . We first give two equivalent definition of this distance: Proposition A.1.
‖sin Θ (U1, U2)‖2F = r − ∥∥U>1 U2∥∥2F
Proof. Write U = [U1, U1⊥] ∈ Od,d we have : r = ‖U2‖2F = ‖U>U2‖2F = ∥∥U>1⊥U2∥∥2F + ∥∥U>1 U2∥∥2F , then by definition of sin Θ distance we can obtain the desired equation.

heading: Proposition A.2.
text: ‖sin Θ (U1, U2)‖2F = 1
2 ‖U1U>1 − U2U>2 ‖2F
Proof. Expand the right hand and use Proposition A.1 we have: 1
2 ‖U1U>1 − U2U>2 ‖2F =
1 2 (‖U1U>1 ‖2F + ‖U2U>2 ‖2F − 2 tr
( U1U > 1 U2U > 2 ) )
= 1
2 (r + r − 2 tr
( U>1 U2U > 2 U1 ) )
=r − ‖U>1 U2‖2F = ‖sin Θ (U1, U2)‖ 2 F .
With Proposition A.1 and A.2, it’s easy to verify its properties to be a distance function. Obviously, we have 0 ≤ ‖sin Θ (U1, U2)‖F ≤ √ r and ‖sin Θ (U1, U2)‖F = ‖sin Θ (U2, U1)‖F by definition. Moreover, we have the following results: Lemma A.1 (Lemma 1 in Cai & Zhang (2018)). For any U, V ∈ Od,r,
‖ sin Θ(U, V )‖2 ≤ inf O∈Or,r
‖UO − V ‖2 ≤ √ 2‖ sin Θ(U, V )‖2, (A.2)
and ‖ sin Θ(U, V )‖F ≤ inf
O∈Or,r ‖UO − V ‖F ≤
√ 2‖ sin Θ(U, V )‖F . (A.3)
Proposition A.3 (Identity of indiscernibles). ‖sin Θ (U1, U2)‖F = 0⇔ ∃O ∈ O r×r, s.t. U1O = U2
Proof. It’s a straightforward corollary by definition: ‖sin Θ (U1, U2)‖F = 0⇔ ∥∥U>1⊥U2∥∥F = 0⇔ U2⊥ ⊥ U1 ⇔ ∃O ∈ Or×r, s.t. U1O = U2.
Proposition A.4 (Triangular inequality). ‖sin Θ (U1, U2)‖F ≤ ‖sin Θ (U1, U3)‖F + ‖sin Θ (U2, U3)‖F
Proof. By the triangular inequality for Frobenius norm we have: ‖U1U>1 − U2U>2 ‖F ≤ ‖U1U>1 − U3U>3 ‖F + ‖U2U>2 − U3U>3 ‖F , then apply Proposition A.2 to replace the Frobenius norm with sin Θ distance we can finish the proof.

heading: A.2 PRINCIPAL COMPONENT ANALYSIS AND AUTOENCODERS
text: Autoencoders are popular unsupervised learning methods to perform dimension reduction. Its basic idea is to learn low dimensional representations for the original data while largely preserving its salient features. To achieve this goal, autoencoders learn two functions: encoder f : Rd → Rr and decoder g : Rr → Rd. While the encoder f compresses the high dimensional data to the low dimensional space, we try to recover the original data based on this low dimensional representation via the decoder g. Formally, it can be formulated to be the following optimization problem:
min f,g
ExL(x, g(f(x))). (A.4)
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, a commonly used form is to optimize the empirical loss function and choose the loss function to be mean squared error, that is:
min fAE ,gDE
1 n ‖xi − gDE(fAE(xi))‖22, ∀i ∈ [n], (A.5)
where fAE , gDE are usually two neural networks. Now if we take fAE , gDE to be both linear transformations, i.e.,
fAE(x) = WAEx+ bAE , g DE(x) = WDEx+ bDE ,
where WAE ∈ Rr×d, bAE ∈ Rr,WDE ∈ Rd×r, , bAE ∈ Rd, and denote X = [x1, · · · , xn] ∈ Rd×n, the optimization problem (A.5) can be reduced to be:
min WAE ,bAE ,WDE ,bDE
1 n ‖X − (WDE(WAEX + bAE1>n ) + bDE1>n )‖2F .
It’s shown in Bourlard & Kamp (2004) that the bias term can be reduced by centeralize the data matrix X , that is, denote x̄ = 1n ∑n i=1 xi as the sample mean and X0 = X − x̄1>n as the centered sample matrix, then the optimization problem correspond to WAE and WDE can be transfromed to be:
min WAE ,WDE
1 n ‖X0 −WDEWAEX0‖2F .
By Theorem 2.4.8 in (Golub & Loan, 1996), the optimal solution is given by the singular value decomposition of matrix X0, i.e., the eigenspace of X(In − 1n1n1 > n )X
>, 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)

heading: A.3 HILBERT-SCHMIDT INDEPENDENT CRITERIA
text: In Gretton et al. (2005), the Hilbert Schmidt Independent Criteria (HSIC) is proposed to measure the dependence between two random variables by computing the Hilbert-Schmidt norm of the crosscovariance operator associated with their Reproducing Kernel Hilbert Spaces (RKHSs). Such measurement has been widely used as supervised loss function in feature selection(Song et al., 2007c), feature extraction(Song et al., 2007a), clustering(Song et al., 2007b) and supervised PCA (Barshan et al., 2011).
The basic idea behind HSIC is that two random variables, named X and Y , are independent if and only if any bounded continuous function of the two random variables are uncorrelated. Let F be a separable RKHS containing all continuous bounded real-valued functions of x from X to R and G be that of Y , likewise. To each point x ∈ X , there corresponds an element φ(x) ∈ F such that 〈φ(x), φ (x′)〉F = k (x, x′), where k : X × X → R is a unique positive definite kernel. Likewise, define the kernel l(·, ·) and feature map ψ for G. Denote the joint measure of px,y , then the empirical HSIC is defined to be: Definition A.1 (Empirical HSIC (Gretton et al., 2005)). Let Z := {(x1, y1) , . . . , (xm, ym)} ⊆ X × Y be a series of m independent observations drawn from pxy . An estimator of HSIC, written HSIC(Z,F ,G), is given by
HSIC(Z,F ,G) := (m− 1)−2 tr(KHLH),
where H,K,L ∈ Rm×m,Kij := k (xi, xj) , Lij := l (yi, yj) and H = Im − 1m1m1 > m.
In our problems, we hope to maximize the dependency between learned features WX ∈ Rr×n and label y ∈ Rn via HSIC, equivalently maximize tr(KHLH) where K is a kernel of WX (e.g. X>W>WX) and L is a kernel of y (e.g. yy>). Then we obtain our supervised loss corresponding to parameter W :
HSIC(X, y;W ) = 1 (n− 1)2 tr ( X>W>WXHyy>H ) . (A.6)

heading: A.3.1 CONNECTION WITH MEAN SQUARED ERROR
text: In regression tasks, a more commonly used loss function is mean squared error:
LMSE(θ) = 1
n n∑ i=1 ‖f(xi, θ)− yi‖2F , (A.7)
where θ is model parameter. In our contrastive learning framework, where we first learn the representation via a linear transformation and then perform linear regression to learn a classifier w ∈ Rr 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, θ) = w>Wx.
Plug this formula back into mean squared error, we have:
LMSE(θ) = 1
n ‖w>WX − y>‖2F .
Since the label is a scalar, the optimal W will be singular since we perform a 1-dimensional projection 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(WX) = d, which can be achieved via joint optimization, the optimal solution of w is:
w? = (WXX>W>)−1WXy.
And the optimal error is:
L(W ) = 1 n ‖X>W>(WXX>W>)−1WXy − y‖2F
= 1
n (y>y − tr
( y>X>W>(WXX>W>)−1WXy ) ).
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 (WXX>W>)−1 which can be viewed as normalization of W . In our contrastive learning framework, this normalization can be achieved by the regularization term ‖WW>‖2F . Thus we can use the HSIC to replace the standard regression error which helps us to avoid dealing with singularity and additional parameters in optimization.

heading: B OMITTED PROOFS FOR SECTION 3

heading: B.1 PROOFS FOR SECTION 3.1
text: In this section, we will prove Theorem 3.1 and 3.2 in Section 3.1. The restatement and proof of them can be found in B.1 and B.3. Before starting the proof, we first provide a lemma to justify the order of I(U?) in the Assumption 3.3. Lemma B.1 (Expectation of incoherent constant over a uniform distribution).
EU∼Uniform(Od,r)I(U ?) = O ( r d log d ) . (B.1)
Before starting the proof, we give two technical lemmas to help the proof.
Lemma B.2 (Uniform distribution on the unit shpere (Marsaglia, 1972)). If x1, x2, · · · , xn i.i.d. ∼ N (0, 1), then (x1/ √∑n i=1 x 2 i , · · · , xn/ √∑n i=1 x 2 i ) is uniformly distributed on the unit sphere
Sd = {(x1, · · · , xn) ∈ Rn : ∑n i=1 x 2 i = 1}.
Lemma B.3. If x1, x2, · · · , xn i.i.d. ∼ N (0, 1), then:
E max 1≤i≤n x2i ≤ 2 log(n).
Proof. Denote Y = max1≤i≤n x2i , then we have:
exp(tEY ) ≤ E exp(tY ) ≤ E n∑ i=1 exp ( tx2i ) = nE exp ( tx2i ) .
Note that the moment-generating function of chi square distribution with v degrees of freedom is:
MX(t) = (1− 2t)−v/2.
Then combine this fact with equation B.1 we have:
exp(tEY ) ≤ n(1− 2t)− 12 ,
which implies:
EY ≤ log(n) t − 1− 2t 2t , ∀t < 1 2 .
In particular, take t→ 12 yields: EY ≤ 2 log(n)
as desired.
Proof of Lemma B.1. Denote the columns of U as U = [u1, · · · , ur] ∈ Od,r, we have:
EU∼Uniform(Od,r)I(U) =EU∼Uniform(Od,r) max i∈[d] r∑ j=1 |e>i uj |2
≤EU∼Uniform(Od,r) r∑ j=1 max i∈[d] |e>i uj |2
=rEu∼Uniform(Sd) max i∈[d] |e>i u|2.
By Lemma B.2 we can transform this expectation on the uniform sphere distribution into normalized multivariate Gaussian variables:
EU∼Uniform(Od,r)I(U) = rEx1,··· ,xd maxi∈[d] x 2 i∑d
j=1 x 2 j
. (B.2)
where x1, x2, · · · , xd are i.i.d. standard normal random variables. Apply Chebyshev’s inequality we know that:
P ( |1 d d∑ i=1 x2j − 1| > ) ≤ 2 d 2 .
In particular, take = 1 we have:
P ( d∑ i=1 x2j < d 2 ) ≤ 8 d .
Then take it back into equation B.2 and apply Lemma B.3 we obtain:
EU∼Uniform(Od,r)I(U) =rEx1,··· ,xd maxi∈[d] x 2 i∑d
j=1 x 2 j I{ d∑ i=1 x2j < d 2 }
+ rEx1,··· ,xd maxi∈[d] x 2 i∑d
j=1 x 2 j I{ d∑ i=1 x2j ≥ d 2 }
≤rP ( d∑ i=1 x2j < d 2 ) + 2r d Ex1,··· ,xd max i∈[d] x2i
≤8r d + 4r log d d
as desired.
Lemma B.1 demonstrates the expectation of incoherent constant over a uniform distribution on Od,r takes the order of O( rd log d), thus in the main body we take the order to be the same as it. Again we need to mention that the order can be chosen to be other functions that decrease to 0 when d→∞, 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, we 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 fAE : Rd → Rr and a decoder gDE : Rr → Rd, it can be formalized as solving the following optimization problem for samples {xi}ni=1
min fAE ,gAE
1
n n∑ i=1 ‖xi − gDE(fAE(xi))‖22.
In the linear representation setting, where fAE(x) = WAEx+ bAE and gDE(y) = WDEy + bDE , it has been shown that the optimal WAE is given by:
WAE = ( UAEΣAEV > AE )> , (B.3)
where UAE is top-r eigenspace of matrix M := X(I − 1n1>n /n)X>, ΣAE is a diagonal matrix consists of eigenvalues of M and VAE = [v1, · · · , vn] ∈ Rr×r 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-Kahan theorem provides a technique to estimate the eigenspace distance via estimate the difference between target matrices. We will adopt this technique to 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 Assumption 3.1-3.3 and n > d r, let WAE be the learned representation of autoencoder with singular value decomposition WAE = (UAEΣAEV >AE)
> (as in Eq.(3.1)). If we further assume {σ2i }di=1 are different from each other and σ2(1)/(σ 2 (r) − σ 2 (r+1)) < Cσ for some universal constant Cσ . Then there exist two universal constants Cρ > 0, c ∈ (0, 1), such that when ρ < Cρ, we have
E ‖sin Θ (U?, UAE)‖F ≥ c √ r. (B.4)
Proof. Denote M = ν2U?U?> to be the target matrix, xi = U?zi + ξi, i = 1, 2, · · ·n to be the samples generated from model 2.5 and let X = [x1, · · · , xn] ∈ Rd×n, Z = [z1, · · · , zn] ∈ Rr×n, E = [ξ1, · · · , ξn] ∈ Rd×n to be the corresponding matrices. In addition, we write the column mean matrix X̄ ∈ Rn×d of a matrix X ∈ Rn×d to be X̄ = 1nX1n1 > n , that is, each column of X̄ is the column mean of X . We denote the sum of variance σ2i as σ 2 sum = ∑d i=1 σ 2 i . As shown in B.3, autoencoder finds the top-r eigenspace of the following matrix:
M̂1 = 1
n X(In −
1 n 1n1 > n )X > = 1 n (U?Z + E)(U?Z + E)> − 1 n (U?Z̄ + Ē)(U?Z̄ + Ē)>.
The rest of the proof is divided into three steps for the sake of presentation.
Step 1, bound the difference between M̂1 and Σ. In this step, we aim to show that the data recovery of autoencoder is dominated by the random noise term. Note that Σ = Cov(ξ) = Eξξ>, we just need to bound the norm of the following matrix:
M̂1−Σ = 1
n U?ZZ>U?>+
1 n (U?ZE>+EZ>U?>)+( 1 n EE>−Σ)− 1 n (U?Z̄+Ē)(U?Z̄+Ē)>,
(B.5) and we will deal with these four terms separately.
1. For the first term, note that Ezz> = ν2Ir, the first term can then be divided into two terms
1 n U?ZZ>U?> = M + U?( 1 n ZZ> − Ezz>)U?>. (B.6)
Then apply the concentration inequality of Wishart-type matrices (Lemma D.3) we have:
E‖ 1 n ZZ> − Ezz>‖2 ≤ (
√ r
n + r n )ν2.
Plug it back into (B.6) we obtain the bound for the first term:
‖ 1 n UZZ>U>‖2 ≤ ‖M‖2 + ‖U‖2‖ 1 n ZZ> − Ezz>‖2‖U‖2 ≤
( 1 + √ r
n + r n
) ν2.
(B.7)
2. For the second term, since Z and E are independent, we must have EU?ZE> = 0, so apply Lemma D.2 twice we have:
1 n E‖EZ>U?‖2 = 1 n EZ [EE [‖EZ>U?‖2|Z]]
. 1
n EZ [‖Z‖2(σsum + r1/4
√ σsumσ(1) + √ rσ(1))]
. 1
n EZ [‖Z‖2]
√ dσ(1)
. 1
n
√ dσ(1)(r 1/2ν + (nr)1/4ν + n1/2ν)
. √ d√ n σ(1)ν.
(B.8)
3. For the third term, apply Lemma D.3 again yields:
E‖ 1 n EE> − Σ‖2 ≤
(√ d
n + d n
) σ2(1). (B.9)
4. For the last term, note that each columns of Z̄ and Ē are the same, so we can rewrite is as:
1 n (U?Z̄ + Ē)(U?Z̄ + Ē)> = (U?z̄ + ξ̄)(U?z̄ + ξ̄)>,
where z̄ = 1n ∑n i=1 zi and ξ̄ = 1 n ∑n i=1 ξi. Since z and ξ are independent zero mean sub-Gaussian random variables and Cov(z) = ν2Ir,Cov(ξ) = Σ, we can conclude that:
E‖ 1 n (U?Z̄ + Ē)(U?Z̄ + Ē)>‖2 ≤ E‖z̄z̄>‖2 + 2E‖z̄ξ̄>‖2 + E‖ξ̄ξ̄>‖2
. rν2
n + √ d√ n σ(1)ν + dσ2(1) n .
To sum up, combine equations (B.7)(B.8)(B.9)(4) together we obtain the upper bound for the 2 norm expectation of matrix M̂ − Σ:
E‖M̂1 − Σ‖2 . ν2 ( 1 + √ r
n + r n
) + σ2(1) (√ d
n + d n
) + √ d
n σ(1)ν. (B.10)
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., Σ. Note that Σ is assumed to be diagonal matrix with different elements, hence its eigenspace only consists of canonical basis ei. Denote UΣ to be the top-r eigenspace of Σ and {ei}i∈C to be its corresponding basis vectors, apply the Davis-Kahan Theorem D.1 we can conclude that:
E‖ sin Θ(UAE , UΣ)‖F ≤ 2 √ rE‖M̂1 − Σ‖2 σ2(r) − σ 2 (r+1)
. √ r 1
σ2(1)
( ν2 ( 1 + √ r
n + r n
) + σ2(1) (√ d
n + d n
) + √ d
n σ(1)ν
)
. √ r ( ρ2 + √ d
n + ρ
√ d
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 Θ(U?, UΣ)‖2F = ‖U>Σ⊥U?‖2F = ∑
i∈[d]/C ‖e>i U?‖2F = ‖U?‖2F − ∑ i∈C ‖e>i U?‖2F
≥ r − rI(U?) = r −O ( r2
d log d
) .
Then apply the triangular inequality of sin Θ distance (Proposition A.4) we can obtain the lower bound of autoencoder.
E‖ sin Θ(UAE , U?)‖F ≥ E‖ sin Θ(U?, UΣ)‖F − E‖ sin Θ(UAE , UΣ)‖F
≥ √ r −O ( r√ d √ log d ) −O ( √ r ( ρ2 + √ d n + ρ √ d n )) .
By Assumption 3.2, it implies that when n and d is sufficient large and ρ is sufficient small (smaller than a given constant Cρ > 0), there exist a universal constant c ∈ (0, 1) such that:
E‖ sin Θ(UAE , U?)‖F ≥ c √ r.
On the other hand, recall that the optimization problem for self-supervised contrastive learning has been formulated to be:
min W∈Rd×r − 1 n n∑ i=1  ∑ xPosi ∈BPosi 〈f(xi,W ), f(xPosi ,W )〉 |BPosi | − ∑ xNegi ∈B Neg i 〈f(xi, θ), f(xNegi ,W )〉 |BNegi | +λR(W ), (B.11) where f(x,W ) = Wx, R(W ) = ‖WW>‖2F /2. To compare contrastive learning with autoencoder, we now derive the optimal solution of the optimization problem B.11. Let’s start with the general result for self-supervised contrastive learning with augmented pairs generation (Definition 2.1), and then turn to the special case for random masking augmentation (Definition 2.2). Theorem B.2. For two fixed augmentation function g1, g2 : Rd → Rd, denote the augmented data matrices as X1 = [g1(x1), · · · , g1(xn)] ∈ Rd×n and X2 = [g2(x1), · · · , g2(xn)] ∈ Rd×n, when the augmented pairs are generated as in Definition 2.1, the optimal solution of contrastive learning problem (B.11) is given by:
WCL = C ( r∑ i=1 uiσiv > i )> ,
where C > 0 is a positive constant, σi is the i-th largest eigenvalue of the following matrix:
X1X > 2 +X2X > 1 −
1
2(n− 1) (X1 +X2)(1r1
> r − Ir)(X1 +X2)>, (B.12)
ui is the corresponding eigenvector and V = [v1, · · · , vn] ∈ Rr×r can be any orthonormal matrix.
Proof of Theorem B.2. When augmented pairs generation 2.1 is applied, the contrastive loss can be written as:
L(W ) =λ 2 ‖WW>‖2F − 1 n n∑ i=1 [〈Wt1(xi),Wt2(xi)〉
− 1 4(n− 1) ∑ j 6=i 〈Wt1(xi) +Wt2(xi),Wt1(xj) +Wt2(xi)〉]
= λ
2 ‖WW>‖2F −
1
n n∑ i=1 〈Wt1(xi),Wt2(xi)〉
+ 1
4n(n− 1) n∑ i=1 ∑ j 6=i 〈Wt1(xi) +Wt2(xi),Wt1(xj) +Wt2(xi)〉
= λ
2 ‖WW>‖2F −
1 2n tr ( X>1 W >WX2 +X > 2 W >WX1 )
+ 1 4n(n− 1) tr ( (1n1 > n − In)(X1 +X2)>W>W (X1 +X2) ) = λ
2 ‖WW>‖2F
− 1 2n tr
( (X2X > 1 +X1X > 2 −
1
2(n− 1) (X1 +X2)(1n1
> n − In)(X1 +X2)>)W>W ) = 1
2 ∥∥∥∥λW>W − 12nλ ( X2X > 1 +X1X > 2 −
1
2(n− 1) (X1 +X2)(1n1
> n − In)(X1 +X2)> )∥∥∥∥2 F
− ∥∥∥∥ 12nλ ( X2X > 1 +X1X > 2 −
1
2(n− 1) (X1 +X2)(1n1
> n − In)(X1 +X2)> )∥∥∥∥2 F .
Note that the last term only depends on X , and the first term implies that when WCL is the optimal solution, λWCLW>CL is the best rank-r approximation of 1 (n−1)λXHX
>. Then apply Lemma D.4 we can conclude that WCL satisfy the desired conditions.
Theorem B.2 shows a general result for augmented pairs generation with any augmentation. Specifically, 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 ∈ Rd×d, we denote D(A) to be A with all off-diagonal entries set to be zero and ∆(A) = A − D(A) to be A with all diagonal entries set to be zero. Then we have the following corollary for random masking augmentation.
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.11) is given by:
WCL = C ( r∑ i=1 uiσiv > i )> ,
where C > 0 is a positive constant, σi is the i-th largest eigenvalue of the following matrix:
∆(XX>)− 1 n− 1 X(1n1 > n − In)X>, (B.13)
ui is the corresponding eigenvector and V = [v1, · · · , vn] ∈ Rr×r can be any orthonormal matrix.
Proof of Corollary B.1. Following the proof of Theorem B.2, now we only need to compute the expectation over the augmentation distribution defined in 2.2:
L(W ) =λ 2 ‖WW>‖2F − E(t1,t2)∼T [ 1 n n∑ i=1 [〈Wt1(xi),Wt2(xi)〉
− 1 4(n− 1) ∑ j 6=i 〈Wt1(xi) +Wt2(xi),Wt1(xj) +Wt2(xi)〉]]
= λ
2 ‖WW>‖2F − E(t1,t2)∼T [
1
2n tr((X2X
> 1 +X1X > 2
− 1 2(n− 1) (X1 +X2)(1n1 > n − In)(X1 +X2)>)W>W )].
(B.14)
Note that by the definition of random masking augmentation, we have X1 = AX,X2 = (I −A)X , which implies X1 + X2 = X . On the other hand, X1 and X2 has disjoint nonzero dimensions, hence the matrix X1X>2 +X2X > 1 only consists of off-diagonal entries and each of the off-diagonal entry, let’s say xij , appears if and only if ai + aj = 1. Moreover, once it appears, we must have xij equals to the (i, j) element of XX>. With this result, we can then compute the expectation in equation (B.14):
L(W ) =λ 2 ‖WW>‖2F − E(t1,t2)∼T [ 1 2n tr((X2X > 1 +X1X > 2
− 1 2(n− 1) (X1 +X2)(1n1 > n − In)(X1 +X2)>)W>W )]
= λ
2 ‖WW>‖2F −
1
2n tr
( ( 1
2 ∆(XX>)− 1 2(n− 1) X(1n1 > n − In)X>)W>W ) = 1
2 ‖λW>W − 1 4nλ (∆(XX>)− 1 n− 1 X(1n1 > n − In)X>‖2F
− ‖ 1 4nλ (∆(XX>)− 1 n− 1 X(1n1 > n − In)X>‖2F .
By similar argument as in the proof of Theorem B.2, we can conclude that WCL satisfy the desired conditions.
Remark B.1. Note that the two views generated by random masking augmentation have disjoint non-zero dimensions, hence contrasting such positive pairs yields correlation between different dimensions only. That’s why the first term in equation (B.13) appears to be ∆(XX>) where the diagonal entries are 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 eliminate the effect of random noise on the diagonal entries of the observed covariance matrix. Since Cov(ξ) = Σ is a diagonal matrix, and by Assumption 3.3 we know that the diagonal entries Cov(U?z) = ν2U?U?> only take a 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 a more accurate estimation of core features. To start the proof, we introduce a technical lemma first. Lemma B.4 (Lemma 4 in Zhang et al. (2018)). If M ∈ Rp×p is any square matrix and ∆(M) is the matrix M with diagonal entries set to 0 , then
‖∆(M)‖2 ≤ 2‖M‖2. Here, the factor ” 2 ” in the statement above cannot be improved.
Then we turn to prove Theorem 3.2. Theorem B.3 (Restatement of Theorem 3.2). Under the spiked covariance model Eq.(2.5), random masking augmentation in Definition 2.2, Assumption 3.1-3.3 and n > d r, let WCL be any solution that minimizes Eq.(2.3), and denote its singular value decomposition as WCL = (UCLΣCLV > CL) >, then we have
E ‖sin Θ (U?, UCL)‖F . r3/2
d log d+
√ dr
n . (B.15)
Proof. The proof strategy is quite similar to that of Theorem 3.2 and we follow the notation defined in the first paragraph of that proof. As we have shown in Corollary B.1, under our linear representation setting, the contrastive learning algorithm finds the top-r eigenspace of the following matrix:
M̂2 = 1
n
( ∆(XX>)− 1
n− 1 X(1n1
> n − In)X> ) = 1
n ∆((U?Z + E)(U?Z + E)>)− 1 n− 1 (U?Z̄ + Ē)(U?Z̄ + Ē)>
+ 1
n(n− 1) (U?Z + E)(U?Z + E)>.
To prove the theorem, first we need to bound the difference between M̂2 andM . We aim to show that the contrastive learning algorithm is dominated by the core feature term. Note that Σ = EUzz>U>, we just need to bound the norm of the following matrix:
M̂2 −M =( 1 n ∆(U?ZZ>U?>)−M) + 1 n ∆(U?ZE> + EZ>U?>) + 1 n ∆(EE>)
− 1 n− 1 (U?Z̄ + Ē)(U?Z̄ + Ē)> + 1 n(n− 1) (U?Z + E)(U?Z + E)>.
(B.16)
and we will also deal with these five terms separately.
1. For the first term, we can divide it into two parts:
1 n ∆(U?ZZ>U?>)−M = ∆( 1 n U?ZZ>U?T −M) + ∆(M)−M. (B.17)
Then apply Lemma B.4 and Lemma D.3 we have:
E‖∆( 1 n U?ZZ>U?> −M)‖2 ≤ 2E‖ 1 n U?ZZ>U?> −M‖2 ≤ 2(
√ r
n + r n )ν2.
Using the incoherent condition I(U) = O( rd log d), we know that:
‖M −∆(M)‖2 ≤ ν2 max i∈[d] ‖e>i U?‖22 = ν2I(U?) .
r d log dν2.
Combine the two equations above together we obtain the bound for the first term:
E‖ 1 n ∆(U?ZZ>U?>)−M‖2 ≤ E‖∆( 1 n U?ZZ>U?> −M)‖2 + ‖M −∆(M)‖2
(B.18)
. ν2( r
d log d+
r n +
√ r
n ). (B.19)
2. For the second term, apply equation (B.8) yields:
1 n E‖∆(U?ZE> + EZ>U?>)‖2 ≤ 4 n E‖EZ>U?>‖2 . √ d√ n σ(1)ν. (B.20)
3. For the third term, apply equation (B.9) yields:
E‖ 1 n ∆(EE>)‖2 = E‖∆( 1 n EE>−Σ)‖2 ≤ 2‖ 1 n EE>−Σ‖2 . (
√ d
n + d n )σ2(1). (B.21)
4. For the fourth term, apply equation (4) yields:
E‖ 1 n− 1 (U?Z̄ + Ē)(UZ̄ + Ē)>‖2 .E‖ 1 n (UZ̄ + Ē)(UZ̄ + Ē)>‖2
. rν2
n + √ d√ n σ(1)ν + dσ2(1) n .
(B.22)
5. For the last term, by equations (B.7)(B.8)(B.9) we know:
E‖ 1 n (U?Z + E)(U?Z + E)>‖2
. ‖Σ‖2 + ( 1 + √ r
n + r n
) ν2 + √ d
n σ(1)ν +
(√ d
n + d n
) σ2(1).
Thus we can conclude that:
E‖ 1 n(n− 1) (U?Z + E)(U?Z + E)>‖2 . d n σ2(1) + r n ν2. (B.23)
To sum up, combine equations (B.18)(B.20)(B.21)(B.22)(B.23) together we obtain the upper bound for the 2 norm expectation of matrix M̂2 −M :
E‖M̂2 −M‖2 . ν2 ( r
d log d+
√ r
n + r n
) + σ2(1) (√ d
n + d n
) + σ(1)ν √ d
n . (B.24)
With the upper bound for ‖M̂2 −M‖2, simply apply Lemma D.1 we can obtain the desired bound for sin Θ distance:
E‖ sin Θ(UCL, U?)‖F ≤ 2 √ rE‖M̂2 −M‖2
ν2
. √ r 1
ν2
( ν2 ( r
d log d+
√ r
n + r n
) + σ2(1) (√ d
n + d n
) + σ(1)ν √ d
n
)
= √ r
(( r
d log d+
√ r
n + r n
) + ρ−2 (√ d
n + d n
) + ρ−1 √ d
n
)
. r3/2
d log d+
√ dr
n .
Moreover, there exists an orthogonal matrix Ô ∈ Or×r depending on UCL such that:
E‖U>UCLÔ − Ir‖F = E‖UCLÔ − U‖F ≤ 2 √ rE‖M̂2 −M‖2
ν2 . r3/2 d log d+
√ dr
n .
which finishes the proof.
In the following, we will show that our results do not change if we applied the same augmentation (2.2) for autoencoders, which indicates that our comparison is fair. As discussed in Section A.2, we can ignore the bias term in autoencoders for simplicity, which only serves as centralization of the data matrix. In that case, we applied random augmentation t1(x) = Ax and t2(x) = (I − A)x to the original data {xi}ni=1, and the optimization problem can be formulated as follows:
min WAE ,WDE
1
2n EA[‖AX −WDEWAEAX‖2F + ‖(I −A)X −WDEWAE(I −A)X‖2F ]. (B.25)
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 = W > DE = C ( r∑ i=1 uiσiv > i )> ,
where C > 0 is a positive constant, σi is the i-th largest eigenvalue of the following matrix:
1 2 ∆(XX>) +D(XX>), (B.26)
ui is the corresponding eigenvector and V = [v1, · · · , vn] ∈ Rr×r can be any orthonormal matrix.
Proof. We first derive the equivalent form for this objective function:
1
2n EA[‖AX −WDEWAEAX‖2F + ‖(I −A)X −WDEWAE(I −A)X‖2F ]
= 1
2n EA[tr
( X>A>AX ) + tr ( X>A>WDEWAEAX ) + tr ( X>A>W>AEW > DEWDEWAEAX ) + tr ( X>(I −A)>(I −A)X ) + tr ( X>(I −A)>WDEWAE(I −A)X
) + tr ( X>(I −A)>W>AEW>DEWDEWAE(I −A)X ) ]
= 1
2n EA[tr
( X>AX ) + tr ( AXX>A>WDEWAE ) + tr ( AXX>A>W>AEW > DEWDEWAE ) + tr ( X>(I −A)X ) + tr ( (I −A)XX>(I −A)>WDEWAE
) + tr ( (I −A)XX>(I −A)>W>AEW>DEWDEWAE ) ]
= 1
2n EA[tr
( X>X ) + tr(MWDEWAE) + tr ( MW>AEW > DEWDEWAE ) ],
(B.27) where M := AXX>A> + (I − A)XX>(I − A)>. Note that by Definition 2.2 we have A = diag(a1, · · · , ad) and ai follows the Bernoulli distribution, so we have:
EAM = 1
2 ∆(XX>) +D(XX>) (B.28)
Again, by Theorem 2.4.8 in (Golub & Loan, 1996), the optimal solution of B.25 is given by the eigenvalue decomposition of EAM = 12∆(XX
>)+D(XXT ), up to an 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.(2.5), under Assumption 3.1-3.3 and n > d r, let WAE be the learned representation of augmented autoencoder with singular value decomposition WAE = (UAEΣAEV >AE)
> (i.e., the optimal solution of optimization problem B.25). If we further assume {σ2i }di=1 are different from each other and σ2(1)/(σ 2 (r)−σ 2 (r+1)) < Cσ for some universal constant Cσ . Then there exist two universal constants Cρ > 0, c ∈ (0, 1), such that when ρ < Cρ, we have
E ‖sin Θ (U?, UAE)‖F ≥ c √ r. (B.29)
Proof. Step1, similar to the proof of Theorem B.1, we first bound the difference between M̂ := ∆(XX>) + 2D(XX>) and Σ := Cov(ξξ>). Note that:
‖M̂ −Σ‖2 = ‖XX> −Σ− 1
2 ∆(XX>)‖2 ≤ ‖XX> −Σ‖2 +
1 2 ‖∆(XX> −Σ)‖2 + 1 2 ‖∆(Σ)‖2
(B.30) Since Σ is a diagonal matrix, then by Lemma B.4 we have:
‖M̂ − Σ‖2 ≤ 2‖XX> − Σ‖2 (B.31)
Now, directly apply equation (B.7)(B.8)(B.9) we can obtain that:
E‖M̂ − Σ‖2 . ν2 ( 1 + √ r
n + r n
) + σ2(1) (√ d
n + d n
) + √ d
n σ(1)ν. (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., Σ. Note that Σ is assumed to be diagonal matrix with different elements, hence its eigenspace only consists of canonical basis ei. Denote UΣ to be the top-r eigenspace of Σ and {ei}i∈C to be its corresponding basis vectors, apply
the Davis-Kahan Theorem D.1 we can conclude that:
E‖ sin Θ(UAE , UΣ)‖F ≤ 2 √ rE‖M̂ − Σ‖2 σ2(r) − σ 2 (r+1)
. √ r 1
σ2(1)
( ν2 ( 1 + √ r
n + r n
) + σ2(1) (√ d
n + d n
) + √ d
n σ(1)ν
)
. √ r ( ρ2 + √ d
n + ρ
√ d
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 Θ(U?, UΣ)‖2F = ‖U>Σ⊥U?‖2F = ∑
i∈[d]/C ‖e>i U?‖2F = ‖U?‖2F − ∑ i∈C ‖e>i U?‖2F
≥ r − rI(U?) = r −O ( r2
d log d
) .
Then apply the triangular inequality of sin Θ distance (Proposition A.4) we can obtain the lower bound of autoencoder.
E‖ sin Θ(UAE , U?)‖F ≥ E‖ sin Θ(U?, UΣ)‖F − E‖ sin Θ(UAE , UΣ)‖F
≥ √ r −O ( r√ d √ log d ) −O ( √ r ( ρ2 + √ d n + ρ √ d n )) .
By Assumption 3.2, it implies that when n and d is sufficient large and ρ is sufficient small (smaller than a given constant Cρ > 0), there exist a universal constant c ∈ (0, 1) such that:
E‖ sin Θ(UAE , U?)‖F ≥ c √ r.
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.

heading: B.2 PROOFS FOR SECTION 3.2
text: In this section, we will provide the proof of Theorem 3.3 and 3.4 with both regression and classification settings. The statement and detailed proof can be found in Theorem B.6 and B.7.
Before going onto the proof, we clarify our models and assumptions. Let WCL and WAE be the learned representations based on train data X ∈ Rn×d. We observe a new signal x̌ = U?ž + ξ̌ independent of X following the spiked covariance model 2.5. For simplicity, assume ž ∼ N(0, ν2Ir) and ξ̌ ⊥ ž. We consider the two major types of downstream tasks: classification and regression. For binary classification task, we observe a new supervised sample y̌ following the binary response model:
y̌|ž = Ber(F (〈ž, w?〉/ν)), (B.33)
where F : R → [0, 1] is a known monotone increasing function satisfying 1 − F (u) = F (−u) for any u ∈ R. Notice that our model B.33 includes logistic models (when F (u) = 1/(1 + e−u)) and probit models (when F (u) = Φ(u), where Φ is the cumulative distribution function of standard normal distribution.) We can also interpret model B.33 as a shallow neural network model with width r for binary classification. For regression task, we observe a new supervised sample y̌ following the linear regression model:
y̌ = 〈ž, w?〉/ν + ̌, (B.34)
where ̌ ∼ (0, σ2 ) is independent of ž.
In classification setting, we specify 0-1 loss, i.e., `c(δ) , I{y̌ 6= δ(x̌)} for some predictor δ taking values in {0, 1}. For regression task, we employ squared error loss `r(δ) , (y̌ − δ(x̌))2. Based on some learned representation W , we consider a class of linear predictors, i.e., δW,w(x̌) , I{F (w>Wx̌) ≥ 1/2} for classification task and δW,w(x̌) , w>Wx̌ for regression task, where w ∈ Rr is a weight vector w ∈ Rr. Note that the learned representation depends only on unsupervised samples X . Let ED[·] and EE [·] the expectations with respect to (X,Z) and (y̌, x̌, ž), respectively.
For notational simplicity, define the prediction risk of predictor δ for classification and regression tasks as Rc(δ) := ED[`c(δ)] and Rr(δ) := ED[`r(δ)], respectively. Define Σx := ν2U?U?> + Σ. Since any representation W can be decomposed into W = V ΣWU> by singular value decomposition, where U ∈ Od,r, {δW,w : w ∈ Rr} = {δU>,w : w ∈ Rr}. Thus we write δU,w for δW,w with a slight abuse of notation. Our goal as stated above is to bound the prediction risk of predictors {δW,w : w ∈ Rr} constructed upon the learned representations WCL and WAE , i.e., the quantity infw∈Rr EE [`(δWCL,w)] and infw∈Rr EE [`(δWAE ,w)].
Now we state our result on the downstream task.
Theorem B.6 (Excess Risk for Downstream Task: Upper Bound). Suppose the conditions in Theorem 3.2 hold. Then, for classification task, we have
ED[ inf w∈Rr EE [`c(δWCL,w)]− inf w∈Rr EE [`c(δU?,w)] = O
( r3/2
d log d+
√ dr
n
) ∧ 1,
and for regression task,
ED[ inf w∈Rr EE [`r(δWCL,w)]− inf w∈Rr EE [`r(δU?,w)] = O
( r3/2
d log d+
√ dr
n
) .
We obtain the lower bound for the downstream predction risk with autoencoders.
Theorem B.7. Suppose the conditions in Theorem 3.1 hold. Suppose r ≤ rc for some constant rc > 0. Additionally assume that ρ = Θ(1) is sufficiently small and n d r. For classification task, assume F is differentiable at 0 and F ′(0) > 0. Then,
ED[ inf w∈Rr EE [`c(δUAE ,w)]− inf w∈Rr EE [`c(δU?,w)] & 1.

heading: For regression task,
text: ED[ inf w∈Rr EE [`r(δUAE ,w)]− inf w∈Rr EE [`r(δU?,w)] & 1.
For two matricesA andB of the same order, we defineA B whenA−B is positive semi-definite. The proofs of Theorem B.6 and B.7 relies on Lemma B.8, B.9, B.10, B.11 and B.12 which are proved later in this section.
Proof of Theorem B.6: Classification Task Part. Lemma B.10 gives for any U ∈ Od,r,
ED[ inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)]
≤ ((κ(1 + ρ2))3 + κρ2(1 + ρ−2)2 + (κρ2 ∨ 1)−1)ED[‖ sin Θ(U,U?)‖2].
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 κ = O(1), (1 + ρ−2)/(1 + κ−1ρ−2)2 = O(1). Lemma B.12 gives for any U ∈ Od,r,
ED[ inf w∈Rr Rr(δU,w)− inf w∈Rr
Rr(δU?,w)] = O ( (1 + ρ−2)ED[‖ sin Θ(U,U?)‖2]‖w?‖2 ) .
Theorem 3.2 with substitution U ← UAE gives the desired result.
Proof of Theorem B.7: Classification Part. Lemma B.9 gives that for c1 := 1− 1/(2κrc) ∈ (0, 1), we can take n d r and sufficiently small ρ > 0 so that ED[‖ sin Θ(UAE , U?)‖2F ] ≥ c1r holds. By Lemma B.11,
ED[ inf w∈Rr Rc(δUAE ,w)− inf w∈Rr Rc(δU?,w)]
& (1 + ρ2)3/2 (1 + κρ2)3/2 ρ2 ( 1 1 + ρ2 − κ(r − ‖ sin Θ(UAE , U?)‖2F ) ) (B.35)
≥ (1 + ρ 2)3/2 (1 + κρ2)3/2 ρ2 ( 1 1 + ρ2 − κ(1− c1)r ) (B.36)
≥ (1 + ρ 2)3/2 (1 + κρ2)3/2 ρ2 ( 1 1 + ρ2 − 1 2 ) , (B.37)
where the last inequality follows since r ≤ rc. If we further take ρ = Θ(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 w∈Rr Rr(δUAE ,w)− inf w∈Rr Rr(δU?,w)
= w?>((I + (1/ν2)U?>ΣU?)−1
− U?>UAE(U>AEU?U?>UAE + (1/ν2)U>AEΣUAE)−1U>AEU?)w?.
Thus from Lemma B.8,
inf w∈Rr Rr(δUAE ,w)− inf w∈Rr Rr(δU?,w) ≥ ( 1
1 + ρ−2 + ρ2κ
( ‖ sin Θ(UAE , U?)‖2F − r )) ‖w?‖2.
Using Lemma B.9 and by the same argument in the proof of Theorem B.7: Classification Part, we conclude the proof.
Lemma B.5. For any U ∈ Od,r,
λmin(ν 2U?>U(U>ΣxU) −1U>U?) ≥ ν 2
ν2 + σ2(1) (1− ‖ sin Θ(U,U?)‖22).
Proof. Since λmin(AC) ≥ λmin(A)λmin(C) for symmetric positive semi-definite matrices A and C,
λmin(ν 2U?>U(U>ΣxU) −1U>U?)
≥ λmin(U>U?U?>U)λmin(ν2(U>ΣxU)−1)
≥ λmin(I − (I − U>U?U?>U)) ν2
λmax(ν2U>U?U?>U + U>ΣU)
≥ ν 2
ν2 + σ2(1) (1− ‖ sin Θ(U,U?)‖22),
where we used Weyl’s inequality λmin(A+ C) ≥ λmin(A)− ‖C‖2 in the second inequality.
Lemma B.6. For any U ∈ Od,r,
λmax(ν 2U?>U(U>ΣxU) −1U>U?) ≤ ν 2
ν2(1− ‖ sin Θ(U,U?)‖2) + σ2(d) .
Proof. Since ‖AC‖2 ≤ ‖A‖2‖C‖2,
λmax(ν 2U?>U(U>ΣxU) −1U>U?) ≤ λmax(ν2(U>ΣxU)−1)
≤ ν 2
λmin(ν2U>U?U?>U + U>ΣU)
≤ ν 2
λmin(ν2I − ν2(I − U>U?U?>U) + U>ΣU)
≤ ν 2
ν2(1− ‖ sin Θ(U,U?)‖2) + σ2(d) ,
where we used Weyl’s inequality λmin(A + C) ≥ λmin(A) − ‖C‖2 and λmin(ν2I + U>ΣU) ≥ ν2 + σ2(d).
Lemma B.7. For any U ∈ Od,r,
‖ν2(U?>ΣxU?)−1 − ν2U?>U(U>ΣxU)−1U>U?‖2
= O
( 1
1− ‖ sin Θ(U,U?)‖22 + κ−1ρ−2 1 + ρ−2 1 + κ−1ρ−2 ‖ sin Θ(U,U?)‖2
) .
Proof. Observe that
‖(U?>ΣxU?)−1 − U?>U(U>ΣxU)−1U>U?‖2 ≤ ‖(U?>ΣxU?)−1 − (U>ΣxU)−1‖2 + ‖(U>ΣxU)−1 − U?>U(U>ΣxU)−1U>U?‖2 := (T1) + (T2).
For the term (T1),
(T1) = ‖(U>ΣxU)−1(U>ΣxU)(U?>ΣxU?)−1 − (U>ΣxU)−1(U?>ΣxU?)(U?>ΣxU?)−1‖2 ≤ ‖(U>ΣxU)−1‖2‖U>ΣxU − U?>ΣxU?‖2‖(U?>ΣxU?)−1‖2.
Note
‖U>ΣxU − U?>ΣxU?‖2 = ‖ν2U>U?U?>U − ν2I + U>ΣU − U?>ΣU?‖2 ≤ ν2‖ sin Θ(U,U?)‖22 + ‖U>Σ(U − U?) + (U − U?)>ΣU?‖2 ≤ ν2‖ sin Θ(U,U?)‖22 + 2σ2(1)‖U − U ?‖2.
Also we have λmin(U>ΣxU) ≥ ν2(1−‖ sin Θ(U,U?)‖22)+σ2(d) from the proof of Lemma B.6 and λmin(U ?>ΣxU ?) ≥ ν2 + σ2(d). Therefore
(T1) ≤ 1 (ν2 + σ2(d))(ν 2(1− ‖ sin Θ(U,U?)‖22) + σ2(d)) (ν2‖ sin Θ(U,U?)‖22 + 2σ2(1)‖U − U ?‖2).
For the term (T2),
(T2) = ‖(U>ΣxU)−1 − U?>(U? + (U − U?))(U>ΣxU)−1(U? + (U − U?))>U?‖2 = ‖ − U?>(U − U?)(U>ΣxU)−1 − (U>ΣxU)−1(U − U?)>U?
− U?>(U − U?)(U>ΣxU)−1(U − U?)>U?‖2
≤ 1 ν2(1− ‖ sin Θ(U,U?)‖22) + σ2(d) (2‖U − U?‖2 + ‖U − U?‖22).
From Lemma A.1, ‖ sin Θ(U,U?)‖2 ≤ ‖U − U?‖2. Finally from these results and ‖U − U?‖22 ≤ 2‖U − U?‖2,
‖ν2(U?>ΣxU?)−1 − ν2U?>U(U>ΣxU)−1U>U?‖2
= O
( ν2
ν2(1− ‖ sin Θ(U,U?)‖22) + σ2(d)
ν2 + σ2(1) ν2 + σ2(d) ‖U − U?‖2
) .
Since LHS does not depend on the orthogonal transformation U ← UO where O ∈ Or,r, we obtain
‖ν2(U?>ΣxU?)−1 − ν2U?>U(U>ΣxU)−1U>U?‖2
= O
( ν2
ν2(1− ‖ sin Θ(U,U?)‖22) + σ2(d)
ν2 + σ2(1) ν2 + σ2(d) inf O∈Or,r ‖UO − U?‖2
) .
Combined again with Lemma A.1, we obtain the desired result.
Lemma B.8. For any U ∈ Od,r,
λmin(ν 2(U?>ΣxU ?)−1 − ν2U?>U(U>ΣxU)−1U>U?)
≥ ν 2 ν2 + σ2(1) − ν 2 σ2(d) (r − ‖ sin Θ(U,U?)‖2F ).
Proof. Observe
λmin(ν 2(U?>ΣxU ?)−1 − ν2U?>U(U>ΣxU)−1U>U?) ≥ λmin((I + (1/ν2)U?>ΣU?)−1)− ‖U?>U(U>U?U?>U + (1/ν2)U>ΣU)−1U>U?‖2.
Since U>U?U?>U 0, it follows that (U>U?U?>U + (1/ν2)U>ΣU)−1 ν2(U>ΣU)−1. Thus
‖U?>U(U>U?U?>U + (1/ν2)U>ΣU)−1U>U?‖2 ≤ ν2λmax((U>ΣU)−1)‖U?>U‖22
≤ ν 2
σ2(d) ‖U?>U‖2F
= ν2
σ2(d) (r − ‖ sin Θ(U,U?)‖2F ),
where we used λmax((U>ΣU)−1) ≤ 1/λmin(U>ΣU) ≤ 1/σ2(d) and ‖sin Θ (U1, U2)‖ 2 F = r −∥∥U>1 U2∥∥2F from Proposition A.1. Combined with Lemma B.6, we obtain
λmin(ν 2(U?>ΣxU ?)−1 − ν2U?>U(U>ΣxU)−1U>U?)
≥ ν 2 ν2 + σ2(1) − ν 2 σ2(d) (r − ‖ sin Θ(U,U?)‖2F ).
Lemma B.9. Suppose the conditions in Theorem 3.1 hold. Fix c1 ∈ (0, 1). There exists a constant c2 > 0such that if √ r log d/d ∨ ρ2 ∨ d/n < c2, then
ED‖ sin Θ(UAE , U?)‖2F ≥ c1r,
where c1 ∈ (0, 1) is a universal constant.
Proof. By Cauchy-Schwartz inequality,
ED‖ sin Θ(UAE , U?)‖2F − r ≥ (ED‖ sin Θ(UAE , U?)‖F )2 − r = (ED‖ sin Θ(UAE , U?)‖F − √ r) ( ED‖ sin Θ(UAE , U?)‖F + √ r ) .
From Theorem 3.1, there exists a constant c3 > 0 such that
ED ‖sin Θ (U?, UAE)‖F ≥ √ r − c3 r√ d
√ log d− c3 √ r ( ρ2 + √ d
n + ρ
√ d
n
) .
Therefore combined with a trivial bound ‖ sin Θ(UAE , U?)‖F ≤ √ r,
ED‖ sin Θ(UAE , U?)‖2F − r ≥ −rc3 ( r1/2√ d √ log d+ ρ2 + √ d n + ρ √ d n )
≥ −rc3 ( 2 r1/2√ d √ log d ∨ 6ρ2 ∨ 6 √ d n ) ,
where we used ρ √ d/n ≤ ρ2∨d/n ≤ ρ2∨ √ d/n since d < n. Thus we can take c2 = 6(1−c1)/c3. This concludes the proof.
Lemma B.10. For any U ∈ Od,r,
ED[ inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)]
≤ ((κ(1 + ρ2))3 + κρ2(1 + ρ−2)2 + (κρ2 ∨ 1)−1)ED[‖ sin Θ(U,U?)‖2].
Proof. Recall that we are considering the class of linear classifiers {δU,w : w ∈ Rr}, where δU,w(x̌) = I{F (x̌>Uw) > 1/2}. For notational simplicity, write β := Uw and β? := U?w?.
Rc(δU,w) = PE(δU,w(x̌) 6= y̌) = PE(y̌ = 0, F (x̌>β) > 1/2) + PE(y̌ = 1, F (x̌>β) ≤ 1/2).
Since F (0) = 1/2 and F is monotone increasing, the false positive probability becomes
PE(y̌ = 0, F (x̌>β) > 1/2) = PE(y̌ = 0, x̌>β > 0) = EE [EE [I{y̌ = 0}|x̌, ž]I{x̌>β > 0}] = EE [(1− F (ν−1ž>U?>β?))I{x̌>β > 0}].
Write ω := x̌>β and ω? := ν−1ž>U?>β?. From assumption, (ω?, ω) jointly follows a normal distribution with mean 0. Write v?2 := Var(ω?) = w?>w?, v2 := Var(ω) = β>Σxβ, where Σx := ν
2U?U?> + Σ. Let τ := Cor(ω?, ω) = νw?>U?>β/(v?v). By a formula for conditional normal distribution, we have ω|ω? ∼ N(τvω?/v?, v2(1− τ2)). This gives
PE(y̌ = 0, F (x̌>β) > 1/2) = EE [(1− F (ω?))I{ω > 0}] = EE [(1− F (ω?))EE [I{ω > 0}|ω?]] = EE [(1− F (ω?))PE(ω > 0|ω?)]
= EE [ (1− F (ω?))PE ( ω − τvω?/v?
v(1− τ2)1/2 > − τvω
?/v?
v(1− τ2)1/2 ∣∣∣∣ω?)] = EE [(1− F (ω?))Φ(αω?/v?)] = EE [(1− F (ω?))Φ(αω?/v?)I{ω? > 0}] + EE [(1− F (ω?))Φ(αω?/v?)I{ω? < 0}],
where Φ is cumulative distribution function of N(0, 1) and α := τ/(1 − τ2)1/2. We define ΨF as ΨF (s
2) := 2Eu∼N(0,s2)[F (u)I{u > 0}]. When F (u) = 1/(1+e−u), ΨF (s2) is called the logisticnormal integral, whose analytical form is not known (Pirjol (2013)). Since a random variable ω? is symmetric about mean 0 and F (u) = 1− F (−u),
EE [(1− F (ω?))Φ(αω?/v?)I{ω? < 0}] = EE [(1− F (−ω?))(1− Φ(αω?/v?))I{ω? > 0}] = EE [F (ω?)(1− Φ(αω?/v?))I{ω? > 0}].
Hence
PE(y̌ = 0, F (x̌>β) > 1/2) = EE [(Φ(αω?/v?) + F (ω?)− 2F (ω?)Φ(αω?/v?))I{ω? > 0}]
= 1
2 ΨF (v
?2)− EE [(2F (ω?)− 1)Φ(αω?/v?)I{ω? > 0}].
Note that the true negative probability is exactly the same as the false positive probability under our settings:
PE(y̌ = 1, F (x̌>β) ≤ 1/2) = EE [F (x̌>β?)I{x̌>β ≤ 0}] = EE [F (−x̌>β?)I{x̌>β ≥ 0}] = EE [(1− F (x̌>β?))I{x̌>β ≥ 0}] = PE(y̌ = 0, F (x̌>β) > 1/2).
Therefore
Rc(δU,w) = ΨF (v?2)− 2EE [(2F (ω?)− 1)Φ(αω?/v?)I{ω? > 0}]. Let
τmax,U := sup w∈Rr
νw?>U?>Uw/(w?>w?w>U>ΣxUw) 1/2,
τmax,U? := sup w∈Rr
νw?>w/(w?>w?w>U?>ΣxU ?w)1/2.
From Cauchy-Schwartz inequality,
τ2max,U = ν2w?>U?>U(U>ΣxU) −1U>U?w?
w?>w? ,
τ2max,U? = ν2w?>(U?>ΣxU ?)−1w?
w?>w? .
Define αmax,U := τmax,U/(1 − τ2max,U )1/2 and αmax,U? := τmax,U?/(1 − τ2max,U?)1/2. Then, since on the event where ω? > 0, α 7→ Φ(αω?/v?) is monotone increasing and 2F (w?) − 1 is non-negative, we have
inf w∈Rr
Rc(δU,w) = ΨF (v?2)− 2EE [(2F (ω?)− 1)Φ(αmax,Uω?/v?)I{ω? > 0}]
inf w∈Rr
Rc(δU?,w) = ΨF (v?2)− 2EE [(2F (ω?)− 1)Φ(αmax,U?ω?/v?)I{ω? > 0}].
This yields
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
= 2EE [(2F (ω?)− 1)(Φ(αmax,U?ω?/v?)− Φ(αmax,Uω?/v?))I{ω? > 0}]. Note that for any a, b ≥ 0,
|Φ(b)− Φ(a)| ≤ φ(a ∧ b)|b− a|, where φ is a density function of standard normal distribution. Observe
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
≤ 2EE [(2F (ω?)− 1)|Φ(αmax,U?ω?/v?)− Φ(αmax,Uω?/v?)|I{ω? > 0}]
. 2
v? ∫ ∞ 0 (2F (ω?)− 1)|αmax,U? − αmax,U |ω?φ((αmax,U? ∧ αmax,U )ω?/v?) φ(ω?/v?) v? dω?
. |αmax,U? − αmax,U |
v?
∫ ∞ 0 (2F (ω?)− 1)φ((αmax,U? ∧ αmax,U )ω?/v?) dω?
= |αmax,U? − αmax,U | αmax,U? ∧ αmax,U ∫ ∞ 0 (2F (ω?)− 1) exp ( −1/(2((αmax,U? ∧ αmax,U )−2v?2))ω?2 )√ 2π((αmax,U? ∧ αmax,U )−2v?2) dω?
= |αmax,U? − αmax,U | αmax,U? ∧ αmax,U (ΨF (((αmax,U? ∧ αmax,U?)−2v?2))− 1/2),
where we used supu>0 uφ(u) < ∞. Since (a − b) = (a2 − b2)/(a + b) ≤ (a2 − b2)/(a ∧ b) for a, b > 0, and ΨF ≤ 1, we obtain
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w) . |α2max,U? − α2max,U | α2max,U? ∧ α2max,U .
When τmax,U? ≥ τmax,U , since τ 7→ τ2/(1− τ2) is increasing in τ > 0,
inf w∈Rr Rc(δU,w)− inf w∈Rr
Rc(δU?,w) . α2max,U? − α2max,U
α2max,U
= τ2max,U? − τ2max,U
(1− τ2max,U?)τ2max,U . (B.38)
From Lemma B.5 and B.6, we have
ν2
ν2 + σ2(1) (1− ‖ sin Θ(U,U?)‖22) ≤ τ2max,U ≤
ν2
ν2(1− ‖ sin Θ(U,U?)‖22) + σ2(d) ,
ν2
ν2 + σ2(1) ≤ τ2max,U? ≤
ν2
ν2 + σ2(d) . (B.39)
Then, equation B.38 becomes
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
. ν2 + σ2(d)
σ2(d)
ν2 + σ2(1)
ν2(1− ‖ sin Θ(U,U?)‖22) (τ2max,U? − τ2max,U )
≤ ν2 + σ2(d)
σ2(d)
ν2 + σ2(1)
ν2(1− ‖ sin Θ(U,U?)‖22) ‖ν2(U?>ΣxU?)−1 − ν2U?>U(U>ΣxU)−1U>U?‖2
≤ (κρ 2 + 1)(ρ−2 + 1)2
(1 + κ−1ρ−2)(1− ‖ sin Θ(U,U?)‖22)2 ‖ sin Θ(U,U?)‖2
= κρ2(ρ−2 + 1)2
(1− ‖ sin Θ(U,U?)‖22)2 ‖ sin Θ(U,U?)‖2.
where the last inequality follows from Lemma B.7.
On the event where ‖ sin Θ(U,U?)‖22 ≤ 1/2,
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w) . κρ2(1 + ρ−2)2‖ sin Θ(U,U?)‖2.
When τmax,U? < τmax,U , on the event where ‖ sin Θ(U,U?)‖2 ≤ κ−1ρ−2/2,
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
. ν2 + σ2(1)
ν2
ν2(1− ‖ sin Θ(U,U?)‖22) + σ2(d) −ν2‖ sin Θ(U,U?)‖22 + σ2(d) (τ2max,U − τ2max,U?)
≤ (ν2 + σ2(1)) 2
ν2 1
−ν2‖ sin Θ(U,U?)‖22 + σ2(d) × ‖ν2(U?>ΣxU?)−1 − ν2U?>U(U>ΣxU)−1U>U?‖2
≤ (1 + ρ −2)3
(−‖ sin Θ(U,U?)‖22 + κ−1ρ−2)3 ‖ sin Θ(U,U?)‖2
. (κ(1 + ρ2))3‖ sin Θ(U,U?)‖2,
where we used Lemma B.7 again.
In summary, on the event where ‖ sin Θ(U,U?)‖2 ≤ κ−1ρ−2/2 ∧ 1/2,
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
. ((κ(1 + ρ2))3 + κρ2(1 + ρ−2)2)‖ sin Θ(U,U?)‖2.
On the other hand, on the event where ‖ sin Θ(U,U?)‖2 > κ−1ρ−2/2 ∧ 1/2, we have a trivial inequality infw∈Rr Rc(δU,w)− infw∈Rr Rc(δU?,w) ≤ 1. This gives
ED[ inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)]
. ((κ(1 + ρ2))3 + κρ2(1 + ρ−2)2)ED[‖ sin Θ(U,U?)‖2] + PD(‖ sin Θ(U,U?)‖2 > κ−1ρ−2/2 ∧ 1/2)
. ((κ(1 + ρ2))3 + κρ2(1 + ρ−2)2 + (κρ2 ∨ 1))ED[‖ sin Θ(U,U?)‖2], where the last inequality follows from Markov’s inequality.
Lemma B.11. Suppose U ∈ Od,r satisfies 1/(1 + ρ2)− κ(r − ‖ sin Θ(U,U?)‖2F ) ≥ 0. Then, inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
& (1 + ρ2)3/2 (1 + κρ2)3/2 ρ2 ( 1 1 + ρ2 − κ(r − ‖ sin Θ(U,U?)‖2F ) ) .
Proof. We firstly bound the term τ2max,U? − τ2max,U . From Lemma B.8,
τ2max,U? − τ2max,U ≥ λmin(ν2(U?>ΣxU?)−1 − ν2U?>U(U>ΣxU)−1U>U?)
≥ ν 2 ν2 + σ2(1) − ν 2 σ2(d) (r − ‖ sin Θ(U,U?)‖2F ). (B.40)
From assumption, RHS of equation B.40 is non-negative. Then using the inequality a− b = (a2 − b2)/(a+ b) ≥ (a2 − b2)/(2a) for a ≥ b ≥ 0,
αmax,U? − αmax,U & 1
αmax,U? (α2max,U? − α2max,U?)
≥ (1− τ2max,U?)1/2
τmax,U?
τ2max,U? − τ2max,U (1− τ2max,U?)(1− τ2max,U ) .
From equation B.39 and equation B.40,
αmax,U? − αmax,U
&
( ν2 + σ2(d)
ν2
)1/2( ν2 + σ2(1)
σ2(1)
)3/2( ν2
ν2 + σ2(1) − ν
2
σ2(d) (r − ‖ sin Θ(U,U?)‖2F )
)
= (1 + κ−1ρ−2)1/2(1 + ρ2)3/2
( ν2
ν2 + σ2(1) − ν
2
σ2(d) (r − ‖ sin Θ(U,U?)‖2F )
) . (B.41)
From the proof of Lemma B.10,
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
= 2EE [(2F (ω?)− 1)(Φ(αmax,U?ω?/v?)− Φ(αmax,Uω?/v?))I{ω? > 0}]. Note that for any b ≥ a ≥ 0, Φ(b)− Φ(a) ≥ φ(b)(b− a). Since we assume RHS of equation B.40 is positive, αmax,U? ≥ αmax,U . Thus on the event where ω? > 0, αmax,U?ω?/v? ≥ αmax,Uω?/v?. Observe
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
≥ 2EE [(2F (ω?)− 1)φ(αmax,U?ω?/v?)(αmax,U?ω?/v? − αmax,Uω?/v?)I{ω? > 0}]
= 2
v? (αmax,U? − αmax,U ) ∫ ∞ 0 (2F (ω?)− 1)ω?φ(ω ?/v?) v? φ(αmax,U?ω ?/v?) dω?
' αmax,U ? − αmax,U v? ∫ ∞ 0 (2F (ω?)− 1)ω? exp ( −(1/2)(1 + α2max,U?)ω? 2/v?2 ) dω? ' αmax,U ? − αmax,U
1 + α2max,U?
∫ ∞ 0 (2F ((1 + α2max,U?) −1/2v?ω?)− 1)ω? exp ( −(1/2)ω?2 ) dω? ,
where in the last equality we transformed w? → (1 + α2max,U?)1/2w?/v?. Since F (u) is differentiable at 0 and F (0) = 1/2,
F (u)− 1/2 = F ′(0)u+ o(u). Thus there exists a constant > 0 only depending on F such that 2(F (u) − 1/2) ≥ F ′(0)u for all u ∈ [0, ] since F ′(0) > 0. This gives
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
& αmax,U? − αmax,U
1 + α2max,U? F ′(0)(1 + α2max,U?) −1/2v?
× ∫ (1+α2max,U? )1/2v?
0
ω?2 exp ( −(1/2)ω?2 ) dω?
& αmax,U? − αmax,U
1 + α2max,U? (1 + α2max,U?)
−1/2v? ∫ v?
0
ω?2 exp ( −(1/2)ω?2 ) dω?
& αmax,U? − αmax,U
1 + α2max,U? (1 + α2max,U?) −1/2.
The last inequality follows since v? = ‖w?‖ = 1 by assumption. It is noted that α2max,U? ≤ ν2/σ2(d) from equation B.39. Therefore with equation B.41,
inf w∈Rr Rc(δU,w)− inf w∈Rr Rc(δU?,w)
& 1
(1 + κρ2)3/2 (1 + κ−1ρ−2)1/2(1 + ρ2)3/2
( 1
1 + ρ−2 − κρ2(r − ‖ sin Θ(U,U?)‖2F ) ) & (1 + ρ2)3/2 (1 + κρ2)3/2 ρ2 ( 1 1 + ρ2 − κ(r − ‖ sin Θ(U,U?)‖2F ) ) .
Proposition B.1. For any U ∈ Od,r,
inf w∈Rr
Rr(δU,w) = ν2w?>(I − ν2U?>U(ν2U>U?U?>U + U>ΣU)−1U>U?)w? + σ2 .
Proof of Proposition B.1. Generate random variables (x̌, ž, ξ̌, ̌) following the model equation B.34. We calculate the prediction risk of δU,w as:
Rr(δU,w) := EE(y̌ − x̌>Uw)2
= VarE(ν −1ž>w? + ̌)2 − 2CovE(ν−1ž>w? + ̌, U?ž + ξ̌)Uw
+ w>U>VarE(U ?ž + ξ̌)Uw
= ‖w?‖2 + σ2 − 2νw? >U?>Uw + w>(ν2U>U?U?>U + U>ΣU)w
= (w −A−1b)>A(w −A−1b)− b>A−1b+ ‖w?‖2 + σ2 ,
where A := ν2U>U?U?>U + U>ΣU and b := νU>U?w?. From this, we obtain
inf w∈Rr
Rr(δU,w) = w?> ( I − U?>U(U>U?U?>U + (1/ν2)U>ΣU)−1U>U? ) w? + σ2 .
Lemma B.12. For any U ∈ Od,r,
ED[ inf w∈Rr Rr(δU,w)− inf w∈Rr
Rr(δU?,w)] = O ( (1 + ρ−2)ED[‖ sin Θ(U,U?)‖2]‖w?‖2 ) .
Proof of Lemma B.12. From proposition B.1, we have
inf w∈Rr Rr(δU,w)− inf w∈Rr Rr(δU?,w) = w?> ( (I + (1/ν2)U?>ΣU?)−1 − U?>U(U>U?U?>U + (1/ν2)U>ΣU)−1U>U? ) w?.

heading: Note that infw∈Rr Rr(δU,w) − infw∈Rr Rr(δU?,w) ≡ infw∈Rr Rr(δUO,w) − infw∈Rr Rr(δU?,w)
text: for any orthogonal matrix O ∈ Or,r. Take Õ ∈ Or,r such that ‖UÕ − U?‖2 ≤ √ 2‖ sin Θ(U,O)‖2 without loss of generality, since we can always take a sequence (Õm)m≥1 such that ‖UOm−U?‖2 ≤√ 2‖ sin Θ(U,O)‖2 + 1/m from Lemma A.1.
Lemma B.7 gives
inf w∈Rr Rr(δU,w)− inf w∈Rr Rr(δU?,w)
= O
( 1
1− ‖ sin Θ(U,U?)‖22 + κ−1ρ−2 1 + ρ−2 1 + κ−1ρ−2 ‖ sin Θ(U,U?)‖2‖w?‖2
) .
On the event where ‖ sin Θ(U,U?)‖22 < 1/2,
inf w∈Rr Rr(δU,w)− inf w∈Rr
Rr(δU?,w) = O (
1 + ρ−2
(1 + κ−1ρ−2)2 ‖ sin Θ(U,U?)‖2‖w?‖2
) .
On the event where ‖ sin Θ(U,U?)‖22 ≥ 1/2, we utlize the trivial upper bound
inf w∈Rr Rr(δU,w)− inf w∈Rr
Rr(δU?,w) ≤ ‖(I + ν−2U?>ΣU?)−1‖2‖w?‖2 ≤ ν2
ν2 + σ2(d) ‖w?‖2.
Combining these results, we have
ED[ inf w∈Rr Rr(δU,w)− inf w∈Rr Rr(δU?,w)]
. 1 + ρ−2
(1 + κ−1ρ−2)2 ED[‖ sin Θ(U,U?)‖2]‖w?‖2
+ 1
1 + κ−1ρ−2 ‖w?‖2PD(‖ sin Θ(U,U?)‖2 ≥ 1/
√ 2)
. 1 + ρ−2
(1 + κ−1ρ−2)2 ED[‖ sin Θ(U,U?)‖2]‖w?‖2,
where the last inequality follows from Markov’s inequality.

heading: C OMITTED PROOFS FOR SECTION 4

heading: C.1 PROOFS FOR SECTION 4.1
text: In this section, we will provide the proof of 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 we allow them to be imbalanced and provide a more general analysis. Suppose we have n unlabeled data X = [x1, · · · , xn] ∈ Rd×n and nk labeled data Xk = [x1k, · · · , x nk k ] ∈ Rd×nk for class k, the contrastive learning task can be formulated as: min
W∈Rr×d L(W ) := min W∈Rr×d LSelfCon(W ) + LSupCon(W ). (C.1)
In addition, we write a generalized version of supervised contrastive loss function to cover the imbalanced cases:
LSupCon(W ) = − 1
r + 1 r+1∑ k=1 αk nk nk∑ i=1 [ ∑ j 6=i 〈Wxki ,Wxkj 〉 nk − 1 − ∑n j=1 ∑ s6=k〈Wxki ,Wxsj〉∑ s6=k ns ]+ λ 2 ‖WW>‖2F ,
(C.2) where αk > 0 is the weight for supervised loss of class k. Again we first provide a theorem to give the optimal solution of contrastive learning problem. Theorem C.1. The optimal solution of supervised contrastive learning problem (C.1) is given by :
WCL = C ( r∑ i=1 uiσiv > i )> ,
where C > 0 is a positive constant, σi is the i-th largest eigenvalue of the following matrix:
1
4n
( ∆(XX>)− 1
n− 1 X(1n1
> n − In)X> ) + 1
r + 1 r+1∑ k=1 αk nk
[ 1
nk − 1 Xk(1nk1
> nk − Ink)X>k − 1∑ t6=k nt Xk1k1 > s X > s
] ,
ui is the corresponding eigenvector and V = [v1, · · · , vn] ∈ Rr×r can be any orthonormal matrix.
Proof. Under this setting, combine with the result obtained in Corollary B.1, the contrastive loss can be rewritten as:
L(W ) =λ 2 ‖WW>‖2F − 1 2n tr
(( 1
2 ∆(XX>)− 1 2(n− 1) X(1n1 > n − In)X>
) W>W )
− 1 r + 1 r+1∑ k=1 αk 1 nk nk∑ i=1  1 nk − 1 ∑ j 6=i 〈Wxki ,Wxkj 〉 − 1∑ t6=k nt ∑ s 6=k ns∑ j=1 〈Wxki ,Wxsj〉 . Then we deal with the last term independently, note that:
nk∑ i=1  1 nk − 1 ∑ j 6=i 〈Wxki ,Wxkj 〉 − 1∑ t 6=k nt ∑ s6=k ns∑ j=1 〈Wxki ,Wxsj〉  = 1
nk − 1 nk∑ i=1 ∑ j 6=i 〈Wxki ,Wxkj 〉 − 1∑ t 6=k nt nk∑ i=1 ∑ s6=k ns∑ j=1 〈Wxki ,Wxsj〉
= 1 nk − 1 tr ( Xk(1nk1 > nk − Ink)X>k W>W ) − 1∑ t 6=k nt ∑ s6=k tr ( Xk1k1 > s X > s W >W ) .
Thus we have:
L(W ) =λ 2 ‖WW>‖2F − 1 4n tr
( (∆(XX>)− 1
n− 1 X(1n1
> n − In)X>)W>W ) − 1 r + 1 r+1∑ k=1 αk nk [ 1 nk − 1 tr ( Xk(1nk1 > nk − Ink)X>k W>W
) − 1∑
t 6=k nt ∑ s6=k tr ( Xk1k1 > s X > s W >W ) ].
Then by similar argument as in the proof of Theorem B.2, we can conclude that the optimal solution WCL must satisfy the desired conditions.
With optimal solution obtained in Theorem C.1, we can provide a generalized version of Theorem 4.1 to cover the imbalance cases.
Theorem C.2 (Generalized version of Theorem 4.1). If Assumption 3.1-3.3 hold, n > d r and let WCL be any solution that minimizes the supervised contrastive learning problem in Eq.(C.1), and denote its singular value decomposition as WCL = (UCLΣCLV >CL) >, then we have
E‖ sin Θ(UCL, U)‖F . ν2
λr(T )
( r3/2
d log d+
√ dr
n
+ 1
r + 1 r+1∑ k=1 αk [∑ s6=k √ nsd∑ t 6=k nt ( √ d nk + √ r) + √ dr nk ]) ,
where T , 14 ∑r+1 k=1 piµkµ > k + 1 r+1 ∑r+1 k=1 αk(µkµ > k − ∑ s6=k ns∑ t 6=k nt 1 2 (µkµ > s + µsµ > k )).
Proof. For labeled dataX = [x1, · · · , xn], we write it to beX = M+E, whereM = [µ1, · · · , µn] and E = [ξ1, · · · , ξn] are two matrices consisting of class mean and random noise. To be more specific, if xi subject to the k-th cluster, then µi = µk and ξi ∼ N (0,Σk). Since the data is randomly drawn from each class, µi follows the multinomial distribution over µ1, · · · , µr with probability p1, · · · , pr+1. Thus µi follows a subgaussian distribution with covariance matrix N = ∑r+1 k=1 pkµkµ > k .
As shown in Theorem C.1, the optimal solution of contrastive learning is equivalent to PCA of the following matrix:
T̂ , 1 4n (∆(XX>)− 1 n− 1 X(1n1 > n − In)X>)
+ 1
r + 1 r+1∑ k=1 αk nk [ 1 nk − 1 Xk(1nk1 > nk − Ink)X>k
− 1∑ t6=k nt ∑ s6=k 1 2 (Xk1k1 > s X > s +Xs1s1 > k X > k )].
Again we will deal with these terms separately,
1. For the first term, as we have discussed,X can be divided into two matricesM andE, each of them consists of subgaussian columns. Again we can obtain the result as in (B.24) (the proof is totally same):
E‖ 1 n (∆(XX>)− 1 n− 1 X(1n1 > n − In)X>)−N‖2 . ν2( r d log d+
√ r
n ) + σ2(1)
√ d
n .
(C.3)
2. For the second term, notice that:
Xk(1nk1 > nk − Ink)X>k = nk∑ i=1 ∑ j 6=i (µk + ξ k i )(µk + ξ k j ) >
=nk(nk − 1)µkµ>k + (nk − 1)µk( nk∑ i=1 ξki ) > + (nk − 1)( nk∑ i=1 ξki )µ > k + nk∑ i=1 ∑ j 6=i ξki ξ kT j ,
(C.4) and that:
1∑ t6=k nt ∑ s6=k Xk1k1 > s X > s = 1∑ t 6=k nt ∑ s6=k nk∑ i=1 (µk + ξ k i ) ns∑ j=1 (µs + ξ s j ) >
= 1∑ t6=k nt ∑ s6=k [nknsµkµ > s + nkµk( ns∑ j=1 ξsj ) > + ns nk∑ i=1 ξki µ > s + nk∑ i=1 ξki ns∑ j=1 ξsTj ]. (C.5)
Since ξki ∼ N (0,Σk), we can conclude that:
E‖ 1 nk nk∑ i=1 ξki ‖2 ≤ √√√√E‖ 1 nk nk∑ i=1 ξki ‖22 = √ d nk σ(1). (C.6)
Moreover, we have
1
nk(nk − 1) E‖ nk∑ i=1 ∑ j 6=i ξki ξ kT j ‖2 ≤
1
nk(nk − 1) E‖EkE>k ‖2 + nk nk − 1 E‖ξ̄k ξ̄k>‖2
. d
nk σ2(1).
(C.7)
Take equation (C.6) and (C.7) back into (C.4) we can conclude:
E‖ 1 nk(nk − 1) Xk(1nk1 > nk − Ink)X>k − µkµ>k ‖2 .
√ d
nk σ(1) √ rν + d nk σ2(1). (C.8)
On the other hand, by equation (C.6) we know:
E‖ 1∑ t6=k nt ∑ s 6=k ns∑ j=1 ξsj‖2 ≤ ∑ s6=k ns∑ t6=k nt E‖ 1 ns ns∑ i=1 ξsi ‖2 . ∑ s6=k ns∑ t 6=k nt
√ d
ns σ(1).
(C.9) Notice that:
E‖ 1∑ t6=k nt 1 nk ∑ s6=k nk∑ i=1 ξki ns∑ j=1 ξsTj ‖2 ≤ E‖ ∑ s6=k ns∑ t 6=k nt ξ̄k ξ̄s >‖2
≤ ∑ s6=k ns∑ t 6=k nt E‖ξ̄k ξ̄s>‖2 . ∑ s 6=k ns∑ t6=k nt d √ nkns σ2(1).
(C.10)
Thus take equations (C.9) and (C.10) back into equation (C.5) we have:
E‖ 1 nk 1∑ t 6=k nt ∑ s6=k Xk1k1 > s X > s − ∑ s 6=k ns∑ t6=k nt µkµ > s ‖2 (C.11)
. ∑ s 6=k √ nsd∑ t6=k nt (
√ d
nk σ2(1) + σ(1)
√ rν). (C.12)
Then combine equations (C.3)(C.8)(C.11) together, we can obtain the following result:
E‖T̂ − 1 4 N − 1 r + 1 r+1∑ k=1 αk(µkµ > k − ∑ s6=k ns∑ t6=k nt 1 2 (µkµ > s + µsµ > k ))‖2
.ν2 ( r
d log d+
√ r
n
) + σ2(1) √ d
n
+ 1
r + 1 r+1∑ k=1 αk ∑ s 6=k √ nsd∑ t6=k nt (√ d nk σ2(1) + √ rσ(1)ν ) + √ d nk σ(1) √ rν + d nk σ2(1) . Since we have assumed that rank( ∑r+1 k=1 pkµkµ > k ) = r we can find that the top-r eigenspace of matrix:
T = 1
4 r+1∑ k=1 piµkµ > k + 1 r + 1 r+1∑ k=1 αk µkµ>k −∑ s6=k ns∑ t6=k nt 1 2 (µkµ > s + µsµ > k )  is spanned by U?, then apply Lemma D.1 again we have:
E‖ sin Θ(USCL, U)‖F ≤ 2 √ rE‖N̂ −N‖2 λr(N)
.
√ r
λr(T )
[ ν2 ( r
d log d+
√ r
n
) + σ2(1) √ d
n
+ 1
r + 1 r+1∑ k=1 αk [∑ s6=k √ nsd∑ t 6=k nt (√ d nk σ2(1) + √ rσ(1)ν ) + √ d nk √ rσ(1)ν + d nk σ2(1) ]]
. ν2
λr(T )
r3/2 d log d+ √ dr n + 1 r + 1 r+1∑ k=1 αk ∑ s6=k √ nsd∑ t 6=k nt (√ d nk + √ r ) + √ dr nk .
Roughly speaking, since ‖µk‖ = √ rν and ∑r+1 k=1 pkµk = 0, approximately we have ν2 λr(N) ≈ 1 mink∈[r][1+αk] . Although we can not obtain the closed-form eigenvalue in general, in a special case,
where α = α1 = · · · = αr+1, m = n1 = n2 = · · · = nr+1 and 1r+1 = p1 = p2 = · · · = pr+1, it’s easy to find that: ∑
s 6=k
1 2 (µkµ > s + µsµ > k ) = −µkµ>k ,
which further implies that:
T = 1
4 r+1∑ k=1 pkµkµ > k + 1 r + 1 r+1∑ k=1 α(1 + 1 r )µkµ > k , λr(T ) = [ 1 4 + α(1 + 1 r )]λ(N).
and we can obtain the result in Theorem 4.1.

heading: C.2 PROOFS FOR SECTION 4.2
text: 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 a single source task, where the data x = U?z + ξ is generated by spiked covariance model and the label is generated by
y = 〈w?, z〉 suppose we have collect n labeled data from this task, denote the data as X = [x1, x2, · · · , xn] ∈ Rd×n and the label y = [y1, y2, · · · , yn] ∈ Rn, then we have the following result. Lemma C.1. Under the conditions similar to Theorem 3.2, we can find an event A such that P(AC) = O( √ d/n) and:
E [∥∥∥∥ 1(n− 1)2XHyy>HX> − ν2U?w?w?>U?> ∥∥∥∥ F I{A} ] . √ d n σ(1)ν. (C.13)
The proof strategy is to estimate the difference between the two rank-1 matrices via bounding the difference of the corresponding the vector component. We first provide a simple lemma to illustrate the technique: Lemma C.2. Suppose α, β ∈ Rd are two vectors, then we have:
‖αα> − ββ>‖F ≤ √ 2(‖α‖2 + ‖β‖2)‖α− β‖2.
Proof. Denote α = (α1, · · · , αd), β = (β1, · · · , βd), then we have:
‖αα> − ββ>‖2F ≤ d∑ i=1 d∑ j=1 |αiαj − βiβj |2 ≤ 2 d∑ i=1 d∑ j=1 |αiαj − αiβj |2 + |αiβj − βiβj |2
≤2 d∑ i=1 d∑ j=1 |αi|2|αj − βj |2 + |βj |2|αi − βi|2 ≤ 2(‖α‖22 + ‖β‖22)‖α− β‖22
≤2(‖α‖2 + ‖β‖2)2‖α− β‖22.
Take square root on both side we can finish the proof.
Now we can prove the Lemma C.1.
Proof of Lemma C.1. Clearly, we have:
‖ 1 (n− 1)2 XHyy>HX> − ν2U?w?w?>U?>‖F
≤ n 2 (n− 1)2 ‖ 1 n2 XHyy>HX> − ν2U?w?w?>U?>‖F + 2n+ 1 (n− 1)2 ‖ν2U?w?w?>U?>‖F
.‖ 1 n2 XHyy>HX> − ν2U?w?w?>U?>‖F + r n ν2,
thus we can replace the 1(n−1)2 with 1 n in equation (C.13) and conclude the proof. Denote N̂ ,
1 n2XHyy >HX>, note that both of N̂ and Uw?w?>U> are rank-1 matrices. We first bound the difference between 1nXHy and Uw ?:
‖ 1 n XHy − νU?w?‖ =‖ 1 nν (U?Z + E)HZ>w? − νU?w?‖
≤‖ 1 nν (U?Z + E)HZ> − νU?‖2 ≤1 ν (‖ 1 n U?ZZ> − ν2U?‖2 + 1 n ‖EZ>‖2 + 1 n ‖U?ZZ̄>‖2 + 1 n ‖EZ̄>‖2).
(C.14) We deal with the four terms in (C.14) separately:
1. For the first term, apply Lemma D.3 we have:
E‖ 1 n U?ZZ> − ν2U?‖2 ≤ E‖ 1 n ZZ> − ν2Ir‖2 ≤
( r
n +
√ r
n
) ν2. (C.15)
2. For the second term, apply Lemma D.2 twice we have:
1 n E‖EZ>‖2 = 1 n EZ [EE [‖EZ>‖2|Z]]
. 1
n EZ [‖Z‖2(σsum + r1/4
√ σsumσ(1) + √ rσ(1))]
. 1
n EZ [‖Z‖2]
√ dσ(1)
. 1
n
√ dσ(1)(r 1/2ν + (nr)1/4ν + n1/2ν)
. √ d√ n σ(1)ν.
(C.16)
3. For the third term and fourth term, from equation (4) we know:
E 1
n ‖U?ZZ̄>‖2 + E
1 n ‖EZ̄>‖2 ≤ E‖z̄z̄>‖2 + E‖ξ̄z̄>‖2 ≤ r n ν2 +
√ d
n νσ(1). (C.17)
Combine these three equations (C.15)(C.16)(C.17) together we have:
E‖ 1 n XHy − νU?w?‖ .
√ d
n σ(1). (C.18)
With equation (C.18), we can now turn to the difference between N̂ and Uw?w?>U>. By Lemma C.2 we know that:
‖N̂ − ν2U?w?w?>U?>‖F . (‖ 1 n XHy‖+ ‖νU?w?‖)‖ 1 n XHy − νU?w?|‖.
Using Markov’s inequality, we can conclude from (C.18) that:
P(‖ 1 n XHy − νU?w?‖ ≥ ν) ≤
E‖ 1nXHy − νU ?w?‖
ν .
√ d
n .
Then denote A = {ω : ‖ 1nXHy − ν 2U?w?‖2 < ν} we have:
E‖N̂ − ν2U?w?w?>U?>‖F I{A} .E(‖ 1 n XHy‖+ ‖νU?w?‖)‖ 1 n XHy − νU?w?|‖I{A}
.νE‖ 1 n XHy − νU?w?‖2 .
√ d
n σ(1)ν.
which finished the proof.
In the main body, we 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. Formally, suppose we have n unlabeled data X = [x1, · · · , xn] ∈ Rd×n and ni labeled data Si Xi = [x 1 i , · · · , x ni i ], yi = [y 1 i , · · · , y n1 i ],∀i = 1, · · ·T for source task , we learn the linear representation via joint optimization:
min W∈Rr×d L(W ) := min W∈Rr×d LSelfCon(W )− T∑ t=1 αi HSIC(X̂ t, yt;W ), (C.19)
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 is given by:
WCL = C ( r∑ i=1 uiσiv > i )> ,
where C > 0 is a constant, σi is the i-largest eigenvalue of the following matrix:
1
4n
( ∆(XX>)− 1
n− 1 X(1n1
> n − In)X>
) + T∑ i=1 αi (ni − 1)2 XiHniyiy > i HniX > i ),
ui is the corresponding eigenvector, V = [v1, · · · , vr] ∈ Rr×r can be any orthogonal matrix and Hni = Ini − 1ni 1ni1 > ni is the centering matrix.
Proof. Under this setting, combine with the result obtained in B.1, the loss function can be rewritten as:
L(W ) =λ 2 ‖WW>‖2F − 1 2n tr
(( 1
2 ∆(XX>)− 1 2(n− 1) X(1n1 > n − In)X>
) W>W ) −
T∑ t=1 αi 1 (ni − 1)2 tr ( X>i W >WXiHyiy > i H ) = λ
2 ∥∥∥∥WW> − 14nλ ( ∆(XX>)− 1 n− 1 X(1n1 > n − In)X> ) −
T∑ i=1 αi λ(ni − 1)2 XiHniyiy > i HniX > i ) ∥∥∥∥2 F
− λ 2 ∥∥∥∥ 14nλ ( ∆(XX>)− 1 n− 1 X(1n1 > n − In)X> ) +
T∑ i=1 αi λ(ni − 1)2 XiHniyiy > i HniX > i ∥∥∥∥2 F .
Then by similar argument as in the proof of Theorem B.2, we can conclude that the optimal solution WCL must satisfy the desired conditions.
Then we can give the proofs of Theorem 4.2 and Theorem 4.3 under our generalized setting, one can easily obtain those under balanced setting by simply setting α = α1 = · · · = αT and m = n1 = · · · = nT , which is consistent with Theorem 4.2 and Theorem 4.3 in the mainbody. Theorem C.4 (Generalized version of Theorem 4.2). Suppose Assumption 3.1-3.3 hold for spiked covariance model Eq.(2.5) and n > d r, if we further assume that T < r andwt’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 = (UCLΣCLV >CL) >, then we have:
E‖ sin(Θ(UCL, U?))‖F .( √ r − T
mini∈[T ]{αi, 1} +
√ T
mini∈[T ] αi )( r d log d+
√ d
n )
+ T∑ i=1 ( √ r − T αi + mini∈[T ]{αi, 1} mini∈[T ]{αi, 1} + √ T αi + mini∈[T ] αi mini∈[T ] αi )
√ d
ni .
Proof. As shown in Theorem C.3, optimizing loss function (C.19) is equivalent to find the top-r eigenspace of matrix
1
4n
( ∆(XX>)− 1
n− 1 X(1n1
> n − In)X>
) + T∑ i=1 αi (ni − 1)2 XiHniyiy > i HniX > i .
Again denote M̂2 , 1n (∆(XX >) − 1n−1X(1n1 > n − In)X>) and N̂i , 1(ni−1)2XiHyiy > i HX > i . By equation (B.24) we know that:
E‖M̂2 −M‖2 . ν2 ( r
d log d+
√ r
n + r n
) + σ2(1) (√ d
n + d n
) + σ(1)ν √ d
n .
By Theorem C.1 we know that for each task Si, we can find an eventAi such that P(Ai) = O( √ d n ):
E‖N̂i − ν2U?wiw>i U?>‖F I{Ai} . √ d
ni σ(1)ν.
The target matrix isN = ν2U?U?>+ ∑T i=1 αiν 2U?wiw T i U
?>, and we can obtain the upper bound for the difference between N and N̂ :
E‖N̂ −N‖2I{∩Ti=1Ai} ≤ 1
4 E‖M̂2 −M‖2 + T∑ i=1 αiE‖N̂i − ν2Uwiw>i U>‖F I{Ai}
.ν2( r
d log d+
√ r
n + r n ) + σ2(1)
(√ d
n + d n
) + σ(1)ν √ d
n + T∑ i=1
[ αi √ d
ni σ(1)ν
2 ] .
(C.20)
We divide the top-r eigenspace UCL of WCLW>CL into two parts: the top-T eigenspace U (1) CL and top-(T + 1) to top-r eigenspace U (2)CL. Similarly, we also divide the top-r eigenspace U ? of N into two parts: U?(1) and U?(2). Then apply Lemma D.1 we have we can bound the sin Θ distance for each parts: on the one hand,
E‖ sin (
Θ(U (1) CL, U ?(1)) ) ‖F
=E‖ sin (
Θ(U (1) CL, U ?(1)) ) ‖F I{∩Ti=1Ai}+ E‖ sin ( Θ(U (1) CL, U ?(1)) ) ‖F I{∪Ti=1ACi }
≤ √ TE‖N̂ −N‖2I{∩Ti=1Ai} λ(T )(N)− λ(T+1)(N) + √ TP(∪Ti=1ACi )
.
√ T
mini∈[T ] αiν2
( ν2 r
d log d+ σ2(1)
√ d
n + T∑ i=1 αi
√ d
ni σ(1)ν
) + √ T
T∑ i=1
√ d
ni
.
√ T
mini∈[T ] αi
( r
d log d+
√ d
n
) + √ T
T∑ i=1 αi + mini∈[T ] αi mini∈[T ] αi
√ d
ni .
On the other hand, E‖ sin (
Θ(U (2) CL, U ?(2)) ) ‖F
= E‖ sin (
Θ(U (2) CL, U ?(2)) ) ‖F I{∩Ti=1Ai}+ E‖ sin ( Θ(U (2) CL, U ?(2)) ) ‖F I{∪Ti=1ACi }
≤ √ r − TE‖N̂ −N‖2I{∩Ti=1Ai}
min{λ(T )(N)− λ(T+1)(N), λ(r)(N)} + √ r − TP(∪Ti=1ACi )
.
√ r − T
mini∈[T ]{αi, 1}ν2
( ν2 r
d log d+ σ2(1)
√ d
n + T∑ i=1 αi
√ d
ni σ(1)ν
) + √ r − T
T∑ i=1
√ d
ni
.
√ r − T
mini∈[T ]{αi, 1}
( r
d log d+
√ d
n
) + √ r − T
T∑ i=1 ( αi mini∈[T ]{αi, 1} + 1 )√ d ni .
Note that: ‖ sin(Θ(UCL, U?))‖2F = r − ‖U>CLU?‖2F ≤ r − ‖U (1)>CL U ?(1)‖2F − ‖U (2)T CL U
?(2)‖2F ≤ T − ‖U (1)>CL U ?(1)‖2F + (r − T )− ‖U (2)> CL U
?(2)‖2F ≤ ‖ sin ( Θ(U
(1) CL, U ?(1)) ) ‖2F + ‖ sin ( Θ(U (1) CL, U ?(1)) ) ‖2F ,
and the sin Θ distance has trivial upper bounds: ‖ sin (
Θ(U (1) CL, U ?(1)) ) ‖2F ≤ T, ‖ sin ( Θ(U (2) CL, U ?(2)) ) ‖2F ≤ r − T
Thus we can conclude: E‖ sin(Θ(UCL, U?))‖F
≤ E‖ sin (
Θ(U (1) CL, U ?(1)) ) ‖F + E‖ sin ( Θ(U (2) CL, U ?(2)) ) ‖F
.
( √ r − T
mini∈[T ]{αi, 1}
( r
d log d+
√ d
n
) +
T∑ i=1 √ r − T αi + mini∈[T ]{αi, 1} mini∈[T ]{αi, 1}
√ d
ni
) ∧ √ r − T
+
( √ T
mini∈[T ] αi
( r
d log d+
√ d
n
) +
T∑ i=1 √ T αi + mini∈[T ] αi mini∈[T ] αi
√ d
ni
) ∧ √ T .
Theorem C.5 (Generalized version of Theorem 4.3). Suppose Assumptions 3.1-3.3 hold for spiked covariance model Eq.(2.5) and n > d r, if we further assume that T ≥ r and ∑T i=1 αiwiw > i is full rank, suppose WCL is the optimal solution of optimization problem eq.(C.19), and denote its singular value decomposition as WCL = (UCLΣCLV >CL) >, then we have:
E‖ sin(Θ(UCL, U))‖F . √ r 1 + ν2λ(r)( ∑T i=1 αiwiw > i )
( r
d log d+
√ d
n
)
+ √ r T∑ i=1
( αi
1 + ν2λ(r)( ∑T i=1 αiwiw > i ) + 1
)√ d
ni .
Proof. The proof strategy is similar to that of Theorem 4.2, here the difference is that each direction can be accurately estimated by the labeled data and we don’t need to separate the eigenspace. Directly applying Lemma D.1 and equation (C.20) we have:
E‖ sin(Θ(UCL, U?))‖F = E‖ sin(Θ(UCL, U?))‖F I{∩Ti=1Ai}+ E‖ sin(Θ(UCL, U?))‖F I{∪Ti=1ACi }
.
√ rE‖N̂ −N‖2I{∩Ti=1Ai}
λ(r)(N) + √ rP(∪Ti=1ACi )
.
√ r
ν2 + ν2λ(r)( ∑T i=1 αiwiw > i )
( ν2 r
d log d+ σ2(1)
√ d
n + T∑ i=1 αi
√ d
ni σ(1)ν
) + √ r
T∑ i=1
√ d
ni
.
√ r
1 + λ(r)( ∑T i=1 αiwiw > i )
( r
d log d+
√ d
n
) + √ r
T∑ i=1
( αi
1 + λ(r)( ∑T i=1 αiwiw > i ) + 1
)√ d
ni .

heading: D USEFUL LEMMAS
text: In this section, we list some of the main techniques that have been used in the proof of the main results.
Lemma D.1 (Theorem 2 in Yu et al. (2015)). Let Σ, Σ̂ ∈ Rp×p be symmetric, with eigenvalues λ1 ≥ . . . ≥ λp and λ̂1 ≥ . . . ≥ λ̂p respectively. Fix 1 ≤ r ≤ s ≤ p and assume that min (λr−1 − λr, λs − λs+1) > 0 where λ0 := ∞ and λp+1 := −∞. Let d := s − r + 1, and let V = (vr, vr+1, . . . , vs) ∈ Rp×d and V̂ = (v̂r, v̂r+1, . . . , v̂s) ∈ Rp×d have orthonormal columns satisfying Σvj = λjvj and Σ̂v̂j = λ̂j v̂j for j = r, r + 1, . . . , s. Then
‖ sin Θ(V̂ , V )‖F ≤ 2 min
( d1/2‖Σ̂− Σ‖2, ‖Σ̂− Σ‖F ) min (λr−1 − λr, λs − λs+1) .
Moreover, there exists an orthogonal matrix Ô ∈ Rd×d such that
‖V̂ Ô − V ‖F ≤ 23/2 min
( d1/2‖Σ̂− Σ‖2, ‖Σ̂− Σ‖F ) min (λr−1 − λr, λs − λs+1) .
Lemma D.2 (Lemma 2 in Zhang et al. (2018)). Assume that E ∈ Rp1×p2 has independent subGaussian entries, Var (Eij) = σ2ij , σ 2 C = maxj ∑ i σ 2 ij , σ 2 R = maxi ∑ j σ 2 ij , σ 2 (1) = maxi,j σ 2 ij .

heading: Assume that
text: ‖Eij/σij‖ψ2 := maxq≥1 q −1/2 {E (|Eij | /σij)q} 1/q ≤ κ.
Let V ∈ Op2,r be a fixed orthogonal matrix. Then
P (‖EV ‖2 ≥ 2 (σC + x)) ≤ 2 exp ( 5r −min { x4
κ4σ2(1)σ 2 C
, x2
κ2σ2(1)
}) ,
E‖EV ‖2 . σC + κr1/4 ( σ(1)σC )1/2 + κr1/2σ(1).
Lemma D.3 (Theorem 6 in Cai et al. (2020)). Suppose Z is a p1-by- p2 random matrix with independent mean-zero sub-Gaussian entries. If there exist σ1, . . . , σp ≥ 0 such that ‖Zij/σi‖ψ2 ≤ CK for constant CK > 0, then
E ∥∥ZZ> − EZZ>∥∥ 2 . ∑ i σ2i + √ p2 ∑ i σ2i ·max i σi.
Lemma D.4 (The Eckart-Young-Mirsky Theorem (Eckart & Young, 1936)). Suppose that A = UΣV T is the singular value decomposition of A. Then the best rank- k approximation of the matrix A w.r.t the Frobenius norm, ‖ · ‖F , is given by
Ak = k∑ i=1 σiuiv T i .
that is, for any matrix B of rank at most k
‖A−Ak‖F ≤ ‖A−B‖F .

heading: E NUMERICAL EXPERIMENTS

heading: E.1 SUPPORTING EMPIRICAL RESULTS IN RELATED WORKS
text: In this section, we list some recent empirical evidence that provides sound support to our theory:
Contrastive learning outperforms generative self-supervised learning. In Figure 1 of Chen et al. (2020a) and Figure 5 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 we show that contrastive learning achieves better performance on both feature recovery and downstream tasks compared with autoencoder, a representative generative selfsupervised learning method.
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. (2021), supervised contrastive learning shows significant improvement with 7%-8% accuracy increase on ImageNet and Mini-ImageNet. This observation is consistent with our finding in Theorem 4.1, where we prove that supervised contrastive learning can achieve a better upper bound in feature recovery compared with self-supervised contrastive learning.
Label information may hurt transferability in contrastive learning. In Table 4 of Khosla et al. (2020) and Table 4 of 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%) and can harm significantly on some datasets (e.g. 5.5% lower for SUN 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. (2021), it is observed that combining supervised learning and self-supervised contrastive learning together achieves the best transfer learning performance compared with each of them individually. These findings are consistent with our theory in Theorem 4.2, where we show that the error can increase as α (the ratio between supervised learning loss and self-supervised learning loss) grows and the optimal error is achieved when choosing a moderate α, i.e., combining self-supervised learning and supervised learning together.

heading: E.2 SIMULATION WITH SYNTHETIC DATA
text: 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, we 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 it (typically 10000 or 50000 depends on dimension d).
We report two criteria to evaluate the quality of the representation, downstream error and sine distance. To obtain the sine distance for a learned representationW , we perform singular value decomposition to get W = (UΣV >)> and then compute ‖ sin Θ(U,U?)‖F . To obtain the downstream task performance, in the comparison between autoencoder and contrastive learning, we first draw n 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 w 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 number of labeled data is set m = 1000 and the number of unlabeled data is set n = 1000. Then train with them to obtain the linear representation W , and draw labeled data from a new source task to learn a linear predictor w 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. 1, 2 and Table 1, 2. As predicted by Theorem 3.1 and 3.2, the feature recovery error and downstream task risk of contrastive learning decreases as d increases (Fig. 1: Left) and as n increases (Fig. 1: 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 α 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.

Review summaries:
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. 

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.

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.