TheoremStatement: 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.

Uniform stability implies expected generalization

Statement

Let $n \geq 1$ and consider a supervised prediction problem with measurable observation space $Z = X \times Y$ , probability law $P$ , measurable predictor class $F$ , and nonnegative measurable loss $ℓ$ . For $f \in F$ and $z = (x, y)$ , write $L_{f} (z) = ℓ (f (x), y)$ , $R_{P} (f) = \int L_{f} (z) P (d z)$ , and, for $S = (Z_{1}, \dots, Z_{n})$ , ${\hat{R}}_{S} (f) = n^{- 1} \sum_{i = 1}^{n} L_{f} (Z_{i})$ . Let $Z_{1}, \dots, Z_{n}$ be IID with law $P$ , and let $U_{n}$ be internal randomness independent of the sample. Suppose the randomized learning rule $A_{n} (S, U_{n})$ takes values in $F$ , the joint loss map $(S, U_{n}, z) \mapsto L_{A_{n} (S, U_{n})} (z)$ is measurable, and all displayed risks are integrable. If $A_{n}$ has uniform replacement stability at level $ε$ , then

$∣ E_{S, U_{n}} [R_{P} (A_{n} (S, U_{n})) - {\hat{R}}_{S} (A_{n} (S, U_{n}))] ∣ \leq ε .$

The expectation is over both the IID sample and the algorithm's internal randomness. No permutation-invariance assumption on $A_{n}$ is required.

Statement references

Hardt, Recht, and Singer, Theorem 2.2 and proof: full arXiv paper.

Matni, Lecture 16, Theorem 2 and proof: full lecture notes.

Facts & Assumptions

Given: The supervised prediction problem, IID sample, independent algorithmic randomness, measurable and integrable loss maps, and uniform replacement stability in the Statement.

[F1]

Supervised prediction problems: the joint observation law is a probability measure and the loss is nonnegative and measurable.

[F2]

Population and empirical risk: population risk is the nonnegative integral of test loss and empirical risk is its finite sample average.

[F3]

Identical distribution and IID families: the observations are mutually independent and have common law $P$ .

[F4]

An IID sample and ghost point are exchangeable: if $Z_{*}$ is an independent observation with law $P$ , then $(S, Z_{*})$ and $(S^{(i)}, Z_{i})$ have the same law for each $i$ , where $S^{(i)}$ replaces coordinate $i$ by $Z_{*}$ .

[F5]

Fubini's theorem for L^1 functions on a sigma-finite product: for the integrable joint loss map, its product integral equals either iterated integral, including integration over the independent algorithm seed and test observation.

[F6]

The Lebesgue integral is linear on $L^{1} (μ)$ : the integral of a finite sum of integrable functions is the sum of their integrals.

[F7]

The modulus of an integral is bounded by the integral of the modulus: the absolute value of an integral is at most the integral of the absolute value.

[F8]

Uniform stability for randomized learning rules: for every fixed adjacent pair of ordered samples and test observation, the difference of their expected losses over $U_{n}$ has absolute value at most $ε$ .

[A1]

The joint loss map is measurable and integrable, as required in the Statement, so Fubini and every displayed expectation are defined.

Proof

1.1A1F1F2F3F4F5givenconstruct

Extend the sample by an independent ghost observation $Z_{*} \sim P$ . By [F1], [F2], and [F5], $E_{S, U_{n}} R_{P} (A_{n} (S, U_{n})) = E_{S, U_{n}, Z_{*}} L_{A_{n} (S, U_{n})} (Z_{*})$ . For each $i$ , [F4] and independence of $U_{n}$ imply $E_{S, U_{n}, Z_{*}} L_{A_{n} (S, U_{n})} (Z_{*}) = E_{S, U_{n}, Z_{*}} L_{A_{n} (S^{(i)}, U_{n})} (Z_{i})$ .

2.1A1F2F6F7F8step 1.1givenalgebra∎

By [F2] and [F6], subtracting the expected empirical risk and averaging the equalities in step 1.1 gives $E_{S, U_{n}} [R_{P} (A_{n} (S, U_{n})) - {\hat{R}}_{S} (A_{n} (S, U_{n}))] = \frac{1}{n} \sum_{i = 1}^{n} E_{S, U_{n}, Z_{*}} [L_{A_{n} (S^{(i)}, U_{n})} (Z_{i}) - L_{A_{n} (S, U_{n})} (Z_{i})] .$ For every fixed $S, Z_{*}$ , the samples $S^{(i)}$ and $S$ differ in one coordinate, so [F8] bounds the absolute value of the inner expectation over $U_{n}$ by $ε$ . Applying [F7] to the outer expectations and then averaging gives the claimed absolute bound.

Depends on

Used by

Dependency tree · two levels

29 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

Moritz Hardt, Benjamin Recht, and Yoram Singer, Train faster, generalize better: Stability of stochastic gradient descent, Theorem 2.2 and proof (standard reference, not scraped)
Nikolai Matni, ESE680 Lecture 16: Algorithmic Stability and Stochastic Gradient Descent, Theorem 2 and proof (standard reference, not scraped)