LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Population contrastive excess of an approximate empirical minimizer

Statement

Assume the Axiom of Choice and the hypotheses of the one-negative uniform-generalization lemma for a sample $S$ of size $M$ . Let $\hat{f}$ be a measurable selector taking values in $F$ almost surely and satisfying, almost surely, ${\hat{L}}_{u n} (\hat{f}) \leq {\hat{L}}_{u n} (f) + η$ for every $f \in F$ , where $η \geq 0$ . For every $0 < δ < 1$ , with probability at least $1 - δ$ ,

$\forall f \in F, L_{u n} (\hat{f}) \leq L_{u n} (f) + 2 Γ_{M} (S, δ) + η,$

where

$Γ_{M} (S, δ) : = \frac{2 \sqrt{18} L_{0} R R_{S} (F)}{M} + 3 B_{ℓ, R} \sqrt{\frac{\ln (4 / δ)}{2 M}}$

is the uniform-deviation quantity for the same sample and loss. The case $η = 0$ includes any attained measurable empirical minimizer; the statement does not assert that such a selector exists.

Statement references

Latent-class contrastive representation learning: defines population and empirical contrastive risk and the measurable-selector convention.

Uniform generalization bound for the one-negative contrastive loss: supplies the simultaneous deviation event with error $Γ_{M} (S, δ)$ .

Saunshi et al., Theorem 4.1 and proof route: compares an empirical minimizer with every population-risk comparator using uniform deviation.

Mohri et al., Foundations of Machine Learning, Chapter 3: develops the same empirical-to-population comparison from a uniform deviation bound.

Facts & Assumptions

Given: AC, the hypotheses and notation of lem-contrastive-uniform-generalization, a measurable random selector $\hat{f}$ , and a tolerance $η \geq 0$ .

[A1]

AC is assumed in the uniform-generalization lemma and enters only through that supplier's bounded-differences theorem. The Axiom of Choice, Uniform generalization bound for the one-negative contrastive loss

[F1]

On an event of probability at least $1 - δ$ , every $g \in F$ satisfies $∣ L_{u n} (g) - {\hat{L}}_{u n} (g) ∣ \leq Γ_{M} (S, δ)$ . Uniform generalization bound for the one-negative contrastive loss

[F2]

Almost surely, the approximate-minimizer condition gives ${\hat{L}}_{u n} (\hat{f}) \leq {\hat{L}}_{u n} (f) + η$ simultaneously for each comparator $f \in F$ . Latent-class contrastive representation learning

Proof

Given: The hypotheses in the Statement and Facts & Assumptions.

1.1A1F1given

On the event in [F1], apply its uniform bound to the random selector $\hat{f}$ (which belongs to $F$ almost surely) to obtain $L_{u n} (\hat{f}) \leq {\hat{L}}_{u n} (\hat{f}) + Γ_{M} (S, δ)$ .

1.2F2given

On the same event, [F2] gives ${\hat{L}}_{u n} (\hat{f}) \leq {\hat{L}}_{u n} (f) + η$ for every $f \in F$ .

2.1F1step 1.1step 1.2givenalgebra∎

Apply [F1] again to each comparator to obtain ${\hat{L}}_{u n} (f) \leq L_{u n} (f) + Γ_{M} (S, δ)$ . Combining the preceding inequalities yields the displayed bound simultaneously for all $f$ . Since the event in [F1] has probability at least $1 - δ$ , the claim follows.

Depends on

Used by

Contrastive transfer for an approximate empirical minimizer Corollary
Contrastive transfer bound with class collisions Theorem

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Nikunj Saunshi et al., A Theoretical Analysis of Contrastive Unsupervised Representation Learning, Theorem 4.1 and proof route (standard reference, not scraped)
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., empirical-to-population risk argument in Chapter 3 (standard reference, not scraped)