summaries: 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.  Using 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.    While 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).   - **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  - **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.  - **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. 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.  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.  On 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.  The 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.   [1] Chen et al., A Simple Framework for Contrastive Learning of Visual Representations, 2021.  [2] Wang and Isola., Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere, 2020.  [3] Saunshi et al., A theoretical analysis of contrastive unsupervised representation learning, 2019.  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.
abstractText: 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 resort 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 different samples from the same class could be bridged together with aggressive data augmentations, thus simply aligning the positive samples (augmented views of the same sample) could make contrastive learning cluster intra-class samples together. We also show that our theory aligns well with existing contrastive methods on both synthetic and real-world datasets. Our work suggests an alternative understanding of contrastive learning: the role of aligning positive samples is more like a surrogate task than an ultimate goal, and it is the overlapping augmented views (i.e., the chaos) that create a ladder for contrastive learning to gradually learn class-separated representations.
references.authors: Jordan T Ash Surbhi Goel Akshay Krishnamurthy Dipendra Misra
references.title: Investigating the role of negatives in contrastive representation learning
references.venue: arXiv preprint arXiv:2106.09943,
references.authors: Ivan Budimir Sever S Dragomir Josep Pecaric
references.title: Further reverse results for jensen’s discrete inequality and applications in information theory
references.venue: RGMIA research report collection,
references.authors: Ting Chen Simon Kornblith Mohammad Norouzi Geoffrey Hinton
references.title: A simple framework for contrastive learning of visual representations
references.authors: Ting Chen Simon Kornblith Kevin Swersky Mohammad Norouzi Geoffrey Hinton
references.title: Big selfsupervised models are strong semi-supervised learners
references.venue: arXiv preprint arXiv:2006.10029,
references.authors: Xinlei Chen Kaiming He
references.title: Exploring simple siamese representation learning
references.venue: arXiv preprint arXiv:2011.10566,
references.authors: Xinlei Chen Saining Xie Kaiming He
references.title: An empirical study of training self-supervised vision transformers
references.venue: arXiv preprint arXiv:2104.02057,
references.authors: Gong Cheng Peicheng Zhou Junwei Han
references.title: RIFD-CNN: Rotation-invariant and fisher discriminative convolutional neural networks for object detection
references.authors: 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 Michal Valko
references.title: Bootstrap your own latent: A new approach to self-supervised learning
references.venue: NeurIPS,
references.authors: Jeff Z HaoChen Colin Wei Adrien Gaidon Tengyu Ma
references.title: Provable guarantees for self-supervised deep learning with spectral contrastive loss
references.venue: NeurIPS,
references.authors: Kaiming He Haoqi Fan Yuxin Wu Saining Xie Ross Girshick
references.title: Momentum contrast for unsupervised visual representation learning
references.authors: Martin Heusel Hubert Ramsauer Thomas Unterthiner Bernhard Nessler Sepp Hochreiter
references.title: Gans trained by a two time-scale update rule converge to a local nash equilibrium
references.venue: NeurIPS,
references.authors: R Devon Hjelm Alex Fedorov Samuel Lavoie-Marchildon Karan Grewal Phil Bachman Adam Trischler Yoshua Bengio
references.title: Learning deep representations by mutual information estimation and maximization
references.authors: Jason D Lee Qi Lei Nikunj Saunshi Jiacheng Zhuo
references.title: Predicting what you already know helps: Provable self-supervised learning
references.venue: arXiv preprint arXiv:2008.01064,
references.authors: Ibrahim Merad Yiyang Yu Emmanuel Bacry Stéphane
references.title: Gaı̈ffas. About contrastive unsupervised representation learning for classification and its convergence
references.venue: arXiv preprint arXiv:2012.01064,
references.authors: Kento Nozawa Issei Sato
references.title: Understanding negative samples in instance discriminative selfsupervised representation learning
references.venue: NeurIPS,
references.authors: Aaron van den Oord Yazhe Li Oriol Vinyals
references.title: Representation learning with contrastive predictive coding
references.venue: arXiv preprint arXiv:1807.03748,
references.authors: Mathew D. Penrose
references.title: A Strong Law for the Longest Edge of the Minimal Spanning Tree
references.venue: The Annals of Probability,
references.authors: Allon G Percus Olivier C Martin
references.title: Scaling universalities of kth-nearest neighbor distances on closed manifolds
references.venue: Advances in Applied Mathematics,
references.authors: Ben Poole Sherjil Ozair Aaron Van Den Oord Alex Alemi George Tucker
references.title: On variational bounds of mutual information
references.authors: Colorado J Reed Sean Metzger Aravind Srinivas Trevor Darrell Kurt Keutzer
references.title: Selfaugment: Automatic augmentation policies for self-supervised learning
references.authors: Nikunj Saunshi Orestis Plevrakis Sanjeev Arora Mikhail Khodak Hrishikesh Khandeparkar
references.title: A theoretical analysis of contrastive unsupervised representation learning
references.authors: Jiaming Song Stefano Ermon
references.title: Understanding the limitations of variational mutual information estimators
references.venue: In ICLR,
references.authors: Yonglong Tian Chen Sun Ben Poole Dilip Krishnan Cordelia Schmid Phillip Isola
references.title: What makes for good views for contrastive learning
references.venue: NeurIPS,
references.authors: Christopher Tosh Akshay Krishnamurthy Daniel Hsu
references.title: Contrastive estimation reveals topic posterior information to linear models
references.venue: arXiv preprint arXiv:2003.02234,
references.authors: Christopher Tosh Akshay Krishnamurthy Daniel Hsu
references.title: Contrastive learning, multi-view redundancy, and linear models
references.venue: In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research,
references.authors: Yao-Hung Hubert Tsai Yue Wu Ruslan Salakhutdinov Louis-Philippe Morency
references.title: Selfsupervised learning from a multi-view perspective
references.venue: In ICLR,
references.authors: Tongzhou Wang Phillip Isola
references.title: Understanding contrastive representation learning through alignment and uniformity on the hypersphere, 2020
references.authors: Yichong Xu Tianjun Xiao Jiaxing Zhang Kuiyuan Yang Zheng Zhang
references.title: Scale-invariant convolutional neural networks
references.venue: arXiv preprint arXiv:1411.6369,
references.title: 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
references.venue: PROOF OF THEOREM
sections.heading: 1 INTRODUCTION
sections.text: Contrastive Learning (CL) emerges to be a promising paradigm for learning data representations without labeled data (Oord et al., 2018; Hjelm et al., 2019). Recently, it has achieved impressive results and gradually closed the gap between supervised and unsupervised learning, hopefully leading to a new era that resolves the hunger for labeled data in the deep learning field (He et al., 2020; Chen et al., 2020b). 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.k.a. negative samples). Intuitively, it is an instance discrimination 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 1(a), CL representations are also class-separated. Therefore, understanding how the pretraining (CL) task and the downstream (classification) task interact plays a central role in both theoretical understandings and practical designings of contrastive methods.
  Previously, Saunshi et al. (2019) and Lee et al. (2020) have tried to establish guarantees on the classification 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 class y. However, this is hardly practical as the augmented views are still strongly input-dependent (see Figure 1(b)). In fact, if the conditional independence is satisfied, the unsupervised task will become as informative as the supervised task, making this discussion 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, we need to reexamine 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 as 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 on the observation that contrastive learning usually adopts much more aggressive data augmentations than that in supervised learning (He et al., 2020; Chen et al., 2020a). As shown in Figure 1(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 connections between different intra-class images through aggressively augmented views of them. Thus, the alignment of positive samples will also cluster all the intraclass samples together, and lead to class-separated representations. From our perspective, the role of data augmentation is to create a certain degree of “chaos” between intra-class samples, and the role of contrastive loss is to “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. Specifically, we derive the upper and lower bounds for its downstream performance and show how the two will asymptotically converge with our assumptions on the support overlapping effect of data augmentations. 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 support overlapping effect of data augmentations. Compared to existing theories on contrastive learning, ours can provide guidance to the practical designing of contrastive methods and evaluation metrics.
  • We establish general guarantees (both upper and lower bounds) for the downstream performance 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 a new unsupervised evaluation metric for contrastive learning named ARC and show that it aligns well with downstream performance on real-world datasets.
sections.heading: 2 RELATED WORK
sections.text: Contrastive Learning in Practice. Contrastive self-supervised learning originates from a mutual information perspective of representation learning (Oord et al., 2018; Hjelm et al., 2019), and soon becomes a general learning paradigm that contrasts between positive and negative pairs (He et 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., 2021), and outperforms supervised 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 certain training techniques (Grill et 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 inputs and representations, but these estimators are shown to have poor bias-variance trade-offs (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. (2020) further link the reconstruction-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) conditionally independent. Besides, there are several other perspectives for analyzing contrastive learning, e.g., information-theoretical perspective (Tian et al., 2020; Tsai et al., 2021; Tosh et al., 2020; 2021). Recently, similar to our analysis, HaoChen 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 matrix 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 a 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.
sections.heading: 3 LIMITATIONS OF PREVIOUS UNDERSTANDINGS
sections.heading: 3.1 PROBLEM SETUP
sections.text: We begin by introducing the basic notations and common practice of contrastive learning in the image classification task. In general, it has two stages, unsupervised pretraining, and supervised finetuning. In the first stage, with N unlabeled samples Du = {xi}Ni=1, we pretrain an encoder mapping from the d-dimensonal input space to a unit hypersphere f ∈ F : Rd → Sm−1 in the mdimensional space. In the second stage, we evaluate the learned representations z with the labeled data Dl = {(xi, yi)} where labels yi ∈ {1, . . . ,K}. Specifically, we fix the encoder and learn a linear classification head g : Rm → RK on top from D̃l = {(z, y)|z = f(x) ∈ Rm}.
  Contrastive Pretraining. Taking a training example x ∈ Du, we draw its positive sample x+ = t(x) by applying a random data augmentation t ∼ T , and draw M randomly augmented samples {x−i }Mi=1 from Du as its negative samples. Then, we can learn the encoder f with the widely used InfoNCE loss (Oord et al., 2018)
  LNCE(f) =Ep(x,x+)E{p(x−i )}
  [ − log exp(f(x)
  >f(x+))∑M i=1 exp(f(x) >f(x−i ))
  ]
  =Ep(x) [ −Ep(x+|x)f(x)>f(x+) + E{p(x−i )} log M∑ i=1 exp(f(x)>f(x−i )) ] .
  (1)
  Let p(x) be the data distribution, p(x, x+) be the joint distribution of positive pairs, and we simply assume p(x, x+) = p(x+, x) and p(x) = ∫ p(x, x+)dx+,∀ x ∈ Rd following Wang & Isola (2020).
  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 (x, y) ∈ Dl
  LCE(f, g) = Ep(x,y)
  [ − log exp ( f(x)>wy )∑K i=1 exp (f(x) >wi) ] , (2)
  with a linear classifier g(z) = Wz where W = [w1, w2, . . . , wK ].
sections.heading: 3.2 EXISTING THEORETICAL ASSUMPTIONS AND THEIR LIMITATIONS
sections.text: 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 (Eq. 1) as they are aiming at the following two properties: 1) alignment (the 1st term): positive samples x, x+ has similar features, i.e., f(x) ≈ f(x+); 2) uniformity (the 2nd term): features are roughly uniformly distributed in the unit hypersphere Sm−1. 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. Proposition 3.1 (Class-uniform features also minimize the InfoNCE loss). For N training examples of K classes, consider the case when features {f(xi)}Ni=1 are randomly distributed in Sm−1 with maximal uniformity (i.e., , minimizing the 2nd term of Eq. 1) while also satisfying ∀xi, x+i ∼ p(x, x+), f(xi) = f(x + i ). Because we have these two properties, 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.
  This indicates that the instance discrimination task (alignment + uniformity) alone cannot guarantee the learning of class-discriminative 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(x, x+|y) = p(x|y)p(x+|y). However, this assumption is too strong as it is hardly practical. As shown in Figure 1(b), augmented views from the same class are not actually independent as views from the same sample are more alike than that from other samples.
