Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Self-Supervised & Contrastive Learning

Learning from the data’s own structure.

A contrastive model never sees a label, yet a linear classifier on its features can rival a fully supervised network. Its loss is a softmax over a batch, and that softmax is secretly a bound on mutual information, one that can never certify more than the logarithm of the batch size. This lesson proves the bound and its ceiling, then turns to the sharper question the bound cannot answer: why do these features transfer?

What you’ll learn

  • Define the InfoNCE objective precisely, prove I(X;Y)≥log⁡N−LNI(X;Y)\ge\log N-\mathcal L_N, and identify the optimal critic.
  • Explain the log⁡N\log N ceiling and the formal limits on estimating mutual information from samples.
  • State the alignment–uniformity limit of the contrastive loss and the role of the temperature.
  • Derive the spectral contrastive loss as a low-rank factorization of the augmentation graph, and compare non-contrastive methods.

InfoNCE bounds mutual information

DerivationProof
  1. I(X;Y1:N)=I(X;Y1)+I(X;Y2:N∣Y1)=I(X;Y)+0I(X;Y_{1:N})=I(X;Y_1)+I(X;Y_{2:N}\mid Y_1)=I(X;Y)+0

    The negatives are independent of (X,Y1)(X,Y_1), so by the chain rule they add no information:

  2. I(X;Y1:N)=Elog⁡q(Y1:N∣X)p(Y1:N)+EX DKL(p(⋅∣X) ∥ q(⋅∣X)) ≥ Elog⁡q(Y1:N∣X)p(Y1:N)I(X;Y_{1:N})=\E\log\frac{q(Y_{1:N}\mid X)}{p(Y_{1:N})}+\E_X\,\KL\big(p(\cdot\mid X)\,\|\,q(\cdot\mid X)\big)\ \ge\ \E\log\frac{q(Y_{1:N}\mid X)}{p(Y_{1:N})}

    For any conditional density qq, the Barber–Agakov bound holds, because the gap is an expected KL divergence:

  3. q(y1:N∣x)=∏j=1Np(yj)⋅N ef(x,y1)∑j=1Nef(x,yj)q(y_{1:N}\mid x)=\prod_{j=1}^Np(y_j)\cdot\frac{N\,e^{f(x,y_1)}}{\sum_{j=1}^Ne^{f(x,y_j)}}

    Choose qq by reweighting the product of marginals with the critic's softmax. It is normalized: under ∏jp(yj)\prod_jp(y_j) the NN softmax weights are exchangeable and sum to 11, so each has mean 1/N1/N:

  4. I(X;Y) ≥ Elog⁡N ef(x,y1)∑jef(x,yj)=log⁡N−LN(f)■I(X;Y)\ \ge\ \E\log\frac{N\,e^{f(x,y_1)}}{\sum_je^{f(x,y_j)}}=\log N-\mathcal L_N(f)\qquad\blacksquare

    Substituting, the product of marginals cancels and what remains is log⁡N\log N minus the loss. The softmax weight is at most 11, so the right side is at most log⁡N\log N:

  5. log⁡N−LN(f⋆)=Elog⁡r(x,y1)−Elog⁡(1N∑jr(x,yj)) →N→∞ I(X;Y)\log N-\mathcal L_N(f^\star)=\E\log r(x,y_1)-\E\log\Big(\tfrac1N\textstyle\sum_jr(x,y_j)\Big)\ \xrightarrow{N\to\infty}\ I(X;Y)

    For the optimal critic: the posterior probability that candidate ii is the positive is r(x,yi)/∑jr(x,yj)r(x,y_i)/\sum_jr(x,y_j) with r=p(y∣x)/p(y)r=p(y\mid x)/p(y), and a cross-entropy is minimized by the true posterior. With f⋆=log⁡rf^\star=\log r, the law of large numbers sends 1N∑jr(x,yj)→Eyr(x,y)=1\frac1N\sum_jr(x,y_j)\to\E_{y}r(x,y)=1, leaving Elog⁡r=I(X;Y)\E\log r=I(X;Y).

Predict before you look

