Sharp Learning Bounds for Contrastive Unsupervised Representation Learning
Authors: Han Bao
Yoshihiro Nagano
Kento Nozawa
Venue: ICLR 2022 Submitted (2022)

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 tight 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 variance of the downstream loss decays with larger negative samples. We verify that our theory is consistent with experiments on synthetic, vision, and language datasets.

Under review as a conference paper at ICLR 2022
SHARP LEARNING BOUNDS FOR CONTRASTIVE UNSU- PERVISED REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Contrastive unsupervised representation learning (CURL) encourages data repre- sentation 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 suc- cess by upper bounds of downstream classification loss by the contrastive loss, they are still not sharp enough to explain an experimental fact: larger negative sam- ples improve the classification performance. This study establishes a downstream classification loss bound with 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 down- stream classification empirically improves with larger negative 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.
because
INTRODUCTION
The contrastive loss (Chopra et al., 2005) is one of the popular loss functions in metric learning (Kulis, 2012) and representation learning (Bengio 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; Hc et al., 2019; Chen et al., 2020), and graph (Lirong et al., 2021) domains. A simple model built top of the learned representation can achieve almost the same accuracy 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 al., 2020; Nozawa & Sato, 2021; Ash et al., 2021) improved theoretical understanding of CURL. They provided upper bounds of 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 by K in this work. From the empirical viewpoint, it has been widely shown that downstream classification accuracy tends to be better with the larger K (He et al., 2020; Chen et al., 2020).! From the theoretical viewpoint, although Ash et al. (2021) 1) and Nozawa& & Sato (2021) 1) addressed the issue the earlier analysis (Arora et al., 2019) the bound grows exponentially in K their improved bounds may not capture the actual behavior of CURL related to K. as we will see in Figure 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.
still so huge that they
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
'The empirical evidence has also not reached consensus yet. Chen et al. (2021) reported that SimCIR with the smaller K could he competitive linear evaluation than K used by the original SimCLR (Chen al., 2020).

---

Under review as a conference paper at ICLR 2022
(Theorem 1). By deriving the lower bound (Theorem 2), we found that the intercept of our upper bound tight in K. Notably, such 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, 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 synthetic dataset, CIFAR- 10/100 (Krizhevsky, 2009) datasets, and Wiki-3029 dataset (Arora et al., 2019).
bounds are compared with the existing bounds to demonstrate that
2 FORMULATION OF CONTRASTIVE LEARNING
First, this section briefly summarizes the prob- lem setup and formulation of CURL.
Ours
106
Arora et al.
Nozawa & Sato
The C-dimensional vector whose elements are all one is denoted by 1c 1] When it is clear from con- text, the subscript is abbreviated. For vector R", ags) denotes the i-th largest element of a, namely, a(]) 2 ((2) 2 ... 2 d(p)- Like- wise, a(-i) denotes the i-th smallest element of the vector a. The indicator function is denoted
Notation.
10
Ash et al.
Supervised loss
1 [1
10
10
102
by [[A) for a predicate A. Let A = {p& e 1) be the C-dimensional prob-
10
[0, 11 |p ability simplex. For A the Shannon en- tropy is denoted by HH (p) == EeE(c) Pe In Pe- Let H, be the n-th harmonic number.
X
4
16 32
64
128
512
K
Empirical comparison of our upper bound and the existing bounds on CIFAR-10 10). Arora et al.'s l.'s and Nozawa & Sato's 's bounds valid only at K + > C. Note that Arora et al.'s 's and Ash et al.'s 's bounds become infinity at K 512. As can be seen, our bound is the closest approximator of the true mean supervised losses. The detailed experimental setup is stated in Sec- tion 6.2.
Figure 1:
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 multi- class classification problem. Assume that there exists unknown number of latent classes de- noted by C' E N. Let X' be d-dimensiioal fea- ture space and y |C] be the supervised label set.² In the supervised setup, we are interested in the following risk quantity, the supervised loss, for multi-class classifier g : X RC:
exp(g,(x))
Raupy (g)
E x.gr>P
In
EEEy exp(ge(x)))
which is specialized for the softmax cross-entropy loss. The expectation taken over the unknown underlying joint distribution P. The classifier is eventually used for prediction by argmax By (-).
Contrastive unsupervised representation learning (CURL). In the CURL framework (Arora al., 2019), target to learn meaningful data representation in 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 contrastive loss. The cass-condiiional distribution is denoted by D. = P(X Y c) for each E y and the class-prior distribution by ग = [I c)leey E A The data generating process described as follows: (i) draw latent positive/negative classes: ct.
'Strictly 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 ) are allowed to be different, i.e., y C [C). To focus the relationship hetween the supervised loss and contrastive loss, analyze under the assumption y = [C] for simplicity.
2

---