sections.heading: 4 A NEW THEORY FOR CONTRASTIVE LEARNING
sections.text: The analysis above motivates us to find a 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).
sections.heading: 4.1 GAP BETWEEN CONTRASTIVE LEARNING AND DOWNSTREAM CLASSIFICATION
sections.text: We start with an assumption on the label consistency between positive samples, that is, any pair of positive samples (x, x+) should belong to the same class. Assumption 4.1 (Label Consistency). ∀ x, x+ ∼ p(x, x+), we assume the labels are deterministic (one-hot) and consistent: p(y|x) = p(y|x+). This is a natural and minimal assumption that is likely to hold in practice. As shown in Figure 1(b), the widely adopted augmentations in contrastive learning (Chen et 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 unsupervised and supervised learning risks. We first introduce the mean CE loss, LµCE(f) = Ep(x,y) [ − log exp(f(x)
  >µy)∑K i=1 exp(f(x) >µi)
  ] , where we use the classwise mean representation µk =
  Ep(x|y=k)[f(x)] as the weight wk of the classifier g. It is easy to see that the mean CE loss upper bounds the CE loss, i.e., LµCE(f) ≥ ming LCE(f, 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). Theorem 4.2 (Guarantees for general encoders). If Assumption 4.1 holds, then, for any f ∈ F , its downstream classification risk LµCE(f) can be bounded by the contrastive learning risk LNCE(f)
  LNCE(f)− √ Var(f(x) | y)− 1 2 · m∑ j=1 √ Var(fj(x) | y)−O ( M−1/2 ) ≤ LµCE(f) + log(M/K) ≤ LNCE(f) + √ Var(f(x)|y) +O ( M−1/2 ) ,
  (3)
sections.heading: Contrastive
sections.heading: Learning
sections.text: where log(M/K) is a constant 1, O
  (
  M−1/2
  )
  denotes the order of the approximation error
  by using M negative samples, fj(x) denotes the j-th coordinate of f(x), and Var(f(x)|y) = Ep(y) [ Ep(x|y)‖f(x)− Ep(x|y)f(x)‖2 ] denotes the conditional variance.
  Remark. Our generalization bounds extend the analysis in Saunshi et al. (2019) in several aspects: 1) we do not require the assumption on conditional independence; 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 terms2 that are incompressible in Saunshi et al. (2019) 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 et al., 2020a). While for our bounds, increasing M indeed leads to a lower approximation error and helps close the gap. We note that several recent works have also been devoted to resolve this “large-M” problem (Ash et al., 2021; Merad et al., 2020). Nevertheless, their analysis also requires the conditional independence assumption as in Saunshi et al. (2019), while we show this problem can be resolved in general cases even without conditional independence. Nozawa & Sato (2021) also establish bounds for the InfoNCE loss, but their bounds have incompressible class collision terms while ours do not. Notably, the theorem above shows that Assumption 4.1 alone is still insufficient to guarantee good downstream performance. As there are two intra-variance terms in the upper and lower bounds, Var(f(x)|y) and Var(fj(x)|y). The contrastive learning might still have inferior performance with intra-class variance as in Proposition 3.1. In the next part, we will present a new understanding of how contrastive learning could control this variance term.
