Eq. (3.5), p. 267 — a gradient step of length 1/β decreases f by at least ‖∇f(x)‖²/(2β)
ProvedConvexOptAlg.SmoothGD.eq_3_5convex-optimizationgradient-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1smoothness
Let be convex and -smooth with . Then for every ,
This inequality measures the improvement made by one step of gradient descent with step size , and is the starting point of the analysis of Theorem 3.3.
Formalization Note Convexity is retained from the source context preceding (3.4). The condition is implicit in the page, which divides by .
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Eq. (3.5) (Bubeck, arXiv:1405.4980v2, p. 267): one gradient step of length `1/β` on a
convex β-smooth `f` (β > 0) decreases `f` by at least `‖∇f(x)‖²/(2β)`:
`f(x − (1/β)∇f(x)) − f(x) ≤ −(1/(2β))‖∇f(x)‖²`. -/
theorem eq_3_5 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β)
(hconv : ConvexOn ℝ Set.univ f) (hf : IsBetaSmooth f g β)
(x : EuclideanSpace ℝ (Fin n)) :
f (x - (1 / β) • g x) - f x ≤ -(1 / (2 * β)) * ‖g x‖ ^ 2 := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, Eq. (3.5), p. 267
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.