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.

Stochastic gradient descent and random-iterate guarantees

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

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

Finite-horizon SGD trajectories have integrable objectives

Statement

Let $d \geq 1$ , let $(Ω, F, P)$ be a probability space, and let $f : R^{d} \to R$ be continuously differentiable with an $L$ -Lipschitz gradient for some finite $L \geq 0$ . Fix an integer $N \geq 1$ , measurable maps $x_{0}, G_{0}, \dots, G_{N - 1} : Ω \to R^{d}$ , and finite real stepsizes $α_{0}, \dots, α_{N - 1}$ . Suppose $E ∥ x_{0} ∥_{2}^{2} < \infty$ and $E ∥ G_{k} ∥_{2}^{2} < \infty$ for every $k < N$ , and define $x_{k + 1} = x_{k} - α_{k} G_{k}$ . Then every $x_{k}$ and $\nabla f (x_{k})$ for $0 \leq k \leq N$ has finite second moment, and every $f (x_{k})$ has finite absolute expectation.

Facts & Assumptions

Given: The probability space, measurable finite-dimensional vector maps, continuously differentiable $f$ , finite-horizon update and finite second-moment assumptions in the Statement.

[F1]

Descent inequality for a Lipschitz gradient: if $\nabla f$ is $L$ -Lipschitz, then $f (y) \leq f (x) + ⟨ \nabla f (x), y - x ⟩ + (L / 2) ∥ y - x ∥_{2}^{2}$ for all $x, y \in R^{d}$ .

[F2]

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

[F3]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ and $∥ u + v ∥_{2} \leq ∥ u ∥_{2} + ∥ v ∥_{2}$ .

[F4]

The principle of mathematical induction: a property true at the first index and inherited by each successor holds at every natural index.

[F5]

Expectation of a nonnegative or integrable random variable: expectations of nonnegative measurable functions are their extended integrals; an integrable real random variable has finite absolute integral.

Proof

1.1F2F3F5givenalgebra

By [F3] and $2 a b \leq a^{2} + b^{2}$ , $∥ u + v ∥_{2}^{2} \leq 2 ∥ u ∥_{2}^{2} + 2 ∥ v ∥_{2}^{2}$ . Thus $E ∥ x_{k + 1} ∥_{2}^{2} \leq 2 E ∥ x_{k} ∥_{2}^{2} + 2 α_{k}^{2} E ∥ G_{k} ∥_{2}^{2}$ for every $k < N$ . The right side is finite whenever $x_{k}$ has finite second moment, using the expectation convention [F5].

2.1F4F5step 1.1giveninduction

The initial second moment is finite by the Statement, and step 1.1 carries finiteness from $x_{k}$ to $x_{k + 1}$ . Finite induction using [F4] therefore gives $E ∥ x_{k} ∥_{2}^{2} < \infty$ for all $k \leq N$ .

3.1F1F3F5step 2.1givenalgebra

The Lipschitz-gradient condition [F1] and [F3] give $∥ \nabla f (x_{k}) ∥_{2} \leq ∥ \nabla f (0) ∥_{2} + L ∥ x_{k} ∥_{2}$ , so $∥ \nabla f (x_{k}) ∥_{2}^{2} \leq 2 ∥ \nabla f (0) ∥_{2}^{2} + 2 L^{2} ∥ x_{k} ∥_{2}^{2}$ . Step 2.1 makes the right side integrable; hence every stated gradient has finite second moment.

4.1F1F3F5step 2.1givenalgebra∎

Apply [F1] to $(0, x_{k})$ and $(x_{k}, 0)$ . The upper bound gives $f (x_{k}) \leq f (0) + ∥ \nabla f (0) ∥_{2} ∥ x_{k} ∥_{2} + (L / 2) ∥ x_{k} ∥_{2}^{2}$ . The lower bound and the Lipschitz-gradient condition give $f (x_{k}) \geq f (0) - ∥ \nabla f (0) ∥_{2} ∥ x_{k} ∥_{2} - (3 L / 2) ∥ x_{k} ∥_{2}^{2}$ . Thus [F3] and $2 a b \leq a^{2} + b^{2}$ imply $∣ f (x_{k}) ∣ \leq ∣ f (0) ∣ + \frac{1}{2} ∥ \nabla f (0) ∥_{2}^{2} + (\frac{1}{2} + \frac{3 L}{2}) ∥ x_{k} ∥_{2}^{2}$ . The right side has finite expectation by step 2.1, so $E ∣ f (x_{k}) ∣ < \infty$ for every $k \leq N$ .

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

