Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, p. 4 — if I(Λ_W(S);W) ≤ ε, then n ≥ (8σ²/α²)(ε/β + log(2/β)) gives P[|L_μ(W) − L_S(W)| > α] ≤ β (countable W)

Proved
InfoGen.HighProb.theorem_3

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

generalization-errorinformation-theoretic-generalizationmutual-informationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexitysubgaussian

Let W\mathsf WW be a countable hypothesis space, Z\mathsf ZZ an instance space with a probability measure μ\muμ, and ℓ:W×Z→R+\ell:\mathsf W\times\mathsf Z\to\mathbb R_+ℓ:W×Z→R+​ a jointly measurable nonnegative loss such that ℓ(w,Z)\ell(w,Z)ℓ(w,Z) is σ\sigmaσ-subgaussian under μ\muμ for all w∈Ww\in\mathsf Ww∈W:

log⁡E[eλ(ℓ(w,Z)−Lμ(w))]≤λ2σ22for all λ∈R.\log\mathbb E\big[e^{\lambda(\ell(w,Z) - L_\mu(w))}\big] \le \frac{\lambda^2\sigma^2}{2}\quad\text{for all }\lambda\in\mathbb R .logE[eλ(ℓ(w,Z)−Lμ​(w))]≤2λ2σ2​for all λ∈R.

Let PW∣SP_{W|S}PW∣S​ be a learning algorithm that receives S=(Z1,…,Zn)S = (Z_1,\dots,Z_n)S=(Z1​,…,Zn​), i.i.d. with law μ\muμ, and outputs W∈WW\in\mathsf WW∈W. Write Lμ(w)=E[ℓ(w,Z)]L_\mu(w) = \mathbb E[\ell(w,Z)]Lμ​(w)=E[ℓ(w,Z)], LS(w)=1n∑i=1nℓ(w,Zi)L_S(w) = \frac1n\sum_{i=1}^n \ell(w,Z_i)LS​(w)=n1​∑i=1n​ℓ(w,Zi​), and ΛW(S)=(LS(w))w∈W\Lambda_{\mathsf W}(S) = (L_S(w))_{w\in\mathsf W}ΛW​(S)=(LS​(w))w∈W​.

Suppose the algorithm satisfies I(ΛW(S);W)≤εI(\Lambda_{\mathsf W}(S);W)\le\varepsilonI(ΛW​(S);W)≤ε for some ε≥0\varepsilon\ge0ε≥0. Then for any α>0\alpha>0α>0 and 0<β≤10<\beta\le10<β≤1, every sample size n≥1n\ge1n≥1 with

n≥8σ2α2(εβ+log⁡2β)n \ge \frac{8\sigma^2}{\alpha^2}\Big(\frac{\varepsilon}{\beta} + \log\frac{2}{\beta}\Big)n≥α28σ2​(βε​+logβ2​)

guarantees

P[ ∣Lμ(W)−LS(W)∣>α ]≤β,\mathbb P\big[\,|L_\mu(W) - L_S(W)| > \alpha\,\big] \le \beta,P[∣Lμ​(W)−LS​(W)∣>α]≤β,

where the probability is taken with respect to the joint distribution PS,W=μ⊗n⊗PW∣SP_{S,W} = \mu^{\otimes n}\otimes P_{W|S}PS,W​=μ⊗n⊗PW∣S​.

When WWW is independent of SSS the Chernoff–Hoeffding bound gives the sample size 2σ2α2log⁡2β\frac{2\sigma^2}{\alpha^2}\log\frac2\betaα22σ2​logβ2​; the theorem shows that a sample complexity polynomial in 1/α1/\alpha1/α and logarithmic in 1/β1/\beta1/β still suffices when WWW depends on SSS, as long as the mutual information between the empirical risks and the output is small. Any algorithm with I(S;W)≤εI(S;W)\le\varepsilonI(S;W)≤ε qualifies, since I(ΛW(S);W)≤I(S;W)I(\Lambda_{\mathsf W}(S);W)\le I(S;W)I(ΛW​(S);W)≤I(S;W).

Formalization Note. Three departures from the print, each disclosed. (1) The paper writes "a sample complexity of n=8σ2α2(εβ+log⁡2β)n = \frac{8\sigma^2}{\alpha^2}(\frac{\varepsilon}{\beta} + \log\frac{2}{\beta})n=α28σ2​(βε​+logβ2​)"; the proof shows that the failure probability exceeding β\betaβ forces nnn below this value, so the statement is posed for every nnn at least this value. (2) The paper asserts its results hold "even when W\mathsf WW is uncountably infinite" (p. 4). Under the product σ-algebra on RW\mathbb R^{\mathsf W}RW this is false: with Z=[0,1]\mathsf Z = [0,1]Z=[0,1], μ\muμ uniform, W=[0,1]n\mathsf W = [0,1]^nW=[0,1]n, ℓ(w,z)=1{z∈{w1,…,wn}}\ell(w,z) = \mathbf 1\{z\in\{w_1,\dots,w_n\}\}ℓ(w,z)=1{z∈{w1​,…,wn​}} and the algorithm W=SW = SW=S, each LS(w)L_S(w)LS​(w) is 000 almost surely, so I(ΛW(S);W)=0I(\Lambda_{\mathsf W}(S);W) = 0I(ΛW​(S);W)=0, while ∣Lμ(W)−LS(W)∣=1|L_\mu(W) - L_S(W)| = 1∣Lμ​(W)−LS​(W)∣=1 always. Hence W\mathsf WW is countable with measurable singletons (Russo and Zou's setting). (3) n≥1n\ge1n≥1, ε≥0\varepsilon\ge0ε≥0 and joint measurability of ℓ\ellℓ are added: a dataset is nonempty (for σ=0\sigma = 0σ=0 the displayed condition alone would allow n=0n = 0n=0), a mutual information is nonnegative, and Lμ(W)L_\mu(W)Lμ​(W), LS(W)L_S(W)LS​(W) must be random variables. Mutual information is valued in [0,∞][0,\infty][0,∞], and the probability in [0,∞][0,\infty][0,∞] is compared with β\betaβ.

Preamble
import Mathlib
import Definitions.Def_InfoGen_HighProb_Setting

open MeasureTheory ProbabilityTheory InformationTheory LearnStability.Characterization
open scoped ENNReal NNReal
Formal statement
namespace InfoGen.HighProb

theorem theorem_3 {Z W : Type*} [MeasurableSpace Z] [MeasurableSpace W]
    [Countable W] [MeasurableSingletonClass W]
    (μ : Measure Z) [IsProbabilityMeasure μ] (n : ℕ) (hn0 : 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) μ)
    (ε : ℝ) (hε0 : 0 ≤ ε) (hε : lambdaInfo ℓ μ κ ≤ ENNReal.ofReal ε)
    (α β : ℝ) (hα : 0 < α) (hβ0 : 0 < β) (hβ1 : β ≤ 1)
    (hn : 8 * (σ : ℝ) ^ 2 / α ^ 2 * (ε / β + Real.log (2 / β)) ≤ n) :
    (sampleLaw μ n ⊗ₘ κ) {p | α < |risk ℓ μ p.2 - empRisk ℓ p.1 p.2|} ≤
      ENNReal.ofReal β := by sorry

end InfoGen.HighProb
Source
Xu & Raginsky, arXiv:1705.07809v2, Theorem 3, eqs. (15)–(16), p. 4; proof App. B, pp. 11–12
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

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