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

Training accuracy, algorithmic stability, and class-wide Rademacher bounds

Example

Assume the Axiom of Choice. Let $X = {1, \dots, N}$ with $N \geq 2$ and its discrete sigma-algebra, let $Y = {0, 1}$ with its discrete sigma-algebra, and let $P (X = j, Y = 0) = 1 / N$ for every $j \in X$ . Use the zero-one loss and the hypothesis class $H = {h : X \to {0, 1}}$ . Define a constant learner $A^{0}$ that always outputs $h_{0} \equiv 0$ . Define a memorizing learner $A^{m e m}$ by predicting the majority label among sample observations at the queried feature, resolving a tie by predicting $0$ , and predicting $1$ at any feature absent from the sample; on the empty sample it predicts $1$ everywhere. Both learners are permutation-invariant. For every one-point sample $S = ((j, 0))$ , the constant learner has zero training and population risk and deletion-stability coefficient $0$ . The memorizing learner also has zero training risk, but has population risk $(N - 1) / N$ and deletion-stability coefficient $1$ . For the full finite loss class $G = {(x, y) \mapsto 1 {h (x) \neq y} : h \in H}$ , define ${\hat{R}}_{S} (G) = \frac{1}{2} (\sup_{g \in G} g (Z_{1}) + \sup_{g \in G} [- g (Z_{1})])$ for a one-point sample and $R_{1} (G) = E_{S \sim P} {\hat{R}}_{S} (G)$ . Both values are $1 / 2$ . Under AC, the two-sided Rademacher uniform-deviation bound is $\sup_{g \in G} ∣ P g - P_{1} g ∣ \leq 2 R_{1} (G) + \sqrt{\log (2 / δ) / 2}$ for $δ \in (0, 1)$ , with probability at least $1 - δ$ ; the natural logarithm makes its right-hand side at least $1$ , the trivial zero-one loss range.

Example references

Uniform deletion stability is defined by Uniform algorithmic stability under deletion.

Population and empirical risk use the integral and finite-average conventions in Population and empirical risk.

The one-sided $1 / m$ complexity normalization is fixed by One-sided Rademacher complexity.

The two-sided uniform-deviation bound and its AC hypothesis are stated in Rademacher uniform generalization bounds.

Confidence terms use the natural logarithm The natural logarithm as the inverse of the exponential function.

Its strict monotonicity and value at $1$ follow from Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm.

The IID and choice assumptions are specified by Identical distribution and IID families

and The Axiom of Choice.

Facts & Assumptions

Given: The finite supervised domain, law $P$ , binary hypothesis class, two learning rules, and Axiom of Choice stated in the Example.

[A1]

Assume AC only for applying the Rademacher concentration theorem; the explicit learner risks, stability coefficients, and finite sign average below are choice-free. The Axiom of Choice

[F1]

The supervised loss on $(x, y)$ is the prediction loss evaluated at $h (x)$ and $y$ . Supervised prediction problems

[F2]

Population risk is the expectation of the loss under $P$ , and training risk is its sample average. Population and empirical risk

[F3]

Uniform deletion stability is the supremum loss change between the full output and the output after deleting one indexed observation. Uniform algorithmic stability under deletion

[F4]

The empirical one-sided Rademacher complexity is the sign average of $\sup_{g} m^{- 1} \sum_{i} σ_{i} g (Z_{i})$ , and expected complexity averages this quantity over an IID sample. One-sided Rademacher complexity

[F5]

For a nonempty measurable $[0, 1]$ loss class with measurable suprema and AC, the two-sided expected-complexity bound is $\sup_{g} ∣ P g - P_{m} g ∣ \leq 2 R_{m} (G) + \sqrt{\log (2 / δ) / (2 m)}$ with probability at least $1 - δ$ . Rademacher uniform generalization bounds

[F6]

IID means mutually independent observations with the same law. Identical distribution and IID families

[F7]

For $x > 0$ , $\log x$ is the unique real $y$ with $\exp (y) = x$ . The natural logarithm as the inverse of the exponential function

[F8]

$\log$ is strictly increasing and $\log 1 = 0$ , so $2 / δ > 1$ implies $\log (2 / δ) > 0$ . Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[A2]

The finite discrete domain makes every loss measurable and every supremum over the nonempty finite class $G$ measurable.

Verification

1.1A2F1F2givenalgebra

Both rules depend only on the sample multiset, so they are permutation-invariant. Under $P$ , $h_{0} \equiv 0$ has zero loss at every feature, so its population and empirical risks are both $0$ . For $S = ((j, 0))$ , the memorizing learner predicts $0$ at $j$ and $1$ at the other $N - 1$ features. Thus its empirical risk is $0$ and its population risk is $(N - 1) / N$ .

1.2A2F4F6givenalgebra

Fix any $z = (j, y)$ and one-point sample $S = (z)$ . Since $H$ contains every binary labeling, some $h$ has loss $g_{h} (z) = 0$ and some has $g_{h} (z) = 1$ . For sign $σ = + 1$ , $\sup_{g \in G} σ g (z) = 1$ ; for sign $σ = - 1$ , the supremum is $0$ . The two equiprobable signs therefore give ${\hat{R}}_{S} (G) = 1 / 2$ for every $S$ , and averaging over $S \sim P$ gives $R_{1} (G) = 1 / 2$ .

2.1F1F3step 1.1algebra

The constant learner returns $h_{0}$ on both $S$ and its deletion, so its size-one stability coefficient is $0$ . The empty-sample memorizer predicts $1$ at $j$ , whereas the full-sample memorizer predicts $0$ there; at test point $(j, 0)$ the loss changes by $1$ . Every zero-one loss difference is at most $1$ , hence the memorizer's coefficient is exactly $1$ .

3.1A1A2F2F5F7F8step 1.1step 1.2algebra∎

With $m = 1$ , [F5] has complexity term $2 R_{1} (G) = 1$ , and [F7]–[F8] make its confidence term positive for every $δ \in (0, 1)$ . Every zero-one loss deviation is at most $1$ , so this class-wide upper bound is no sharper than the trivial range, while step 1.1 gives the constant learner an exact zero gap and the memorizer zero training risk with a large population risk.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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