sections.heading: 4.2 CLOSING THE GAP WITH INTRA-CLASS CONNECTIVITY
sections.text: The theorem above motivates us to study how contrastive learning could effectively control its intraclass variance and learn class-separated features. Here, we propose a new understanding of this clustering ability through a dissection of the augmented views. In particular, we notice that although samples are different from each other, applying aggressive augmentations like that in SimCLR (Chen et al., 2020a) can largely make them more alike. For example, in Figure 1(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-class samples could be aligned together if they have overlapping 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 G = (V, E) where V = (v1, v2, . . . , vN ) is a set of vertices and E ⊆ V × V is a set of edges. A path is a sequence of edges that joins a sequence of vertices, e.g., vi1 − vi2 − · · · − vik . We say that two vertices v and u are connected if G contains a
  1log(M/K) could be absorbed in the loss functions by replacing sum with mean in InfoNCE and CE. 2Error terms introduced because there are samples from the same class as x in the negative samples {x−i }.
  path from v to 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-graph vertices are not connected.
  To begin with, we define the concept of T -connectivity of sample pairs, which describes whether two samples could be connected via the support overlapping of their augmented views. Definition 4.3 (T -connectivity). Given a collection of augmentations T = {t | t : Rd → Rd}, we say that two different images xi, xj ∈ Rd are T -connected if they have overlapping views: supp(p(x+i |xi)) ⋂ supp(p(x+j |xj)) 6= ∅, or equivalently, ∃ ti, tj ∈ T such that ti(xi) = tj(xj).
  Then, we can define an augmentation graph of all training samples in terms of their T -connectivity. Definition 4.4 (Augmentation Graph). Given a set ofN samplesD = {xi}Ni=1 and an augmentation set T = {t | t : Rd → Rd}, we can define an augmentation graph G(D, T ) = (V, E) as
  • we take the N natural samples as the vertices of the graph, i.e., V = {xi}Ni=1;
  • there exists an edge eij between two vertices xi and xj if they are T -connected.
  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 Figure 3. Assumption 4.5 (Intra-class Connectivity). Given a training set Du, there exists an appropriate augmentation set T such that the augmentation graph G(Du, T ) is class-wise connected, i.e., ∀ k ∈ {1, . . . ,K}, the subgraph Gk (graph G restricted to vertices in class k) is connected.
  Comparing to Saunshi et al. (2019) and Lee et al. (2020) that require (nearly) conditional independence p(x, x+|y) = p(x|y)p(x+|y), ours only requires the connectivity of intra-class samples as in Figure 1(b), and does not need them to be conditionally independent.
  To make this analysis simpler, we need another assumption on the alignment term that by minimizing the InfoNCE loss we can align the positive samples perfectly (empirical evidence in Appendix E). Assumption 4.6 (Perfect Alignment). At the minimizer f? of the InfoNCE loss, we can achieve perfect alignment, i.e., ∀ x, x+ ∼ p(x, x+), f?(x) = f?(x+). Proposition 4.7. Under Assumptions 4.5 & 4.6, by minimizing the InfoNCE loss we can conclude that the conditional variance term vanishes at the minimizer f?, i.e.,
  Var(f?(x) | y) = Var(f?j (x) | y) = 0, ∀j ∈ {1, 2, . . . ,m}. (4)
  Intuitively, for samples in each class k, if the corresponding subgraph Gk is connected, there exists a path connecting every intra-class pairs (xi, xj), as shown in Figure 3. Consequently, aligning the positive pairs will also align all samples on the path, and eventually align xi and xj . 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 support overlap (Assumption 4.1), inter-class samples can be well separated with the uniformity term. As a 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.1, 4.5 & 4.6 hold and f is L-smooth, then, for the minimizer f? = arg minLNCE(f), its classification risk can be upper and lower bounded by its contrastive risk as
  LNCE(f?)−O ( M−1/2 ) ≤ LµCE(f ?) + log(M/K) ≤ LNCE(f?) +O ( M−1/2 ) . (5)
  We note that different to previous bounds that hold for any f ∈ F 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. Besides, we also provide a generalized version of this guarantee under less restrictive setting (weak alignment) in Appendix A.
sections.heading: 4.3 DISCUSSIONS
sections.text: Our analysis above suggests a new understanding of the role of data augmentations in contrastive learning. Conventionally, the success of contrastive learning is usually contributed to learning invariance w.r.t. various data augmentations by matching positive examples. However, as shown in
  Proposition 3.1, matching positive pairs is theoretically inadequate to learn useful features. Indeed, assume that we have an ideal encoder that possesses invariance a priori as desired, like invariance to translation (CNNs), rotation (Cheng et al., 2016), and scaling (Xu et al., 2014), do we obtain class-discriminative features simply by random initialization? NO, since these low-level properties are independent of the high-level class information that we want to learn. Thus, the reason why contrastive learning works cannot simply be contributed to the invariance learning principle.
  We instead believe that the role of data augmentation is to create a certain degree of “chaos” between different intra-class samples (Figure 1(b)) such that they become more alike (or formally, T -connected). In this way, the chaos serves as a “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 overlapping positive samples, as shown in Figure 3. Therefore, from our perspective, instance discrimination by contrastive learning is actually a surrogate for the classification task, and the surrogate can complete its misson when the ladder of chaos is complete (or formally, when intra-class connectivity holds).
sections.heading: 5 ON THE INFLUENCE OF AUGMENTATION STRENGTH
sections.text: We have shown that with appropriate augmentations, we can derive guarantees on downstream performance. However, in practice, as illustrated in Figure 4, there could be cases where augmentations 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 provide a quantitative analysis of how different strength of data augmentation will affect the final performance both theoretically and empirically.
sections.heading: 5.1 CHARACTERIZATION ON RANDOM AUGMENTATION GRAPH
sections.text: In practice, there are various data augmentation types that are hard to 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 ck on a hypersphere Sd. We then augment each sample xi 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 by r) will affect the connectivity of the augmentation as a function of the number of samples N , the position of the cluster centers ck and input dimensions d. In particular, the minimal r for the graph to be connected decreases as N increases, so large-scale datasets can bring better connectivity. Meanwhile, the required r also increases as d increases, so we need more samples or stronger augmentations for large-size inputs. Here, we show our simulation results by applying contrastive learning to the problem above. From Figure 5, we can see that when r = 0 (no augmentation), the features are mixed together and hardly (linearly) separable, which corresponds to the under-overlapping case in Figure 4. As we increase r from 0 to 0.1, the features become more and more discriminative. And when r is too large (r = 1.5), the inter-class features become mixed and inseparable again (overly overlapping). In Appendix B.2, we provide visualization results of the augmentation graphs, which also align well with our analysis. Overall, our theoretical and empirical discussions verify our theory that intra-class support overlapping with a proper amount of data augmentation is crucial for contrastive learning to work well.
sections.heading: 5.2 NEW SURROGATE METRICS FOR THE SUPPORT OVERLAPPING
sections.text: From our theory and analysis above, we see that the support overlapping between intra-class samples indeed matters from contrastive learning to generalize better. Inspired by this, we propose the Confusion Ratio metric as a measure of the degree of support overlapping. Specifically, for an unlabeled datasetDu withN samples, we randomly augment each raw sample xi ∈ Du for C times, and get an augmented set D̃u = {xij , i ∈ [N ], j ∈ [C]}. Then, for each xip ∈ D̃u that is an augmented view of xi ∈ Du, denoting its k-nearest neighbors in D̃u in the feature space of f asNk(xip, f) and other augmented views from the same image as C(xip) = {xij , j 6= p}, we can define its Confusion Ratio (CR) as the ratio of augmented views from the same raw sample in its k-nearest neighbors,
  CRk(xij , f) = #[Nk(xip, f)
  ⋂ C(xip)]
  #Nk(xip, f) . (6)
  We also define its average as Average Confusion Ratio (ACR):
  ACRk(f) = Exij∼D̃u CRk(xij,f ). (7)
  When support overlapping happens, the nearest neighbors could be augmented views from a different sample, leading to a lower ACR. Thus, ACR measures the degree of support overlapping, and a lower ACR indicates a higher degree of support overlapping. Here we take k = 1 by default.
  Here, to measure the augmentation strength in real-world datasets, following the common practice (Chen et al., 2020a), we adopt the RandomResizedCrop operator with scale range [a, b] for data 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 B.1). As shown in Figure 6(a), ACR (support overlapping) indeed decreases with the strength of data augmentations, and only a 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 6(b) & 6(c). We can notice that for small augmentations, the initial ACR is large, and it rapidly grows to the optimum and seldom changes while training, which leads to poor test accuracy. Instead, with proper augmentations, the initial ACR is lower, and it gradually increases to nearly one and obtains good accuracy. This is also consistent with our theory that we need a certain amount of support overlapping for contrative learning to work well. At the beginning, this will lead to a lower ACR, but as training continues, better alignment (higher ACR) will help bring up the test accuracy.
  Average Relative Confusion (ARC). In the discussion above, we notice that although ACR itself does not indicate the test accuracy, the relative change of ACR before and after training can be used as such an indicator. A large change of ACR means a large change of support overlapping, which indicates that the contrastive loss can actually cluster intra-class samples together through overlapped views. Based on this observation, we propose Average Relative Confusion (ARC) as
  ARCk = ACRk(ffinal)
  ACRk(finit) , (8)
  a ratio of ACR with the initialized model finit and the final model ffinal after contrastive learning. A higher ARC indicates that the contrastive learning process faces a harder task (support overlapping) at the beginning (lower initial ACR), while successfully clustering intra-class samples with good alignment of positive samples at the end (higher final ACR). Therefore, a higher ARC should correspond to higher downstream accuracy.
  As shown in Figure 7 & 8, as augmentations become stronger, ARC scores 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 support overlapping. Meanwhile, as the calculation of ARC only involves unsupervised data, it could serve as a good surrogate metric for evaluating contrastive learning without using labeled data. Compared to previous evaluation methods like linear classification (Eq. 2), our ARC metric is more preferable as 1) it is theoretically motivated; 2) it does not need labeled data; 3) it does not need to learn additional modules like linear classifiers or rotation tasks (Reed et al., 2021). More experimental details can be found in Appendix F.