An independent finite random index has the weighted expectation formula

Statement

Let $(Ω, F, P)$ be a probability space, let $N \geq 1$ , and let $p_{1}, \dots, p_{N} \geq 0$ satisfy $\sum_{k = 1}^{N} p_{k} = 1$ . There is a probability-space extension carrying an independent random index $R \in {1, \dots, N}$ with $P (R = k) = p_{k}$ . For any integrable real random variables $H_{1}, \dots, H_{N}$ on the original space, the lifted random variable $H_{R} (ω, k) = H_{k} (ω)$ is integrable on the extension and satisfies $E [H_{R}] = \sum_{k = 1}^{N} p_{k} E [H_{k}]$ .

Facts & Assumptions

Given: A probability space, a positive integer $N$ , nonnegative weights of total mass one, and integrable real random variables $H_{1}, \dots, H_{N}$ .

[F1]

Probability measures and probability spaces: a probability measure has total mass one.

[F2]

Measures on sigma-algebras: a measure is countably additive on pairwise disjoint measurable sequences.

[F3]

Random elements and real random variables: a random element is a measurable map into its stated measurable space.

[F4]

Expectation of a nonnegative or integrable random variable: the expectation is the Lebesgue integral, extended for nonnegative functions and finite for integrable real functions.

[F5]

The Lebesgue integral is linear on $L^{1} (μ)$ : the integral is linear on integrable functions.

[F6]

Every nonnegative measurable function is the increasing limit of simple measurable functions: each nonnegative measurable function is the increasing limit of nonnegative simple functions.

[F7]

Monotone convergence for the integral: the integrals of an increasing sequence of nonnegative measurable functions converge to the integral of its limit.

Proof

1.1F1givenconstruct

Define $\tilde{Ω} = Ω \times {1, \dots, N}$ and let $\tilde{F}$ consist of the sets $E = ⋃_{k = 1}^{N} A_{k} \times {k}$ with every $A_{k} \in F$ . Each such decomposition is unique, since $A_{k} = {ω : (ω, k) \in E}$ . The empty set and whole space have this form; complements replace each $A_{k}$ by $Ω ∖ A_{k}$ ; and countable unions replace each $A_{k}$ by the corresponding countable union in $F$ . Thus $\tilde{F}$ is a sigma-algebra.

2.1F1F2step 1.1givenalgebra

For $E = ⋃_{k} A_{k} \times {k}$ define $\tilde{P} (E) = \sum_{k} p_{k} P (A_{k})$ . This is nonnegative and $\tilde{P} (\tilde{Ω}) = \sum_{k} p_{k} = 1$ . If $E_{j} = ⋃_{k} A_{j, k} \times {k}$ are pairwise disjoint, then for each fixed $k$ the sets $A_{j, k}$ are pairwise disjoint. Countable additivity of $P$ from [F2] gives $\tilde{P} (⋃_{j} E_{j}) = \sum_{k} p_{k} \lim_{m \to \infty} \sum_{j = 1}^{m} P (A_{j, k})$ . Because the sum over $k$ is finite, its limit commutes with this finite sum; rearranging each finite double sum gives $\tilde{P} (⋃_{j} E_{j}) = \lim_{m \to \infty} \sum_{j = 1}^{m} \tilde{P} (E_{j}) = \sum_{j} \tilde{P} (E_{j})$ . Hence $\tilde{P}$ is a probability measure.

3.1F1F3step 2.1givenalgebra

Let $R (ω, k) = k$ . It is measurable because each inverse image is $Ω \times {k}$ , and $\tilde{P} (R = k) = p_{k}$ . For every $A \in F$ , its lift $\tilde{A} = A \times {1, \dots, N}$ satisfies $\tilde{P} (\tilde{A} \cap {R = k}) = p_{k} P (A) = \tilde{P} (\tilde{A}) \tilde{P} (R = k)$ , so $R$ is independent of all lifted original events.

3.2F4F5step 2.1givenalgebra

First suppose each $H_{k}$ is a nonnegative simple function. Write it as a finite sum of nonnegative constants times indicators of measurable sets. On the $k$ th slice, the lifted indicator of $A \in F$ is $1_{A \times {k}}$ , whose integral is its probability $p_{k} P (A)$ by [F4] and step 2.1. Finite linearity [F5], followed by summing the finitely many slices, gives $\tilde{E} [H_{R}] = \sum_{k} p_{k} E [H_{k}]$ .

