A Theoretical Analysis of Contrastive Unsupervised Representation Learning

Introduction

This paper concerns unsupervised representation learning: using unlabeled data to learn a representation function $f$ such that replacing data point $x$ by feature vector $f(x)$ in new classification tasks reduces the requirement for labeled data. This is distinct from semi-supervised learning, where learning can leverage unlabeled as well as labeled data. (Section 7 surveys other prior ideas and models).

For images, a proof of existence for broadly useful representations is the output of the penultimate layer (the one before the softmax) of a powerful deep net trained on ImageNet. In natural language processing (NLP), low-dimensional representations of text – called text embeddings – have been computed with unlabeled data Peters et al. (2018); Devlin et al. (2018). Often the embedding function is trained by using the embedding of a piece of text to predict the surrounding text Kiros et al. (2015); Logeswaran & Lee (2018); Pagliardini et al. (2018). Similar methods that leverage similarity in nearby frames in a video clip have had some success for images as well Wang & Gupta (2015).

Many of these algorithms are related: they assume access to pairs or tuples (in the form of co-occurrences) of text/images that are more semantically similar than randomly sampled text/images, and their objective forces representations to respect this similarity on average. For instance, in order to learn a representation function $f$ for sentences, a simplified version of what Logeswaran & Lee (2018) minimize is the following loss function

where $(x,x^{+})$ are a similar pair and $x^{-}$ is presumably dissimilar to $x$ (often chosen to be a random point) and typically referred to as a negative sample. Though reminiscent of past ideas – e.g. kernel learning, metric learning, co-training Cortes et al. (2010); Bellet et al. (2013); Blum & Mitchell (1998) – these algorithms lack a theoretical framework quantifying when and why they work. While it seems intuitive that minimizing such loss functions should lead to representations that capture ‘similarity,’ formally it is unclear why the learned representations should do well on downstream linear classification tasks – their somewhat mysterious success is often treated as an obvious consequence. To analyze this success, a framework must connect ‘similarity’ in unlabeled data with the semantic information that is implicitly present in downstream tasks.

We propose the term Contrastive Learning for such methods and provide a new conceptual framework with minimal assumptionsThe alternative would be to make assumptions about generative models of data. This is difficult for images and text. . Our main contributions are the following:

We formalize the notion of semantic similarity by introducing latent classes. Similar pairs are assumed to be drawn from the same latent class. A downstream task is comprised of a subset of these latent classes.

Under this formalization, we prove that a representation function $f$ learned from a function class ${\mathcal{F}}$ by contrastive learning has low average linear classification loss if ${\mathcal{F}}$ contains a function with low unsupervised loss. Additionally, we show a generalization bound for contrastive learning that depends on the Rademacher complexity of ${\mathcal{F}}$. After highlighting inherent limitations of negative sampling, we show sufficient properties of ${\mathcal{F}}$ which allow us to overcome these limitations.

Using insights from the above framework, we provide a novel extension of the algorithm that can leverage larger blocks of similar points than pairs, has better theoretical guarantees, and performs better in practice.

Ideally, one would like to show that contrastive learning always gives representations that compete with those learned from the same function class with plentiful labeled data. Our formal framework allows a rigorous study of such questions: we show a simple counterexample that prevents such a blanket statement without further assumptions. However, if the representations are well-concentrated and the mean classifier (Definition 2.1) has good performance, we can show a weaker version of the ideal result (Corollary 5.1.1). Sections 2 and 3 give an overview of the framework and the results, and subsequent sections deal with the analysis. Related work is discussed in Section 7 and Section 8 describes experimental verification and support for our framework.

Framework for Contrastive Learning

To formalize the notion of semantically similar pairs $(x,x^{+})$, we introduce the concept of latent classes.

Let ${\mathcal{C}}$ denote the set of all latent classes. Associated with each class $c\in{\mathcal{C}}$ is a probability distribution ${\mathcal{D}}_{c}$ over ${\mathcal{X}}$ .

Roughly, ${\mathcal{D}}_{c}(x)$ captures how relevant $x$ is to class $c$. For example, ${\mathcal{X}}$ could be natural images and $c$ the class “dog” whose associated ${\mathcal{D}}_{c}$ assigns high probability to images containing dogs and low/zero probabilities to other images. Classes can overlap arbitrarily.An image of a dog by a tree can appear in both ${\mathcal{D}}_{dog}$ & ${\mathcal{D}}_{tree}$. Finally, we assume a distribution $\rho$ over the classes that characterizes how these classes naturally occur in the unlabeled data. Note that we make no assumption about the functional form of ${\mathcal{D}}_{c}$ or $\rho$.

Semantic Similarity

To formalize similarity, we assume similar data points $x,x^{+}$ are i.i.d. draws from the same class distribution ${\mathcal{D}}_{c}$ for some class $c$ picked randomly according to measure $\rho$. Negative samples are drawn from the marginal of ${\mathcal{D}}_{sim}$:

Since classes are allowed to overlap and/or be fine-grained, this is a plausible formalization of “similarity.” As the identity of the class in not revealed, we call it unlabeled data. Currently empirical works heuristically identify such similar pairs from co-occurring image or text data.

Supervised Tasks

We now characterize the tasks that a representation function $f$ will be tested on. A $(k+1)$-wayWe use $k$ as the number of negative samples later. supervised task ${\mathcal{T}}$ consists of distinct classes $\{c_{1},\dots,c_{k+1}\}\subseteq{\mathcal{C}}$. The labeled dataset for the task ${\mathcal{T}}$ consists of $m$ i.i.d. draws from the following process:

A label $c\in\{c_{1},...,c_{k+1}\}$ is picked according to a distribution ${\mathcal{D}}_{\mathcal{T}}$. Then, a sample $x$ is drawn from ${\mathcal{D}}_{c}$. Together they form a labeled pair $(x,c)$ with distribution

A key subtlety in this formulation is that the classes in downstream tasks and their associated data distributions ${\mathcal{D}}_{c}$ are the same as in the unlabeled data. This provides a path to formalizing how capturing similarity in unlabeled data can lead to quantitative guarantees on downstream tasks. ${\mathcal{D}}_{\mathcal{T}}$ is assumed to be uniformWe state and prove the general case in the Appendix. for theorems in the main paper.

Evaluation Metric for Representations

Crucial to our results and experiments will be a specific $W$ where the rows are the means of the representations of each class which we define below.

Since contrastive learning has access to data with latent class distribution $\rho$, it is natural to have better guarantees for tasks involving classes that have higher probability in $\rho$.

Average loss for a function $f$ on $(k+1)$-way tasks is defined as

The average supervised loss of its mean classifier is

Contrastive Learning Algorithm

and its empirical counterpart with M samples $(x_{j},x^{+}_{j},x_{j1}^{-},...,x_{jk}^{-})_{j=1}^{M}$ from ${\mathcal{D}}_{sim}\times{\mathcal{D}}_{neg}^{k}$ is

Note that, by the assumptions of the framework described above, we can now express the unsupervised loss as

The algorithm to learn a representation function from ${\mathcal{F}}$ is to find a function $\widehat{f}\in\operatorname*{arg\,min}_{f\in{\mathcal{F}}}{\widehat{L}_{un}(f)}$ that minimizes the empirical unsupervised loss. This function $\widehat{f}$ can be subsequently used for supervised linear classification tasks. In the following section we proceed to give an overview of our results that stem from this framework.

Overview of Analysis and Results

What can one provably say about the performance of $\widehat{f}$? As a first step we show that $L_{un}$ is like a “surrogate” for $L_{sup}$ by showing that $L_{sup}(f)\leq\alpha L_{un}(f),\forall f\in{\mathcal{F}}$, suggesting that minimizing $L_{un}$ makes sense. This lets us show a bound on the supervised performance $L_{sup}(\widehat{f})$ of the representation learned by the algorithm. For instance, when training with one negative sample, the performance on average binary classification has the following guarantee:

where $\alpha,\eta,\delta$ are constants depending on the distribution $\rho$ and $Gen_{M}\to 0$ as $M\to\infty$. When $\rho$ is uniform and $|{\mathcal{C}}|\to\infty$, we have that $\alpha,\eta\to 1,\ \delta\to 0$.

At first glance, this bound seems to offer a somewhat complete picture: When the number of classes is large, if the unsupervised loss can be made small by ${\mathcal{F}}$, then the supervised loss of $\widehat{f}$, learned using finite samples, is small.

While encouraging, this result still leaves open the question: Can $L_{un}(f)$ indeed be made small on reasonable datasets using function classes ${\mathcal{F}}$ of interest, even though the similar pair and negative sample can come from the same latent class? We shed light on this by upper-bounding $L_{un}(f)$ by two components: (a) the loss $L_{un}^{\neq}(f)$ for the case where the positive and negative samples are from different classes; (b) a notion of deviation $s(f)$, within each class.

for constants $\beta,\eta$ that depend on the distribution $\rho$. Again, when $\rho$ is uniform and $|{\mathcal{C}}|\to\infty$ we have $\beta\to 0,\eta\to 1$.

This bound lets us infer the following: if the class ${\mathcal{F}}$ is rich enough to contain a function $f$ for which $L_{un}^{\neq}(f)+\beta s(f)$ is low, then $\widehat{f}$ has high supervised performance. Both $L_{un}^{\neq}(f)$ and $s(f)$ can potentially be made small for rich enough ${\mathcal{F}}$.

Ideally, however, one would want to show that $\widehat{f}$ can compete on classification tasks with every $f\in{\mathcal{F}}$

Unfortunately, we show in Section 5.1 that the algorithm can pick something far from the optimal $f$. However, we extend Theorem 4.5 to a bound similar to (7) (where the classification is done using the mean classifier) under assumptions about the intraclass concentration of $f$ and about its mean classifier having high margin.

Sections 6.1 and 6.2 extend our results to the more complicated setting where the algorithm uses $k$ negative samples (5) and note an interesting behavior: increasing the number of negative samples beyond a threshold can hurt the performance. In Section 6.3 we show a novel extension of the algorithm that utilizes larger blocks of similar points. Finally, we perform controlled experiments in Section 8 to validate components of our framework and corroborate our suspicion that the mean classifier of representations learned using labeled data has good classification performance.

Guaranteed Average Binary Classification

To provide the main insights, we prove the algorithm’s guarantee when we use only 1 negative sample ($k=1$). For this section, let $L_{sup}(f)$ and $L^{\mu}_{sup}(f)$ be as in Definition 2.2 for binary tasks. We will refer to the two classes in the supervised task as well as the unsupervised loss as $c^{+},c^{-}$. Let ${\mathcal{S}}=\{x_{j},x_{j}^{+},x_{j}^{-}\}_{j=1}^{M}$ be our training set sampled from the distribution ${\mathcal{D}}_{sim}\times{\mathcal{D}}_{neg}$ and $\widehat{f}\in\operatorname*{arg\,min}_{f\in{\mathcal{F}}}\widehat{L}_{un}(f)$.

