ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 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.