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.

✓ 3 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 3 also cleared it.

Algorithmic stability and generalization — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

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

Absolute-loss RKHS regularization has an explicit stability envelope

Example

Let $X = {x_{0}}$ and $Y = {0, 1}$ with their discrete sigma-algebras, and let $P (X = x_{0}, Y = 1) = q$ and $P (X = x_{0}, Y = 0) = 1 - q$ for $q \in [0, 1]$ . Take $H = R$ as the RKHS of the one-point kernel $K (x_{0}, x_{0}) = 1$ , so $f_{t} (x_{0}) = t$ and $∥ f_{t} ∥_{H} = ∣ t ∣$ . Use absolute loss $c (t, y) = ∣ t - y ∣$ and regularization parameter $λ > 0$ . For a size- $m$ sample and retained index set $J \subseteq [m]$ , use the fixed-denominator objective $m^{- 1} \sum_{j \in J} ∣ t - y_{j} ∣ + λ t^{2}$ . If $p_{J}$ and $r_{J}$ count the labels $1$ and $0$ in $J$ , respectively, its unique minimizer is $t_{J} = \min {1, \max {0, (p_{J} - r_{J}) / (2 λ m)}}$ . Thus all full and deleted outputs lie in $[0, 1]$ , every loss is bounded by $M = 1$ , and the deletion-stability coefficient satisfies $β_{m} \leq 1 / (2 λ m)$ . For $0 \leq t \leq 1$ , the population and empirical risks are $R_{P} (f_{t}) = q (1 - t) + (1 - q) t$ and ${\hat{R}}_{S} (f_{t}) = m^{- 1} [p_{[m]} (1 - t) + r_{[m]} t]$ .

Example references

The full-size deletion convention and RKHS stability conclusion are given by Strongly convex RKHS regularized ERM is stable.

Uniform deletion stability and its coefficient are defined by Uniform algorithmic stability under deletion.

The supervised prediction and loss setting is specified by Supervised prediction problems.

Population risk is an integral and empirical risk is the finite sample average by Population and empirical risk.

Facts & Assumptions

Given: The one-point supervised model, $q \in [0, 1]$ , $m \geq 1$ , $λ > 0$ , and a sample with labels in ${0, 1}$ .

[F1]

Population risk is the integral under $P$ and empirical risk is the sample average. Population and empirical risk

[F2]

Uniform deletion stability is the supremum loss change from a full output to its indexed deletion output. Uniform algorithmic stability under deletion

[F3]

For a real RKHS with $K (x, x) \leq κ^{2}$ and convex $σ$ -Lipschitz loss, attained fixed-denominator regularized ERM minimizers have $β_{m} \leq σ^{2} κ^{2} / (2 λ m)$ . Strongly convex RKHS regularized ERM is stable

[A1]

Here $K (x_{0}, x_{0}) = 1$ and $c (t, y) = ∣ t - y ∣$ ; each retained sample uses denominator $m$ and $λ > 0$ . Strongly convex RKHS regularized ERM is stable

Verification

1.1givenA1algebra

For $t \in [0, 1]$ , the objective is $p_{J} / m + (r_{J} - p_{J}) t / m + λ t^{2}$ , whose derivative vanishes at $(p_{J} - r_{J}) / (2 λ m)$ ; strict convexity gives the clipped formula as the unique minimizer on this interval. For $t < 0$ the objective is $p_{J} / m - ∣ J ∣ t / m + λ t^{2}$ and is decreasing toward $0$ ; for $t > 1$ it is $∣ J ∣ t / m - p_{J} / m + λ t^{2}$ and is increasing away from $1$ . Hence no global minimizer lies outside $[0, 1]$ , including when $J = \emptyset$ .

2.1F1A1step 1.1

Since $t_{J}, y \in [0, 1]$ , $∣ t_{J} - y ∣ \leq 1$ , so the common loss bound is $M = 1$ . Formula [F1] gives $R_{P} (f_{t}) = q (1 - t) + (1 - q) t$ and ${\hat{R}}_{S} (f_{t}) = m^{- 1} [p_{[m]} (1 - t) + r_{[m]} t]$ for $t \in [0, 1]$ . The map $t \mapsto ∣ t - y ∣$ is convex and satisfies $∣ ∣ t - y ∣ - ∣ s - y ∣ ∣ \leq ∣ t - s ∣$ , so $σ = 1$ ; the one-point RKHS has $κ = 1$ .