With probability at least $1-\delta$, for all $f\in{\mathcal{F}}$

The complexity measure ${\mathcal{R}}_{S}({\mathcal{F}})$ is tightly related to the labeled sample complexity of the classification tasks. For the function class ${\mathcal{G}}=\{w^{T}f(\cdot)|f\in{\mathcal{F}},\ \|w\|\leq 1\}$ that one would use to solve a binary task from scratch using labeled data, it can be shown that $\mathcal{R}_{{\mathcal{S}}}({\mathcal{F}})\leq d\mathcal{R}_{\mathcal{S}}({\mathcal{G}})$, where $\mathcal{R}_{\mathcal{S}}({\mathcal{G}})$ is the usual Rademacher complexity of ${\mathcal{G}}$ on ${\mathcal{S}}$ (Definition 3.1 from Mohri et al. (2018)).

We state two key lemmas needed to prove the theorem.

With probability at least $1-\delta$ over the training set ${\mathcal{S}}$, for all $f\in{\mathcal{F}}$

The result follows directly by applying Lemma 4.3 for $\widehat{f}$ and finishing up with Lemma 4.2. ∎

One could argue that if ${\mathcal{F}}$ is rich enough such that $L_{un}$ can be made small, then Theorem 4.1 suffices. However, in the next section we explain that unless $\tau\ll 1$, this may not always be possible and we show one way to alleviate this.

2 Price of Negative Sampling: Class Collision

Note first that the unsupervised loss can be decomposed as

where $L^{\neq}_{un}(f)$ is the loss suffered when the similar pair and the negative sample come from different classes.

and $L^{=}_{un}(f)$ is when they come from the same class. Let $\nu$ be a distribution over ${\mathcal{C}}$ with $\nu(c)\propto\rho^{2}(c)$, then

by Jensen’s inequality again, which implies $L_{un}(f)\geq\tau$. In general, without any further assumptions on $f$, $L_{un}(f)$ can be far from $\tau$, rendering the bound in Theorem 4.1 useless. However, as we will show, the magnitude of $L_{un}^{=}(f)$ can be controlled by the intraclass deviation of $f$. Let $\Sigma(f,c)$ the covariance matrix of $f(x)$ when $x\sim{\mathcal{D}}_{c}$. We define a notion of intraclass deviation as follows:

where $c^{\prime}$ is a positive constant.

We prove Lemma 4.4 in Appendix A.1. Theorem 4.1 combined with Equation (8) and Lemma 4.4 gives the following result.

With probability at least $1-\delta$, $\forall f\in{\mathcal{F}}$

where $\beta=c^{\prime}\frac{\tau}{1-\tau}$, $\eta=\frac{1}{1-\tau}$ and $c^{\prime}$ is a constant.

The above bound highlights two sufficient properties of the function class for unsupervised learning to work: when the function class ${\mathcal{F}}$ is rich enough to contain some $f$ with low $\beta s(f)$ as well as low $L_{un}^{\neq}(f)$ then $\widehat{f}$, the empirical minimizer of the unsupervised loss – learned using sufficiently large number of samples – will have good performance on supervised tasks (low $L_{sup}(\widehat{f}))$.

Towards Competitive Guarantees

We provide intuition and counter-examples for why contrastive learning does not always pick the best supervised representation $f\in{\mathcal{F}}$ and show how our bound captures these. Under additional assumptions, we show a competitive bound where classification is done using the mean classifier.

The bound provided in Theorem 4.5 might not appear as the most natural guarantee for the algorithm. Ideally one would like to show a bound like the following: for all $f\in{\mathcal{F}}$,

for constants $\alpha,\eta$ and generalization error $Gen_{M}$. This guarantees that $\widehat{f}$ is competitive against the best $f$ on the average binary classification task. However, the bound we prove has the following form: for all $f\in{\mathcal{F}}$,

To show that this discrepancy is not an artifact of our analysis but rather stems from limitations of the algorithm, we present two examples in Figure 1. Our bound appropriately captures these two issues individually owing to the large values of $L^{\neq}(f)$ or $s(f)$ in each case, for the optimal $f$.

In Figure 1(a), we see that there is a direction on which $f_{1}$ can be projected to perfectly separate the classes. Since the algorithm takes inner products between the representations, it inevitably considers the spurious components along the orthogonal directions. This issue manifests in our bound as the term $L^{\neq}_{un}(f_{1})$ being high even when $s(f_{1})=0$. Hence, contrastive learning will not always work when the only guarantee we have is that ${\mathcal{F}}$ can make $L_{sup}$ small.

This should not be too surprising, since we show a relatively strong guarantee – a bound on $L^{\mu}_{sup}$ for the mean classifier of $\widehat{f}$. This suggests a natural stronger assumption that ${\mathcal{F}}$ can make $L_{sup}^{\mu}$ small (which is observed experimentally in Section 8 for function classes of interest) and raises the question of showing a bound that looks like the following: for all $f\in{\mathcal{F}}$,

without accounting for any intraclass deviation – recall that $s(f)$ captures a notion of this deviation in our bound. However this is not true: high intraclass deviation may not imply high $L_{sup}^{\mu}(f)$, but can make $L_{un}^{=}(f)$ (and thus $L_{un}(f)$) high, resulting in the failure of the algorithm. Consequently, the term $s(f)$ also increases while $L_{un}^{\neq}$ does not necessarily have to. This issue, apparent in Figure 1(b), shows that a guarantee like (11) cannot be shown without further assumptions.

