Year: 2021

Abstract:
Contrastive unsupervised representation learning (CURL) encourages data representation to make semantically similar pairs closer than randomly drawn negative samples, which has been successful in various domains such as vision, language, and graphs. Although recent theoretical studies have attempted to explain its success by upper bounds of a downstream classification loss by the contrastive loss, they are still not sharp enough to explain an experimental fact: larger negative samples improve the classification performance. This study establishes a downstream classification loss bound with a tight intercept in the negative sample size. By regarding the contrastive loss as a downstream loss estimator, our theory not only improves the existing learning bounds substantially but also explains why downstream classification empirically improves with larger negative samples—because the estimation gap of the downstream loss decays with larger negative samples. We verify that our theory is consistent with experiments on synthetic, vision, and language datasets.

heading: 1 INTRODUCTION
text: The contrastive loss (Chopra et al., 2005) is one of the popular loss functions in metric learning (Kulis, 2012) and representation learning (Bengio et al., 2013). The contrastive loss forces data representation of semantically similar pairs closer in some metric space than multiple random samples, called negative samples. Many state-of-the-art representation learning algorithms use a type of contrastive losses in natural language processing (Mikolov et al., 2013; Logeswaran & Lee, 2018), vision (Chopra et al., 2005; He et al., 2019; Chen et al., 2020), and graph (Lirong et al., 2021) domains. A simple model built on top of the learned representation can achieve almost the same accuracy as supervised learning does. See surveys (Le-Khac et al., 2020; Schmarje et al., 2021) and references therein for recent empirical progress.
Compared to its empirical success, we still do not know much about the theoretical perspective of the contrastive loss function. Since the first theoretical analysis of contrastive unsupervised representation learning (CURL) (Arora et al., 2019), a number of follow-up researches (Nozawa et al., 2020; Chuang et al., 2020; Nozawa & Sato, 2021; Ash et al., 2021) improved theoretical understanding of CURL. They provided upper bounds of a downstream classification loss by the contrastive loss. While they partially explain why CURL provides good representation in terms of downstream classification, a controversy has been held on the impact of the negative sample size, denoted byK in this work. From the empirical viewpoint, it has been widely shown that downstream classification accuracy tends to be better with the largerK (He et al., 2020; Chen et al., 2020).1 From the theoretical viewpoint, although Ash et al. (2021) and Nozawa & Sato (2021) addressed the issue of the earlier analysis (Arora et al., 2019)—the bound grows exponentially in K—their improved bounds are still so huge that they may not capture the actual behavior of CURL related to K, as we will see in Figure 1. In addition, Ash et al. (2021) claims that the optimal K exists in smaller K, which does not agree well with the empirical observations. Henceforth, the relationship between the performance of downstream classification and K needs to be investigated carefully.
This study aims to clarify the relationship between the performance of downstream classification and the negative sample size K by deriving an upper bound of the downstream classification loss
1The empirical evidence has also not reached a consensus yet. Chen et al. (2021) reported that SimCLR with the smaller K could be competitive in linear evaluation than K used by the original SimCLR (Chen et al., 2020).
(Theorem 1). By deriving the lower bound (Theorem 2), we found that the intercept of our upper bound is tight in K. Notably, such a lower bound has yet to be known in CURL so far. Our bounds support that the larger K reduces estimation gap of the downstream classification loss (Section 3.2), while the smaller K could perform well. This finding is evidence for the empirical success of the larger K. In addition, our bounds are compared with the existing bounds to demonstrate that there is no optimal point in K and how accurately the derived bounds capture the downstream loss (Section 4). Finally, we empirically verify our theory by experiments (Section 6) on a synthetic dataset, CIFAR-10/100 (Krizhevsky, 2009) datasets, and Wiki-3029 dataset (Arora et al., 2019).

heading: 2 FORMULATION OF CONTRASTIVE LEARNING
text: First, this section briefly summarizes the problem setup and formulation of CURL.
Notation. The C-dimensional vector whose elements are all one is denoted by 1C := [1 1 . . . 1]>. When it is clear from context, the subscript is abbreviated. For a vector a ∈ Rp, a(i) denotes the i-th largest element of a, namely, a(1) ≥ a(2) ≥ · · · ≥ a(p). Likewise, a(−i) denotes the i-th smallest element of the vector a. The indicator function is denoted by 1{A} for a predicate A. Let 4C := {p ∈ [0, 1]C | p>1 = 1} be the C-dimensional probability simplex. For p ∈ 4C , the Shannon entropy is denoted by H (p) := − ∑ c∈[C] pc ln pc. Let Hn be the n-th harmonic number.
Supervised classification. One of the goals in machine learning is supervised classification, while we consider the setup where supervision is unavailable. Here, we first formulate the multiclass classification problem. Assume that there exists an unknown number of latent classes denoted by C ∈ N. Let X be d-dimensional feature space and Y := [C] be the supervised label
set.2 In the supervised setup, we are interested in the following risk quantity, the supervised loss, for a multi-class classifier g : X → RC :
Rsupv(g) := E x,y∼P
[ − ln exp(gy(x))∑
c∈Y exp(gc(x))
] , (1)
which is specialized for the softmax cross-entropy loss. The expectation is taken over the unknown underlying joint distribution P. The classifier is eventually used for prediction by argmaxy∈Y gy(·).
Contrastive unsupervised representation learning (CURL). In the CURL framework (Arora et al., 2019), we target to learn meaningful data representation in an unsupervised manner. By doing so, a similarity model is trained to make the representation of positive pairs more similar than randomly drawn K negative samples using a contrastive loss. The class-conditional distribution is denoted by Dc := P(X | Y = c) for each c ∈ Y and the class-prior distribution by π := [P(Y = c)]c∈Y ∈ 4C . The data generating process is described as follows: (i) draw latent positive/negative classes: c+,
2Strictly speaking, latent classes should be distinguished from the supervised labels as they may contain concepts that human annotators are not interested in. In the CURL framework (Arora et al., 2019), latent classes [C] and the supervised label set Y are allowed to be different, i.e., Y ⊆ [C]. To focus on the relationship between the supervised loss and contrastive loss, we analyze under the assumption Y = [C] for simplicity.
{c−k }Kk=1 ∼ πK+1 (ii) draw an anchor sample x ∼ Dc+ (iii) draw a positive sample x+ ∼ Dc+3 (iv) draw K negative samples x−k ∼ Dc−k (for each k ∈ [K]).
Now we specify our model. A multi-class classifier g : X → RC consists of representation f : X → Rh and linear parameters W ∈ RC×h as g(·) := Wf(·), where h ∈ N denotes the dimensionality of the representation given in advance. In CURL, the representation is learned through minimization of the following contrastive loss
Rcont(f) := E c+,{c−k } K k=1
∼πK+1
E x,x+∼D2
c+
x−k ∼Dc− k
[ − ln exp(f(x) >f(x+))
exp(f(x)>f(x+)) + ∑ k∈[K] exp(f(x) >f(x−k ))
] . (2)
In the downstream task, the representation f shall be frozen, and the parameters W are to be learned via minimizing the supervised loss Rsupv.
Evaluation of representations. For the sake of evaluation, a specific linear classifier called mean classifier is introduced. Given representation f , the mean classifier Wµ is defined as Wµ := [µ1 · · · ,µC ]>, where µc := Ex∼Dc [f(x)]. This will later be used for evaluating the representation f combined with the supervised loss, which is denoted by Rµ-supv(f) := Rsupv(Wµf). We call it the mean supervised loss. If the mean supervised loss is successfully bounded from above, we end up a bound on the supervised loss through infW∈RC×h Rsupv(Wf) ≤ Rµ-supv(f). For this reason, an upper bound on Rµ-supv is an intermediate milestone that we seek throughout this paper.

heading: 3 LEARNING BOUNDS FOR CONTRASTIVE LEARNING
text: In this section, our main theoretical results are provided. We aim at showing that the contrastive loss Rcont(f)—the computable functional in CURL—serves as a good estimator of the mean supervised loss Rµ-supv(f)—the inaccessible target in CURL—for any f . We show this by establishing upper and lower bounds of Rµ-supv(f) by Rcont(f). Eventually, the minimization of Rcont(f) may lead to a good minimizer of Rµ-supv(f). All proofs are provided in Appendix B.

