A Theoretical Analysis of Contrastive Unsupervised Representation Learning

Sanjeev Arora; Hrishikesh Khandeparkar; Mikhail Khodak; Orestis Plevrakis; Nikunj Saunshi

Source-linked AI summary

A Theoretical Analysis of Contrastive Unsupervised Representation Learning

Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, Nikunj Saunshi

arXiv:1902.09229v1Feb 25, 2019cs.LGcs.AIstat.ML

TL;DR

The paper addresses why contrastive objectives using similar pairs and negative samples produce representations useful for downstream classification. It introduces latent classes and proves classification and generalization guarantees, while identifying limits of negative sampling and supporting the framework with controlled text and image experiments.

Problem
Existing contrastive methods lacked a theoretical framework explaining when similarity-based unlabeled objectives yield effective downstream linear classification.
Method
The paper models similar points as samples from shared latent classes and analyzes contrastive learning over a representation-function class using downstream linear classification.
Results
The framework proves low average linear classification loss under a low-unsupervised-loss condition, provides generalization bounds, and supports an extension using larger similar-point blocks.
Takeaways & Limitations
The analysis provides a principled connection between unlabeled similarity and downstream classification, with experiments supporting the framework and practical extensions.
Takeaways & Limitations
Contrastive learning does not always work when the only guarantee is that F can make supervised loss small; stronger assumptions are needed for broader guarantees.

Abstract

from arXiv · show

Recent empirical works have successfully used unlabeled data to learn feature representations that are broadly useful in downstream classification tasks. Several of these methods are reminiscent of the well-known word2vec embedding algorithm: leveraging availability of pairs of semantically "similar" data points and "negative samples," the learner forces the inner product of representations of similar pairs with each other to be higher on average than with negative samples. The current paper uses the term contrastive learning for such algorithms and presents a theoretical framework for analyzing them by introducing latent classes and hypothesizing that semantically similar points are sampled from the same latent class. This framework allows us to show provable guarantees on the performance of the learned representations on the average classification task that is comprised of a subset of the same set of latent classes. Our generalization bound also shows that learned representations can reduce (labeled) sample complexity on downstream tasks. We conduct controlled experiments in both the text and image domains to support the theory.

1. Introduction

The paper introduces contrastive learning as a framework for using semantically similar and negative pairs from unlabeled data to learn representations useful for downstream classification. It formalizes similarity through latent classes and proves guarantees while identifying limitations and extending pairwise learning to larger blocks.

Motivation: Contrastive learning uses semantically similar pairs and negative samples to train representations whose similarity structure can support downstream linear classification.The framework addresses why empirically successful objectives should produce useful representations for classification tasks.
Framework: The paper formalizes semantic similarity by assuming similar pairs come from the same latent class, with downstream tasks using subsets of those classes.This connects unlabeled similarity information to semantic labels in later classification tasks.
Theoretical results: The analysis proves low average linear classification loss when the representation class contains a function with low unsupervised loss, and gives a Rademacher-complexity generalization bound.The theory also identifies sufficient properties of the function class that can overcome negative-sampling limitations.
Extension: The paper extends contrastive learning beyond pairs to larger blocks of similar points, with better theoretical guarantees and better empirical performance.The extension is motivated by insights from the theoretical framework.
Limitations: A blanket guarantee that contrastive learning always matches plentifully labeled representations is impossible without further assumptions.A weaker result is available when representations are well-concentrated and the mean classifier performs well.

2. Framework for Contrastive Learning

The framework models similar unlabeled pairs through latent classes, samples negatives from a marginal distribution, and evaluates learned representations on linear classification tasks over related classes. Contrastive learning minimizes an empirical loss over a representation-function class before supervised evaluation.

