Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap
Authors: Yifei Wang
Qi Zhang
Yisen Wang
Jiansheng Yang
Zhouchen Lin
Venue: ICLR 2022 Poster (2022)
Keywords: Contrastive Learning
Representation Learning
Self-supervised Learning

Abstract: Recently, contrastive learning has risen to be a promising approach for large-scale self-supervised learning. However, theoretical understanding of how it works is still unclear. In this paper, we propose a new guarantee on the downstream performance without resorting to the conditional independence assumption that is widely adopted in previous work but hardly holds in practice. Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations, thus simply aligning the positive samples (augmented views of the same sample) could make contrastive learning cluster intra-class samples together. Based on this augmentation overlap perspective, theoretically, we obtain asymptotically closed bounds for downstream performance under weaker assumptions, and empirically, we propose an unsupervised model selection metric ARC that aligns well with downstream accuracy. Our theory suggests an alternative understanding of contrastive learning: the role of aligning positive samples is more like a surrogate task than an ultimate goal, and the overlapped augmented views (i.e., the chaos) create a ladder for contrastive learning to gradually learn class-separated representations. The code for computing ARC is available at https://github.com/zhangq327/ARC.

Published as a conference paper at ICLR 2022
CHAOS IS A LADDER: A NEW THEORETICAL UN- DERSTANDING OF CONTRASTIVE LEARNING VIA AUG- MENTATION OVERLAP
Yifei Wang Qi Zhang2 Yisen Wang2.4
Jiansheng Yang'
Zhouchen Lin
1 School of Mathematical Sciences, Peking University
2 School of Computer Science and Engineering, Sun Yat-sen University
3 Key Lab. of Machine Perception (MoE), School of Artificial Intelligence, Peking University
Institute for Artificial Intelligence, Peking University
5 Pazhou Lab, Guangzhou, 510330, China
ABSTRACT
Recently, contrastive learning has risen to be promising approach for large-scale self-supervised learning. However, theoretical understanding of how it works is still unclear. In this paper, we propose new guarantee on the downstream per- formance without resorting to the conditional independence assumption that is widely adopted in previous work but hardly holds in practice. Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations, thus simply aligning the positive samples (augmented views of the same sample) could make contrastive learning cluster intra-class samples together. Based on this augmentation over- lap perspective, theoretically, we obtain asymptotically closed bounds for down- stream performance under weaker assumptions, and empirically, we propose an unsupervised model selection metric ARC that aligns well with downstream ac- curacy. Our theory suggests an alternative understanding of contrastive learning: the role of aligning positive samples is more like surroatte task than an ultimate goal, and the overlapped augmented views (i.e., the chaos) create ladder for con- trastive learning to gradually learn class-separated representations. The code for computing ARC is available at //tttps://gitiiii thub. com/ zhangg327/ARC
INTRODUCTION
Contrastive Learning (CL) emerges to be promising paradigm for learning data representations without labeled data (Oord et al. 2018 Hjelm et al. 2019). Recently, it has achieved impressive re- sults and gradually closed the gap between supervised and unsupervised learning, hopefully leading to era that resolves the hunger for labeled data in the deep learning field (He et al. 2020 Chen jet al. 2020b Wang et al. 202T). However, despite its intriguing empirical success, a theoretical understanding of how contrastive learning actually works in practice is still under-explored.
The general methodology of contrastive learning is quite simple, that is to maximize the similarity between augmented views of the same image (a.k.a. positive samples), and minimize the similarity between that of two random images (a.ka. negative samples). Intuitively, it is an instance discrim- ination task (differing each image from others) instead of a classification task (clustering images from the same class together and differing with other classes). Nevertheless, as shown in Figure I(a) CL representations are also class-separated. Therefore, understanding how the pretraining Task (CL) and the downstream task (classífication) interact plays a central role in both theoretical understandings and practical designings of contrastive methods.
Previously, Saunshi et al. 2019) Lnd et al. (2000) have tried to establish guarantees on the clas- sification performance for self-supervised representations. However, their analysis relies heavily on the assumption that the two positive samples, as augmented views of the same image, are (nearly) conditionally independent on the class y. However, this is hardly practical as the augmented views are still strongly dependee (see Figure [(b)). In fact, if the conditional independence is satis- fied, the unsupervised task will become informative the supervised task, making this discussion
Equul contribution. Qi Zhang's 's work was done during an internship at Poking University. Corresponding author; Yisen Wang (yisen.wangee @ pku.edu.cn).

---

Published as a conference paper at ICLR 2022
Before Training
After Training
(a) Contrastive learning learns clustered features.
(b) Intra-class samples are more alike via augmented views.
Figure I: (a) t-SNE visualization of representations before and after contrastive learning. Each point denotes sample and its color denotes its class. (b) Applying aggressive data augmentations (Chen al. 2020a) to four images from ImageNet (two are cars and two are pens). The 1tt column shows the raw (center-cropped) images and the 2-5th colums show the augmented ones.
almost unnecessary. This motivates us to find more practical and weaker assumptions to understand how contrastive learning actually works (even without conditional independence). To achieve this, need to re-examine the contrastive learning process. Previously, [Wang & Isola (2020) show that CL objective involves two goals: alignment (for positive samples) and uniformity (for negative samples). Nevertheless, we show that there exist bad cases where the features could still have poor performance even with perfect alignment and uniformity. Thus, contradictory to the common belief of contrastive learning learning invariance, we note that invariance alone is inadequate to learning useful representations for downstream tasks.
In this paper, we provide a novel understanding of contrastive learning that requires only practical and minimal assumptions, while also guarantee class-separated representations. Our core insight hinges the observation that contrastive learning usually adopts much more aggressive data aug- mentations than that supervised learning (He et al. 2020; Chen et al. 2020a). As shown in Figure I(b). we notice that aggressive random cropping of two images can generate views that are very much alike that we could even hardly tell them apart, e.g., the wheels of two different cars. In other words, there will be support overlap between different intra-class images through aggressively augmented views of them, a phenomenon we call augmentation overlap. Thus, the alignment of positive samples will also cluster all the intra-class samples together, and lead to class-separated representations. From our perspective, the role of data augmentation is to create certain degree of "chaos" between intra-class samples, and the role of contrastive loss is "climb the ladder of chaos", i.e., the process that we gradually cluster intra-class samples by aligning positive samples.
Following this intuition, we develop a new theory for understanding the effectiveness of contrastive learning from the perspective of augmentation overlap. Specifically, we derive the upper and lower bounds for its downstream performance and show how the two bounds will asymptotically converge with our assumptions on augmentation overlap. Driven by this analysis, we further discuss how varying augmentation will affect the performance of contrastive learning from both synthetic and real-world datasets, and show that the results align well with our theory. In summary.
We characterize the failure of the previous analysis of contrastive learning, and develop a new understanding through the augmentation overlap effect. Compared to existing theories on contrastive learning, ours can provide guidance to the practical designing of contrastive methods and evaluation metries.
We establish general guarantees (both upper and lower bounds) for the downstream perfor- mance without assumptions on conditional independence. And we further show how the two bounds could asymptotically converge under our less restrictive assumptions.
We provide a quantitative discussion on the effect of augmentation strength, which verifies our theory from both theoretical and empirical aspects. Motivated by our theory, we further propose
unsupervised evaluation metrie for contrastive learning named ARC and show that it aligns well with downstream performance on real-world datasets.
RELATED WORK
Contrastive Learning in Practice. Contrastive self-supervised learning originates from mutual information perspective of representation learning (Oord et al. 2018 Hjelm et al. 2019), and soon
2

---

Published as a conference paper at ICLR 2022
becomes general learning paradigm that contrasts between positive and negative pairs (He al. 2020 Chen et al. 2020a). It is rapidly closing the performance gap between unsupervised and supervised learning on large-scale dataset like ImageNet (Chen et al., (021), and outperforms su- pervised learning when combined with a few (e.g. 10%) labels (Chen et al., 2020b). Several recent works show that similar performance could be achieved without negative samples by adopting cer- tain training techniques (Grill al. 2020, Chen & He 2020).
Understanding Contrastive Learning Objectives. Both the original InfoNCE loss (Oord et al, 2018) and its InfoMax variants (Hjelm et al. 2019 Poole et al., 2019) are designed as variational estimates of the mutual information between inpuls and representations, but these estimators are shown to have poor bias-variance trade-off's (Song & Ermon 2020). Instead, Wang & Isola (2020) simply understand contrastive learning through the two terms in the InfoNCE loss: alignment of positive samples and uniformity of negative samples. However, as we show later, this perspective is also insufficient to explain the effectiveness of contrastive learning. and we should take the interplay between augmentation and alignment into consideration.
Understanding Downstream Generalization. Saunshi et al. 2019 propose the first theoretical guarantees by bridging the contrastive and classification objectives, Lee et al. (202)) further link the reconstruction-base based objective to the downstream objective. However, both Saunshi et al. (2019) and Lee et al. (2020) rely on the unrealistic assumption that the positive samples are (nearly) con-
ditionally independntt. Huang et al. (2021) establish bounds by assuming a very small intra-class support diameter, which is also not practical. Besides, some also explore the information-ther theoretical perspectives for analyzing contrastive learning (Tian et al. 2020; Tsai et al. 2021 Tosh al.) 2020) 2021). though their mutual information assumptions are hard to verty. Recently, simlaar to our anal- ysis. ysis, (aooChn et al. (2021) also study the augmentation graph and establish guarantees in terms of graph connectivity. Our work differs to theirs mainly in three aspects: 1) our analysis is applicable for the widely adopted InfoNCE and CE losses, while theirs is developed for their own spectral loss; 2) ours starts from the alignment and uniformity perspective while theirs starts from the ma- trix decomposition perspective; 3) our theory is empirically verified and inspires a useful evaluation metric for data augmentation, while their analysis focusing on minimizing the decomposition error is farther from the practical designing of positive and negative samples. In nutshell, compared to previous discussions, our theory has a closer connection to the actual contrastive learning process, and we verify the feasibility of each assumption with empirical evidence.
LIMITATIONS OF PREVIOUS UNDERSTANDINGS
We begin by introducing the basic notations and common practice of contrastive learning in the image classification task. In general, has two stages, unsupervised pretraining, and supervised finetuning. In the first stage, with N unlabeled samples D, = { we pretrain an encoder mapping from the d-dimensonal input space to a unit hypersphere f E FF; Rd 5mm11 in the m- dimensional space. In the second stage, we evaluate the learned representations z with the labeled data D, = {(z,, };}} where labels yi E {l...., K}. Specifically, we fix the encoder and learn a linear classification head g Rm + RK on top from D. = [(22 v)1z = f(x) E R'
Contrastive Pretraining. Taking a training example x E Da, we draw its positive sample a ((x) by applying a random data augmentation t ~ T, and draw M randomly augmented samples {zz 1.M 1i-1 from D., as its negative samples. Then, we can learn the encoder f with the widely used InfoNCE loss (Oord et al. 2018)
exp(f(x) f(x))) exp(f())((xtt)) log EM exp(s(x) f(x)))
Exex()) =Bplo ) (00777)
(I)
Let p(x) be the data distribution, p(a, x ) be the joint distribution of positive pairs, and we simply x
assume p(5,*+)) = p(=+ ,x) and p(x:) = (a,,, V Rd following Wang & Isola 22020).
Linear Evaluation. To evaluate the learned representations by contrastive learning. we usually
adopt the Cross Entropy (CE) loss (Chen et al. 2020a) for a labeled pair (2, y) E Di
exp (f(z) (
Lee(f.g) = Eptr.))
log Ex exp (f(x) (oeTTw)) wx)
(2)
with linear classifier g(z) where W
[w); 12......... wk].
3

