Theorem 5 — SGD with α-suffix averaging: E[F(w̄ᵅ_T) − F(w*)] ≤ (2 + 2.5 log(1/(1−α)))/α · G²/(λT)
ProvedOptimalSGD.Suffix.theorem_5Let be closed and convex with , and let be -strongly convex on for some . Let be a probability law on a sample space and a jointly measurable stochastic gradient oracle such that, for every , is integrable, its mean is a subgradient of at relative to , and
Let minimize over . Run projected SGD with step sizes on an i.i.d. sample , :
and let be such that is an integer. Return the α-suffix average
Then has a finite expectation and
For any fixed this is an rate for plain SGD on a non-smooth strongly convex objective, whereas averaging all iterates can lose a factor.
Formalization Note The paper's Hilbert space is specialized to (UnderstandingML.Vec d). The statement of Theorem 5 on p. 6 writes the hypothesis as ; the standing assumption of §2 (p. 3) and the proof use , which is what is stated here. "Regardless of how the iterates evolve" is rendered as the moment bound at every point of . is the natural logarithm. The iterate index in Lean is the paper's , and is passed as a natural number tied to by . Strong convexity is Mathlib's StrongConvexOn W lam F, equivalent to the paper's (1) for functions with subgradients relative to at every point of , which the oracle provides.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Definitions.Def_OptimalSGD_Suffix_Model open MeasureTheory UnderstandingML open scoped InnerProductSpace
namespace OptimalSGD.Suffix
/-- **Theorem 5** (Rakhlin, Shamir, Sridharan, arXiv:1109.5647v7, §5, p. 6; proof App. B.6,
p. 18). Consider projected SGD started at `w₁ = 0` with step sizes `η_t = 1/(λt)` on the closed
convex set `W ∋ 0`, an i.i.d. sample `S ∼ D^T`, and α-suffix averaging with `α ∈ (0, 1)` and
`k = (1 − α)T` an integer. Suppose `F` is `λ`-strongly convex on `W`, the oracle mean
`E_z g(w, z)` is a subgradient of `F` relative to `W` at every `w ∈ W`, `E‖g(w, z)‖² ≤ G²` at
every `w ∈ W`, and `w*` minimizes `F` over `W`. Then `F(w̄ᵅ_T)` has a finite expectation and
`E[F(w̄ᵅ_T) − F(w*)] ≤ (2 + 2.5 log(1/(1 − α)))/α · G²/(λT)`, `log` the natural logarithm. -/
theorem theorem_5
{d : ℕ} {Z : Type*} [MeasurableSpace Z]
(W : Set (Vec d)) (hWconv : Convex ℝ W) (hWclosed : IsClosed W) (hW0 : (0 : Vec d) ∈ W)
(F : Vec d → ℝ) {lam : ℝ} (hlam : 0 < lam) (hF : StrongConvexOn W lam F)
(D : Measure Z) [IsProbabilityMeasure D] (g : Vec d → Z → Vec d)
(hg : Measurable (Function.uncurry g)) (horacle : IsSubgradientOracleOn W F D g)
{G : ℝ} (hmoment : ∀ w ∈ W, ∫⁻ z, ENNReal.ofReal (‖g w z‖ ^ 2) ∂D ≤ ENNReal.ofReal (G ^ 2))
(wstar : Vec d) (hwstar : wstar ∈ W) (hmin : ∀ w ∈ W, F wstar ≤ F w)
{α : ℝ} (hα0 : 0 < α) (hα1 : α < 1) (T k : ℕ) (hT : 0 < T) (hk : (k : ℝ) = (1 - α) * T) :
Integrable (fun S => F (suffixAverage lam W g S k)) (iidLaw D T) ∧
∫ S, (F (suffixAverage lam W g S k) - F wstar) ∂(iidLaw D T) ≤
(2 + 2.5 * Real.log (1 / (1 - α))) / α * (G ^ 2 / (lam * T)) := by sorry
end OptimalSGD.Suffix
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.