A contrastive run uses N=4096N=4096 candidates per anchor. Whatever the encoder, what is the largest mutual information, in nats, that its InfoNCE bound can certify?

Show the answer

8.3

ln⁡4096=12ln⁡2≈8.32\ln4096=12\ln2\approx8.32 nats, exactly 12 bits. Two views of a photograph may share far more information than that, so the bound saturates long before it measures it.

The ceiling is not a quirk of InfoNCE. McAllester and Stratos (2020) proved that no distribution-free, high-confidence lower bound on mutual information estimated from NN samples can exceed O(log⁡N)\order{\log N}. Variational bounds without the ceiling, such as the Donsker–Varadhan bound used by MINE or the Nguyen–Wainwright–Jordan bound, pay with estimator variance that grows exponentially in the true information (Poole et al., 2019; Song & Ermon, 2020).

Alignment, uniformity and temperature

The proof is one line: with s=g(x)⊤g(⋅)/τs=g(x)^\top g(\cdot)/\tau bounded by 1/τ1/\tau, log⁡((es++∑i≤Mesi−)/M)\log\big((e^{s^+}+\sum_{i\le M}e^{s_i^-})/M\big) converges to log⁡Ees−\log\E e^{s^-} by the law of large numbers, since the single positive term vanishes after dividing by MM. The decomposition explains the two forces: positives pulled together, everything else spread out as evenly as the sphere allows, so that no information-carrying directions collapse. Wang and Isola's direct estimates of the two terms track linear-probe accuracy across many trained encoders.

The temperature sets how the push is distributed. The gradient weight on negative jj is its softmax probability, ∝esj\propto e^{s_j}, so a small τ\tau concentrates almost all of it on the hardest negatives. That sharpens local separation, but other images of the anchor's own class are also negatives, and pushing hard on them can split semantically similar examples apart.

Check your understanding

With unit vectors and similarities z⊤zj\mathbf z^\top\mathbf z_j, consider τ⋅L\tau\cdot\mathcal L as τ→0\tau\to0. What does the scaled loss become?

  1. The average similarity to all negatives
  2. max⁡(0, max⁡jz⊤zj−−z⊤z+)\max\big(0,\ \max_j\mathbf z^\top\mathbf z_j^--\mathbf z^\top\mathbf z^+\big): a hinge on the single hardest negative
  3. Zero for every encoder
  4. The similarity to the easiest negative
Show the answer

B. max⁡(0, max⁡jz⊤zj−−z⊤z+)\max\big(0,\ \max_j\mathbf z^\top\mathbf z_j^--\mathbf z^\top\mathbf z^+\big): a hinge on the single hardest negative

τlog⁡∑jesj/τ→max⁡jsj\tau\log\sum_je^{s_j/\tau}\to\max_js_j (log-sum-exp tends to the maximum), so τL→max⁡(z⊤z+,max⁡jz⊤zj−)−z⊤z+\tau\mathcal L\to\max\big(\mathbf z^\top\mathbf z^+,\max_j\mathbf z^\top\mathbf z_j^-\big)-\mathbf z^\top\mathbf z^+, a triplet-style hinge on the hardest negative. At large τ\tau the weights flatten toward all negatives equally.

Why do contrastive features transfer?

Mutual information alone cannot be the explanation. It is invariant under invertible maps, so an encoder that scrambles its input bijectively keeps all the information while destroying linear separability; Tschannen et al. (2020) also found that tighter MI estimators can yield worse representations. What matters is which features the encoder class and the augmentations make easy. Two lines of theory make this precise.

