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.

Class-conditional sub-Gaussian concentration yields a contrastive margin bound

Statement

In the one-negative latent-class model, fix a bounded representation $f$ with $\sup_{x} ∥ f (x) ∥_{2} \leq R$ , where $R > 0$ . Use the hinge loss $ℓ_{h} (t) = (1 + t)_{+}$ . Suppose that for every class $c$ , the centered vector $f (X) - μ_{c}$ , for $X \sim D_{c}$ , is sub-Gaussian in every direction with proxy $σ^{2} \geq 0$ . For $0 < ϵ \leq 1$ , define

$γ : = {\begin{cases} 1 + 2 R σ \sqrt{2 \ln R + \ln (3 / ϵ)}, & R \geq 1, \\ 1 + 2 R σ \sqrt{\ln (3 / ϵ)}, & 0 < R < 1. \end{cases}$

Then the contrastive risk conditioned on distinct positive and negative classes satisfies

$L_{u n}^{\neq} (f) \leq γ L_{γ, s u p}^{μ} (f) + ϵ .$

This comparison is for the hinge contrastive loss and its scaled hinge mean-classifier risk.

Statement references

Latent-class contrastive representation learning: defines the one-negative score, class-conditional means, distinct-class contrastive risk and scaled hinge mean-classifier risk.

Sub-Gaussian variables and vectors, and sub-exponential variables: defines the centered vector sub-Gaussian proxy condition used for every class.

Convexity, Lipschitz bounds, and oscillation of the source contrastive losses: defines the hinge contrastive loss.

Saunshi et al., Lemma 5.1, main paper §5.2.

Saunshi et al., complete proof of Lemma 5.1, Supplementary Appendix A.2.

Facts & Assumptions

Given: The one-negative latent-class model, a representation $f$ bounded by $R > 0$ , the classwise centered sub-Gaussian hypothesis, $0 < ϵ \leq 1$ , and the value of $γ$ in the Statement.

[F1]

Given classes $c_{+}, c_{-}$ and an anchor $x$ , the examples $X^{+} \sim D_{c_{+}}$ and $X^{-} \sim D_{c_{-}}$ are independent; the contrastive score is $q = f (x)^{⊤} (f (X^{-}) - f (X^{+}))$ . Latent-class contrastive representation learning, Independent random elements have product joint law

[F2]

For each class $c$ , $f (X) - μ_{c}$ is centered and satisfies $E e^{⟨ u, f (X) - μ_{c} ⟩} \leq e^{σ^{2} ∥ u ∥_{2}^{2} / 2}$ for every $u \in R^{d}$ . Sub-Gaussian variables and vectors, and sub-exponential variables

[F3]

The underlying laws are countably additive probability measures; integrable coordinates have expectations given by integration, the integral is linear, and bounded integrands on probability product spaces satisfy Fubini. Expectation of a nonnegative or integrable random variable, Probability measures and probability spaces, The Lebesgue integral is linear on $L^{1} (μ)$ , Fubini's theorem for L^1 functions on a sigma-finite product

[F4]

If $W \geq 0$ and $a > 0$ , then $\Pr (W \geq a) \leq E [W] / a$ . Markov's inequality for random variables

[F5]

The natural logarithm is inverse to the real exponential, is increasing, and satisfies $\ln (a b) = \ln a + \ln b$ for positive $a, b$ . The natural logarithm as the inverse of the exponential function, The real exponential function and the number $e$ by a power series, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F6]

For vectors $u, v$ , $∣ u^{⊤} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ . Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors

[F7]

The ordered law of $(C_{+}, C_{-})$ conditioned on $C_{+} \neq C_{-}$ is invariant under swapping its coordinates. Latent-class contrastive representation learning, Independent random elements have product joint law

[F8]

For the hinge mean-classifier risk, the positive-label loss at $(c_{+}, c_{-}, x)$ is $(1 + f (x)^{⊤} (μ_{c_{-}} - μ_{c_{+}}) / γ)_{+}$ ; the task label is uniform. Latent-class contrastive representation learning

