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 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]

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.

[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]

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 ⟩$ .

[F4]

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$ .

[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.

Depends on

Used by

Constant and inverse-time schedules give different stability bounds Example

Dependency tree · two levels

111 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.12 and complete proof (conference Theorem 3.8) (standard reference, not scraped)
Nikolai Matni, ESE680 Lecture 16: Algorithmic Stability and Stochastic Gradient Descent, §4 (standard reference, not scraped)