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.

Uniform generalization bound for the one-negative contrastive loss

Statement

Assume the Axiom of Choice. In the one-negative latent-class model, fix $R > 0$ , a source loss $ℓ \in {ℓ_{h}, ℓ_{l o g}}$ , a sample size $M \geq 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_{ℓ, R} = ℓ (2 R^{2}) - ℓ (- 2 R^{2})$ and define

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

With probability at least $1 - δ$ over $S$ ,

$\forall f \in F, ∣ L_{u n} (f) - {\hat{L}}_{u n} (f) ∣ \leq Γ_{M} (S, δ) .$

Here $R_{S} (F)$ is the unnormalized vector Rademacher complexity of the three embeddings in each triplet.

Statement references

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_{ℓ, 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.

Facts & Assumptions

Given: AC, the one-negative latent-class model with $R > 0$ , either source loss, IID triplets, $M \geq 1$ , $0 < δ < 1$ , and the measurability assumptions in the Statement.

[A1]

AC is the set-theoretic choice axiom used by the uniform-generalization supplier through its bounded-differences theorem. The Axiom of Choice, Rademacher uniform generalization bounds

[F1]

The triplets are IID; the population and empirical risks are the expectation and sample average of $ℓ (q_{f})$ . Latent-class contrastive representation learning, Identical distribution and IID families, Independent random elements have product joint law

[F2]

The score obeys $∣ q_{f} (x, x^{+}, x^{-}) ∣ \leq 2 R^{2}$ , the loss is nondecreasing and $L_{0}$ -Lipschitz, and its range on that interval is $B_{ℓ, R} > 0$ . Latent-class contrastive representation learning, Convexity, Lipschitz bounds, and oscillation of the source contrastive losses

[F3]

The two-sided empirical Rademacher deviation theorem for a measurable class $G$ of functions into $[0, 1]$ gives, with probability at least $1 - δ$ , $\sup_{g \in G} ∣ P g - P_{M} g ∣ \leq 2 {\hat{R}}_{S} (G) + 3 \sqrt{\ln (4 / δ) / (2 M)}$ . It assumes AC. Rademacher uniform generalization bounds

[F4]

For a nonempty bounded trace set and coordinatewise functions with common Euclidean Lipschitz constant $L$ , one-sided vector contraction bounds the scalar sign supremum by $\sqrt{3} L$ times the independent coordinate-sign supremum. A finite-dimensional vector contraction bound for one-sided Rademacher averages

[F5]

For vectors $u, v$ , $∣ u^{⊤} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ ; integrable expectations are linear. Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors, The Lebesgue integral is linear on $L^{1} (μ)$

Proof

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

1.1A1F1F2F5given

Set $a = ℓ (- 2 R^{2})$ and $B = B_{ℓ, R}$ . For each triplet $z = (x, x^{+}, x^{-})$ , define $g_{f} (z) = (ℓ (q_{f} (z)) - a) / B$ . By [F2], $g_{f}$ takes values in $[0, 1]$ . Since the shift $a$ is common to every $f$ , averaging over the signs shows that the empirical one-sided Rademacher complexity of ${g_{f} : f \in F}$ equals $B^{- 1}$ times that of ${ℓ (q_{f}) : f \in F}$ : the extra term is $- (a / B) \sum_{j} ε_{j}$ , whose sign expectation is zero.

1.2F2F5givenalgebra

For a fixed triplet, write $v = (u_{0}, u_{+}, u_{-}) \in (R^{d})^{3}$ and $h (v) = ℓ (u_{0}^{⊤} (u_{-} - u_{+}))$ on $K = ({\overline{B}}_{R})^{3}$ , where ${\overline{B}}_{R} = {u : ∥ u ∥_{2} \leq R}$ . For $v, v^{'} \in K$ , expansion of the score difference and [F5] give $∣ h (v) - h (v^{'}) ∣ \leq L_{0} R (2 ∥ u_{0} - u_{0}^{'} ∥_{2} + ∥ u_{-} - u_{-}^{'} ∥_{2} + ∥ u_{+} - u_{+}^{'} ∥_{2}) \leq \sqrt{6} L_{0} R ∥ v - v^{'} ∥_{2}$ . The last inequality is Cauchy–Schwarz for the three nonnegative coordinate distances. This Lipschitz function extends to all of $(R^{d})^{3}$ with the same constant by $\tilde{h} (v) = \inf_{w \in K} {h (w) + \sqrt{6} L_{0} R ∥ v - w ∥_{2}}$ : on $K$ the Lipschitz inequality gives equality with $h$ , and the triangle inequality gives the global Lipschitz bound.

2.1F1F4step 1.1step 1.2givenalgebra

For the observed triplets, let $V = {(f (x_{j}), f (x_{j}^{+}), f (x_{j}^{-}))_{j = 1}^{M} : f \in F}$ , a nonempty bounded trace set. Apply [F4] to the extensions in step 1.2 with $L = \sqrt{6} L_{0} R$ . The independent coordinate signs are exactly those defining $R_{S} (F)$ , so ${\hat{R}}_{S} ({g_{f} : f \in F}) \leq \frac{\sqrt{3} \sqrt{6} L_{0} R R_{S} (F)}{B M} = \frac{\sqrt{18} L_{0} R R_{S} (F)}{B M}$ . The normalization $1 / M$ comes from the empirical complexity convention; $R_{S}$ itself is unnormalized.

3.1A1F1F2F3step 1.1step 2.1givenalgebra∎

Apply [F3] to the normalized class in step 1.1. With probability at least $1 - δ$ , its uniform deviation is at most twice the complexity in step 2.1 plus $3 \sqrt{\ln (4 / δ) / (2 M)}$ . Multiplying by $B$ converts that deviation to the unnormalized losses and yields exactly $Γ_{M} (S, δ)$ for every $f \in F$ .

Depends on

Used by

Population contrastive excess of an approximate empirical minimizer Lemma

Dependency tree · two levels

51 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, Supplementary Appendix A.3 (standard reference, not scraped)
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Theorem 3.3 and complete proof (standard reference, not scraped)
Andreas Maurer, A vector-contraction inequality for Rademacher complexities, Theorem 3, Corollary 4, and complete proof (standard reference, not scraped)