Theorem 5.4, p. 21 — uniform empirical small-ball estimate on the L₂ unit sphere
ProvedLearnNoConc.ERM.theorem_5_4Let be a probability space and let be a class of measurable functions on the unit sphere of ( for every ). Let () be i.i.d. with law and independent random signs. Suppose that satisfies , where , and that
Then, with probability at least ,
This is the uniform lower estimate that drives the proof of Theorem 3.1: under a small-ball condition, every function of the class is large on a proportional number of sample points, without any concentration assumption.
Formalization Note The conclusion is stated as: the (outer) probability that some has fewer than indices with is at most . The expectation of the supremum is taken in . Measurability of every , membership in , and pointwise separability of (a countable subclass approximating every element pointwise and in ) are added; the last stands in for the measurability of suprema that the paper takes for granted.
import Mathlib import Definitions.Def_LearnNoConc_ERM_Setting
namespace LearnNoConc.ERM
open MeasureTheory
open scoped ENNReal
/-- Theorem 5.4, p. 21: the uniform empirical small-ball estimate on the `L₂(μ)` unit sphere. -/
theorem theorem_5_4 {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(H : Set (Ω → ℝ)) (hHm : ∀ h ∈ H, Measurable h) (hH2 : ∀ h ∈ H, MemLp h 2 μ)
(hS : ∀ h ∈ H, eLpNorm h 2 μ = 1) (hHsep : PointwiseSeparable μ H)
(N : ℕ) (hN : 0 < N) (τ : ℝ) (hτ : 0 < τ) (hQ : 0 < Q μ H (2 * τ))
(hE : radSup μ H N ≤ ENNReal.ofReal (τ * Q μ H (2 * τ) / 16)) :
(Measure.pi fun _ : Fin N => μ)
{x | ∃ h ∈ H, ((Finset.univ.filter fun i => τ ≤ |h (x i)|).card : ℝ)
< N * Q μ H (2 * τ) / 4}
≤ ENNReal.ofReal (2 * Real.exp (-(N * Q μ H (2 * τ) ^ 2 / 2))) := by sorry
end LearnNoConc.ERM
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.