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.

✓ 8 results · all verified · 6 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Stochastic approximation and stochastic gradient methods

1 · Prerequisites

2 · Summary

This page defines filtration-adapted Robbins–Monro, SGD, and projected SGD, with conditional unbiasedness, bias, variance, and moment hypotheses stated separately. It proves the almost-supermartingale lemma locally from the published Doob convergence interface, then applies it to strongly monotone root finding and projected strongly convex optimization. The finite-time results give an averaged convex $O (N^{- 1 / 2})$ bound, a last-iterate strongly convex $O (k^{- 1})$ bound, and a nonconvex randomized-iterate stationarity bound. Biased or constant-step noise leaves the explicit weighted terms shown in the corresponding theorem. Almost-sure claims assume AC for the conditional-expectation and Doob interfaces. These are optimization guarantees only; convergence supplies no central-limit or inferential guarantee.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates

Definition

Fix a finite dimension $d \geq 1$ and a discrete filtered probability space $(Ω, F, (F_{k})_{k \geq 0}, P)$ as in Filtration and filtered probability space. A sequence $x_{k} : Ω \to R^{d}$ is an iterate process when each coordinate is $F_{k}$ -measurable; a sequence $G_{k} : Ω \to R^{d}$ is an oracle process when each coordinate is $F_{k + 1}$ -measurable. These are coordinatewise instances of Random elements and real random variables and Adapted and integrable stochastic process. Assume the coordinates used in a conditional moment are square-integrable.

For deterministic stepsizes $α_{k} > 0$ , the unconstrained Robbins–Monro/SGD update is $x_{k + 1} = x_{k} - α_{k} G_{k} .$ For a differentiable objective $f : R^{d} \to R$ , the oracle is conditionally unbiased when $E [G_{k} ∣ F_{k}] = \nabla f (x_{k})$ coordinatewise almost surely; it has conditional bias $b_{k}$ when $E [G_{k} ∣ F_{k}] = \nabla f (x_{k}) + b_{k}$ . The conditional variance of a vector is the sum of the scalar conditional variances of its coordinates, using Conditional variance. By Conditional variance is well-defined and has the second-moment formula, it satisfies $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] = ∥ E [G_{k} ∣ F_{k}] ∥_{2}^{2} + Var (G_{k} ∣ F_{k})$ almost surely. All conditional expectations are coordinatewise instances of Conditional expectation as an ae class, whose existence assumes the The Axiom of Choice. No independence across iterations is part of this definition.

The conditional second-moment bound $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq M_{k}^{2}$ and the conditional variance bound $Var (G_{k} ∣ F_{k}) \leq σ_{k}^{2}$ are distinct hypotheses; the latter combines with conditional unbiasedness through the displayed identity.

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

Robbins–Siegmund almost-supermartingale convergence

Statement

Assume the Axiom of Choice. Let $(Ω, F, (F_{k})_{k \geq 0}, P)$ be a discrete filtered probability space. Let $X_{k}$ be nonnegative, adapted, and integrable for every $k$ . Let $a_{k}, c_{k}$ be deterministic nonnegative sequences with finite sums, and let $b_{k}$ be nonnegative, $F_{k}$ -measurable, and integrable. If $E [X_{k + 1} ∣ F_{k}] \leq (1 + a_{k}) X_{k} - b_{k} + c_{k} almost surely for every k,$ then $X_{k}$ converges almost surely to a finite nonnegative random variable and $\sum_{k \geq 0} b_{k} < \infty$ almost surely.

Facts & Assumptions

Given: The filtered probability space, processes, summable sequences, conditional inequality, and the Axiom of Choice in the Statement. A sequence of nonnegative reals is summable when its partial sums have a finite supremum.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function. It is assumed for the conditional-expectation and Doob interfaces used here.

[F1]

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

[F2]

Adapted and integrable stochastic process: adaptedness means $F_{k}$ -measurability at time $k$ , and integrability means finite expectation of the absolute value at every fixed time.

[F3]

Conditional expectation as an ae class: under AC, conditional expectations exist as almost-sure classes; inequalities and equalities between them are interpreted almost surely.

[F4]

Doob submartingale convergence theorem: under AC, a submartingale $Y_{k}$ with $\sup_{k} E [Y_{k}^{+}] < \infty$ has a finite integrable almost-sure limit.

[F5]

The real exponential function and the number $e$ by a power series: $\exp (t) = \sum_{n \geq 0} t^{n} / n!$ , so $\exp (0) = 1$ .

[F6]

The exponential function is smooth and $(\exp)^{'} = \exp$ : $\exp^{'} (t) = \exp (t)$ .

[F7]

The exponential function is strictly increasing: $\exp$ is increasing on $R$ .

