§3.2, proof of Theorem 3.3, p. 269 — gradient descent with η = 1/β does not increase ‖x_s − x*‖
ProvedConvexOptAlg.SmoothGD.thm_3_3_dist_decreaseconvex-optimizationgradient-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be convex and -smooth with , and let be a minimizer of on . Let be gradient descent with step size , . Then for every ,
This is the last step of the proof of Theorem 3.3: the distance to the minimizer is non-increasing along the iterates.
Formalization Note The existence of the minimizer is the book's standing assumption (p. 242). The fact used on the page is not a hypothesis; it follows from minimality. is implicit ().
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Proof of Theorem 3.3, display on p. 269 (Bubeck, arXiv:1405.4980v2): for gradient descent with
`η = 1/β` on a convex β-smooth `f` (β > 0) with a minimizer `x*`, for every `s ≥ 1`,
`‖x_{s+1} − x*‖² ≤ ‖x_s − x*‖² − (1/β²)‖∇f(x_s)‖²` and hence `‖x_{s+1} − x*‖ ≤ ‖x_s − x*‖`. -/
theorem thm_3_3_dist_decrease {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) :
‖x (s + 1) - xstar‖ ^ 2 ≤ ‖x s - xstar‖ ^ 2 - 1 / β ^ 2 * ‖g (x s)‖ ^ 2 ∧
‖x (s + 1) - xstar‖ ≤ ‖x s - xstar‖ := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, §3.2, proof of Theorem 3.3, display on p. 269 (after (3.6))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.