Theorem 3.9 — Hoeffding–Azuma inequality for bounded martingale differences
ProvedModernOnlineLearning.OnlineToBatch.theorem_3_9concentrationmartingalep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probability
Let be an integrable martingale on a probability space, adapted to a filtration. Suppose , , , and almost surely for every . Then both tails satisfy
This concentration bound supplies the two deviations used in the high-probability online-to-batch conversion.
Formalization Note The source leaves the threshold and denominator domain implicit. The conditions , and make its printed formula valid and defined. The martingale is indexed only through , matching the finite sequence in the book.
Preamble
import Mathlib
Formal statement
namespace ModernOnlineLearning.OnlineToBatch
/-- Orabona, arXiv:1912.13213v10, Theorem 3.9, p. 27. -/
theorem theorem_3_9 {Ω : Type*} [MeasurableSpace Ω]
(μ : MeasureTheory.Measure Ω) [MeasureTheory.IsProbabilityMeasure μ]
(T : ℕ) (ℱ : MeasureTheory.Filtration (Fin (T + 1)) ‹MeasurableSpace Ω›)
(Z : Fin (T + 1) → Ω → ℝ) (B ε : ℝ)
(hT : 1 ≤ T) (hB : 0 < B) (hε : 0 ≤ ε)
(hZ : MeasureTheory.Martingale Z ℱ μ)
(hZint : ∀ t : Fin (T + 1), MeasureTheory.Integrable (Z t) μ)
(hdiff : ∀ t : Fin T,
∀ᵐ ω ∂μ, |Z ⟨t.val + 1, Nat.succ_lt_succ t.isLt⟩ ω -
Z ⟨t.val, Nat.lt_trans t.isLt (Nat.lt_succ_self T)⟩ ω| ≤ B) :
μ.real {ω | ε ≤ Z (Fin.last T) ω - Z ⟨0, Nat.zero_lt_succ T⟩ ω} ≤
Real.exp (-(ε ^ 2) / (2 * B ^ 2 * (T : ℝ))) ∧
μ.real {ω | ε ≤ Z ⟨0, Nat.zero_lt_succ T⟩ ω - Z (Fin.last T) ω} ≤
Real.exp (-(ε ^ 2) / (2 * B ^ 2 * (T : ℝ))) := by sorry
end ModernOnlineLearning.OnlineToBatch
Source
Orabona, arXiv:1912.13213v10, Theorem 3.9, p. 27 (PDF p. 39)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.