heading: 3.1 MAIN RESULTS
text: First, we show a sharp upper bound of the mean supervised loss. Unlike any of the existing learning bounds of CURL, the upper bound obtained here has a constant coefficient in the contrastive loss and is applicable for all C and K (see discussions in Section 4).4
Theorem 1. For all f such that ‖f(x)‖2 ≤ L (∀x ∈ X ), the following inequality holds.
Rµ-supv(f) ≤ Rcont(f) + ∆U, (3)
where ∆U := 2 ln((CKπ(−1) + 1) cosh(L2))− 2 ln(1 +K)− lnKπ(−1).
Next, the first lower bound of the mean supervised loss is provided. While the existing theoretical analyses only provided upper bounds, they often entail a huge coefficient in the contrastive loss. The lower bound provided below has the same constant coefficient and intercept (∆U and ∆L) rate as our upper bound, ensuring the tightness of our analysis.
Theorem 2. For all f such that ‖f(x)‖2 ≤ L (∀x ∈ X ), the following inequality holds.
Rµ-supv(f) ≥ Rcont(f) + ∆L, (4)
where ∆L := H (π) + ln K(K+1)2 − 2 ln cosh(L 2).
3In self-supervised learning, data augmentation (DA) is commonly used to obtain a positive sample. While Nozawa & Sato (2021) handled DA in this formulation, we omit it for simplicity to focus on the effect of K.
4Even if Y = [C] is assumed in Section 2, Theorem 1 can be extended to the case Y ⊆ [C] (subset) and Y is a coarse-grained set of [C]. In contrast, Theorem 2 can only be extended to the coarse-grained Y . The details are discussed in their proofs.
Our proofs leverage that the contrastive loss and mean supervised loss share the similar log-sum-exp functional form, which leads to the direct relationships between the two losses. This is in contrast to the existing works including Arora et al. (2019), which approximate the mean supervised loss with the contrastive loss by taking the expectation over latent classes, leading to an exponentially large coefficient.
In Theorems 1 and 2, the size of the representation ‖f(x)‖2 is assumed to be bounded. This assumption is reasonable from the experimental perspective since it is common to normalize representation to employ the cosine similarity as the similarity metric. Several works reported that the normalized embeddings improve the performance (Chen et al., 2020; Wang & Isola, 2020). Unlike the existing analyses (reviewed in Section 4), we take advantage of this assumption to derive the sharp bounds.
As we see in Section 3.2, ∆U and ∆L are the same order in K under the uniform class prior assumption. By applying either the high-probability bound (Arora et al., 2019) or PAC-Bayesian analysis (Nozawa et al., 2020), Theorem 1 (Theorem 2 as well) can be naturally extended to the form Rµ-supv(f̂) ≤ Rcont(f) + ∆U + χ with a complexity term χ, where f̂ is the empirical minimizer of the contrastive loss. Since this is a routine, we omit the high-probability bounds.
3.2 DISCUSSION
Subsequently, we discuss implications of our main results on the relationship between the mean supervised loss and the negative sample size K. For the sake of simplicity, we assume πc = 1/C for all c ∈ [C] (the uniform class prior) in this section.
Gap between learning upper and lower bounds. Both of our upper (Theorem 1) and lower (Theorem 2) bounds draw the linear relationship between the mean supervised loss Rµ-supv and the contrastive loss Rcont, with the additional intercept terms ∆U and ∆L. Under the uniform class prior assumption, the intercepts are in the same order:
∆U = ln C
K + 2 ln cosh(L2) = O(ln
1
K ), ∆L = ln
CK (K + 1)2 − 2 ln cosh(L2) = O(ln 1 K ), (5)
and the gap between two bounds is ∆U−∆L = 4 ln cosh(L2) + 2 ln ( 1 + 1K ) , meaning that the gap shrinks to 4 ln cosh(L2) as K increases. Hence, our bounds have the tight intercepts, and the larger K is beneficial for CURL from the viewpoint of the estimation gap of the mean supervised loss.
Learning bounds and feasible region. Next, we consider the (Rcont, Rµ-supv)-plot, in which a point indicates (Rcont(f), Rµ-supv(f)) for some f (see Figure 2). Here, let us focus on the feasible region in the (Rcont, Rµ-supv)-plot by assuming ‖f‖2 ≤ L for any f (same as Theorems 1 and 2). Then, the mean supervised loss and contrastive loss are essentially lower-bounded by the constants5
R∗µ-supv := ln ( 1 + (C − 1) exp(−2L2) ) , (6)
R∗cont := K∑ m=0 ( K m )( 1 C )m( 1− 1 C )K−m ln{1 +m+ (K −m) exp(−2L2)}, (7)
respectively. Hence, the feasible region is
Rµ-supv(f) ≤ Rcont(f) + ∆U, Rµ-supv(f) ≥ Rcont(f) + ∆L, (8a) Rµ-supv(f) ≥ R∗µ-supv, Rcont(f) ≥ R∗cont, (8b)
as illustrated in Figure 2. The first two bounds (8a) restrict the mean supervised loss by the contrastive loss. We specifically refer to these bounds as learning bounds. The remaining two bounds (8b)
5The derivations of R∗µ-supv and R∗cont are detailed in Appendix C.
represent the achievable limits for each loss separately. One of the important questions is how the smallest possible value of Rµ-supv in the feasible region (8) changes as K and C change. In other words, we are interested in whether the optimal point (R∗cont, R ∗ µ-supv) (F in Figure 2) is always achievable regardless of the values of K and C. To investigate it, we check the following two points.
• The feasible region at Rcont(f) = R∗cont (Figure 3a): We plot the value R ∗ cont + ∆U (solid line;
the Rµ-supv-value of the point • in Figure 2) and the minimum possible Rµ-supv (R∗µ-supv; dotted line) numerically. These two curves do not cross for allK, which meansRµ-supv(f) = R∗µ-supv is attainable no matter the values K and C. In addition, the bound becomes sharper as K increases, but the gap between the upper bound and R∗µ-supv does remain even at the limit K ↗∞.
• The feasible region at Rµ-supv(f) = R∗µ-supv (Figure 3b): When Rµ-supv(f) = R ∗ µ-supv, the con-
trastive loss Rcont(f) is upper-bounded by R∗µ-supv − ∆L (the Rcont-value of the point in Figure 2). The curve of this value does not cross R∗cont, which tells us that the lower bound does not exclude the optimal point (R∗cont, R ∗ µ-supv) from the feasible region (8) at any K. Note that the gap between R∗cont and R ∗ µ-supv −∆L gradually increases, meaning that it becomes much easier to attain R∗µ-supv as K increases.
Hence, the optimal point F stays in the feasible region (8) no matter the value K. From this viewpoint, smaller K is not necessarily disadvantageous because the optimal point F remains in the feasible region. Note again that the estimation of Rµ-supv may become harder with the smaller K because of the bound gap ∆U −∆L = O(ln 1/K), even if the optimal solution is unaffected by K.
Summary. We draw a connection between the mean supervised loss and the negative sample size K by the following claim: if we regard CURL as an estimation process of the mean supervised loss by the contrastive loss, the small K does not necessarily have the estimation bias, but the larger K helps reduce the estimation gap.