Data and representations: Contrastive learning assumes similar pairs and k independent negative samples, then learns a bounded representation function from a function class F.Similar pairs come from Dsim, negatives from Dneg, and the representation maps X to R^d with norm bounded by R.
Latent classes: Latent classes define similarity: two similar points are independently drawn from the same class distribution, while classes may overlap and have arbitrary distributions.The class identity is hidden, so these pairs constitute unlabeled data; negative samples are drawn from the marginal of the similar-pair distribution.
Downstream tasks: Downstream tasks consist of distinct latent classes shared with the unlabeled data, and representation quality is measured by linear multiclass classification loss.The classifier uses a matrix W with g(x)=Wf(x), and the supervised loss selects the best W for the representation.
Losses: The supervised evaluation considers hinge and logistic losses based on coordinate differences between the correct class and competing classes.These losses quantify multiclass classification performance for the fixed downstream task.
Mean classifier: The mean classifier uses each task class’s mean representation as a row of W.For class c, the row is the expected representation μ_c of inputs drawn from D_c.
Training objective: The training objective minimizes empirical unsupervised contrastive loss over F, after which the learned representation is used for supervised linear classification.The loss uses the same supervised loss family and k negative samples.

3. Overview of Analysis and Results

The paper establishes theoretical guarantees connecting contrastive loss to average downstream classification performance, while identifying limitations that require additional assumptions. It also extends the analysis to multiple negatives and larger similar-point blocks.

Core guarantee: Contrastive loss can serve as a surrogate for average supervised loss, yielding a bound on the learned representation’s classification performance.The paper first proves Lsup(f) ≤ αLun(f), then bounds the supervised loss of the empirical unsupervised minimizer.
Core guarantee: When the number of classes is large, small unsupervised loss implies small supervised loss for a finite-sample learned representation.For uniform class distributions with |C| →∞, α and η approach 1 while δ approaches 0, and GenM approaches 0 as M grows.
Analysis: The framework decomposes unsupervised loss into different-class loss and within-class representation deviation, clarifying when contrastive learning can work.The decomposition isolates class collisions from a deviation term s(f).
Analysis: Theorem 4.5 requires a function class containing a representation with low different-class loss and low intraclass deviation.Under these conditions, the resulting representation has low supervised loss under the stated bound.
Limitations: The paper gives a counterexample showing that contrastive learning need not compete with every representation in the same function class.A weaker result is recovered under intraclass concentration and good mean-classifier margin assumptions.
Extensions: Increasing negative samples beyond a threshold can hurt performance, while larger blocks of similar points provide better theoretical guarantees and practical performance.The block-based extension is presented as a novel algorithmic improvement within the broader multi-negative analysis.

4. Guaranteed Average Binary Classification

The binary analysis bounds downstream supervised loss using unsupervised contrastive loss, representation-class complexity, and intraclass variation. It also identifies assumptions under which the bound becomes useful and links the complexity term to labeled sample complexity.

Setup: The analysis studies one-negative-sample contrastive learning, with similar and negative examples drawn from distributions Dsim and Dneg.The learned representation is an empirical minimizer of the unsupervised loss over F.
Class collisions: The probability τ measures how often two independently sampled latent classes coincide, creating a class-collision component in negative sampling.The analysis separates cases where the positive and negative samples come from the same or different classes.
Theorem 4.1: Theorem 4.1 bounds supervised performance uniformly over F with a generalization term governed by the Rademacher complexity of F.The theorem applies with probability at least 1−δ over the training set.
Sample complexity: The representation-class complexity is tied to labeled sample complexity through RS(F) ≤ dRS(G).G contains linear classifiers composed with representations in F and bounded classifier weights.
Proof idea: The mean of a latent class can act as a classifier whose loss is no greater than using a random same-class point, via Jensen’s inequality.This observation supports the connection between unsupervised and supervised losses.
Limitations: Without further assumptions, unsupervised loss can be far from τ, making the Theorem 4.1 bound useless.The paper controls this gap using the intraclass deviation of f, represented through covariance-based quantities.
Sufficient conditions: The sufficient conditions require F to contain a representation with both low different-class unsupervised loss and low intraclass deviation.The resulting theorem combines the general bound with a deviation-control lemma; its coefficients depend on τ.
Conclusion: With sufficiently many samples, an empirical minimizer of unsupervised loss has low supervised loss when the function class can make the relevant unsupervised quantities small.This conclusion follows from the theorem’s uniform bound and the stated richness condition.