[F8]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : for a function continuous on $[u, v]$ and differentiable on $(u, v)$ , some $w \in (u, v)$ satisfies $g (v) - g (u) = g^{'} (w) (v - u)$ .

[F9]

The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ : $\exp (s + t) = \exp (s) \exp (t)$ .

[F10]

Complete ordered field (least-upper-bound property): every nonempty set of reals bounded above has a least upper bound.

[F11]

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

[F12]

Basic algebra and order properties of conditional expectation: conditional expectation is linear and fixes constants; Taking out what is known: an integrable measurable factor can be taken outside when the products are integrable.

Proof

1.1A1F5F6F7F8F9F10F11givenchoosealgebrainduction

Define $A_{0} = 1$ , $A_{k + 1} = A_{k} (1 + a_{k})$ , and $T_{k} = \sum_{j \geq k} c_{j} / A_{j + 1}$ . Then $A_{k} \geq 1$ . For $t > 0$ , [F8] applied to $\exp$ on $[0, t]$ gives $\exp (t) - 1 = t \exp (w)$ for some $w \in (0, t)$ ; by [F5] and [F7], $\exp (w) \geq 1$ , so $1 + t \leq \exp (t)$ , with equality at $t = 0$ . Repeated use of [F9] now gives $A_{k} \leq \exp (\sum_{j < k} a_{j}) \leq \exp (\sum_{j \geq 0} a_{j})$ . Thus $A_{k}$ is nondecreasing and bounded. Let $A_{\infty} = \sup_{k} A_{k}$ , which exists by [F10]; for every $ε > 0$ , some $n$ has $A_{n} > A_{\infty} - ε$ , and then $A_{\infty} - ε < A_{n} \leq A_{k} \leq A_{\infty}$ for all $k \geq n$ , so $A_{k} \to A_{\infty} \geq 1$ . If $C_{m} = \sum_{j < m} c_{j}$ and $C_{\infty} = \sup_{m} C_{m}$ , then for every $ε > 0$ some $m$ has $C_{m} > C_{\infty} - ε$ ; for $k \geq m$ , $0 \leq T_{k} \leq C_{\infty} - C_{k} \leq C_{\infty} - C_{m} < ε$ . Thus $T_{k} \to 0$ .

2.1A1F1F2F3F4F12step 1.1givenalgebra

Put $Z_{k} = X_{k} / A_{k} + T_{k}$ . Each $Z_{k}$ is nonnegative, adapted, and integrable by [F1]–[F3]. By [F12], division by the positive deterministic $A_{k + 1}$ and addition of the deterministic $T_{k + 1}$ commute with conditional expectation. Since $A_{k + 1} = A_{k} (1 + a_{k})$ and $T_{k} = c_{k} / A_{k + 1} + T_{k + 1}$ , the given conditional inequality yields $E [Z_{k + 1} ∣ F_{k}] \leq \frac{(1 + a_{k}) X_{k} - b_{k} + c_{k}}{A_{k + 1}} + T_{k + 1} = Z_{k} - \frac{b_{k}}{A_{k + 1}} .$ Hence $- Z_{k}$ is an integrable adapted submartingale and $\sup_{k} E [(- Z_{k})^{+}] = 0$ . By [F4], $Z_{k}$ converges almost surely to a finite limit.

3.1A1F1F2F3F4F12step 2.1algebra

Define $S_{k} = \sum_{j < k} b_{j} / A_{j + 1}$ and $W_{k} = Z_{k} + S_{k}$ . For each $k$ , $S_{k + 1} = S_{k} + b_{k} / A_{k + 1}$ is $F_{k}$ -measurable: each earlier $b_{j}$ is $F_{j}$ -measurable with $F_{j} \subseteq F_{k}$ , the new term $b_{k}$ is $F_{k}$ -measurable by hypothesis, and the denominators are deterministic. The finite sums $S_{k}, S_{k + 1}$ are nonnegative and integrable by [F2]–[F3]. Hence [F12] gives $E [S_{k + 1} ∣ F_{k}] = S_{k + 1} = S_{k} + b_{k} / A_{k + 1}$ . Combining this with step 2.1 by linearity yields $E [W_{k + 1} ∣ F_{k}] \leq Z_{k} - b_{k} / A_{k + 1} + S_{k} + b_{k} / A_{k + 1} = W_{k}$ . Thus $- W_{k}$ is an integrable adapted submartingale with $\sup_{k} E [(- W_{k})^{+}] = 0$ ; [F4] gives a finite almost-sure limit for $W_{k}$ . Since the increasing partial sums $S_{k}$ are bounded above by $W_{k}$ , their limit is finite almost surely.

4.1step 1.1step 2.1step 3.1algebra∎

From $1 \leq A_{j + 1} \leq A_{\infty}$ , step 3.1 implies $\sum_{j} b_{j} \leq A_{\infty} \sum_{j} b_{j} / A_{j + 1} < \infty$ almost surely. By definition, $X_{k} = A_{k} (Z_{k} - T_{k})$ ; step 1.1 gives $A_{k} \to A_{\infty}$ and $T_{k} \to 0$ , and step 2.1 gives convergence of $Z_{k}$ . Therefore $X_{k}$ converges to a finite nonnegative limit and the asserted decrement sum is finite.

Source notes

The author-hosted Bertsekas appendix states a generalized Robbins–Siegmund theorem but provides no proof of it; the preceding note describes a proof route without giving its argument. It is recorded as statement-level comparison only; the proof above derives the required result from the complete current Doob submartingale supplier.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Robbins–Monro converges almost surely for a strongly monotone root

Statement

Assume the Axiom of Choice. Let $h : R^{d} \to R^{d}$ have a root $x^{*}$ , so $h (x^{*}) = 0$ , and suppose that for some $μ > 0$ , $⟨ h (x) - h (y), x - y ⟩ \geq μ ∥ x - y ∥_{2}^{2} (x, y \in R^{d}) .$ On a filtered probability space, let $x_{0}$ be square-integrable and let $x_{k}, G_{k}$ follow Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates. Assume each $h (x_{k})$ is $F_{k}$ -measurable, and suppose $E [G_{k} ∣ F_{k}] = h (x_{k}), E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq M^{2}$ almost surely for a finite constant $M$ . If the deterministic stepsizes satisfy $α_{k} > 0$ , $\sum_{k} α_{k} = \infty$ , and $\sum_{k} α_{k}^{2} < \infty$ , then $x_{k} \to x^{*}$ almost surely. Strong monotonicity also makes the root unique.

Facts & Assumptions

Given: AC, the update and filtration in the Statement, a root $x^{*}$ , the strong-monotonicity inequality, square-integrable $x_{0}$ , and the stated conditional oracle bounds.

[A1]

The Axiom of Choice: AC is assumed for the conditional-expectation and Doob interfaces.

[F1]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: $x_{k + 1} = x_{k} - α_{k} G_{k}$ , $x_{k}$ is $F_{k}$ -measurable, $G_{k}$ is $F_{k + 1}$ -measurable, vector conditional expectations are coordinatewise almost-sure classes, and $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] = ∥ E [G_{k} ∣ F_{k}] ∥_{2}^{2} + Var (G_{k} ∣ F_{k})$ with nonnegative conditional variance.

[F2]

Robbins–Siegmund almost-supermartingale convergence: if $V_{k}$ is nonnegative adapted integrable and $E [V_{k + 1} ∣ F_{k}] \leq V_{k} - b_{k} + c_{k}$ with $b_{k} \geq 0$ predictable and $\sum c_{k} < \infty$ , then $V_{k}$ converges almost surely and $\sum b_{k} < \infty$ almost surely.

[F3]

Taking out what is known: a finite $F_{k}$ -measurable factor may be taken outside conditional expectation when the input and products are integrable.

[F4]

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

[F5]

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

[F6]

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

[F7]

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

Proof

1.1F1F4F5F6F7givenalgebrainduction

