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

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]

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

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

53 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, SIAM Review 60(2) (2018), §4.2, Theorem 4.7 (standard reference, not scraped)
Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, §6.1, Theorem 6.2 (standard reference, not scraped)