TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

68 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

Saeed Ghadimi and Guanghui Lan, Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming, §2.1, Theorem 2.1(a) and proof (standard reference, not scraped)
Léon Bottou, Frank E. Curtis, and Jorge Nocedal, Optimization Methods for Large-Scale Machine Learning, §4.3 (standard reference, not scraped)
MIT 6.7220/15.084 Nonlinear Optimization, Lecture 15: Stochastic Gradient Descent (standard reference, not scraped)