Write $V_{k} = ∥ x_{k} - x^{*} ∥_{2}^{2}$ . By [F6] and $(\sqrt{μ} ∥ u ∥_{2} - ∥ v ∥_{2} / \sqrt{μ})^{2} \geq 0$ , $2 ∣ ⟨ u, v ⟩ ∣ \leq μ ∥ u ∥_{2}^{2} + μ^{- 1} ∥ v ∥_{2}^{2}$ . The update therefore gives $V_{k + 1} \leq (1 + μ α_{k}) V_{k} + (α_{k} / μ + α_{k}^{2}) ∥ G_{k} ∥_{2}^{2} .$ By [F4], the conditional moment bound implies $E ∥ G_{k} ∥_{2}^{2} \leq M^{2}$ . Using [F1] and nonnegativity of conditional variance gives $E [∥ h (x_{k}) ∥_{2}^{2}] \leq M^{2}$ . Thus [F7] and induction from square-integrable $x_{0}$ show every $V_{k}$ is integrable; Cauchy–Schwarz makes the products of $x_{k} - x^{*}$ with both $G_{k}$ and $h (x_{k})$ integrable.

2.1A1F1F3F4F5givenstep 1.1algebra

Strong monotonicity with $y = x^{*}$ gives $⟨ h (x_{k}), x_{k} - x^{*} ⟩ \geq μ V_{k}$ . Expanding the update and using [F3] to take out $x_{k} - x^{*}$ , then [F4] for the conditional mean and moment, yields $E [V_{k + 1} ∣ F_{k}] \leq V_{k} - 2 μ α_{k} V_{k} + M^{2} α_{k}^{2} .$ The products are integrable by step 1.1.

3.1A1F2step 1.1step 2.1given

Step 2.1 supplies the conditional inequality required by [F2]. Apply it with $a_{k} = 0$ , $b_{k} = 2 μ α_{k} V_{k}$ , and $c_{k} = M^{2} α_{k}^{2}$ . Step 1.1 gives the required integrability, and the stepsize hypotheses make $b_{k}$ predictable and $c_{k}$ summable. Hence $V_{k}$ converges almost surely and $\sum_{k} α_{k} V_{k} < \infty$ almost surely.

4.1F2step 3.1givenalgebra∎

If the almost-sure limit of $V_{k}$ were positive, then eventually $V_{k}$ would be bounded below by half that limit, contradicting $\sum_{k} α_{k} V_{k} < \infty$ and $\sum_{k} α_{k} = \infty$ . Thus $V_{k} \to 0$ and $x_{k} \to x^{*}$ almost surely. If $x^{'}$ were another root, the strong-monotonicity inequality at $(x^{*}, x^{'})$ would give $0 \geq μ ∥ x^{*} - x^{'} ∥_{2}^{2}$ , hence $x^{'} = x^{*}$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Nonconvex SGD stationarity bound for a uniform randomized iterate

Statement

Assume AC. Let $f : R^{d} \to R$ be continuously differentiable with $L$ -Lipschitz gradient for $L > 0$ , and suppose $f (x) \geq f_{\inf}$ for every $x$ , where $f_{\inf} \in R$ is a lower bound. Let $x_{0}$ be deterministic, $Δ = f (x_{0}) - f_{\inf}$ , and run the unconstrained update of Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates with constant $0 < α \leq 1 / L$ . Suppose $E [G_{k} ∣ F_{k}] = \nabla f (x_{k}), Var (G_{k} ∣ F_{k}) \leq σ^{2}$ almost surely for every $k$ . After generating $x_{0}, \dots, x_{N - 1}$ , independently choose $R$ uniformly from ${0, \dots, N - 1}$ on the finite product extension of the trajectory space; equivalently, $E ∥ \nabla f (x_{R}) ∥_{2}^{2} = N^{- 1} \sum_{k < N} E ∥ \nabla f (x_{k}) ∥_{2}^{2}$ . Then $E ∥ \nabla f (x_{R}) ∥_{2}^{2} \leq \frac{2 Δ}{α N} + L α σ^{2} .$ For fixed $Δ, σ$ , the stepsize $α = \min {1 / L, \sqrt{2 Δ / (L σ^{2} N)}}$ gives an $O (N^{- 1 / 2})$ bound when $Δ, σ > 0$ ; zero cases have the stronger bounds specified in the proof. This is an optimization guarantee, not an inferential or central-limit theorem.

Facts & Assumptions

Given: AC; $f, L, f_{\inf}, x_{0}, Δ, N$ and the stochastic update and conditional oracle assumptions in the Statement.

[A1]

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

[F1]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: the update is $x_{k + 1} = x_{k} - α G_{k}$ , and conditional unbiasedness is interpreted coordinatewise almost surely.

[F2]

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

[F3]

Conditional variance and Conditional variance is well-defined and has the second-moment formula: for a square-integrable scalar coordinate, $Var (X ∣ G) = E [X^{2} ∣ G] - (E [X ∣ G])^{2}$ ; summing this identity over the finitely many coordinates gives the vector second-moment identity.

[F4]

Taking out what is known: finite measurable factors may be taken outside conditional expectation once products are integrable.

[F5]

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

[F6]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the Euclidean norm square is the sum of squared coordinates.

[F7]

[F8]

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

Proof

1.1F1F2F7F8giveninductionalgebra

The oracle definition [F1] requires each $G_{k}$ used in a conditional variance to be square-integrable. Since $x_{0}$ is deterministic and $α$ is finite, the update and [F8] give square-integrable $x_{k}$ at every finite iteration by induction. The Lipschitz condition and triangle inequality in [F7] give $∥ g_{k} ∥_{2} \leq ∥ \nabla f (0) ∥_{2} + L ∥ x_{k} ∥_{2}$ . Applying [F2] at $0, x_{k}$ , then using [F7] and $2 a b \leq a^{2} + b^{2}$ , bounds $∣ f (x_{k}) ∣$ by $C (1 + ∥ x_{k} ∥_{2}^{2})$ for a finite constant $C$ ; thus $f (x_{k})$ is integrable.

2.1A1F1F2F3F4F5F6step 1.1givenalgebra

Put $g_{k} = \nabla f (x_{k})$ . Apply [F2] with $y = x_{k} - α G_{k}$ and condition on $F_{k}$ . By [F1], [F3], [F4], [F5], and [F6], $E [f (x_{k + 1}) ∣ F_{k}] \leq f (x_{k}) - α ∥ g_{k} ∥_{2}^{2} + \frac{L α^{2}}{2} E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq f (x_{k}) - α (1 - L α / 2) ∥ g_{k} ∥_{2}^{2} + \frac{L α^{2} σ^{2}}{2} .$ The last inequality uses $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] = ∥ g_{k} ∥_{2}^{2} + Var (G_{k} ∣ F_{k})$ ; all products are integrable by step 1.1.

