LemmaStatement: 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.

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

Depends on

Used by

Dependency tree · two levels

32 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

Léon Bottou, Frank E. Curtis, and Jorge Nocedal, Optimization Methods for Large-Scale Machine Learning, §4.1 (standard reference, not scraped)
MIT 6.7220/15.084 Nonlinear Optimization, Lecture 15: Stochastic Gradient Descent (standard reference, not scraped)