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.

A finite-dimensional vector contraction bound for one-sided Rademacher averages

Statement

Let $m, d \geq 1$ , let $V$ be a nonempty bounded subset of $(R^{d})^{m}$ , and let $h_{i} : R^{d} \to R$ be $L$ -Lipschitz for one common $L \geq 0$ . Let $(ε_{i})_{i = 1}^{m}$ and $(η_{i t})_{1 \leq i \leq m, 1 \leq t \leq d}$ be independent uniform signs in ${- 1, + 1}$ . Writing $v_{i} = (v_{i 1}, \dots, v_{i d})$ , the one-sided averages satisfy

$E_{ε} \sup_{v \in V} \sum_{i = 1}^{m} ε_{i} h_{i} (v_{i}) \leq \sqrt{3} L E_{η} \sup_{v \in V} \sum_{i = 1}^{m} \sum_{t = 1}^{d} η_{i t} v_{i t} .$

Neither supremum uses an absolute value, and no condition $h_{i} (0) = 0$ is imposed. The bound holds for finite or infinite bounded $V$ ; all displayed suprema are finite.

Statement references

Cauchy-Schwarz for finite random variables: $E [X Y]^{2} \leq E [X^{2}] E [Y^{2}]$ : supplies Cauchy–Schwarz for the finite uniform sign spaces used in the proof.

Maurer, Theorem 3 and Corollary 4, complete vector-contraction proof: proves the sharper $\sqrt{2} L$ version through a one-coordinate comparison and induction.

Lei et al., Lemma A.1, complete vector-contraction proof: gives an independent contrastive-learning application of the vector-contraction inequality.

Facts & Assumptions

Given: $m, d \geq 1$ , a nonempty bounded set $V \subseteq (R^{d})^{m}$ , a common Lipschitz constant $L \geq 0$ , and the independent uniform signs in the Statement.

[F1]

On a finite probability space, $E [X Y]^{2} \leq E [X^{2}] E [Y^{2}]$ . Cauchy-Schwarz for finite random variables: $E [X Y]^{2} \leq E [X^{2}] E [Y^{2}]$

Proof

Given: The objects and hypotheses in the Statement.

1.1F1givenalgebra

For any $u \in R^{d}$ , put $X = \sum_{t = 1}^{d} η_{t} u_{t}$ for independent uniform signs $η_{t}$ . Expanding the finite sign average gives $E X^{2} = \sum_{t} u_{t}^{2} = ∥ u ∥_{2}^{2}$ and $E X^{4} = \sum_{t} u_{t}^{4} + 6 \sum_{s < t} u_{s}^{2} u_{t}^{2} = 3 ∥ u ∥_{2}^{4} - 2 \sum_{t} u_{t}^{4} \leq 3 ∥ u ∥_{2}^{4}$ . By [F1], $E ∣ X ∣^{2} \leq (E ∣ X ∣)^{1 / 2} (E ∣ X ∣^{3})^{1 / 2}$ and $E ∣ X ∣^{3} \leq (E X^{2})^{1 / 2} (E X^{4})^{1 / 2}$ . If $u \neq 0$ , combining and squaring these inequalities yields $E ∣ X ∣ \geq (E X^{2})^{3 / 2} / (E X^{4})^{1 / 2} \geq ∥ u ∥_{2} / \sqrt{3}$ ; the same bound is immediate for $u = 0$ .

2.1F1step 1.1givenalgebra

Fix an index $i$ and any real function $a$ on $V$ . Averaging over $ε_{i} = \pm 1$ gives half the sum of $\sup_{v} (h_{i} (v_{i}) + a (v))$ and $\sup_{w} (- h_{i} (w_{i}) + a (w))$ , hence half the supremum over ordered pairs $(v, w)$ of $h_{i} (v_{i}) - h_{i} (w_{i}) + a (v) + a (w)$ . Swapping $v, w$ leaves $a (v) + a (w)$ unchanged and reverses the loss difference, so this ordered-pair supremum equals $E_{ε_{i}} \sup_{v \in V} {ε_{i} h_{i} (v_{i}) + a (v)} = \frac{1}{2} \sup_{v, w \in V} {∣ h_{i} (v_{i}) - h_{i} (w_{i}) ∣ + a (v) + a (w)}$ . By Lipschitz continuity and step 1.1, the right side is at most $\frac{1}{2} E_{η_{i}} \sup_{v, w \in V} {\sqrt{3} L ∣ ⟨ η_{i}, v_{i} - w_{i} ⟩ ∣ + a (v) + a (w)}$ . For each fixed sign vector, swapping $v, w$ shows the supremum is unchanged if the absolute value is removed. It then separates into a sum of two suprema; symmetry of $η_{i}$ makes their expectations equal. Therefore $E_{ε_{i}} \sup_{v \in V} {ε_{i} h_{i} (v_{i}) + a (v)} \leq E_{η_{i}} \sup_{v \in V} {\sqrt{3} L ⟨ η_{i}, v_{i} ⟩ + a (v)}$ .

3.1step 2.1givenalgebra

For finite $V$ , define $Q_{k}$ to be the expectation of the supremum with the first $k$ terms replaced by $\sqrt{3} L \sum_{t} η_{i t} v_{i t}$ and the remaining terms equal to $ε_{i} h_{i} (v_{i})$ . Then $Q_{0}$ is the left side of the Statement and $Q_{m}$ is its right side. For each $k < m$ , condition on all signs except $ε_{k + 1}$ and the corresponding vector signs, and collect the other terms into $a (v)$ . Step 2.1 gives $Q_{k} \leq Q_{k + 1}$ . Iterating these finitely many inequalities yields $Q_{0} \leq Q_{m}$ .

4.1step 3.1givenchoosealgebra∎

For arbitrary bounded nonempty $V$ , the scalar sign cube has finitely many elements. Given $δ > 0$ , choose for each scalar sign vector one point of $V$ whose left-hand signed sum is within $δ$ of its supremum, and let $V_{0}$ be the finite set of chosen points. Then the left average over $V_{0}$ is within $δ$ of that over $V$ , while the coordinate-sign supremum over $V_{0}$ is no larger than that over $V$ . Applying step 3.1 to $V_{0}$ and letting $δ ↓ 0$ proves the claimed inequality for $V$ . This uses only finitely many approximate choices for each $δ$ .

Depends on

Cauchy-Schwarz for finite random variables: $\mathbb E[XY]^2\le\mathbb E[X^2]\mathbb E[Y^2]$

Used by

Uniform generalization bound for the one-negative contrastive loss Lemma

Dependency tree · two levels

4 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

Andreas Maurer, A vector-contraction inequality for Rademacher complexities, Theorem 3 and Corollary 4 (standard reference, not scraped)
Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuan Zhou, Generalization Analysis for Contrastive Representation Learning, Lemma A.1 (standard reference, not scraped)