heading: 4 COMPARISON WITH EXISTING LEARNING BOUNDS
text: This section discusses the difference between our main results and the existing theoretical results on CURL. The learning bound analysis of CURL has been first established by Arora et al. (2019) and later extended by Nozawa & Sato (2021) and Ash et al. (2021). Here, we briefly review these results. For ease of the comparison, we assume the uniform class prior, namely, πc = 1/C for all c ∈ [C]. We introduce a notation Col := ∑ k∈[K] 1{c+=c−k }
. Let vK be the probability that sampled K negative classes contains all classes c ∈ [C].
vK := K∑ n=1 C−1∑ m=0 ( C − 1 m ) (−1)m ( 1− m+ 1 C )n−1 . (9)
The value vK is often referred to as the coupon collector’s probability. Let τK be the probability that at least one of the negative classes c−k is the same as the positive class c
+. Under the uniform class prior, τK = 1− (1− 1/C)K . The learning bounds are summarized in Table 1.6
Comparison. First, the coefficient ofRcont(f) in the upper bounds are numerically compared in Figure 4a. While Theorem 1 has the coefficient 1 for all K, the existing bounds have different nature—Arora et al.’s and Ash et al. (2021)’s coefficients have unique minima, and Nozawa & Sato’s coefficient has monotonically decreasing nature. Since the larger K was shown advantageous in the several experimental work (Chen et al., 2020; He et al., 2020), the behaviors of Arora et al.’s and Ash et al.’s bounds do not explain it well. In Section 6, we also experimentally confirm the benefits of the large K.
Figure 4b compares the upper bound values at Rcont(f) = R∗cont, namely, the best possible mean supervised loss in terms of the upper bounds. The tendencies are slightly different from Figure 4a—Ash et al.’s bound is monotonically increasing, Arora et al.’s and Nozawa & Sato’s bounds have a unique minimum, and ours is monotonically decreasing. Among the compared bounds, only ours agrees well with the experimental fact that the larger K is better.7
Note that the coefficients of the existing theories are so large—the vertical axes are log-scaled—that the upper bounds are vacuous in both situations. In contrast, our theory can bound the downstream classification loss most sharply in all ranges of K. This sharpness can be empirically observed as well in Figure 1; the details are stated in Section 6.2.

heading: 5 RELATED WORK
text: While our work and the existing works reviewed in Section 4 attempt to understand CURL by connecting the contrastive loss to the mean supervised loss, there are other approaches; Wang & Isola (2020) showed that the contrastive loss asymptotically favors data representation uniformly distributed over the unit sphere yet aligning across semantically similar samples. Li et al. (2021) proposed an alternative loss function to the contrastive loss based on a kernel metric, following the
6More precisely, Arora et al. (2019) bound the averaged supervised loss over a part of the latent classes rather than Rµ-supv. Thus we can obtain a slightly better upper bound than Arora et al.’s bound shown in Table 1. Nevertheless, the scale of the upper bound is dominated by the coefficient (1− τK)vK+1.
7Note that Nozawa & Sato (2021)’s bound also implies larger K is better. Still, its mechanism and resulting explainability are different from ours. See Appendix D for the further discussions.
similar idea to Wang & Isola (2020). Tosh et al. (2021) showed that a (linear) mean classifier learned in CURL can approximate the (potentially nonlinear) Bayes classifier well.
While our work does not handle data augmentation (DA), several works analyzed how DA affects the performance of downstream classification. Wen & Li (2021) showed that DA is necessary to recover sparse signals under a specific assumption on the model architecture. HaoChen et al. (2021) introduces a notion of the augmentation graph, representing how likely the nearby samples are generated via DA and showed that a type of contrastive loss could be viewed as a low-rank approximation of the adjacency matrix of the augmentation graph. von Kügelgen et al. (2021) proposed a loss function that enables the model to identify invariant factors across DA.
We mention a few works analyzing the other types of self-supervised learning; Garg & Liang (2020) analyzed masked self-supervised learning, Wei et al. (2021) analyzed the input consistency loss for unsupervised learning, and Saunshi et al. (2021) analyzed auto-regressive language models.
As a final remark, multi-sample estimators (Oord et al., 2018; Poole et al., 2019; Song & Ermon, 2020) popularly used in mutual information (MI) estimation are substantially related to the contrastive loss. Although the multi-sample estimators have high bias and low variance compared to variational estimators in general (Poole et al., 2019; Song & Ermon, 2020; Guo et al., 2021), the quantitative analysis of the bias-variance trade-off of the multi-sample MI estimators has yet to be clearly known.8 Note that Tian et al. (2020) and Tschannen et al. (2020) experimentally showed that maximizing tighter MI bound does not necessarily lead to good representation; there is no guarantee that the model can achieve higher MI by the tighter bound.

heading: 6 EXPERIMENTS
text: We verified our theoretical findings with experiments on synthetic datasets (Section 6.1), vision, and language datasets (Section 6.2). The details of the experimental setup are provided in Appendix F.

heading: 6.1 SMALL-SCALE EXPERIMENTS ON SYNTHETIC DATASET
text: Dataset and learning setups. We create a synthetic dataset circle, which is a 2D dataset created as follows: for each class c ∈ [C], 1 000 samples are drawn from Uniform([−0.5 − 0.5], [0.5, 0.5]), normalized, and multiplied by c+1/2. The generated samples are nonlinear and require disentanglement to be linearly separable. We treated 60% of the generated samples as a training dataset and the rest of the samples as a test dataset. We did not use data augmentation.
As a feature extractor f , we used a multi-layer perceptron (the number of units 2-256-256-256) with the ReLU activation functions following after each hidden layer. During the training, the extracted feature representations are normalized. For negative samples, we sampled K ∈ {1, 4, 16, 64, 256} samples without replacement from 2B − 2 points included in the same mini-batch to avoid the influence of mini-batch size B, inspired by Ash et al. (2021).9
Results. Figure 5 shows a single trajectory in the (Rcont, Rµ-supv)-plot and the feasible region (confer Figure 2) for each K. We plotted the trajectories by tracking (Rcont(f (t)), Rµ-supv(f (t))) at each epoch t computed with the test dataset. All trajectories were located in between the upper (Rcont + ∆U) and lower (Rcont + ∆L) bounds as a matter of course. Given that the existing learning bounds provide the much larger upper bounds (Figure 4), our learning bounds provide the finest estimate of the mean supervised loss. In addition, it is remarkable that all trajectories have nearly the same slopes as our learning bounds, which constitutes solid evidence that our learning bounds capture the learning dynamics well.
In Figure 6, the mean supervised loss and accuracy are compared with the different K. For each K, we conducted the same experiments with eight different random seeds, and the standard deviations are shown in the figures. From these figures, it can be concluded that the contrastive loss performance
8There are some quantitative analyses such as the bias of general MI estimators (Gao et al., 2015; McAllester & Stratos, 2020) and the variance of the NWJ/MINE estimators (Song & Ermon, 2020). We will further discuss the implication of the bias analysis in Appendix E.
9Each mini-batch consists of B pairs of positive pairs. The candidates of the negative samples are the 2B− 2 samples excluding the anchor and its paired point.
becomes better with the larger K in the sense that the supervised loss improved and the variance shrank. The variance improvement can be theoretically observed from Figure 5 as well; the larger K is, the smaller the gap between upper and lower bounds becomes.

heading: 6.2 LARGE-SCALE EXPERIMENTS ON VISION AND LANGUAGE DATASETS
text: We used the same datasets as Arora et al. (2019): CIFAR-100 (Krizhevsky, 2009) and Wiki3029 (Arora et al., 2019) datasets. In addition, we used CIFAR-10 (Krizhevsky, 2009) dataset.
Learning setups. To create positive pairs for contrastive learning, we treated the supervised classes as latent classes as in Arora et al. (2019) and Ash et al. (2021). We treated the original supervised classes of CIFAR-10/100 as [C]; C = 10 and C = 100, respectively. We used K in {4, 16, 32, 64, 128, 512} and in {4, 64, 128, 512} for CIFAR-10/100, respectively. For Wiki-3029, we used C ∈ {500, 1 000, 2 000, 3 029} and K ∈ {8, 64, 256, 1 024}. For each different (C,K) pair, we trained the feature extractor f on the training dataset. We then evaluated its supervised performance on the test dataset with mean and linear classifiers. We used ResNet-18 (He et al., 2016)-based feature extractor f for CIFAR-10/100 and the fasttext (Joulin et al., 2017)-based feature extractor for Wiki-3029.
Results. Figure 1 shows the comparison between the estimated upper bounds using Theorem 1 and actual supervised loss on CIFAR-10 for different K on the test dataset. We estimated the bounds by substituting the actual Rcont(f) to the equations shown in Theorem 1 and Table 1. Our learning bound gave the closest upper bound to the experimental value of the supervised loss. The existing learning bounds of Arora et al. (2019) and Ash et al. (2021) were not sharp enough to explain the classification performance. Although Nozawa & Sato’s bound was comparable with our bound, it was valid only in K + 1 ≥ C and tended to increase near K + 1 = C, as we explained in Section 4. We investigated how K affects the test accuracy for different C in Figure 7. The test accuracy improved or was saturated with the larger K for all C on Wiki-3029. In contrast, it was degraded as K increased in mean and linear classifiers on CIFAR-10/100. This behavior could be partly because of the gap between the cross-entropy loss and the supervised accuracy—the theory of CURL, including the existing studies, usually focuses on the cross-entropy loss only. Figure 9 in Appendix F.6 revealed that the supervised loss was not significantly worse with the larger K on CIFAR-10/100.
With the smaller K and large C, we found that long epochs were more effective to improve classification accuracy than increasing the negative sample size K (Figure 8b). While similar experimental results were reported by Chen et al. (2020, Figure 9), it is important to remark that we randomly
drew K negative samples from the 2B − 2 samples in the given mini-batch at each iteration as in Ash et al. (2021)—a different approach was used by Chen et al. (2020) to regard the all samples in the mini-batch except an anchor sample as negative samples. Under our experimental setup, a learner may encounter less diverse samples with the smaller K even if the mini-batch size B is the same, which could make the performance of downstream classification worse—the longer epochs are necessary to mitigate the issue. Since the CIFAR-10 dataset has a smaller C and is simpler than the CIFAR-100, all accuracies were saturated with similar epochs for all K (Figure 8a).

