§3.2, proof of Theorem 3.3, p. 268 — the gaps δ_s satisfy δ_{s+1} ≤ δ_s − δ_s²/(2β‖x₁ − x*‖²)
ProvedConvexOptAlg.SmoothGD.thm_3_3_recursionconvex-optimizationgradient-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be convex and -smooth with , let be a minimizer of , and let be gradient descent with . Write . Then for every ,
that is, when ,
This one-step recursion on the optimality gaps is what the proof of Theorem 3.3 turns into the rate.
Formalization Note The page writes the recursion with in a denominator; the Lean statement is multiplied through by , which is equivalent when and remains true (with both sides ) when . The minimizer's existence is the book's standing assumption; is implicit ().
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Proof of Theorem 3.3, last display on p. 268 (Bubeck, arXiv:1405.4980v2), multiplied out: for
gradient descent with `η = 1/β` on a convex β-smooth `f` (β > 0) with a minimizer `x*`, writing
`δ_s = f(x_s) − f(x*)`, for every `s ≥ 1`,
`δ_s² ≤ 2β‖x₁ − x*‖² (δ_s − δ_{s+1})`, i.e. `δ_{s+1} ≤ δ_s − δ_s²/(2β‖x₁ − x*‖²)` when `x₁ ≠ x*`;
the multiplied form also covers `x₁ = x*`. -/
theorem thm_3_3_recursion {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β)
(hconv : ConvexOn ℝ Set.univ f) (hf : IsBetaSmooth f g β)
(xstar : EuclideanSpace ℝ (Fin n)) (hmin : ∀ y, f xstar ≤ f y)
(x : ℕ → EuclideanSpace ℝ (Fin n)) (hrun : IsGDRun g (1 / β) x) (s : ℕ) (hs : 1 ≤ s) :
(f (x s) - f xstar) ^ 2 ≤
2 * β * ‖x 1 - xstar‖ ^ 2 * ((f (x s) - f xstar) - (f (x (s + 1)) - f xstar)) := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, §3.2, proof of Theorem 3.3, last display on p. 268
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.