Self-supervised and contrastive representations

Write $\ln$ for the natural logarithm and ${\log }_{2}u:=\ln (u)\mathrm{/}\ln (2)$ for $u>0$. Define the one-negative hinge and logistic losses by ${\mathrm{\ell }}_{\mathrm{h}}(t):=(1+t{)}_{+}$ and ${\mathrm{\ell }}_{\mathrm{l}\mathrm{o}\mathrm{g}}(t):={\log }_2(1+e^t)$ for $t\in \mathbb{R}$, where $r_{+}:=\max \{r,0\}$. Put $L_0:=1+1\mathrm{/}\ln (2)$. Each loss is convex, nondecreasing, $L_0$-Lipschitz, and has value $1$ at $0$. For $R>0$ and either loss $\mathrm{\ell }$, define $B_{\mathrm{\ell },R}:=\mathrm{\ell }(2R^2)-\mathrm{\ell }(-2R^2)$. Then $0<B_{\mathrm{\ell },R}\le 4L_0{R}^2$.

The natural logarithm as the inverse of the exponential function

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: fix the natural-logarithm convention and its strict monotonicity.

The exponential function is smooth and $(\exp {)}^{\mathrm{\prime }}=\exp$

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t

Sum, product, quotient, and chain rules from difference quotients: supply the derivatives used for the logistic loss.

A twice-differentiable function on an open interval is convex if and only if its second derivative is nonnegative: nonnegative second derivative implies convexity on an open interval.

Mean value theorem on a closed real interval: a derivative bound gives a Lipschitz bound on each closed interval.

Saunshi et al., Section 2.2, one-negative hinge and logistic losses.

MIT OpenCourseWare, Real Analysis, Lectures 15–16.

Let $m,d\ge 1$, let $V$ be a nonempty bounded subset of $({\mathbb{R}}^d{)}^m$, and let $h_i:{\mathbb{R}}^d\to \mathbb{R}$ be $L$-Lipschitz for one common $L\ge 0$. Let $({\epsilon }_i{)}_{i=1}^m$ and $({\eta }_{it}{)}_{1\le i\le m,1\le t\le d}$ be independent uniform signs in $\{-1,+1\}$. Writing $v_i=(v_{i1},\dots ,v_{id})$, the one-sided averages satisfy

${\mathbb{E}}_{\epsilon }{\sup }_{v\in V}{\sum }_{i=1}^m{\epsilon }_i{h}_i(v_i)\le \sqrt{3}L{\mathbb{E}}_{\eta }{\sup }_{v\in V}{\sum }_{i=1}^m{\sum }_{t=1}^d{\eta }_{it}{v}_{it}\mathrm{.}$

Neither supremum uses an absolute value, and no condition $h_i(0)=0$ is imposed. The bound holds for finite or infinite bounded $V$; all displayed suprema are finite.

Cauchy-Schwarz for finite random variables: $\mathbb{E}[XY{]}^2\le \mathbb{E}[X^2]\mathbb{E}[Y^2]$: supplies Cauchy–Schwarz for the finite uniform sign spaces used in the proof.

Maurer, Theorem 3 and Corollary 4, complete vector-contraction proof: proves the sharper $\sqrt{2}L$ version through a one-coordinate comparison and induction.

Lei et al., Lemma A.1, complete vector-contraction proof: gives an independent contrastive-learning application of the vector-contraction inequality.

Let $(\mathcal{C},{\mathcal{C}}_0,\rho )$ be a measurable probability space and $(\mathcal{X},\mathcal{A})$ a measurable space. For each class $c\in \mathcal{C}$, let $D_c$ be a probability measure on $(\mathcal{X},\mathcal{A})$ and assume $c\mapsto D_c(A)$ is measurable for every $A\in \mathcal{A}$. Assume the displayed mixtures define probability measures. The positive-pair law $D_{\mathrm{s}\mathrm{i}\mathrm{m}}$ and negative marginal $D_{\mathrm{n}\mathrm{e}\mathrm{g}}$ are specified by