5. Towards Competitive Guarantees

The paper shows that contrastive learning need not select the best supervised representation, but derives competitive guarantees when representations are concentrated within classes and their mean classifiers have high margin.

Limitations: Contrastive learning can select a representation far from the supervised optimum, so low supervised loss alone does not guarantee competitive selection.The analysis presents counterexamples showing this discrepancy reflects algorithmic limitations rather than only looseness in the proof.
Limitations: Inner-product objectives can be distorted by spurious orthogonal components, producing high unsupervised loss despite perfect class separation along another direction.This issue appears as a high intraclass-deviation term in the bound.
Assumptions: Merely having a representation with low supervised loss is insufficient when it lacks intraclass concentration.The paper distinguishes supervised separability from the concentration needed for the stronger result.
Limitations: The desired guarantee cannot hold without further assumptions because high unsupervised loss can cause the algorithm to choose a suboptimal representation.Figure 1 illustrates this failure through representations with different supervised and unsupervised losses.
Competitive guarantee: A competitive bound is obtained when a representation is strongly concentrated within each class and its mean classifier separates classes with high average margin.The concentration condition is formalized through sub-Gaussianity in every direction and a bounded representation norm.
Competitive guarantee: The resulting guarantee bounds the learned representation’s mean-classifier loss using the representation’s unsupervised loss, deviation, and generalization terms.The proof combines a concentration lemma with the generalization theorem.

6. Multiple Negative Samples and Block Similarity

The analysis extends contrastive learning to multiple negative samples and blocks of similar points. More negatives can worsen performance after a threshold, whereas block-based objectives provide stronger surrogate guarantees and can perform better.

Multiple negative samples: The multiple-negative analysis accounts for class collisions and derives guarantees whose deviation coefficient increases with the number of negatives.For nearly uniform classes and k much smaller than the number of classes, the coefficient scales approximately as k divided by the number of classes.
Multiple negative samples: Experiments show that increasing negative samples helps only up to a threshold, after which performance stops improving or can decline.This pattern is reported in the experiments and is consistent with the collision-based analysis.
Multiple negative samples: For nearly uniform class distributions, increasing negatives to k = Ω(|C|) can cause collisions that prevent learning the supervised-optimal representation.The same failure can occur at smaller k when the representation groups classes into clusters.
Blocks of similar points: The paper extends the framework from similar pairs to blocks of i.i.d. samples drawn from the same latent class.This setting models data such as paragraphs containing multiple related sentences.
Blocks of similar points: Using averages of positive and negative blocks makes the block unsupervised loss a tighter surrogate for mean-classifier supervised loss through Jensen’s inequality.The tighter relation yields a formally better bound than using one positive and one negative point.
Blocks of similar points: The block-based objective can yield better performance than the pair-based objective when larger similar-data blocks are available.The paper reports this improvement experimentally and positions the block loss as a more attractive choice in that setting.

7. Related Work

The paper situates contrastive learning among related representation-learning approaches while distinguishing its unlabeled-data setting from semi-supervised learning. It also notes unresolved comparison questions and contrasts its downstream guarantees with prior approaches.

Contrastive learning builds on co-occurring or semantically similar data and negative sampling, extending ideas used in word and sentence embeddings.
Unlike co-training, this framework learns representations from unlabeled data alone and uses labeled data only for subsequent tasks.
Rigorous comparison of generalization errors with related approaches remains future work.
The paper argues that its downstream classification guarantees are not obtained by assumption-free compression methods.

8. Experimental Results

Experiments in text and vision are designed primarily to support the theoretical framework, while also testing reduced labeled-data requirements and the larger-block CURL extension. Results show strong unsupervised performance and benefits from more data, negative samples, and larger similarity blocks.

