TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

High-probability generalization from uniform stability

Statement

Assume the Axiom of Choice. Let $(X, Σ_{X})$ and $(Y, Σ_{Y})$ be nonempty measurable instance and label spaces, and equip $Z = X \times Y$ with $Σ_{Z} = Σ_{X} \otimes Σ_{Y}$ . Let $P$ be a probability measure on $(Z, Σ_{Z})$ , let $F$ be a nonempty class of measurable functions $f : (X, Σ_{X}) \to (R, B (R))$ , and let $ℓ : R \times Y \to [0, \infty)$ be measurable with respect to $B (R) \otimes Σ_{Y}$ . For $f \in F$ and $z = (x, y)$ write $L_{f} (z) = ℓ (f (x), y)$ , $R_{P} (f) = \int_{Z} L_{f} (z) P (d z)$ , and ${\hat{R}}_{S} (f) = m^{- 1} \sum_{i = 1}^{m} L_{f} (Z_{i})$ . Let $S = (Z_{1}, \dots, Z_{m})$ have product law $P^{m}$ on $(Z^{m}, Σ_{Z}^{\otimes m})$ , with $m \geq 1$ , and let $A$ be a deterministic, permutation-invariant size-indexed learning rule that outputs members of $F$ and has a nonincreasing uniform deletion-stability sequence $(β_{n})_{n \geq 1}$ . Assume the maps $(S, z) \mapsto L_{A_{S}} (z)$ and $(S, z) \mapsto L_{A_{S ∖ i}} (z)$ for every $i \in [m]$ are jointly measurable on the sample/test product space, and all sample-dependent risk, empirical-risk, and leave-one-out maps in the conclusions are measurable, and assume $0 \leq L_{A_{T}} (z) \leq M < \infty$ for every full or deleted sample $T$ and every $z \in Z$ . Define $R_{l o o} (A, S) = m^{- 1} \sum_{i = 1}^{m} L_{A_{S ∖ i}} (Z_{i})$ using the size- $m$ deletion output. For each $δ \in (0, 1)$ , the following two bounds hold separately, each with probability at least $1 - δ$ over $S \sim P^{m}$ :

$R_{P} (A_{S}) \leq {\hat{R}}_{S} (A_{S}) + 2 β_{m} + (4 m β_{m} + M) \sqrt{\frac{\log (1 / δ)}{2 m}},$

$R_{P} (A_{S}) \leq R_{l o o} (A, S) + β_{m} + (4 m β_{m} + M) \sqrt{\frac{\log (1 / δ)}{2 m}} .$

The displayed probability guarantees are separate and need not hold on the same event.

Statement references

The natural logarithm in the confidence terms is defined by The natural logarithm as the inverse of the exponential function.

Its positivity on arguments greater than $1$ follows from Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm.

Bousquet and Elisseeff, Theorem 12 and full proof, printed pp. 507–509, give these two separate bounds under deletion stability. Full JMLR paper PDF

Mohri, Rostamizadeh, and Talwalkar, Theorem 14.2 and complete proof, printed pp. 334–336, give the corresponding replacement-stability bound. Full second-edition book PDF

Facts & Assumptions

Given: AC, an IID product sample, a measurable supervised loss, a permutation-invariant rule with uniform deletion stability, jointly measurable sample-dependent test losses, measurable sample-dependent risks, and the common finite loss bound $M$ .

[A1]

Assume AC. It is used through the bounded-differences supplier, whose conditional-expectation and martingale proof assumes AC. The Axiom of Choice

[A2]

The full and deleted sample-dependent test losses are jointly measurable in the sample and test observation. The sample-dependent risk, empirical-risk, and leave-one-out maps are measurable, and $0 \leq L_{A_{T}} (z) \leq M$ .

[F1]

Population risk is the $P$ -integral of the loss; empirical risk is its finite sample average. Population and empirical risk

[F2]

Uniform deletion stability bounds the pointwise loss change from a full output to its size- $m$ deletion output by $β_{m}$ . Uniform algorithmic stability under deletion

[F3]

IID means mutually independent sample coordinates with common law $P$ . Identical distribution and IID families

[F4]

The expected stability theorem gives $E [R_{P} (A_{S}) - {\hat{R}}_{S} (A_{S})] \leq 2 β_{m}$ , $E [R_{P} (A_{S}) - R_{l o o} (A, S)] \leq β_{m}$ , and the pointwise risk-change bound $∣ R_{P} (A_{S}) - R_{P} (A_{S ∖ i}) ∣ \leq β_{m}$ . Expected generalization from uniform stability

[F5]

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

[F6]

The natural logarithm is strictly increasing and $\log 1 = 0$ , so $x > 1$ implies $\log x > 0$ . Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F7]

