Appendix B (corrected) — E sup_{h∈L∘F}(Eh − Ê_nh) ≤ R_n(F)/2 for the 0–1 loss
ProvedRadGauss.Classification.symmetrizationLet be a probability distribution on , its marginal on , a nonempty set of measurable -valued functions on , , and . With the 0–1 loss ,
where is the Rademacher complexity (Definition 2) of , viewed as a class of real functions with values in , with respect to .
This is the symmetrization half of the proof of Theorem 5(b): the expected worst-case gap between misclassification probability and training error is controlled by the Rademacher complexity of the classifiers themselves, not of the loss class.
Formalization Note The paper prints the chain ending "". The last step is only an inequality: has an absolute value inside the supremum, and for a single function the left side of that step is while . The statement here is the chain's conclusion with , which is what Theorem 5(b) uses. The left side is a real number converted to ; it is nonnegative for nonempty . Three random variables are assumed measurable, because the proof integrates them: , the double-sample supremum , and . The hypothesis is needed: at the factor is in Lean, so while the left side can be positive.
import Mathlib import Definitions.Def_RadGauss_Classification_Complexity import Definitions.Def_RadGauss_Classification_Classifier open MeasureTheory
namespace RadGauss.Classification
/-- **Symmetrization for the 0–1 loss** (Bartlett–Mendelson 2002, Appendix B, p. 480, third
display, corrected): `E sup_{h ∈ L∘F} (E h − Ê_n h) ≤ R_n(F)/2`, where `L(Y, f(X)) = 1(Y ≠ f(X))`
and `R_n(F)` is the Rademacher complexity (Definition 2, with the absolute value) of the real
class `F ⊆ {±1}^X` with respect to the marginal of `P` on `X`. The paper prints the last step of
its chain as an equality; it is only an inequality (for `F = {f}` the left side of that step is
`0` while `R_n(F)/2 > 0`), and the chain's conclusion is stated with `≤`.
Measurability guards: `S ↦ sup_f (P(Y ≠ f(X)) − P̂_n(Y ≠ f(X)))`, the double-sample supremum
`(S, S') ↦ sup_f (P̂'_n − P̂_n)(Y ≠ f(X))`, and `x ↦ R̂_n(F)(x)` are measurable. -/
theorem symmetrization {X : Type*} [MeasurableSpace X]
(P : Measure (X × ℤˣ)) [IsProbabilityMeasure P] (F : Set (X → ℤˣ)) (hFne : F.Nonempty)
(hF : ∀ f ∈ F, Measurable f) (n : ℕ) (hn : 0 < n)
(hgap : Measurable (fun S : Fin n → X × ℤˣ => gapSup P F S))
(hghost : Measurable (fun p : (Fin n → X × ℤˣ) × (Fin n → X × ℤˣ) =>
ghostGapSup F p.1 p.2))
(hrad : Measurable (fun x : Fin n → X => empiricalRademacher (realClass F) n x)) :
ENNReal.ofReal (∫ S, gapSup P F S ∂(Measure.pi fun _ : Fin n => P))
≤ rademacherComplexity (P.map Prod.fst) n (realClass F) / 2 := by sorry
end RadGauss.Classification
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.