Source
Tosh, Krishnamurthy & Hsu (2021; ALT 2021), LIT-251, read in NOTE-841: §2.2–2.4 with Lemma 1 (proof App. A.1), §3 with Lemma 2 and Theorem 3 (App. A.2), Proposition 5 (App. A.4), Lemma 6, Theorems 10–11 (App. A.9–A.10).
What was actually shown
Redundancy. For views X, Z and label Y, let εX = E[(E[Y|X] − E[Y|X,Z])²] and εZ = E[(E[Y|Z] − E[Y|X,Z])²]. The “infer, then predict” function µ(x) = E[E[Y|Z] | X = x] satisfies E[(µ(X) − E[Y|X,Z])²] ≤ εX + 2√(εXεZ) + εZ (Lemma 1). The proof is Jensen and AM/GM and holds for any joint law with finite second moments.
The ratio. The logistic problem of telling a same-datum pair from an independent pair, with equal priors, is solved over all functions by the PMI, so g*(x,z) = p(x,z)/(p(x)p(z)) (§2.3, stated). Then µ(x) = ∫ E[Y|Z=z] g*(x,z) p_Z(z) dz: “g⋆ provides the change-of-measure from the marginal distribution of Z to the conditional distribution of Z given X = x”, and g* “does not depend on Y at all” (§2.4).
Linear readout. With landmarks Z_1, …, Z_m drawn from p_Z and φ*(x) = (g*(x,Z_1), …, g*(x,Z_m)), with probability 1 − δ some w gives E[(wᵀφ*(X) − µ(X))²] ≤ 2 var(E[Y|Z]g*(X,Z̃)) / ⌊m/log₂(1/δ)⌋ (Lemma 2), and so a near-Bayes linear predictor (Theorem 3). For |Y| ≤ 1 the variance is at most E[g*(X,Z̃)²] with X, Z̃ independent. That quantity is 1 + χ² of the joint against the product of marginals. The identification with χ² is the record’s; in the paper’s Gaussian model it is (1 + σ²)²/(1 + 2σ²) (Prop. 5).
What could have failed. Redundancy could have required that the representation see the label, or that the views be exchangeable. The argument uses neither: X and Z may be different spaces with any joint law.
Estimation. If the ratio is learned with excess logistic loss ε_opt, the downstream risk grows by terms in (1 + g_max)²√ε_opt and (1 + g_max)⁴ε_opt, where g_max is a uniform bound on the ratio (Theorem 10). The direct loss with prediction log(η(x)ᵀψ(z)) has the ratio itself as its minimizer, and its excess loss bounds the risk of η (Lemma 6, Theorem 11).
What this does not say
- That µ is the Bayes predictor. It is close to it, by εµ, only when both views are redundant for the label.
- Anything about the top eigen- or singular functions. The readout is through random landmarks of the full ratio. A low-dimensional direct embedding of the ratio is shown to exist (Lemma 7) but not to be what minimizing the direct loss finds, and the authors say so.
- Anything about InfoNCE with many negatives. The contrastive problem is logistic, with a single negative.
- That the guarantees survive an unbounded ratio. Theorems 10–11 need g_max < ∞. Lemma 2 needs only a finite variance, which is the square-integrability condition of THEORY-005, but only for the exact ratio.
- That redundancy holds for any real task. It is assumed, not measured. The examples are a topic model and a Gaussian latent model.
Connections
- QUESTION-052. An answer in part to its second half. For linear decisions about labels on which two views are redundant, the full density-ratio kernel is decision-sufficient with no symmetry between the views. The signature here is the full kernel through random landmarks, not a low-dimensional eigenspace, and the guarantee is at the population ratio.
- THEORY-239. The same conditional-expectation operator between two spaces, g ↦ E[g(Z)|X]. Zhai’s result picks the top-d singular functions as the minimax span for compatible tasks; this one reads µ, an image of that operator, off the whole kernel. µ = E[h(Z)|X] with h = E[Y|Z] is exactly the form of target Zhai’s compatibility measures.
- THEORY-001. Supplies, for general densities, the logistic optimum that THEORY-001 holds on a finite space, and §5’s contrast between a loss minimized by log g* and one minimized by g*.
- THEORY-005. The landmark bound is controlled by E[g*²], the Hilbert–Schmidt quantity THEORY-005 names, without any operator or eigenfunction formulation.
- THEORY-228 and THEORY-007. Different conditions on the target: augmentation rarely changing the label and conductance there, approximate view invariance in THEORY-007, redundancy across views here.
- THEORY-009. A guarantee that never uses symmetry. It does not meet THEORY-009’s promote_when, which asks about asymmetric objectives of the BYOL kind and eigen- or singular-function characterizations.
Note of 2026-10-19: Lemmas 1 and 2, re-derived
With η = E[Y|X,Z], a = E[Y|X], b = E[Y|Z] and µ(x) = E[b(Z) | X = x], the tower rule gives a = E[η|X], so µ − a = E[b − η | X]. Conditional Jensen gives ‖µ − a‖² ≤ ‖b − η‖² = εZ. Minkowski then gives ‖µ − η‖ ≤ √εZ + √εX, and squaring gives Lemma 1. Only finite second moments are used, with X and Z in any spaces and under any joint law.
For telling a joint pair from an independent one with equal priors, the Bayes posterior is g/(1 + g), with g = p(x,z)/(p(x)p(z)), so the logistic optimum is log g* and does not involve Y. Then µ(x) = ∫ b(z) g*(x,z) p(z) dz, which is linear in g*(x,·).
With landmarks Z_1, …, Z_n drawn from p_Z and weights b(Z_i)/n, the readout (1/n) Σ b(Z_i) g*(x, Z_i) is unbiased for µ(x). Its mean squared error, averaged over X and the landmarks, is at most V/n, with V = var(b(Z̃)g*(X,Z̃)) for independent X and Z̃. Split m landmarks into log₂(1/δ) groups. By Markov, each group exceeds 2V/n with probability at most ½, so with probability 1 − δ some group’s readout is within 2V/⌊m/log₂(1/δ)⌋: Lemma 2, with its constant. For |Y| ≤ 1, V ≤ E[g*(X,Z̃)²] = 1 + χ²(P_XZ ‖ P_X ⊗ P_Z). The rate therefore needs that quantity finite. Whether a learned ratio keeps the rate without a uniform bound on it is QUESTION-182.