Under review as a conference paper at ICLR 2022
fo& TK=1 π x+1 (ii) draw anchor sample Det (iii) draw positive sample x Det (iv) draw K negative samples Xx Dey (for each [K])
Now we specify our model. A multi-class classifier g X RC consists of representation f X Rh and linear parameters W E RCxh 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
exp(f(x) (e(((x)((xx)
Reont (f) = E ot Lor 1i-1
E
In exp(f(x) T(xx)))((()))))) Exe[k (xp(f(x)T((xx)))
(2)
xxxxxxx
x.x X
DD
In the downstream task, the representation shall be frozen, and the parameters are to be learned via minimizing the supervised loss Raupe.
Evaluation of representations. For the sake of evaluation, specific linear classifier called mean classifier is introduced. Given representation f, the mean classifier W is defined as W =
[M1... uc] where μe Ex~D. [x)]. This will later be used for evaluating the representation combined with the supervised loss, which is denoted by Ry-supp (f) Ryupy (W"f). (F")). We call the mean supervised loss. If the mean supervised loss is successfully bounded from above, we end up bound on the supervised loss through inf inf weR Reupe (Wf) I Ry-supy (f). For this reason, an upper bound on Ry-supy an intermediate milestone that we seek throughout this paper.
LEARNING BOUNDS FOR CONTRASTIVE LEARNING
In this section, our main theoretical results are provided. We aim at showing that the contrastive loss good estimator of the mean supervised
Reont (he the computable functional in CURL- loss RyI-supv (f)-the (f) the inaccessible target in CURL-for any f. We show this by establishing upper and lower bounds of Ry--upp (f) by Reont (f). Eventually, the minimization of Reont (f) may lead to a good minimizer of Ry-supe (f). All proofs are provided in Appendix B.
3.1 MAIN RESULTS
First, we show 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 applicable for all C' and K (see discussions in Section 4).
Theorem 1. For all f such that [[((x]]2 L (Vx X), the following inequality holds.
Ry-supe (f) < Reout (f) Aus
where Au = 22 + cosh(L3)) In(1 + K) In In
Next, the first lower bound of the mean supervised loss is provided. While the existing theoretical analyses only provided upper bounds, they often entail huge coefficient in the contrastive loss. The lower bound provided below has the same constant coefficient and intercept (Au and AL) rate as our upper bound, ensuring the tightness of our analysis.
Theorem 2. For all f such that [[f(x)]l S L LVxx X), the following inequality holds.
R Ry-supy (f) 2 Reont + AL.
(4)
where Ar, (TT) In K +K+1y7 2 cLsh(L
In self-supervised leaminng data augmentation (DA) is commonly used to obtain positive sample. While Nozawa & Sato (2021) handled DA in this formulation, omit for simplicity focus on the effect of K. 'Even y = [C] is assumed in Section 2, Theorem can be extended to the case y S [C] (subset) and y is coarse-graines set of [C]. In contrast, Theorem 2 can only be extended to the coarse-grained )) The details discussed in their proofs.

---

Under review as a conference paper at ICLR 2022
Our proofs leverage that the contrastive loss and mean supervised loss share the similar log-sum-ex,, functional form, which leads to the direct relationships between the two losses. This is in contrast to the existing works including Arora 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 and 2, the size of the representation [|f(x)]l2 is assumed to be bounded. This assump- tion is reasonable from the experimental perspective since it is common 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, Au and AL 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 (Theorem 2 as well) can be naturally extended the form Ru-supv (f) I Reout (f) + Au + X with a complexity term X, where is the empirical minimizer of the contrastive loss. Since this is 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 Te 1/c for all c [C) (the uniform class prior) in this section.
Ryvenpe (f) < Ruiilf) + Aul
Ryssgelf) Rood (f) An.
Ri + Au R sxpe
Gap between learning upper and lower bounds. Both of our upper (Theorem 1) and lower (Theorem 2) bounds draw the linear lationship between the mean supervised loss Ry-supy and the contrastive loss Reont, with the additional intercept terms Au and A, Under the uniform class prior assumption, the inter- cepts are in the same order:
FC Roont
AC
Rans (E)
Figure 2:
The learning bounds and feasible re- gion. The point * ( R Rup-s is the opti- mal point in the feasible region. The points and are mentioned the texts.
C + 2 In cosh(L?) = = 0(In Au = In K
1 CK - -2 cosh( = 0(n - ) (5) ). A, = In (K 1)2 K
K
and the gap between two bounds is Au - -A = In cosh + 2 (1+ 1). meaning that the gap shrinks to In cosh( T.2) as K increases. Hence, our bounds have the tight intercepts, and the larger K is beneficial for CURLfrom the viewpoint of the estimation gap of the mean supervised loss.
Learning bounds and feasible region. Next, we consider the (Reout R Ry-supy) -plot, in which a point indicates (Reont (f), R Ryu-supv(t (f)) for some f (see Figure 2). Here, let us focus on the feasible region in the (Reont. Ry-supe) Jlloo by assuming [| la < L for any f (same as Theorems 1 and 2). Then, the mean supervised loss and contrastive loss are essentially lower-bounded by the constants'
R Rausupp = In + (C 1) exp((22²)),
(6)
Reont
Σ
K
K
1 (1-7)
K K-m
Inf1 + m + (K - m)) exp(-223)),
m==
respectively. Hence, the feasible region is
Ry--oupe (f) < Roont (f) + Au,
Ry-supv (f) > Reont (f) + AL.
(8a)
Ry--upp (f) 2 Ry
Reont (f) 2 Riontt
(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)
"The derivations of Rypaupe and R are detailed in Appendix C.
4

---

Under review as a conference paper at ICLR 2022
Rion + Au (C 50)
5
Kigs (C = 50)
Riom Au (C 100)
Riseepe
Rijenge 50)
Nont (C 500
3
Ngazap 4g (C 100)
Rims
80
100
0
20
40
60
80
100
K
(a) The feasible region Reont (f)
Roont-
(b) The feasible region at Ryceupp (f)
R Rupsupy
Figure 3: Visualization of the smallest possible value of Ry-supv in the feasible region (8) for different
K and C. The dotted lines show the essential lower bounds which come from each loss separately. The solid lines show the learning upper bounds in which Ry-supy and Reout restrict each other.
Table I:
Learning bounds of the existing works. Remark that Arora al.'s and Nozawa & Sato's bounds are valid only K + 2 C. The detailed derivations are discussed in Appendix D.
UPPER BOUND
REFERENCE
Ry--upp (f) S
(Reont (f) In(Col 1)}
Arora al. (2019)
TK U841
(2Rcont (f) E Eln(Col + 1)}
Nozawa Sato (2021)
cK
2
2(0 1)Hc-1
[Reon (f) -E ElInCol + 1))
Ash al. (2021)
TK
K
represent the achievable limits for each loss separately. One of the important questions is how the smallest possible value of Ry-supy in the feasible region (8) changes as K and C' change. In other words, we are interested in whether the optimal point (Ront:: R Ry-supu) (* 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 Reont (f) -Riunt (Figure 3a): We plot the value Riont + Au (solid line; the Ruy-aup--value of the point in Figure and the minimum possible Ry-supy (Re--supei dotted line) numerically. These curves do not cross for all K, which means Ry-supp (f) R Rez-supy 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 Riusupy does remain even the limit K / xc.
The feasible region Ru-supv (f) R sups (Figure 3b): When Ry-supo (f) Ri.supee the con-
trastive loss Reomt (f) is upper-bounded by Ryi-upy Dr. (the Reont value of the point in Figure 2). The curve of this value does not cross Reout which tells us that the lower bound does not exclude the optimal point (Reont R a(y-) from the feasible region (8) at any K. Note that the gap between Riont and R ju-supy AL gradually increases, meaning that it becomes much casier to attain R Ru-supy K increases.
Hence, the optimal point * stays in the feasible region (8) matter the value K. From this viewpoint, smaller K is not necessarily disadvantageous because the optimal point * remains in the feasible region. Note again that the estimation of Ry-supv may become harder with the smaller K because of the bound gap Au A. = O(In l/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 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.
5

---

Under review as a conference paper at ICLR 2022
4 COMPARISON WITH EXISTING LEARNING BOUNDS
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 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, Tee = 1/C for all E [C]. We introduce notation Col = EkE(K] (at=e5)) Let Ux be the probability that sampled K negative
classes contains all classes E [C].
K C-1 UK = ΣΣ
C 1 m
(-1)Th (1 (1- m + 1
C
The value og is often referred to as the coupon collector's probability. Let TK be the probability that least one of the negative classes oj is the same the positive class et. Under the uniform class prior, TK- 1 - (1 1/c/*. The learning bounds are summarized in Table 1.9
Comparison. First, the coefficient of Roont (f) in the upper bounds are numerically compared in Figure 4a. While Theorem has the coefficient 1 for all K, the existing bounds have different Meaure-Arora et al.' 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 advanta- geous in the several experimental work (Chen et al., 2020; He et al., 2020), the behaviors of Arora al.'s and Ash et al.'s bounds do not explain it well. In Section 6, we also experimen- tally confirm the benefits of the large K.
Ours
10a
Arora
Nozawa & Sato
10a
Ash
10P
20
40
60
80
100
K
(a) Coefficient of Reont (f).
10a
10
Figure 4b compares the upper bound values Reont (f) Re namely, the best possi- ble mean supervised loss in terms of the upper bounds. The tendencies are slightly different from Figure 4a-Ash et al.'s bound is mono- tonically increasing, Arora et 's and Nozawa & Sato's bounds have 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."
10
0
20
40
60
80
100
K
(b) Upper bound at Roont (f) Roont-
Figure 4: Theoretical comparison of our upper bound and the existing bounds (C = 10). Arora al. 's and Nozawa & Sato's bounds are valid only (the dotted vertical lines).
at K 1 2
Note that the coefficients of the existing theories are so large- the vertical axes are log-scaled -ccaldd-hhat the upper bounds are vacuous in both situations. In contrast, 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.
5 RELATED WORK
While our work and the existing works reviewed in Section 4 attempt to understand CURL by connecting the contrastive loss 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 al. (2021) proposed an alternative loss function to the contrastive loss based on a kernel metric, following the
part of the latent classes rather than Ry--uuve. Thus we can obtain slightly better upper bound than Arora et al.'s bound shown Table 1.
'More precisely, Arora al. (2019) bound the averaged supervised loss
Nevertheless. the scale of the upper bound is dominated by the coefficient (1 7x Ut Note that Nozawa & Sato (2021)'s 1)'s bound also implies larger K is hetter. Still, its mechanism and resulting explainability different from ours. See Appendix D for the further discussions.

---

Under review as a conference paper at ICLR 2022
similar idea to Wang & Isola (2020). Tosh et al. (2021) showed that (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 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 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 final remark, multi multi-sample estimators (Oord 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- bias-variance trade-off of the multi-sample MI estimators has yet to be clearly known. Note that Tian et al. (2020) and Tschannen 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.
6 EXPERIMENTS
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.
6.1 SMALL-SCALE EXPERIMENTS ON SYNTHETIC DATASET
Dataset and learning setups. We create a synthetic dataset circle, which is 2D dataset created as follows: for each class e E [C]. 1 000 samples are drawn from Uni - 0..5, [0.5, 0.5)), normalized, and multiplied by 1/2 The generated samples are nonlinear and require disentangle- ment to be linearly separable. We treated 60% of the generated samples as a training dataset and the rest of the samples
test dataset. We did not use data augmentation.
As a feature extractor f. we used a multi-layer perceptron (the number of units 2256-256-2500 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 E (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)."
Results. Figure 5 shows a single trajectory in the (Reont, Ry-supe) -plot and the feasible region (confer Figure 2) for each K. We plotted the trajectories by tracking (Reont (f(*), Ryssupy (f(+)) at each epoch t computed with the test dataset. All trajectories were located in between the upper (Rront + Av) and lower (Reont + ÅT.) 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 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 shown in the figures. From these figures, it can be concluded that the contrastive loss performance
'There some quantitative analyses such as the bias of general MI estimators (Gao al., 2015; McAllester & Stratos, 2020) and the variance of the NWJ/MINE estimators (Song & Ermon, 2020). We will further discuss the implication of the hias analysis Appendix E.
Fach 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.
7

---

Under review as a conference paper at ICLR 2022
K
K
K
K
K - 256
300
supervied
100
Rices Au Risse da.
-00
2
6
Figure 5: Learning trajectories of the circle dataset the (Roont: su J-plot. The trajectories are plotted with gradient color lines, indicating the epochs.
aupeviced loss
supeveel bos
K
4.0
100
0.75
3.8
3.0
epoch
opcch
Figure 6: For each K, eight plotted. (Left) the test mean supervised losses at each epoch with the different negative sample sizes K. (Middle) the test mean supervised accuracy each epoch with the different negative sample sizes K. (Right) the best test mean supervised loss with the different negative sample sizes K.
the circle dataset are averaged with the standard deviations
becomes better with the larger K 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.
6.2 LARGE-SCALE EXPERIMENTS ON VISION AND LANGUAGE DATASETS
We used the same datasets Arora al. (2019): CIFAR-100 (Krizhevsky, 2009) and Wiki- 3029 (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/106 as [C]; C = 10 and C 100, respectively. We used K in respectively. For Wiki-3029, {4, 16, 32, 64, 128, 512} } and in f4, 64, 128, 512} for {8, 64, 256. 024]. For each different (C, K) we used pair, we trained the feature extractor f on the training dataset. We then evaluated its supervised performance on the test dataset with mean and lincar classifiers. We used ResNet-18 (He al., 2016)-based feature extractor for LIFAR-10/100 and the fasttext (Joulin et al., 2017)-basee feature extractor for Wiki-3029.
{500, 000, 2 2000, 3 029) and
Results. Figure! shows the comparison between the estimated upper bounds using Theorem and actual supervised loss on CIFAR-10 for different K on the test dataset. We estimated the bounds by substituting the actual Reont (f') the equations shown in Theorem 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 al. (2019) and Ash 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 + 2 C' and tended to increase near K + C, as we explained in Section
We investigated how K affects the test accuracy for different C' in Figure 7. 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 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/101
The test accuracy
With the smaller K and large C, we found that long epochs tion accuracy than increasing the negative sample size K (Figure 8b). While similar experimental results were reported by Chen al. (2020, Figure 9), it is important to remark that randomly
effective to improve classifica-
8

---

Under review as a conference paper at ICLR 2022
mean classifier
lincar class fier
92.5
mcan clazaller lineer
40.91
43,00
00.0
2003
(0003)
20
00.0 50.5
sipenood acounyy
2000
(0:17)
$2.00
44.00
(0.0))
11.38
10.24
(0/700
LS,L3
40.33
14)
06.00
86.37
(0)10)
32
64
1.20
512
66
68
1000
(0.32)
68.07
48.77 77 (1:25)
48.75
(105))
(0.80)
49.63
50.88
(0122))
51.21
(0:355)
$1.00
(0.24)
50.94 (0.20)
67
65 06
52.06
52.08
58.04
58.72
53.41
55.01
55,52
55.09
(0.71)
(0,09)
(0.67)
(0.63)
(0.29)
43)
(0.50)
(0.47)
1024
64
2h6
1024
(a) CIFAR-10 (Top)/100 (Bottom).
(b) Wiki-3029.
Figure 7: Mean and linear classifier's test accuracy CIFAR- 10/100 and Wiki-3029 when varying the negative samples size K. For Wiki-3029, we also change the number latent classes C. The error bars in (a) and parenthesized number in (b) indicate the standard deviation of three runs.
supervise 303rr3y
Taaee accuraty
60
35
60
80
7G
198
512
512
000100
200
400
600
800
1000
1200
1400
1600
1800
2000
200
400
600
800
1000
1200
1400
1600
1800
2000
spoch
(a) CIFAR-10.
(b) CIFAR-100.
Figure 8: Test accuracy of classifier every 200 epochs on CIFAR-10/100 In CIFAR-100. the accuracy of 4 and the others' have large gap at smaller epochs at epoch 200, but the gap become smaller when epochs increase. The error bars indicate the standard deviation of three runs.
drew K negative samples from the 2B 2 samples in the given mini-batch each iteration in Ash et al. (2021)-a different approach was used by Chen et al. (2020) to regard the all samples the mini-batch except an anchor sample as negative samples. Under our experimental setup, 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).
CONCLUSION
In this study, we established novel theoretical bounds for contrastive unsupervised representation learning. We derived sharp upper and lower bounds on downstream classification loss that are tight in the negative sample size. They suggest that the contrastive loss can be used 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. is left open to fill the gap between the supervised loss and accuracy. In addition, may understand contrastive unsupervised representation learning better by incorporating the optimization perspective into the theoretical analysis.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Since this study is theoretical in nature, we do not have specific ethical concerns.
REPRODUCIBILITY STATEMENT
All experimental codes available in the supplementary material. In addition, the details of experimental datasets and prper-pprameters 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.
10

---

Under review as a conference paper at ICLR 2022
<APPNNDIX>> SHARP LEARNING BOUNDS FOR CONTRASTIVE UNSUPERVISED REPRESENTATION LEARNING
As an additional notation, the d-dimensional ball of radius associated with the Lorm is denoted by (r) = fx R | S r}. For R,, the log-sum-exp function is denoted by LSE (z) == In (c exp(ze)).
A USEFUL LEMMAS
In this section, a few lemmas are introduced in order to prove the main results. Lemma 3. For z E RN,
I 1 Σ exp(-21) - In 1+ Σ exp(2*) + Do: nE(N]
(10)
RE[N]
where Ao 21 N).
Proof. Define (z)) = LSE (-10 ž1 =N() + LSE (I0 zN]).
Then, Ao is lower bound
of H. Since
0H
exp( 2;)
exp(2;)
(11)
0z,
EnE(N] exp(- - 2n)
EnE(N] exp(2n) 2n)
for all E [N]. z 0v 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 minimized at z Oy- Hence, we can choose
Ao (OO)) In(1 N).
Lemma 4. For E 11- 2 1- and p 0. exp(-20)
exp(20) (1 P) exp(20) p Enelyy exp(zn)
In (1+ ()+p)exp((20 -20) + EnE[N] D exp(-
--hn In
A
(12)
where 41 = 21 (in(p(N+++)) (N+1+ cosh(l?))
Proof. The goal is to find a tight upper bound A of
exp(z0)
exp(-2o)
In (1 (1+p)) exp((2)) + Enely exp(2n)
(13)
(1 (1+p)exijp exppp -2) eexp(=2)
+ + EnE(N expl exp(- -2n)
in (1+ p)) + Σ exp(zn)
+ In (1 pxp((-x) +p Σ exp(-2n)
REIN]
nE[N]
(14)
exp( = Ilppin In (1+ exp(20) + Σ exp(zn) + In (1+ exp( -2) ) + Σ (ap(--2n)
(2)
(15)
where ă 2== [20 z T..
11

---

Under review as a conference paper at ICLR 2022
Equivalently, we aim upper bound of (2) for 2
B (L²). Observe that (z) - + In 1 (1+ 0
of 0...0] is the sum of the two log-sun -og-sme-epp functions after adding the constant vector henee it is convex in In addition, the domain (L²)) is compact convex polytope. Henceforth, every vertex of the polytope, H' is concave minimization over convex polytope (Pardalos & Rosen, 1986). Since H' (ž) is symmetric in every 2n except 20. need to divide the cases depending on either 20 L or 20 = L2 and compare the maximum values of
LSE 2 + In (1 +1++ 0 o.... of + LSE
2 E (-L", 12J is local maximizer because maximizing
H' (z)
20 I. In order to maximize H' (2). it is sufficient to test the vertices 2 E {z E BN+1 (L?)
=0 1,2) and see the difference between (m)) and H' + 1), where
(1(m) = H1' (1(11 L2 L2 ,,.,...- -L²
(16)
N-m
{( m 1 expl- + (N m) exp(L
In
{( (m+1+ exp(L2) (N mm) exp( -12)
+ In
-L3)
(17)
for m. E (O...., N) to seek the maximum. Here, the definition of H' can be naturally extended over the real domain E A simple algebra shows
N
exp (im) -(2- (exp(2I.2) exp(-21.3)
P
Const.
(18)
2
<0 CAM-GGM inequalitt)
Since H' is concave over m R, H' is maximized m the maximum value is
N-1-3
(< (< N). If
then
N-I
H' N N (N-1-2 = 2hn ((x+1+ costh((3))
(19)
If 2 N-1 H' is maximized at m = 00 and its value is
H'(0) = In N2 + (1+= p) + N 1 ( :) (exp(212)+ + exp(-2(.2))
(20)
< eex((212) + exp( 21.2
N2 + (1+ )) + 2N (1+ 1
p 11)
(21)
2
=In (N++1+) !) cosh(2122)
(22)
where the inequality follows from the AM-GM inequality exp(22"))+sx)) -21²)
2 1.
If 2u L Similarry, we define
('(m) = H' -L2, L LL -
-L?
(23)
m
N N
In in<mexp(-LL)) +
N +++1+
1
exp(L2)
+In mexp(1
N + 1
m
exp( exp(-I1²)
(24)
12

---

Under review as a conference paper at ICLR 2022
and extends its definition over the real line N.. Since
N + 1 + 1 P
exp (i)(m) (2 (xxp(2)")+xx(((2211)) exp(-2L3)))
m
Const,
(25)
2
<A incquality)
it is maximized at m min and its value is
N ( 0). N-. Ht' is maximized at m N+1+
N+1+
2
2
N +++++ 1
211 ((N+1+ cosh((13)
Ar'
(26)
If N-. Ht' is maximized at N and its value is
(I'(N) = In N2 (1+- : +N (1+1) (exp(2L3) + exp(
(27)
Iin ((++++ .) cosh(2112)
(28)
After all, H' is bounded from above by either
((++1 ") cosh(L2)) or In ((N+1+) !) cosh(2(3))
21n
(29)
These two values be compared follows.
1
cosh(1?3) ) -In (N((N+++) cosh(21?))
2
N 1
(30)
0
1
In
N + 1
In cosh 2 (L2) In coocohss21 (2L3)
(31)
1
N + 1 1
In (26h
In
(32)
In N 1
(33)
0,
(34)
where the first inequality is due the AM-GM inequality exp(2L")+exp( 1. Hence, regardless
of p, 2n (N (N+ + +++++ b) cosh(L?)) is a tight upper bound of Al'
Lemma 5. For all 20 R and RR such that 20, 2x E [ L3) (Vk [K])
exp(-zo)
exp(-20) + EkElKy exp(-2x)
exp(zn)
2 -n exp(20) + Exe[K] exp(za) 2 2n { + 1) cosh cosh(L?))
(35)
Proof. We write ă = 1z0 JT Let H()) be a function such that
exp(20)
exp( (xp(-20)
H(ž) = In
In
(36)
exp(2o) EE((K] exp(z*) K-1
exp(-20) + Σ>E[K] exp(-2x)
K+1
In
exp( + In
exp( -āx)
(37)
k=1
1=1
13

---

Under review as a conference paper at ICLR 2022
Our goal is to find tight upper bound of (() for ž E BB++(L3)
Observe that H (z) the sum of the two log-sum-exp functions hence is convex in In addition, the domain B (L2) is compact convex polytope. Henceforth, every vertex of the polytope, 2 E (-L2, L2]x* +1 is local maximizer because maximizing H(z) is concave minimization over convex polytope (Pardalos & Rosen, 1986). Since H (2) is symmetric in every element žg. is sufficient to test the vertices and see the difference between
I.2 I1 ,..... I2
-...,.-13) and H I12 II,,..... L.2 -I? ...., ,...,,,-... 1222)
(38)
#=
#=f+1
=B())
-(f++1)
for j (O...., K} to seek out the global maximum. For 0 S S K, simple algebra shows
exp (A()) exp ( (K 22j (2 (exxexxx(22 + exp((_
(39)
20 because AM-GM inoquality
from which we can tell that HJ) is maximized at j = K/2 when K is even and j = (K + 1)/2 when is odd. In addition, it confirmed that
K
K +
2 - (exp(21.)) +
exp
H
exp
H
(40)
2
S 0,
(41)
where the AM-GM inequality is invoked at the last line. Eventually, H(K + 1)/2) turns out to be tight upper bound of Hz)) for ž E B (IZ²). It is elementary confirm H ((K 1)/2)
2n {KK + 1) cosh(L?)).
B PROOFS OF MAIN RESULTS
In this section, we provide proofs for the main results, Theorems and 2. Theorem 1. For all f such that [[f(x]]2 I L (Vx X), the following inequality holds.
Ry-supe (f) S Roont (f) Aus
(3)
where Au = (\) + 1) cosh(1 (1?)) - 2n + K) In K KT(-1)-
Proof of Theorem I. Define the two constants
Au = 2 2n + K).
(42)
A := 2 In Lln((CCC(-)) ((1) + 1) cosh((?)).
(43)
The proof begins with the Jensen's 's inequality applied the contrastive loss:
Roont (f)
E at ct,fc ( 1xxxx
In
1+ Σ exp(f(x)T(P(())) (f(xT) f(x+)))
(44)
[(x]
KE(R]
In
1+
exp(f(x) (H (o!)))
(45)
ct ct,c,, |xx
kE[K]
In
1+ Σ exp(f(x)T (ft(x Moz5) ADo
(46)
lx
k]
14

---

Under review as a conference paper at ICLR 2022
where the second inequality follows from Lemma' 3. The first term, the origin-symmetric transform of the contrastive loss, is further bounded as follows.
In
1+
Σ kE[K]
exp(f(x) (Met Mo--))
ct,fc }
E In
1+ Σ
Eexp(f(x)) (Mel Ho))
(47)
c x
kE
(Het -Ma)) Mc)) )
E In 1 K (-1-1)
1+
Σ exp(f(x) (pet CE(C]((ct)
(48)
c x
where the first inequality is the Jensen's 's inequality and the second inequality holds by noting that E. E. A. E. A. In order 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
In
1+ (T)()))
1+
Σ cE|C]{(at)
exp(f(x) (Mot He))
exp(f(x) THe - pe Ha))) 11)) A
E
In
1 (T(-1
1+ Σ
(49)
c+
cE(c](ot)
E
ln
+1+
Σ
exp(f(x)T (Ne - Mot)) Ai In (m(-)) (50)
(T(-1)
2 E In
1+
Σ
exp(f(x) (mo Mct))) - -AI+InKTCH
(51)
ct
cE(C][ett)
-pp-supy (f)
(52)
where the first inequality is consequence Lemma and the second inequality simply observed by In( R + x)) In x for any x > 0 since K 0. Combining all the above, get the final bound Ryy-supv (f) < Reomt (f) Ao + A In (-(-)-
Even if Theorem assumes y = [C7, it can be extended to the cases y C [C] (subset) and y is coarse-grained of [C". When + [C], Ry-supv defined over the class set V, while Reont is defined over the class set (C). In the subset case, we can replace Eq. (52) with the subset class bound:
E In
1+
Σ exp(f(x) (mo Mc! Hcl))
x
cEJCTR(at)
In
1+
Σ exp(f(x) - me- -mo-))-)) = Ryssupr (f).
(53)
ct x
<EV)(ct)
In the coarse- grasied case, Eq. (52) holds without modification.
Theorem 2. For all ff such that [[f(x)]12 LVx X), the following inequality holds.
Ry-supy (f) 2 Reont (f) AL.
(4)
where 3 + In (K+1y In cosh
Proof of Theorem 2. The proof essentially 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
15

---

Under review as a conference paper at ICLR 2022
negative Shannon entropy, the following identity is obtained.
R Ry-aupy (f)
E
[-f(x)
My + LSE (W"f(x))
(54)
x,9
f(x) My sup {p +
(55)
x.9
PEáC
we choose an arbitrary E AC, Ressupy( (f) is lower bounded (Fenchel's inequality). Our choice is p æ. Recall that K is the number of negative samples. Then,
Ry-supv (f) 2
E ct
f(xx
T Mot Σ Te- fxx) Me-
+ +
(56)
CTEV
E
IE
-(xx) f(x))((xx) +((x)
E x
[f(x }]
- H (T)
(57)
c
x.x
DD?
E
E
f(x) f(x+)) + 1
Σ [
+ +
(58)
K
c x,x
kE|K| Xx
1 f(x)) - ((x) ((xE))
E
E
+ H
(59)
K
el 11
x
KE[K]
E
E
lnexp(f(x)) (f(x*))+f+)))))))))))))(())) f(xx)))
+ H (T). (60)
K
ct et (x,
KE[K]
Here, we can proceed with the Jensen's inequality to lower bound the first term: for a non-negative vector T the inequality -N-1 LiE[N] In 2, -In NNNN~EEENN 2,) holds. If set
24 exp(f(xx (f(x") f(x;)) ))) for k E [K].
R Ry--upp (f) - H (TT)
(xp(f(x)T(((xx)) EkEIKi exp(f(x) (f(xt) - f(x ())
E
In
(61)
ct for hx:
K
x.x [x, }a
exp(f(x)T(f(() (f(xx) - f(xx))) E
EKE[K] exp(f(x)) (f(x*) - f(x; )))
E
In
at (or kk,
K
x.x (x2 }
(62)
f(x**) 1)
E (c hxs x.x (xx ha
In
+ K.
(63)
+ EKE(K] cxp(-f(x) f(xxx
Finally, by using Lemma 5,
Ry-supe (f)
H (T)
exp(f(x) f(xx)) (Fxx))
2 E
E
- In
+ +ln
(64)
exp(f(x)TF(xx) + ExEcKy exp(f(x)
dei xxxx
xxx
[xTTs 3+
-2 {KK + 1) cosh(L"))
(65)
Roont (f) + In K In(K + 1) In cosh(L3).
(66)
which concludes the proof.
16

---

Under review as a conference paper at ICLR 2022
Unlike Theorem Theorem 2 can only be extended the coarse-grained y from the case ) [C]. Indeed, the first expectation term on the right-hand hand side of Eq. (56) can be transformed as
E
[(x) Met + Σ Te-((()) pe-
E ct,xx
((x) Met +
Σ Te- [(x) [CE[c]
pe- (67)
C-Ey
because of the linearity of the expectation. On the other hand, it is not straightforward twwer-bound Eq. (56) by the expectation over the label set [C] when Y is strict subset of [C].
C ESSENTIAL BOUNDS OF MEAN SUPERVISED AND CONTRASTIVE LOSSES
This section provides a supplementary explanation of the essential lower bounds of the mean su- pervised and contrastive losses. The common approaches of CURL applies the normalization representation, in order to employ the cosine similarity []](x)]|a- f(x))lla as the similarity metric. Then, is reasonable assume [[f(x)]l2 - L for all x with our data representation f. The normalized representation corresponds to the case L = 1.
f(x) f(x')
When we introduce the constraint [|f(x)l2 I L, the mean supervised loss and contrastive loss are restricted as well. As for the mean supervised loss,
R Reesupx (f) 2
inf Rassupo (f') [
(68)
Σ (x) (Mt (Ho-HH))) Hul) ]
= inf
E
1+
(69)
= =In (1 + (C exxppx212)
(70)
(== R(psspp))
(71)
As for the contrastive loss,
Reont (f) 2 inf
Roout (f')
(72)
1
inf | ct Aew (x5
E
In 1+ Σ exp(f (P((x() - f((xx)))
(73)
kE[K]
2 inf
In
1+ Σ
exp(f'(x) (xp Mct)))
(74)
|| at tet
kE[K]
K
m
1
K-m
Σ m==
1
Inf1 m + (K m) exp( -x
(75)
m
C
c
):
(76)
where the Jensen's inequality is applied in the second inequality.
D DISCUSSION OF EXISTING LEARNING BOUNDS
In this section, we describe the existing learning bounds in details to make them comparable with main results. Then, further discuss the detailed comparison between theory and existing works. Before the discussion, we need to introduce the sub-class loss (of the mean classifier), which the supervised classification loss over subset of classes:
exp(1 f(x))
Penb (P,T)
=
In
(77)
E exp(pe f(x))
x.9
where T [C] is subset of classes and y is drawn from the subset of with respect T.
17

---

Under review as a conference paper at ICLR 2022
Arora et al.'s bound. We introduce additional notation that Arora et al. (2019) use. For subset of classes T,
Q - [C] is the set distinct classes in ct .T. ,.....
1+ {k: E [K] c = ct}
Col [xE[K] (at (at=a))= |++1
Pmax (T) = max.eT Tee
Pmin (T') min.er P de h =c T,1+ 1 = 0)
TK P(I #
Arora et al. (2019) prove tinite-saplle learning bound in Theorem B.I. In its proof, Eq. (26) is learning bound established for a fixed f. For the comparison, we focus on their Eq. (26);
Priin (I)
(1
TK)
Raub (f, (f,
k++ Tw
Pmax (T)
Roont (f) TK
E
[nnCCol+ +1/+ #
(78)
al dez ha
We split the expectation term in the left-hand side as follows.
Pmin (T')
Reub (f, T)
Pinax (T)
P(T covers [C]) EE
Punn
Raub (f, T) covers [C]]
Pmax (1)
=ek+1
Pmin (T)
+ P(T does not cover (C]) E
Reub (f. T)
does not cover [C]
(79)
Punx (T)
Ptii (ICT)
2 UK+1
Banch (f, (C])
(80)
Pmax (C)
Ry (f)
Under the uniform class prior assumption (πr 1/c 1), Pmnxx PmC) l/c, and we can pick any class
co E [C] by the symmetry and p ([C)) P(c co Q [C], /+ 0) = 1/c. In addition,
TK
E
[InCCol + 1)| * 0] = R. [In[Col + 1)] (1 - TK) E [In(Col + 1) = 0]
ct ot k+
(81)
[In(Col 1)]
(82)
As result, we obtain the following simplified expression Table 1:
Ry--aupy (f) (1
TK TK {Reont (f) E[In(Col 1)]}
(83)
Nozawa & Sato's bound. The learning bound provided by Nozawa & Sato (2021, Theorem 8) involves factor resulting from data augmentation and self-supervised learning setting. By dropping this (negative) factor, the learning bound
RRaus (f,uu(f,))) (f, Elln + mnn
Reone (f) 2
2 UK Ry-supp (f) + (1 - -K-+)) E P~
(84)
1
2 2 (UK+I (f) Elin 1)]}
(85)
resulting in the bound in Table 1. The sub-class loss may be safely dropped because it has the coefficient UK+1, which is expected to be exponentially small in K.
18

---

Under review as a conference paper at ICLR 2022
Ash et al.'s bound.
Ash et al. (2021, Theorem 5) provides the following learning bound
11)
R Ryssupy (f)
(=1-)) (1 T(1))*
Reout (f) - TK at tor K
E
[in(Col+1)Jr+ + + 00
(86)
By substituting = 1/c 1 and Tk B[In(Col++)] 1+ + 0J = Elln(Coll + 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 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 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 Reont and Ry-supy have the similar log-sum-exp functional forms. This similarity casts Reout as surrogate estimator of Ry-supe and its estimation gap is reduced with larger K. Even with small K, the upper bound of Ra-supy is loose but not vacuous thereby the estimation of Ry-supy is still possible. Our theoretical claim reveals that the surrogate gap improves in OIn 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) trade off the downstream performance with the computational cost.
E RELATIONSHIP TO MUTUAL INFORMATION (MI) ESTIMATION
The contrastive loss Reout 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 (Oord et al., 2018; Poole et al., 2019; Song & Ermon, 2020). Recently, the theoretical limitations of sasele 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
estimation of mutual information (MI)
its lower bound (McAllester& & Stratos, 2020) can be upper bounded by (In N) 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 {(ri, y:) K++ from these random variables such that for all (i.j), (I2, y/) can be regarded 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:
K+1 Σ
In exp(s(x1, v.))
1(X;)) 2
K+1 NCE
E
(87)
K
R+I jj=1 exp(s(<;, 8g))
where I(X;Y) is the MI between X and Y, and s(x, u) is critic function. This lower bound estimator can be rewritten using Reont as follows:
exp(s(xn.1))
K+1 NCE
E
(88)
K +
K+1
exp(s(en
K+1
exp(s(mt,
Vi))
=E
In
+ +ln(K +
(89)
K + 1
Σ
K+1
j=1 exp(s(rr,(,))
19

---

Under review as a conference paper at ICLR 2022
K+1
exp(s(21, 91))
E
+ +In(K +1)
(90)
K exp(s(2;;, U:)) + jzz exp(s(a;, k5))
exp(s(x,
E
+ +li(k +
(91)
cxp(s(x,27) xx)) + Ej= exp(s(x,
Roont (f) + In(K 1).
(92)
The first equality is obtained by putting the constant in the denominator outside. The third equality comes by replacing the notation (#i 3k) with (a, x+) under the assumption that all (2t, ya) come from the same iid distribution. By setting s(z, y) = f(x) f(v), we obtain the last equation.
Here, McAllester & Stratos (2020) gave the following theorem for the sample-baeed estimator of the lower bound on MI.
Theorem (McAllester Stratos (2020) Theorem 1.1, informal), Let I be any mapping from N samples of (X,Y) to I that satisfies
I(X;Y) 2 1S (1(2;, v))
(93)
high probability, then the following relationship holds in high probability:
1 (((2s, (.) (0) S 2m +5.
(94)
Since NCE satisfies the condition for [K+1, we now have the following:
Reont (f) + In(K + 1) 2 21 +)
Reont (f) 2 + + 5.
(95)
However, the right-hand statement always holds by the construction of Reont for all f (Vf, Reont (f) 2 0). In other words, in the case of the CURL setting, McAllester & Stratos (2020)'s ' theorem does not restrict Reouts 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 worthwhile in the sense that these works revealed the OIn N) effect the non-trivial estimators such as k-NN based estimator (Gao et al., 2015) or any kind of lower bound estimator (McAllester & Stratos, 2020).
F EXPERIMENTAL DETAILS
F.1 SYNTHETIC DATASET
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 = 024 and the number of epochs was 300. The learning rate set to 0.01 with ReduceLROnPlateau scheduler (patience: 10 epochs) provided by PyTorch (Paszke et al., 2019).
F.2 10F1R-
We treated 10% training samples validation dataset by sampling class uniformly. We used the original test dataset for testing. We used the same aata-auumentation as in the CIFAR-10 experiment by Chen et al. (2020) during contrastive learning and linear supervised training of the linear classifier.
As 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 fully- connected layer with a nonlinear projection head whose dimensional 32.
Since need to enlarge the negative samples size K that depends the size of mini-batches, followed a large mini-batch training setting used in recent self-supervised learning (Chen et al., 2020;
10 Unlike the reported results by Chen et al. (2021), smaller dimensionality, ie.. 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.
20

---

Under review as a conference paper at ICLR 2022
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 's parameters. The base learning rate was initialized at Ir VB, where Ir E (2, 4, 6) x 1/64 and mini-batch size B 1 024 inspired by SimCLR's 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 data- parallel training (Li et al., 2020) on 8 NVIDIA A100 GPUs provided by the internal cluster. Therefore we replaced the all batch normalization layer with SymcBatchNorm module provided by PyTorch." 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/ees splits, we split the dataset into 70%/10% 22%% train/validation/tess datasets, respectively. As pre-processing, we tokenized the dataset using torchtext's 's basic_ basic_englist 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 2 248;; the initial learning rate was selected in {1, (1, 4) x 1/20; no weights decay; the number of epochs was 90; and perform linear warmup during the first epochs. When we decrease C, the number of epochs is multiplied by 3000/c for simplicity." 13
F.4 CONTRASTIVE LEARNING
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 latent classes saaning/vaaldation/eee
datasets as described above, we carefully constructed positive pairs for contrastive learning before training!* training data as an anchor sample. We drew a different sample from the same latent class of each anchor sample as positive sample in the training dataset. For negative samples,
[C]. After obtaining
follows; We treated each sample in the
drew K negative samples from other samples in the same mini-batch by following the convention of self-supervise 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 To relax the effect of the difference of the mini-batch size when we change K,
other: K = 2B- we drew K samples without replacement from 2B- 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.
F.5 MEAN AND LINEAR CLASSIFIERS' EVALUATION
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
"eee Wu & Johnson (2021, Sec. 6.2) for more detailed discussion of this replacement for contrastive learning. 12 Arora et al. (2019) uses GaU-based feature encoder with frozen word embeddings of GloVe (Pennington ct al., 2014) trained on commonCraw/
We found the contrastive learning did not yield good feature representations for downstream task without this longer training.
We can create the labeled dataset, especially with non-overlapped latent classes, if we draw positive samples each iteration or epoch during optimization using stochastic gradient descent.
21

---

Under review as a conference paper at ICLR 2022
3.4
Ours
5.6
Ours
Supervised
Supervised
3.2
3.0
5.2
2.8
5.0
4.8
2.1
X
1
X
2.2
*
X
94
X
4.4
4
16
32
64
128
512
4
64
128
512
K
K
(a) CIFAR-IO.
(b) CIFAR-100
Figure Enlarged Figure/ for the detailed comparison between the proposed bound and the supervised loss 1IFAR-10/100 datasets. All value is averaged value among three runs with different random seed. Error bar indicates the standard deviation.
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/10 and Wiki-3029 datasets, respectively. For CIFAR- 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/20". scaled by using squared learning rate scaling. For linear evaluation of CIFAR 10/100, we used Py PyTorch's 's distributed data-paralle aata-ppaallll training. We calculated the test accuracy by using the best combination of the contrastive model and the hyper-parameter of 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.
The learning rate
F.6 DETAILS OF FIGURE
Before computing the upper bounds and supervised loss, we normalized feature representations f(x) learned in Appendix F.4 to ensure I. = which is the upper bound [ff Vx. For each random seed and the number of negative samples K, 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 La normalization, we calculated the contrastive loss on the test dataset. To do so, created positive pairs by the same procedure the test dataset 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, used the same batch size as the contrastive learning step and only one epoch. Since this contrastive loss calculation stochastic due the sampling of positive and negative samples, repeated the contrastive loss calculation 25 times and averaged them to create plot Figure 1. Note that we used the theoretical values of TK UK E In (Col + 1) that are shown in the existing upper bounds on Table I 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).
F.7 DETAILS OF FIGURE
During minimization of the contrastive loss to leam f in Appendix F.4, saved the model's weight at every 200 epochs. We reported the test mean supervised accuracy using that maximized validation accuracy among different learning rate values.
22

---

Under review as a conference paper at ICLR 2022
F.8 ADDITIONALLY USED LIBRARIES
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).
23


Reviews:
[{"review_id": "l7AEbshq9Td", "reviewer": "Reviewer_URqh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n* The new upper bound is tighter than the existing works, and provides a better insights of having the large size of negative example that people found useful in practice.  One thing I enjoy during reading is Section 3. After having lower bound, the discussion of feasible region is interesting, and also provide some aspects of having \"small K\", which is also quite aligned with some empirical findings. \n\n* The numerical figures in Sec 4 is a great illustration to understand and compare different bounds. \n\nSuggestions:\n\n* It would be great to extend the mean classifier to a more general linear classifier setting, which is more commonly used. \n\n* Currently, the success of many contrastive learning heavily relying on data augmentations. It would be great the augmentation can be formulated into the analysis (e.g. as some stochastic process .. etc)", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper is well written with many great figures to explain ideas. The improved upper bound and lower bound are studied, which I think it's good to the community.  However, I don't closely follow the theory development of representation learning, which I can only follow the derivations in the paper, and judge from a practitioner perspective.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Tq_eEourTmG", "reviewer": "Reviewer_unTX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.\tThe proposed upper-bound on both contrastive loss and downstream supervised loss is lower compared to other upper-bounds, which make it sharper.\n2.\tThe upper-bound on supervised loss decreases when K (the number of negative examples) increases. This does not happen for other upper-bounds and is important for understanding why the performance of models gets better with more negative samples.\n3.\tThe empirical experiments on the synthetic datasets, CIFAR-10, and CIFAR-100 further show the clear advantage of this upperbound compared to the others.\n\nWeaknesses:\n1.\tThis upper-bound does not include the interaction between K and C (the number of classes). This makes it monotonically decrease when K increases, which is contradict to the empirical results on CIFAR-10 or CIFAR-100 (though the loss values do not change that much, the performance indeed decreases instead of increases as predicted). This interaction is in fact shown in earlier upper-bound. I wonder how this interaction can also be introduced into the current upperbound, especially giving the intuition that with more negative samples, there will also be more examples in the same class treated as positive examples.\n2.\tThe proposed upperbound on downstream supervised loss is based on the intermediate upperbound on the mean supervised loss, which essentially uses the low-dimensional embeddings as the final representations to do the classification. Although this would serve as a right intermediate upperbound when the embedding is only one linear layer away from the typical layer the category readout is extracted, this would not be true when the embedding is several layers away from the typical layer, which is actually the case in most SOTA algorithms now. Can the authors explain how this would influence the results in this work?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This work proposes a sharp loss upperbound for contrastive learning and its downstream supervised learning. It is validated by the empirical experiments conducted by the authors on different datasets, but lacks the interaction between the number of classes and the number of negative samples. Because it’s indeed lower than the earlier upperbound, I think it would be useful for the community and would recommend for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RZ4pULPo9fx", "reviewer": "Reviewer_Dmou", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper address an important theoretical problem in contrastive learning. The paper is well-written and the contributions are stated clearly. I have a few questions and concerns.\n\n1. Is CURL really unsupervised? The paper claims to analyze the “unsupervised” representation learning, however, the positive samples are drawn from class-conditioned distribution, which requires ground truth labels to estimate. I know this step is necessary to have some closed-form analyses, but this makes the study a bit deviated from the recent contrastive learning approaches. Does the observation still holds for general unsupervised contrastive learning, where positive samples are drawn via data augmentations? At least, in the experimental section, it would be great to see some results with standard framework such as SimCLR. Even though the results might not perfectly match the theory, some discussions are still valuable.\n\n\n2. The class sampling assumption is stronger than Arora et al. [1]. In particular, the latent classes used in [1] is not equivalent to the output classes for supervised classification task. Can the current framework generalizes to this scenario?\n\n\n3. Theorem 1 and 2 are nice. Maybe the authors can provide some proof sketch or at least discuss the key tool use to tighten the bounds? It seems that most of the approaches including Thm 1 applying Jensen Ineq at first, what makes the bound tighter? Giving a high level intuition of proof technique can help reader understand the theorems better.\n\n4. Are the bounds also tighter in term of generalization error? With access to only finite samples, the bound could behave different from its expected value.\n\nOverall, the theorems are solid and sound. However, I am concern about the applicability of the bounds. The assumption makes it hard to quantify the behavior of “actual” unsupervised contrastive learning algorithms. The insights from the analyses seem to not directly applicable to practical setting.\n\n\n\n[1] Arora et al., A Theoretical Analysis of Contrastive Unsupervised Representation Learning, 2019", "summary_of_the_paper": "The paper analyzes contrastive learning by bounding the supervised loss with contrastive loss. The bounds are tighter than those proposed by previous works.", "summary_of_the_review": "The paper is well-written, but I am concern about the applicability of the bounds due to its assumptions. The authors claim to analyze an unsupervised algorithm, but the assumptions do require the access to full supervision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "IrtyRDKy0w", "reviewer": "Reviewer_fm83", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper has made some interesting points, and the experiment results strongly support its theories. However, I do have a few outstanding concerns that prevent me from granting a positive recommendation. I am happy to discuss these during the author-reviewer interaction round, and I am more than willing to change my score if the author(s) have made proper changes or managed to convince me. Details of my review comments are given below. \n\n**Strength**\n* Strong theoretical analyses, clear writing, and nice illustrative figures. Overall the technical contents of the paper are easy to follow.\n* Empirical results well aligned with the theories\n* Very update-to-date coverage of the related literature, especially on the theoretical analyses of contrastive representation learning\n\n**Weakness**\n* My most concerning point is that: is this paper supervised representation learning in disguise? Because the contrastive loss used here clearly has leveraged class information (last equation on pp.2). This is clearly the setup in supervised contrastive learning [1]. In that case, it is not surprising that contrastive loss bounds the prediction loss: because they are essentially the same thing. In general, I do not think unsupervised learning can directly benefit supervised learning without some strong assumptions (see for example [2]).\n\n* Apart from the above, another point I do not agree on is why larger K helps. The genuine unsupervised contrastive representation learning implicitly optimizes the MI across augmented views, and larger K drastically reduces estimator variance. The author(s) claimed that \"the quantitative relationship between the negative sample size K and the MI estimation error has yet to be clearly known\", which is not true, see theoretical analyses in [3,4]. \n\n* Following up on the last point, the author(s)' statement that \"Note that Tian et al. (2020) and Tschannen et al. (2020) experimentally showed that maximizing MI does not necessarily lead to good representation.\" is also imprecise. To be more accurate, these works simply used tighter MI bounds for representation optimization, there is no guarantee that they indeed learned representations with higher MI. This view is supported by the empirical evidence from [5], where ground-truth representation MI strongly correlates with downstream classification, and tight MI bounds do not necessarily yield high MI representation. \n\n* Unlike the author(s) have claimed, the gap between learning upper and lower bounds has nothing to do with the estimation variance of the mean supervised loss (pp. 4).\n\n* Figure 4 is very compelling, my suggestion is to present it earlier in the text, which may better serve to prove the author(s) points. \n\n* Per author(s)' theory, variance reduction is the key to performance gains. However, none of the experimental results shows the variance.\n\n* What is the intuitive explanation for notation Col?\n\n* Please label the equations with numbers.\n\n\n**References**\n* [1] P Khosla, et al. Supervised contrastive learning. NeurIPS 2020\n* [2] J Robinson. Strength from weakness: Fast learning using weak supervision. ICML 2020\n* [3] S Gao, et al. Efficient Estimation of Mutual Information for Strongly Dependent Variables. AISTATS 2015\n* [4] D McAllester, et al. Formal Limitations on the Measurement of Mutual Information. AISTATS 2020\n* [5] J Chen, et al. Simpler, Faster, Stronger: Breaking The log-K Curse On Contrastive Learners With FlatNCE. arXiv 2107.01152\n\n\n", "summary_of_the_paper": "=== After Rebuttal ===\n\nThe 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. \n\n=================\n\nThis 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. ", "summary_of_the_review": "I am recommending weak rej at this stage. My main arguments are that (i) the author(s) actually analyzed supervised contrastive learning, not unsupervised contrastive learning; (2) need evidence to show the gains from large K are really from the variance reduction of sandwich bound, not from the variance reduction + bound tightening from the MI estimation perspective. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HVveKSn4IQ", "reviewer": "Reviewer_d3WX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n(1)\tIts theoretical results could explain larger negative samples improve the classification performance in contrastive learning by establishing lower and upper bound of downstream classification loss.\n(2)\tThe authors also do some experiments to investigate their theories. \n\nWeaknesses: \n(1)\tMy biggest concern is that this work does not provide any useful and new insights. It can only explains a well-known experimental fact that larger negative samples improve the classification performance, and does not provide any insights to further improve contrastive learning which is actually the key for theoretical work in my viewpoint. for a theoretical work, providing a more sharp bound is not the goal but providing new insights is. For example, Arora first establish the relation between pretext contrastive loss and the downstream classification loss and shows why contrastive loss can work well for downstream tasks.  However, in this work, I did not find such kinds of insights. \n\n(2)\tthe bound in Nozawa & Sato actually also partially support that larger negative samples improve the classification performance, which can be illustrated by Fig. 3 (a). The authors may claim for possible best R*cont, the bound in Nozawa & Sato cannot explain the experimental fact. Actually, R*cont  is obtained under a simplified case where data augmentation is not considered, and the classification head in f is not discarded when training on downstream tasks, etc. So R*cont may not be achievable for one real contrastive learning or apart from the real optimal contrastive loss since the simplified case are different from the real contrastive learning. \n\n(3)\tThe authors should discuss the novelty of the proof techniques compared with existing one, such as Arora et al, Nozawa & Sato. It seems that the authors use the property that the function f is bounded to give a tight bound. So it is better to discuss your technique differences. \n", "summary_of_the_paper": "This work establishes a downstream classification loss bound for contrastive learning which shows that larger negative samples improve the classification performance. Existing works cannot explain the experimental fact that larger negative samples improve the classification performance. ", "summary_of_the_review": "Overall, although this work provides new tighter bound for contrastive learning, it does not provide new insights and new proof technique/frameworks.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an analysis of the benefit of unsupervised contrastive learning for downstream classification tasks using the cross-entropy loss. Building on prior work, the authors show that the contrastive loss can be bounded in terms of the cross=entropy term and an “intercept” term which depends logarithmically on the number of negative samples per positive sample (for contrastive learning) rather than polynomially as in the prior work. 

There are several differences between the setting here and that of the prior work by Arora et al. (2019). First, the work here focuses only on cross-entropy loss and leverages the similarity of the loss structure between the contrastive loss and the cross-entropy loss. Second, the assumptions here are different, e.g., boundedness of the representation. Finally, the assumption that latent classes are the same as the label classes (which is not the case in the prior work) is significantly restrictive. 

The writing is poor and the presentation is not clear. Despite the title and various references to learning bounds in the abstract and the main text, there are no learning bounds in the paper. The main result is to bound the contrastive loss in terms of the cross-entropy loss under the assumption that the latent classes and the label classes coincide. Authors state that getting generalization bounds is routine and, therefore, they chose not to give them — I do not see how generalization bounds follow in a straightforward manner here, and even if they do, it is important to write them for completeness. 

The main contribution here is that the bounds depend logarithmically in K — the number of negative samples per positive sample — compared to sqrt{K} in the previous work. The previous bound however holds for Lipschitz losses as well, for e.g., hinge loss. So the question remains whether this improvement is only for the cross-entropy loss. Regardless, K is typically small in practical applications. Even the experiments in the paper (Figure 7) suggest that the performance degrades for larger K even on simple tasks. So, the improvement is really somewhat insignificant. 
 
The reviewers were generally positive and appreciated the paper. However, in the light of comments above (of which I am quite certain), unfortunately, I am unable to accept the paper at this point. I believe the comments above (and from the other reviewers) will help improve the overall quality of the paper. I encourage the authors to incorporate the feedback and work towards a stronger submission.
Decision: Reject