4.1F6F7step 3.2algebra

For arbitrary nonnegative measurable $H_{k}$ , choose increasing simple approximations $H_{k, m} ↑ H_{k}$ by [F6]. Since there are finitely many $k$ , the lifted simple functions $H_{m} (ω, k) = H_{k, m} (ω)$ increase pointwise to $H_{R}$ . Apply [F7] on the extension and on the original space to the simple-function identity of step 3.2; the finite sum over $k$ commutes with the increasing limit. Therefore $\tilde{E} [H_{R}] = \sum_{k} p_{k} E [H_{k}]$ for all nonnegative measurable $H_{k}$ .

5.1F4F5step 4.1givenalgebra∎

For integrable real $H_{k}$ , apply step 4.1 separately to $H_{k}^{+}$ and $H_{k}^{-}$ . Their weighted expectations are finite because $\sum_{k} p_{k} E ∣ H_{k} ∣ < \infty$ . Subtracting the two nonnegative identities using [F5] proves both integrability of $H_{R}$ and the stated expectation formula. The extension and selector are explicitly finite-slice constructions, so this proof uses no choice axiom.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Stochastic gradient descent

Definition

Given $d \geq 1$ , a continuously differentiable objective $f : R^{d} \to R$ , a discrete filtered probability space $(Ω, F, (F_{t})_{t \geq 0}, P)$ , an initial iterate $x_{1}$ measurable with respect to $F_{1}$ , an integer horizon $N \geq 1$ , deterministic finite stepsizes $α_{1}, \dots, α_{N} > 0$ , and a stochastic-gradient oracle whose output at $x_{t}$ is a random vector $G_{t} : Ω \to R^{d}$ measurable with respect to $F_{t + 1}$ , the procedure returns the trajectory $(x_{t})_{t = 1}^{N + 1}$ . For each iteration $t = 1, \dots, N$ , query the oracle at $x_{t}$ and set $x_{t + 1} = x_{t} - α_{t} G_{t} .$ No conditional mean, variance, or independence-across-iterations property is part of this procedure's definition.

Definition references

Stochastic-gradient oracle and unconstrained-update definition: fixes the coordinatewise oracle, conditional-moment, and update conventions.

Filtered probability-space definition: fixes the increasing sigma-algebra sequence used to describe information at each iteration.

Adapted-process definition: fixes time-indexed measurability and integrability conventions.

Random-element definition: a vector-valued oracle output is a measurable map into its stated measurable space.

Population and empirical-risk definition: distinguishes the fixed finite-sample objective from population risk.

Supervised prediction-problem definition: fixes the sample, predictor, and loss context for the learning interpretation.

Remarks

The oracle interface does not specify which risk is being optimized. For empirical risk, the objective is the fixed sample average and sampling is over its finite terms. For population risk, sampling is from the population law; identifying the expected sampled gradient with the population-risk gradient requires a separately justified differentiation-under-expectation step. This algorithm asserts neither mean identity.

Remarks references

Population and empirical-risk definition: gives the distinct finite-sample and population objectives.

Supervised prediction-problem definition: specifies the joint law and loss whose population risk is integrated.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Minibatch stochastic gradient descent

Definition

Given $d \geq 1$ , a continuously differentiable objective $f : R^{d} \to R$ , a discrete filtered probability space $(Ω, F, (F_{t})_{t \geq 0}, P)$ , an initial iterate $x_{1}$ measurable with respect to $F_{1}$ , an integer horizon $N \geq 1$ , deterministic finite stepsizes $α_{1}, \dots, α_{N} > 0$ , an integer batch size $b \geq 1$ , and a batched oracle whose outputs at $x_{t}$ are random vectors $G_{t, 1}, \dots, G_{t, b} : Ω \to R^{d}$ , each measurable with respect to $F_{t + 1}$ . For each iteration $t = 1, \dots, N$ , query the batched oracle at the current iterate $x_{t}$ , receive the $b$ vectors, and form ${\overline{G}}_{t} = \frac{1}{b} \sum_{j = 1}^{b} G_{t, j}$ and set $x_{t + 1} = x_{t} - α_{t} {\overline{G}}_{t}$ . Return the trajectory $(x_{t})_{t = 1}^{N + 1}$ . The batch vectors are evaluated at the same current iterate; no independence, unbiasedness, or variance-reduction claim is part of this procedure's definition.

Definition references

Single-direction stochastic-gradient-descent procedure: the averaged direction is supplied to its unconstrained update.

