Pipeline-generated

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.

Rademacher complexity and uniform generalization — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A two-function loss class has explicit Rademacher complexity

Example

Let $Z = {a, b}$ with the discrete sigma-algebra, let $P ({a}) = p$ and $P ({b}) = 1 - p$ for $p \in [0, 1]$ , and let $G = {g_{0}, g_{1}}$ where $g_{0}$ is identically zero and $g_{1} (z) = 1$ for $z = a$ and $g_{1} (z) = 0$ for $z = b$ . For a one-observation sample ( $m = 1$ ), ${\hat{R}}_{S} (G) = 1 / 2$ when $Z_{1} = a$ and $0$ when $Z_{1} = b$ , so $R_{1} (G) = p / 2$ .

Example references

One-sided Rademacher complexity: defines the empirical sign supremum and its expectation over the sample.

Facts & Assumptions

Given: The two-point probability law, the finite class $G$ , and sample size $m = 1$ .

[F1]

${\hat{R}}_{S} (G) = E_{σ} \sup_{g \in G} m^{- 1} \sum_{i} σ_{i} g (Z_{i})$ and $R_{m} (G) = E_{S} {\hat{R}}_{S} (G)$ . One-sided Rademacher complexity

Verification

Given: The objects and hypotheses in the Example.

1.1F1givenalgebra

If $Z_{1} = a$ , then for sign $σ_{1} = 1$ the supremum of $σ_{1} g (Z_{1})$ over $G$ is $1$ , and for $σ_{1} = - 1$ it is $0$ . Thus ${\hat{R}}_{S} (G) = \frac{1}{2} (1 + 0) = \frac{1}{2}$ . If $Z_{1} = b$ , both functions vanish at the observation, so ${\hat{R}}_{S} (G) = 0$ .

2.1F1step 1.1algebra∎

The two sample outcomes have probabilities $p$ and $1 - p$ . Averaging the values from step 1.1 gives $R_{1} (G) = p (\frac{1}{2}) + (1 - p) 0 = p / 2$ .

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Bounded linear predictors have a radius-dependent bound

Example

Let $⟨ u, v ⟩ : = \sum_{j = 1}^{d} u_{j} v_{j}$ and $∥ u ∥_{2} : = \sqrt{\sum_{j = 1}^{d} u_{j}^{2}}$ on $R^{d}$ . Put $X_{R} : = {x \in R^{d} : ∥ x ∥_{2} \leq R}$ with its Borel sigma-algebra, let $m, d \geq 1$ , and let a fixed sample $x_{1}, \dots, x_{m} \in X_{R}$ . Let $B, R \geq 0$ satisfy $B R \leq 1$ . For the loss class

$G : = {g_{w} : X_{R} \to [0, 1], g_{w} (x) = \frac{1 + ⟨ w, x ⟩}{2}, ∥ w ∥_{2} \leq B},$

every $g_{w}$ takes values in $[0, 1]$ on the sample domain ${x : ∥ x ∥_{2} \leq R}$ , and

${\hat{R}}_{S} (G) \leq \frac{B R}{2 \sqrt{m}} .$

Example references

One-sided Rademacher complexity: fixes the empirical one-sided sign-average convention.

Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors: gives the Euclidean inner-product bound used to maximize over the ball.

Cauchy-Schwarz for finite random variables: $E [X Y]^{2} \leq E [X^{2}] E [Y^{2}]$ : bounds the sign-average norm by its second moment.

Facts & Assumptions

Given: The fixed sample, radii $B, R \geq 0$ with $B R \leq 1$ , and independent uniform signs.

[F1]

In a real inner product space, $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ . Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors

[F2]

For finite random variables, $(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}]$

[F3]

The empirical complexity is $E_{σ} \sup_{g \in G} m^{- 1} \sum_{i} σ_{i} g (x_{i})$ . One-sided Rademacher complexity

Verification

Given: The objects and hypotheses in the Example.

1.1F1given

For every $w$ in the radius- $B$ ball and every sample point, [F1] gives $∣ ⟨ w, x_{i} ⟩ ∣ \leq B R \leq 1$ . Thus $g_{w} (x_{i}) \in [0, 1]$ , as required for the stated loss class.

1.2F1F3givenconstructalgebra

Put $V_{σ} : = \sum_{i} σ_{i} x_{i}$ . By [F3], ${\hat{R}}_{S} (G) = \frac{1}{2 m} E_{σ} [\sum_{i} σ_{i} + \sup_{∥ w ∥_{2} \leq B} ⟨ w, V_{σ} ⟩]$ . The sign sum has expectation zero. By [F1], $⟨ w, V_{σ} ⟩ \leq B ∥ V_{σ} ∥_{2}$ ; equality is attained at $w = B V_{σ} / ∥ V_{σ} ∥_{2}$ when $V_{σ} \neq 0$ , while both sides are zero when $V_{σ} = 0$ . Therefore ${\hat{R}}_{S} (G) = \frac{B}{2 m} E_{σ} ∥ V_{σ} ∥_{2}$ .

2.1F2step 1.2givenalgebra∎

Apply [F2] with $X = ∥ V_{σ} ∥_{2}$ and $Y = 1$ to get $(E_{σ} ∥ V_{σ} ∥_{2})^{2} \leq E_{σ} ∥ V_{σ} ∥_{2}^{2}$ . Expanding the square and using $E_{σ} [σ_{i} σ_{j}] = 0$ for $i \neq j$ and $1$ for $i = j$ gives $E_{σ} ∥ V_{σ} ∥_{2}^{2} = \sum_{i} ∥ x_{i} ∥_{2}^{2} \leq m R^{2}$ . Substitution in step 1.2 proves ${\hat{R}}_{S} (G) \leq B R / (2 \sqrt{m})$ .

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Clipping can make the linear radius bound loose

