Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8 — w.p. ≥1−δ\ge 1-\delta≥1−δ, EL(Y,f(X))≤E^nϕ(Y,f(X))+Rn(ϕ~∘F)+8ln⁡(2/δ)/n\mathbf E\mathcal L(Y,f(X))\le\hat{\mathbf E}_n\phi(Y,f(X))+R_n(\tilde\phi\circ F)+\sqrt{8\ln(2/\delta)/n}EL(Y,f(X))≤E^n​ϕ(Y,f(X))+Rn​(ϕ~​∘F)+8ln(2/δ)/n​ for every f∈Ff\in Ff∈F

Proved
RadGauss.RiskBound.theorem_8

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

generalization-boundlearning-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity

Let X\mathcal XX be an input space, A\mathcal AA an action space containing a distinguished action 000, and Y\mathcal YY an output space. Let L:Y×A→[0,1]\mathcal L : \mathcal Y \times \mathcal A \to [0, 1]L:Y×A→[0,1] be a loss function and ϕ:Y×A→[0,1]\phi : \mathcal Y \times \mathcal A \to [0, 1]ϕ:Y×A→[0,1] a dominating cost function, ϕ(y,a)≥L(y,a)\phi(y, a) \ge \mathcal L(y, a)ϕ(y,a)≥L(y,a) for all y∈Yy \in \mathcal Yy∈Y, a∈Aa \in \mathcal Aa∈A. Let FFF be a class of functions from X\mathcal XX to A\mathcal AA, and let (X1,Y1),…,(Xn,Yn)(X_1, Y_1), \dots, (X_n, Y_n)(X1​,Y1​),…,(Xn​,Yn​) be independent, each distributed according to a probability measure PPP on X×Y\mathcal X \times \mathcal YX×Y; (X,Y)(X, Y)(X,Y) denotes a fresh draw from PPP and E^nh(X,Y)=1n∑i=1nh(Xi,Yi)\hat{\mathbf E}_n h(X, Y) = \frac1n\sum_{i=1}^n h(X_i, Y_i)E^n​h(X,Y)=n1​∑i=1n​h(Xi​,Yi​). Then for every integer n≥1n \ge 1n≥1 and every 0<δ<10 < \delta < 10<δ<1, with probability at least 1−δ1 - \delta1−δ over samples of length nnn, every f∈Ff \in Ff∈F satisfies

EL(Y,f(X))≤E^nϕ(Y,f(X))+Rn(ϕ~∘F)+8ln⁡(2/δ)n,\mathbf E\mathcal L(Y, f(X)) \le \hat{\mathbf E}_n\phi(Y, f(X)) + R_n(\tilde\phi\circ F) + \sqrt{\frac{8\ln(2/\delta)}{n}},EL(Y,f(X))≤E^n​ϕ(Y,f(X))+Rn​(ϕ~​∘F)+n8ln(2/δ)​​,

where ϕ~∘F={(x,y)↦ϕ(y,f(x))−ϕ(y,0):f∈F}\tilde\phi\circ F = \{(x, y) \mapsto \phi(y, f(x)) - \phi(y, 0) : f \in F\}ϕ~​∘F={(x,y)↦ϕ(y,f(x))−ϕ(y,0):f∈F} and RnR_nRn​ is the Rademacher complexity of Definition 2 with respect to PPP.

The bound controls the expected loss of every predictor in the class, including one chosen after seeing the data, by an observable surrogate cost plus a complexity penalty of the centred cost class; it is the decision-theoretic risk bound of the paper, covering multiclass and other structured prediction problems.

