Eq. (3.6), p. 269 — the gradient of a convex β-smooth f is (1/β)-co-coercive
ProvedConvexOptAlg.SmoothGD.eq_3_6co-coercivityconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1smoothness
Let be convex and -smooth with . Then for all ,
This co-coercivity of the gradient is what makes the distance from the gradient descent iterates to a minimizer non-increasing in the proof of Theorem 3.3.
Formalization Note The gradient is an explicit map ; 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.6) (Bubeck, arXiv:1405.4980v2, p. 269): the gradient of a convex β-smooth `f` on `ℝⁿ`
(β > 0) is co-coercive, `(∇f(x) − ∇f(y))⊤(x − y) ≥ (1/β)‖∇f(x) − ∇f(y)‖²` for all `x, y`. -/
theorem eq_3_6 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β)
(hconv : ConvexOn ℝ Set.univ f) (hf : IsBetaSmooth f g β) (x y : EuclideanSpace ℝ (Fin n)) :
1 / β * ‖g x - g y‖ ^ 2 ≤ ⟪g x - g y, x - y⟫_ℝ := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, Eq. (3.6), §3.2, proof of Theorem 3.3, p. 269
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.