Theorem 6.9, p. 66 — unique minimizer of a closed strongly convex function
ProvedModernOnlineLearning.OMD.theorem_6_9convex-optimizationminimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1strong-convexity
Let be a proper, closed function on a finite-dimensional real normed space, with finite domain . Suppose is -strongly convex on for , and its subdifferential is nonempty at some point of . Then there is exactly one such that
This existence and uniqueness result supplies the minimizer of each strongly convex mirror-descent update.
Formalization Note The extended-valued function is represented by a real-valued function on its exact finite domain and by elsewhere. Closedness is closedness of that extended function's epigraph. The nonempty-subdifferential hypothesis is an explicit point and continuous linear subgradient on .
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OMD_Defs
Formal statement
namespace ModernOnlineLearning.OMD
/-- Orabona, Theorem 6.9, p. 66. The extended function is represented by a
real-valued `f` on its exact finite domain `D`, and `+∞` elsewhere. -/
theorem theorem_6_9 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (D : Set E) (f : E → ℝ) (lam : ℝ)
(hlam : 0 < lam) (hclosed : IsClosedOnDomain D f)
(hstrong : StrongConvexOn D lam f)
(hsub : ∃ y ∈ D, ∃ g : E →L[ℝ] ℝ, IsSubgradientOn D f y g) :
∃! x : E, x ∈ D ∧ ∀ z ∈ D, f x ≤ f z := by sorry
end ModernOnlineLearning.OMD
Source
Orabona, arXiv:1912.13213v10, Theorem 6.9, p. 66
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.