Realisable PAC-Learnable Hypothesis Class

machine-learning learning-theory statistics

Definition

Realisable PAC-Learnable Hypothesis Class

A hypothesis class $\mathcal{H}$ is realisable PAC-learnable if there exists a learning algorithm $A$ and a sample complexity function $m(ϵ,\delta )$ such that for any parameters $ϵ,\delta \in (0,1)$ and any distribution $P$ satisfying the realisability assumption, the following holds:

${\mathrm{Pr}}_{S\sim P^m}\left(R_P(A(S))\le ϵ\right)\ge 1-\delta$

provided that the sample size $m\ge m(ϵ,\delta )$. The produced hypothesis $h_S$ is approximately correct (error $\le ϵ$) with a probability of at least $1-\delta$ (probably).

Empirical Risk Minimisation

A hypothesis class $\mathcal{H}$ is realisable PAC-learnable by any ERM algorithm provided that the functional capacity of the class is bounded. For finite classes, the sample complexity scales with the logarithm of the cardinality $|\mathcal{H}|$. For infinite classes, learnability is guaranteed if and only if the VC dimension $d$ is finite, with the complexity bounded by:

$m(ϵ,\delta )\le \mathcal{O}\left(\frac{d\ln (1/ϵ)+\ln (1/\delta )}{ϵ}\right)$

This result establishes that the complexity of the functional space is the fundamental constraint on the amount of data required to ensure generalisation.