---

Published as a conference paper at ICLR 2022
3.1 EXISTING THEORETICAL ASSUMPTIONS AND THEIR LIMITATIONS
As discussed above, there are some previous understandings on how contrastive learning yields good performance, and they mainly differ by their theoretical assumptions.
First, Wang Isola 2020) interpret the first and second terms of the InfoNCE loss [ as they are aiming at the following two properties: 1) alignment (the nominator): positive samples I, has similar features, i.e. f(z) z f(x+); 2) uniformity (the denominator); features are roughly uniformly distributed in the unit hypersphere g In particular, they show that InfoNCE can be minimized with 1) perfect alignment and 2) perfect uniformity. However, as we illustrate in Figure 2 the features could still have very poor downstream performance in the finite sample scenario. This issue can be described rigor- ously by the following proposition.
f(x;) = f(x²) V x Du
Proposition 3.1 (Class-uniform Features Also Minimize the InfoNCE Loss). For N training examples of K classes, con- sider the case when features { are randomly dis- tributed in gm-1 with maximal uniformity (i.e., minimiz- ing the 2nd term of Eq. 1 while also satisfying Va,, xt ~ p(æ,,*); );); [(xz)) = [(x;). Because we have these two properties, the InfoNCE loss achieves its minimum. However, the downstream classification accuracy is most 1/K + and is nearly zero when N is large enough.
Figure 2: Contrastive learning may learn class inseparable features even with perfect aligned pos- tive samples and uniform negative samples. Colors denote classes.
Proofs can be found in Appendix A This proposition indicates that the instance discrimination task (alignment + uniformity) alone cannot guarantee the learning of class- diiisssiicrimiaaivve features as desired in the downsteam classification. Instead, Saunshi et al. (2019) and Lee et al. (2020) both establish the relationship between pretraining and classification objectives and provide guarantees for the downstream performance. In fact, the two works both assume the conditional independence of the two positive samples, i.e., p(a, x+ ly) p(zly)p(<* (y). However, this assumption is too
strong as it is hardly practical. As shown in Figure [(b]] augmented views from the same class not actually independent as views from the same sample are more alike than that from other samples.
4 NEW AUGMENTATION OVERLAP THEORY FOR CONTRASTIVE LEARNING
The analysis above motivates us to find minimal and practical assumption: 1) it is enough to guarantee good performance on downstream tasks; 2) it is less restrictive than the i.i.d. assumptions as in Saunshi et al. (2019) and Lee et al. (2020).
4.1 GAP BETWEEN CONTRASTIVE LEARNING AND DOWNSTREAM CLASSIFICATION
We start with an assumption the label consistency between positive samples, that is, any pair of positive samples (x, - should belong to the same class.
Assumption 4.1 (Label Consistency). V Vx, p(axxx)) we assume the labels are deterministic (one-hot) and consistent: p(y|z) p())
This is natural and minimal assumption that is likely to hold in practice. As shown in Figure I(b) the widely adopted augmentations in contrastive learning (Chen al. 2020a) like images cropping. color distortion, and horizontal flipping will hardly alter the belonging image classes.
With this minimal assumption, we can characterize the generalization gap between unsuper-
vised and supervised learning risks. We first introduce the mean CE loss. L(r(()
Ep(a.)) log exp(f(x)TH) H.) ""K,exp(/ u:)] where we use the classwise mean representation JAk
( as the weight wa of the classifier It is easy to see that the mean CE loss up- per bounds the CE loss, Le., (f) 2 min, LCE(s.g) and Saunshi et al. (2019) showed that the mean classifier could achieve comparable performance to learned weights. Then, we have the following upper and lower bounds on the downstream risk (measured by mean CE loss).
4

---

Published as a conference paper at ICLR 2022
Contrastive
Learning
Augmentation Graph
Learned Representations (feature
(Inout
Under Overlapping
Perfect Overlapping
Overly Overlapping
(a) Contrastive learning with augmentation graph satisfying class connectivity.
(b) Augmentation graph under increasing augmentation strengthes (left to right).
Figure 3: Illustrative examples of augmentation graphs, where each dot denotes a sample z E Du and its color denotes its class. The lighter disks denote the support of the positive samples p(æ* (2r). We draw a solid edge for each T -cconnected pair.
Theorem 4,2 (Guarantees for General Encoders). If Assumption 4. holds, then, for any f E F, its downstream classification risk C (f) can be bounded by the contrastive learning risk LXCE
[NCE(f) | y) Var (ar(f(x)] (x)) o - (M-11/2)
2
(E +
s (NcE(f) + Var(f Log(M/K) Log(M))
O M (M-1/2)
where (og(M/K) is constan Var(f b) Epis)) (Eplela) ff Epta a) fx))l denotes the conditional (intra-class) feature variance, and O (M-1/2) denotes the order of the approximation ervor by using M negative samples.
Notably, our generalization bounds above improve over previous ones in the following aspects:
1) we do not require the conditional independence assumption in Saunshi al. (2019);
2) we directly analyze the widely adopted InfoNCE loss (for contrastive learning) and CE loss (for supervised finetuning). while Saunshi et al. (2019) are restricted to hinge and logistic
objectives that have worse performance in practice (Chen et al. 2020a);
3) the class collision етгоr terms introduced in Saunssh et al. (2019) (due to the existence of same-class samples in the negative samples) now disappear in our bounds by adopting the InfoNCE loss, which also helps understand why InfoNCE performs better in practice; and
4) the bounds in Saunshi et al. (2019) will become looser with more negative samples, which is contradictory to the common practice (Chen al., (020aa). While in our bounds, larger M indeed has lower approximation error and helps close the generalization gap.
In fact, several recent works have also been devoted to resolve the last "large-M" problem (Ash et al., 1 Merad et al. (2020). Nevertheless, their analysis also requires the conditional independence assumption as in Saunshi al. (2019), while we show this problem can be resolved even without conditional independence. [Nozawa Sato (22TT) also establish bounds for the InfoNCE loss, but their bounds have incompressible class collision terms while ours do not.
Nevertheless, an important message of the theorem above is that Assumption 4.J alone is still insuf- ficient to guarantee good downstream performance. As there are intra-class variance terms in the upper and lower bounds, when they are large enough, contrastive learning might still have inferior performance as shown in Proposition 3.1 Although the variance terms can be easily eliminated with the canonical conditional independence assumption, discussions in Section have already demon- strated its impracticality. In the next part, we will present new understandmg of how contrastive learning could control this variance term in practice.
4.2 CLOSING THE GAP WITH INTRA-CLASS CONNECTIVITY
The theorem above motivates us to study how contrastive learning could effectively control its intra- class variance and learn class-separated features. Here, we propose new understanding of this clustering ability through dissection of the augmented views. In particular, notice that although samples are different from each other, applying aggressive augmentations like that SimCLR CCen
"log( M/K) K") could he absorhed in the loss functions by replacing sum with mean in InfoNCE and CE.

---

Published as a conference paper at ICLR 2022
et al. 2020a can largely make them more alike. For example, in Figure I(b) two different cars become very similar when they are both cropped to the wheels. Then, with contrastive learning, the two cars will have closer representations as they share a common view of the wheels. In other words, two different intra-clas, samples could be aligned together if they have overlapped augmented views. If all intra-class samples could be bridged by data augmentations, we can successfully cluster the whole class together. Below, we formalize the intuition above with the language of graphs.
Notations. A graph G is represented by a tuple 9 = (V,E) where V = (V), U2,....... UN) is set of vertices and & S V x V is set of edges. A path is a sequence of edges that joins a sequence of vertices, e.g., 1/2 V/2
Uig. We say that two vertices v and u. are connected if & contains path from v u. A graph is said to be connected if every pair of vertices in the graph is connected. Two graphs are said to be disjoint if any pair of inter-grape graph vertices are not connected.
To begin with, we define the concept of T -connecctvvity of sample pairs, which describes whether two samples could be connected via the augmentation overlap of their augmented views.
Definition 4.3 (T --onnecttvvtty. Given a collection of augmentations T = {t I tt IRd + Rd), we say that two different images Zz, 3jj E I are T-connected if they have overlapped views: supp(p(a; (x:)) O supp(p(x]]=;)) + 2, or equivalently, 3 44, 4 E T such that 1c(x;)) = 1z(xz).
Then, can define an augmentation graph of all training samples in terms of their T-connectivity. Definition 4.4 (Augmentation Graph). Given a set of N samples DD = {z; AN and an augmentation set T = {t L: TR + R we can define an augmentation graph G T) EV,E) as
we take the N natural samples as the vertices of the graph, i.e., V {
there exists an edge eij between two vertices x; and øj if they are -cconeected.
Based on these concepts, we introduce the following assumption that with a proper choice of data augmentations, all intra-class samples could form a connected graph, as depicted in Fia) Assumption 4.5 (Intra-class Connectivity). Given a training set Da. there exists an appropriate augmentation set TT such that the augmentation graph (DD., T) is class-wise connected, i.e., V k E {1...., K}, the subgraph Gk (graph restricted to vertices in class k) is connected.
Comparing to Saunshi al. 2019) and Lee al. 2020) that require (nearly) conditional indepen- dence p(x. x (x) = p( y
p)pppa x y), ours only requires the connectivity of intra-class samples as in Figure [(b) and does not need them to be conditionally independent.
To make this analysis technically simpler, we make another assumption that can align positive samples perfectly by minimizing the InfoNCE loss. practice, the alignment loss can typically be minimized up to a small error E, and we have appended a more involved discussion of this weak alignment scenario in Appendix B For now, we focus on the simplified perfect alignment scenario.
Assumption 4.6 (Perfect Alignment). At the minimizer f of the InfoNCE loss, we can achieve perfect alignment, i.e., V x, xr ~ p(æ, x= ), (xx) [ (x+)
Proposition 4.7. Under Assumptions 4.5 & 4.6 by minimizing the InfoNCE loss we can conclude that the conditional variance terms vanish at the minimizer f*, iee.
Var(J*(x) =0
(4)
Intuitively, for samples in each class k. if the corresponding subgraph G3 is connected, there exists a path connecting every intra-class pairs (x;,,;;) as shown in Figure 3(a) Consequently, aligning the positive pairs will also align all samples on the path, and eventually augn x; and Zj, In this way, all intra-class samples can be clustered together and the intra-class variance shrinks to zero (under Assumption 4.6). Besides, because proper data augmentation will not cause inter-class augmentation overlap (Assumption 4.1,, inter-class samples can be well separated with the uniformity term. As result, we can attain alignment of intra-class samples while maximizing the uniformity of inter-class samples. According to Theorem 4.2) we will have an asymptotically closed generalization gap (with more negative samples M for the encoder that minimizes the contrastive loss.
Theorem 4.8 (Guarantees for the Optimal Encoder). If Assumption 4.7 4.5 & 4.6 hold and I is L-smooth, then, for the minimizer f arg min [NCR(J), its classification risk can be upper and lower bounded by its contrastive risk as
( S (' + log(M/K) S LNCE( + O (M-112
(5)
6

---

Published as a conference paper at ICLR 2022
acc = 0.50
acc = 0.78
acc = 1.00
acc 0.50
Raw Training data (d 2)
==
T T= 0.001
= 0.1
T= 1.5
Figure 4: I-SNE visualization of features learned with different augmentation strength r on the random augmentation graph experiment. Each dot denotes a sample and its color denotes its class.
We note that different to previous bounds that hold for any E J as in Theorem 4.2 our results here only stand for the minimizer of the contrastive loss f*. This indicates that the InfoNCE loss alone cannot simply guarantee good downstream performance, and the learning dynamics matters for the contrastive learning to learn useful features.
4.3 RETHINKING THE ROLE OF DATA AUGMENTATIONS
Our analysis above suggests a new understanding of the role of data augmentations in contrastive learning. Conventionally, the success of contrastive learning is usually attributed to learning in- variance w.r.. various data augmentations by matching positive examples. However, as shown in Proposition 3.1 matching positive pairs alone is theoretically inadequate to learn useful features. Indeed, assuming that an ideal encoder that possesses invariance a priori does exist, like invariance to translation (CNNs), rotation (Cheng et al. 2016). and scaling (Xu et al.] [2014). do we obtain class-discimmnnative features simply by random initialization? Still NO, since these low-level prop- erties are independent of high-level class information that we want to learn. Thus, the reason why contrastive learning works cannot simply be attributed to the invariance learning principle.
We instead believe that the role of data augmentation is to create certain degree of "chaos" be- tween different intra-class samples (Figure [(b) such that they become more alike (or formally, -coonnected.. this way, the chaos serves as "ladder" for bridging intra-class samples together when labels are absent, and the mission of the contrastive loss is to "climb this ladder", that is, aligning intra-class samples by aligning the overlapped positive samples, as shown in Figure (3aa Therefore, from our perspective, instance discrimination by contrastive learning is actually surro- gate for the classification task, and the surrogate can complete misson when the ladder of chaos is complete (or formally, when intra-class connectivity holds).
QUANTIFYING THE INFLUENCE OF AUGMENTATION STRENGTH
We have shown that with appropriate augmentations, formance. However, practice, as illustrated Figure 3()] ]
derive guarantees downstream per- there could be cases where augmen- tations are either too weak (intra-class features cannot be clustered together as in Figure 2 or too strong (inter-class features will also collapse to the same point) and lead to sub-optimal results. In this section, we further provide quantitative analysis of how different strength of data augmentation will affect the final performance, both theoretically and empirically.
5.1 CHARACTERIZATION ON RANDOM AUGMENTATION GRAPH
In practice, there are various data augmentation types that are hard be described precisely. For the ease of analysis, we consider a simple case where for each class k. there are N samples uniformly distributed around the cluster center e₁ on a hypersphere gd. We then augment each sample x, with random samples in a hyper-disk of radius r on the hypersphere.
In Appendix D we provide theoretical analysis on how different augmentation strength (measured function of the number of samples N.
by r) will affect the connectivity of the augmentation the position of the cluster centers Gę and input dimensions In particular, the minimal r for the graph to be connected decreases as N increases, so large-scale datasets can bring better connectiv- ity. Meanwhile, the required also increases as d increases, so we need more samples stronger augmentations for large-size inputs. Here, we show simulation results by applying contrastive

---

Published as a conference paper at ICLR 2022
0.4
0.3
0.8
0.8
Tedt Accurayy
0.5
0.4
ACR
0.75
1.50
NOW
Test Accuracy
0.3
0.2
ACR
0.2
$50V
Test Accuraty
0.8
0.7
0.5
0.4
ACR
0.6
04 2
0.5
0.3
0.3
0.1
0.2
02
0.2
0.1
0.1
0.01
1.86
1.99
0.0
100
200
0.0
0.0
0
100
200
Aug Stringth
Epoch
Epoch
(a) ACR aug-strength
(b) ACR while training (r=0.01). (c) ACR while training (r=0.92).
Figure 5: (a) Average Confusion Rate (ACR) and downstream accuracy E.S. different augmentation strength (before training). (b,c): ACR and downstream accuracy while training.
learning to the problem above. From Figure 4 we can see that when r = O (no augmentation), the features are mixed together and hardly (linearly) separable, which corresponds to the under-overlap case in Figure ((b As we increase from 0 to 0.1, the features become more and more discrim- inative. And when is too large (r === 1.5), the inter-class features become mixed and inseparable again (over-overlap). In Appendix C.2 we provide visualization results of the augmentation graphs, which also align well with our ana asalysis. Overall, our theoretical and empirical discussions verify our theory that intra-class augmentation overlap with proper amount of data augmentation is crucial for contrastive learning to work well.
5.2 NEW SURROGATE METRICS FOR AUGMENTATION OVERLAP
From our theory and analysis above, we see that the augmentation overlap between intra-class sam- ples indeed matters from contrastive learning generalize better. Inspired by this, propose the Confusion Ratio metric as a measure of the degree of augmentation overlap. Specifically, for an unlabeled dataset Dz, with N samples, we randomly augment each raw sample I; E D. for C times, and get an augmented set D., = {æıj. [M]. E [C]]. Then, for each Zip E Du that is an augmented view of x; E Du., denoting its k-nearest neighbors in D,, in the feature space of as ( and other augmented views from the same image as C(rip) = [Zigh + p). we can define its Confusion Ratio (CR) as the ratio of augmented views from different raw samples in its k-nearest neighbors.
CR( f) = # #[Na(Zip J) A((xip) E [0.
(6)
#Na f)
We also define its average as Average Confusion Ratio (ACR):
ACR(/) = =E E.,,5. CR(
(7)
When augmentation overlap happens, the nearest neighbors could be augmented views from a dif- ferent sample, leading to a higher ACR. Thus, ACR measures the degree of augmentation overlap, and higher ACR indicates higher degree of augmentation overlap. Here we take l: by default.
Here, to measure the augmentation strength in real-world datasets, following the common practice (Chen al., (2020a), we adopt the LandomResizedCrri augmentation, and we define its strength of augmentation as r = (1 b) + (1 - a) (a comparison with other kinds of augmentations, e.g., color jittering, can be found in Appendix C. As shown in Figure 5(a) ACR (augmentation overlap) indeed increases with the strength of data augmentations, and only moderate ACR achieves the best accuracy, which is consistent with our theory discussed above. Besides, we also plot the change of ACR along the training process in Figure [(b) & [(c)) We can notice that for weak augmentations, the initial ACR is low, and it rapidly decreases to zero and seldom changes while training. which leads to poor test accuracy. Instead, with proper aug- mentations, the initial ACR is higher, and it gradually decreases to zero and obtains good aceuracy. This is also consistent with our theory that we need a certain amount of augmentation overlap for contrastive learning to work well. At the beginning, this will lead to a higher ACR, but as training continues, better alignment (lower ACR) will help bring up the test accuracy.
operator with scale range [a, b] for data
Average Relative Confusion (ARC). In the discussion above, we notice that ACR itself does not indicate the test accuracy, but the relative change of ACR before and after training can be used as such an indicator. A large change of ACR means large change of augmentation overlap, which in- dicates that the contrastive loss actually cluster intra-class samples together through overlapped
8

---

Published as a conference paper at ICLR 2022
0.5
0.5
Test TettMoor93
0.8
Teet Au Cacc
AcE
25
Test MOOT
Od
20
0.4
03
0.2
0.15
10
001
0.3
0.5 0.82
1.90
1.99
0.01
0.3
06
0.60
1.96
1.96
on1
03
0.5
1.96
1.98
001
0.3
0.5 Strngghh
1.90
1.99
Sminggh
Striigh
Aug Strengh
(a) CIFAR- 10 (SimCLR)
(b) CIFAR-I0 (BYOL)
(c) CIFAR-100 (SimCLR)
(d) STL-10 (SimCLR)
Figure 6: Average Relative Confusion (ARC) and downstream accuracy v.s. different augmenta-
tion strength on different datasets (CIFAR-10. 10. CIFAR-100 and STL-10) with different contrastive
learning methods: SimCLR (Chen et al. 2020a) and BYOL (Grill et al. 2020
0.5
1.75
0.5
Acc
ARC
1.5
0.5
Acc
ARC
1.2
Tes, Accuray
Teat Aocurary
Text Aocurary
0.4
0.4
0.4
1.0
0.3
0.3
0.3
1.00
0.2
0.2
0.5
0.2
0.75
0.92
1,96
0.92
1.96
1.96
Strength
Aug Strength
Aug Strengih
(a) l: 10
(b) 20
(c) k 100
Figure 7: Average Relative Confusion (ARC) and downstream accuracy u.s. different augmentation strength on CIFAR-10 (SimCLR) with different number of nearest neighbors k.
views. Based on this observation, propose Average Relative Confusion (ARC) as
ARC 1 - ACR() 1 AmR()m)))
(8)
ratio calculated with the initial ACR of the initialized model finit and the final ACR of the pre- trained model final- A higher ARC indicates that the contrastive learning process faces hard task (augmentation overlap) at the beginning (high initial ACR), while successfully clustering intra-class samples with good alignment of positive samples at the end (lo final ACR). Therefore, higher ARC score should correspond to higher downstream accuracy.
As shown in Figure 7 augmentations become stronger, ARC scores indeed align well with the change of downstream accuracy across 1) different datasets, 2) different contrastive methods, and 3) different choices of k. This justifies our understanding of contrastive learning through augmentation overlap. Meanwhile, as the calculation of ARC only involves unsupervised data, it could serve as good surrogate metric for evaluating contrastive learning without using labeled data. Compared to previous evaluation methods like linear classification (Eq. 2). our ARC metric more preferable as 1) it is theoretically motivated; 2) does not need labeled data; 3) does not need to learn additional modules like linear classifiers or rotation tasks (Reed et al. 202T More experimental details can be found in Appendix
6 CONCLUSION
In this paper, we have proposed a new understanding of contrastive learning through a revisiting of the role of data augmentations. In particular, we notice the aggressive data augmentation applied in contrastive learning can significantly increase the augmentation overlap between intra-class sam- ples, and result, by aligning positive samples, we also cluster inter-class samples together. Based on this insight, we develop a new augmentation overlap theory that could guarantee good downstream performance without relying on conditional independence and obtain asymptotically closed gaps. With this perspective, we also characterize how different augmentation strength affects downstream performance with both random graphs and real-world datasets. Last but not least, also develop a new surrogate metric for evaluating contrastive learning without labels and show that aligns well with downstream performance. Overall, we helieve that we pave a new way for under- standing contrastive learning with insights on the designing of contrastive methods and evaluation metrics.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
Yisen Wang is partially supported by the National Natural Science Foundation of China under Grant 62006153, Project 2020BD006 supported by PKU-Baidu Fund, and Huawei Technologies Inc. Jiansheng Yang is supported by the National Science Foundation of China under Grant No. 11961141007. Zhouchen Lin is supported by the NSF China (No. 61731018), NSFC Tianyuan Fund for Mathematics (No. 12026606), Project 2020BD006 supported by PKU-Baidu Fund, and Qualcomm.
REFERENCES
Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives contrastive representation learning. arXiv preprint 1xkiv:2106.099:/ 2021.
Ivan Budimir, Sever S Dragomir, and Josep Pecaric. Further reverse results for jensen's discrete inequality and applications in information theory. RGMIA research report collection. 3(1), 2000.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. ICML, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self- supervised models are strong supervise learners. arXiv preprint arXiv:2006. 10029, 2020b.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. arXiv preprint 1..i::0011.05000 2020.
Xinlei Chen, Saining Xie, and Kaiming He. An empirical study of training self-supervised vision transformers. arXiv preprint arXiv:2104.02057, 2021.
Gong Cheng, Peicheng Zhou, and Junwei Han. RIFD-CNN: Rotation-invariant and fisher discrimi- native convolutional neural networks for object detection. In CVPR, 2016
Jean-Bastien Grill, Florian Strub, Florent Altché, C. Tallec, Pierre H. Richemond, Elena Buchatskaya, C. Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, B. Piot, K. Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent: A new approach to self-supervised learning. NeurIPS, 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. NeurlPS, 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. CVPR, 2020.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to a local nash equilibrium. NeurIPS, 2017.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildae Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. ICLR, 2019.
Weiran Huang, Mingyang Yi, and Xuyang Zhao. Towards the generalization of contrastive self- supervised learning. arXiv preprint arXiv:2111.0074, 2021.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008.00 0/0600 2020.
Ibrahim Merad, Yiyang Yu, Emmanuel Bacry, and Stéphane Gaiffas. About contrastive unsupervised
representation learning for classification and its convergence. arXiv preprint arXiv:2012.01064 2020.
Kento Nozawa and Issei Sato. Understanding negative samples in instance discriminative self- supervised representation learning. NeurIPS, 2021.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint 180.v:1807.03748. 2018
10

---

Published as a conference paper at ICLR 2022
Mathew D. Penrose. A Strong Law for the Longest Edge of the Minimal Spanning Tree. The Annals of Probability, 27(1):246 260, 1999.
Allon G Percus and Olivier C Martin. Scaling universalities of kth-nearest neighbor distances
closed manifolds. Advances in Applied Mathematics, 21(3):424 436, 1998. ISSN 0196-8858.
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. ICML, 2019.
Colorado J Reed, Sean Metzger, Aravind Srinivas, Trevor Darrell, and Kurt Keutzer. Selfaugment: Automatic augmentation policies for self-supervised learning. In CVPR, 2021.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In ICML, 2019.
Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual information estimators. In ICLR, 2020.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning. NeurIPS, 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv preprini arXiv:2003.022:44 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. In ALT, 2021.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self- supervised learning from multi-view perspective. In /CLR, 2021.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity the hypersphere, 2020.
Yifei Wang, Zhengyang Geng, Feng Jiang, Chuming Li, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Residual relaxation for multi-view representation learning. In NeurIPS, 2021.
Yichong Xu, Tianjun Xiao, Jiaxing Zhang, Kuiyuan Yang. and Zheng Zhang, volutional neural networks. arXiv preprint arXiv:1411.6369 2014.
con-

---

Published as a conference paper at ICLR 2022
A OMITTED PROOFS
A.1 PROOF OF PROPOSITION 3.1
Proposition A.1 (Class-uniform features also minimize the InfoNCE loss). For N training examples of classes, consider the case when features (f(x)) are randomly distributed in S with maximal uniformity while also satisfying 2 ~ p(x,x*),, x+)x f(x;) = {xxt). Because we have perfect alignment and perfect uniformity. the InfoNCE loss achieves its minimum. However, the downstream classification accuracy is at most 1/K + and is nearly zero when N is large enough.
Proof. We only need to give counterexample that satisfy the desired classification accuracy. We consider the case when there is no T-connectivity between any pair of samples from {ær j which is easily achieved if we adopt a small enough data augmentation. In this scenario, the perfect align- ment of positive samples (I,, could have no effect on the other samples. Therefore, when the features {f( are uniformly distributed Sm-1, according to the law of large number, for any measurable set E 5m-1, when is large enough, there will be almost equal size of features from each class in M. Consequently, any classifier that classifies U to class k will only have 1/K accuracy asymptotically.
A.2 PROOF OF THEOREM 4.2
We will prove the upper and lower bounds separately as follows.
A.2.1 THE UPPER BOUND
We first provide the upper bound of the approximation error of the following Monte Carlo estimate.
Lemma A.2. For LSF == log E p(s) exp(f(x)T g(z)), we denote its (biased) Monte Carlo estimate with M random samples ~ p(z), = 1,...,M .M as LSE = log 17 Eiz exp( g(zi)). Then the approximation error A(M) can be upper bounded in expectation as
A(M) Ep(x.))) LSE(M) LSE < O(M 1/2).
(9)
We can see that the approximation error converges to zero in the order of 1/M-2
1/2
Proof. First, we have
E (p())))
log
1
Σ exp(f(x) g(2+) log Eptz) exp(f(a) g((2))
M
M
ScEp(e,e.)
Σ
cxp(f(x) g(x))) ((())) Ep(x)) exp(f(x) exp(f(x)To(zz))) = (1221)))
M
where the first inequality follows the Intermediate Value Theorem and e (the natural number) is
the upper bound of the absolute derivative of log between two points when If(x) T[(=))] < 1. And the second inequality follows the Berry-Esseen Theorem given the bounded support of (x)({(x) 9(2:)) following: for i.i.d random variables Y, with bounded support supp(Y) C
12

---

Published as a conference paper at ICLR 2022
[-a, a.,, zero mean and bounded variance oy a², we have:
M
M
By
1
Y
M
v M
VM
i=1
Qy
ay
1
P
Yi
dx
VM
VMa
0
PIAY
1) (0)00,1122 x]
Ca dx VM
M
OY
aCa
P(IW(0.1) > x/dx)
V M
OY
Ca
a (0]] (M
VM
VM
where the constant Co only depends on a. Here, we set Y, = exp(s(x) g(()))
Ep(z.) exp(f(a) g(2i)). (z))). As [f(x) g(()) S 1, |. S 2e Y, has zero mean and bounded vari- ance (2e)?.
Theorem A.3. For each f E F, the mean CE loss can be upper bounded by the InfoNCE loss:
Ce y; f) S LNCE(E;; f) log(M/K) + VVr([[(x) v) + A(M),
(10)
where Var(f Bp(n) [Poee
Bppals) [=) denotes the conditional variance.
[z))]
Proof. Denote 2._ v) the joint distribution of the positive pairs x, x and the label y. Denote
the M independently negative smaples as { According to Assumption 4.1 xt and x here has the same label y. Denote My as the center of features of class y, y 1,..., K. Then we have the following lower bounds of the InfoNCE loss,
M
(NCE(f) = -xxzz fxx) f(x*)=+++)))==))()))) + Ep(a) E p(z; log exp(f(x) f(z,)) exp(f(=)(((TT))
==1
M
1
=- =-Ep(aat)((x)) f(x+) Bp(c)
log
exp(f(x)T f(x,)(x))) + log M
pla,))
M
(
2 -ppp fx) f(x+) Ep(r) log M
1 p(a,)
E
M
exp(f(x) ( A(M) log M
-Ep(e,tt) (x) f(x+) + Ep(s log E B exp(f (x) f(x - A(M) + log M
Epta,tt w) (z) fxx*) + Ep(x) log E Pp(o B Bpla p(pp-11))) v-) exp( (z) [(x )) A(M) + log M
()
2 Epplr,at v) (x) T f(x + Ep( log F exp (B [xx)) T f(x (())))))))))))) - A(M) + log M
Ep(naat w) f(x) (ny + f(xt) (4y) + Epte) log E exp by [f(x)) f(x )) ) A(M) + log M
Ep wi (f()) By f(x) T (f(x+()))))+))))))())(())) n,)1 Ex) log E p( cxp(f(x) (y-)) A(M) log M
(3)
2- Ep(aat w) [f(x) My + II(f(=+)) - py] + Ep(x) log En exp(f(x) My (0-)-AUU 1-((M) + log M
(4)
f (x) My E (f()) 12 + E Ep(x) log E Eplrr ex)(f(x)] My-) - A(M) + log M
K
1
-- (x)] By Var(J(x) v) + Ep(e) log
exp(f(x:T (4x) A(M) log M
K
K
-Ep(a.e) I- f(x)) My + log Σ
exp(f(x) [4)] - /Var(f(x) - A(M) + (lg(/KK)
k=
-fo - Var(J(x) v)) A(M) log(M/K),
13

---

Published as a conference paper at ICLR 2022
which is equivalent to our desired results. In the proof above, (1) follows Lemma A.2 (2) follows
the Jensen's 's inequality for the convex function exp(-): (3) follows from the fact that because f(x)
gm-1, we have
(f(zt)))))) & (((tt))
) (1 -m(
[1f(xt)) Hyll
-y)- - Myll:
(11)
and (4) follows the Cauchy-Schwarz inequality and the fact that because p(x,xx) = p(xt,x) holds, 2, x have the same marginal distribution.
A.2.2 THE LOWER BOUND
In this part, we further show lower bound on the downstream performance.
Lemma A.4 (Budimir al. (2000) Corollary 3.5 (restated)). Let 9 R + R be differentiable convex mapping and z E E. Suppose that g is L- smooth with the constant L O, i.e, Vx, y IR"h, [[Vg(z) Vg(y)]l - L yll. Then we have
0 < (2) g (E))))=) s L [Ex2) p() =|3] = Σ Var(z
(12)
where x(5) denotes the j-th dimension of æ.
With the lemma above, we can derive the lower bound of the downstream performance. Theorem A.S. For any F, we have
(f) 2 (NCE(E; f) Var(f(() v) Var(f(x) v) A(M) log M
(13)
K
where Var(u(<))yy) Ep(x) (1((x)))l((x)) 1p [ (())])) denotes the conditional variance.
Proof. Similar to the proof of Theorem A.3 we have
K
(.) = - Ep((.)) My + Ep(a) log
exp(s(x) (4)
1
Ep(a,)) (x) My + Ep(x) log
Σ
exp(X (1))) us) + log K
K
1=1
- (x) My + Ep(z) log E p(C. exp(J(x) (gy) log K
(
2 Exlass f(x (()) (wg fxxx)))] Ep(c) (( log M
exp([(x)T A(M) log K
2
2 Ep f(x)) E (l(= - Myll -
+ Eptt) B. POTT) log M
exp(E p(07 lo f(x) f(x5)) [
A(M) + log K
(3)
2 EEpla.r f(x) (ar(f(=) v)
M
+ Ep(a, p(u, E pp
log M Σ (xp(((x)Tf(r> f(x
Σ
Var(f,(>7) -(MM) + log K
2 1=1
--pp(tt)t)
f(x) f(x)T((xt)= ((aatt++0 +I p(a log exp(f(x) (((x)(((a))) f(x
Var(f(2 (v) Var(f 1 v) A(M) + log K log M
(4) 2xccE(2:1) VVr(f(() [y) 2
*Va(f(x)) () A(M) - log M
K
14

---

Published as a conference paper at ICLR 2022
which is our desired result. In the proof, (1) we adopt Monte Carlo estimate with M samples from p(y) and bound the approximation error with Lemma A.2 (2) follows the same deduction in The- inequality for the alignment term. As for the second term, we first show that the convex function logsumexp is L-smooth as a function of f(27) ) in our scenario. Because [lf(X))] S 1, we have (((1)).(()))) E R", the
orem A.3 (3) the first term is derived following the Cauchy-Schwand
following bound on the difference of their gradients holds
i [loglcxp(((=) f(x))) Eizs exp(f(x) f(xT)) [loglexp(f(1) f(x Eis exp(f(x) f(a, )))) 0)77))
0f(z))
(1op(()) exp(f(x)) [(,5,)
exp([(x)TT0TT)
[(x)
Eizy exp([(x]][ (pp((()TT(())) + Lifj (((
E exp( [(x,) )
exp exp(s
f(x,)) Exg exp(f(x)] (x)( ((
[[(()]]
(exp(f(x) f(z,)) exp(f(x) (cx
+ ef (z) f(z,)))
<[I/(>)| 1 -
So here the logsumexp is T-soooth for I. = 2-
Then, can apply the reversed Jensen's inequality
in Lemma
A.4 (4) holds because
(ar(f)())lv)
> Bp(w) Bp(all) ()((())()(())) (
(14)
= -Ep( Bp(all))
(f)(z) - Ex
5=1
= -Ep(y (p(att) [lf(()) E.y (2'))1
=Vr(((x))lv)
A.3 PROOF OF PROPOSITION 4.7
Proposition A.6. Under Assumptions 4.5 & 4..66 by minimizing the InfoNCE loss, we can conclude that the conditional variance term vanishes, i.e.,
Var(f(z) (3) 0.
(15)
Proof. Consider any T -connectedd sample ni, F.- Accoding to the definition of T-connectivityy
there exist ti E T such that (x) (x). When perfect alignment holds in Assumption 4.6 we will have f(x;) = ((,()=)) and f(x)) = ((,)) Combining with (xx2)) (xy)), we have (xx;)
= = f(x)). That is, any T-connected pair has same representation, Then, in the augmentation subgraph GR. that is connected according to Assumption 4.5) there exists a path for any pair of samples G,, 2j Gr where any two adjacent samples are T Tcoonectedd. As a result, A; -connectivvity recursively. At last, all samples in G% will have the same representation and the intra-class variance vanishes.
and &j will also have the same representation by applying 7
A.4 PROOF OF THEOREM 4.8
Theorem A.7 (Guarantees for the optimal encoder). If Assumption 4.1 4.5 & 4.6 hold and J is L-smooth, then, for the minimizer f -== arg min LNCE(f), its classifictiin risk can be upper and lower bounded by its contrastive risk as
Lxce(s*) - (M- (M-1/2) (C + log(M/K) Excr(I*) (M-1/2).
(16)
Proof. A direct combination of Theorem 4.2 and 4.7 will give the above two-sided bounds.
n
15

---

Published as a conference paper at ICLR 2022
B GENERALIZED GUARANTEES UNDER WEAK ALIGNMENT
In Section we have shown that with perfect alignment (Assumption 4.6). the variance terms in the bounds of Theorem can be minimized to zero, and consequently, the upper and lower bounds can be asymptotically closed. Nevertheless, in practice, due to the constraint of hypothesis class F and optimization algorithms, typically cannot achieve the exact minimizer, i.e., perfect degree of alignment. This motivates us to consider less restrictive setting, namely the s-weak alignment assumption, where the alignment error could be as large as E.
Definition B.1 (Weak Alignment). A mapping f satisfies e-weak alignment if 4 x, p(r, (l((z) - f(x+)ll S.
For any e-weak alignment f F,, we have the following bounds on its downstream risk. Theorem B.2 (Guarantees under weak alignment). If Assumption 4.7 4.3 hold, then vf F sat- isfying w-we alignment, its classification risk can be upper and lower bounded by its contrastive risk as
CxCE(s) De - -0
(17)
(S) 1og S (NCR(S) + DE O (M-1/2))
where D denotes the maximal diameter of the intra-class augmentation graphs (G k 1, and denotes the output dimension of the encoder f.
K}
In this way, we extend the guarantees developed optimal encoders (Theorem 4.8) to even non- minimizers f E F as long as it could align the positive samples within error &.
inf
Diameter
Diamater
3
Aug=0.001
Aug=0.5
Aug=1
Aug=1.5
0.0
1.5
2.0
100
500
1000
5000
10000
Aug Strength
Sample Number
(a) Diameter v.s. augmentation strength r.
(b) Diameter v.s. number of samples.
Figure 8: Evaluation of the maximal diameter D function of different augmentation strength (a)
and different number of samples (b) on the synthetic data in Section 5.1
Empirical Verification. Besides the alignment error, we could notice this relaxation also introduces the dependence on an additional parameter D, the maximal diameter of the intra-class augmentation graphs. As shown in Figure 8. when the augmentation is very weak, the intra-class graph is not connected and the diameter is 50. Then, by applying stronger augmentations, D will become smaller (fully connected). Besides, increasing the number of samples,
and smaller, and finally converge ranging from 50 to 10, 000, does not have a large impact on D in practice. Given these facts, we could reasonably assume that D is bounded and has relatively small value with properly chosen augmentations. As a result, with bounded diameter D, small alignment a small generalization gap between the upstream and downstream tasks. This generalizes Theorem 4.8 by quantifying the generalization gap under weak alignment.
will guarantee
Proof. Consider any pair of samples (I,x²) from the same class y, and the positive sample of x as + As intra-class connectivity holds, æ and x' are connected, and the maximal length of the path from to x' is D. Therefore, under the e-weak alignment that
Va,x t p(a, (1)()) f(x s
(18)
we can bound the representation distance between and x' by the triangular inequality
[I[(x) [(+)||<
sup
[[((x) (s
(19)
p(z.z 1p<p(s..
16

---

Published as a conference paper at ICLR 2022
With the inequality above, bound the variance terms in Theorem 4.2 In particular, the conditional variance can be bounded as
Var(f(x) v)
-Pppoo Bpcalvi f(x) - Ex f(x')11
- Ep(o) Bp(ale) / (xx) {<x))11
SPpc Be(aly) Bpte (1) - -(z')1
(20)
BPp( max (1 [()')11
a.v'~p(alv)
E p(s) D2 D2g²
where (1) follows Eq. 19 At last, we can bound the variance items in Theorem 4.2 with Eq. arrive at the desired bounds
20
(NCE(f) DE D2 (
(f + log(M/K) & LNCElf) + DE + 1MM00M1000 (M-
which conclude proof.
C ADDITIONAL EMPIRICAL EVIDENCE
C.I FURTHER EVALUATION OF ARC METRIC
In the main text, we study the effect of different strength of RandomResizedCrop on the downstream accuracy as our proposed metrics (ACR and ARC), which help verify our theory. Nevertheless, in practice, the augmentations adopted in contrastive learning is composed of list of different kinds of augmentations. Therefore, this part, we further study the effect other types of data
augmentations, and we show that our ARC metric also effective for evaluating not only other kinds of data augmentations, but also their composed ones.
Randomm@nsttgsCCngg
70
80
AGC
Color_kiter
lorizonlalFiip
Solertzation
Gaussian GrayScale
1.5
25
3.0
Figure 9: Downstream accuracy (ACC) v.s. Average Relative Confusion (ARC) for different types of augmentations in SimCLR on CIF
Comparing different kinds of augmentations. We begin by comparing the four kinds data aug- mentations adopted in SimCLR (Chen et al.) 2020a]: RandomResizedCrop ColorJitter, Grayscale, etc. For fair comparison, we apply each alone for contrastive learning, and evaluate both the downstream accuracy and ARC. From Tigure[l we can conclude that among the six kinds of aug- mentations, RandomResszzedCrpp is the most important augmentation, and ColorJitter is the second. The rest of them are less powerful, as they cannot even learn useful features by themselves. We also that our ARC metric aligns well with the downstream accuracy for different kinds of augmentations.
Comparing ColorJitter with different strength. Based on the observation above, as we have discussed RandomResizedCrop in Section 5.2, we now choose ColorJitter, the second important augmentation, another kind of augmentation for the study of different augmentation strength. Specifically, we study the four parameters brightness, contrast, saturation, and hue, where large value corresponds a large degree of augmentation. Note that we also adopt the default augmentations in SimCLR while only changing the parameters of ColorJitter (different to the setup in Figure 99. As shown in Figure TO there is also reverse-U curve like that in RandomResizedCrop. and the
17

---

Published as a conference paper at ICLR 2022
25
25
Acc ARC
Acc
Accuracy
80
Test Accuracy
20
16
86
15
10
84
10
0.3
0.5
0.8
0.3
0.5 Aug Strength
Aug Strength
(a) Brightness.
(b) Saturation.
Acc ARC
Ace ARRO
Test Ancuracy
88
-20
Accuracy
20
15
ARC
62.5
15
5
10
0.3
0.8
0.1
0.2
0.4
0.5
Aug Sirength
Aug Strength
(c) Contrast.
(d) Hue.
Figure 10:
Average Relative Confusion (ARC) v.s. downstream accuracy with different augmenta- tion strength on four different kinds of color jittering operations.
sweet spot is usually achieved with 0.8, which corresponds to the default of choice SimCLR (which is selected with exhausted hyperparameter search). Meanwhile, our ARC metric still aligns well with the downstream accuracy for different strength of different kinds of color jittering, which demonstrates its wide applicability.
90
80
Aco
70
60
50
p=
2
3
loglARC)
Downstream accuracy (ACC) v.s. the logarithm of Average Relative Confusion (ARC) on composition of RandomResizedCCog and ColorJitter with different strength. Experiments are conducted on CIFAR-10 with SimCLR.
Figure 11:
Comparing composed augmentations. In the above discussion, we focus on the effect of a single kind of augmentations. Here, show that ARC metric is still effective for evaluating the composition of different augmentations. Notably, it hard to define metric of augmentation strength in this case, as the effect different augmentations could be nested. Nevertheless, we can still draw a "ACC log(ARC)" plot to show the correlation between the downstream accuracy (ACC) and our ARC metric, where each point denotes model trained with randomly selected parameters of ResiedResizedCrrop and ColorJitter. As shown in Figure 11 we can see there is indeed a strong correlation between the two metrics, with a Pearson correlation coefficient = 0.80. Therefore, our metric can be used for selecting different kinds of augmentations well as their compositions in an unsupervised fashion.
18

---

Published as a conference paper at ICLR 2022
C.2 VISUALIZATION OF AUGMENTATION GRAPH
For a more intuitive and practical understanding of our augmentation overlap theory developed in
Section 4 we visualize of the augmentation graphs on both synthetic data (Section 5.1) and real- world data (Section 5.2
(a) r 0, acc 0.50. (b) r
acc 0.78. (c) r 0.1, acc 1.00. (d) r 15, acc 0.50.
Figure 12: Visualization of the augmentation graph with different augmentation strength on the synthetic data described in Section 5.1 Each color denotes a connected component. The corre- sponding t-SNE visualization and test accuracy (of contrastive learning) can be found in Figure
Synthetic data. Following the setting of experiments in Section 5.1 we construct the adjacent matrix of different samples, calculate its connected components, and visualize it in Figure [2 with different colors. It shows that when there is no augmentation, i.e., r O, each sample is a con- nected component alone, and the number of connected components is the same the number of samples N. As we increase the augmentation strength, samples will be connected together through the augmented views. In particular, when r 0.1, the whole intra-class samples are connected while inter-class samples are separated, which exactly satisfy our assumptions on intra-class con- nectivity and label consistency, respectively. Therefore, this is the perfect overlap desired, and indeed, as shown in Figure [5.1] contrastive learning on obtains 100% test accuracy. When we keep increasing the augmentation strength to be as large as 1.5, inter-class samples also become connected and inseparable, leading to a random guess in test accuracy (50%). This shows that the relationship between the augmentation graph and the downstream performance aligns well with our augmentation overlap theory.
(a) Under-overlap augmentation (b) Proper overlap augmentation (c) Over-overlap graph (r=0.01, ac25).25).
augmentation
graph 0r90,2,, acc=0.75).
graph (r=1.96, acc=9.29).
Figure 13: The augmentation graph of CIFAR- 10 with different strength r of RandomRessizddrrp as in Section 5.2, We choose a random subset of test images, randomly augment each one for 20 times. Then, calculate the sample distance in the representation space in prior work like FID (Heusel al. 2017), and draw edges for image pairs whose smallest view distance is below a small threshold, Afterwards, we visualize the samples with t-SNE and color intra-class edges in black and inter-class edges in red and report their frequencies.
Real-world data. For the ease of analysis, augmentation overlap theory adopts simplified scenario by assuming label consistency (Assumption 4.1p and intra-class connectivity (Assumption 4.5), and we have verified their feasibility on the synthetic data. In comparison, these assumptions cannot hold exactly on real-world data as the chosen augmentations could be sub-optimal. Never- theless, as shown in the augmentation graphs of CIFAR-10 (Figure our assumptions could still approximately hold: with a properly chosen augmentation strength, the inter-class connections will be much less frequent than intra-class connections: 96.4% edges are intra-class edges. Further con- sidering the continuity property and extrapolation ability of deep neural networks, these approximate conditions could still achieve close performance to the optimal performance guaranteed under the
19

---

Published as a conference paper at ICLR 2022
exact conditions. Besides, we also have similar conclusions for the under-overlap and over-overlap scenarios: 1) the lack of enough augmentations produces only few edges in the augmentation graph, as a result, even though all edges are intra-class edges, the downstream performance still poor (25% test accuracy); 2) too strong augmentations instead produce too many inter-class edges (87.6%), which laso leads poor downstream accuracy (29%). This highlights that assumptions on label consistency and intra-class connectivity are indeed effective guidelines for the designing of contrastive methods.
D THEORETICAL CHARACTERIZATION OF AUGMENTATION STRENGTH
Following the setting in Section 5.1 we can take the radius r as a notation of augmentation strength, and analyze its effect on the connectivity of the corresponding augmentation graph.
Theorem D.1. For N random samples taken from a class, while gradually increasing the augmen- tation strength r, we have the following results.
(a) Under-overlap. When 0 Sr [d/2))
J/ (H)
1/4+1/02
IN + +TTTN-TT
where T1 is the minimal distance between N samples, all samples (vertices) in the aug- mentation graph will be isolated. As result, the learned features could be totally random
as in Proposition 3.1 Instead, if 2 there are at least two intra-class samples are T -connecced and enjoy the same representation.
(b) Perfect overlap. When 2
Kd/2j4 (N-241/d) / (N-2) ( 2(-1I)
1/d41/d
where r2 is the maximal distance between N samples, all samples in the augmentation graph will be -connected. As a result, the classwise connectivity Assumption 4.5 will be guaranteed.
(c) Over-overlap. When <r m
where v3 is the (asymptotic) minimal distance between samples from different classes, the label consistency is guaran- teed. Otherwise, when the augmentation is too large, e.g., T > T3, there will be inter-class augmentation overlap and Assumption 4.1 not longer holds.
In the theorem above, we show that the proper augmentation strength function of the number of samples N and the input dimensions d. In particular, for each 2, as N increases, there will be more natural examples and we only need a smaller r to obtain overlap sample. Instead, as d increases, due to the curse of dimensionality, there will be less samples within the same distance, thus requires a larger r.
Nevertheless, we actually only need the augmentation sub-graph Gp to be connected, instead of being fully connected as in Theorem D.I (b). While the connectivity is hard to analyze in the finite sample scenario (N oo). we have the following asymptotic property as N cc.
Theorem D.2. For N uniformly distributed samples defined in IRd as above, we denote the min- imal augmentation strength needed for connectivity as a function of N: eN = inf(r > Glr)) is connected), and the minimal augmentation strength needed for avoiding isolated points as a function of N: dx = inf(r > O every vertex at least has neighbour). Vu is the volume of unit hyperball. Then we have the following asymptotic result:
(
N²
log N ) = 2 (1-1/d) (1-1//0
N2
2 lim
CN
log )
lim N
d
(21)
N
Vn
0c. First, this result is aligned with the empirical finding that self-supervised learning can benefit more from large scale dataset (Chen et al., 2020b). Second, it also indicate a curse of dimensionality that the required augmentation strength is exponentially large.
From the theorem we can see that ot decreases in the order of θ
Nog N=
as N
+
D.I PROOF OF THEOREM D.
Proof. From definition and notation in section 4. We can construct an augmentation Graph G(D, T) given N random samples. We define D₃ the distance from random point its k-th nearest
20

---

Published as a conference paper at ICLR 2022
neighbour. Percus & Martin (1998) discuss D2 in random grpah and give the estimation of that:
[dd/)]]] VT
1 1/d) (k
1/d + 1/d2 + O (N (N-
D& =
- [
(22)
(k ( 1)!
2(N 1)
where d the dimension of hypersphere and is the number of random points. When r < D2 there is no edge in the graph. So the class is separated. When r > DN-1. any pair of vertexes have an edge between them,so the graph is full connected.
D.2 PROOF OF THEOREM D.2
Proof. Denote
CN = inf 0: Gv,V E,r;)is connected).
(23)
With Theorem 1.1 from Penrose 1999) and features uniformly distributed in the surface of unit hypersphere, V, denotes to the volume of unit hypershpere
A2
(1
4)s
lim (cN N
d
d22
(24)
log N
Va
log 2NTV.d
NN0 when N > No. and augmentation strength larger than connected,i.e the class is overlapped.
+ 61, the graph is
Then we want specify the case the class will be depart begin with some concepts in graph theory. The largest nearest-neighhor link: For give edge distance and for each i= I,...,nllet
deg UN.J
Σ
Le11U, Unll S r
(25)
ISTAREN
to be the degree of the vertex Uj in the random graph (V, E, E,), and let
(r; = min Um.1(x,..., deg UN.v(=)}
(26)
be the minimum vertex Define the largest nearest-neighhor link, the smallest edge distance which each vertex has least one neighbor
dx = in dN(ri) 2 1}
(27)
With Theorem 1.2 from Penrose 1999).
N2 (1 2)5 .22
lim d
log N =
(28)
Vn
N
END when N > Ný, and augmentation strength is less than ((dd1)) N N c2, there will be at least 1 isolated point which is not connected to any other point,i.e e the class is departed.
2N
Thus 3N
max(No, N%). N > N1. if augmentation strength is larger than (2(d-1)51og N )j + 61, the graph connected, if augmentation strength is less than Vod
(2 1)5 N j C2, there will be least isolated point.
2.
E ADDITIONAL EXPERIMENTAL DETAILS
E. SIMULATION ON RANDOM AUGMENTATION GRAPH
Following our setting in Section 5.1 we consider a binary classification task with InfoNCE loss. We generate data from two uniform distribution on a unit ball $2 in the 3-dimensional space. One center (0, 0, 1) and another is (0, 0, - 1). The area of both parts are 1. We take 5000 samples as train set and 1000 samples as test set. For the encoder class F. we use single-hidden-layer neural network with softmax activation, and
InfoNCE loss to optimize it.
E.2 EXPERIMENTS ON REAL-WORLD DATASETS
To better understand and verify theorem, conduct experiments real-world datasets, in- cluding CIFAR-I0, CIFAR-I0K 100 and ST1-10. We use SimCLR (Chen et al., 2020a) and BYOL Grill et al. (2020) as our training framework and use ResNet18 as our network. For CIFAR-10 and CIFAR- T00, we adopt C 10 augmentations for each image, and search neural neighbors in the entire augmented dataset. For STL-10, we adopt C 6 due its relatively large size.
21


Reviews:
[{"review_id": "rdCs3XG597o", "reviewer": "Reviewer_bTLa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe authors provided a new understanding of contrastive learning from the perspective of data augmentation for intra-class samples. Moreover, to evaluate the effect of data augmentation a quantitative analysis is provided along with a new metric. \n\n############\n\nWeaknesses:\n\n. Theorem 4.2: For the downstream classification, the loss is upper and lower bounded in terms of the L_NCE loss. The authors provided comparison with Saunshi et al. (2019) from the technical perspective. Is there any intuitive explanation on how to evaluate the classification performance in terms of contrastive learning (loss)? \n\n. Assumption 4.5 (intra-class connectivity): This assumption is strong. Without the label information, it seems impossible to derive such augmentation set. Please add discussion on the practicality of this assumption, and show an example on some datasets if possible.\n\n. Proposition 4.7: Based on the proof provided in the appendix the conclusion not only relies on the existence of such augmentation set (Assumption 4.5), but also that such augmentation should be applied to intra-class samples, ie, t_i(x_i) = t_j(x_j). This kind of operation is impractical without the label information. Please add comment on that.\n\n. In the experiments, RandomResizedCrop is used to illustrate the relationship between Aug Strength and ACC(ARC). The best performance for different datasets all achieves at Aug Strength = 0.92. Any comments on that? eg., in terms of data augmentation for intra-class samples at Aug Strength = 0.92?\n\n. In practice, there are different kinds of data augmentation, eg, flipping, rotation, and scaling. The authors only showed results on RandomResizedCrop. Can you show results for other data augmentation types? Do you have similar conclusion as that for RandomResizedCrop? \n\n. Different data augmentation types are often used together in practice (eg, randomly pick two augmentations from the augmentation set for the raw image). Then how to apply the proposed analysis in such practical case? In particular, how to measure the Aug Strength? \n\n. The authors emphasized the importance of the data augmentation design for intra-class samples (ie, perfect overlapping). 1) The study on applying the analysis to existing contrastive learning algorithms is, however, preliminary (only with RandomResizedCrop). 2) Based on the proposed analysis how to find the sweet spot of data augmentation for contrastive learning is crucial, but this is not discussed. \n\n", "summary_of_the_paper": "The authors provided a new understanding of contrastive learning from the perspective of data augmentation for intra-class samples. In particular, the authors proposed to understand the role of data augmentation as to create certain ``chaos'' between intra-class samples so to encourage the clustering of intra-class samples and also the learning of class-separated representations. Additionally, a new metric ARC is proposed to evaluate the downstream performance. The conclusion is validated via both synthetic and real-world datasets. ", "summary_of_the_review": "The idea of understanding contrastive learning from the perspective of data augmentation for intra-class samples is interesting. However, 1) some key assumption for the analysis is too strong; 2) the analysis on the existing contrastive learning algorithms is preliminary and needs more work; and 3) the authors emphasized the importance of finding the sweet spot of data augmentation (ie, perfect overlapping). But how to achieve that in practice is not discussed.", "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": "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": "VUq7VDDE7Si", "reviewer": "Reviewer_tWSB", "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\n- (S1) The problem being addressed is very relevant. Contrastive learning has enjoyed a lot of empirical success, and various works on theoretically understanding lack in one of many aspects when it comes to closeness to practice. This paper addresses issues with the theoretical assumptions and results in many prior work.\n\n- (S2) Theorem 4.2 that upper bounds the downstream classification loss without conditional independence is new and interesting. The ACR metric that can select good augmentations using just unlabeled data is also an interesting finding.\n\n- (S2) Various parts of the paper are accompanied with experiments (simulations and on standard datasets) to relate the theoretical analysis to practice\n\n- (S3) Paper is clearly written and easy to follow\n\n**Weaknesses**:\n\nHere are many concerns about the theoretical assumptions and results that would help to have addressed by the authors.\n\n- (W1) Assumption 4.6: One of the main concerns is the perfect alignment assumption, which *assumes* that the optimal solution $f^*$ of the NCE loss will satisfy $f^*(x) = f^*(x^+)$ for all positive samples $x$ and $x^+$. This seems like an unnatural assumption to make directly on the optimal solution, and is implicitly an assumption on the distribution of positive samples $p(x, x^+)$, since the optimal unit norm representations that minimizes that infoNCE loss depends strongly on this distribution. While some arguments for perfect alignment have been made in prior work [3], it is not clear whether that can be coherently imported here as an assumption. In fact, it is quite likely that the optimal infoNCE solution will not satisfy this assumption exactly for most joint distributions $p(x, x^+)$ (at the very least, a lot more justification is needed). This benign looking assumption undercuts the point that results here are shown under \"less restrictive assumptions\" compared to prior work, and it kind of trivializes the result in Theorem 4.8. **Note that the concern here is not just that the assumption is too strong or unrealistic (which is often unavoidable and acceptable), but that its not clear when the assumption can even be true and whether or not it is mathematically compatible with the rest of the setting.**.\n\n- (W2) (Non-)vacuousness of bounds: I found Theorem 4.2 interesting since it can show a bound similar to the bound from [1] but without the conditional independence. One discussion I found missing is about how vacuous/non-vacuous the upper bound can be. Since the upper bound looks like $\\mathcal{L}_{NCE}(f) - \\log(M/K) + \\sqrt{\\text{Var}(f(x) | y)}$, it is not entirely clear whether this bound can ever be non-vacuous, i.e. are there cases where the sum of these terms can be very small. For e.g., in Theorem 4.8 where $\\text{Var}(f(x) | y) = 0$, I can estimate a rough lower bound on this upper bound of $\\log(M/K + M(1-1/K)/e^2) - \\log(M/K) \\approx \\log(1 + (K-1)/e^2)$ which can be large for a large value of $K$. (here I used $\\|f(x)\\| = 1$). A discussion about the vacuousness (or not) of the bound can be critical in understanding whether the bound is indeed meaningful. A side note, given Theorem 4.2 and Proposition 4.7, Theorem 4.8 just seems like a corollary rather than a theorem.\n\n- (W3) The result in [2] does not need conditional independence kind of assumption and in fact does analyze a more general case, albeit for a different spectral version of the contrastive loss. In particular, Assumption 4.1 from this paper will lead to $\\alpha=0$ from that paper, and Assumption 4.5 from this paper will lead to reasonably high value for the Dirichlet conductance $\\rho_{K}$ that shows up in their bound. Given that their results for spectral contrastive learning hold for the setting being considered in this paper, it is worth making a more detailed comparison to that paper.\n\n\n**Other comments and questions**\n\n- Section 5.1 seems to have some potentially interesting hypersphere example to demonstrate many of the points, but I thought it was not discussed enough in the main paper. It would help to give a short and clear summary of the results in Section B in the main paper.\n\n- Some statements made in the paper deserve much more justification or could be toned down. E.g. \"the class collision terms that are incompressible in Saunshi et al. (2019) now disappear in our bounds by adopting the InfoNCE loss, which also explains why InfoNCE performs better in practice\": this does not really seem like an explanation for why InfoNCE performs better in practice, it is a weak justification at best. \"increasing M indeed leads to a lower approximation error and helps close the gap\" this is not clear since $\\mathcal{L}_{NCE}(f)$ also depends on $M$.\n\n- The setting for Proposition 3.1 is not described clearly, with regards to what kind of augmentation distributions (overlapping or not) does it hold for. I can only guess that it is for the case where they don't overlap for any pair of inputs, so it is not applicable when Assumption 4.5 is satisfied for example. Some clarification on this would be appreciated.\n\n- Assumption 4.1 says that the conditional label distribution $p(y|x) = p(y|x^+)$ matches for positive samples $x$ and $x^+$. However this assumption is invoked in many places to say that inputs from different classes do not have overlapping support of augmentations and that the label is deterministic given $x$ or $x^+$, e.g. \"Besides, because proper data augmentation will not cause inter-class support overlap (Assumption 4.1)\" on page 6. Perhaps this assumption needs to be modified appropriately, or may be a separate assumption is needed about augmentation distributions not overlapping between inputs from different classes.\n\n- The ACR metric makes sense and it is interesting that it helps in practice. but connection to theory is weaker than it is made out to be. After all the theory only talks about the overlap between augmentation distributions, but nothing about the nearest neighbors w.r.t. randomly initialized network features or the learned features.\n\n- Will help to explain what $f_j(x)$ means in Theorem 4.2; seems like it means that $j^{th}$ coordinate of $f(x)$.\n\n- Proposition 4.7 should only be true for $f^*$ and not all $f$.\n\n- Is \"chaos\" used as a technical term? If so, any citation for its prior usage would be useful to include.\n\n- Missing citations: [4,5] theoretically analyze contrastive learning for downstream task, [6] reports inverted-U shaped curves as in Figures 7 and 8 in this paper.\n\n[1] Arora et al., A theoretical analysis of contrastive unsupervised representation learning. 2019.\n\n[2] HaoChen et al., Provable guarantees for self-supervised deep learning with spectral contrastive loss. 2021.\n\n[3] Wang et al., Understanding contrastive representation learning through alignment and uniformity on the hypersphere. 2020.\n\n[4] Tosh et al., Contrastive estimation reveals topic posterior information to linear models. 2020.\n\n[5] Tosh et al., Contrastive learning, multi-view redundancy, and linear models. 2020.\n\n[6] Tian et al., What Makes for Good Views for Contrastive Learning? 2020.", "summary_of_the_paper": "This paper aims to provide theoretical understanding for contrastive learning where \"similar pairs\" of points $x$ and $x^+$ are encouraged to have similar representations through an InfoNCE inspired objective function. Some prior works show the benefit of learned representations for linearly classifying downstream classes, by making conditional independence like assumption on the similar pairs or positive samples, i.e. $x$ and $x^+$ are (approximately) conditionally independent given downstream label $y$. This work argues that these assumptions are quite strong for contrastive learning with data augmentations, and aims to show guarantees under the following weaker and more realistic assumption: support of augmentation distribution of different inputs from the same class overlap to form a \"connected graph\" of inputs within a class, whereas support of augmentations of inputs from different classes do not overlap. Lower and upper bounds using this and some other assumptions, connecting the downstream performance of representation function to the contrastive loss. Some simulation experiments are presented to support some aspects of the theoretical analysis.\n\nUsing the insights from the analysis, the paper proposes an \"Average Confusion Ratio (ACR)\" metric that can be used to predict the ranking of downstream performances of different augmentations **using only unlabeled data**. Experimental evidence is provided on CIFAR and STL datasets to verify the efficacy of this metric for some practical augmentations. \n\n\nWhile there are some interesting aspects in the paper (especially the ACR metric), the theoretical analysis seems to have raised many questions and concerns that I have summarized below (details in main review). \n\n- **Soundness of assumptions**: Assumption 4.6, which is crucial, seems questionable and may not be coherent or appropriate to make in this setting. More on this in point (W2) of main review\n\n- **Deeper dive into theoretical results**: There is a lack of discussion about the (non-)vacuousness of the bounds in the main results Theorem 4.2 and 4.8, that puts the interpretation and significance of the result in question. More on this and related issues in point (W2) of main review.\n\n- **Comparison to prior work**: The work of HaoChen et al. in particular is not adequately compared to, especially since some of the points being addressed here are covered through a different kind of analysis in that paper. More on this in point (W3) of main review.", "summary_of_the_review": "The paper aims to provide some theoretical analysis for contrastive representation learning under weaker assumptions than prior work (like conditional independence) and has some interesting empirical findings about how performance of augmentations can be ranked using a metric that depends just on unlabeled data. While the general idea is nice, there are issues with the theoretical setup (as described in the main review), raising questions about the meaningful-ness of the assumptions and results. Furthermore the comparison to prior very relevant work is also inadequate. This leads me to assign a score of reject for the current version.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "V63nzBcHbry", "reviewer": "Reviewer_qd5j", "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": "In this exploration of data augmentation, much emphasis has been placed in the concept of \"augmentation strength\" - but what about the choices of augmentations themselves?  Can we perhaps use the ARC metric to evaluate, compare, and select data augmentation schemes themselves?  Separately, can the ARC metric be used to guide the selection of data augmentation parameters?  For example, for an arbitrary given augmentation scheme we can calculate the parameters that would maximize the ARC metric in an unsupervised way - then would applying those augmentations lead to comparable performance across different *choices* of augmentation strategies?  In other words, is the ARC metric a strong-enough metric that supercedes the selection of data augmentation strategies?  I would like to see more thought, analysis, and application regarding this new metric to fully convince me of its value and uses.\n\nAdditionally, to bridge the synthetic scenario and real data, I would like to see an augmentation graph of real augmented images, drawn with T-connections (where T can even be 1), and perhaps varied over different strength parameters.  I think there is definitely a gap between the authors' theoretical proposals/scenarios and that of actual natural data that can be closed with extra effort.  For example, the authors only mention one augmentation scheme to measure augmentation strength in real-world datasets, the RandomResizedCrop operator, and only evaluate it using their proposed metric.  Lastly, the reference section appears rather sparse, given the massive catalogue of work (including theoretical) surrounding contrastive learning.\n\nSome typos:\n- \"alone cannot guarantee to learn class-discriminative...\" should be \"alone cannot guarantee the learning of class-discriminative...\"\n- \"Comparing to Saunshi..., while ours only...\" should be \"Compared to Saunshi..., ours only\" (page 6, Section 4.2).\n- \"and the surrogate could complete its mission...\" should be \" and the surrogate can complete its mission...\" (page 7, Section 4.3)\n- \"different augmentation strength affects\" should be \"different augmentation strengths affect\" (page 9, Section 6).\n- \"We take 500 sample as...For the encoder class , we...\" should be \"We take 500 samples as...For the encoder class, we\" (page 16, Section D.1)", "summary_of_the_paper": "The current leading theory of what contrastive losses are doing and why they work interprets contrastive learning as balancing alignment with uniformity, as proposed in [2].  This paper seeks to augment that understanding of contrastive learning using a new perspective, focusing on the role of data augmentation.  It is well-known that contrastive learning techniques are highly sensitive to the data augmentation schemes used, most notably discussed in [1].  In this work, the authors interpret augmentation as a way to connect different intra-class images together.  Then, the contrastive loss is seen as a way to gradually cluster intra-class samples together by aligning augmented views, producing representations that are class-separated even in feature space.\n\nOn top of introducing a new lens with which to understand contrastive learning, the authors also provide proofs on performance guarantees, as well as a new evaluation metric.  The metric is inspired by their augmentation-oriented understanding, and was also found to align well with downstream performance.\n\nThe authors provide a scenario where alignment and uniformity are satisfied, but fails to translate well to downstream classification accuracy.  This suggests to them that the instance discrimination task alone cannot guarantee the learning of class-discriminative features that would enable better downstream classification, and directs their attention to the other important component of contrastive-learning to help explain the story: augmentation.  They then build off the analytical work of [3] to prove guarantees for the downstream performance with a relaxed assumption.\n\n\n[1] Chen et al., A Simple Framework for Contrastive Learning of Visual Representations, 2021.\n\n[2] Wang and Isola., Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere, 2020.\n\n[3] Saunshi et al., A theoretical analysis of contrastive unsupervised representation learning, 2019.\n", "summary_of_the_review": "The authors expand our understanding of contrastive learning on top of the existing alignment and uniformity perspective, by studying the role of data augmentation.  They provide theoretical guarantees on downstream performance, and propose an interesting new metric that can be evaluated using only the given unsupervised data.  Overall I think this is a strong submission, and would recommend an accept.  ", "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": "MHCGIhAfG1t", "reviewer": "Reviewer_Pr6A", "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:\n+ Theory considering both augmentation and alignment, without making too much assumptions.\n+ Empirical verification on the niceness of a proper amount of augmentation.\n+ The ACR and ARC metrics characterizes the interplay between augmentation and alignment, and are indicative of task performance.\n\nWeaknesses:\n+ The theoretical results are a bit weak. E.g., as pointed out in paper, Thm 4.8 only talks about the minimizer of the contrastive loss.\n\n  Maybe this is unavoidable with the current set of augmentations. But can there be a version with the perfect alignment assumptions relaxed into approximate alignment? If so, it might be possible to talk about non-minimizers.\n\n+ Proposition 3.1 is incorrect (but fixable I think). \n\n  No finite samples can attain uniformity, because perfect alignment $\\implies$ features are concentrated among finite number of vectors $\\implies$ not a uniform distribution. The exact stated form is wrong, but I think some variants of it is true. \n\n+ Figure 6.\n\n  What is the experiment setting for this?\n\n+ Sec. 5.1 \"... And when $r$ is too large ($r=3$), ... \"\n \n  Is $r$ the geodesic distance on sphere or Euclidean distance in the ambient space? Either case, it is really large... (almost) containing the entire sphere! Is there not a milder augmentation that can also show the difference?\n   ", "summary_of_the_paper": "The paper proposes a new theory for understanding contrastive representation learning. The novelty is the focus on the interplay between alignment and augmentation. Prior work has identified alignment as one of the factors of contrastive learning, but have not investigated how different types of augmentations may affect the learned embeddings. This work adds that missing piece. The results intuitively make sense, showing that proper amount of augmentation (that connects samples of the same class) has positive effect on downstream classification. Empirically, the authors verify that too weak or too strong augmentation harms performance. Based on observations, the authors define a metric on ratio of positive pairs among nearest (embedding) neighbors, and found the change of this metric throughout training positively correlate with performance.", "summary_of_the_review": "The paper provides a theoretical analysis on the interplay between alignment and augmentations. Empirical experiments nicely complement the theory, and lead to interesting metrics that reveal the properties of this interplay. Overall the paper is also nicely written. While there is one slightly incorrect claim (which I think is fixable) and some places that would need clarification, I think the findings in this paper are valuable to the field. Thus, I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper under review provides a theoretical analysis for contrastive representation learning. The paper proposes a guarantee on the performance (specifically upper and lower bounds) without resorting to previously used conditional independence assumptions. Throughout, the theoretical results and assumptions are supported by experiments. 

After a lively discussion, and after changes made to the paper in the revision stage, all four reviewers recommend this paper for acceptance. 
- Reviewer tWSB appreciates that the paper makes weaker assumptions than prior work (i.e., not assuming conditional independence), but raises a number of serious concerns on the theoretical results: The review questions whether assumption 4.6 used in the theory can be true, and whether the bound is vacuousness. The authors argue that this assumption was used in prior work, point out that only some of their results rely on this assumption, and that the assumption is compatible with the theory. The response of the authors partly resolved the reviewers concern and the reviewer raised their score. 
- Reviewer bTLa finds the idea of understanding contrastive learning for intra-class samples interesting, but finds some key assumptions too strong, a critique similar to that raised by reviewer tWSB. The authors responded and the reviewer increased their score, and mentioned that most concerns were addressed. The response partially resolved the reviewers concern, and the reviewer now also recommends acceptance. 

I recommend to accept the paper. Understanding contrastive learning better is an important problem, and based on my own reading, I agree with the reviewers that the paper contributes to the understanding of contrastive learning. Two reviewers had concerns about unrealistic assumptions, but those have been largely resolved in the discussion.
Decision: Accept (Poster)