3.1F5step 2.1givenalgebra

Since $α \leq 1 / L$ , $1 - L α / 2 \geq 1 / 2$ . Take ordinary expectations in step 2.1 and sum for $k = 0, \dots, N - 1$ . The terms $f (x_{k})$ telescope and $E f (x_{N}) \geq f_{\inf}$ , so $\frac{α}{2} \sum_{k = 0}^{N - 1} E ∥ g_{k} ∥_{2}^{2} \leq Δ + \frac{N L α^{2} σ^{2}}{2} .$ Dividing by $α N / 2$ gives $N^{- 1} \sum_{k < N} E ∥ g_{k} ∥_{2}^{2} \leq 2 Δ / (α N) + L α σ^{2}$ .

4.1step 3.1givenalgebra∎

The independent uniform index has $E ∥ \nabla f (x_{R}) ∥_{2}^{2} = N^{- 1} \sum_{k < N} E ∥ g_{k} ∥_{2}^{2}$ , so step 3.1 proves the stated finite- $N$ estimate. If $Δ, σ > 0$ and the square-root choice is at most $1 / L$ , the two terms in the bound are equal and their sum is $2 \sqrt{2 L Δ σ^{2} / N}$ . If the choice is clipped at $1 / L$ , then $σ^{2} N \leq 2 L Δ$ , and the bound is $2 L Δ / N + σ^{2} \leq 4 L Δ / N$ . If $σ = 0 < Δ$ , choose $α = 1 / L$ to get $2 L Δ / N$ ; if $Δ = 0$ , choose $α = 1 / (L (N + 1))$ to get $σ^{2} / (N + 1)$ . Thus every zero case is covered and the asserted asymptotic order follows.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Biased SGD has an explicit weighted stationarity floor

Statement

Assume AC. Let $f : R^{d} \to R$ have $L$ -Lipschitz gradient for $L > 0$ and satisfy $f (x) \geq f_{\inf}$ for a real lower bound $f_{\inf}$ . Run the unconstrained update of Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates from square-integrable $x_{0}$ with deterministic steps $0 < α_{k} \leq 1 / (4 L)$ . Suppose $E [G_{k} ∣ F_{k}] = \nabla f (x_{k}) + b_{k}, ∥ b_{k} ∥_{2} \leq β_{k}, Var (G_{k} ∣ F_{k}) \leq σ_{k}^{2}$ almost surely, where $b_{k}$ is $F_{k}$ -measurable and $β_{k}, σ_{k}$ are deterministic nonnegative bounds. For $N \geq 1$ and $Δ = E f (x_{0}) - f_{\inf} < \infty$ , $\frac{\sum_{k = 0}^{N - 1} α_{k} E ∥ \nabla f (x_{k}) ∥_{2}^{2}}{\sum_{k = 0}^{N - 1} α_{k}} \leq \frac{2 Δ + 2 \sum_{k < N} α_{k} β_{k}^{2} + 2 L \sum_{k < N} α_{k}^{2} β_{k}^{2} + L \sum_{k < N} α_{k}^{2} σ_{k}^{2}}{\sum_{k < N} α_{k}} .$ In particular, for constant $α, β, σ$ the uniform average is at most $\frac{2 Δ}{α N} + \frac{5}{2} β^{2} + L α σ^{2},$ and therefore ${lim sup}_{N \to \infty} \frac{1}{N} \sum_{k = 0}^{N - 1} E ∥ \nabla f (x_{k}) ∥_{2}^{2} \leq \frac{5}{2} β^{2} + L α σ^{2} .$ Decreasing steps retain the displayed weighted bias and noise sums.

Facts & Assumptions

Given: AC; the smooth objective, lower bound, update, conditional mean and variance conditions in the Statement.

[A1]

The Axiom of Choice: AC supplies the conditional-expectation classes.

[F1]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: the update is $x_{k + 1} = x_{k} - α_{k} G_{k}$ , with conditional mean and vector variance defined coordinatewise.

[F2]

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

[F3]

Conditional variance and Conditional variance is well-defined and has the second-moment formula: vector second moment equals squared conditional mean plus the sum of coordinate conditional variances.

[F4]

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

[F5]

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

[F6]

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

[F7]

[F8]

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

Proof

1.1A1F1F2F3F4F5F6F7F8givenalgebrainduction

By the oracle definition [F1], each $G_{k}$ used in the conditional variance is square-integrable. Since $x_{0}$ is square-integrable and each deterministic step is finite, the update and [F8] give square-integrable $x_{k}$ for every finite $k$ by induction. The Lipschitz gradient and the triangle inequality in [F7] make $g_{k} = \nabla f (x_{k})$ square-integrable. Applying [F2] at $0, x_{k}$ , and using [F7] and $2 a b \leq a^{2} + b^{2}$ , gives $∣ f (x_{k}) ∣ \leq C (1 + ∥ x_{k} ∥_{2}^{2})$ for a finite constant $C$ depending on $f (0), \nabla f (0), L, f_{\inf}$ ; thus the objective values are integrable. Write ${\overset{ˉ}{G}}_{k} = E [G_{k} ∣ F_{k}] = g_{k} + b_{k}$ . By [F3] and the bias bound, $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] = ∥ {\overset{ˉ}{G}}_{k} ∥_{2}^{2} + Var (G_{k} ∣ F_{k}) \leq ∥ g_{k} + b_{k} ∥_{2}^{2} + σ_{k}^{2} .$ The conditional products are integrable by the square-integrable oracle and the stated moment hypotheses.

2.1A1F1F2F3F4F5F6step 1.1algebra

Apply [F2] to $x_{k + 1} = x_{k} - α_{k} G_{k}$ , condition on $F_{k}$ , and use step 1.1. Expanding $∥ g_{k} + b_{k} ∥_{2}^{2}$ gives $E [f (x_{k + 1}) ∣ F_{k}] \leq f (x_{k}) - α_{k} (1 - L α_{k} / 2) ∥ g_{k} ∥_{2}^{2} - α_{k} (1 - L α_{k}) ⟨ g_{k}, b_{k} ⟩ + \frac{L α_{k}^{2}}{2} (β_{k}^{2} + σ_{k}^{2}) .$

3.1F7step 2.1givenalgebra