sections.heading: 6 CONCLUSION
sections.text: 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 support overlapping between intra-class samples, and as a result, by aligning positive samples, we can also cluster inter-class samples together. Based on this insight, we develop a new 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, we also develop a new surrogate metric for evaluating contrastive learning without labels and show that it aligns well with downstream performance. Overall, we believe that we pave a new way for understanding contrastive learning with insights on the designing of contrastive methods and evaluation metrics.
sections.heading: A GENERALIZED GUARANTEES UNDER WEAK ALIGNMENT
sections.text: In Section 4.2, we have shown that with perfect alignment (Assumption 4.6), the variance terms in the bounds of Theorem 4.2 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, we typically cannot achieve the exact minimizer, i.e., a perfect degree of alignment. This motivates us to consider a less restrictive setting, namely the ε-weak alignment assumption, where the alignment error could be as large as ε.
  Definition A.1 (Weak Alignment). A mapping f satisfies ε-weak alignment if ∀ x, x+ ∼ p(x, x+), ‖f(x)− f(x+)‖ ≤ ε.
  For any ε-weak alignment f ∈ F , we have the following bounds on its downstream risk. Theorem A.2 (Guarantees under weak alignment). If Assumption 4.1, 4.5 hold, then ∀f ∈ F satisfying ε-weak alignment, its classification risk can be upper and lower bounded by its contrastive risk as
  LNCE(f)− (1 + √ m
  2 ) √ Dε−O
  ( M−1/2 ) ≤LµCE(f) + log(M/K) ≤ LNCE(f) + √ Dε+O ( M−1/2 ) ,
  (9)
  where D denotes the maximal diameter of the intra-class augmentation graphs {Gk, k = 1, . . . ,K} and m denotes the output dimension of the encoder f .
  In this way, we extend the guarantees developed for optimal encoders (Theorem 4.8) to even nonminimizers f ∈ F as long as it could align the positive samples within error ε.
  Empirical Verification. Besides the alignment error, we could notice this relaxation also introduces the dependence on an additional parameterD, the maximal diameter of the intra-class augmentation graphs. As shown in Figure 9, when the augmentation is very weak, the intra-class graph is not connected and the diameter is∞. Then, by applying stronger augmentations,D will become smaller and smaller, and finally converge to 1 (fully connected). Besides, increasing the number of samples, 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 a relatively small value with properly chosen augmentations. As a result, with a bounded diameter D, a small alignment error ε will guarantee a small generalization gap between the upstream and downstream tasks. This generalizes Theorem 4.8 by quantifying the generalization gap under weak alignment.
  Proof. Consider any pair of samples (x, x′) from the same class y, and the positive sample of x as x+. As intra-class connectivity holds, x and x′ are connected, and the maximal length of the path from x to x′ is D. Therefore, under the ε-weak alignment that
  ∀x, x+ ∼ p(x, x+), ‖f(x)− f(x+)‖2 ≤ ε2, (10)
  we can bound the representation distance between x and x′ by the triangular inequality
  ‖f(x)− f(x′)‖2≤D sup p(x,x+|y∼p(x,x+) ‖f(x)− f(x+)‖2≤Dε2 (11)
  With the inequality above, we can bound the variance terms in Theorem 4.2. In particular, the conditional variance can be bounded as
  Var(f(x) | y) =Ep(y)Ep(x|y)‖f(x)− Ex′f(x′)‖2
  =Ep(y)Ep(x|y)‖Ex′f(x)− f(x′)‖2
  ≤Ep(y)Ep(x|y)Ep(x′|y)‖f(x)− f(x′)‖2
  ≤Ep(y) max x,x′∼p(x|y)
  ‖f(x)− f(x′)‖2
  (1) ≤Ep(y)Dε2 = Dε2,
  (12)
  where (1) follows Eq. 11. Similarly, we can also bound the element-wise variance terms,
  m∑ j=1 √ Var(fj(x) | y) (1) ≤ √√√√m m∑ j=1 Var(fj(x)|y) (2) = √ mVar(f(x)|y) (3) ≤ √ mDε2, (13)
  where (1) employs the Cauchy–Schwarz inequality, (2) holds because m∑ j=1 Var(fj(x)|y)
  = m∑ j=1 Ep(y)Ep(x|y)(fj(x)− Ep(x′|y)fj(x′))2
  =Ep(y)Ep(x|y) m∑ j=1 (fj(x)− Ex′fj(x′))2
  =Ep(y)Ep(x|y)‖f(x)− Ex′f(x′)‖2
  =Var(f(x)|y),
  (14)
  and (3) follows Eq. 12. At last, we can bound the variance items in Theorem 4.2 with Eq. 12 & 13, and arrive at the desired bounds
  LNCE(f)− (1 + √ m
  2 ) √ Dε−O
  ( M−1/2 ) ≤LµCE(f) + log(M/K) ≤ LNCE(f) + √ Dε+O ( M−1/2 ) ,
  which conclude our proof.
sections.heading: B ADDITIONAL EMPIRICAL EVIDENCE
sections.heading: B.1 FURTHER EVALUATION OF AUGMENTATIONS
sections.text: 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 a list of different kinds of augmentations. Therefore, in this part, we further study the effect of other types of data augmentations, and we show that our ARC metric is also effective for evaluating not only other kinds of data augmentations, but also their composed ones.
  Comparing different kinds of augmentations. We begin by comparing the four kinds of data augmentations adopted in SimCLR (Chen et al., 2020a): RandomResizedCrop, ColorJitter, Grayscale, etc. For a fair comparison, we apply each one alone for contrastive learning, and evaluate both the
  downstream accuracy and ARC. From Figure 12, we can conclude that among the six kinds of augmentations, RandomResizedCrop 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 can also see 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, as another kind of augmentation for the study of different augmentation strength. Specifically, we study the four parameters of brightness, contrast, saturation, and hue, where a 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 10). As shown in Figure 11, there is also a reverse-U curve like that in RandomResizedCrop, and the sweet spot is usually achieved with 0.8, which corresponds to the default of choice in 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.
  Comparing composed augmentations. In the above discussion, we focus on the effect of a single kind of augmentations. Here, we show that our ARC metric is still effective for evaluating the composition of different augmentations. Notably, it is hard to define a metric of augmentation
  strength in this case, as the effect of 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 a model trained with randomly selected parameters of RandomResizedCrop and ColorJitter. As shown in Figure 12, 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 as well as their compositions in an unsupervised fashion.
  B.2 VISUALIZATION OF AUGMENTATION GRAPH
  For a more intuitive and practical understanding of our overlapping 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).
  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 13 with different colors. It shows that when there is no augmentation, i.e., r = 0, each sample is a connected component alone, and the number of connected components is the same as 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 connectivity and label consistency, respectively. Therefore, this is the perfect overlapping as desired, and indeed, as shown in Figure 5.1, contrastive learning on it 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 overlapping theory.
  Real-world data. For the ease of analysis, our overlapping theory adopts a simplified scenario by assuming label consistency (Assumption 4.1) 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. Nevertheless, as shown
  in the augmentation graphs of CIFAR-10 (Figure 14), 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 considering 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 exact conditions. Besides, we also have similar conclusions for the under-overlapping and overly-overlapping scenarios: 1) the lack of enough augmentations produces only a few edges in the augmentation graph, as a result, even though all edges are intra-class edges, the downstream performance is still poor (25% test accuracy); 2) too strong augmentations instead produce too many inter-class edges (87.6%), which laso leads to poor downstream accuracy (29%). This highlights that our assumptions on label consistency and intra-class connectivity are indeed effective guidelines for the designing of contrastive methods.