2 Competitive Bound via Intraclass Concentration

We saw that $L_{sup}^{\mu}(f)$ being small does not imply low $L_{sup}^{\mu}(\widehat{f})$, if $f$ is not concentrated within the classes. In this section we show that when there is an $f$ that has intraclass concentration in a strong sense (sub-Gaussianity) and can separate classes with high margin (on average) with the mean classifier, then $L_{sup}^{\mu}(\widehat{f})$ will be low.

For $f\in{\mathcal{F}}$, if the random variable $f(X)$, where $X\sim D_{c}$, is $\sigma^{2}$-sub-Gaussian in every direction for every class $c$ and has maximum norm $R=max_{x\in{\mathcal{X}}}\|f(x)\|$, then for all $\epsilon>0$,

where $\gamma=1+c^{\prime}R\sigma\sqrt{\log\frac{R}{\epsilon}}$ and $c^{\prime}$ is some constant.

The proof of Lemma 5.1 is provided in the Appendix A.2. Using Lemma 5.1 and Theorem 4.5, we get the following:

For all $\epsilon>0$, with probability at least $1-\delta$, for all $f\in{\mathcal{F}}$,

where $\gamma(f)$ is as defined in Lemma 5.1, $\beta=c^{\prime}\frac{\tau}{1-\tau}$, $\eta=~{}\frac{\tau}{1-\tau}$ and $c^{\prime}$ is a constant.

Multiple Negative Samples and Block Similarity

In this section we explore two extensions to our analysis. First, in Section 6.1, inspired by empirical works like Logeswaran & Lee (2018) that often use more than one negative sample for every similar pair, we show provable guarantees for this case by careful handling of class collision. Additionally, in Section 6.2 we show simple examples where increasing negative samples beyond a certain threshold can hurt contrastive learning. Second, in Section 6.3, we explore a modified algorithm that leverages access to blocks of similar data, rather than just pairs and show that it has stronger guarantees as well as performs better in practice.

Here the algorithm utilizes $k$ negative samples $x_{1}^{-},...,x_{k}^{-}$ drawn i.i.d. from ${\mathcal{D}}_{neg}$ for every positive sample pair $x,x^{+}$ drawn from ${\mathcal{D}}_{sim}$ and minimizes (6). As in Section 4, we prove a bound for $\widehat{f}$ of the following form:

(Informal version) For all $f\in{\mathcal{F}}$

where $L_{un}^{\neq}(f)$ and $Gen_{M}$ are extensions of the corresponding terms from Section 4 and $s(f)$ remains unchanged. The formal statement of the theorem and its proof appears in Appendix B.1. The key differences from Theorem 4.5 are $\beta$ and the distribution of tasks in ${\mathcal{L}}_{sup}$ that we describe below. The coefficient $\beta$ of $s(f)$ increases with $k$, e.g. when $\rho$ is uniform and $k\ll|{\mathcal{C}}|$, $\beta\approx\frac{k}{|{\mathcal{C}}|}$.

The average supervised loss that we bound is

where ${\mathcal{D}}$ is a distribution over tasks, defined as follows: sample $k+1$ classes $c^{+},c_{1}^{-},\dots,c_{k}^{-}\sim\rho^{k+1}$, conditioned on the event that $c^{+}$ does not also appear as a negative sample. Then, set ${\mathcal{T}}$ to be the set of distinct classes in $\{c^{+},c_{1}^{-},\dots,c_{k}^{-}\}$. ${\mathcal{L}}_{sup}^{\mu}(\widehat{f})$ is defined by using $L^{\mu}_{sup}({\mathcal{T}},\widehat{f})$.

Bounding ${\mathcal{L}}_{sup}(\widehat{f})$ directly gives a bound for average $(k+1)$-wise classification loss $L_{sup}(\widehat{f})$ from Definition 2.2, since $L_{sup}(\widehat{f})\leq{\mathcal{L}}_{sup}(\widehat{f})/p$, where $p$ is the probability that the $k+1$ sampled classes are distinct. For $k\ll|{\mathcal{C}}|$ and $\rho$ $\approx$ uniform, these metrics are almost equal.

We also extend our competitive bound from Section 5.2 for the above $\widehat{f}$ in Appendix B.2.

2 Effect of Excessive Negative Sampling

The standard belief is that increasing the number of negative samples always helps, at the cost of increased computational costs. In fact for Noise Contrastive Estimation (NCE) Gutmann & Hyvärinen (2010), which is invoked to explain the success of negative sampling, increasing negative samples has shown to provably improve the asymptotic variance of the learned parameters. However, we find that such a phenomenon does not always hold for contrastive learning – larger $k$ can hurt performance for the same inherent reasons highlighted in Section 5.1, as we illustrate next.

When $\rho$ is close to uniform and the number of negative samples is $k=\Omega(|{\mathcal{C}}|)$, frequent class collisions can prevent the unsupervised algorithm from learning the representation $f\in{\mathcal{F}}$ that is optimal for the supervised problem. In this case, owing to the contribution of $s(f)$ being high, a large number of negative samples could hurt. This problem, in fact, can arise even when the number of negative samples is much smaller than the number of classes. For instance, if the best representation function $f\in{\mathcal{F}}$ groups classes into $t$ “clusters”,This can happen when ${\mathcal{F}}$ is not rich enough. such that $f$ cannot contrast well between classes from the same cluster, then $L^{\neq}_{un}$ will contribute to the unsupervised loss being high even when $k=\Omega(t)$. We illustrate, by examples, how these issues can lead to picking suboptimal $\widehat{f}$ in Appendix C. Experimental results in Figures 2(a) and 2(b) also suggest that larger negative samples hurt performance beyond a threshold, confirming our suspicions.

