Eq. (3.4), p. 267 — a convex β-smooth f satisfies 0 ≤ f(x) − f(y) − ∇f(y)⊤(x − y) ≤ (β/2)‖x − y‖²
ProvedConvexOptAlg.SmoothGD.eq_3_4convex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1smoothness
Let be convex and -smooth. Then for all ,
The lower bound is the first-order characterization of convexity and the upper bound is Lemma 3.4. The book notes that this pair of inequalities characterizes convex -smooth functions and is often taken as their definition.
Formalization Note Convexity is Mathlib's ConvexOn ℝ Set.univ f; the gradient is an explicit map with .
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Eq. (3.4) (Bubeck, arXiv:1405.4980v2, p. 267): for a convex β-smooth `f` on `ℝⁿ` with gradient
map `g`, `0 ≤ f(x) − f(y) − ∇f(y)⊤(x − y) ≤ (β/2)‖x − y‖²` for all `x, y`. -/
theorem eq_3_4 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : ℝ)
(hconv : ConvexOn ℝ Set.univ f) (hf : IsBetaSmooth f g β) (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 := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, Eq. (3.4), p. 267
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.