Lemma 6.10, p. 67 — one-step OMD inequality chain
ProvedModernOnlineLearning.Dynamic.lemma_6_10Let be a nonempty closed convex feasible set in a finite-dimensional real normed space. Let be closed, differentiable at the interior points used by OMD, and -strongly convex on , with . For an OMD update with step , a chosen subgradient , and every , the inequality part of Lemma 6.10 is
This is the per-round estimate used in the dynamic regret analysis.
Formalization Note This item states the inequality part for an already-defined run; it does not claim the lemma's separate existence and uniqueness result. The OMD run records the interior condition and the book's Algorithm 6.1 update. Relative subgradients on suffice for these comparisons. The book assumes "(6.5) or (6.6)" and derives ; here that conclusion is taken directly as a clause of the run, as Theorem 14.2 does. The book's -strong convexity "in " is assumed only on the convex set , which contains every point the inequality chain uses, so this item is implied by the book's inequality.
import Mathlib import Definitions.Def_ModernOnlineLearning_Dynamic_Defs
namespace ModernOnlineLearning.Dynamic
/-- Lemma 6.10, p. 67, inequality part, for a well-defined OMD run.
The existence and uniqueness assertion is represented by the run predicate's
chosen argmin and is not part of this item. -/
theorem lemma_6_10
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(X V : Set E) (ψ : E → ℝ) (η : ℕ → ℝ) (ℓ : ℕ → E → ℝ)
(x : ℕ → E) (g : ℕ → E →L[ℝ] ℝ) (T : ℕ) (lam : ℝ)
(hVsub : V ⊆ X) (hVne : V.Nonempty) (hVclosed : IsClosed V)
(hVconv : Convex ℝ V) (hXconv : Convex ℝ X)
(hψclosed : ClosedRegularizerOn X ψ)
(hψstrict : StrictConvexOn ℝ X ψ)
(hψdiff : DifferentiableOn ℝ ψ (interior X))
(hlam : 0 < lam) (hψstrong : StrongConvexOn (V ∩ interior X) lam ψ)
(hrun : IsOMDRun X V ψ η ℓ x g T) :
∀ 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.Dynamic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.