$D_{\mathrm{s}\mathrm{i}\mathrm{m}}(A\times B):={\int }_{\mathcal{C}}{D}_c(A)D_c(B)\rho (dc),D_{\mathrm{n}\mathrm{e}\mathrm{g}}(A):={\int }_{\mathcal{C}}{D}_c(A)\rho (dc)$

for measurable $A,B\in \mathcal{A}$. Equivalently, draw $C\sim \rho$ and then draw $X,X^{+}$ independently with law $D_C$ for a positive pair; draw a fresh independent class $C^{\mathrm{\prime }}\sim \rho$ and $X^{-}\sim D_{C^{\mathrm{\prime }}}$ for one negative. The class labels are latent: the learner observes the pair and negative data, not their classes.

Let $d\ge 1$, $R>0$, and let $\mathcal{F}$ be a nonempty class of measurable maps $f:\mathcal{X}\to {\mathbb{R}}^d$ satisfying ${\sup }_{x\in \mathcal{X}}\parallel f(x){\parallel }_2\le R$. Use either one-negative loss ${\mathrm{\ell }}_{\mathrm{h}}(t)=(1+t{)}_{+}$ or ${\mathrm{\ell }}_{\mathrm{l}\mathrm{o}\mathrm{g}}(t)={\log }_2(1+e^t)$ from the immediately preceding loss-properties lemma. The contrastive score and population loss are

$q_f(x,x^{+},x^{-}):=f(x{)}^{\mathrm{\top }}(f(x^{-})-f(x^{+})),L_{\mathrm{u}\mathrm{n}}(f):={\mathbb{E}}_{(X,X^{+})\sim D_{\mathrm{s}\mathrm{i}\mathrm{m}},X^{-}\sim D_{\mathrm{n}\mathrm{e}\mathrm{g}}}[\mathrm{\ell }(q_f(X,X^{+},X^{-}))]\mathrm{.}$

For $M\ge 1$, an observed sample is $S=((x_j,x_j^{+},x_j^{-}){)}_{j=1}^M$ of $M$ independent triplets with common law $D_{\mathrm{s}\mathrm{i}\mathrm{m}}\otimes D_{\mathrm{n}\mathrm{e}\mathrm{g}}$, and its empirical loss is ${\widehat{L}}_{\mathrm{u}\mathrm{n}}(f):=M^{-1}{\sum }_{j=1}^M\mathrm{\ell }(q_f(x_j,x_j^{+},x_j^{-}))$. For this sample define the unnormalized vector Rademacher complexity

${\mathcal{R}}_S(\mathcal{F}):={\mathbb{E}}_{\epsilon }{\sup }_{f\in \mathcal{F}}{\sum }_{j=1}^M{\sum }_{t=1}^d({\epsilon }_{jt0}{f}_t(x_j)+{\epsilon }_{jt+}{f}_t(x_j^{+})+{\epsilon }_{jt-}{f}_t(x_j^{-})),$

where every ${\epsilon }_{jt0},{\epsilon }_{jt+},{\epsilon }_{jt-}$ is an independent uniform sign. This is the one-sided convention with no absolute value and no $1\mathrm{/}M$ factor.

All vector and matrix expectations in this definition are taken entrywise in finite dimensions. The bound on $f$ makes each coordinate of $f(X)$ and every product defining a covariance entry integrable.