3 Blocks of Similar Points

Often a dataset consists of blocks of similar data instead of just pairs: a block consists of $x_{0},x_{1},\dots x_{b}$ that are i.i.d. draws from a class distribution $D_{c}$ for a class $c\sim\rho$. In text, for instance, paragraphs can be thought of as a block of sentences sampled from the same latent class. How can an algorithm leverage this additional structure?

We propose an algorithm that uses two blocks: one for positive samples $x,x^{+}_{1},\dots,x^{+}_{b}$ that are i.i.d. samples from $c^{+}\sim\rho$ and another one of negative samples $x^{-}_{1},\dots x^{-}_{b}$ that are i.i.d. samples from $c^{-}\sim\rho$. Our proposed algorithm then minimizes the following loss:

To understand why this loss function make sense, recall that the connection between $L^{\mu}_{sup}$ and $L_{un}$ was made in Lemma 4.3 by applying Jensen’s inequality. Thus, the algorithm that uses the average of the positive and negative samples in blocks as a proxy for the classifier instead of just one point each should have a strictly better bound owing to the Jensen’s inequality getting tighter. We formalize this intuition below. Let $\tau$ be as defined in Section 4.

This bound tells us that $L_{un}^{block}$ is a better surrogate for $L_{sup}$, making it a more attractive choice than $L_{un}$ when larger blocks are available.Rigorous comparison of the generalization errors is left for future work.. The algorithm can be extended, analogously to Equation (5), to handle more than one negative block. Experimentally we find that minimizing $L_{un}^{block}$ instead of $L_{un}$ can lead to better performance and our results are summarized in Section 8.2. We defer the proof of Proposition 6.2 to Appendix A.4.

Related Work

The contrastive learning framework is inspired by several empirical works, some of which were mentioned in the introduction. The use of co-occurring words as semantically similar points and negative sampling for learning word embeddings was introduced in Mikolov et al. (2013). Subsequently, similar ideas have been used by Logeswaran & Lee (2018) and Pagliardini et al. (2018) for sentences representations and by Wang & Gupta (2015) for images. Notably the sentence representations learned by the quick thoughts (QT) method in Logeswaran & Lee (2018) that we analyze has state-of-the-art results on many text classification tasks. Previous attempts have been made to explain negative sampling Dyer (2014) using the idea of Noise Contrastive Estimation (NCE) Gutmann & Hyvärinen (2010) which relies on the assumption that the data distribution belongs to some known parametric family. This assumption enables them to consider a broader class of distributions for negative sampling. The mean classifier that appears in our guarantees is of significance in meta-learning and is a core component of ProtoNets Snell et al. (2017).

Our data model for similarity is reminiscent of the one in co-training Blum & Mitchell (1998). They assume access to pairs of “views” with the same label that are conditionally independent given the label. Our unlabeled data model can be seen as a special case of theirs, where the two views have the same conditional distributions. However, they additionally assume access to some labeled data (semi-supervised), while we learn representations using only unlabeled data, which can be subsequently used for classification when labeled data is presented. Two-stage kernel learning Cortes et al. (2010); Kumar et al. (2012) is similar in this sense: in the first stage, a positive linear combination of some base kernels is learned and is then used for classification in the second stage; they assume access to labels in both stages. Similarity/metric learning Bellet et al. (2012; 2013) learns a linear feature map that gives low distance to similar points and high to dissimilar. While they identify dissimilar pairs using labels, due to lack of labels we resort to negative sampling and pay the price of class collision. While these works analyze linear function classes, we can handle arbitrarily powerful representations. Learning of representations that are broadly useful on a distribution of tasks is done in multitask learning, specifically in the learning-to-learn model Maurer et al. (2016) but using labeled data.

Recently Hazan & Ma (2016) proposed “assumption-free” methods for representation learning via MDL/compression arguments, but do not obtain any guarantees comparable to ours on downstream classification tasks. As noted by Arora & Risteski (2017), this compression approach has to preserve all input information (e.g. preserve every pixel of the image) which seems suboptimal.

Experimental Results

We report experiments in text and vision domains supporting our theory. Since contrastive learning has already shown to obtain state-of-the-art results on text classification by quick thoughts (QT) in Logeswaran & Lee (2018), most of our experiments are conducted to corroborate our theoretical analysis. We also show that our extension to similarity blocks in Section 6.3 can improve QT on a real-world task.

Datasets: Two datasets were used in the controlled experiments. (1) The CIFAR-100 dataset Krizhevsky (2009) consisting of 32x32 images categorized into 100 classes with a 50000/10000 train/test split. (2) Lacking an appropriate NLP dataset with large number of classes, we create the Wiki-3029 dataset, consisting of 3029 Wikipedia articles as the classes and 200 sentences from each article as samples. The train/dev/test split is 70%/10%/20%. To test our method on a more standard task, we also use the unsupervised part of the IMDb review corpus Maas et al. (2011), which consists of 560K sentences from 50K movie reviews. Representations trained using this corpus are evaluated on the supervised IMDb binary classification task, consisting of training and testing set with 25K reviews each.