Formalization Note

  1. The probability is the product measure PnP^nPn of the set of samples on which some f∈Ff \in Ff∈F violates the bound (an outer measure, so the event need not be measurable); the quantifier over FFF is inside the event.
  2. RnR_nRn​ takes values in [0,∞][0, \infty][0,∞], so the inequality is stated in [0,∞][0,\infty][0,∞], with the real, nonnegative terms EL\mathbf E\mathcal LEL, E^nϕ\hat{\mathbf E}_n\phiE^n​ϕ and the square root embedded by ENNReal.ofReal.
  3. Added hypotheses, all implicit in the paper: n≥1n \ge 1n≥1 (at n=0n = 0n=0 the bound would read EL≤0\mathbf E\mathcal L \le 0EL≤0, false); L\mathcal LL, ϕ\phiϕ and the members of FFF are measurable; A\mathcal AA has a distinguished element 000.
  4. Measurability guard: three random variables are assumed measurable — the uniform deviation S↦sup⁡h∈ϕ~∘F(Eh−E^nh)S \mapsto \sup_{h\in\tilde\phi\circ F}(\mathbf Eh - \hat{\mathbf E}_nh)S↦suph∈ϕ~​∘F​(Eh−E^n​h), the empirical Rademacher complexity S↦R^n(ϕ~∘F)(S)S \mapsto \hat R_n(\tilde\phi\circ F)(S)S↦R^n​(ϕ~​∘F)(S), and the double-sample deviation (S,S′)↦sup⁡h(1n∑ih(Si′)−E^nh)(S, S') \mapsto \sup_h(\frac1n\sum_i h(S'_i) - \hat{\mathbf E}_nh)(S,S′)↦suph​(n1​∑i​h(Si′​)−E^n​h). They hold, for instance, for countable FFF. Without them RnR_nRn​ would be a lower integral and the bound could fail.
Preamble
import Mathlib
import Definitions.Def_RadGauss_RiskBound_rademacherComplexity
import Definitions.Def_RadGauss_RiskBound_uniformDeviation
import Definitions.Def_RadGauss_RiskBound_phiTildeComp

open MeasureTheory
Formal statement
namespace RadGauss.RiskBound

/-- **Theorem 8** (p. 467). Let `L : 𝒴 × 𝒜 → [0, 1]` be a loss and `φ : 𝒴 × 𝒜 → [0, 1]` a cost
dominating it, `F` a class of maps `𝒳 → 𝒜`, and `(X_i, Y_i)_{i=1}^n` i.i.d. from the probability
measure `P` on `𝒳 × 𝒴`. For every `n ≥ 1` and `0 < δ < 1`, with probability at least `1 − δ`
every `f ∈ F` satisfies
`E L(Y, f(X)) ≤ Ê_n φ(Y, f(X)) + R_n(φ̃∘F) + √(8 ln(2/δ)/n)`,
where `φ̃∘F = {(x, y) ↦ φ(y, f(x)) − φ(y, 0) : f ∈ F}`. The probability of the bad event is an
outer measure. Measurability guard: the uniform deviation, the empirical Rademacher complexity
of `φ̃∘F` and the double-sample supremum are measurable functions of the sample(s). -/
theorem theorem_8 {X Y A : Type*} [MeasurableSpace X] [MeasurableSpace Y]
    [MeasurableSpace A] [Zero A]
    (L φ : Y → A → ℝ) (hL : Measurable (Function.uncurry L))
    (hφ : Measurable (Function.uncurry φ))
    (hL01 : ∀ y a, 0 ≤ L y a ∧ L y a ≤ 1) (hφ01 : ∀ y a, 0 ≤ φ y a ∧ φ y a ≤ 1)
    (hdom : ∀ y a, L y a ≤ φ y a)
    (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)))
    (hrad : Measurable (empiricalRademacher n (phiTildeComp φ F)))
    (hdbl : Measurable (fun p : (Fin n → X × Y) × (Fin n → X × Y) =>
      doubleSupDev n (phiTildeComp φ F) p.1 p.2)) :
    (Measure.pi fun _ : Fin n => P)
      {S | ∃ f ∈ F, ¬ (ENNReal.ofReal (∫ z, L z.2 (f z.1) ∂P) ≤
          ENNReal.ofReal (empMean S (fun z => φ z.2 (f z.1))) +
            rademacherComplexity P n (phiTildeComp φ F) +
            ENNReal.ofReal (Real.sqrt (8 * Real.log (2 / δ) / n)))}
      ≤ ENNReal.ofReal δ := 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), Theorem 8
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