Stochastic-gradient oracle and update definition: fixes the vector-update convention.

Filtered probability-space definition: fixes the information sequence for the batch outputs.

Adapted-process definition: fixes time-indexed measurability.

Random-element definition: each vector output is a measurable map into $R^{d}$ .

Euclidean inner-product and norm definition: fixes the finite-dimensional vector operations and norm convention.

Remarks

The procedure specifies how to average the returned vectors. The chosen batch law must separately justify any claim about the average's mean or variance; no such claim follows from the batch size alone.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Expected-average stationarity under aligned stochastic directions

Statement

Assume AC. Let $d \geq 1$ , $L > 0$ , and let $f : R^{d} \to R$ be continuously differentiable with $L$ -Lipschitz gradient. On a discrete filtered probability space $(Ω, F, (F_{t})_{t \geq 0}, P)$ , start at a deterministic $x_{1}$ and run stochastic gradient descent with square-integrable directions $G_{t}$ , adapted iterates $x_{t}$ , and updates $x_{t + 1} = x_{t} - α_{t} G_{t}$ . For each $t \geq 1$ , put $g_{t} = \nabla f (x_{t})$ and $m_{t} = E [G_{t} ∣ F_{t}]$ , with conditional expectations interpreted coordinatewise almost surely. Let the conditional variance of a vector be the sum of its coordinate conditional variances. Suppose there are constants $μ_{G} \geq μ > 0$ , $M \geq 0$ , $M_{V} \geq 0$ , and $F_{\inf} \in R$ such that, almost surely for every $t$ , $⟨ g_{t}, m_{t} ⟩ \geq μ ∥ g_{t} ∥_{2}^{2}, ∥ m_{t} ∥_{2} \leq μ_{G} ∥ g_{t} ∥_{2}, Var (G_{t} ∣ F_{t}) \leq M + M_{V} ∥ g_{t} ∥_{2}^{2}, f (x_{t}) \geq F_{\inf} .$ Set $M_{G} = M_{V} + μ_{G}^{2} > 0$ .

If the stepsize is constant, $α_{t} = α$ with $0 < α \leq μ / (L M_{G})$ , then for every integer $T \geq 1$ , $E [\frac{1}{T} \sum_{t = 1}^{T} ∥ \nabla f (x_{t}) ∥_{2}^{2}] \leq \frac{α L M}{μ} + \frac{2 (f (x_{1}) - F_{\inf})}{T μ α} .$

If instead the deterministic stepsizes satisfy $α_{t} > 0$ , $\sum_{t = 1}^{\infty} α_{t} = \infty$ , and $\sum_{t = 1}^{\infty} α_{t}^{2} < \infty$ , then, with $A_{T} = \sum_{t = 1}^{T} α_{t}$ , $E [\frac{1}{A_{T}} \sum_{t = 1}^{T} α_{t} ∥ \nabla f (x_{t}) ∥_{2}^{2}] ⟶ 0 (T \to \infty) .$ Conditional unbiasedness is the special case $μ = μ_{G} = 1$ ; a uniform conditional-variance bound $σ^{2}$ then gives $M = σ^{2}$ and $M_{V} = 0$ . No convexity or minimizer attainment is assumed.

Facts & Assumptions

Given: AC; the objective, filtered process, SGD updates, conditional direction moments, pathwise lower bound, and either stepsize regime in the Statement.

[A1]

The Axiom of Choice: AC supplies the conditional-expectation classes used in this theorem.

[A2]

The local alignment hypothesis is $⟨ g_{t}, m_{t} ⟩ \geq μ ∥ g_{t} ∥_{2}^{2}$ almost surely, with $μ > 0$ .

[A3]

The local conditional-mean norm hypothesis is $∥ m_{t} ∥_{2} \leq μ_{G} ∥ g_{t} ∥_{2}$ almost surely, with $μ_{G} \geq μ$ .

[A4]

The local conditional-variance hypothesis is $Var (G_{t} ∣ F_{t}) \leq M + M_{V} ∥ g_{t} ∥_{2}^{2}$ almost surely, with $M, M_{V} \geq 0$ .

[A5]

The objective lower bound is $f (x_{t}) \geq F_{\inf}$ almost surely at each iterate.

[F1]

Stochastic gradient descent: the algorithm uses $x_{t + 1} = x_{t} - α_{t} G_{t}$ and imposes no moment or unbiasedness conclusion by itself.