heading: 7 CONCLUSION
text: In this study, we established novel theoretical bounds for contrastive unsupervised representation learning. We derived sharp upper and lower bounds on a downstream classification loss that are tight in the negative sample size. They suggest that the contrastive loss can be used as a downstream loss estimator and its estimation gap decays with larger negative samples. In the experiments, we verified that our bounds well explained learning dynamics on the synthetic dataset, and the estimation gap was large with smaller negative samples. In addition, the empirical downstream classification loss was best explained by our learning bound compared to the existing ones. It is left open to fill the gap between the supervised loss and accuracy. In addition, we may understand contrastive unsupervised representation learning better by incorporating the optimization perspective into the theoretical analysis.

heading: ETHICS STATEMENT
text: Since this study is theoretical in nature, we do not have specific ethical concerns.

heading: REPRODUCIBILITY STATEMENT
text: All experimental codes are available in the supplementary material. In addition, the details of experimental datasets and hyper-parameters of learning algorithms are described in Appendix F.
All theorems’ proofs are described in Appendix B. Appendix A provides Lemmas used in Appendix B. Appendices C and D provide how to derive equations used in Section 3.2 and Section 4, respectively.
«APPENDIX»

heading: SHARP LEARNING BOUNDS FOR CONTRASTIVE UNSUPERVISED

heading: REPRESENTATION LEARNING
text: As an additional notation, the d-dimensional ball of radius r associated with the Lp-norm is denoted by Bdp(r) := {x ∈ Rd | ‖x‖p ≤ r}. For z ∈ RC , the log-sum-exp function is denoted by LSE (z) := ln( ∑ c∈[C] exp(zc)).