sections.heading: C OMITTED PROOFS
sections.heading: C.1 PROOF OF PROPOSITION 3.1
sections.text: Proposition C.1 (Class-uniform features also minimize the InfoNCE loss). ForN training examples of K classes, consider the case when features {f(xi)}Ni=1 are randomly distributed in Sm−1 with maximal uniformity while also satisfying ∀xi, x+i ∼ p(x, x+), f(xi) = f(x + i ). 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 whenN is large enough.
  Proof. We only need to give a counterexample that satisfy the desired classification accuracy. We consider the case when there is no T -connectivity between any pair of samples from {xi}Ni=1, which is easily achieved if we adopt a small enough data augmentation. In this scenario, the perfect alignment of positive samples (xi, x+i ) could have no effect on the other samples. Therefore, when the features {f(xi)}Ni=1 are uniformly distributed in Sm−1, according to the law of large number, for any measurable set U ∈ Sm−1, when N is large enough, there will be almost equal size of features from each class in U . Consequently, any classifier g that classifies U to class k will only have 1/K accuracy asymptotically.
sections.heading: C.2 PROOF OF THEOREM 4.2
sections.text: We will prove the upper and lower bounds separately as follows.
sections.heading: C.2.1 THE UPPER BOUND
sections.text: We first provide the upper bound of the approximation error of the following Monte Carlo estimate.
  Lemma C.2. For LSE := logEp(z) exp(f(x)>g(z)), we denote its (biased) Monte Carlo estimate with M random samples zi ∼ p(z), i = 1, . . . ,M as L̂SEM = log 1M ∑M i=1 exp(f(x)
  >g(zi)). Then the approximation error A(M) can be upper bounded in expectation as
  A(M) := Ep(x,zi)|L̂SE(M)− LSE| ≤ O(M −1/2). (15)
  We can see that the approximation error converges to zero in the order of 1/M−1/2.
  Proof. First, we have
  Ep(x,zi)
  [ log 1
  M M∑ i=1 exp(f(x)>g(zi))− logEp(zi) exp(f(x) >g(zi))
  ]
  ≤eEp(x,zi)
  [ 1
  M M∑ i=1 exp(f(x)>g(zi))− Ep(zi) exp(f(x) >g(zi))
  ] = O(M−1/2),
  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 |f(x)>g(zi)| ≤ 1. And the second inequality follows the Berry-Esseen Theorem given the bounded support of exp(f(x)>g(zi)) as following: for i.i.d random variables Yi with bounded support supp(Y ) ⊂ [−α, α], zero mean and bounded variance σ2Y < α2, we have:
  E [∣∣∣∣∣ 1M M∑ i=1 Yi ∣∣∣∣∣ ] = σy√ M E [∣∣∣∣∣ 1√Mσy M∑ i=1 Yi ∣∣∣∣∣ ]
  = σY√ M
  ∫ α√M σY
  0
  P [∣∣∣∣∣ 1√MσY M∑ i=1 Yi ∣∣∣∣∣ > x ] dx
  ≤ σY√ M
  ∫ α√M σY
  0
  P[|N (0, 1)| > x] + Cα√ M dx
  ≤ σY√ M ( αCα σY + ∫ ∞ 0 P[|N (0, 1)| > x]dx )
  ≤ Cα√ M + α√ M E[|N (0, 1)|] = O(M−1/2)
  where the constant Cα only depends on α. Here, we set Yi = exp(f(x)>g(zi)) − Ep(zi) exp(f(x)>g(zi)). As |f(x)>g(zi)| ≤ 1, |Yi| ≤ 2e. Yi has zero mean and bounded variance (2e)2.
  Theorem C.3. For each f ∈ F , the mean CE loss can be upper bounded by the InfoNCE loss:
  LµCE(x, y; f) ≤ LNCE(x; f)− log(M/K) + √ Var(f(x) | y) +A(M), (16)
  where Var(f(x)|y) = Ep(y) [ Ep(x|y)‖f(x)− Ep(x|y)f(x)‖2 ] denotes the conditional variance.
  Proof. Denote p(x, x+, y) as the joint distribution of the positive pairs x, x+ and the label y. Denote the M independently negative smaples as {x−i }Mi=1. According to Assumption 4.1, x+ and x here has the same label y. Denote µy as the center of features of class y, y = 1, . . . ,K. Then we have
  the following lower bounds of the InfoNCE loss,
  LNCE(f) = −Ep(x,x+)f(x)>f(x+) + Ep(x)Ep(x−i ) M∑ i=1 exp(f(x)>f(x−i ))
  =− Ep(x,x+)f(x)>f(x+) + Ep(x)Ep(x−i ) log 1
  M M∑ i=1 exp(f(x)>f(x−i )) + logM
  (1) ≥ − Ep(x,x+)f(x)>f(x+) + Ep(x) log 1
  M Ep(x−i ) M∑ i=1 exp(f(x)>f(x−i ))−A(M) + logM
  =− Ep(x,x+)f(x)>f(x+) + Ep(x) logEp(x−) exp(f(x)>f(x−))−A(M) + logM =− Ep(x,x+,y)f(x)>f(x+) + Ep(x) logEp(y−)Ep(x−|y−) exp(f(x)>f(x−))−A(M) + logM
  (2) ≥ − Ep(x,x+,y)f(x)>f(x+) + Ep(x) logEp(y−) exp(Ep(x−|y−) [ f(x)>f(x−) ] )−A(M) + logM
  =− Ep(x,x+,y)f(x)>(µy + f(x+)− µy) + Ep(x) logEp(y−) exp(Ep(x−|y−) [ f(x)>f(x−) ] )−A(M) + logM
  =− Ep(x,x+,y)[f(x)>µy + f(x)>(f(x+)− µy)] + Ep(x) logEp(y−) exp(f(x)>µy−)−A(M) + logM (3)
  ≥ − Ep(x,x+,y) [ f(x)>µy + ‖(f(x+)− µy)‖ ] + Ep(x) logEp(y−) exp(f(x)>µy−)−A(M) + logM
  (4) ≥ − Ep(x,y)f(x)>µy − √ Ep(x,y)‖f(x)− µy)‖2 + Ep(x) logEp(y−) exp(f(x)>µy−)−A(M) + logM
  =− Ep(x,y)f(x)>µy − √ Var(f(x) | y) + Ep(x) log 1
  K K∑ k=1 exp(f(x)>µk)−A(M) + logM
  =Ep(x,y) [ − f(x)>µy + log K∑ k=1 exp(f(x)>µk) ] − √ Var(f(x) | y)−A(M) + log(M/K)
  =LµCE(f)− √
  Var(f(x) | y)−A(M) + log(M/K), which is equivalent to our desired results. In the proof above, (1) follows Lemma C.2; (2) follows the Jensen’s inequality for the convex function exp(·); (3) follows from the fact that because f(x) ∈ Sm−1, we have
  f(x)>(f(x+)− µy) ≤ (
  f(x+)− µy ‖f(x+)− µy‖
  )> (f(x+)− µy) = ‖f(x+)− µy‖; (17)
  and (4) follows the Cauchy–Schwarz inequality and the fact that because p(x, x+) = p(x+, x) holds, x, x+ have the same marginal distribution.
