Finite-class realizable PAC bound via the elementary union bound
ProvedOptimalPAC.SampleComplexity.finite_class_sample_complexity_boundLet C be a finite concept class and let the distribution be realizable (the labels are generated by some target concept in C). For a sample of m i.i.d. draws, let bad(h) be the event that hypothesis h is consistent with the sample but has true error at least ε. A fixed bad hypothesis survives the sample with probability at most (1-ε)^m. Then the union bound gives P(some bad hypothesis survives) ≤ |C|·(1-ε)^m, and since (1-ε)^m ≤ exp(-ε·m), this is at most δ whenever m ≥ (1/ε)(log |C| + log (1/δ)). In other words, any consistent learner achieves sample complexity M(ε,δ) ≤ (1/ε)(log |C| + log (1/δ)) in the realizable case. This is the elementary finite-class fragment of Hanneke (2016), Theorem 2.
Preamble
import Mathlib
Formal statement
namespace OptimalPAC.SampleComplexity
/-- **Finite-class realizable PAC bound** (elementary union-bound fragment of
Hanneke 2016, Theorem 2): for a finite concept class `C`, model the `m`-sample
as a finite probability space `(Ω, p)` and write `bad h ⊆ Ω` for the event that
hypothesis `h` is consistent with the sample yet has true error at least `ε`.
In the realizable case a fixed bad hypothesis survives `m` i.i.d. draws with
probability at most `(1 - ε)^m`; the union bound over `C` then gives
`p(⋃ bad) ≤ |C|·(1 - ε)^m`, and `(1 - ε)^m ≤ exp(-ε·m)` makes this `≤ δ`
whenever `m ≥ (1/ε)(log |C| + log (1/δ))` — i.e. a consistent learner achieves
`M(ε,δ) ≤ (1/ε)(log |C| + log (1/δ))`. -/
theorem finite_class_sample_complexity_bound
{Ω : Type*} [Fintype Ω] [DecidableEq Ω]
(p : Ω → ℝ)
(hp_nonneg : ∀ ω, 0 ≤ p ω)
(hp_sum : Finset.sum Finset.univ (fun ω => p ω) = 1)
{ι : Type*} [DecidableEq ι]
(C : Finset ι)
(bad : ι → Finset Ω)
(m : ℕ) (ε δ : ℝ)
(hε0 : 0 < ε) (hε1 : ε < 1) (hδ0 : 0 < δ)
(hbad : ∀ h ∈ C, Finset.sum (bad h) (fun ω => p ω) ≤ (1 - ε) ^ m)
(hm : (1 / ε) * (Real.log (C.card : ℝ) + Real.log (1 / δ)) ≤ (m : ℝ)) :
Finset.sum (Finset.biUnion C bad) (fun ω => p ω) ≤ δ := by sorry
end OptimalPAC.SampleComplexity