Theorem 3.17 — validation over a finite set
ProvedModernOnlineLearning.OnlineToBatch.theorem_3_17concentrationempirical-riskmachine-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Fix a nonempty finite set before drawing independent samples from . Let , define , and choose a measurable empirical-risk minimizer of . For , with probability at least ,
This validates a predictor selected from finitely many candidates using fresh data.
Formalization Note Nonemptiness makes the empirical minimizer and the real infimum meaningful. Measurability of for and of the selected minimizer is explicit. The minimum is represented by the infimum over a nonempty finite bounded-risk set.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OnlineToBatch_Defs
Formal statement
namespace ModernOnlineLearning.OnlineToBatch
/-- Orabona, arXiv:1912.13213v10, Theorem 3.17, pp. 31–32. -/
theorem theorem_3_17 (d : ℕ) {D : Type*} [MeasurableSpace D]
(ρ : MeasureTheory.Measure D) [MeasureTheory.IsProbabilityMeasure ρ]
(V : Set (Decision d)) (S : Finset (Decision d)) (f : Decision d → D → ℝ)
(T : ℕ) (δ : ℝ) (xHat : (ℕ → D) → Decision d)
(hT : 1 ≤ T) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(hS : S.Nonempty) (hSV : ∀ x ∈ S, x ∈ V)
(hf_meas : ∀ x ∈ V, Measurable (f x))
(hf_bounds : ∀ x ∈ V, ∀ z, 0 ≤ f x z ∧ f x z ≤ 1)
(hxHat : ∀ ω, xHat ω ∈ S)
(hxMin : ∀ ω, ∀ x ∈ S, empiricalRisk f ω (xHat ω) T ≤ empiricalRisk f ω x T)
(hxMeas : Measurable xHat) :
(MeasureTheory.Measure.infinitePi (fun _ : ℕ => ρ)).real
{ω : ℕ → D | risk ρ f (xHat ω) ≤ bestRisk ρ f S +
2 * Real.sqrt (2 * Real.log (2 * (S.card : ℝ) / δ) / (T : ℝ))} ≥
1 - δ := by sorry
end ModernOnlineLearning.OnlineToBatch
Source
Orabona, arXiv:1912.13213v10, Theorem 3.17, pp. 31–32 (PDF pp. 43–44)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.