Proof

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

1.1F1F2F3F6given

Fix distinct classes $c_{+}, c_{-}$ and an anchor $x$ . Put $u = f (x)$ and write the score as $q = m + Z$ , where $m = u^{⊤} (μ_{c_{-}} - μ_{c_{+}})$ and $Z = u^{⊤} (f (X^{-}) - μ_{c_{-}}) - u^{⊤} (f (X^{+}) - μ_{c_{+}})$ . By [F1]–[F3], independence factors the moment generating function of the two centered terms, so for every $λ \in R$ , $E e^{λ Z} \leq e^{λ^{2} σ^{2} ∥ u ∥_{2}^{2}} \leq e^{λ^{2} v / 2}$ with $v : = 2 R^{2} σ^{2}$ . Also $∣ q ∣ \leq 2 R^{2}$ by [F6] and the representation bound.

2.1F3F4F5step 1.1given

Put $t = γ - 1$ . If $σ > 0$ , then $t > 0$ . Applying [F4] to $e^{λ Z}$ with $λ = t / v > 0$ and using step 1.1 gives $p : = \Pr (Z \geq t) \leq e^{- t^{2} / (2 v)} = e^{- t^{2} / (4 R^{2} σ^{2})} \leq ϵ / (3 R^{2})$ for $R \geq 1$ , and $p \leq ϵ / 3$ for $0 < R < 1$ . If $σ = 0$ , then $v = 0$ and step 1.1 gives $E e^{λ Z} \leq 1$ for every $λ > 0$ . For any $a > 0$ and $0 < r < 1$ , [F4] with $λ = \ln (1 / r) / a$ gives $\Pr (Z \geq a) \leq r$ , so $\Pr (Z \geq a) = 0$ . Since ${Z > 0} = ⋃_{n \geq 1} {Z \geq 1 / n}$ , countable subadditivity [F3] gives $\Pr (Z > 0) = 0$ . Thus $Z \leq 0$ almost surely and the margin estimate below holds with no tail error when $t = 0$ .

3.1F6step 1.1step 2.1givenalgebra

Suppose first that $σ > 0$ . On ${Z < t}$ , monotonicity of the positive-part function gives $(1 + m + Z)_{+} \leq (γ + m)_{+}$ . On ${Z \geq t}$ , the score bound in step 1.1 gives $(1 + m + Z)_{+} = (1 + q)_{+} \leq 1 + 2 R^{2}$ . Therefore $E_{Z} (1 + m + Z)_{+} \leq (γ + m)_{+} + p (1 + 2 R^{2}) \leq (γ + m)_{+} + ϵ$ , because $1 + 2 R^{2} \leq 3 R^{2}$ for $R \geq 1$ and $1 + 2 R^{2} \leq 3$ for $R < 1$ . When $σ = 0$ , step 2.1 gives $Z \leq 0 = t$ almost surely, so $(1 + m + Z)_{+} \leq (1 + m)_{+} = (γ + m)_{+}$ and the same inequality follows. Since $γ \geq 1$ , $(γ + m)_{+} = γ (1 + m / γ)_{+}$ .

4.1F7F8step 3.1givenalgebra∎

Integrate the conditional inequality in step 3.1 over $x \sim D_{c_{+}}$ and the ordered class-pair law conditioned on inequality. Its leading term is $γ$ times the positive-label mean-classifier hinge risk. Swapping the two classes preserves the ordered distinct-pair law by [F7] and changes the positive-label margin into the negative-label margin; hence the positive-label risk equals the uniform-label mean-classifier risk $L_{γ, s u p}^{μ} (f)$ . The integrated error remains at most $ϵ$ . This yields the Statement.

Depends on

Used by

Dependency tree · two levels

61 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, Lemma 5.1 and Supplementary Appendix A.2 (standard reference, not scraped)
Nikunj Saunshi et al., Supplementary Appendix A.2, complete proof of Lemma 5.1 (standard reference, not scraped)