Skip to content

Statistical Consistency and Generalization of Contrastive Representation Learning

Conference: ICML 2026
arXiv: 2605.02116
Code: None
Area: Self-supervised / Representation Learning / Learning Theory
Keywords: Contrastive Learning, Statistical Consistency, Calibration Inequality, Generalization Bound, Number of Negative Samples

TL;DR

This work is the first to establish the Fisher/statistical consistency of contrastive representation learning (CRL), showing that "minimizing upstream contrastive loss is equivalent to optimal downstream AUC-type retrieval performance." It further provides sharp generalization bounds dependent on the number of positive samples \(n\) and negative samples \(m\): \(O(1/m+1/\sqrt n)\) (supervised) and \(O(1/\sqrt m+1/\sqrt n)\) (self-supervised). This theoretically explains, for the first time, why using tens of thousands of negatives in CLIP/SimCLR continues to improve performance.

Background & Motivation

Background: Foundational models such as CLIP, SimCLR, and MoCo are trained with a core objective of contrastive loss (Eq. 1), which takes the form of an InfoNCE/log-sum-exp pairwise ranking loss. The goal is to learn transferable representations by increasing the score \(s_w(x,y)\) for positive pairs \((x,y)\) and decreasing it for negative pairs \((x,y')\).

Limitations of Prior Work: Existing theory has three mutually contradictory gaps: (i) Only the "surrogate gap" has been proven—small contrastive risk implies small supervised loss under a linear probe—but statistical consistency (whether the optimal solution of contrastive loss converges to the downstream optimum as sample size grows) has not been established; (ii) Existing generalization bounds (Saunshi et al.) degrade monotonically with the number of negatives \(m\), e.g., \(O(m/\sqrt n)\) or \(O(\log m/\sqrt n)\), which contradicts empirical findings that SimCLR (8192 negatives) and CLIP (32768 negatives) benefit from large \(m\); (iii) There is almost no theoretical quantification of contrastive learning's downstream performance from a retrieval perspective, even though retrieval is the core application of CLIP.

Key Challenge: Contrastive loss is essentially a pairwise ranking loss, but prior analyses force it into a classification framework, losing the geometric structure of ranking and causing \(m\) to appear in the numerator.

Goal: Decompose into two steps: (a) Use an AUC-type ranking criterion \(\mathcal E(s)\) for downstream evaluation, prove Fisher consistency for contrastive loss, and provide a calibration inequality \(\mathcal E^*-\mathcal E(s)\lesssim\sqrt{L(s)-L^*}\); (b) Re-decompose the generalization error so that \(m\) appears in the denominator rather than the numerator.

Key Insight: Rewrite the inner log-mean-exp of the empirical contrastive risk \(\widehat L_S(s_w)\) as a strongly convex minimization problem over an auxiliary variable \(\mu\) (Lemma 4.2), interpret the inner error as a generalization problem for ERM, and use algorithmic stability to obtain \(O(1/m)\) instead of \(O(1/\sqrt m)\).

Core Idea: Replace the surrogate-gap with an AUC-type retrieval criterion, rewrite the log-sum-exp loss as an OCE (optimized certainty equivalent) form, and use stability arguments to derive a generalization bound of \(O(1/m+1/\sqrt n)\), thereby simultaneously resolving consistency, large negative sample benefit, and retrieval semantics.

Method

Overall Architecture

This is a purely theoretical work, with two main modules: 1. Consistency Module: Introduces the AUC-type downstream metric \(\mathcal E(s)=\Pr[s(x,y)>s(x,y')]+\tfrac12\Pr[s(x,y)=s(x,y')]\), characterizing the probability that a positive pair is ranked above a negative pair. It is shown that the global minimizer of the contrastive loss satisfies \(s^*(x,y)=\tau\log\frac{p_x^+(y)}{p_x^-(y)}+g(x)\) (Lemma 3.2), which also maximizes \(\mathcal E(s)\) (Lemma 3.3), thus establishing Fisher consistency. A monotonic chain then yields the calibration inequality \(\mathcal E^*-\mathcal E(s)\le\sqrt{2/\tau\,(L(s)-L^*)}\) (Thm 3.4). 2. Generalization Module: Decomposes the generalization gap along the outer (positive pair) + inner (negative pair) composite structure of the contrastive loss; the outer part uses Rademacher complexity to obtain \(O(1/\sqrt n)\); the inner part, via OCE rewriting and stability, yields \(O(1/m)\) for SCRL and \(O(1/\sqrt m)\) for SSCRL, which are then combined for the overall bound.

Key Designs

  1. AUC-type Downstream Criterion + Fisher Consistency Proof:

    • Function: Uses the pairwise ranking criterion \(\mathcal E(s)\) instead of "linear classification error," aligning the evaluation target with the pairwise geometry of contrastive loss.
    • Mechanism: Expresses \(L(s)\)'s pointwise solution over all measurable function classes as \(s^*=\tau\log(p^+/p^-)+g(x)\); since \(\log\) is monotonic, \(s^*(x,y)>s^*(x,y')\) iff \(p^+(y)/p^-(y)>p^+(y')/p^-(y')\), which is exactly the AUC optimal ranking condition. Thus, \(L(s_n)\to L^*\Rightarrow\mathcal E(s_n)\to\mathcal E^*\), achieving statistical consistency.
    • Design Motivation: Previous surrogate-gap results only compare "contrastive risk" with "supervised risk after linear probing," without guaranteeing convergence to the oracle as sample size grows. Using AUC as the natural downstream ranking closes the loop.

  2. OCE Rewriting + Algorithmic Stability for \(O(1/m)\) Inner Bound:

    • Function: Rewrites the inner term \(\tau\log\tfrac1m\sum_j\exp(\Delta_w/\tau)\), which is highly sensitive to the number of negatives, as a strongly convex minimization over an auxiliary scalar \(\mu\in[-2B,2B]\) (Lemma 4.2): \(\widehat L_S(s_w)=-\tau+\tfrac1n\sum_i\min_{|\mu_i|\le 2B}\bigl[\tfrac{\tau}{m}\sum_j\exp((\Delta-\mu_i)/\tau)+\mu_i\bigr]\).
    • Mechanism: After rewriting, the inner error becomes \(f(w,x,y)-\hat f(w,x,y)\), where \(\hat f\) is the ERM over \(m\) negatives and \(f\) is its population version. By strong convexity, the stability of the ERM solution \(\hat f\) relative to the optimum is \(O(1/m)\) (Bousquet-Elisseeff), so the supervised CRL inner bound is \(\sup_w|L_S(s_w)-\mathbb E\widehat L_S(s_w)|=O(1/m)\) (Lemma 4.3). In the self-supervised case, since negatives are shared across all anchors, there is no ERM decoupling, so only uniform convergence yields \(O(1/\sqrt m)\).
    • Design Motivation: Previous approaches using Hoeffding/uniform convergence to directly handle the \(\log\)-mean-\(\exp\) inevitably push \(m\) into the numerator (due to the sup operation); OCE transforms the sum into a decomposable strongly convex problem, enabling the \(1/m\) fast rate.

  3. Inner/Outer Decomposition + Rademacher Control of Outer Layer:

    • Function: Writes the overall generalization gap as \(L(s_w)-\widehat L(s_w)\le\underbrace{L(s_w)-\mathbb E\widehat L(s_w)}_{\text{inner}}+\underbrace{\mathbb E\widehat L(s_w)-\widehat L(s_w)}_{\text{outer}}\), decoupling the independent perturbations of "negative sampling" and "anchor sampling."
    • Mechanism: Introduces the aggregation function \(k_w(x,y,y'_1,\dots,y'_m)=\tau\log\tfrac1m\sum_j\exp(\Delta_w/\tau)\), and uses the Rademacher complexity \(\mathcal R_S(\mathcal K)\) of deep networks to obtain the outer bound \(O(\sqrt{\log(1/\delta)/n})\), making the outer bound completely independent of \(m\). Combining both yields the main theorem Thm 4.5: \(\sup_w|L_S(s_w)-\widehat L_S(s_w)|=O(1/m+\sqrt{\log(1/\delta)/n})\).
    • Design Motivation: This decomposition exposes the explicit trade-off between \(m\) and \(n\): with total sample budget \(N=n\cdot m\) fixed, increasing \(m\) shrinks the inner term exponentially, while increasing \(n\) shrinks the outer term at \(1/\sqrt n\), explaining the engineering rationale for CLIP using all non-matching captions in a batch as negatives.

Loss & Training

No new loss is introduced; instead, two existing contrastive objectives are analyzed: the supervised \(L_S(s_w)\) (Eq. 5, each anchor samples \(m\) negatives independently) and the self-supervised \(L_{SS}(s_w)\) (Eq. 8 / GCL, \(m\) negatives are shared across all anchors, as in CLIP/SimCLR). Both share the InfoNCE log-sum-exp form, differing only in the coupling of negative sampling, which leads to the inner bound tightening from \(O(1/\sqrt m)\) (SSCRL) to \(O(1/m)\) (SCRL).

Key Experimental Results

Main Results

The paper uses CLIP/vision-language models to empirically validate two scaling behaviors predicted by theory on large-scale data (see Sec 5 and appendix for details):

Dimension Theoretical Prediction Empirical Validation
Number of negatives \(m\) Inner error decays as \(1/m\) (SCRL) / \(1/\sqrt m\) (SSCRL) Increasing negatives per batch leads to monotonic improvement in downstream zero-shot retrieval R@1, with marginal gains matching the \(1/m\) curve
Number of anchors \(n\) Outer error decays as \(1/\sqrt n\) With \(m\) fixed, increasing positives yields \(1/\sqrt n\)-like improvement in retrieval performance
\(m\) vs \(n\) trade-off Both appear additively, not substitutable With fixed total samples \(n\cdot m\), either extreme (small \(m\), large \(n\) or vice versa) is inferior to a balanced configuration
Calibration \(\mathcal E^*-\mathcal E(s)\le\sqrt{2(L-L^*)/\tau}\) At different training steps, the measured downstream retrieval AUC gap and upstream loss gap exhibit a \(\sqrt{\cdot}\) relationship

Ablation Study

Configuration Key Findings Notes
Increase \(m\) (SCRL) Marginal gain in retrieval AUC is steeper Consistent with \(O(1/m)\), large negatives benefit more in supervised setting
Increase \(m\) (SSCRL / CLIP) Marginal gain is milder Consistent with \(O(1/\sqrt m)\), benefit is reduced when negatives are shared
Increase \(n\) only Gains always shrink as \(1/\sqrt n\) Matches outer term theory, explains CLIP scaling law on the \(n\) side

Key Findings

  • The \(O(m/\sqrt n)\) dependence in prior theory is a byproduct of analysis technique, not intrinsic difficulty: rewriting log-sum-exp as OCE immediately moves \(m\) to the denominator.
  • SCRL and SSCRL fundamentally differ in inner rate (\(1/m\) vs \(1/\sqrt m\)), stemming from whether negatives are shared across anchors—providing a quantifiable criterion for whether CLIP should use supervised negatives.
  • The calibration inequality is \(\sqrt{\cdot}\) rather than linear, indicating that even as upstream loss "approaches optimal 95%," marginal downstream retrieval improvements remain significant, explaining why small loss decreases in late-stage pretraining still yield notable downstream gains.

Highlights & Insights

  • Elegant theoretical closure: Consistency, calibration inequality, and generalization bound all hold, directly applying to the actual losses of modern vision-language models without needing a "theory-friendly" surrogate.
  • OCE rewriting is a key technique: Transforming the "inner average" log-mean-exp loss into a strongly convex ERM is a general method transferable to other conditional stochastic optimization problems (e.g., DRO, learning-to-rank, softmax pooling in attention).
  • Explains \(m\uparrow\) performance gains: This is the first work to quantitatively explain the empirical phenomenon in CLIP/SimCLR, providing theoretical assurance that "increasing batch size will continue to help," not just luck.
  • AUC-based retrieval criterion: Emphasizes that contrastive learning is fundamentally about ranking, not classification—a perspective extendable to any InfoNCE-trained model with retrieval downstream (dense retrieval, recommendation).

Limitations & Future Work

  • Assumption 4.1 requires the scoring function to be an inner product with bounded spectral norm; whether actual transformer encoders satisfy this remains to be verified. The spectral norm accumulates exponentially with depth (\(B=\prod_l s_l^2\)), possibly making explicit constants loose.
  • Consistency proof is over "all measurable functions," leaving approximation error between this and practical neural network hypothesis classes uncharacterized.
  • Experiments focus on validating scaling trends, without providing actionable guidance on "optimal \(m,n\) values"; future work could derive optimal allocation formulas under budget constraints based on \(1/m+1/\sqrt n\).
  • Hard-negative mining, a common engineering speedup, is not covered; it breaks the i.i.d. negative sample assumption and is a promising direction for future analysis.
  • vs Saunshi et al. 2019 / Lei et al. 2023: Their surrogate-gap models downstream as linear classification, with generalization bounds \(O(m/\sqrt n)\) or \(O(\log m/\sqrt n)\) contradicting practice; this work uses AUC ranking + OCE rewriting to simultaneously resolve consistency and large negative sample benefit.
  • vs HaoChen et al. 2021 (spectral methods): Spectral perspective explains representation geometry but does not directly provide sample complexity; this work complements with a classical SLT sample-size view.
  • vs Wang & Isola 2020 (alignment & uniformity): They characterize "alignment + uniformity" from an information geometry perspective; this work provides corresponding statistical learning theory fast-rate evidence, making the two lines complementary.
  • For dense retrieval/recommendation and other production systems, these conclusions directly support "increasing batch negatives" and "hard negative mining on the query side" as theoretically justified strategies.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ First to provide Fisher consistency + calibration + \(O(1/m+1/\sqrt n)\) triple proof for contrastive learning; OCE rewriting is a methodological innovation.
  • Experimental Thoroughness: ⭐⭐⭐ Experiments mainly serve to validate theory, with no new algorithms or broader ablation across models.
  • Writing Quality: ⭐⭐⭐⭐ Logical chain (consistency → calibration → generalization) is very clear; decomposition (inner/outer) is easy to follow.
  • Value: ⭐⭐⭐⭐⭐ Must-read theoretical reference for all teams training foundational models with InfoNCE, directly explaining the batch size scaling law.