Appendix B — w.p. ≥ 1 − δ, every f in F has P(Y ≠ f(X)) ≤ P̂_n(Y ≠ f(X)) + E sup_{h∈L∘F}(Eh − Ê_nh) + √(ln(1/δ)/(2n))
ProvedRadGauss.Classification.mcdiarmid_stepLet be a probability distribution on , a nonempty set of measurable -valued functions on , , and . Let be drawn from , let be the 0–1 loss, and write
Then with probability at least , every satisfies
Precisely, the -probability of the event that some violates this inequality is at most . This is the concentration half of the proof of Theorem 5(b); the remaining half bounds by .
Formalization Note The map is assumed measurable (the paper does not discuss measurability; McDiarmid's inequality needs a genuine expectation of , and is bounded, so the expectation is a Bochner integral of a bounded measurable function). The hypotheses , and are the reading of the page's "with probability at least " and "every ". The bad event is a union over and is measured by the outer measure of .
import Mathlib import Definitions.Def_RadGauss_Classification_Classifier open MeasureTheory
namespace RadGauss.Classification
/-- **McDiarmid step for the 0–1 loss** (Bartlett–Mendelson 2002, Appendix B, p. 480, second
display). With probability at least `1 − δ` over an i.i.d. sample `S ∼ P^n`, every `f ∈ F`
satisfies `P(Y ≠ f(X)) ≤ P̂_n(Y ≠ f(X)) + E sup_{h ∈ L∘F}(E h − Ê_n h) + √(ln(1/δ)/(2n))`.
The bad event (some `f ∈ F` violates the bound) has `P^n`-(outer) measure at most `δ`.
Measurability guard: the supremum `S ↦ gapSup P F S` is measurable (so its expectation is a
genuine Bochner integral of a bounded measurable function). -/
theorem mcdiarmid_step {X : Type*} [MeasurableSpace X]
(P : Measure (X × ℤˣ)) [IsProbabilityMeasure P] (F : Set (X → ℤˣ)) (hFne : F.Nonempty)
(hF : ∀ f ∈ F, Measurable f) (n : ℕ) (hn : 0 < n) (δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(hgap : Measurable (fun S : Fin n → X × ℤˣ => gapSup P F S)) :
(Measure.pi fun _ : Fin n => P)
{S | ∃ f ∈ F, ¬ (classError P f ≤ trainError S f
+ (∫ S', gapSup P F S' ∂(Measure.pi fun _ : Fin n => P))
+ Real.sqrt (Real.log (1 / δ) / (2 * n)))}
≤ ENNReal.ofReal δ := by sorry
end RadGauss.Classification
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.