Experiments use CIFAR-100, Wiki-3029, and IMDb to evaluate contrastive representations in image, text, and supervised-task settings.Wiki-3029 contains 3029 article classes with 200 sentences per article.
Unsupervised performance on Wiki-3029 is very close to supervised performance, while CIFAR-100 performance is respectable overall and good for binary classification.
Almost 4% and 5% gains over supervised training occur on the 100-way and average binary tasks, respectively, with only 50 labeled samples.
Increasing unlabeled data and negative samples improves representations, but many negative examples eventually stop helping.
Larger similarity blocks improve CIFAR-100 and Wiki-3029 accuracy, and CURL outperforms QT on IMDb.CURL is evaluated as the paper’s large-block contrastive method against QT.

9. Conclusion

The paper presents contrastive learning as a framework for understanding when unlabeled similarity information yields useful representations and downstream guarantees. Experiments primarily support this framework, while the authors identify efficiency and modeling extensions as open directions.

The framework formalizes guarantees and limitations for representations learned through contrastive objectives.
The analysis studies relationships among loss minimizers and training generalization sample complexity rather than efficient loss minimization.
Potential extensions include metric structure among latent classes and connections to meta-learning and transfer learning.
The authors use experiments mainly to illustrate and support the framework, while noting improvements to sentence embeddings as one practical example.

A.4. Proof of Proposition 6.2

This appendix proves the formal theorem for the larger-block contrastive-learning setting by decomposing unsupervised loss into supervised-task, contrastive, deviation, and generalization terms. The proof also identifies an intrinsic lower bound caused by repeated negative classes.

The proof establishes the formal statement corresponding to Theorem 6.1 for an empirical minimizer of the unsupervised loss.
The argument decomposes the loss into a supervised-task component and terms measuring cross-class contrast and intraclass deviation.
Convexity and task decomposition handle repeated classes before symmetrization produces the desired supervised-task bound.
Rademacher-complexity bounds control the generalization error uniformly over the function class.
The unsupervised loss cannot approach zero arbitrarily closely because negative samples can repeat the positive class with nonzero probability.

B.2. Competitive Bound

The paper establishes a competitive bound for supervised performance using the unsupervised representation-learning objective, under distributional and representation assumptions.

B.2. Competitive Bound: The proof uses multiclass hinge loss with margin γ and derives γ from representation complexity, variance, and the number of classes.The displayed definitions include γ(f), α, β, and η under the section’s assumptions.
B.2. Competitive Bound: The task distribution is formed by sampling class tuples under conditioning events, with D′ approximating D when I+ is empty with high probability.The construction also tracks the maximum conditional class probability and the minimum task-class probability.
B.2. Competitive Bound: The bound compares the learned representation against a benchmark quantity defined over tasks and class-distribution probabilities.The analysis introduces p_max(T), p_min(T), and task-dependent supervised-loss terms.
B.2. Competitive Bound: The result assumes f(X) is direction-wise subgaussian within every class and that representations have bounded maximum norm.These conditions appear in the stated lemma for all f in the representation class.
B.2. Competitive Bound: The proof bounds the expected hinge loss by combining a probability decomposition with subgaussian tail and union-bound estimates.The resulting inequality adds an ϵ term to the margin-dependent expression.

C. Examples for Section 6.2

The examples show that increasing the number of negative samples can make the unsupervised objective select a suboptimal representation, even when perfect class separation is available.

C. Examples for Section 6.2: The first example concerns k = Ω(|C|), where the algorithm selects a suboptimal representation despite an available representation that separates every class.The example uses hinge loss, and the same construction extends to logistic loss.
C. Examples for Section 6.2: When k = Ω(n), collisions between positive and negative classes occur with constant probability, increasing the unsupervised loss of the separating representation.For sufficiently large r, the construction gives L_un(f) = Ω(r^2) > 1 = L_un(f0).
C. Examples for Section 6.2: Replicating the construction into clusters of classes extends the failure case to k = o(|C|).The replicated setting contains n^2 classes arranged into clusters, so collisions can remain relevant below the total class count.
C. Examples for Section 6.2: The controlled text experiment uses 3029 filtered Wikipedia articles, sampling 200 sentences per article with a 70%/10%/20% split.The representation model is a 300-dimensional bidirectional GRU initialized with fixed pretrained CC GloVe embeddings and dropout 0.3.