Lemma 6.4, p. 29 — E_σRₙ{ℓ_f : f ∈ F, Pₙℓ_f ≤ b} = 1/2 − E_σ min{Pₙℓ(f(X),σ) : f ∈ F, Pₙℓ(f(X),Y) ≤ b}
ProvedLocalRademacher.Classif.lemma_6_4Let be fixed inputs () with labels , let be a class of classifiers with values in , and let be the discrete loss. Write and . For every such that some has ,
where is the average over the sign vectors and the left side is over the same feasible .
The lemma turns the local Rademacher average of the loss class into the expected value of a constrained empirical risk minimization problem in which the labels are replaced by random signs. It is the first step of the proof of Theorem 6.3.
Formalization Note The page writes "for every " without requiring a feasible ; the hypothesis that some has is added because the page's presupposes a nonempty feasible set (with no feasible , Lean's left side would be and its right side ). The minimum is the real infimum over the subtype of feasible classifiers; it is attained because the empirical losses take finitely many values. The Rademacher average is the published UnderstandingML.rademacher of the set of loss vectors.
import Mathlib import Definitions.Def_UnderstandingML_Rademacher import Definitions.Def_LocalRademacher_Classif_Setting
namespace LocalRademacher.Classif
/-- **Lemma 6.4** (Bartlett, Bousquet & Mendelson, arXiv:math/0508275v1, p. 29). For labels
`Yᵢ ∈ {±1}`, a class `F` of `{±1}`-valued classifiers and every `b ∈ [0, 1]` for which some
`f ∈ F` has `Pₙℓ_f ≤ b`,
`E_σ Rₙ{ℓ_f : f ∈ F, Pₙℓ_f ≤ b} = 1/2 − E_σ min{Pₙℓ(f(X), σ) : f ∈ F, Pₙℓ(f(X), Y) ≤ b}`,
both expectations being the average over the `2ⁿ` sign vectors. The feasibility hypothesis
`hfeas` is added: the page's `min` presupposes a nonempty feasible set. -/
theorem lemma_6_4 {X : Type*} (n : ℕ) (hn : 0 < n) (xs : Fin n → X) (ys : Fin n → ℝ)
(hys : ∀ i, ys i = 1 ∨ ys i = -1)
(F : Set (X → ℝ)) (hF : ∀ f ∈ F, ∀ z, f z = 1 ∨ f z = -1)
(b : ℝ) (hb0 : 0 ≤ b) (hb1 : b ≤ 1)
(hfeas : ∃ f ∈ F, empLoss xs ys f ≤ b) :
UnderstandingML.rademacher (lossVecs F xs ys b) =
1 / 2 - (1 / 2 ^ n : ℝ) * ∑ σ : Fin n → Bool,
⨅ f : {f : X → ℝ // f ∈ F ∧ empLoss xs ys f ≤ b},
empLoss xs (UnderstandingML.signVec σ) f.1 := by sorry
end LocalRademacher.Classif
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.