[F2]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: oracle vectors are adapted; conditional means and vector conditional variances are coordinatewise; the second-moment identity is $E [∥ G_{t} ∥_{2}^{2} ∣ F_{t}] = ∥ m_{t} ∥_{2}^{2} + Var (G_{t} ∣ F_{t})$ .

[F3]

Filtration and filtered probability space: $F_{t} \subseteq F_{t + 1} \subseteq F$ .

[F4]

Adapted and integrable stochastic process: an adapted vector process is measurable at its stated time, and integrability is timewise.

[F5]

Random elements and real random variables: a vector-valued random element is a measurable map into $R^{d}$ .

[F6]

Conditional expectation as an ae class: under AC, conditional expectations are almost-sure classes and their equalities are almost-sure equalities.

[F7]

Conditional variance and Conditional variance is well-defined and has the second-moment formula: conditional variance is the sum of coordinate variances and yields the vector second-moment identity in [F2].

[F8]

Martingale difference sequence: an integrable adapted sequence with conditional mean zero at the preceding filtration time is a martingale-difference sequence.

[F9]

Descent inequality for a Lipschitz gradient: $f (y) \leq f (x) + ⟨ \nabla f (x), y - x ⟩ + (L / 2) ∥ y - x ∥_{2}^{2}$ .

[F10]

Taking out what is known: an integrable product with a finite measurable factor may be taken outside conditional expectation when both products are integrable.

[F11]

Basic algebra and order properties of conditional expectation: conditional expectation is linear, preserves order, and preserves ordinary expectation.

[F12]

Tower property of conditional expectation: nested conditional expectations satisfy the tower identity.

[F13]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the inner product and norm are the coordinatewise Euclidean ones.

[F14]

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

[F15]

Expectation of a nonnegative or integrable random variable: expectation is the Lebesgue integral, finite for integrable real random variables.

[F16]

Finite-horizon SGD trajectories have integrable objectives: finite-horizon SGD iterates, their gradients, and objective values have the integrability needed for conditional expectations and telescoping.

Proof

1.1A1A3A4F2F3F4F5F6F7F8F15F16givenalgebra

Fix $t \geq 1$ and write $g_{t} = \nabla f (x_{t})$ , $m_{t} = E [G_{t} ∣ F_{t}]$ , and $ε_{t} = G_{t} - m_{t}$ . The filtration and adapted-process conventions [F3, F4], together with the random-element convention [F5], make the time-indexed measurability explicit. By [F16], the objective values, gradients, and oracle vectors used below are integrable. The vector $ε_{t}$ is $F_{t + 1}$ -measurable and has conditional mean zero given $F_{t}$ , so each coordinate, after shifting the filtration to $H_{n} = F_{n + 1}$ , is a martingale difference by [F8]. The conditional variance identity [F2, F7] and [A3]–[A4] give $E [∥ G_{t} ∥_{2}^{2} ∣ F_{t}] = ∥ m_{t} ∥_{2}^{2} + Var (G_{t} ∣ F_{t}) \leq M + (M_{V} + μ_{G}^{2}) ∥ g_{t} ∥_{2}^{2} = M + M_{G} ∥ g_{t} ∥_{2}^{2}$ .

2.1A1A2A3A4F1F9F10F11F13F14F15F16step 1.1algebra

Apply [F9] with $x = x_{t}$ and $y = x_{t + 1} = x_{t} - α_{t} G_{t}$ , condition on $F_{t}$ , and use [F10] to take the $F_{t}$ -measurable gradient factor outside. Each coordinate product is integrable because $2 ∣ g_{t, j} G_{t, j} ∣ \leq g_{t, j}^{2} + G_{t, j}^{2}$ , with finite expectations by [F16] and the stated oracle moments. Conditional linearity and order [F11] give $E [f (x_{t + 1}) ∣ F_{t}] \leq f (x_{t}) - α_{t} ⟨ g_{t}, m_{t} ⟩ + \frac{L α_{t}^{2}}{2} E [∥ G_{t} ∥_{2}^{2} ∣ F_{t}] \leq f (x_{t}) - (μ α_{t} - \frac{L M_{G} α_{t}^{2}}{2}) ∥ g_{t} ∥_{2}^{2} + \frac{L M α_{t}^{2}}{2}$ . All remaining terms are integrable by [F15]–[F16] and the second-moment bound in step 1.1.

3.1A5F11F12F15F16step 2.1givenalgebra

