Theorem 3.3, p. 267 — gradient descent with η = 1/β on a convex β-smooth f satisfies f(x_t) − f(x*) ≤ 2β‖x₁ − x*‖²/(t − 1)
ProvedConvexOptAlg.SmoothGD.theorem_3_3convergence-rateconvex-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 started at :
Then for every ,
This is the basic convergence rate of gradient descent on smooth convex functions: the optimality gap decays like , with a constant depending only on the smoothness and on the initial distance to a minimizer, and not on the dimension.
Formalization Note The bound is stated for : at the right-hand side has denominator . The existence of a minimizer is the book's standing assumption (p. 242). is implicit in the step size . The gradient is an explicit map with , and is EuclideanSpace ℝ (Fin n).
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Theorem 3.3 (Bubeck, arXiv:1405.4980v2, p. 267): let `f` be convex and β-smooth on `ℝⁿ`
(β > 0) with a minimizer `x*`. Then gradient descent with `η = 1/β`, started at `x₁`, satisfies
`f(x_t) − f(x*) ≤ 2β‖x₁ − x*‖²/(t − 1)` for every `t ≥ 2`. -/
theorem theorem_3_3 {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) (t : ℕ) (ht : 2 ≤ t) :
f (x t) - f xstar ≤ 2 * β * ‖x 1 - xstar‖ ^ 2 / ((t : ℝ) - 1) := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, Theorem 3.3, p. 267
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.