Let $C_{+},C_{-}\sim \rho$ be independent class draws and set $\tau :=\mathrm{Pr}(C_{+}=C_{-})<1$. Assume the diagonal $\mathrm{\Delta }:=\{(c,c):c\in \mathcal{C}\}$ and each ${\mathrm{\Delta }}_A:=\{(c,c):c\in A\}$, $A\in {\mathcal{C}}_0$, are measurable. The average binary task draws $(C_{+},C_{-})$ conditional on $C_{+}\mathrm{\ne }{C}_{-}$, then samples a label $Y$ uniformly from $\{+1,-1\}$ and an input $X$ from $D_{C_{+}}$ if $Y=+1$ or $D_{C_{-}}$ if $Y=-1$. For a vector representation $f$, a binary linear classifier uses a weight vector $w\in {\mathbb{R}}^d$ and loss $\mathrm{\ell }(-Y{w}^{\mathrm{\top }}f(X))$. Define $L_{\mathrm{s}\mathrm{u}\mathrm{p}}(f)$ as the average over tasks of the infimum of this risk over $w\in {\mathbb{R}}^d$. Write ${\mu }_c:={\mathbb{E}}_{X\sim D_c}f(X)$ and define the class-mean classifier by $w_{\mu }={\mu }_{C_{+}}-{\mu }_{C_{-}}$; its average risk is $L_{\mathrm{s}\mathrm{u}\mathrm{p}}^{\mu }(f)$. For $\gamma >0$, write $L_{\gamma ,\mathrm{s}\mathrm{u}\mathrm{p}}^{\mu }(f)$ for the same mean-classifier risk with margin loss ${\mathrm{\ell }}_{\gamma }(t):=(1+t\mathrm{/}\gamma {)}_{+}$ in place of $\mathrm{\ell }$.

For $\tau >0$, let $L_{\mathrm{u}\mathrm{n}}^{=}(f)$ and $L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}(f)$ be the conditional contrastive risks given $C_{+}=C_{-}$ and $C_{+}\mathrm{\ne }{C}_{-}$, respectively. Let $\nu$ be the class law conditioned on the collision event, namely $\nu (A):=(\rho \otimes \rho )({\mathrm{\Delta }}_A)\mathrm{/}\tau$ for $A\in {\mathcal{C}}_0$; for an atomic class law this gives $\nu (\{c\})=\rho (\{c\}{)}^2\mathrm{/}\tau$. Define ${\mathrm{\Sigma }}_f(c):={\mathbb{E}}_{X\sim D_c}[(f(X)-{\mu }_c)(f(X)-{\mu }_c{)}^{\mathrm{\top }}]$ and

$s(f):={\mathbb{E}}_{C\sim \nu }[\sqrt{\parallel {\mathrm{\Sigma }}_f(C){\parallel }_{\mathrm{o}\mathrm{p}}}{\mathbb{E}}_{X\sim D_C}\parallel f(X){\parallel }_2],\parallel \mathrm{\Sigma }{\parallel }_{\mathrm{o}\mathrm{p}}:={\max }_{\parallel u{\parallel }_2=1}\parallel \mathrm{\Sigma }u{\parallel }_2\mathrm{.}$

The assumed measurability of $\mathrm{\Delta }$ and every ${\mathrm{\Delta }}_A$ makes the displayed collision event and conditional class law well-defined; disjoint class sets give disjoint ${\mathrm{\Delta }}_A$, so the formula for $\nu$ is countably additive and has total mass one. Assume also that $c\mapsto {\mu }_c$ and $c\mapsto {\mathrm{\Sigma }}_f(c)$ are measurable for each $f$, and that the displayed class-conditional risks and random suprema used below are measurable.

If $\tau =0$, there is no collision term; set $s(f):=0$ and use $L_{\mathrm{u}\mathrm{n}}(f)=L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}(f)$. Any empirical minimizer or approximate minimizer used below is separately assumed to be a measurable selector; no selector-existence claim is part of this definition.

Probability measures and probability spaces: fixes probability laws and their total mass.

Expectation of a nonnegative or integrable random variable: supplies scalar expectations; vector and matrix expectations use the entrywise convention stated above.

Supervised prediction problems

Population and empirical risk: supply the measurable prediction-problem and population/empirical risk conventions.

Population and empirical risks are measurable: establishes measurability of fixed-predictor risks in the supervised interface.

Identical distribution and IID families

Independent random elements have product joint law: fix IID sampling and the product-law convention for independent draws.