Example

Let $m \geq 1$ , let the fixed sample be $x_{1} = \dots = x_{m} = 1$ in $R$ with its Borel sigma-algebra, and let $B \geq 1$ . Define $clip (u) : = \max {- 1, \min {1, u}}$ and

$G_{B} : = {g_{w} : R \to [0, 1], g_{w} (x) = \frac{1 + clip (w x)}{2}, ∣ w ∣ \leq B} .$

For this sample, ${\hat{R}}_{S} (G_{B}) = m^{- 1} E_{σ} [(\sum_{i} σ_{i})_{+}]$ , where $u_{+} : = \max {u, 0}$ , so ${\hat{R}}_{S} (G_{B}) \leq 1 / (2 \sqrt{m})$ independently of $B$ . The contraction inequality and the direct radius estimate for the unclipped linear class also give ${\hat{R}}_{S} (G_{B}) \leq B / (2 \sqrt{m})$ ; this latter bound grows with $B$ although the actual complexity on this fixed sample does not.

Example references

One-sided Rademacher complexity: fixes the empirical one-sided sign-average convention.

One-sided coordinate Rademacher contraction: gives the factor-one contraction bound used for the second, looser estimate.

Cauchy-Schwarz for finite random variables: $E [X Y]^{2} \leq E [X^{2}] E [Y^{2}]$ : bounds the sign-average absolute sum by its second moment.

Facts & Assumptions

Given: $m \geq 1$ , the all-ones sample, radius $B \geq 1$ , and independent uniform signs.

[F1]

The one-sided empirical complexity is the sign average of the supremum divided by $m$ . One-sided Rademacher complexity

[F2]

For a fixed sample and an admissible nonempty real-valued class $H$ , the general one-sided convention is ${\hat{R}}_{S} (H) : = m^{- 1} E_{σ} \sup_{h \in H} \sum_{i} σ_{i} h (z_{i})$ . Under the theorem's class and finite-supremum hypotheses, a common 1-Lipschitz coordinate map contracts this complexity by factor 1, without a zero-at-zero assumption. One-sided coordinate Rademacher contraction

[F3]

For finite random variables, $(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}]$

Verification

Given: The objects and hypotheses in the Example.

1.1F1givenconstruct

Since $B \geq 1$ and every sample input is $1$ , the clipped values $clip (w)$ range over all of $[- 1, 1]$ , so the class values on the sample range over $a \in [0, 1]$ . For $T : = \sum_{i} σ_{i}$ , the signwise supremum is $\sup_{a \in [0, 1]} a T = T_{+}$ . Hence ${\hat{R}}_{S} (G_{B}) = m^{- 1} E_{σ} T_{+}$ .

2.1F3step 1.1givenalgebra

The distribution of $T$ is symmetric, so $E T_{+} = \frac{1}{2} E ∣ T ∣$ . Apply [F3] to $X = ∣ T ∣$ and $Y = 1$ ; independence and symmetry of the signs give $E T^{2} = m$ . Thus $E T_{+} \leq \sqrt{m} / 2$ and step 1.1 gives ${\hat{R}}_{S} (G_{B}) \leq 1 / (2 \sqrt{m})$ .

3.1F2F3step 2.1givenalgebra∎

Put $H_{B} : = {h_{w} : x \mapsto w x : ∣ w ∣ \leq B}$ and $H_{0} : = {h_{- B}, h_{B}} \subseteq H_{B}$ . For every sign vector, with $T = \sum_{i} σ_{i}$ , the raw supremum is $\sup_{∣ w ∣ \leq B} w T = B ∣ T ∣$ , attained at an endpoint. The clipped supremum is $\sup_{∣ w ∣ \leq B} clip (w) T = ∣ T ∣$ , also attained at an endpoint because $B \geq 1$ . Thus $H_{0}$ gives both suprema required by [F2]. The map $clip$ is 1-Lipschitz: for $u \leq v$ , its increase is $0$ if both are below $- 1$ or both above $1$ , is $v - u$ if both lie in $[- 1, 1]$ , is $v + 1 \leq v - u$ if $u \leq - 1 \leq v \leq 1$ , is $1 - u \leq v - u$ if $- 1 \leq u \leq 1 \leq v$ , and is $2 \leq v - u$ if $u \leq - 1$ and $v \geq 1$ . Thus [F2] applies. The constant offset $1 / 2$ has zero expected sign sum, and scaling by $1 / 2$ gives ${\hat{R}}_{S} (G_{B}) = \frac{1}{2} {\hat{R}}_{S} (clip \circ H_{B})$ . By the general formula in [F2], ${\hat{R}}_{S} (H_{B}) = m^{- 1} E_{σ} \sup_{∣ w ∣ \leq B} w T = B E ∣ T ∣ / m \leq B / \sqrt{m}$ , where [F3] is applied to $X = ∣ T ∣$ and $Y = 1$ and $E T^{2} = m$ . Therefore the contraction route gives ${\hat{R}}_{S} (G_{B}) \leq B / (2 \sqrt{m})$ , which can grow arbitrarily relative to the bound in step 2.1 as $B$ increases.