Lemma 6.7, p. 64 — Bregman three-point identity
ProvedModernOnlineLearning.OMD.lemma_6_7bregman-divergenceconvex-optimizationonline-mirror-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be strictly convex on its domain and differentiable on . For and , its Bregman divergence obeys
The identity reorganizes three divergence terms into one dual pairing; it is used in the one-step analysis of mirror descent.
Formalization Note Gradients are Fréchet derivatives in the continuous dual. The statement assumes differentiability on the interior, as Definition 6.4 does; the related published Beck–Teboulle identity assumes the stronger condition and therefore is not used as an exact reference.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OMD_Defs
Formal statement
namespace ModernOnlineLearning.OMD
/-- Orabona, Lemma 6.7, p. 64, with only the differentiability required by
Definition 6.4. -/
theorem lemma_6_7 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (X : Set E) (ψ : E → ℝ)
(hstrict : StrictConvexOn ℝ X ψ)
(hdiff : DifferentiableOn ℝ ψ (interior X))
(x y z : E) (hx : x ∈ interior X) (hy : y ∈ interior X) (hz : z ∈ X) :
BeckTeboulleMD.EMDA.bregman ψ z x +
BeckTeboulleMD.EMDA.bregman ψ x y -
BeckTeboulleMD.EMDA.bregman ψ z y =
(fderiv ℝ ψ y - fderiv ℝ ψ x) (z - x) := by sorry
end ModernOnlineLearning.OMD
Source
Orabona, arXiv:1912.13213v10, Lemma 6.7, p. 64
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.