Put $q = L α_{k} \leq 1 / 4$ . By [F7] and $(∥ g_{k} ∥_{2} / 2 - (1 - q) β_{k})^{2} \geq 0$ , $(1 - q) ∥ g_{k} ∥_{2} β_{k} \leq \frac{1}{4} ∥ g_{k} ∥_{2}^{2} + (1 - q)^{2} β_{k}^{2} .$ Use this to bound the possibly positive cross term in step 2.1. Its gradient coefficient is at most $- α_{k} (3 / 4 - q / 2) \leq - α_{k} / 2$ , and the bias terms are at most $α_{k} β_{k}^{2} + L α_{k}^{2} β_{k}^{2}$ . Hence $E [f (x_{k + 1}) ∣ F_{k}] \leq f (x_{k}) - \frac{α_{k}}{2} ∥ g_{k} ∥_{2}^{2} + α_{k} β_{k}^{2} + L α_{k}^{2} β_{k}^{2} + \frac{L α_{k}^{2}}{2} σ_{k}^{2} .$

4.1F5step 3.1givenalgebra

Take ordinary expectations and sum step 3.1 from $k = 0$ to $N - 1$ . The objective terms telescope and $E f (x_{N}) \geq f_{\inf}$ , giving $\frac{1}{2} \sum_{k < N} α_{k} E ∥ g_{k} ∥_{2}^{2} \leq Δ + \sum_{k < N} α_{k} β_{k}^{2} + L \sum_{k < N} α_{k}^{2} β_{k}^{2} + \frac{L}{2} \sum_{k < N} α_{k}^{2} σ_{k}^{2} .$ Multiply by $2$ and divide by $\sum_{k < N} α_{k} > 0$ to obtain the weighted bound.

5.1step 4.1givenalgebra∎

For constant $α, β, σ$ , divide the numerator in step 4.1 by $N α$ ; the result is $2 Δ / (α N) + 2 β^{2} + 2 L α β^{2} + L α σ^{2}$ . Since $L α \leq 1 / 4$ , this is at most $2 Δ / (α N) + (5 / 2) β^{2} + L α σ^{2}$ . Taking the upper limit as $N \to \infty$ proves the displayed limit-superior bound.

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

Strong convexity makes a differentiable gradient strongly monotone

Statement

Let $U \subseteq R^{d}$ be open and convex, let $C \subseteq U$ be convex, and let $f : U \to R$ be differentiable. Suppose $f ∣_{C}$ is $μ$ -strongly convex in the strong-Jensen sense of Strong convexity for an extended-real objective, for $μ > 0$ ; explicitly, for $x, y \in C$ and $0 < t < 1$ , $f ((1 - t) x + t y) \leq (1 - t) f (x) + t f (y) - \frac{μ}{2} t (1 - t) ∥ x - y ∥_{2}^{2} .$ Then for all $x, y \in C$ , $f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩ + \frac{μ}{2} ∥ y - x ∥_{2}^{2},$ and consequently $⟨ \nabla f (x) - \nabla f (y), x - y ⟩ \geq μ ∥ x - y ∥_{2}^{2} .$

Facts & Assumptions

Given: $U, C, f, μ$ and the strong-convexity hypothesis in the Statement.

[F1]

Strong convexity for an extended-real objective: for $x, y \in dom F$ and $0 < t < 1$ , $F ((1 - t) x + t y) \leq (1 - t) F (x) + t F (y) - (μ / 2) t (1 - t) ∥ x - y ∥_{2}^{2}$ .

[F2]

The chain rule for total derivatives: $D (g \circ f) (a) = D g (f (a)) \circ D f (a)$ : along the segment $s \mapsto x + s (y - x)$ , the derivative of $f$ is $⟨ \nabla f (x + s (y - x)), y - x ⟩$ .

[F3]

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

Proof

1.1F1givenalgebra

Fix $x, y \in C$ , put $d = y - x$ , and take $0 < t < 1$ . Since $F = f$ on $C$ , [F1] gives $\frac{f (x + t d) - f (x)}{t} \leq f (y) - f (x) - \frac{μ}{2} (1 - t) ∥ d ∥_{2}^{2} .$

2.1F2step 1.1algebra

As $t ↓ 0$ , [F2] makes the left side tend to $⟨ \nabla f (x), d ⟩$ ; the right side tends to $f (y) - f (x) - (μ / 2) ∥ d ∥_{2}^{2}$ . The inequality persists in the limit: if the left limit exceeded the right limit, their difference would stay positive for sufficiently small $t$ , contradicting step 1.1. Thus the first displayed conclusion follows.

3.1F3step 2.1algebra∎

Apply step 2.1 once to $(x, y)$ and once to $(y, x)$ , then add. The function-value terms cancel and symmetry in [F3] gives $⟨ \nabla f (x) - \nabla f (y), x - y ⟩ \geq μ ∥ x - y ∥_{2}^{2}$ , proving the second conclusion.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Last-iterate SGD rate for smooth strongly convex objectives

Statement

Assume AC. Let $f : R^{d} \to R$ have $L$ -Lipschitz gradient for $L > 0$ and be $μ$ -strongly convex in the strong-Jensen sense of Strong convexity for an extended-real objective for $μ > 0$ , with minimizer $x^{*}$ satisfying $\nabla f (x^{*}) = 0$ . Start the unconstrained update of Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates at deterministic $x_{0}$ , with $E [G_{k} ∣ F_{k}] = \nabla f (x_{k}), E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq M^{2}$ almost surely for every $k$ . Use $α_{0} = 1 / μ$ and $α_{k} = 1 / (μ (k + 1))$ for $k \geq 1$ . Then for every $k \geq 1$ , $E ∥ x_{k} - x^{*} ∥_{2}^{2} \leq \frac{M^{2}}{μ^{2} k}, E [f (x_{k}) - f (x^{*})] \leq \frac{L M^{2}}{2 μ^{2} k} .$

Facts & Assumptions

Given: AC, the hypotheses and update in the Statement.

[A1]

The Axiom of Choice: AC is assumed for the conditional-expectation classes.

[F1]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: the update is $x_{k + 1} = x_{k} - α_{k} G_{k}$ , conditional unbiasedness means $E [G_{k} ∣ F_{k}] = \nabla f (x_{k})$ coordinatewise almost surely, and the vector conditional second-moment identity implies $∥ \nabla f (x_{k}) ∥_{2}^{2} \leq E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}]$ .

[F2]

