Theorem 3, p. 4 — if I(Λ_W(S);W) ≤ ε, then n ≥ (8σ²/α²)(ε/β + log(2/β)) gives P[|L_μ(W) − L_S(W)| > α] ≤ β (countable W)
ProvedInfoGen.HighProb.theorem_3Let be a countable hypothesis space, an instance space with a probability measure , and a jointly measurable nonnegative loss such that is -subgaussian under for all :
Let be a learning algorithm that receives , i.i.d. with law , and outputs . Write , , and .
Suppose the algorithm satisfies for some . Then for any and , every sample size with
guarantees
where the probability is taken with respect to the joint distribution .
When is independent of the Chernoff–Hoeffding bound gives the sample size ; the theorem shows that a sample complexity polynomial in and logarithmic in still suffices when depends on , as long as the mutual information between the empirical risks and the output is small. Any algorithm with qualifies, since .
Formalization Note. Three departures from the print, each disclosed. (1) The paper writes "a sample complexity of "; the proof shows that the failure probability exceeding forces below this value, so the statement is posed for every at least this value. (2) The paper asserts its results hold "even when is uncountably infinite" (p. 4). Under the product σ-algebra on this is false: with , uniform, , and the algorithm , each is almost surely, so , while always. Hence is countable with measurable singletons (Russo and Zou's setting). (3) , and joint measurability of are added: a dataset is nonempty (for the displayed condition alone would allow ), a mutual information is nonnegative, and , must be random variables. Mutual information is valued in , and the probability in is compared with .
import Mathlib import Definitions.Def_InfoGen_HighProb_Setting open MeasureTheory ProbabilityTheory InformationTheory LearnStability.Characterization open scoped ENNReal NNReal
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.