heading: A USEFUL LEMMAS
text: In this section, a few lemmas are introduced in order to prove the main results. Lemma 3. For z ∈ RN ,
ln 1 + ∑ n∈[N ] exp(−zi)  ≥ − ln 1 + ∑ n∈[N ] exp(zk) + ∆0, (10) where ∆0 := 2 ln(1 +N).
Proof. Define H(z) := LSE (−[0 z1 . . . zN ]) + LSE ([0 z1 . . . zN ]). Then, ∆0 is a lower bound of H . Since
∂H ∂zi = − exp(−zi)∑ n∈[N ] exp(−zn) + exp(zi)∑ n∈[N ] exp(zn)
(11)
for all i ∈ [N ], z = 0N satisfies the first-order optimality condition of H . By noting that H is convex due to the convexity of the log-sum-exp functions, H is minimized at z = 0N . Hence, we can choose ∆0 = H(0N ) = 2 ln(1 +N).
Lemma 4. For z0 ∈ [−L2, L2], z ∈ [−L2, L2]N , and ρ > 0,
ln exp(−z0) (1 + ρ) exp(−z0) + ρ ∑ n∈[N ] exp(−zn) ≥ − ln exp(z0) (1 + ρ) exp(z0) + ρ ∑ n∈[N ] exp(zn) −∆1,
(12) where ∆1 := 2 ln ( ρ ( N + 1 + 1ρ ) cosh(L2) ) .
Proof. The goal is to find a tight upper bound ∆1 of
− ln exp(z0) (1 + ρ) exp(z0) + ρ ∑ n∈[N ] exp(zn) − ln exp(−z0) (1 + ρ) exp(−z0) + ρ ∑ n∈[N ] exp(−zn) (13)
= ln (1 + ρ) exp(z0) + ρ ∑ n∈[N ] exp(zn) + ln (1 + ρ) exp(−z0) + ρ ∑ n∈[N ] exp(−zn)  (14)
= 2 ln ρ+ ln {( 1 + 1ρ ) exp(z0) + ∑ n exp(zn) } + ln {( 1 + 1ρ ) exp(−z0) + ∑ n exp(−zn) } ︸ ︷︷ ︸
:=H′(z̃)
,
(15)
where z̃ := [z0 z>]>.
Equivalently, we aim at an upper bound of H ′(z̃) for z̃ ∈ BN+1∞ (L2). Observe that H ′(z̃) =
LSE ( z̃ + [ ln (
1 + 1ρ
) 0 . . . 0 ]>) + LSE ( −z̃ + [ ln (
1 + 1ρ
) 0 . . . 0 ]>) is the sum of the
two log-sum-exp functions after adding the constant vector hence it is convex in z̃. In addition, the domain BN+1∞ (L2) is a compact convex polytope. Henceforth, every vertex of the polytope, z̃ ∈ {−L2, L2}N+1, is a local maximizer because maximizing H ′(z̃) is concave minimization over a convex polytope (Pardalos & Rosen, 1986). Since H ′(z̃) is symmetric in every zn except z0, we need to divide the cases depending on either z0 = L2 or z0 = −L2 and compare the maximum values of H ′(z̃).
If z0 = L2: In order to maximize H ′(z̃), it is sufficient to test the vertices z̃ ∈ {z ∈ BN+1∞ (L2) | z0 = L 2} and see the difference between H̃ ′(m) and H̃ ′(m+ 1), where
H̃ ′(m) := H ′ ( L2, L2, . . . , L2︸ ︷︷ ︸
m
,−L2, . . . ,−L2︸ ︷︷ ︸ N−m
) (16)
= ln {( m+ 1 + 1
ρ
) exp(−L2) + (N −m) exp(L2) } + ln {( m+ 1 + 1
ρ
) exp(L2) + (N −m) exp(−L2) } (17)
for m ∈ {0, . . . , N} to seek the maximum. Here, the definition of H̃ ′ can be naturally extended over the real domain m ∈ R. A simple algebra shows
exp ( H̃ ′(m) ) = ( 2− (exp(2L2) + exp(−2L2)) )︸ ︷︷ ︸ <0 (AM-GM inequality) ( m− N − 1− 1ρ 2 )2 + Const. (18)
Since H̃ ′ is concave over m ∈ R, H̃ ′ is maximized at m = [ N−1− 1ρ
2 ] + (< N). If ρ < 1N−1 , then
the maximum value is
H̃ ′
( N − 1− 1ρ
2
) = 2 ln (( N + 1 + 1
ρ
) cosh(L2) ) . (19)
If ρ ≥ 1N−1 , H̃ ′ is maximized at m = 0 and its value is
H̃ ′(0) = ln ( N2 + ( 1 + 1
ρ
)2 +N ( 1 + 1
ρ
) (exp(2L2) + exp(−2L2)) ) (20)
≤ ln
( exp(2L2) + exp(−2L2)
2
( N2 + ( 1 + 1
ρ
)2 + 2N ( 1 + 1
ρ
))) (21)
= ln (( N + 1 + 1
ρ
) cosh(2L2) ) , (22)
where the inequality follows from the AM-GM inequality exp(2L 2)+exp(−2L2)
2 ≥ 1.
If z0 = −L2: Similarly, we define
H̃ ′(m) := H ′ −L2, L2, . . . , L2︸ ︷︷ ︸ m ,−L2, . . . ,−L2︸ ︷︷ ︸ N−m  (23) = ln { m exp(−L2) + ( N + 1 + 1
ρ −m
) exp(L2) } + ln { m exp(L2) + ( N + 1 + 1
ρ −m
) exp(−L2) } , (24)
and extends its definition over the real line m ∈ [0, N ]. Since
exp ( H̃ ′(m) ) = ( 2− (exp(2L2) + exp(−2L2)) )︸ ︷︷ ︸ <0 (AM-GM inequality) ( m− N + 1 + 1ρ 2 )2 + Const, (25)
H̃ ′ is maximized at m = min { N+1+ 1ρ 2 , N } (> 0). If ρ ≥ 1N−1 , H̃ ′ is maximized at m = N+1+ 1ρ 2 and its value is
H̃ ′
( N + 1 + 1ρ
2
) = 2 ln (( N + 1 + 1
ρ
) cosh(L2) ) . (26)
If ρ < 1N−1 , H̃ ′ is maximized at m = N and its value is
H̃ ′(N) = ln ( N2 + ( 1 + 1
ρ
)2 +N ( 1 + 1
ρ
) (exp(2L2) + exp(−2L2)) ) (27)
≤ ln (( N + 1 + 1
ρ
) cosh(2L2) ) . (28)
After all, H̃ ′ is bounded from above by either
2 ln (( N + 1 + 1
ρ
) cosh(L2) ) or ln (( N + 1 + 1
ρ
) cosh(2L2) ) . (29)
These two values can be compared as follows.
2 ln (( N + 1 + 1
ρ
) cosh(L2) ) − ln (( N + 1 + 1
ρ
) cosh(2L2) ) (30)
= ln ( N + 1 + 1
ρ
) + ln cosh2(L2)− ln cosh(2L2) (31)
= ln ( N + 1 + 1
ρ
) + ln 1 + 1cosh(2L2)
2 (32) ≥ ln ( N + 1 + 1
ρ
) (33)
> 0, (34)
where the first inequality is due to the AM-GM inequality exp(2L 2)+exp(−2L2)
2 ≥ 1. Hence, regardless of ρ, 2 ln (( N + 1 + 1ρ ) cosh(L2) ) is a tight upper bound of H̃ ′.
Lemma 5. For all z0 ∈ R and z ∈ RK such that z0, zk ∈ [−L2, L2] (∀k ∈ [K]),
ln exp(−z0) exp(−z0) + ∑ k∈[K] exp(−zk)
≥ − ln exp(z0) exp(z0) + ∑ k∈[K] exp(zk)
− 2 ln { (K + 1) cosh(L2) } . (35)
Proof. We write z̃ := [z0 z>]>. Let H(z̃) be a function such that
H(z̃) := − ln exp(z0) exp(z0) + ∑ k∈[K] exp(zk) − ln exp(−z0) exp(−z0) + ∑ k∈[K] exp(−zk)
(36)
= ln K+1∑ k=1 exp(z̃k) + ln K+1∑ k=1 exp(−z̃k). (37)
Our goal is to find a tight upper bound of H(z̃) for z̃ ∈ BK+1∞ (L2). Observe that H(z̃) is the sum of the two log-sum-exp functions hence it is convex in z̃. In addition, the domain BK+1∞ (L2) is a compact convex polytope. Henceforth, every vertex of the polytope, z̃ ∈ {−L2, L2}K+1, is a local maximizer because maximizing H(z̃) is concave minimization over a convex polytope (Pardalos & Rosen, 1986). Since H(z̃) is symmetric in every element z̃k, it is sufficient to test the vertices and see the difference between
H (L2, . . . , L2︸ ︷︷ ︸ # = j ,−L2, . . . ,−L2)  ︸ ︷︷ ︸
:=H̃(j)
and H (L2, . . . , L2︸ ︷︷ ︸ # = j + 1 ,−L2, . . . ,−L2)  ︸ ︷︷ ︸
:=H̃(j+1)
(38)
for j ∈ {0, . . . ,K} to seek out the global maximum. For 0 ≤ j ≤ K, a simple algebra shows exp ( H̃(j) ) − exp ( H̃(j + 1) ) = (K − 2j) { 2− ( exp(2L2) + exp(−2L2) )}︸ ︷︷ ︸ ≤0
because of AM-GM inequality
, (39)
from which we can tell that H̃(j) is maximized at j = K/2 when K is even and j = (K + 1)/2 when K is odd. In addition, it is confirmed that
exp ( H̃ ( K
2
)) − exp ( H̃ ( K + 1
2
)) = 2− ( exp(2L2) + exp(−2L2) ) 4
(40)
≤ 0, (41)
where the AM-GM inequality is invoked at the last line. Eventually, H̃ ((K + 1)/2) turns out to be a tight upper bound of H(z̃) for z̃ ∈ BK+1∞ (L2). It is elementary to confirm H̃ ((K + 1)/2) = 2 ln { (K + 1) cosh(L2) } .

heading: B PROOFS OF MAIN RESULTS
text: In this section, we provide proofs for the main results, Theorems 1 and 2.
Theorem 1. For all f such that ‖f(x)‖2 ≤ L (∀x ∈ X ), the following inequality holds.
Rµ-supv(f) ≤ Rcont(f) + ∆U, (3)
where ∆U := 2 ln((CKπ(−1) + 1) cosh(L2))− 2 ln(1 +K)− lnKπ(−1).
Proof of Theorem 1. Define the two constants
∆0 := 2 ln(1 +K), (42)
∆1 := 2 ln((CKπ(−1) + 1) cosh(L 2)). (43)
The proof begins with the Jensen’s inequality applied on the contrastive loss:
Rcont(f) = E c+,{c−k },x,x+,{x − k } ln 1 + ∑ k∈[K] exp(f(x)>(f(x−k )− f(x +)))  (44) ≥ E c+,{c−k },x ln 1 + ∑ k∈[K] exp(f(x)>(µc−k − µc+))
 (45) ≥ − E
c+,{c−k },x ln 1 + ∑ k∈[K] exp(f(x)>(µc+ − µc−k )) + ∆0, (46)
where the second inequality follows from Lemma 3. The first term, the origin-symmetric transform of the contrastive loss, is further bounded as follows.
− E c+,{c−k },x ln 1 + ∑ k∈[K] exp(f(x)>(µc+ − µc−k ))  ≥ − E
c+,x ln 1 + ∑ k∈[K] E c exp(f(x)>(µc+ − µc))  (47) ≥ − E
c+,x ln
1 +Kπ(−1) 1 + ∑
c∈[C]\{c+}
exp(f(x)>(µc+ − µc))  , (48) where the first inequality is the Jensen’s inequality and the second inequality holds by noting that Ec[A] = ∑ c πcA ≥ ∑ c π(−1)A. In order to proceed further, the origin-symmetric transform is needed to be applied on the lower-bounding term, resulting in a term aligning to the mean supervised loss.
− E c+,x ln
1 +Kπ(−1) 1 + ∑
c∈[C]\{c+}
exp(f(x)>(µc+ − µc))  ≥ E c+,x ln 1 +Kπ(−1) 1 + ∑
c∈[C]\{c+}
exp(f(x)>(µc − µc+)) −∆1 (49) = E c+,x ln  1 Kπ(−1) + 1 + ∑
c∈[C]\{c+}
exp(f(x)>(µc − µc+)) −∆1 + lnKπ(−1) (50) ≥ E c+,x ln 1 + ∑ c∈[C]\{c+} exp(f(x)>(µc − µc+))
−∆1 + lnKπ(−1) (51) = Rµ-supv(f)−∆1 + lnKπ(−1), (52)
where the first inequality is a consequence of Lemma 4 and the second inequality is simply observed by ln( 1Kπ(−1) + x) ≥ lnx for any x > 0 since 1 Kπ(−1)
≥ 0. Combining all the above, we get the final bound Rµ-supv(f) ≤ Rcont(f)−∆0 + ∆1 − lnKπ(−1).
Even if Theorem 1 assumes Y = [C], it can be extended to the cases Y ⊆ [C] (subset) and Y is a coarse-grained set of [C]. When Y 6= [C], Rµ-supv is defined over the class set Y , while Rcont is defined over the class set [C]. In the subset case, we can replace Eq. (52) with the subset class bound:
E c+,x ln 1 + ∑ c∈[C]\{c+} exp(f(x)>(µc − µc+))  ≥ E c+,x ln 1 + ∑ c∈Y\{c+} exp(f(x)>(µc − µc+))
 = Rµ-supv(f). (53) In the coarse-grained case, Eq. (52) holds without modification. Theorem 2. For all f such that ‖f(x)‖2 ≤ L (∀x ∈ X ), the following inequality holds.
Rµ-supv(f) ≥ Rcont(f) + ∆L, (4)
where ∆L := H (π) + ln K(K+1)2 − 2 ln cosh(L 2).
Proof of Theorem 2. The proof is essentially a consequence of the Fenchel’s inequality and the Jensen’s inequality. First, by noting that the convex conjugate of the log-sum-exp function is the
negative Shannon entropy, the following identity is obtained.
Rµ-supv(f) = E x,y
[ −f(x)>µy + LSE (Wµf(x)) ] (54)
= E x,y
[ −f(x)>µy + sup
p∈4C
{ p>(Wµf(x)) + H (p) }] . (55)
If we choose an arbitrary p ∈ 4C , Rµ-supv(f) is lower bounded (Fenchel’s inequality). Our choice is p = π. Recall that K is the number of negative samples. Then,
Rµ-supv(f) ≥ E c+,x −f(x)>µc+ + ∑ c−∈Y πc−f(x) >µc− + H (π) (56) = E c+ E x,x+∼D2
c+
[ −f(x)>f(x+) + f(x)> ( E c− E x−∼Dc− [ f(x−) ])] + H (π) (57)
= E c+ E x,x+ −f(x)>f(x+) + 1 K ∑ k∈[K] E c−k E x−k [f(x)>f(x−k )] + H (π) (58) = E c+,{c−k }k E x,x+,{x−k }k − 1 K ∑ k∈[K] ( f(x)>f(x+)− f(x)>f(x−k )
)+ H (π) (59) = E c+,{c−k }k E x,x+,{x−k }k − 1 K ∑ k∈[K] ln exp(f(x)>(f(x+)− f(x−k )))
+ H (π) . (60) Here, we can proceed with the Jensen’s inequality to lower bound the first term: for a non-negative vector z ∈ RN≥0, the inequality −N−1 ∑ i∈[N ] ln zi ≥ − ln(N−1 ∑ i∈[N ] zi) holds. If we set zk = exp(f(x) >(f(x+)− f(x−k ))) for k ∈ [K],
Rµ-supv(f)−H (π)
≥ E c+,{c−k }k,
x,x+,{x−k }k
[ − ln ∑ k∈[K] exp(f(x)
>(f(x+)− f(x−k ))) K
] (61)
≥ E c+,{c−k }k,
x,x+,{x−k }k
[ − ln exp(f(x)>(f(x+)− f(x+))) + ∑ k∈[K] exp(f(x)
>(f(x+)− f(x−k ))) K
]
(62)
= E c+,{c−k }k,
x,x+,{x−k }k
[ ln
exp(−f(x)>f(x+)) exp(−f(x)>f(x+)) + ∑ k∈[K] exp(−f(x)>f(x − k ))
] + lnK. (63)
Finally, by using Lemma 5,
Rµ-supv(f)−H (π)
≥ E c+,{c−k }k E x,x+,{x−k }k
[ − ln exp(f(x) >f(x+))
exp(f(x)>f(x+)) + ∑ k∈[K] exp(f(x) >f(x−k ))
] + lnK (64)
− 2 ln { (K + 1) cosh(L2) }
(65)
= Rcont(f) + lnK − 2 ln(K + 1)− 2 ln cosh(L2), (66)
which concludes the proof.
Unlike Theorem 1, Theorem 2 can only be extended to the coarse-grained Y from the case Y = [C]. Indeed, the first expectation term on the right-hand side of Eq. (56) can be transformed as
E c+,x −f(x)>µc+ + ∑ c−∈Y πc−f(x) >µc−  = E c+,x −f(x)>µc+ + ∑ c−∈[C] πc−f(x) >µc−  , (67) because of the linearity of the expectation. On the other hand, it is not straightforward to lower-bound Eq. (56) by the expectation over the label set [C] when Y is a strict subset of [C].

heading: C ESSENTIAL BOUNDS OF MEAN SUPERVISED AND CONTRASTIVE LOSSES
text: This section provides a supplementary explanation of the essential lower bounds of the mean supervised and contrastive losses. The common approaches of CURL applies the normalization on representation, in order to employ the cosine similarity f(x)
>f(x′) ‖f(x)‖2·‖f(x′)‖2 as the similarity metric. Then,
it is reasonable to assume ‖f(x)‖2 ≤ L for all x with our data representation f . The normalized representation corresponds to the case L = 1.
When we introduce the constraint ‖f(x)‖2 ≤ L, the mean supervised loss and contrastive loss are restricted as well. As for the mean supervised loss,
Rµ-supv(f) ≥ inf ‖f ′‖2≤L Rµ-supv(f ′) (68)
= inf ‖f ′‖2≤L E
ln 1 +∑
c6=y
exp(f ′(x)>(µc − µy))  (69) = ln ( 1 + (C − 1) exp(−2L2) ) (70)
(:= R∗µ-supv). (71)
As for the contrastive loss,
Rcont(f) ≥ inf ‖f ′‖2≤L Rcont(f ′) (72)
= inf ‖f ′‖2≤L E c+,{c−k },x E x+,{x−k }
ln 1 + ∑
k∈[K]
exp(f ′(x)>(f ′(x−k )− f ′(x+)))  (73) ≥ inf ‖f ′‖2≤L
E c+,{c−k },x
ln 1 + ∑
k∈[K]
exp(f ′(x)>(µc−k − µc+))  (74) =
K∑ m=0 ( K m )( 1 C )m( 1− 1 C )K−m ln{1 +m+ (K −m) exp(−2L2)} (75) (:= R∗cont), (76)
where the Jensen’s inequality is applied in the second inequality.

heading: D DISCUSSION OF EXISTING LEARNING BOUNDS
text: In this section, we describe the existing learning bounds in details to make them comparable with our main results. Then, we further discuss the detailed comparison between our theory and existing works. Before the discussion, we need to introduce the sub-class loss (of the mean classifier), which is the supervised classification loss over a subset of classes:
Rsub(f , T ) := E x,y
[ − ln
exp(µ>y f(x))∑ c∈T exp(µ > c f(x))
] , (77)
where T ⊆ [C] is a subset of classes and y is drawn from the subset of π with respect to T .
Arora et al.’s bound. We introduce additional notation that Arora et al. (2019) use. For a subset of classes T ,
• Q ⊆ [C] is the set of distinct classes in c+, c−1 , . . . , c − K
• I+ := {k ∈ [K] | c−k = c+} • Col := ∑ k∈[K] 1{c+=c−k } = |I+|
• ρmax(T ) := maxc∈T πc
• ρ+min(T ) := minc∈T Pc+,{c−k }k∼πK+1(c + = c | Q = T, I+ = ∅)
• τK := P(I+ 6= ∅)
Arora et al. (2019) prove a finite-sample learning bound in Theorem B.1. In its proof, Eq. (26) is a learning bound established for a fixed f . For the comparison, we focus on their Eq. (26):
(1− τK) E T∼πK+1
[ ρ+min(T )
ρmax(T ) Rsub(f , T ) ] ≤ Rcont(f)− τK E
c+,{c−k }k∼πK+1
[ ln(Col + 1) ∣∣I+ 6= ∅] . (78) We split the expectation term in the left-hand side as follows.
E [ ρ+min(T )
ρmax(T ) Rsub(f , T ) ] = P(T covers [C])︸ ︷︷ ︸
=vK+1
·E [ ρ+min(T )
ρmax(T ) Rsub(f , T )
∣∣∣∣T covers [C]]
+ P(T does not cover [C]) · E [ ρ+min(T )
ρmax(T ) Rsub(f , T ) ∣∣∣∣T does not cover [C]] (79) ≥ vK+1 ρ+min([C])
ρmax([C]) Rsub(f , [C])︸ ︷︷ ︸ =Rµ-supv(f) . (80)
Under the uniform class prior assumption (π = 1/C · 1), ρmax([C]) = 1/C, and we can pick any class c0 ∈ [C] by the symmetry and ρ+min([C]) = P(c+ = c0 | Q = [C], I+ = ∅) = 1/C. In addition,
τK E c+,{c−k }k∼πK+1
[ ln(Col + 1) ∣∣I+ 6= ∅] = E [ln(Col + 1)]− (1− τK)E [ln(Col + 1)∣∣I+ = ∅] (81)
= E [ln(Col + 1)] . (82)
As a result, we obtain the following simplified expression in Table 1:
Rµ-supv(f) ≤ 1
(1− τK)vK+1 {Rcont(f)− E[ln(Col + 1)]} . (83)
Nozawa & Sato’s bound. The learning bound provided by Nozawa & Sato (2021, Theorem 8) involves a factor resulting from data augmentation and self-supervised learning setting. By dropping this (negative) factor, the learning bound is
Rcont(f) ≥ 1
2
{ vK+1Rµ-supv(f) + (1− vK+1) E
T∼πK+1 [Rsub(f , T )] + E[ln(Col + 1)]
} (84)
≥ 1 2 {vK+1Rµ-supv(f) + E[ln(Col + 1)]} , (85)
resulting in the bound in Table 1. The sub-class loss may be safely dropped because it has the coefficient 1− vK+1, which is expected to be exponentially small in K.
Ash et al.’s bound. Ash et al. (2021, Theorem 5) provides the following learning bound Rµ-supv(f) ≤ 2 ⌈ 2(1−π(−1))HC−1 Kπ(−1) ⌉ (1− π(1))K { Rcont(f)− τK E
c+,{c−k }k∼πK+1
[ ln(Col + 1) ∣∣I+ 6= ∅]} . (86)
By substituting π = 1/C · 1 and τK E[ln(Col + 1) | I+ 6= ∅] = E[ln(Col + 1)], the bound in Table 1 is obtained.
Detailed comparisons. As we stated in Section 4 of the main text, only our bound agrees well with the experimental fact that the larger K is better for all K regions:
• Arora et al. (2019): Large K degrades the performance because of the label collision. • Nozawa & Sato (2021): Large K improves the performance for K > C. • Ash et al. (2021): The optimal K exists by the collision-coverage trade-off.
Even though the claim by Nozawa & Sato (2021) is similar with ours, we discovered a different underlying mechanism to support this idea, which leads to better explainability of empirical facts.
The proof of Nozawa & Sato (2021) is based on the idea of label coverage: The more negative samples we draw (larger K), the more likely the negative samples can cover all class labels. The upper bound based on this idea is only activated when K > C because label coverage is impossible with K ≤ C. This inability contradicts the real experiments including Chen et al. (2021), which showed that CURL exhibits reasonable performance even with small K.
Our proof leverages the idea that Rcont and Rµ-supv have the similar log-sum-exp functional forms. This similarity casts Rcont as a surrogate estimator of Rµ-supv and its estimation gap is reduced with larger K. Even with small K, the upper bound of Rµ-supv is loose but not vacuous thereby the estimation of Rµ-supv is still possible. Our theoretical claim reveals that the surrogate gap improves in O(ln 1/K) for all K regions, which is in good agreement with the real experiments. Eventually, our theory provides practical feedback such that one may reduce K (even smaller than C) to trade off the downstream performance with the computational cost.

heading: E RELATIONSHIP TO MUTUAL INFORMATION (MI) ESTIMATION
text: The contrastive loss Rcont we studied in this paper is also known as the InfoNCE loss (Oord et al., 2018), which is known to be deeply related to the multi-sample estimation of mutual information (MI) (Oord et al., 2018; Poole et al., 2019; Song & Ermon, 2020). Recently, the theoretical limitations of sample-based MI estimation have been analyzed (Gao et al., 2015; McAllester & Stratos, 2020). These studies revealed that a particular type of sample-based estimator of MI (Gao et al., 2015) or its lower bound (McAllester & Stratos, 2020) can be upper bounded by O(lnN) for the number of samples N . In this section, we discuss the implications of these limitations in the CURL setting.
Given two random variables X and Y , suppose that we have K + 1 randomly drawn pairs {(xi, yi)}K+1i=1 from these random variables such that for all (i, j), (xi, yj) can be regarded as a positive pair when i = j, and otherwise can be regarded as a negative pair. Poole et al. (2019, Equation 10) derived the following lower bound for MI:
I(X;Y ) ≥ IK+1NCE := E
[ 1
K + 1 K+1∑ i=1 ln exp(s(xi, yi)) 1 K+1 ∑K+1 j=1 exp(s(xi, yj))
] , (87)
where I(X;Y ) is the MI between X and Y , and s(x, y) is a critic function. This lower bound estimator can be rewritten using Rcont as follows:
IK+1NCE := E
[ 1
K + 1 K+1∑ i=1 ln exp(s(xi, yi)) 1 K+1 ∑K+1 j=1 exp(s(xi, yj))
] (88)
= E
[ 1
K + 1 K+1∑ i=1 ln exp(s(xi, yi))∑K+1 j=1 exp(s(xi, yj))
] + ln(K + 1) (89)
= E
[ 1
K + 1 K+1∑ i=1 ln exp(s(xi, yi)) exp(s(xi, yi)) + ∑ j 6=i exp(s(xi, yj))
] + ln(K + 1) (90)
= E [ ln
exp(s(x, x+)) exp(s(x, x+)) + ∑K j=1 exp(s(x, x − j ))
] + ln(K + 1) (91)
= −Rcont(f) + ln(K + 1). (92)
The first equality is obtained by putting the constant in the denominator outside. The third equality comes by replacing the notation (xi, yi) with (x, x+) under the assumption that all (xi, yi) come from the same iid distribution. By setting s(x, y) := f(x)>f(y), we obtain the last equation.
Here, McAllester & Stratos (2020) gave the following theorem for the sample-based estimator of the lower bound on MI.
Theorem 6 (McAllester & Stratos (2020) Theorem 1.1, informal). Let ÎN be any mapping from N samples of (X,Y ) to R that satisfies
I(X;Y ) ≥ ÎN ({(xi, yi)}Ni=1) (93)
in high probability, then the following relationship holds in high probability:
ÎN ({(xi, yi)}Ni=1) ≤ 2 lnN + 5. (94)
Since IK+1NCE satisfies the condition for Î K+1, we now have the following:
−Rcont(f) + ln(K + 1) ≤ 2 ln(K + 1) + 5 =⇒ Rcont(f) ≥ − ln(K + 1)− 5. (95)
However, the right-hand statement always holds by the construction ofRcont for all f (∀f , Rcont(f) ≥ 0). In other words, in the case of the CURL setting, McAllester & Stratos (2020)’s theorem does not restrict Rcont, which means that the large K effect investigated in our paper comes from a completely different mechanism from the above theorem. The existing studies on sample-based MI estimation are worthwhile in the sense that these works revealed the O(lnN) effect on the non-trivial estimators such as k-NN based estimator (Gao et al., 2015) or any kind of lower bound estimator (McAllester & Stratos, 2020).

heading: F EXPERIMENTAL DETAILS

heading: F.1 SYNTHETIC DATASET
text: We used Adam (Kingma & Ba, 2015) optimizer with the weight decay of coefficient 0.01 to all parameters. The mini-batch size was set to B = 1 024 and the number of epochs was 300. The learning rate was set to 0.01 with ReduceLROnPlateau scheduler (patience: 10 epochs) provided by PyTorch (Paszke et al., 2019).
F.2 CIFAR-10/100
We treated 10% training samples as a validation dataset by sampling class uniformly. We used the original test dataset for testing. We used the same data-augmentation as in the CIFAR-10 experiment by Chen et al. (2020) during contrastive learning and linear supervised training of the linear classifier.
As a feature extractor f , we modified the ResNet-18 (He et al., 2016) by following the convention of self-supervised representation learning (Chen et al., 2020, B.9); replacement of the first convolutional layer with a smaller one, removal of the first max-pooling layer, and replacement of the final fullyconnected layer with a nonlinear projection head whose dimensional is 32.10
Since we need to enlarge the negative samples size K that depends on the size of mini-batches, we followed a large mini-batch training setting used in recent self-supervised learning (Chen et al., 2020;
10Unlike the reported results by Chen et al. (2021), smaller dimensionality, i.e., 32 gives better downstream accuracy on CIFAR-100 than 64 or 128. This difference might come from the differences in the loss function and positive pair’s generation process.
Caron et al., 2020). We used LARC (You et al., 2017) optimizer wrapping the momentum SGD, whose momentum term was 0.9. We applied weights decay of coefficient 10−4 to all parameters except for all bias terms and batch norm’s parameters. The base learning rate was initialized at lr× √ B, where lr ∈ {2, 4, 6} × 1/64 and mini-batch size B = 1 024 inspired by SimCLR’s squared learning rate scaling. As a learning rate scheduler for each iteration, we used linear warmup during the first 10 epochs and cosine annealing without restart (Loshchilov & Hutter, 2017) during the rest epochs. The number of epochs was 2 000.
We implemented our experimental code by using PyTorch (Paszke et al., 2019)’s distributed dataparallel training (Li et al., 2020) on 8 NVIDIA A100 GPUs provided by the internal cluster. Therefore we replaced the all batch normalization layer with SyncBatchNorm module provided by PyTorch.11 To accelerate contrastive learning, we used automatic mixed-precision training provided by PyTorch.
F.3 WIKI-3029
Wiki-3029 contains 3 029 English Wikipedia article pages. Each page consists of 200 sentences. Since the dataset does not have the explicit train/validation/test splits, we split the dataset into 70%/10%/20% train/validation/test datasets, respectively. As a pre-processing, we tokenized the dataset using torchtext’s basic_english tokenizer. After tokenization, we removed the tokens whose frequency is less than 5 in the training dataset. We did not use data augmentation.
We used fasttext (Joulin et al., 2017)’s based feature extractor.12 In our preliminary experiments, only using a word embedding layer and average pooling among words perform better than either additional linear or nonlinear projection heads. A similar model to ours is also used in Ash et al. (2021). The dimensionality of the word embedding layer was 256.
We mainly followed the same optimization setting as our CIFAR-10/100 experiments. We note that the mini-batch size B = 2 048; the initial learning rate lr was selected in {1, 2, 3, 4} × 1/40; no weights decay; the number of epochs was 90; and perform linear warmup during the first 3 epochs. When we decrease C, the number of epochs is multiplied by 3000/C for simplicity.13

heading: F.4 CONTRASTIVE LEARNING
text: By following the data generation process in contrastive representation learning and existing work (Arora et al., 2019; Ash et al., 2021), we treated the supervised classes Y as latent classes [C]. After obtaining training/validation/test datasets as described above, we carefully constructed positive pairs for contrastive learning before training14 as follows; We treated each sample in the training data as an anchor sample. We drew a different sample from the same latent class of each anchor sample as a positive sample in the training dataset. For negative samples, we drew K negative samples from other samples in the same mini-batch by following the convention of self-supervised representation learning such as SimCLR (Chen et al., 2020). Since Chen et al. (2020) used all other samples as negative samples, the negative samples size and the size of mini-batches depend on each other: K = 2B − 2. To relax the effect of the difference of the mini-batch size when we change K, we drew K samples without replacement from 2B− 2 inspired by Ash et al. (2021). In this sampling, we guaranteed to draw at most one sample from each positive pair because we are concerned about the relation between the number of latent classes and K. We did not use validation and test datasets during contrastive representation learning.

heading: F.5 MEAN AND LINEAR CLASSIFIERS’ EVALUATION
text: For evaluation, we reported the test accuracy values of mean and linear classifiers. For a linear classifier, we used Nesterov’s momentum SGD, whose momentum coefficient was 0.9 without weight
11See Wu & Johnson (2021, Sec. 6.2) for more detailed discussion of this replacement for contrastive learning. 12Arora et al. (2019) uses GRU-based feature encoder with frozen word embeddings of GloVe (Pennington et al., 2014) trained on commonCrawl. 13We found the contrastive learning did not yield good feature representations for a downstream task without this longer training. 14We can create the labeled dataset, especially with non-overlapped latent classes, if we draw positive samples at each iteration or epoch during optimization using stochastic gradient descent.
decay. We set the mini-batch size B = 256 and B = 512 for CIFAR-10/100 and Wiki-3029, respectively. We used cosine annealing without restart as a learning rate scheduler for each iteration. We set 100 and 30 epochs for CIFAR-10/100 and Wiki-3029 datasets, respectively. For CIFAR-10/100, we set learning rate as 0.03. For Wiki-3029, we searched the learning rate in {0.5, 1, 5, 10, 50}×1/103. The learning rate was scaled by using squared learning rate scaling. For linear evaluation of CIFAR10/100, we used PyTorch’s distributed data-parallel training. We calculated the test accuracy by using the best combination of the contrastive model and the hyper-parameter of a linear classifier that maximizes the validation accuracy. We repeated contrastive learning and downstream task’s evaluation three times with different random seeds and reported the averaged values.

heading: F.6 DETAILS OF FIGURE 1
text: Before computing the upper bounds and supervised loss, we normalized feature representations f(x) learned in Appendix F.4 to ensure L = 1, which is the upper bound of ‖f(x)‖2,∀x. For each random seed and the number of negative samplesK, we selected learned feature encoder f that got the highest validation mean supervised accuracy in different learning rates of the optimizer of the contrastive learning. Then we calculated the test supervised loss value by using the selected contrastive models.
Using the same feature encoder with L2 normalization, we calculated the contrastive loss on the test dataset. To do so, we created positive pairs by the same procedure on the test dataset as described in Appendix F.4. Negative samples were also drawn from the other samples in the mini-batches as the contrastive learning step described in Appendix F.4. To calculate the contrastive loss, we used the same batch size as the contrastive learning step and only one epoch. Since this contrastive loss calculation was stochastic due to the sampling of positive and negative samples, we repeated the contrastive loss calculation 25 times and averaged them to create plot Figure 1. Note that we used the theoretical values of τK , vK+1,E ln(Col + 1) that are shown in the existing upper bounds on Table 1 rather than the simulated values.
Figure 9 shows the enlarged version of Figure 1 and the same plot using CIFAR-100. This figure focuses on the detailed comparison between the test datasets’ empirical supervised loss values and theoretical bounds. For both CIFAR-10/100 datasets, there were almost no changes in the supervised loss as K varied, and the losses were slightly larger in the region where K was small. These results are consistent with the theoretical estimation of the upper bounds (solid lines).

heading: F.7 DETAILS OF FIGURE 8
text: During minimization of the contrastive loss to learn f in Appendix F.4, we saved the model’s weight at every 200 epochs. We reported the test mean supervised accuracy using f that maximized validation accuracy among different learning rate values.

heading: F.8 ADDITIONALLY USED LIBRARIES
text: In our experiments, we also used scikit-learn (Pedregosa et al., 2011) for train/val/test data splits. We created all plots by using matplotlib (Hunter, 2007) and seaborn (Waskom, 2021) via pandas (Reback et al., 2020) except for Figure 2. We managed our experiments’ configuration using hydra (Yadan, 2019) and experimental results using Weights & Biases (Biewald, 2020). For effective parallelized execution of our experimental codes, we use GNU Parallel (Tange, 2021).

Review summaries:
=== After Rebuttal ===  The author(s) have made many clarifications and improvements to the paper per reviewers' requests. I am happy to bump up my score by 1 to reflect the changes & promises made.   =================  This paper provides some new theoretical insights on how contrastive representation help to improve downstream classification performance. In particular, it fixes the mismatch between prior theoretical predictions and empirical observations, that a larger negative sample size leads to better downstream performance. 

The paper studies the learning bounds of popular representation learning. Not only the improved tighter upper bound is provided, the lower bound is also studied. The paper is well written with thorough discussion and nice example for illustration. 

This work proposes a new theoretical upper-bound for contrastive unsupervised learning loss and its downstream supervised loss. Compared to previously published upper-bounds, the newly proposed one is lower and decreases when the number of negative samples increases, which is expected according to empirical observations, but not shown in previous upper-bounds. The authors use experiments on multiple datasets to verify the theoretic results and the gaps between this and earlier upper-bounds.