Strong convexity makes a differentiable gradient strongly monotone: $⟨ \nabla f (x) - \nabla f (y), x - y ⟩ \geq μ ∥ x - y ∥_{2}^{2}$ .

[F3]

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

[F4]

Taking out what is known and Basic algebra and order properties of conditional expectation: conditional expectation is linear and an integrable measurable factor may be taken outside when the products are integrable.

[F5]

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

[F6]

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

[F7]

[F8]

Strong convexity for an extended-real objective: strong convexity means $f ((1 - t) x + t y) \leq (1 - t) f (x) + t f (y) - (μ / 2) t (1 - t) ∥ x - y ∥_{2}^{2}$ for $0 < t < 1$ on the effective domain.

Proof

1.1A1F1F2F4F5F7F8givenalgebrainduction

Put $V_{k} = ∥ x_{k} - x^{*} ∥_{2}^{2}$ . First, the pointwise bound $V_{k + 1} \leq (1 + μ α_{k}) V_{k} + (α_{k} / μ + α_{k}^{2}) ∥ G_{k} ∥_{2}^{2}$ follows from [F5], [F7], and $2 u v \leq μ u^{2} + μ^{- 1} v^{2}$ , so induction from deterministic $x_{0}$ and the unconditional moment bound gives $V_{k} \in L^{1}$ for every $k$ . The conditional-moment identity in [F1] gives $E ∥ \nabla f (x_{k}) ∥_{2}^{2} \leq M^{2}$ ; hence Cauchy–Schwarz makes the inner-product products integrable. By [F8], the strong-Jensen hypothesis is the one used in [F2]; applying [F2] with $y = x^{*}$ gives $⟨ \nabla f (x_{k}), x_{k} - x^{*} ⟩ \geq μ V_{k}$ . Expanding the update and conditioning using [F1] and [F4] now gives $E [V_{k + 1} ∣ F_{k}] \leq (1 - 2 μ α_{k}) V_{k} + M^{2} α_{k}^{2}$ .

2.1F6step 1.1givenalgebrainduction

At $k = 0$ , the recurrence in step 1.1 and $α_{0} = 1 / μ$ give $E V_{1} \leq - E V_{0} + M^{2} / μ^{2} \leq M^{2} / μ^{2}$ . For $k \geq 1$ , if $E V_{k} \leq M^{2} / (μ^{2} k)$ , then $E V_{k + 1} \leq \frac{M^{2}}{μ^{2}} (\frac{k - 1}{k (k + 1)} + \frac{1}{(k + 1)^{2}}) = \frac{M^{2}}{μ^{2}} \frac{k^{2} + k - 1}{k (k + 1)^{2}} \leq \frac{M^{2}}{μ^{2} (k + 1)},$ because $k^{2} + k - 1 \leq k (k + 1)$ . This proves the induction step; [F6] then gives the distance bound for all $k \geq 1$ .

3.1F3step 2.1givenalgebra∎

Apply [F3] with $x = x^{*}$ and $y = x_{k}$ . Since $\nabla f (x^{*}) = 0$ , it gives $f (x_{k}) - f (x^{*}) \leq (L / 2) V_{k}$ . Taking expectations and using step 2.1 proves the objective-gap bound.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Projected stochastic-gradient update

Definition

Let $C \subseteq R^{d}$ be nonempty, closed, and convex, and let $x_{0} \in C$ . The Euclidean projection $P_{C} (y)$ is the unique nearest point to $y$ in $C$ ; its existence and equivalence with the proximal map of the indicator of $C$ are supplied by The proximal map of an indicator is Euclidean projection. The indicator is zero on $C$ and $+ \infty$ off $C$ , as defined in Extended-real indicator of a set. For the filtration-adapted oracle and deterministic stepsizes $α_{k} > 0$ of Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates, a sequence $(x_{k})_{k \geq 0}$ satisfies the projected stochastic-gradient update when, for every $k \geq 0$ , $x_{k + 1} = P_{C} (y_{k}), y_{k} = x_{k} - α_{k} G_{k} .$

This relation specifies a unique next point $x_{k + 1} \in C$ for each $x_{k}$ and $G_{k}$ , because the projection exists uniquely for every $y_{k} \in R^{d}$ under the stated conditions. Its nonexpansiveness is not part of this definition; it is supplied by the proximal-map theorem when used in proofs.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Projected SGD converges almost surely on a strongly convex objective

Statement

Assume AC. Let $C \subseteq R^{d}$ be nonempty, closed, and convex. Let $f : R^{d} \to R$ be differentiable, and suppose $F = f + ι_{C}$ is $μ$ -strongly convex for $μ > 0$ in the sense of Strong convexity for an extended-real objective, where $ι_{C}$ is zero on $C$ and $+ \infty$ off $C$ (Extended-real indicator of a set). Assume a minimizer $x^{*} \in C$ exists. Start projected SGD as in Projected stochastic-gradient update from square-integrable $x_{0} \in C$ , with $E [G_{k} ∣ F_{k}] = \nabla f (x_{k}), E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq M^{2}$ almost surely for every $k$ , where $M < \infty$ . For deterministic stepsizes satisfying $0 < α_{k} \leq 1 / (2 μ)$ , $\sum_{k} α_{k} = \infty$ , and $\sum_{k} α_{k}^{2} < \infty$ , the iterates converge almost surely to $x^{*}$ . The projection supplies stability, so no separate coercivity hypothesis is needed for this projected theorem.

Facts & Assumptions

Given: AC, $C, f, μ, x^{*}$ , the adapted projected update, the conditional oracle bounds, and the stepsize assumptions in the Statement.

[A1]

The Axiom of Choice: AC is assumed for conditional-expectation existence and the Doob convergence interface.

[F1]

Projected stochastic-gradient update: $x_{k + 1} = P_{C} (x_{k} - α_{k} G_{k})$ and $P_{C}$ is the unique nearest-point map.

[F2]

Existence, resolvent characterization, and firm nonexpansiveness of the proximal map: the proximal map is nonexpansive.

[F3]

The proximal map of an indicator is Euclidean projection: for nonempty closed convex $C$ , ${prox}_{t ι_{C}}$ is the singleton map $P_{C}$ for every $t > 0$ .

[F4]

Strong convexity makes a differentiable gradient strongly monotone: $⟨ \nabla f (x) - \nabla f (y), x - y ⟩ \geq μ ∥ x - y ∥_{2}^{2}$ for $x, y \in C$ .

[F5]

