Theorem 1, p. 4 — if ℓ(w, Z) is σ-subgaussian for every w, then |gen(μ, P_{W|S})| ≤ √(2σ² I(S;W)/n)
ProvedInfoGen.Expected.theorem_1This is the main theorem of Xu and Raginsky: the expected generalization error of a learning algorithm is bounded by the mutual information between its input and its output.
Let be an instance space, a hypothesis space and a nonnegative, jointly measurable loss. Let be a probability measure on , , and an i.i.d. sample. A learning algorithm is a Markov kernel from to ; the pair has law . With and , the expected generalization error is , and is the input–output mutual information.
Suppose that is -subgaussian under for all , that is, for all , and that . Then
The less the output hypothesis reveals about the training data, the smaller the expected gap between population and empirical risk. The bound places no restriction on the size of and allows unbounded losses, provided they are subgaussian; a loss with values in is -subgaussian for every .
Formalization Note Subgaussianity is Mathlib's HasSubgaussianMGF of the centred loss with variance proxy (the square of the paper's ). The mutual information lives in ; the hypothesis is added because Lean's conversion of to a real number gives , which would turn the page's vacuous bound into a false one. Also added, as implicit on the page: (the bound divides by ) and joint measurability of (so that and are random variables). The nonnegativity of is the page's own assumption. The generalization error integrates the pointwise difference ; no integrability hypothesis is assumed.
import Mathlib import Definitions.Def_InfoGen_Expected_Setting open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal NNReal
namespace InfoGen.Expected
open LearnStability.Characterization
/-- Theorem 1 (Xu & Raginsky, arXiv:1705.07809v2, p. 4, eq. (10)). Let `S` be an i.i.d. sample of
size `n ≥ 1` from `μ` and `W` the output of the learning algorithm `κ = P_{W|S}`. If `ℓ(w, Z)` is
`σ`-subgaussian under `μ` for every hypothesis `w` and `I(S; W) < ∞`, then
`|gen(μ, P_{W|S})| ≤ √((2σ²/n) I(S; W))`. -/
theorem theorem_1 {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)
(κ : Kernel (Fin n → Z) W) [IsMarkovKernel κ]
(σ : ℝ≥0) (hσ : ∀ w, HasSubgaussianMGF (fun z => ℓ w z - risk ℓ μ w) (σ ^ 2) μ)
(hI : mutualInfo (sampleLaw μ n ⊗ₘ κ) ≠ ⊤) :
|genError ℓ μ κ|
≤ Real.sqrt (2 * (σ : ℝ) ^ 2 / n * (mutualInfo (sampleLaw μ n ⊗ₘ κ)).toReal) := by sorry
end InfoGen.Expected
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.