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.

Algorithmic stability of stochastic training

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

An IID sample and ghost point are exchangeable

Statement

Let $(Z, Σ)$ be a measurable space, let $P$ be a probability measure on it, and let $m \geq 1$ . If $Z_{1}, \dots, Z_{m}, Z_{*}$ are IID random elements with law $P$ , define $S = (Z_{1}, \dots, Z_{m})$ and, for $i \in {1, \dots, m}$ , let $S^{(i)}$ be $S$ with coordinate $i$ replaced by $Z_{*}$ . Then the random vectors $(S, Z_{*})$ and $(S^{(i)}, Z_{i})$ have the same distribution on the finite product measurable space $(Z^{m + 1}, Σ^{\otimes (m + 1)})$ .

Statement references

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

Matni, Lecture 16, §3.1, proof of Theorem 2: full lecture notes.

Facts & Assumptions

Given: A common measurable target, a probability law $P$ , and the IID random elements in the Statement.

[F1]

Identical distribution and IID families: IID means mutual independence together with equality of all coordinate laws.

[F2]

Independent sigma-algebras and independent events: for any finite selection of coordinate events, their intersection has probability equal to the product of their probabilities.

[F3]

The product sigma-algebra and its finite iterates: finite product sigma-algebras are generated recursively by coordinate measurable rectangles.

[F4]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique: a finite product measure is uniquely determined by its values on coordinate rectangles; this follows by iterating the stated two-factor uniqueness theorem.

Proof

1.1F1F2given

Fix $i \in {1, \dots, m}$ and a measurable rectangle $B_{1} \times \dots \times B_{m + 1}$ . By [F1] and [F2], its probability under $(S, Z_{*})$ is $\prod_{j = 1}^{m + 1} P (B_{j})$ . The vector $(S^{(i)}, Z_{i})$ swaps coordinates $i$ and $m + 1$ , so the same rectangle has probability $\prod_{j = 1}^{m + 1} P (B_{j})$ under that vector as well.

2.1F3F4step 1.1given∎

Each vector is measurable: the preimage of a coordinate rectangle is a finite intersection of measurable coordinate events, and [F3] says these rectangles generate $Σ^{\otimes (m + 1)}$ . Thus both vector laws are probability measures on that product sigma-algebra. They agree on its generating coordinate rectangles by step 1.1; iterating [F4] along the recursive finite product in [F3] identifies both with the same product measure. Hence their distributions agree.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Uniform stability for randomized learning rules

Definition

