Fundamental Theorem of PAC Learning

SSU

Theorem: For a hypothesis class $\mathcal{H}\subset \{-1,+1{\}}^{\mathcal{X}}$:

The following are equivalent:

1. Uniform Law of Large Numbers (ULLN) holds for $\mathcal{H}$
2. ERM is a successful PAC learner for $\mathcal{H}$
3. $\mathcal{H}$ has finite VC dimension $d_{\text{VC}}(\mathcal{H})<\infty$

Sample complexity bound:

$$m_{\text{H, PAC}}(ϵ,\delta )\le C\frac{d_{\text{VC}}+\log (1/\delta )}{{ϵ}^2}$$