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.

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.

Depends on

Used by

Dependency tree · two levels

53 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, arXiv-version Theorem 3.8 and proof (conference Theorem 3.7) (standard reference, not scraped)
Nikolai Matni, ESE680 Lecture 16: Algorithmic Stability and Stochastic Gradient Descent, Theorem 3 and proof (standard reference, not scraped)