One-sided Rademacher complexity: supplies the one-sided sign-supremum convention; the vector form above is unnormalized as in the source.

Moments, variance, and covariance on a probability space

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: define the within-class covariance matrix and its operator norm.

Convexity, Lipschitz bounds, and oscillation of the source contrastive losses: defines the source hinge/logistic losses and the common constant $L_0$.

Saunshi et al., Sections 2–5, latent classes, pair/triplet sampling, mean classifier and one-negative objective.

Lei et al., Sections 2–4, contrastive sampling and a distinct unsupervised-loss generalization analysis.

The two class roots are sampled independently. The arrows show conditional sampling laws, not deterministic functions; $X$ and $X^{+}$ are independent conditional on $C_{+}$, and the negative example has its own independent class draw.

The transfer claims below concern the source's average binary tasks, one independent marginal negative, the stated hinge/logistic losses, and the class-mean linear classifier. They do not assert multiclass top-1 accuracy, universal invariance, an attained population minimizer, or a guarantee for empirical SimCLR outcomes. The source treats multiple-negative and block-similarity extensions separately.

Saunshi et al., Sections 4–6 and Supplementary Appendix B.

Chen et al., Sections 2–4, SimCLR's batch NT-Xent objective and reported experiments.

Assume the one-negative latent-class model has $\tau <1$. Let $C_{+},C_{-}$ be independent with law $\rho$, conditioned on $C_{+}\mathrm{\ne }{C}_{-}$, let $X,X^{+}$ be independent with law $D_{C_{+}}$, and let $X^{-}$ be independent with law $D_{C_{-}}$. For every measurable bounded representation $f$ and either source hinge or logistic loss, the average binary-task mean-classifier risk satisfies

$L_{\mathrm{s}\mathrm{u}\mathrm{p}}^{\mu }(f)\le L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}(f)\mathrm{.}$

Here each binary task uses a uniform label from its two classes, and $L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}$ is the contrastive loss conditional on different positive and negative classes.

Latent-class contrastive representation learning: defines the latent-class sampling laws, binary-task risk, mean classifier, and distinct-class contrastive loss.

Convexity, Lipschitz bounds, and oscillation of the source contrastive losses: establishes convexity of both source losses.

Saunshi et al., Lemma 4.3 and complete proof: proves the same one-negative Jensen comparison for uniformly labeled binary tasks.

In the one-negative latent-class model, for every bounded representation $f$ and either source loss, the population contrastive loss decomposes as

$L_{\mathrm{u}\mathrm{n}}(f)=\tau L_{\mathrm{u}\mathrm{n}}^{=}(f)+(1-\tau )L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}(f)\mathrm{.}$

If $\tau >0$, the same-class conditional loss obeys

$1\le L_{\mathrm{u}\mathrm{n}}^{=}(f)\le 1+c_{0}s(f),c_0:=\sqrt{2}{L}_0,$

where $L_0$ is the common Lipschitz constant of the hinge and logistic losses. If $\tau =0$, then $L_{\mathrm{u}\mathrm{n}}(f)=L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}(f)$ and the model's convention is $s(f)=0$.

Latent-class contrastive representation learning: defines $\tau$, the conditional collision/distinct losses, the covariance matrix, and $s(f)$.

Convexity, Lipschitz bounds, and oscillation of the source contrastive losses: both losses are convex, $L_0$-Lipschitz, and have value $1$ at zero.

Moments, variance, and covariance on a probability space

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: supply the covariance and operator-norm conventions.

Saunshi et al., Equations (8)–(9) and Lemma 4.4.

Saunshi et al., Supplementary Lemma A.1 and complete proof.

In the one-negative latent-class model, fix a bounded representation $f$ with ${\sup }_x\mathrm{\parallel }f(x){\mathrm{\parallel }}_2\le R$, where $R>0$. Use the hinge loss ${\mathrm{\ell }}_{\mathrm{h}}(t)=(1+t{)}_{+}$. Suppose that for every class $c$, the centered vector $f(X)-{\mu }_c$, for $X\sim D_c$, is sub-Gaussian in every direction with proxy ${\sigma }^2\ge 0$. For $0<ϵ\le 1$, define

