Lemma 3.4, p. 267 — a β-smooth f satisfies |f(x) − f(y) − ∇f(y)⊤(x − y)| ≤ (β/2)‖x − y‖²
ProvedConvexOptAlg.SmoothGD.lemma_3_4convex-optimizationdescent-lemmap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1smoothness
Let be -smooth, i.e. differentiable with -Lipschitz gradient . Then for all ,
This is the two-sided quadratic bound on the error of the first-order Taylor approximation; no convexity is assumed. Its upper half is the descent lemma used to measure the progress of one gradient step.
Formalization Note The gradient is an explicit map with for every ; is included because a Lipschitz constant is non-negative, including when .
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Lemma 3.4 (Bubeck, arXiv:1405.4980v2, p. 267): for a β-smooth `f` on `ℝⁿ` with gradient map
`g`, `|f(x) − f(y) − ∇f(y)⊤(x − y)| ≤ (β/2)‖x − y‖²` for all `x, y`. No convexity. -/
theorem lemma_3_4 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : ℝ)
(hf : IsBetaSmooth f g β) (x y : EuclideanSpace ℝ (Fin n)) :
|f x - f y - ⟪g y, x - y⟫_ℝ| ≤ β / 2 * ‖x - y‖ ^ 2 := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, Lemma 3.4, p. 267
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.