Proof of Theorem 8 — w.p. ,
ProvedRadGauss.RiskBound.mcdiarmid_stepconcentration-inequalityempirical-processlearning-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a probability measure on , let be measurable, let be a class of measurable maps , let and . Let be an i.i.d. sample from . Then with probability at least ,
The outer expectation is over the sample. This is the concentration half of the proof of Theorem 8.
Formalization Note The uniform deviation is assumed measurable (the mission's measurability guard; the paper does not discuss measurability). The statement bounds the measure of the failure event by . The hypothesis is the paper's "integer ".
Preamble
import Mathlib import Definitions.Def_RadGauss_RiskBound_uniformDeviation import Definitions.Def_RadGauss_RiskBound_phiTildeComp open MeasureTheory
Formal statement
namespace RadGauss.RiskBound
/-- **Proof of Theorem 8** (p. 467), the McDiarmid step: with probability at least `1 − δ/2` over
an i.i.d. sample of size `n ≥ 1` from `P`,
`sup_{h ∈ φ̃∘F} (E h − Ê_n h) ≤ E sup_{h ∈ φ̃∘F} (E h − Ê_n h) + √(2 ln(2/δ)/n)`.
The uniform deviation is assumed measurable as a function of the sample. -/
theorem mcdiarmid_step {X Y A : Type*} [MeasurableSpace X] [MeasurableSpace Y]
[MeasurableSpace A] [Zero A]
(φ : Y → A → ℝ) (hφ : Measurable (Function.uncurry φ))
(hφ01 : ∀ y a, 0 ≤ φ y a ∧ φ y a ≤ 1)
(F : Set (X → A)) (hF : ∀ f ∈ F, Measurable f)
(P : Measure (X × Y)) [IsProbabilityMeasure P] (n : ℕ) (hn : 0 < n)
(δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(hsup : Measurable (supDev P n (phiTildeComp φ F))) :
(Measure.pi fun _ : Fin n => P)
{S | ¬ (supDev P n (phiTildeComp φ F) S ≤
(∫ S', supDev P n (phiTildeComp φ F) S' ∂(Measure.pi fun _ : Fin n => P)) +
Real.sqrt (2 * Real.log (2 / δ) / n))}
≤ ENNReal.ofReal (δ / 2) := by sorry
end RadGauss.RiskBound
Source
Bartlett, Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, J. Mach. Learn. Res. 3 (2002), p. 467 (PDF p. 5), proof of Theorem 8, last display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.