To simulate the data generation process described in Section 2, we generate similar pairs (blocks) of data points by sampling from the same class. Dissimilar pairs (negative samples) are selected randomly. Contrastive learning was done using our objectives (5), and compared to performance of standard supervised training, with both using the same architecture for representation $f$. For CIFAR-100 we use VGG-16 Simonyan & Zisserman (2014) with an additional 512x100 linear layer added at the end to make the final representations 100 dimensional, while for Wiki-3029 we use a Gated Recurrent Network (GRU) Chung et al. (2015) with output dimension 300 and fix the word embedding layer with pretrained GloVe embeddings Pennington et al. (2014). The unsupervised model for CIFAR-100 is trained with 500 blocks of size 2 with 4 negative samples, and for Wiki-3029 we use 20 blocks of size 10 with 8 negative samples. We test (1) learned representations on average tasks by using the mean classifier and compare to representations trained using labeled data; (2) the effect of various parameters like amount of unlabeled data ($N$)If we used $M$ similar blocks of size $b$ and $k$ negative blocks for each similar block, $N=Mb(k+1)$. In practice, however, we reuse the blocks for negative sampling and lose the factor of $k+1$., number of negative samples ($k$) and block size ($b$) on representation quality; (3) whether the supervised loss tracks the unsupervised loss as suggested by Theorem 4.1; (4) performance of the mean classifier of the supervised model.

Results: These appear in Table 1. For Wiki-3029 the unsupervised performance is very close to the supervised performance in all respects, while for CIFAR-100 the avg-$k$ performance is respectable, rising to good for binary classification. One surprise is that the mean classifier, central to our analysis of unsupervised learning, performs well also with representations learned by supervised training on CIFAR-100. Even the mean computed by just $5$ labeled samples performs well, getting within $2\%$ accuracy of the $500$ sample mean classifier on CIFAR-100. This suggests that representations learnt by standard supervised deep learning are actually quite concentrated. We also notice that the supervised representations have fairly low unsupervised training loss (as low as 0.4), even though the optimization is minimizing a different objective.

To measure the sample complexity benefit provided by contrastive learning, we train the supervised model on just $10\%$ fraction of the dataset and compare it with an unsupervised model trained on unlabeled data whose mean classifiers are computed using the same amount of labeled data. We find that the unsupervised model beats the supervised model by almost $4\%$ on the 100-way task and by $5\%$ on the average binary task when only 50 labeled samples are used.

Figure 2 highlights the positive effect of increasing number of negative samples as well as amount of data used by unsupervised algorithm. In both cases, using a lot of negative examples stops helping after a point, confirming our suspicions in Section 6.2. We also demonstrate how the supervised loss tracks unsupervised test loss in Figure 2(c).

2 Effect of Block Size

As suggested in Section 6.3, a natural extension to the model would be access to blocks of similar points. We refer to our method of minimizing the loss in (12) as CURL for Contrastive Unsupervised Representation Learning and perform experiments on CIFAR-100, Wiki-3029, and IMDb. In Table 2 we see that for CIFAR-100 and Wiki-3029, increasing block size yields an improvement in classification accuracy. For IMDb, as is evident in Table 2, using larger blocks provides a clear benefit and the method does better than QT, which has state-of-the-art performance on many tasks. A thorough evaluation of CURL and its variants on other unlabeled datasets is left for future work.

Conclusion

Contrastive learning methods have been empirically successful at learning useful feature representations. We provide a new conceptual framework for thinking about this form of learning, which also allows us to formally treat issues such as guarantees on the quality of the learned representations. The framework gives fresh insights into what guarantees are possible and impossible, and shapes the search for new assumptions to add to the framework that allow tighter guarantees. The framework currently ignores issues of efficient minimization of various loss functions, and instead studies the interrelationships of their minimizers as well as sample complexity requirements for training to generalize, while clarifying what generalization means in this setting. Our approach should be viewed as a first cut; possible extensions include allowing tree structure – more generally metric structure – among the latent classes. Connections to meta-learning and transfer learning may arise.

We use experiments primarily to illustrate and support the new framework. But one experiment on sentence embeddings already illustrates how fresh insights derived from our framework can lead to improvements upon state-of-the-art models in this active area. We hope that further progress will follow, and that our theoretical insights will begin to influence practice, including design of new heuristics to identify semantically similar/dissimilar pairs.

Acknowledgements

This work is supported by NSF, ONR, the Simons Foundation, the Schmidt Foundation, Mozilla Research, Amazon Research, DARPA, and SRC. We thank Rong Ge, Elad Hazan, Sham Kakade, Karthik Narasimhan, Karan Singh and Yi Zhang for helpful discussions and suggestions.

References

Appendix A Deferred Proofs

We prove a general Lemma, from which Lemma 4.4 can be derived directly.

where $c^{\prime}$ is a positive constant.

A.2 Proof of Lemma 5.1

A.3 Generalization Bound

We first state the following general Lemma in order to bound the generalization error of the function class ${\mathcal{F}}$ on the unsupervised loss function $L_{un}(\cdot)$. Lemma 4.2 can be directly derived from it.

and $f_{|{\mathcal{S}}}=\left(f_{t}(x_{j}),f_{t}(x_{j}^{+}),f_{t}(x_{j1}^{-}),\dots,,f_{t}(x_{jk}^{-})\right)_{\begin{subarray}{c}j\in[M]\\ t\in[d]\end{subarray}}$

Note that for $k+1$-way classification, for hinge loss we have $\eta=1$ and $B=O(R^{2})$, while for logistic loss $\eta=1$ and $B=O(R^{2}+\log{k})$. Setting $k=1$, we get Lemma 4.2. We now prove Lemma A.2.