Under AC, for independent coordinates and a product-measurable integrable function whose $i$ th coordinate oscillation is at most $c_{i}$ , McDiarmid gives $P {F - E F \geq t} \leq \exp (- 2 t^{2} / \sum_{i} c_{i}^{2})$ for $t > 0$ when $\sum_{i} c_{i}^{2} > 0$ . McDiarmid bounded-differences inequality

Proof

1.1A2F1F2F4givenalgebra

Fix an index $k$ and let $S^{'}$ be any sample that differs from $S$ only at coordinate $k$ . Their retained samples $S ∖ k$ and $S^{'} ∖ k$ coincide. By [F4], $∣ R_{P} (A_{S}) - R_{P} (A_{S^{'}}) ∣ \leq ∣ R_{P} (A_{S}) - R_{P} (A_{S ∖ k}) ∣ + ∣ R_{P} (A_{S^{'} ∖ k}) - R_{P} (A_{S^{'}}) ∣ \leq 2 β_{m}$ . For every $j \neq k$ , the two loss terms at the common test point $Z_{j}$ differ by at most $2 β_{m}$ , by [F2] through the same deleted output. The two $k$ th loss terms each lie in $[0, M]$ , so their difference is at most $M$ . Hence $∣ {\hat{R}}_{S} (A_{S}) - {\hat{R}}_{S^{'}} (A_{S^{'}}) ∣ \leq 2 (m - 1) β_{m} / m + M / m \leq 2 β_{m} + M / m$ . For $Φ (S) = R_{P} (A_{S}) - {\hat{R}}_{S} (A_{S})$ this yields the coordinate oscillation $∣ Φ (S) - Φ (S^{'}) ∣ \leq 4 β_{m} + M / m$ .

1.2A2F2F4givenconstructalgebra

Fix an index $k$ and samples $S, S^{'}$ differing only at coordinate $k$ . The risk term in $Ψ (S) = R_{P} (A_{S}) - R_{l o o} (A, S)$ changes by at most $2 β_{m}$ by [F4]. In the leave-one-out average, the $k$ th term uses the same deleted training sample for $S$ and $S^{'}$ , and its test losses differ by at most $M$ . For $j \neq k$ , the two deleted training samples $S ∖ j$ and $S^{'} ∖ j$ have the same $m - 2$ common observations and the two alternative $k$ th observations. Form a size- $m$ indexed sample $T$ from those $m - 2$ common observations and both alternatives. Up to permutation, each of the two deleted training samples is obtained by deleting one of the alternatives from $T$ . Permutation invariance and [F2] therefore bound their loss change at the common test point $Z_{j}$ by $2 β_{m}$ . When $m = 1$ there are no indices $j \neq k$ , so only the $k$ th term occurs. Thus the leave-one-out average changes by at most $2 (m - 1) β_{m} / m + M / m \leq 2 β_{m} + M / m$ , and $∣ Ψ (S) - Ψ (S^{'}) ∣ \leq 4 β_{m} + M / m$ .

2.1A1A2F3F4F5F6F7step 1.1givenalgebra

Put $c = 4 β_{m} + M / m$ . If $c = 0$ , then $M = β_{m} = 0$ and every loss and both gaps vanish. If $c > 0$ , then $Φ$ is bounded, measurable, and integrable by [A2]. Since $0 < δ < 1$ , [F5]–[F6] give $\log (1 / δ) > 0$ , so $t = c \sqrt{m \log (1 / δ) / 2} > 0$ . The product law $P^{m}$ makes the coordinates independent by [F3], and [F7] with all $m$ coordinate bounds equal to $c$ gives $P {Φ - E Φ \geq t} \leq \exp (- 2 t^{2} / (m c^{2})) = δ$ . By [F4], outside this event $Φ \leq 2 β_{m} + t = 2 β_{m} + (4 m β_{m} + M) \sqrt{\log (1 / δ) / (2 m)}$ . Together with the $c = 0$ case this proves the first probability bound.

3.1A1A2F3F4F5F6F7step 1.2givenalgebra∎

With $c = 4 β_{m} + M / m$ , the case $c = 0$ again has zero losses and zero gaps. If $c > 0$ , [A2] makes $Ψ$ bounded, measurable, and integrable. Since $0 < δ < 1$ , [F5]–[F6] give $\log (1 / δ) > 0$ . The product law $P^{m}$ makes the coordinates independent by [F3], and [F7] with coordinate bounds $c$ gives $P {Ψ - E Ψ \geq c \sqrt{m \log (1 / δ) / 2}} \leq δ$ . By [F4], $E Ψ \leq β_{m}$ , so outside this event $Ψ \leq β_{m} + (4 m β_{m} + M) \sqrt{\log (1 / δ) / (2 m)}$ . This proves the second probability bound, separately from the first.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

46 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

Olivier Bousquet and André Elisseeff, Stability and Generalization, JMLR 2 (2002), Theorem 12 and proof (standard reference, not scraped)
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Theorem 14.2 and proof (standard reference, not scraped)