Proof of Theorem 14.2, p. 229 — summed OMD comparison before choosing the endpoint
ProvedModernOnlineLearning.Dynamic.proof_14_2_sumdynamic-regretmirror-descentonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and let be an online mirror descent run with one positive step size , a closed -strongly convex regularizer , and subgradients . For any feasible comparator sequence , the summed inequality in the proof of Theorem 14.2 is
Keeping free exposes the comparator-shift term before the final specialization .
Formalization Note The loss sequence has a relative subgradient at each feasible point, and the run's iterates through lie in . The extra comparator is feasible; no path-length bound has been applied yet.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Dynamic_Defs
Formal statement
namespace ModernOnlineLearning.Dynamic
/-- The display beginning “Putting everything together” in the proof of
Theorem 14.2, p. 229, before choosing `u (T+1) = u T`. -/
theorem proof_14_2_sum
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(X V : Set E) (ψ : E → ℝ) (η : ℝ) (ℓ : ℕ → E → ℝ)
(x u : ℕ → E) (g : ℕ → E →L[ℝ] ℝ) (T : ℕ) (lam : ℝ)
(hT : 1 ≤ T) (hη : 0 < η) (hlam : 0 < 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))
(hψstrong : StrongConvexOn (V ∩ interior X) lam ψ)
(hrun : IsOMDRun X V ψ (fun _ => η) ℓ x g T)
(hu : ∀ t ∈ Finset.Icc 1 (T + 1), u t ∈ V) :
dynamicRegret ℓ x u T ≤
(BeckTeboulleMD.EMDA.bregman ψ (u (T + 1)) (x 1) -
BeckTeboulleMD.EMDA.bregman ψ (u (T + 1)) (x (T + 1))) / η +
(η / (2 * lam)) * (∑ t ∈ Finset.Icc 1 T, ‖g t‖ ^ 2) +
(1 / η) * (∑ t ∈ Finset.Icc 1 T,
(fderiv ℝ ψ (x (t + 1)) - fderiv ℝ ψ (x 1)) (u t - u (t + 1))) := by sorry
end ModernOnlineLearning.Dynamic
Source
Orabona, arXiv:1912.13213v10, proof of Theorem 14.2, display “Putting everything together”, p. 229 (PDF p. 241)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.