The chain rule for total derivatives: $D (g \circ f) (a) = D g (f (a)) \circ D f (a)$ : the derivative of $t \mapsto f (x + t d)$ is $⟨ \nabla f (x + t d), d ⟩$ .

[F6]

Taking out what is known and Basic algebra and order properties of conditional expectation: integrable $F_{k}$ -measurable factors may be taken outside conditional expectation, which is linear and expectation-preserving.

[F7]

Robbins–Siegmund almost-supermartingale convergence: a nonnegative adapted integrable process with summable deterministic errors and predictable decrement converges almost surely, with finite total decrement.

[F8]

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

[F9]

[F10]

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

[F11]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: vector conditional second moment equals the squared conditional mean plus nonnegative vector conditional variance.

[F12]

Strong convexity for an extended-real objective: strong convexity means $F ((1 - t) x + t y) \leq (1 - t) F (x) + t F (y) - (μ / 2) t (1 - t) ∥ x - y ∥_{2}^{2}$ for $0 < t < 1$ on $dom F = C$ .

[F13]

Extended-real indicator of a set: $ι_{C}$ is $0$ on $C$ and $+ \infty$ off $C$ , so $F = f + ι_{C}$ has effective domain $C$ and agrees with $f$ there.

Proof

1.1A1F1F2F3F6F8F9F10F11givenalgebrainduction

Since $P_{C}$ is the proximal map of $ι_{C}$ by [F3], [F2] makes it nonexpansive and therefore continuous; [F3] also gives $P_{C} (x^{*}) = x^{*}$ and $x_{k + 1} \in C$ . The point $x_{k} - α_{k} G_{k}$ is $F_{k + 1}$ -measurable, so continuity makes $x_{k + 1}$ $F_{k + 1}$ -measurable. Thus the distance process is adapted. Hence $V_{k + 1} = ∥ x_{k + 1} - x^{*} ∥_{2}^{2} \leq ∥ x_{k} - α_{k} G_{k} - x^{*} ∥_{2}^{2} \leq (1 + μ α_{k}) V_{k} + (α_{k} / μ + α_{k}^{2}) ∥ G_{k} ∥_{2}^{2},$ where the last inequality follows by expanding the square, applying [F8], [F9], and using $2 u v \leq μ u^{2} + μ^{- 1} v^{2}$ . By [F6], $E ∥ G_{k} ∥_{2}^{2} \leq M^{2}$ , so induction from square-integrable $x_{0}$ shows each $V_{k}$ is integrable. By [F11] and the conditional moment bound, $∥ \nabla f (x_{k}) ∥_{2}^{2} = ∥ E [G_{k} ∣ F_{k}] ∥_{2}^{2} \leq M^{2}$ almost surely. Cauchy–Schwarz therefore makes the cross products in the conditional expansion integrable.

1.2F5givenchoose

For any $y \in C$ and $0 < t \leq 1$ , convexity of $C$ gives $x^{*} + t (y - x^{*}) \in C$ . Minimality of $x^{*}$ implies $f (x^{*} + t (y - x^{*})) \geq f (x^{*})$ . Divide by $t$ and let $t ↓ 0$ ; [F5] makes the quotient tend to $⟨ \nabla f (x^{*}), y - x^{*} ⟩$ , which must be nonnegative because a limit of nonnegative reals is nonnegative.

2.1A1F4F6F8F12F13step 1.1step 1.2givenalgebra

By [F13], $dom F = C$ and $F = f$ on $C$ , so the strong-Jensen condition [F12] is exactly the hypothesis of [F4]. Apply [F4] to $x_{k}, x^{*}$ and use step 1.2 with $y = x_{k}$ to obtain $⟨ \nabla f (x_{k}), x_{k} - x^{*} ⟩ \geq μ V_{k}$ . Expanding the projection estimate in step 1.1 and conditioning with [F6] now gives $E [V_{k + 1} ∣ F_{k}] \leq V_{k} - 2 μ α_{k} V_{k} + M^{2} α_{k}^{2} .$

3.1A1F7step 1.1step 2.1givenalgebra∎

Apply [F7] with $a_{k} = 0$ , $b_{k} = 2 μ α_{k} V_{k}$ , and $c_{k} = M^{2} α_{k}^{2}$ . Step 1.1 gives integrability, and the stepsize conditions give $\sum c_{k} < \infty$ . Thus $V_{k}$ converges almost surely and $\sum_{k} α_{k} V_{k} < \infty$ almost surely. If its limit were positive, the divergent sum $\sum_{k} α_{k}$ would force $\sum_{k} α_{k} V_{k} = \infty$ , a contradiction. Therefore $V_{k} \to 0$ and $x_{k} \to x^{*}$ almost surely.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Finite-time projected SGD bound for a convex objective

Statement

Assume AC. Let $C \subseteq R^{d}$ be nonempty, closed, and convex, with diameter $D = \sup_{x, y \in C} ∥ x - y ∥_{2} < \infty$ . Let $f : R^{d} \to R$ be differentiable and convex, and assume a minimizer $x^{*} \in C$ exists. Start projected SGD at deterministic $x_{0} \in C$ , with conditionally unbiased gradients, meaning $E [G_{k} ∣ F_{k}] = \nabla f (x_{k})$ as in Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates, and $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq G^{2}$ almost surely for every $k$ . For $N \geq 1$ , put ${\overset{ˉ}{x}}_{N} = N^{- 1} \sum_{k = 0}^{N - 1} x_{k}$ . If $D, G > 0$ and $α_{k} = α = D / (G \sqrt{N})$ for $0 \leq k < N$ , then $E [f ({\overset{ˉ}{x}}_{N}) - f (x^{*})] \leq \frac{D G}{\sqrt{N}} .$ If $D = 0$ or $G = 0$ , the initial point is already optimal and the displayed bound holds with right side zero.

Facts & Assumptions

Given: AC, $C, f, x^{*}, x_{0}, N$ , the projected update, conditional unbiasedness, and the moment bound in the Statement.

[A1]

The Axiom of Choice: AC supplies the conditional-expectation classes.

[F1]

Projected stochastic-gradient update: $x_{k + 1} = P_{C} (x_{k} - α G_{k})$ .

[F2]

Existence, resolvent characterization, and firm nonexpansiveness of the proximal map: the proximal map is nonexpansive.

[F3]

The proximal map of an indicator is Euclidean projection: the proximal map of $ι_{C}$ is $P_{C}$ , and it fixes every point of $C$ .