$\gamma :=\{\begin{array}{ll}1+2R\sigma \sqrt{2\ln R+\ln (3\mathrm{/}ϵ)},& R\ge 1,\\ 1+2R\sigma \sqrt{\ln (3\mathrm{/}ϵ)},& 0<R<1.\end{array}$

Then the contrastive risk conditioned on distinct positive and negative classes satisfies

$L_{\mathrm{u}\mathrm{n}}^{\mathrm{\ne }}(f)\le \gamma L_{\gamma ,\mathrm{s}\mathrm{u}\mathrm{p}}^{\mu }(f)+ϵ\mathrm{.}$

This comparison is for the hinge contrastive loss and its scaled hinge mean-classifier risk.

Latent-class contrastive representation learning: defines the one-negative score, class-conditional means, distinct-class contrastive risk and scaled hinge mean-classifier risk.

Sub-Gaussian variables and vectors, and sub-exponential variables: defines the centered vector sub-Gaussian proxy condition used for every class.

Convexity, Lipschitz bounds, and oscillation of the source contrastive losses: defines the hinge contrastive loss.

Saunshi et al., Lemma 5.1, main paper §5.2.

Saunshi et al., complete proof of Lemma 5.1, Supplementary Appendix A.2.

Assume the Axiom of Choice. In the one-negative latent-class model, fix $R>0$, a source loss $\mathrm{\ell }\in \{{\mathrm{\ell }}_{\mathrm{h}},{\mathrm{\ell }}_{\mathrm{l}\mathrm{o}\mathrm{g}}\}$, a sample size $M\ge 1$, and a sample $S$ of $M$ IID triplets. Assume the loss risks and all sample, independent-copy, and sign suprema below are measurable. Let $B_{\mathrm{\ell },R}=\mathrm{\ell }(2R^2)-\mathrm{\ell }(-2R^2)$ and define

${\mathrm{\Gamma }}_M(S,\delta ):=\frac{2\sqrt{18}{L}_{0}R{\mathcal{R}}_S(\mathcal{F})}{M}+3B_{\mathrm{\ell },R}\sqrt{\frac{\ln (4\mathrm{/}\delta )}{2M}},0<\delta <1.$

With probability at least $1-\delta$ over $S$,

$\mathrm{\forall }f\in \mathcal{F},\mathrm{\mid }{L}_{\mathrm{u}\mathrm{n}}(f)-{\widehat{L}}_{\mathrm{u}\mathrm{n}}(f)\mathrm{\mid }\le {\mathrm{\Gamma }}_M(S,\delta )\mathrm{.}$

Here ${\mathcal{R}}_S(\mathcal{F})$ is the unnormalized vector Rademacher complexity of the three embeddings in each triplet.

Latent-class contrastive representation learning: fixes the one-negative triplet loss, IID sample, representation bound and unnormalized vector Rademacher complexity.

Convexity, Lipschitz bounds, and oscillation of the source contrastive losses: supplies $L_0$ and the positive oscillation $B_{\mathrm{\ell },R}$ of either source loss on the score range.

A finite-dimensional vector contraction bound for one-sided Rademacher averages: bounds the one-sided vector Rademacher average, with constant $\sqrt{3}$.

Rademacher uniform generalization bounds: supplies the two-sided high-probability deviation bound for measurable $[0,1]$-valued classes under AC.

Saunshi et al., Supplementary Appendix A.3: applies vector contraction and bounded-loss uniform generalization to the contrastive class.

Mohri et al., Theorem 3.3 and complete proof, printed pp. 30–33: proves the bounded-loss Rademacher uniform-deviation step.

Maurer, Theorem 3, Corollary 4 and complete proof: gives a sharper vector-contraction constant; the proof here instead uses the local $\sqrt{3}$ lemma.