Fix a supervised prediction problem with observation space $Z = X \times Y$ , measurable predictor class $F$ , and nonnegative measurable loss $ℓ$ . Write $L_{f} (x, y) = ℓ (f (x), y)$ for $f \in F$ . Fix a sample size $n \geq 1$ . A randomized learning rule at this sample size consists of internal randomness $U_{n}$ with law $Q_{n}$ , independent of the sample, and an output $A_{n} (S, U_{n}) \in F$ for every ordered sample $S \in Z^{n}$ . Assume the expected test losses below are finite. For $ε \geq 0$ , the rule has uniform replacement stability at level $ε$ if, for every pair $S, S^{'} \in Z^{n}$ differing in at most one coordinate, and every test observation $z \in Z$ ,

$∣ E_{U_{n}} L_{A_{n} (S, U_{n})} (z) - E_{U_{n}} L_{A_{n} (S^{'}, U_{n})} (z) ∣ \leq ε .$

The absolute value is outside expectation over the internal randomness. No permutation-invariance condition is imposed on the learning rule.

Definition references

Hardt, Recht, and Singer, Definition 2.1: full arXiv paper.

Matni, Lecture 16, Definition 1: full lecture notes.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

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.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Expected generalization of convex stochastic gradient training

Statement

Let $n, T, d \geq 1$ , let $β > 0$ and $L \geq 0$ , and let $(X, Σ_{X})$ , $(Y, Σ_{Y})$ , and $(A, Σ_{A})$ be measurable spaces. Let $P$ be a probability measure on $X \times Y$ , let $ℓ : A \times Y \to [0, + \infty)$ be a measurable loss, and let $f_{w} : X \to A$ be a measurable predictor for every $w \in R^{d}$ . For $z = (x, y)$ set $g (w, z) = ℓ (f_{w} (x), y)$ and assume this map and $(w, z) \mapsto \nabla_{w} g (w, z)$ are jointly measurable. For every observation $z$ , assume $w \mapsto g (w, z)$ is totally differentiable and convex, its Euclidean gradient is $β$ -Lipschitz, and its values are $L$ -Lipschitz in the sense that $∣ g (w, z) - g (v, z) ∣ \leq L ∥ w - v ∥_{2}$ for all $w, v \in R^{d}$ . Let $S = (Z_{1}, \dots, Z_{n})$ be IID with law $P$ , and abbreviate $R_{P} (f_{w}) = \int g (w, z) P (d z)$ and ${\hat{R}}_{S} (f_{w}) = n^{- 1} \sum_{i = 1}^{n} g (w, Z_{i})$ . Let $I_{1}, \dots, I_{T}$ be random indices in ${1, \dots, n}$ , independent of $S$ and satisfying $P (I_{t} = i) = 1 / n$ for every $1 \leq t \leq T$ and $1 \leq i \leq n$ ; dependence between indices at different times is allowed. From a fixed $w_{0} \in R^{d}$ , set

$w_{t} = w_{t - 1} - α_{t} \nabla_{w} g (w_{t - 1}, Z_{I_{t}}), 1 \leq t \leq T,$

where the deterministic steps satisfy $0 \leq α_{t} \leq 2 / β$ . Assume the displayed sample-dependent loss and risk maps are measurable and integrable. Then this randomized procedure has uniform replacement stability at level

$ε_{s t a b} = \frac{2 L^{2}}{n} \sum_{t = 1}^{T} α_{t},$

and its expected population-minus-empirical risk gap satisfies

$∣ E_{S, I} [R_{P} (f_{w_{T}}) - {\hat{R}}_{S} (f_{w_{T}})] ∣ \leq ε_{s t a b} .$

The result concerns the specified uniform-marginal sample-selection updates, including independent sampling with replacement and uniform random-permutation passes. It does not assert generalization for every stochastic-gradient oracle.

Statement references

Hardt, Recht, and Singer, arXiv-version Theorem 3.8 and proof (conference Theorem 3.7): full arXiv paper.

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

Facts & Assumptions

Given: The IID supervised sample, independent uniform-marginal indices, fixed initialization, loss hypotheses, and integrability conditions in the Statement.

[F1]

Convex and strictly convex functions on Euclidean convex sets: convexity is the segment inequality on a convex Euclidean domain.

[F2]

The total (Fréchet) derivative $D f (a)$ as the linear first-order approximation with $o (∥ h ∥_{2})$ remainder and The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: total differentiability means a linear first-order approximation with normwise $o (∥ h ∥_{2})$ remainder, and the scalar gradient is the vector of its partial derivatives.

[F3]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $⟨ u, v ⟩$ is the Euclidean inner product and $∥ u ∥_{2} = \sqrt{⟨ u, u ⟩}$ .

[F4]

For a differentiable scalar field, $D_{v} f (a) = ⟨ \nabla f (a), v ⟩$ and the unit direction of steepest ascent is the normalized gradient: for a totally differentiable scalar field, $D_{v} g (w, z) = ⟨ \nabla_{w} g (w, z), v ⟩$ .

[F5]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: the Euclidean norm satisfies the triangle inequality and every normalized nonzero vector has norm $1$ .

[F6]

Gradient steps of smooth convex functions are nonexpansive: for a differentiable convex loss with $β$ -Lipschitz gradient, the update $w \mapsto w - α \nabla ℓ (w, z)$ is nonexpansive when $0 \leq α \leq 2 / β$ .

[F7]

Uniform stability for randomized learning rules: stability compares expected test losses for every fixed neighboring ordered sample pair and every fixed test observation.

[F8]

Uniform stability implies expected generalization: uniform replacement stability at level $ε$ implies an absolute expected generalization gap at most $ε$ when the sample, algorithm, and risk maps satisfy its measurability and integrability hypotheses.

[F9]

Supervised prediction problems and Population and empirical risk: the test loss, population risk, and empirical risk use the stated measurable loss and law $P$ .

[F10]

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

[A1]

The random index vector is independent of the sample and each coordinate is uniform; no independence between different indices is assumed.

[A2]

The population-risk and empirical-risk random variables are measurable and integrable, as required in the Statement.

Proof

1.1F2F3F4F5givenalgebra

Fix $w, z$ and suppose $\nabla_{w} g (w, z) \neq 0$ . Put $v = \nabla_{w} g (w, z) / ∥ \nabla_{w} g (w, z) ∥_{2}$ , which is a unit vector by [F3] and [F5]. The directional derivative of $t \mapsto g (w + t v, z)$ at $0$ is $⟨ \nabla_{w} g (w, z), v ⟩ = ∥ \nabla_{w} g (w, z) ∥_{2}$ by [F2] and [F4]. The $L$ -Lipschitz inequality in the Statement bounds every difference quotient by $L$ , so passage to the derivative gives $∥ \nabla_{w} g (w, z) ∥_{2} \leq L$ ; the same bound is immediate when the gradient is zero.

2.1A1F1F5F6step 1.1givenconstruct

Fix neighboring samples $S, S^{'}$ differing at coordinate $j$ and couple their runs using the same index vector. Put $δ_{t} = ∥ w_{t} (S) - w_{t} (S^{'}) ∥_{2}$ , so $δ_{0} = 0$ . If $I_{t} \neq j$ , both runs apply the same convex-loss gradient step and [F6] gives $δ_{t} \leq δ_{t - 1}$ . If $I_{t} = j$ , the triangle inequality from [F5] and step 1.1 give $δ_{t} \leq δ_{t - 1} + 2 α_{t} L$ . Thus, pathwise, $δ_{t} \leq δ_{t - 1} + 2 α_{t} L 1_{{I_{t} = j}}$ .

3.1A1step 2.1algebra

Taking expectation in the pathwise inequality and using only $P (I_{t} = j) = 1 / n$ yields $E δ_{t} \leq E δ_{t - 1} + 2 α_{t} L / n$ . Summing from $t = 1$ to $T$ gives $E δ_{T} \leq (2 L / n) \sum_{t = 1}^{T} α_{t}$ .

4.1F7step 3.1givenalgebra

For every test observation $z$ , the value-Lipschitz hypothesis gives $E_{I} ∣ g (w_{T} (S), z) - g (w_{T} (S^{'}), z) ∣ \leq L E δ_{T} \leq (2 L^{2} / n) \sum_{t} α_{t}$ . Hence the absolute difference of the two expected losses is at most this value, proving the stated uniform stability.

5.1A1A2F8F9F10step 4.1given∎

The sample is IID by [F10], the index vector is independent of it by [A1], and the risk maps $R_{P} (f_{w_{T}})$ and ${\hat{R}}_{S} (f_{w_{T}})$ are measurable and integrable by [A2]; they use the loss and risk conventions of [F9]. Apply [F8] with the stability level from step 4.1 to obtain the expected generalization bound.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Expected generalization of nonconvex stochastic gradient training

Statement

Let $n \geq 2$ , $T, d \geq 1$ , and let $β, c > 0$ and $L \geq 0$ . Let $(X, Σ_{X})$ , $(Y, Σ_{Y})$ , and $(A, Σ_{A})$ be measurable spaces, let $P$ be a probability measure on $X \times Y$ , let $ℓ : A \times Y \to [0, + \infty)$ be a measurable loss, and let $f_{w} : X \to A$ be a measurable predictor for every $w \in R^{d}$ . For $z = (x, y)$ set $g (w, z) = ℓ (f_{w} (x), y)$ . Assume $(w, z) \mapsto g (w, z)$ and $(w, z) \mapsto \nabla_{w} g (w, z)$ are jointly measurable. For every $z$ , assume $g (\cdot, z)$ is totally differentiable, takes values in $[0, 1]$ , is $L$ -Lipschitz in values, and has a $β$ -Lipschitz Euclidean gradient; these mean, respectively,

$∣ g (w, z) - g (v, z) ∣ \leq L ∥ w - v ∥_{2}, ∥ \nabla_{w} g (w, z) - \nabla_{w} g (v, z) ∥_{2} \leq β ∥ w - v ∥_{2}$

for all $v, w \in R^{d}$ . No convexity is assumed. Let $S = (Z_{1}, \dots, Z_{n})$ be IID with law $P$ , and abbreviate $R_{P} (f_{w}) = \int g (w, z) P (d z)$ and ${\hat{R}}_{S} (f_{w}) = n^{- 1} \sum_{i = 1}^{n} g (w, Z_{i})$ . Let $I_{1}, \dots, I_{T}$ be random indices in ${1, \dots, n}$ , independent of $S$ and satisfying $P (I_{t} = i) = 1 / n$ for every $1 \leq t \leq T$ and $1 \leq i \leq n$ ; dependence between indices at different times is allowed. From a fixed $w_{0} \in R^{d}$ , define

$w_{t} = w_{t - 1} - α_{t} \nabla_{w} g (w_{t - 1}, Z_{I_{t}}), 1 \leq t \leq T,$

where $0 \leq α_{T} \leq \dots \leq α_{1}$ and $α_{t} \leq c / t$ . Assume the resulting random variables $R_{P} (f_{w_{T}})$ and ${\hat{R}}_{S} (f_{w_{T}})$ are measurable; they are integrable because $0 \leq g \leq 1$ . Then the randomized procedure has uniform replacement stability and absolute expected population-minus-empirical risk gap at most

$(1 + \frac{1}{β c}) \frac{(2 c L^{2})^{1 / (β c + 1)}}{n - 1} T^{β c / (β c + 1)} .$

If $L = 0$ , the right side is interpreted as $0$ . The conclusion concerns only this expected gap for the stated random sample-selection procedure; it does not assert generalization for every stochastic-gradient oracle.

Statement references

Hardt, Recht, and Singer, arXiv-version Theorem 3.12 and complete proof (conference Theorem 3.8): full arXiv paper.

Matni, Lecture 16, §4: full lecture notes.

Facts & Assumptions

Given: The supervised IID sample, independent uniform-marginal indices, fixed initialization, loss range/Lipschitz/smoothness assumptions, nonincreasing steps, and integrable risk maps in the Statement.

[F1]

[F2]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $⟨ u, v ⟩$ is the Euclidean inner product and $∥ u ∥_{2} = \sqrt{⟨ u, u ⟩}$ .

[F3]

[F4]

[F5]

Uniform stability for randomized learning rules: uniform replacement stability bounds the absolute difference of expected test losses for every fixed adjacent sample pair and test observation.

[F6]

Uniform stability implies expected generalization: such a stability bound implies the same absolute expected population-minus-empirical risk gap under its IID, measurability, and integrability conditions.

[F7]

$1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ , The exponential function is strictly increasing, and The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ : $1 + x \leq \exp (x)$ , the exponential is increasing, and exponentials multiply by addition of exponents.

[F8]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log b - \log a = \int_{a}^{b} x^{- 1} d x$ for $0 < a \leq b$ , and $\log (b / a) = \log b - \log a$ .

[F9]

Real powers for positive bases, with the zero-base positive-exponent convention: for $a > 0$ , $a^{q} = \exp (q \log a)$ ; Continuity and derivatives of positive-base real powers gives $(x^{q})^{'} = q x^{q - 1}$ on $(0, \infty)$ .

[F10]

The second fundamental theorem: if $G$ is differentiable on $[a, b]$ with $G^{'} = f$ and $f$ is integrable, then $\int_{a}^{b} f = G (b) - G (a)$ : for $a < b$ , if $G$ is differentiable on $[a, b]$ and $G^{'}$ is integrable there, then $\int_{a}^{b} G^{'} = G (b) - G (a)$ .

[F11]

For $a < c < b$ : $f$ is integrable on $[a, b]$ if and only if it is integrable on $[a, c]$ and on $[c, b]$ , and then $\int_{a}^{b} f = \int_{a}^{c} f + \int_{c}^{b} f$ ; with the oriented form for arbitrary $a, b, c$ and If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$ : finite adjacent interval integrals add, and pointwise ordered integrands have ordered integrals.

[F12]

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

[F13]

Supervised prediction problems and Population and empirical risk: the loss, population risk, and empirical risk use the stated measurable observation law and loss.

[F14]

A continuous function on $[a, b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion: every continuous real function on a compact interval $[a, b]$ with $a < b$ is Riemann integrable there.

[A1]

The joint loss and gradient maps and the displayed population-risk and empirical-risk random variables are measurable. The loss range $[0, 1]$ makes all these risks integrable.

[A2]

Each sample index is uniform and the whole index vector is independent of the sample; no cross-time independence is assumed.

Proof

1.1F1F2F3F4givenalgebra

For any $w, z$ with $\nabla_{w} g (w, z) \neq 0$ , take $v = \nabla_{w} g (w, z) / ∥ \nabla_{w} g (w, z) ∥_{2}$ , which is a unit vector by [F2] and [F4]. The directional derivative of $t \mapsto g (w + t v, z)$ at zero is $∥ \nabla_{w} g (w, z) ∥_{2}$ by [F1] and [F3], while the value-Lipschitz condition bounds the absolute difference quotient by $L$ . Thus $∥ \nabla_{w} g (w, z) ∥_{2} \leq L$ ; the zero-gradient case is immediate.

1.2F7F8F9F11givenalgebra

Put $q = β c > 0$ . By [F7], $α_{k} \leq c / k$ , and finite multiplication, $\prod_{k = s + 1}^{T} (1 + β α_{k}) \leq \exp ⁣ (q \sum_{k = s + 1}^{T} \frac{1}{k}) .$ If $s = T$ , the product is empty and equals $(T / s)^{q} = 1$ . If $s < T$ , then for each $k > s$ and $x \in [k - 1, k]$ , $1 / x \geq 1 / k$ , so [F11] gives $1 / k \leq \int_{k - 1}^{k} d x / x$ . Additivity over these nondegenerate intervals and [F8] yield $\sum_{k = s + 1}^{T} 1 / k \leq \int_{s}^{T} d x / x = \log (T / s)$ . Therefore the product is at most $(T / s)^{q}$ by [F8] and [F9].

2.1A2F4step 1.1givenconstruct

Fix neighboring samples $S, S^{'}$ that differ at coordinate $j$ and couple their runs using the same index vector. Let $δ_{t} = ∥ w_{t} (S) - w_{t} (S^{'}) ∥_{2}$ , with $δ_{0} = 0$ . If $I_{t} \neq j$ , the same example is used in both updates, so gradient smoothness gives $δ_{t} \leq (1 + β α_{t}) δ_{t - 1}$ . If $I_{t} = j$ , add and subtract $\nabla_{w} g (w_{t - 1} (S^{'}), Z_{j})$ ; smoothness for the common example, the triangle inequality from [F4], and step 1.1 give $δ_{t} \leq (1 + β α_{t}) δ_{t - 1} + 2 α_{t} L$ . Thus, for every update, $δ_{t} \leq (1 + β α_{t}) δ_{t - 1} + 2 α_{t} L 1_{{I_{t} = j}} .$

3.1A2step 2.1givenalgebra

Iterating the finite recurrence in step 2.1 from $δ_{0} = 0$ yields $δ_{T} \leq 2 L \sum_{s = 1}^{T} α_{s} 1_{{I_{s} = j}} \prod_{k = s + 1}^{T} (1 + β α_{k}) .$ The loss difference at any fixed test point is at most $1$ by the range hypothesis and at most $L δ_{T}$ by value-Lipschitzness. For nonnegative $a_{s}$ , $\min (1, \sum_{s} a_{s}) \leq \sum_{s} \min (1, a_{s})$ : if any $a_{s} \geq 1$ the right side is at least $1$ , and otherwise it equals $\sum_{s} a_{s}$ . Applying this to the displayed kicks and using $P (I_{s} = j) = 1 / n$ gives $E_{I} ∣ g (w_{T} (S), z) - g (w_{T} (S^{'}), z) ∣ \leq \frac{1}{n} \sum_{s = 1}^{T} \min ⁣ (1, 2 L^{2} α_{s} \prod_{k = s + 1}^{T} (1 + β α_{k})) .$

4.1F9F11F14step 1.1step 1.2step 3.1givenalgebra

If $L = 0$ , step 1.1 gives zero gradients, so the output is independent of the sample and stability is zero; set $r = 0$ . Suppose $L > 0$ and put $r = (2 c L^{2})^{1 / (q + 1)} T^{q / (q + 1)} > 0.$ By step 1.2 and $α_{s} \leq c / s$ , the $s$ th summand in step 3.1 is at most $h (s)$ , where $h (x) = \min {1, (r / x)^{q + 1}}$ for $x \geq 1$ . This function is continuous by [F9]. If $r \geq 1$ , it equals $1$ up to $r$ and then decreases; if $r < 1$ , it decreases throughout, since $(r / x)^{q + 1}$ has negative derivative. Thus it is nonincreasing. If $T = 1$ , the sum is $h (1)$ . If $T \geq 2$ , [F14] makes $h$ integrable on $[1, T]$ ; for each integer $s \geq 2$ , [F11] gives $h (s) \leq \int_{s - 1}^{s} h (x) d x$ . Additivity over these adjacent intervals then yields $\sum_{s = 1}^{T} h (s) \leq h (1) + \int_{1}^{T} h (x) d x$ .

5.1F9F10F11F14step 3.1step 4.1algebra

If $L = 0$ , step 4.1 gives stability zero. Suppose $L > 0$ . When $T = 1$ and $r \geq 1$ , $h (1) = 1 \leq (1 + 1 / q) r$ ; when $T = 1$ and $0 < r < 1$ , $h (1) = r^{q + 1} \leq (1 + 1 / q) r$ . Now let $T \geq 2$ . The displayed integrands are continuous on their compact intervals and hence integrable by [F14]. If $r \geq 1$ , then $h (1) = 1$ . For $T \leq r$ , $h = 1$ on $[1, T]$ and $\int_{1}^{T} h (x) d x = T - 1 \leq r - 1$ . For $T > r = 1$ , $h (x) = x^{- (q + 1)}$ on $[1, T]$ , so [F9] and [F10] give $\int_{1}^{T} h (x) d x = (1 / q) (1 - T^{- q}) \leq 1 / q$ . For $T > r > 1$ , split at $r$ using [F11] and integrate $1$ on $[1, r]$ and $r^{q + 1} x^{- (q + 1)}$ on $[r, T]$ to get $\int_{1}^{T} h (x) d x = (r - 1) + (r / q) (1 - (r / T)^{q}) \leq r - 1 + r / q$ . In each case $h (1) + \int_{1}^{T} h \leq (1 + 1 / q) r$ . If $0 < r < 1$ , then $h (1) = r^{q + 1}$ and [F9]–[F10] give $\int_{1}^{T} h (x) d x = \frac{r^{q + 1}}{q} (1 - T^{- q}) \leq \frac{r^{q + 1}}{q}$ , so $h (1) + \int_{1}^{T} h \leq (1 + 1 / q) r^{q + 1} \leq (1 + 1 / q) r$ . In every case, step 4.1 now bounds the sum in step 3.1 by $(1 + 1 / q) r$ . Therefore the right side of step 3.1 is at most $(1 + 1 / q) r / n$ .

6.1A1F5F6F12F13step 3.1step 4.1step 5.1givenalgebra∎

Steps 3.1, 4.1, and 5.1 show that every neighboring sample pair and test point has expected absolute loss change at most $(1 + 1 / q) r / n$ . This implies uniform replacement stability at that level by [F5]. Since $n \geq 2$ , $(1 + 1 / q) r / n \leq (1 + 1 / q) r / (n - 1)$ . The sample is IID by [F12], the risk conventions are [F13], and the measurable, integrable risks meet [A1]. Apply [F6] and substitute $q = β c$ and the value of $r$ to obtain the stated expected-gap bound.

4 · Examples, counterexamples and false statements

None yet.

Algorithmic stability of stochastic training

2 · Logical flowchart

3 · Definitions, theorems and proofs

An IID sample and ghost point are exchangeable

Statement

Statement references

Facts & Assumptions

Proof

Uniform stability for randomized learning rules

Definition

Definition references

Uniform stability implies expected generalization

Statement

Statement references

Facts & Assumptions

Proof

Expected generalization of convex stochastic gradient training

Statement

Statement references

Facts & Assumptions

Proof

Expected generalization of nonconvex stochastic gradient training

Statement

Statement references

Facts & Assumptions

Proof

4 · Examples, counterexamples and false statements

Sources