3.1F2F3step 2.1algebra∎

By [F2] and [F3], the learner has uniform deletion-stability coefficient $β_{m} \leq 1 / (2 λ m)$ ; step 2.1 independently verifies the bounded-loss premise required by the high-probability theorem.

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

A nearest-neighbor rule can have unit deletion instability and zero training loss

Example

Let $X = R$ with its Borel sigma-algebra and distance $d (x, x^{'}) = ∣ x - x^{'} ∣$ , and let $Y = A = {0, 1}$ with the discrete sigma-algebra. Let $P$ be any probability measure on $(X \times Y, B (R) \otimes 2^{{0, 1}})$ , let $F$ be the class of all Borel-measurable predictors $h : X \to A$ , and use the zero-one loss $ℓ (a, y) = 1 {a \neq y}$ , so $L (h, (x, y)) = ℓ (h (x), y)$ . Define a deterministic one-nearest-neighbor rule that predicts the majority label among all sample points at minimum distance from $x$ , resolving a tie by predicting $0$ ; on the empty sample it predicts $1$ everywhere. For a fixed finite sample, each nearest-index region is specified by finitely many distance comparisons and is Borel, so the resulting predictor belongs to $F$ . This rule is permutation-invariant. For any $m \geq 2$ , let $S$ contain one observation $(0, 0)$ and $m - 1$ copies of $(10, 1)$ . Its empirical risk is zero. At the test point $(1, 1)$ the full rule predicts $0$ and incurs loss $1$ , while the rule after deleting $(0, 0)$ predicts $1$ and incurs loss $0$ . Since the loss is bounded by $1$ , the uniform deletion-stability coefficient at size $m$ is exactly $1$ .

Example references

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

The supervised sample and loss setting is specified by Supervised prediction problems.

Empirical risk is the finite sample average by Population and empirical risk.

Facts & Assumptions

Given: The metric feature space, binary labels, zero-one loss, permutation-invariant nearest-neighbor rule, sample $S$ , and test point $(1, 1)$ in the Example.

[F1]

A supervised prediction problem includes measurable instance and label spaces, predictors, a joint sample law, and a measurable loss. Supervised prediction problems

[F2]

The empirical risk of a length- $m$ sample is the average of the $m$ loss values. Population and empirical risk

[F3]

The stability coefficient is the supremum of the deletion loss change over all samples, indices, and test observations. Uniform algorithmic stability under deletion

[A1]

The displayed sample contains exactly one point at feature $0$ with label $0$ and $m - 1$ copies at feature $10$ with label $1$ .

Verification

1.1A1F1F2givenalgebra

For a fixed finite sample, nearest-index regions are finite Boolean combinations of Borel distance comparisons, so the prediction map is measurable. The tie rule depends only on the multiset of labels at the minimum distance, so reordering the training sample leaves every prediction unchanged. At feature $0$ the unique nearest label is $0$ , and at feature $10$ all nearest labels are $1$ ; hence the rule predicts every training label correctly and [F2] gives empirical risk $0$ . At feature $1$ , the distances to $0$ and $10$ are $1$ and $9$ , so the unique nearest label is $0$ and the loss at $(1, 1)$ is $1$ .

2.1A1F3step 1.1algebra

After deleting the unique point $(0, 0)$ , every remaining training point has feature $10$ and label $1$ , so the nearest-neighbor rule predicts $1$ at feature $1$ and has test loss $0$ . The deletion loss change for this sample, deleted index, and test point is therefore $1$ , so [F3] gives a stability coefficient at least $1$ .

3.1F3step 2.1algebra∎

Every zero-one loss difference has absolute value at most $1$ , so every term in the supremum [F3] is at most $1$ . Step 2.1 attains this value for every $m \geq 2$ , hence the coefficient is exactly $1$ .

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

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.