Lemma 6.10, p. 67 — three-part one-step OMD inequality
ProvedModernOnlineLearning.OMD.lemma_6_10bregman-divergenceonline-mirror-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret
Under the assumptions of Lemma 6.10 and an online mirror descent run, let . On every round , with positive step size and selected subgradient ,
This is the one-step estimate that telescopes to the regret bound in Theorem 6.11.
Formalization Note The primal norm is the norm on , and is the continuous dual's operator norm. Subgradient inequalities are relative to . The setting assumes the book's condition (6.5) or (6.6); and make the displayed divisions meaningful. The update's existence and uniqueness are a separate item from this lemma.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OMD_Defs
Formal statement
namespace ModernOnlineLearning.OMD
/-- The full three-part one-step inequality in Lemma 6.10, p. 67, for every
round of Algorithm 6.1 under "(6.5) or (6.6)". -/
theorem lemma_6_10 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (X V : Set E) (ψ : E → ℝ) (lam : ℝ)
(hsetting : IsOMDSetting X V ψ lam)
(T : ℕ) (η : ℕ → ℝ) (ℓ : ℕ → E → ℝ)
(x : ℕ → E) (g : ℕ → E →L[ℝ] ℝ)
(hrun : IsOMDRun T X V ψ η ℓ x g) :
∀ t ∈ Finset.Icc 1 T, ∀ u ∈ V,
η t * (ℓ t (x t) - ℓ t u) ≤ η t * g t (x t - u) ∧
η t * g t (x t - u) ≤
BeckTeboulleMD.EMDA.bregman ψ u (x t) -
BeckTeboulleMD.EMDA.bregman ψ u (x (t + 1)) -
BeckTeboulleMD.EMDA.bregman ψ (x (t + 1)) (x t) +
η t * g t (x t - x (t + 1)) ∧
BeckTeboulleMD.EMDA.bregman ψ u (x t) -
BeckTeboulleMD.EMDA.bregman ψ u (x (t + 1)) -
BeckTeboulleMD.EMDA.bregman ψ (x (t + 1)) (x t) +
η t * g t (x t - x (t + 1)) ≤
BeckTeboulleMD.EMDA.bregman ψ u (x t) -
BeckTeboulleMD.EMDA.bregman ψ u (x (t + 1)) +
(η t) ^ 2 / (2 * lam) * ‖g t‖ ^ 2 := by sorry
end ModernOnlineLearning.OMD
Source
Orabona, arXiv:1912.13213v10, Lemma 6.10, inequality clause, p. 67
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.