For constant $α \leq μ / (L M_{G})$ , $μ α - L M_{G} α^{2} / 2 \geq μ α / 2$ . Take ordinary expectations in step 2.1, using [F11]–[F12], and sum from $t = 1$ to $T$ . The objective terms telescope and [A5] gives $\frac{μ α}{2} \sum_{t = 1}^{T} E ∥ g_{t} ∥_{2}^{2} \leq f (x_{1}) - F_{\inf} + \frac{L α^{2} M T}{2}$ . Divide by $T μ α / 2$ to obtain the stated constant-step average bound.

4.1A1A2A3A4A5F11F12F15F16step 2.1choosealgebra∎

In the diminishing-step regime, $\sum_{t} α_{t}^{2} < \infty$ implies $α_{t} \to 0$ : otherwise some $ϵ > 0$ would satisfy $α_{t} \geq ϵ$ at infinitely many indices, forcing the square sum to diverge. Since $μ / (L M_{G}) > 0$ , choose $K$ so that $α_{t} \leq μ / (L M_{G})$ for every $t \geq K$ . Apply step 2.1 on this tail, take expectations, and telescope through $T \geq K$ ; then $\frac{μ}{2} \sum_{t = K}^{T} α_{t} E ∥ g_{t} ∥_{2}^{2} \leq E f (x_{K}) - F_{\inf} + \frac{L M}{2} \sum_{t = K}^{T} α_{t}^{2}$ . The right side is bounded independently of $T$ by [F15], [F16], and square summability. The omitted finite prefix has finite weighted sum by [F16]. Thus $\sum_{t = 1}^{T} α_{t} E ∥ g_{t} ∥_{2}^{2}$ stays bounded while $A_{T} = \sum_{t = 1}^{T} α_{t} \to \infty$ . Their ratio tends to zero, which is the claimed expectation of the weighted average because each $α_{t}$ is deterministic.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Nonconvex SGD weighted random-iterate stationarity

Statement

Assume AC. Let $d \geq 1$ , $L > 0$ , $σ \geq 0$ , and let $f : R^{d} \to R$ be continuously differentiable with $L$ -Lipschitz gradient and finite global infimum $f^{*} = \inf_{x \in R^{d}} f (x) \in R$ ; the infimum need not be attained. Start at a deterministic $x_{1}$ and, on a discrete filtered probability space $(Ω, F, (F_{k})_{k \geq 0}, P)$ , run stochastic gradient descent for an integer horizon $N \geq 1$ with square-integrable oracle vectors $G_{k}$ , adapted iterates $x_{k}$ , and updates $x_{k + 1} = x_{k} - γ_{k} G_{k}$ . Suppose, almost surely for $k = 1, \dots, N$ , $E [G_{k} ∣ F_{k}] = \nabla f (x_{k}), Var (G_{k} ∣ F_{k}) \leq σ^{2},$ where the conditional variance of a vector is the sum of the coordinate conditional variances, and let $0 < γ_{k} < 2 / L$ . Put $a_{k} = 2 γ_{k} - L γ_{k}^{2}$ , $S_{N} = \sum_{k = 1}^{N} a_{k}$ , and $D_{f} : = \sqrt{2 (f (x_{1}) - f^{*}) / L} \geq 0$ , so $D_{f}^{2} = 2 (f (x_{1}) - f^{*}) / L$ . On an independent finite probability-space extension, choose $R \in {1, \dots, N}$ with $P (R = k) = a_{k} / S_{N}$ and output $x_{R}$ . Then $S_{N} > 0$ and $\frac{1}{L} E ∥ \nabla f (x_{R}) ∥_{2}^{2} \leq \frac{D_{f}^{2} + σ^{2} \sum_{k = 1}^{N} γ_{k}^{2}}{\sum_{k = 1}^{N} (2 γ_{k} - L γ_{k}^{2})} .$

If $D_{f} > 0$ and $σ > 0$ , the constant choice $γ_{k} = \min {1 / L, D_{f} / (σ \sqrt{N})}$ gives $\frac{1}{L} E ∥ \nabla f (x_{R}) ∥_{2}^{2} \leq \frac{2 L D_{f}^{2}}{N} + \frac{2 D_{f} σ}{\sqrt{N}} .$ If $σ = 0$ , the choice $γ_{k} = 1 / L$ gives the bound $L D_{f}^{2} / N$ . If $D_{f} = 0 < σ$ , the choice $γ_{k} = 1 / (L \sqrt{N})$ gives $σ^{2} / [L (2 \sqrt{N} - 1)]$ . Thus the constant-step guarantee is $O (N^{- 1} + N^{- 1 / 2})$ for fixed $L, D_{f}, σ$ , with the zero cases covered separately. No global-minimum or iterate-convergence conclusion is asserted.

