Lemma 3.5, p. 268 — if (3.4) holds, then f(x) − f(y) ≤ ∇f(x)⊤(x − y) − (1/(2β))‖∇f(x) − ∇f(y)‖²
ProvedConvexOptAlg.SmoothGD.lemma_3_5convex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1smoothness
Let be differentiable, let , and suppose that (3.4) holds: for all ,
Then for all ,
This sharpens the basic subgradient inequality under smoothness, and shows that (3.4) implies co-coercivity of the gradient (3.6).
Formalization Note The hypothesis is the two-sided inequality (3.4), as in the book, not "convex and -smooth". The gradient is an explicit map with ; 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
/-- Lemma 3.5 (Bubeck, arXiv:1405.4980v2, p. 268): let `f : ℝⁿ → ℝ` be differentiable with
gradient map `g`, `β > 0`, and suppose (3.4) holds for all `x, y`:
`0 ≤ f(x) − f(y) − ∇f(y)⊤(x − y) ≤ (β/2)‖x − y‖²`. Then for all `x, y`,
`f(x) − f(y) ≤ ∇f(x)⊤(x − y) − (1/(2β))‖∇f(x) − ∇f(y)‖²`.
The hypothesis is the two-sided inequality (3.4), as printed, not convexity and β-smoothness. -/
theorem lemma_3_5 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β)
(hgrad : ∀ x, HasGradientAt f (g x) x)
(h34 : ∀ x y : EuclideanSpace ℝ (Fin n),
0 ≤ f x - f y - ⟪g y, x - y⟫_ℝ ∧ f x - f y - ⟪g y, x - y⟫_ℝ ≤ β / 2 * ‖x - y‖ ^ 2)
(x y : EuclideanSpace ℝ (Fin n)) :
f x - f y ≤ ⟪g x, x - y⟫_ℝ - 1 / (2 * β) * ‖g x - g y‖ ^ 2 := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, Lemma 3.5, p. 268
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.