sections.heading: C.2.2 THE LOWER BOUND
sections.text: In this part, we further show a lower bound on the downstream performance. Lemma C.4 (Budimir et al. (2000) Corollary 3.5 (restated)). Let g : Rm → R be a differentiable convex mapping and z ∈ Rn. Suppose that g is L- smooth with the constant L > 0, i.e., ∀x, y ∈ Rm, ‖∇g(x)−∇g(y)‖ ≤ L‖x− y‖. Then we have
  0 ≤ Ep(z)g(z)− g ( Ep(z)z ) ≤ L [ Ep(z)‖z‖2 − ‖Ep(z)z‖2 ] = L n∑ j=1 Var(z(j)), (18)
  where x(j) denotes the j-th dimension of x.
  With the lemma above, we can derive the lower bound of the downstream performance. Theorem C.5. For any f ∈ F , we have
  LµCE(f) ≥ LNCE(x; f)− √
  Var(f(x) | y)− 1 2 m∑ j=1 Var(fj(x −) | y)−A(M)− log M K , (19)
  where Var(u(x)|y) = Ep(y) [ Ep(x|y)‖u(x)− Ep(x|y)u(x)‖2 ] denotes the conditional variance.
  Proof. Similar to the proof of Theorem C.3, we have
  LµCE(f) = −Ep(x,y)f(x) >µy + Ep(x) log K∑ i=1 exp(f(x)>µi)
  =− Ep(x,y)f(x)>µy + Ep(x) log 1
  K K∑ i=1 exp(f(x)>µi) + logK
  =− Ep(x,y)f(x)>µy + Ep(x) logEp(y−i ) exp(f(x) >µyi) + logK
  (1) ≥ − Ep(x,y)[f(x)>f(x+) + f(x)>(µy − f(x+))] + Ep(x)Ep(y−i ) log 1
  M M∑ i=1 exp(f(x)>µyi)−A(M) + logK
  (2) ≥ − Ep(x,x+)f(x)>f(x+)− Ep(x,y)‖f(x)> − µy‖
  + Ep(x)Ep(y−i ) log 1
  M M∑ i=1 exp(Ep(x−i |y−i )f(x) >f(x−i ))−A(M) + logK
  (3) ≥ − Ep(x,x+)f(x)>f(x+)− √ Var(f(x) | y)
  + Ep(x)Ep(y−i )Ep(x−i |y)
  [ log 1
  M M∑ i=1 exp(f(x)>f(x−))
  ] − 1
  2 m∑ j=1 Var(fj(x −) | y)−A(M) + logK
  =− Ep(x,x+) [ f(x)>f(x+) + Ep(x−i ) log M∑ i=1 exp(f(x)>f(x−)) ]
  − √
  Var(f(x) | y)− 1 2 m∑ j=1 Var(fj(x −) | y)−A(M) + logK − logM
  =LNCE(x; f)− √
  Var(f(x) | y)− 1 2 m∑ j=1 Var(fj(x −) | y)−A(M)− log M K ,
  which is our desired result. In the proof, (1) we adopt a Monte Carlo estimate with M samples from p(y) and bound the approximation error with Lemma C.2; (2) follows the same deduction in Theorem C.3; (3) the first term is derived following the Cauchy–Schwarz 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(x−j ) in our scenario. Because ‖f(X)‖ ≤ 1, we have ∀f(xj1), f(xj2) ∈ Rm, the following bound on the difference of their gradients holds
  ∥∥∥∥∥∂ log[exp(f(x)>f(x − j1 ) + ∑ i 6=j exp(f(x) >f(x−i )))] ∂f(x−j1) − ∂ log[exp(f(x)>f(x−j2) + ∑ i 6=j exp(f(x) >f(x−i )))] ∂f(x−j2) ∥∥∥∥∥ = ∥∥∥∥∥ ( exp(f(x)>f(x−j1)) exp(f(x)>f(x−j1) + ∑ i 6=j exp(f(x − i ))) − exp(f(x)>f(x−j2)) exp(f(x)>f(x−j2) + ∑ i 6=j exp(f(x) >f(x−i ))) ) f(x)
  ∥∥∥∥∥ ≤ ∣∣∣∣∣ ( ∑ i 6=j exp(f(x) >f(x−i )) exp(f(x − j1 ))− ∑ i6=j exp(f(x) >f(x−i )) exp(f(x) >f(x−j2)) (exp(f(x)>f(x−j1)) + ∑ i 6=j exp(f(x) >f(x−i )))(exp(f(x) >f(x−j2)) + ∑ i 6=j exp(f(x) >f(x−i )))
  ∣∣∣∣∣ · ‖f(x)‖ ≤‖f(x)‖ ≤ 1
  2 ∥∥f(x−j1)− f(x−j2)∥∥ So here the logsumexp is L-smooth for L = 12 . Then, we can apply the reversed Jensen’s inequality in Lemma C.4.
sections.heading: C.3 PROOF OF PROPOSITION 4.7
sections.text: Proposition C.6. Under Assumptions 4.5, & 4.6, by minimizing the InfoNCE loss, we can conclude that the conditional variance term vanishes, i.e.,
  Var(f(x) | y) = Var(fj(x) | y) = 0, ∀j ∈ {1, 2, . . . ,m}. (20)
  Proof. Consider any T -connected sample xi, xj . Accoding to the definition of T -connectivity, there exist ti, tj ∈ T such that ti(x) = tj(x). When perfect alignment holds as in Assumption 4.6, we will have f(xi) = f(ti(xi)) and f(xj) = f(tj(xj)). Combining with ti(xi) = tj(xj), we have f(xi) = f(xj). That is, any T -connected pair has the same representation. Then, in the augmentation subgraph Gk that is connected according to Assumption 4.5, there exists a path for any pair of samples x̂i, x̂j ∈ Gk where any two adjacent samples are T -connected. As a result, x̂i and x̂j will also have the same representation by applying T -connectivity recursively. At last, all samples in Gk will have the same representation and the intra-class variance terms vanish.
sections.heading: C.4 PROOF OF THEOREM 4.8
sections.text: Theorem C.7 (Guarantees for the optimal encoder). If Assumption 4.1, 4.5 & 4.6 hold and f is L-smooth, then, for the minimizer f? = arg minLNCE(f), its classification risk can be upper and lower bounded by its contrastive risk as
  LNCE(f?)−O ( M−1/2 ) ≤ LµCE(f ?) + log(M/K) ≤ LNCE(f?) +O ( M−1/2 ) . (21)
  Proof. A direct combination of Theorem 4.2 and 4.7 will give us the above two-sided bounds.
sections.heading: D THEORETICAL CHARACTERIZATION OF AUGMENTATION STRENGTH
sections.text: 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 augmentation strength r, we have the following results.
  (a) Under-overlapping. When 0 ≤ r ≤ r1 = [(d/2)!] 1 d√
  π ( 1d )!( S N−1 ) 1 d [1 − 1/d+1/d
  2
  2(N−1) +
  O( 1(N−1)2 )], where r1 is the minimal distance betweenN samples, all samples (vertices) in the augmentation graph will be isolated. As a result, the learned features could be totally random as in Proposition 3.1. Instead, if r ≥ r1, there are at least two intra-class samples are T -connected and enjoy the same representation.
  (b) Perfect Overlapping. When r ≥ r2 = [(d/2)!] 1 d√ π (N−2+1/d)! (N−2)! ( S N−1 ) 1 d [1 − 1/d+1/d 2 2(N−1) +
  O( 1(N−1)2 )], where r2 is the maximal distance between N samples, all samples in the augmentation graph will be T -connected. As a result, the classwise connectivity in Assumption 4.5 will be guaranteed.
  (c) Over-overlapping. When 0 ≤ r < r3 = 12 mini,j ‖ci−cj‖−1, where r3 is the (asymptotic) minimal distance between samples from different classes, the label consistency is guaranteed. Otherwise, when the augmentation is too large, e.g., r > r3, there will be inter-class support overlap and Assumption 4.1 not longer holds.
  In the theorem above, we show that the proper augmentation strength is a function of the number of samples N and the input dimensions d. In particular, for each x, as N increases, there will be more natural examples and we only need a smaller r to obtain an overlapping sample. Instead, as d increases, due to the curse of dimensionality, there will be less samples within the same distance, thus it requires a larger r.
  Nevertheless, we actually only need the augmentation sub-graph Gk to be connected, instead of being fully connected as in Theorem D.1 (b). While the connectivity is hard to analyze in the finite sample scenario (N <∞), we have the following asymptotic property as N →∞.
  Theorem D.2. For N uniformly distributed samples defined in Rd as above, we denote the minimal augmentation strength needed for connectivity as a function of N : cN = inf{r > 0 : G
  (r) k is connected}, and the minimal augmentation strength needed for avoiding isolated points as a function of N : dN = inf{r > 0 : every vertex at least has a neighbour}. Vu is the volume of unit hyperball. Then we have the following asymptotic result:
  ∀ d ≥ 2, lim N→∞
  ( cdN N2
  logN ) = lim N→∞ ( ddN N2 logN ) = 2 (1− 1/d)S Vu . (22)
  From the theorem we can see that cdN decreases in the order of Θ ( d √ logN N2 ) as N → ∞. 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.
sections.heading: D.1 PROOF OF THEOREM D.1
sections.text: Proof. From definition and notation in section 4. We can construct an augmentation Graph G(D, T ) given N random samples. We define Dk as the distance from a random point to its k-th nearest neighbour. Percus & Martin (1998) discuss Dk in random grpah and give the estimation of that:
  Dk ≈ [(d/2)!]
  1 d
  √ π (k − 1 + 1/d)! (k − 1)! ( S N − 1 ) 1 d [1− 1/d+ 1/d 2 2(N − 1) +O(
  1
  (N − 1)2 )] (23)
  where d is the dimension of hypersphere and N is the number of random points. When r < D1 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.
sections.heading: D.2 PROOF OF THEOREM D.2
sections.text: Proof. Denote cN = inf{ri > 0 : GN (V,E, ri)is connected}. (24)
  With Theorem 1.1 from Penrose (1999) and features are uniformly distributed in the surface of unit hypersphere, Vu denotes to the volume of unit hypershpere
  lim N→∞
  (cdN N2
  logN ) = 2 (1− 1d )S Vu , d ≥ 2 (25)
  ∃N0 when N > N0, and augmentation strength is larger than ( 2(d−1)S logN2N2Vud ) 1 d + 1, the graph is connected,i.e the class is overlapped. Then we want specify the case the class will be depart begin with some concepts in graph theory. The largest nearest-neighbor link: For a give edge distance x and for each i= 1,...,n,let
  deg UN,j = ∑
  1≤j 6=k≤N
  1{‖Uj − Uk‖ ≤ ri} (26)
  to be the degree of the vertex Uj in the random graph GN (V,E, ri), and let δN (ri) = min{deg Um,1(x), ...,deg UN,N (x)} (27)
  be the minimum vertex degree.Define the largest nearest-neighbor link, the smallest edge distance for which each vertex has at least one neighbor
  dN = inf{ri : δN (ri) ≥ 1} (28)
  With Theorem 1.2 from Penrose (1999),
  lim sup N→∞
  (ddN N2
  logN ) = 2 (1− 1d )S Vu , d ≥ 2 (29)
  ∃N ′0 when N > N ′0, and augmentation strength is less than ( 2(d−1)S logN
  2N2Vud )
  1 d − 2, there will be at
  least 1 isolated point which is not connected to any other point,i.e the class is departed. Thus ∃N1 = max(N0, N ′0),when N > N1, if augmentation strength is larger than ( 2(d−1)S logN2N2Vud ) 1 d + 1, the graph is connected, if augmentation strength is less than ( 2(d−1)S logN2N2Vud ) 1 d − 2, there will be at least 1 isolated point.
sections.heading: E ALIGNMENT IN THE TRAINING PROCESS
sections.text: Here, we show the empirical learning process with the InfoNCE loss on Figure 15. Comparing the alignment and uniformity terms, we can see that the alignment gradually improves while test accuracy improves. In comparison, the uniformity term becomes very small at the beginning and is relatively stable while training. This indicates that the alignment term is the main driving force in the contrastive learning process and the uniformity term is mainly used to avoid feature collapse.
sections.heading: F ADDITIONAL EXPERIMENTAL DETAILS
sections.heading: F.1 SIMULATION ON RANDOM AUGMENTATION GRAPH
sections.text: 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 S2 in the 3-dimensional space. One center is (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 , we use a single-hidden-layer neural network with softmax activation, and we use InfoNCE loss to optimize it.
sections.heading: F.2 EXPERIMENTS ON REAL-WORLD DATASETS
sections.text: To better understand and verify our theorem, we conduct experiments on real-world datasets, including CIFAR-10, CIFAR-100 and STL-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-100, 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 to its relatively large size.