Facts & Assumptions

Given: AC; the smooth objective, deterministic initial point, filtered SGD trajectory, square-integrable oracle, conditional unbiasedness and variance assumptions, and the stepsize range in the Statement.

[A1]

The Axiom of Choice: AC supplies the conditional-expectation classes used in the oracle assumptions and proof.

[A2]

The local conditional-unbiasedness hypothesis is $E [G_{k} ∣ F_{k}] = \nabla f (x_{k})$ almost surely.

[A3]

The local conditional-variance hypothesis is $Var (G_{k} ∣ F_{k}) \leq σ^{2}$ almost surely.

[A4]

The global lower-bound hypothesis is $f (x) \geq f^{*}$ for every $x \in R^{d}$ ; no minimizer is required.

[F1]

Stochastic gradient descent: the update is $x_{k + 1} = x_{k} - γ_{k} G_{k}$ .

[F2]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: conditional oracle moments are coordinatewise, and the vector second moment is conditional squared mean plus conditional variance.

[F3]

Filtration and filtered probability space and Adapted and integrable stochastic process: $x_{k}$ is $F_{k}$ -measurable and $G_{k}$ is $F_{k + 1}$ -measurable.

[F4]

Random elements and real random variables: vector iterates and oracle outputs are measurable maps into $R^{d}$ .

[F5]

Conditional expectation as an ae class: conditional expectations are almost-sure classes under AC.

[F6]

Conditional variance and Conditional variance is well-defined and has the second-moment formula: the coordinate variance formula gives the vector conditional second-moment identity.

[F7]

Martingale difference sequence: each coordinate of $G_{k} - E [G_{k} ∣ F_{k}]$ , with the filtration shifted by one index, is a martingale difference.

[F8]

Finite-horizon SGD trajectories have integrable objectives: finite-horizon iterates, gradients, and objective values are integrable.

[F9]

Descent inequality for a Lipschitz gradient: $f (y) \leq f (x) + ⟨ \nabla f (x), y - x ⟩ + (L / 2) ∥ y - x ∥_{2}^{2}$ .

[F10]

Taking out what is known: an integrable measurable factor may be taken outside conditional expectation when the products are integrable.

[F11]

Basic algebra and order properties of conditional expectation: conditional expectation is linear and order preserving and preserves ordinary expectation.

[F12]

Tower property of conditional expectation: nested conditional expectations satisfy the tower identity.

[F13]

An independent finite random index has the weighted expectation formula: a finite index with weights summing to one can be added independently, and $E [H_{R}] = \sum_{k} P (R = k) E [H_{k}]$ for integrable $H_{k}$ .

[F14]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: norms and inner products use the Euclidean convention and satisfy Cauchy–Schwarz.

[F15]

Expectation of a nonnegative or integrable random variable: expectation is integration and is finite for integrable real random variables.

Proof

1.1A1A2A3F2F3F4F5F6F7F8givenalgebra

Fix $k$ and put $g_{k} = \nabla f (x_{k})$ and $ε_{k} = G_{k} - g_{k}$ . The filtration and adapted-process convention [F3] puts $x_{k}$ and $G_{k}$ at their stated time indices, and [F4] records their random-element measurability. Under AC [A1], the conditional-expectation classes used here are the almost-sure classes in [F5]. By [F8], the objective values, gradients, and directions used in the descent calculation are integrable. The residual $ε_{k}$ has conditional mean zero given $F_{k}$ ; after shifting the filtration by one index, its coordinates form martingale differences by [F3, F7]. The conditional variance identity [F2, F6] and [A3] yield $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] = ∥ g_{k} ∥_{2}^{2} + Var (G_{k} ∣ F_{k}) \leq ∥ g_{k} ∥_{2}^{2} + σ^{2}$ .

2.1A1A2A3F1F8F9F10F11F14F15step 1.1algebra

Apply the smoothness inequality [F9] to $x_{k + 1} = x_{k} - γ_{k} G_{k}$ and condition on $F_{k}$ . The products are integrable because $2 ∣ g_{k, j} G_{k, j} ∣ \leq g_{k, j}^{2} + G_{k, j}^{2}$ coordinatewise, with finite expectations by [F8]. Take the $F_{k}$ -measurable gradient factor outside conditional expectation by [F10], then use [A2], [F11], and step 1.1 to obtain $E [f (x_{k + 1}) ∣ F_{k}] \leq f (x_{k}) - (γ_{k} - \frac{L}{2} γ_{k}^{2}) ∥ g_{k} ∥_{2}^{2} + \frac{L γ_{k}^{2} σ^{2}}{2}$ .