First, we use the classical bound for the generalization error in terms of the Rademacher complexity of the function class (see Mohri et al. (2018) Theorem 3.1). For a real function class $G$ whose functions map from a set $Z$ to $$and for any$\delta>0$, if${\mathcal{S}}$is a training set composed by$M$iid samples$\{z_{j}\}_{j=1}^{M}$, then with probability at least$1-\frac{\delta}{2}$, for all$g\in G$

where $\mathcal{R}_{\mathcal{S}}(G)$ is the usual Rademacher complexity. We apply this bound to our case by setting $Z={\mathcal{X}}^{k+2}$, ${\mathcal{S}}$ is our training set and the function class is

We will show that for some universal constant c, $\mathcal{R}_{{\mathcal{S}}}(G)\leq c\frac{\eta R\sqrt{k}}{B}\mathcal{R}_{{\mathcal{S}}}({\mathcal{F}})$ or equivalently

where $(g_{f})_{|\mathcal{S}}=\{g_{f}(x_{j},x_{j}^{+},x_{j1}^{-},...,x_{jk}^{-})\}_{j=1}^{M}$. To do that we will use the following vector-contraction inequality.

We apply Theorem A.3 to our case by setting $Z={\mathcal{X}}^{k+2}$, $n=d(k+2)$ and

Now, we see that $\phi$ is $\sqrt{6k}R$-Lipschitz when $\sum_{t}v_{t}^{2},\sum_{t}(v_{t}^{+})^{2},\sum_{t}(v_{tj}^{-})^{2}\leq R^{2}$ by computing its Jacobian. Indeed, for all $i,j\in[k]$ and $t\in[d]$, we have $\frac{\partial\phi_{i}}{\partial v_{t}}=v_{t}^{+}-v_{ti}^{-}$, $\frac{\partial\phi_{i}}{\partial v_{t}^{+}}=v_{t}$ and $\frac{\partial\phi_{i}}{\partial v_{tj}^{-}}=-v_{t}1\{i=j\}$. From triangle inequaltiy, the Frobenius norm of the Jacobian $J$ of $\phi$ is

Now, we have that with probability at least $1-\frac{\delta}{2}$

Let $f^{*}\in\operatorname*{arg\,min}_{f\in{\mathcal{F}}}L_{un}(f)$. With probability at least $1-\frac{\delta}{2}$, we have that $\widehat{L}_{un}(f^{*})\leq L_{un}(f^{*})+3B\sqrt{\frac{\log{\frac{2}{\delta}}}{2M}}$ (Hoeffding’s inequality). Combining this with Equation (20), the fact that $\widehat{L}_{un}(\hat{f})\leq\widehat{L}_{un}(f^{*})$ and applying a union bound, finishes the proof. ∎

A.4 Proof of Proposition 6.2

The proof of the lower bound is analogous to that of Lemma 4.3.

Appendix B Results for k Negative Samples

We now present Theorem B.1 as the formal statement of Theorem 6.1 and prove it. First we define some necessary quantities.

Let $(c^{+},c_{1}^{-},\dots,c_{k}^{-})$ be $k+1$ not necessarily distinct classes. We define $Q(c^{+},c_{1}^{-},\dots,c_{k}^{-})$ to be the set of distinct classes in this tuple. We also define $I^{+}(c_{1}^{-},...,c_{k}^{-})=\{i\in[k]\ |\ c_{i}^{-}=c^{+}\}$ to be the set of indices where $c^{+}$ reappears in the negative samples. We will abuse notation and just write $Q$, $I^{+}$ when the tuple is clear from the context.

To define $L_{un}^{\neq}(f)$ consider the following tweak in the way the latent classes are sampled: sample $c^{+},c_{1}^{-},\dots,c_{k}^{-}\sim\rho^{k+1}$ conditioning on $|I^{+}|<k$ and then remove all $c_{i}^{-}$, $i\in I^{+}$. The datapoints are then sampled as usual: $x,x^{+}\sim{\mathcal{D}}_{c^{+}}^{2}$ and $x_{i}^{-}\sim{\mathcal{D}}_{c_{i}^{-}}$, $i\in[k]$, independently.

which always contrasts points from different classes, since it only considers the negative samples that are not from $c^{+}$.

The generalization error is The $\log{k}$ term can be made $O(1)$ for the hinge loss.

Let $\hat{f}\in\operatorname*{arg\,min}_{f\in{\mathcal{F}}}\widehat{L}_{un}(f)$. With probability at least $1-\delta$, for all $f\in{\mathcal{F}}$

Note that the definition of $s(f)$ used here is defined in Section 4

First, we note that both hinge and logistic loss satisfy the following property: $\forall I_{1},I_{2}$ such that $I_{1}\cup I_{2}=[t]$ we have that

Step 2 (decomposing into supervised tasks) We now decompose the above quantity to handle repeated classes.

Recall that in the main paper, sampling ${\mathcal{T}}$ from ${\mathcal{D}}$ is defined as sampling the (k+1)-tuple from $\rho^{k+1}$ conditioned on $I^{+}=\emptyset$ and setting ${\mathcal{T}}=Q$. Based on this definition, by the tower property of expectation, we have

where $\rho^{+}({\mathcal{T}})$ is the distribution of $c^{+}$ when $(c^{+},c_{1}^{-},...,c_{k}^{-})$ are sampled from $\rho^{k+1}$ conditioned on $Q={\mathcal{T}}$ and $I^{+}=\emptyset$. Recall that $\rho_{min}^{+}({\mathcal{T}})$ from the theorem’s statement is exactly the minimum out of these $|{\mathcal{T}}|$ probabilities. Now, to lower bound the last quantity with the LHS in the theorem statement, we just need to observe that for all tasks ${\mathcal{T}}$