DerivationThe spectral contrastive loss is matrix factorization (HaoChen, Wei, Gaidon & Ma, 2021)
  1. L(f)=−2 E(x,x+)[f(x)⊤f(x+)]+Ex,x′[(f(x)⊤f(x′))2]=−2∑x,x′wxx′f(x)⊤f(x′)+∑x,x′wxwx′(f(x)⊤f(x′))2\mathcal L(f)=-2\,\E_{(x,x^+)}\big[f(x)^\top f(x^+)\big]+\E_{x,x'}\big[(f(x)^\top f(x'))^2\big]=-2\sum_{x,x'}w_{xx'}f(x)^\top f(x')+\sum_{x,x'}w_xw_{x'}\big(f(x)^\top f(x')\big)^2

    Build the augmentation graph on augmented inputs: wxx′w_{xx'} is the probability that xx and x′x' are two views of the same natural example, and wx=∑x′wxx′w_x=\sum_{x'}w_{xx'}. For an encoder ff into Rk\R^k, define the spectral contrastive loss:

  2. L(f)=−2tr⁡(AˉFF⊤)+∥FF⊤∥F2=∥Aˉ−FF⊤∥F2−∥Aˉ∥F2\mathcal L(f)=-2\operatorname{tr}\big(\bar AFF^\top\big)+\norm{FF^\top}_F^2=\norm{\bar A-FF^\top}_F^2-\norm{\bar A}_F^2

    Collect the rows wx f(x)⊤\sqrt{w_x}\,f(x)^\top into a matrix FF and normalize the adjacency, Aˉxx′=wxx′/wxwx′\bar A_{xx'}=w_{xx'}/\sqrt{w_xw_{x'}}. Both sums become matrix expressions:

  3. min⁡fL(f)  ⟺  min⁡rank⁡(FF⊤)≤k∥Aˉ−FF⊤∥F\min_f\mathcal L(f)\iff\min_{\rank(FF^\top)\le k}\norm{\bar A-FF^\top}_F

    So minimizing the loss over all encoders is the best rank-kk approximation of Aˉ\bar A: by Eckart–Young, FF spans its top-kk eigenvectors, the same spectral embedding as in spectral clustering. If augmentations rarely cross class boundaries, these eigenvectors are nearly constant on each class, and HaoChen et al. bound the linear-probe error by the cross-class augmentation probability divided by a spectral gap of the graph.

The picture these results share: augmentations define which inputs count as "the same", the loss learns a spectral embedding of that similarity graph, and a linear probe succeeds when classes are nearly disconnected in it. The graph is never written down, and the encoder's inductive biases decide how it is extrapolated to unseen inputs, which current theory captures only partially.

Beyond negatives, and the state of the art

MethodObjectiveWhat prevents collapse
BYOL (2020), SimSiam (2021)predict the other view's embedding: ∥h(z1)/∥h(z1)∥−sg⁡(z2)/∥z2∥∥2\norm{h(z_1)/\norm{h(z_1)}-\operatorname{sg}(z_2)/\norm{z_2}}^2the predictor hh and the stop-gradient sg⁡\operatorname{sg} (plus a moving-average target in BYOL); linear analyses show collapse is avoided by the learning dynamics, not by the loss (Tian, Chen & Ganguli, 2021)
Barlow Twins (2021)push the cross-correlation matrix CC of the two views' embeddings toward II: ∑i(1−Cii)2+λ∑i≠jCij2\sum_i(1-C_{ii})^2+\lambda\sum_{i\ne j}C_{ij}^2decorrelated dimensions cannot all carry the same signal
VICReg (2022)invariance (squared distance) + a hinge keeping each dimension's standard deviation above 1 + off-diagonal covariance penaltythe variance term forbids constant outputs
DINO (2021)a student matches a momentum teacher's sharpened, centered softmax outputs on different cropscentering and sharpening balance each other
Masked modeling (BERT 2019, MAE 2022)reconstruct hidden tokens or patchesthe target is the input itself, so a constant code cannot succeed
In language, next-token prediction is the dominant self-supervised objective; contrastive losses remain central for retrieval and for aligning modalities, as in Contrastive Vision–Language Models.

Key takeaways

  • InfoNCE with NN candidates satisfies I(X;Y)≥log⁡N−LNI(X;Y)\ge\log N-\mathcal L_N; the optimal critic is the log density ratio, and the bound is tight only as N→∞N\to\infty.
  • The bound is capped at log⁡N\log N, and no high-confidence distribution-free estimator does better than O(log⁡N)\order{\log N}; uncapped variational bounds pay in variance.
  • As the number of negatives grows, the loss splits into alignment and uniformity on the sphere; small temperatures focus on the hardest negatives.
  • Mutual information cannot explain transfer by itself. Latent-class bounds and the spectral view, a low-rank factorization of the augmentation graph, tie the loss to linear-probe error.
  • Non-contrastive methods avoid collapse through predictors and stop-gradients, decorrelation or variance penalties; masked modeling reconstructs the input instead.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

InfoNCE is run with a single negative per anchor (N=2N=2). Whatever the critic, what is the most mutual information it can certify?

  1. ln⁡2\ln2 nats, i.e. one bit
  2. 22 nats
  3. Unlimited, given a perfect critic
  4. Nothing: one negative gives no bound
Show the answer

A. ln⁡2\ln2 nats, i.e. one bit

I≥log⁡N−LN≤log⁡2I\ge\log N-\mathcal L_N\le\log2: the task is a binary choice, and a perfect score proves only that the views share at least one bit.

Question 2

Which critic minimizes the InfoNCE loss?

  1. f(x,y)=log⁡p(x,y)f(x,y)=\log p(x,y)
  2. f(x,y)=p(y∣x)f(x,y)=p(y\mid x)
  3. Any critic that is symmetric in xx and yy
  4. f(x,y)=log⁡p(y∣x)p(y)+c(x)f(x,y)=\log\frac{p(y\mid x)}{p(y)}+c(x) for any function cc
Show the answer

D. f(x,y)=log⁡p(y∣x)p(y)+c(x)f(x,y)=\log\frac{p(y\mid x)}{p(y)}+c(x) for any function cc

The loss is the cross-entropy of identifying the positive; the true posterior is r(x,yi)/∑jr(x,yj)r(x,y_i)/\sum_jr(x,y_j) with r=p(y∣x)/p(y)r=p(y\mid x)/p(y), which the softmax reproduces exactly when f=log⁡rf=\log r up to a term depending only on xx, since that term cancels.

Question 3

In the large-MM limit of the contrastive loss, what does the uniformity term reward?

  1. Mapping positives to the same point
  2. Embeddings spread as evenly as possible over the unit sphere
  3. Embeddings concentrated near one pole
  4. Small embedding norms
Show the answer

B. Embeddings spread as evenly as possible over the unit sphere

Exlog⁡Ex−eg(x)⊤g(x−)/τ\E_x\log\E_{x^-}e^{g(x)^\top g(x^-)/\tau} is small when typical pairs of embeddings have low similarity, which on the sphere means a near-uniform distribution; it is what prevents collapse.

Question 4

Minimizing the spectral contrastive loss over all encoders into Rk\R^k is equivalent to which problem?

  1. Maximizing the mutual information between views
  2. kk-means clustering of the augmented inputs
  3. The best rank-kk approximation of the normalized augmentation-graph adjacency Aˉ\bar A
  4. PCA of the raw input pixels
Show the answer

C. The best rank-kk approximation of the normalized augmentation-graph adjacency Aˉ\bar A

L(f)=∥Aˉ−FF⊤∥F2−∥Aˉ∥F2\mathcal L(f)=\norm{\bar A-FF^\top}_F^2-\norm{\bar A}_F^2, so the optimum spans the top-kk eigenvectors of Aˉ\bar A, a spectral embedding of the augmentation graph.

Further reading

  • A. van den Oord, Y. Li & O. Vinyals, "Representation learning with contrastive predictive coding," arXiv:1807.03748 (2018).
  • B. Poole, S. Ozair, A. van den Oord, A. A. Alemi & G. Tucker, "On variational bounds of mutual information," ICML (2019).
  • T. Wang & P. Isola, "Understanding contrastive representation learning through alignment and uniformity on the hypersphere," ICML (2020).
  • J. Z. HaoChen, C. Wei, A. Gaidon & T. Ma, "Provable guarantees for self-supervised deep learning with spectral contrastive loss," NeurIPS (2021).
  • R. Balestriero et al., "A cookbook of self-supervised learning," arXiv:2304.12210 (2023).