Lemma 6.10, p. 67 — existence and uniqueness of the OMD update
ProvedModernOnlineLearning.OMD.lemma_6_10_existsconvex-optimizationonline-mirror-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1strong-convexity
Let be nonempty, closed, and convex, and assume condition (6.5) or condition (6.6), . Let be proper, closed, differentiable on , and -strongly convex on , where . For any , positive step size , and dual vector , there is exactly one minimizing
and that point lies in . Thus the next OMD iterate exists and is well defined.
Formalization Note The setting also records strict convexity of on from Definition 6.4. Properness follows from and ; closedness is stated through the epigraph. Condition (6.5) is encoded as for every and ; the setting assumes (6.5) or (6.6), as the book does.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OMD_Defs
Formal statement
namespace ModernOnlineLearning.OMD
/-- The existence, uniqueness, and interior-point clause of Lemma 6.10, p. 67,
under "(6.5) or (6.6)": the argmin of the update exists, is unique, and lies in
`int X`. -/
theorem lemma_6_10_exists {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (X V : Set E) (ψ : E → ℝ) (lam : ℝ)
(hsetting : IsOMDSetting X V ψ lam)
(x : E) (hx : x ∈ V ∩ interior X)
(η : ℝ) (hη : 0 < η) (g : E →L[ℝ] ℝ) :
(∃! y : E, IsOMDStep V ψ η g x y) ∧
∀ y : E, IsOMDStep V ψ η g x y → y ∈ interior X := by sorry
end ModernOnlineLearning.OMD
Source
Orabona, arXiv:1912.13213v10, Lemma 6.10, existence and uniqueness clause, p. 67
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.