By combining this with Equations (22), (B.1), (25) we get

Now, by applying Lemma A.2, we bound the generalization error: with probability at least $1-\delta$, $\forall f\in{\mathcal{F}}$

However, $L_{un}(f)$ cannot be made arbitrarily small. One can see that for all $f\in{\mathcal{F}}$, $L_{un}(f)$ is lower bounded by the second term in Equation (22), which cannot be made arbitrarily small as $\tau_{k}>0$.

where we applied Jensen’s inequality. Since $\tau_{k}$ is not 0, the above quantity can never be arbitrarily close to 0 (no matter how rich ${\mathcal{F}}$ is).

Step 3 ($L_{un}$ decomposition) Now, we decompose $L_{un}(f)$ by applying the RHS of Equation (21)

Observe that the first term is exactly $(1-\tau^{\prime})L_{un}^{\neq}(f)$. Thus, combining (26), (27) and (31) we get

From the definition of $I^{+}$, $c_{i}^{-}=c^{+}$, $\forall i\in I^{+}$. Thus, from Lemma A.1, we get that

Now, using the fact that $\tau_{k}=1-\sum_{c^{\prime}}\rho(c^{\prime})(1-\rho(c^{\prime}))^{k}=\sum_{c^{\prime}}\rho(c^{\prime})\left(1-(1-\rho(c^{\prime}))^{k}\right)$ and $\tau_{1}=\sum_{c}\rho^{2}(c)$,

B.2 Competitive Bound

For all $f\in{\mathcal{F}}$ suppose the random variable $f(X)$, where $X\sim D_{c}$, is $\sigma^{2}(f)$-subgaussian in every direction for every class $c$ and has maximum norm $R(f)=max_{x\in{\mathcal{X}}}\|f(x)\|$. Let $\widehat{f}\in\operatorname*{arg\,min}_{f\in{\mathcal{F}}}\widehat{L}_{un}(f)$. Then for all $\epsilon>0$, with probability at least $1-\delta$, for all $f\in{\mathcal{F}}$

where $\gamma(f)=1+c^{\prime}R(f)\sigma(f)(\sqrt{\log{k}}+\sqrt{\log{\frac{R(f)}{\epsilon}}})$, $c^{\prime}$ is some constant, $\alpha=\frac{1-\tau^{\prime}}{1-\tau_{k}}$, $\beta=k\frac{\tau_{1}}{1-\tau_{k}}$ and $\eta=\frac{1}{1-\tau_{k}}$.

We will show that $\forall f\in{\mathcal{F}}$

and the Lemma follows from Theorem 6.1. Now, we fix an $\epsilon>0$, an $f\in{\mathcal{F}}$ and we drop most of the arguments $f$ in the rest of the proof. Also, fix $c^{+},c_{1}^{-}\dots c_{k}^{-},x$ and let $t=k-|I^{+}|$. We assume without loss of generality, that $c^{+}\neq c_{i}^{-}$, $\forall i\in[t]$. Now,

Appendix C Examples for Section 6.2

Here, we illustrate via examples two ways in which the increase of $k$ can lead to suboptimal $\hat{f}$. We will consider the hinge loss as the loss function, while the examples carry over trivially for logistic loss.

We can extend the first example to the case where, even when $k=o(|{\mathcal{C}}|)$, the algorithm picks suboptimal representations. To do so, we simply ‘replicate’ the first example to create clusters of classes. Formally, let ${\mathcal{C}}=\{c_{ij}\}_{i,j\in[n]}$ where for each class, $D_{c_{ij}}$ is uniform over two points $\{x^{1}_{ij},x^{2}_{ij}\}$. Finally, same as above, let ${\mathcal{F}}$ consist of two functions $\{f_{0},f_{1}\}$. The function $f_{1}$ maps $f_{1}(x^{1}_{ij})=3/2re_{i}$ and $f_{1}(x^{2}_{ij})=1/2re_{i}$ for all $i,j$ and $f_{0}=\vec{0}$. $\rho$ is uniform over ${\mathcal{C}}$. Now, note that $f_{1}$ ‘clutsters’ the $n^{2}$ classes and their points into $n$ clusters, each along an $e_{i}$. Thus, it is only useful for contrasting classes from different clusters. However, note that the probability of intra-cluster collision with $k$ negative samples is $1-(1-1/n)^{k}$. When $k=o(n)$, we have that $L_{un}(f_{1})=o(1)<1=L_{un}(f_{0})$ so the algorithm will pick $f_{1}$. However, when $k=\Omega(n)$, $L_{un}(f)=\Omega(r^{2})>1=L_{un}(f_{0})$ and the algorithm will pick the suboptimal representation $f_{0}$. Thus, despite $|{\mathcal{C}}|=n^{2}$, having more than $n$ negative samples can hurt performance, since even tough $f_{1}$ cannot solve all the tasks, the average supervised loss over $t$-way tasks, $t=o(n)$, is $L_{sup}(f)\leq O(1-(1-1/n)^{t-1})=o(1)$.

Appendix D Experiments

We use the Wikipedia dump and select articles that have entries in the WordNet, have at least 8 sections and at least 12 sentences of length at least 4 per section. At the end of this filtering we are left with 3029 articles with at least 200 sentences per article. We then sample 200 sentences from each article and do a 70%/10%/20% train/dev/test split.

D.2 GRU model

We use a bi-directional GRU with output dimension of 300 trained using dropout 0.3. The input word embeddings are initialized to pretrained CC GloVe vectors and fixed throughout training.