[F4]

Differentiable convex functions are characterized by the gradient inequality: for differentiable convex $f$ , $f (y) \geq f (x) + ⟨ \nabla f (x), y - x ⟩$ .

[F5]

Convex and strictly convex functions on Euclidean convex sets: convexity means $f ((1 - t) x + t y) \leq (1 - t) f (x) + t f (y)$ for $t \in [0, 1]$ .

[F6]

The principle of mathematical induction: a property true at the first natural and preserved by successors holds for every natural.

[F7]

Taking out what is known and Basic algebra and order properties of conditional expectation: integrable measurable factors may be taken outside conditional expectation, which is linear and expectation-preserving.

[F8]

A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere: a nonnegative integrable random variable with zero expectation vanishes almost surely.

[F9]

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

[F10]

Conditional variance and Conditional variance is well-defined and has the second-moment formula: vector conditional variance is nonnegative and conditional second moment equals squared conditional mean plus variance.

[F11]

[F12]

Dedekind completeness: the least-upper-bound property: every nonempty set of reals bounded above has a supremum.

[F13]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: conditional unbiasedness is the almost-sure identity $E [G_{k} ∣ F_{k}] = \nabla f (x_{k})$ .

Proof

1.1A1F2F3F4F6F10F11F12F13givenalgebrainduction

First establish adaptedness of the projected iterates. The deterministic $x_{0}$ is $F_{0}$ -measurable. If $x_{k}$ is $F_{k}$ -measurable, then $x_{k}$ and $G_{k}$ are $F_{k + 1}$ -measurable because $F_{k} \subseteq F_{k + 1}$ and [F13] makes $G_{k}$ $F_{k + 1}$ -measurable. Thus $x_{k} - α G_{k}$ is $F_{k + 1}$ -measurable. By [F2]–[F3], $P_{C}$ is nonexpansive and hence continuous, so $x_{k + 1} = P_{C} (x_{k} - α G_{k})$ is $F_{k + 1}$ -measurable and lies in $C$ . Induction [F6] proves this for every $k$ . The set of pairwise distances in the nonempty set $C$ is nonempty and bounded above by the finite $D$ , so [F12] supplies its supremum. By [F10] and [F13], $∥ \nabla f (x_{k}) ∥_{2}^{2} \leq E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] \leq G^{2}$ . Since $x_{k}, x^{*} \in C$ , their distance is at most $D$ . The convex gradient inequality [F4] and [F11] give $0 \leq f (x_{k}) - f (x^{*}) \leq ⟨ \nabla f (x_{k}), x_{k} - x^{*} ⟩ \leq D G$ , so each objective value in the telescope is integrable.

2.1A1F1F2F3F4F7F9F13step 1.1givenalgebra

By [F3], $P_{C} (x^{*}) = x^{*}$ , and [F2] makes $P_{C}$ nonexpansive. Therefore $∥ x_{k + 1} - x^{*} ∥_{2}^{2} \leq ∥ x_{k} - α G_{k} - x^{*} ∥_{2}^{2}$ . Expand the square, take conditional expectation, and use [F1], [F7], [F13], and the conditional moment bound. The gradient inequality in [F4] with $x = x_{k}$ , $y = x^{*}$ gives $E [∥ x_{k + 1} - x^{*} ∥_{2}^{2} ∣ F_{k}] \leq ∥ x_{k} - x^{*} ∥_{2}^{2} - 2 α (f (x_{k}) - f (x^{*})) + α^{2} G^{2}$ .

3.1F7step 2.1givenalgebra

Take ordinary expectations in step 2.1 and sum for $k = 0, \dots, N - 1$ . The distance terms telescope, $E ∥ x_{N} - x^{*} ∥_{2}^{2} \geq 0$ , and $∥ x_{0} - x^{*} ∥_{2} \leq D$ , so $2 α \sum_{k = 0}^{N - 1} E [f (x_{k}) - f (x^{*})] \leq D^{2} + N α^{2} G^{2}$ .

4.1F5F6step 3.1givenalgebrainduction

Convexity keeps ${\overset{ˉ}{x}}_{N}$ in $C$ and gives $f ({\overset{ˉ}{x}}_{N}) \leq N^{- 1} \sum_{k < N} f (x_{k})$ . To verify this finite Jensen inequality, induction starts with equality for one point; the step writes the $m$ -point mean as $\frac{m - 1}{m}$ times the $(m - 1)$ -point mean plus $\frac{1}{m} x_{m - 1}$ , then applies [F5]. Take expectations and use step 3.1 to get $E [f ({\overset{ˉ}{x}}_{N}) - f (x^{*})] \leq \frac{D^{2}}{2 α N} + \frac{α G^{2}}{2}$ .

5.1A1F3F4F6F7F8step 4.1givenalgebrainduction∎

With $α = D / (G \sqrt{N})$ , the two terms in step 4.1 are each $D G / (2 \sqrt{N})$ , proving the stated bound. If $D = 0$ , $C$ is a singleton and $x_{0} = x^{*}$ . If $G = 0$ , [F8] applied to each conditional moment and expectation-preservation in [F7] give $G_{k} = 0$ almost surely for every fixed $k$ . For each finite horizon, induction using [F6] shows all its iterates equal $x_{0}$ almost surely. Unbiasedness at $k = 0$ gives $\nabla f (x_{0}) = 0$ , and [F4] makes $x_{0}$ a global minimizer. Thus the zero-case bound holds for every $N$ .

5 · Examples, counterexamples and false statements

None yet.

Stochastic approximation and stochastic gradient methods

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates

Definition

Robbins–Siegmund almost-supermartingale convergence

Statement

Facts & Assumptions

Proof

Source notes

Robbins–Monro converges almost surely for a strongly monotone root

Statement

Facts & Assumptions

Proof

Nonconvex SGD stationarity bound for a uniform randomized iterate

Statement

Facts & Assumptions

Proof

Biased SGD has an explicit weighted stationarity floor

Statement

Facts & Assumptions

Proof

Strong convexity makes a differentiable gradient strongly monotone

Statement

Facts & Assumptions

Proof

Last-iterate SGD rate for smooth strongly convex objectives

Statement

Facts & Assumptions

Proof

Projected stochastic-gradient update

Definition

Projected SGD converges almost surely on a strongly convex objective

Statement

Facts & Assumptions

Proof

Finite-time projected SGD bound for a convex objective

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources