nucleation

LIT-251: Contrastive learning, multi-view redundancy, and linear models

3 min read

Properties5
StatusActive — read 2026-10-14 (NOTE-841) in full; worth reading as the redundancy account of contrastive learning: when two views are redundant for a label, the infer-then-predict function µ(x) = E[E[Y|Z]|X=x] is within εX + 2√(εXεZ) + εZ of the Bayes predictor (Lemma 1), and µ is linear in the density ratio g*(x,·) = p(x,z)/(p(x)p(z)), "the change-of-measure from the marginal distribution of Z to the conditional distribution of Z given X = x". Random landmark evaluations of g* then give near-Bayes linear predictors at rate 1/m. Read it knowing that it is population-level, that the logistic problem has a single negative, that its error propagation assumes a uniform bound on the ratio, and that its low-dimensional direct embeddings are shown to exist, not to be reached. It never assumes the views are exchangeable.
Version2
Tagsrepresentation-learning, learning-theory, anthology-candidate
Cited as “paper” byNOTE-222 — Tosh et al., contrastive learning and multi-view redundancy, NOTE-841 — Tosh, Krishnamurthy & Hsu — contrastive learning, multi-view redundancy and linear models
Cited as “source” byTHEORY-001 — On a finite augmentation space, InfoNCE, logistic and spectral contrastive losses share one population optimum: the positive-pair density ratio, THEORY-005 — The positive-pair density ratio is the kernel of the conditional-expectation operator on L²(p), so spectral representations are that operator's eigenfunctions, well defined when the positive-pair χ²-divergence is finite, THEORY-319 — When two views are redundant for a label, the predictor that infers one view from the other is within εX + 2√(εXεZ) + εZ of the Bayes predictor in mean squared error, and it is linear in the contrastive density ratio, so for a bounded label and a square-integrable ratio a linear readout of m random evaluations of the exact ratio approaches it at rate 1/m, with no symmetry between the views required

Graph View

Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu (2020), Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT 2021), PMLR 132:1179-1206 — ARXIV-2008.10150

Key takeaways

From the reading, NOTE-841.

  • The optimum. The logistic problem with equal priors is solved over all functions by the PMI, and g* = exp f* is the joint-to-product density ratio (§2.3). The paper states this without derivation.
  • Redundancy. µ(x) = E[E[Y|Z]|X=x] satisfies E[(µ(X) − E[Y|X,Z])²] ≤ εX + 2√(εXεZ) + εZ for any joint law (Lemma 1, proved).
  • The change of measure. µ(x) = ∫ E[Y|Z=z] g*(x,z) p_Z(z) dz, so the label enters only through redundancy and g* does not depend on Y (§2.4).
  • Landmarks. m random landmarks give a linear predictor within 2 var(E[Y|Z]g*(X,Z̃))/⌊m/log₂(1/δ)⌋ of µ (Lemma 2, Theorem 3). For bounded labels the variance is at most E[g*²], which is 1 + χ² of the joint against the product (the record’s identification). In the Gaussian model it is (1 + σ²)²/(1 + 2σ²) (Prop. 5).
  • Direct embeddings. With a finite hidden variable the ratio factorizes exactly at rank |S| (§4.1). Otherwise low-dimensional factorizations exist (Lemma 7), but the paper does not show that minimizing its direct loss finds them.
  • Error propagation. Downstream risk grows smoothly with excess contrastive loss, under a uniform bound g_max on the ratio (Theorems 10–11). The logistic loss is minimized by log g*, the direct loss by g* itself (§5).
  • No symmetry. X and Z may be different spaces with any joint law.

Standing in the record

Filed on 2026-09-26 while pursuing, at the owner’s request, the connection Radon–Nikodym, density ratios and contrastive objectives (see the curation entry of that date). Read in full on 2026-10-14 in NOTE-841, which supersedes the seeded skim NOTE-222.

The reading filed THEORY-319, the redundancy account, which answers part of QUESTION-052 for directed pairs. THEORY-001 cites §2.3 correctly for the logistic optimum, but quotes §2.4 in words the paper does not use. THEORY-005 calls µ “the Bayes predictor under redundancy”, which it only approximates. The reading also finds that the paper’s landmark bound is controlled by E[g*²], the Hilbert–Schmidt quantity THEORY-005 names, without meeting THEORY-005’s promote_when. Johnson et al. (LIT-258, App. B.2) take the logistic optimum from here.

Tagged anthology-candidate (ADR-005): the seed judged it chiefly about machine-learning practice. The reading finds it a learning-theory paper with no training advice beyond the landmark construction. It is kept here by the owner’s decision of 2026-09-26 that new work stays in nucleation until a transfer is judged appropriate (ADR-010).

Backlinks