Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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}

Proved
LocalRademacher.Classif.lemma_6_4

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

classificationdiscrete-lossempirical-risk-minimizationlocal-rademacher-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let X1,…,XnX_1,\dots,X_nX1​,…,Xn​ be fixed inputs (n≥1n\ge1n≥1) with labels Y1,…,Yn∈{−1,1}Y_1,\dots,Y_n\in\{-1,1\}Y1​,…,Yn​∈{−1,1}, let F\mathcal FF be a class of classifiers with values in {−1,1}\{-1,1\}{−1,1}, and let ℓ(y,y′)=1[y≠y′]\ell(y,y')=\mathbf 1[y\ne y']ℓ(y,y′)=1[y=y′] be the discrete loss. Write Pnℓ(f(X),z)=1n∑iℓ(f(Xi),zi)P_n\ell(f(X),z)=\frac1n\sum_i\ell(f(X_i),z_i)Pn​ℓ(f(X),z)=n1​∑i​ℓ(f(Xi​),zi​) and Pnℓf=Pnℓ(f(X),Y)P_n\ell_f=P_n\ell(f(X),Y)Pn​ℓf​=Pn​ℓ(f(X),Y). For every b∈[0,1]b\in[0,1]b∈[0,1] such that some f∈Ff\in\mathcal Ff∈F has Pnℓf≤bP_n\ell_f\le bPn​ℓf​≤b,

EσRn{ℓf:f∈F, Pnℓf≤b}=12−Eσmin⁡{Pnℓ(f(X),σ):f∈F, Pnℓ(f(X),Y)≤b},\mathbb E_\sigma R_n\{\ell_f : f\in\mathcal F,\ P_n\ell_f\le b\}=\frac12-\mathbb E_\sigma\min\{P_n\ell(f(X),\sigma) : f\in\mathcal F,\ P_n\ell(f(X),Y)\le b\},Eσ​Rn​{ℓf​:f∈F, Pn​ℓf​≤b}=21​−Eσ​min{Pn​ℓ(f(X),σ):f∈F, Pn​ℓ(f(X),Y)≤b},

where Eσ\mathbb E_\sigmaEσ​ is the average over the 2n2^n2n sign vectors σ∈{−1,1}n\sigma\in\{-1,1\}^nσ∈{−1,1}n and the left side is 1nEσsup⁡f∑iσiℓ(f(Xi),Yi)\frac1n\mathbb E_\sigma\sup_f\sum_i\sigma_i\ell(f(X_i),Y_i)n1​Eσ​supf​∑i​σi​ℓ(f(Xi​),Yi​) over the same feasible fff.

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 b∈[0,1]b\in[0,1]b∈[0,1]" without requiring a feasible fff; the hypothesis that some f∈Ff\in\mathcal Ff∈F has Pnℓf≤bP_n\ell_f\le bPn​ℓf​≤b is added because the page's min⁡\minmin presupposes a nonempty feasible set (with no feasible fff, Lean's left side would be 000 and its right side 1/21/21/2). 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.

Preamble
import Mathlib
import Definitions.Def_UnderstandingML_Rademacher
import Definitions.Def_LocalRademacher_Classif_Setting
Formal statement
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
Source
Bartlett, Bousquet & Mendelson, arXiv:math/0508275v1, Lemma 6.4, p. 29 (proof pp. 29–30)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me