§3.2, p. 4 — if ℓ(w,Z) is σ-subgaussian for every w, then each empirical risk L_S(w) is σ/√n-subgaussian under μ^{⊗n}
ProvedInfoGen.Expected.empRisk_subgaussianLet be an instance space, a hypothesis space, a nonnegative, jointly measurable loss, and a probability measure on . Let and let be an i.i.d. sample. Write for the population risk and for the empirical risk.
Suppose that for every the random variable , , is -subgaussian: for all . Then for every the empirical risk is -subgaussian under :
This is the first half of the step that connects Lemma 1 to the learning problem: with , each section inherits subgaussianity from the loss, with the variance proxy reduced by the factor because of the i.i.d. sample.
Formalization Note Subgaussianity is Mathlib's HasSubgaussianMGF of the centred variable, whose parameter is the variance proxy: for the loss, for the empirical risk. Joint measurability of and are added (the page assumes both implicitly). The page's nonnegativity of is kept as a hypothesis although it plays no role.
import Mathlib import Definitions.Def_InfoGen_Expected_Setting open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal NNReal
namespace InfoGen.Expected
open LearnStability.Characterization
/-- §3.2, p. 4, first clause (Xu & Raginsky, arXiv:1705.07809v2). If `ℓ(w, Z)` is
`σ`-subgaussian under `μ` for every hypothesis `w`, then for every `w` the empirical risk
`L_S(w) = f(S, w)` of an i.i.d. sample `S ∼ μ^{⊗n}` is `σ/√n`-subgaussian: its centred version
`L_S(w) − L_μ(w)` has variance proxy `σ²/n`. -/
theorem empRisk_subgaussian {Z W : Type*} [MeasurableSpace Z] [MeasurableSpace W]
(μ : Measure Z) [IsProbabilityMeasure μ] (n : ℕ) (hn : 0 < n)
(ℓ : W → Z → ℝ) (hℓ : Measurable (Function.uncurry ℓ)) (hℓ0 : ∀ w z, 0 ≤ ℓ w z)
(σ : ℝ≥0) (hσ : ∀ w, HasSubgaussianMGF (fun z => ℓ w z - risk ℓ μ w) (σ ^ 2) μ) :
∀ w, HasSubgaussianMGF (fun s => empRisk ℓ s w - risk ℓ μ w) (σ ^ 2 / n)
(sampleLaw μ n) := by sorry
end InfoGen.Expected
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.