Theorem 15 — sample variance penalization has excess risk
ProvedEmpiricalBernstein.SVP.svp_excess_riskLet be a random variable with values in a set and distribution , and let be a class of hypotheses . Fix and , and set
Sample variance penalization selects, from a sample , a hypothesis
Fix . Then with probability at least in the draw of ,
Here , , and are the sample mean and sample variance of , and is the growth function.
Taking optimal, the excess risk of the selected hypothesis is controlled by the variance of an optimal hypothesis: it decays as when some optimal hypothesis has zero variance, whereas empirical risk minimization can be stuck at order .
Formalization Note The selector is any function svp that returns, for every sample, an element of minimizing the penalized objective with the stated ; every minimizer is covered, as the paper's presupposes one exists. No measurability of svp is assumed: the probability of the bad event is its outer measure under . Added hypotheses, making the paper's convention on measurability precise: countable with measurable members, and ( is the real number calM F n). is Mathlib's variance. is as printed.
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.