3.1A4F11F12F15step 2.1givenalgebra

Take ordinary expectations in step 2.1 using the tower property [F11, F12], and sum from $k = 1$ to $N$ . The objective terms telescope; by [A4], $E f (x_{N + 1}) \geq f^{*}$ . Therefore $\sum_{k = 1}^{N} (γ_{k} - \frac{L}{2} γ_{k}^{2}) E ∥ g_{k} ∥_{2}^{2} \leq f (x_{1}) - f^{*} + \frac{L σ^{2}}{2} \sum_{k = 1}^{N} γ_{k}^{2}$ . Multiplying by $2$ gives $\sum_{k = 1}^{N} a_{k} E ∥ g_{k} ∥_{2}^{2} \leq 2 (f (x_{1}) - f^{*}) + L σ^{2} \sum_{k = 1}^{N} γ_{k}^{2}$ .

4.1F8F13step 3.1givenalgebra

Since $a_{k} = γ_{k} (2 - L γ_{k}) > 0$ , $S_{N} > 0$ and $(a_{k} / S_{N})_{k = 1}^{N}$ is a probability vector. Apply [F13] to the integrable random variables $H_{k} = ∥ g_{k} ∥_{2}^{2}$ ; it gives $E ∥ \nabla f (x_{R}) ∥_{2}^{2} = S_{N}^{- 1} \sum_{k} a_{k} E ∥ g_{k} ∥_{2}^{2}$ . Dividing step 3.1's bound by $L S_{N}$ yields the claimed weighted estimate.

5.1step 3.1givenalgebra∎

Suppose $D_{f}, σ > 0$ and set $γ = \min {1 / L, D_{f} / (σ \sqrt{N})}$ . If $γ = D_{f} / (σ \sqrt{N}) \leq 1 / L$ , then $2 γ - L γ^{2} \geq γ$ and $D_{f}^{2} + N σ^{2} γ^{2} = 2 D_{f}^{2}$ , so the weighted bound is at most $2 D_{f} σ / \sqrt{N}$ . If $γ = 1 / L$ , the bound equals $L D_{f}^{2} / N + σ^{2} / L$ , and the clipping condition implies $σ^{2} / L \leq L D_{f}^{2} / N$ , giving at most $2 L D_{f}^{2} / N$ . Thus it is bounded by the stated sum of the two terms. If $σ = 0$ , use $γ = 1 / L$ in the formula to obtain $L D_{f}^{2} / N$ . If $D_{f} = 0 < σ$ , use $γ = 1 / (L \sqrt{N})$ ; then $S_{N} = (2 \sqrt{N} - 1) / L$ and the right side is $σ^{2} / [L (2 \sqrt{N} - 1)]$ . These cases prove the asserted constant-step rate and handle the zero boundaries.

Remarks

With constant $γ_{k} = α \leq 1 / L$ , all weights $a_{k}$ are equal, so $R$ is uniform. The published uniform-index theorem covers this exact regime under its global lower-bound and square-integrable conditional-oracle hypotheses and gives $E ∥ \nabla f (x_{R}) ∥_{2}^{2} \leq 2 (f (x_{1}) - f^{*}) / (α N) + L α σ^{2}$ . The weighted statement above retains the nonuniform stepsizes and the full interval $0 < γ_{k} < 2 / L$ .

Remarks references

Published constant-step uniform-random-iterate theorem: its exact oracle hypotheses and bound are the comparison interface stated above.

4 · Examples, counterexamples and false statements

None yet.

Stochastic gradient descent and random-iterate guarantees

2 · Logical flowchart

3 · Definitions, theorems and proofs

Finite-horizon SGD trajectories have integrable objectives

Statement

Facts & Assumptions

Proof

An independent finite random index has the weighted expectation formula

Statement

Facts & Assumptions

Proof

Stochastic gradient descent

Definition

Definition references

Remarks

Remarks references

Minibatch stochastic gradient descent

Definition

Definition references

Remarks

Expected-average stationarity under aligned stochastic directions

Statement

Facts & Assumptions

Proof

Nonconvex SGD weighted random-iterate stationarity

Statement

Facts & Assumptions

Proof

Remarks

Remarks references

4 · Examples, counterexamples and false statements

Sources