Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 15 — sample variance penalization has excess risk ≤32V(f∗,μ)ln⁡(3M(n)/δ)/n+22ln⁡(3M(n)/δ)/(n−1)\le\sqrt{32V(f^*,\mu)\ln(3\mathcal M(n)/\delta)/n}+22\ln(3\mathcal M(n)/\delta)/(n-1)≤32V(f∗,μ)ln(3M(n)/δ)/n​+22ln(3M(n)/δ)/(n−1)

Proved
EmpiricalBernstein.SVP.svp_excess_risk

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

empirical-bernsteinlearning-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-variance-penalization

Let XXX be a random variable with values in a set X\mathcal XX and distribution μ\muμ, and let F\mathcal FF be a class of hypotheses f:X→[0,1]f : \mathcal X \to [0,1]f:X→[0,1]. Fix δ∈(0,1)\delta \in (0,1)δ∈(0,1) and n≥2n \ge 2n≥2, and set

M(n)=10 N∞(1/n,F,2n),λ=18ln⁡(3M(n)/δ).\mathcal M(n) = 10\,\mathcal N_\infty(1/n,\mathcal F,2n), \qquad \lambda = \sqrt{18\ln(3\mathcal M(n)/\delta)} .M(n)=10N∞​(1/n,F,2n),λ=18ln(3M(n)/δ)​.

Sample variance penalization selects, from a sample X\mathbf XX, a hypothesis

SVPλ(X)∈arg⁡min⁡f∈F  Pn(f,X)+λVn(f,X)n.SVP_\lambda(\mathbf X) \in \arg\min_{f\in\mathcal F}\; P_n(f,\mathbf X) + \lambda\sqrt{\frac{V_n(f,\mathbf X)}{n}} .SVPλ​(X)∈argf∈Fmin​Pn​(f,X)+λnVn​(f,X)​​.

Fix f∗∈Ff^* \in \mathcal Ff∗∈F. Then with probability at least 1−δ1-\delta1−δ in the draw of X∼μn\mathbf X \sim \mu^nX∼μn,

P(SVPλ(X),μ)−P(f∗,μ)≤32 V(f∗,μ)ln⁡(3M(n)/δ)n+22ln⁡(3M(n)/δ)n−1.P(SVP_\lambda(\mathbf X),\mu) - P(f^*,\mu) \le \sqrt{\frac{32\, V(f^*,\mu)\ln(3\mathcal M(n)/\delta)}{n}} + \frac{22\ln(3\mathcal M(n)/\delta)}{n-1}.P(SVPλ​(X),μ)−P(f∗,μ)≤n32V(f∗,μ)ln(3M(n)/δ)​​+n−122ln(3M(n)/δ)​.

Here P(f,μ)=Ef(X)P(f,\mu)=\mathbb Ef(X)P(f,μ)=Ef(X), V(f,μ)=Vf(X)V(f,\mu) = \mathbb Vf(X)V(f,μ)=Vf(X), PnP_nPn​ and VnV_nVn​ are the sample mean and sample variance of (f(X1),…,f(Xn))(f(X_1),\dots,f(X_n))(f(X1​),…,f(Xn​)), and N∞\mathcal N_\inftyN∞​ is the growth function.

Taking f∗f^*f∗ optimal, the excess risk of the selected hypothesis is controlled by the variance of an optimal hypothesis: it decays as (ln⁡M(n))/n(\ln\mathcal M(n))/n(lnM(n))/n when some optimal hypothesis has zero variance, whereas empirical risk minimization can be stuck at order 1/n1/\sqrt n1/n​.

Formalization Note The selector is any function svp that returns, for every sample, an element of F\mathcal FF minimizing the penalized objective with the stated λ\lambdaλ; every minimizer is covered, as the paper's arg⁡min⁡\arg\minargmin presupposes one exists. No measurability of svp is assumed: the probability of the bad event is its outer measure under μn\mu^nμn. Added hypotheses, making the paper's convention on measurability precise: F\mathcal FF countable with measurable members, and N∞(1/n,F,2n)<∞\mathcal N_\infty(1/n,\mathcal F,2n)<\inftyN∞​(1/n,F,2n)<∞ (M(n)\mathcal M(n)M(n) is the real number calM F n). V(f∗,μ)V(f^*,\mu)V(f∗,μ) is Mathlib's variance. n≥2n\ge2n≥2 is as printed.

Preamble
import Mathlib
import Definitions.Def_VarianceRegularization_Expansion_empMean
import Definitions.Def_EmpiricalBernstein_SVP_sampleVar
import Definitions.Def_EmpiricalBernstein_SVP_growthFunction

open MeasureTheory ProbabilityTheory VarianceRegularization.Expansion
Formal statement
namespace EmpiricalBernstein.SVP

/-- Theorem 15 (arXiv:0907.3740v1, p. 6): excess risk of sample variance penalization (10) with
`λ = √(18 ln(3ℳ(n)/δ))`. `svp` is any selector returning, for every sample `x`, a minimizer over
`F` of `P_n(f, x) + λ √(V_n(f, x)/n)` (the paper's `arg min`). `F` is a countable class of
measurable `[0,1]`-valued functions with finite growth function `N∞(1/n, F, 2n)`. The probability
of the (possibly non-measurable) bad event is its outer measure under `μ^n`. -/
theorem svp_excess_risk {𝒳 : Type*} [MeasurableSpace 𝒳] (μ : Measure 𝒳) [IsProbabilityMeasure μ]
    (F : Set (𝒳 → ℝ)) (hFc : F.Countable) (hFm : ∀ f ∈ F, Measurable f)
    (hF01 : ∀ f ∈ F, ∀ y, f y ∈ Set.Icc (0 : ℝ) 1)
    (δ : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1) (n : ℕ) (hn : 2 ≤ n)
    (hfin : growthFunction (1 / (n : ℝ)) F (2 * n) < ⊤)
    (lam : ℝ) (hlam : lam = Real.sqrt (18 * Real.log (3 * calM F n / δ)))
    (fstar : 𝒳 → ℝ) (hfstar : fstar ∈ F)
    (svp : (Fin n → 𝒳) → (𝒳 → ℝ)) (hsvpF : ∀ x, svp x ∈ F)
    (hsvp : ∀ x, ∀ f ∈ F,
      empMean (fun i => svp x (x i)) + lam * Real.sqrt (sampleVar (fun i => svp x (x i)) / n)
        ≤ empMean (fun i => f (x i)) + lam * Real.sqrt (sampleVar (fun i => f (x i)) / n)) :
    Measure.pi (fun _ : Fin n => μ) {x |
        (∫ y, svp x y ∂μ) - (∫ y, fstar y ∂μ)
          > Real.sqrt (32 * variance fstar μ * Real.log (3 * calM F n / δ) / n)
            + 22 * Real.log (3 * calM F n / δ) / ((n : ℝ) - 1)}
      ≤ ENNReal.ofReal δ := by sorry

end EmpiricalBernstein.SVP
Source
Maurer, Pontil, Empirical Bernstein Bounds and Sample Variance Penalization, arXiv:0907.3740v1, Theorem 15, p. 6
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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