Proof of Theorem 3.10 — the adaptive-prediction concentration step
ProvedModernOnlineLearning.OnlineToBatch.martingale_step_3_10concentrationonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1probability
Draw samples independently from . Let be measurable in for every , and let the deterministic online rule predict using only samples before round . Put . For , with probability at least ,
This is the first concentration bound in the proof of Theorem 3.10, for the sample-dependent predictions.
Formalization Note The sample space is the infinite product of , and probabilities are real-valued. Measurability of each prediction, realized loss, and realized true risk is stated explicitly so the event and integrals are genuine.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OnlineToBatch_Defs
Formal statement
namespace ModernOnlineLearning.OnlineToBatch
/-- Orabona, arXiv:1912.13213v10, §3.1.2, first concentration display in the proof
of Theorem 3.10, p. 28. -/
theorem martingale_step_3_10 (d : ℕ) {D : Type*} [MeasurableSpace D]
(ρ : MeasureTheory.Measure D) [MeasureTheory.IsProbabilityMeasure ρ]
(V : Set (Decision d)) (f : Decision d → D → ℝ) (A : ℕ → (ℕ → D) → Decision d)
(T : ℕ) (δ : ℝ)
(hT : 1 ≤ T) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(hf_meas : ∀ x ∈ V, Measurable (f x))
(hf_bounds : ∀ x ∈ V, ∀ z, 0 ≤ f x z ∧ f x z ≤ 1)
(hA : IsOnlineAlgorithm V A)
(hA_meas : ∀ t ∈ Finset.Icc 1 T, Measurable (A t))
(hloss_meas : ∀ t ∈ Finset.Icc 1 T,
Measurable (fun ω : ℕ → D => f (A t ω) (ω t)))
(hrisk_meas : ∀ t ∈ Finset.Icc 1 T,
Measurable (fun ω : ℕ → D => risk ρ f (A t ω))) :
(MeasureTheory.Measure.infinitePi (fun _ : ℕ => ρ)).real
{ω : ℕ → D |
(∑ t ∈ Finset.Icc 1 T, risk ρ f (A t ω)) / (T : ℝ) ≤
(∑ t ∈ Finset.Icc 1 T, f (A t ω) (ω t)) / (T : ℝ) +
Real.sqrt (2 * Real.log (2 / δ) / (T : ℝ))} ≥ 1 - δ / 2 := by sorry
end ModernOnlineLearning.OnlineToBatch
Source
Orabona, arXiv:1912.13213v10, §3.1.2, proof of Theorem 3.10, p. 28 (PDF p. 40), display after “Thus, with probability at least 1 − δ/2”
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.