Realisable PAC-Learnable Hypothesis Class

machine-learning learning-theory

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(\epsilon ,\delta )$ such that for any parameters $\epsilon ,\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 \epsilon \right)\ge 1-\delta$$

provided that the sample size $m\ge m(\epsilon ,\delta )$. The produced hypothesis $h_S$ is approximately correct (error $\le \epsilon$) 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_{\mathcal{H}}(\epsilon ,\delta )=\mathcal{O}\left(\frac{d\ln (1/\epsilon )+\ln (1/\delta )}{\epsilon }\right)$$

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

Finite-class realisable PAC guarantee ( ERM)

Let $\mathcal{H}$ be finite, $\mathcal{Y}=\{0,1\}$, and assume the realisability assumption, i.e. there exists $h^{\ast }\in \mathcal{H}$ with $R_P(h^{\ast })=0$. Let $A$ be an ERM algorithm and let $h_S=A(S)$ for $S=\{(x_i,y_i){\}}_{i=1}^m\sim P^m$.
Here $R_P(h)$ denotes the true risk of $h$ under distribution $P$ (equivalently $R(h)$ when $P$ is implicit).

Since $R_P(h^{\ast })=0$, we have $R_S(h^{\ast })=0$ for every sample $S$, hence ERM can return a consistent hypothesis and therefore $R_S(h_S)=0$.

Define the bad set

$${\mathcal{H}}_{\epsilon }:=\{h\in \mathcal{H}:R_P(h)>\epsilon \}.$$

Fix any $h\in {\mathcal{H}}_{\epsilon }$. Under binary classification with 0-1 loss,

$$R_P(h)={\mathbb{E}}_{(x,y)\sim P}[1\{h(x)\ne y\}]=\underset{(x,y)\sim P}{\mathrm{Pr}}(h(x)\ne y),$$

where the second equality uses that the expectation of an indicator equals the probability of its event. Hence

$$\underset{(x,y)\sim P}{\mathrm{Pr}}(h(x)=y)=1-\underset{(x,y)\sim P}{\mathrm{Pr}}(h(x)\ne y)=1-R_P(h).$$

Since $h\in {\mathcal{H}}_{\epsilon }$ implies $R_P(h)>\epsilon$, we obtain

$$\underset{(x,y)\sim P}{\mathrm{Pr}}(h(x)=y)=1-R_P(h)<1-\epsilon .$$

By i.i.d. sampling,

$$\begin{array}{rl}\underset{S\sim P^m}{\mathrm{Pr}}(\forall i\in \{1,\dots ,m\}:h(x_i)=y_i)& =\prod _{i=1}^m\mathrm{Pr}(h(x_i)=y_i)\\ & =(1-R_P(h){)}^m\\ & \le (1-\epsilon {)}^m\\ & \le e^{-\epsilon m}\end{array}$$

Thus a fixed bad hypothesis is consistent with probability at most $e^{-\epsilon m}$.

Now consider the failure event $\{R_P(h_S)>\epsilon \}$. Because $h_S$ is consistent, failure implies that at least one bad hypothesis is consistent with $S$. Therefore, by the union bound,

$$\begin{array}{rl}\underset{S\sim P^m}{\mathrm{Pr}}(R_P(h_S)>\epsilon )& \le \mathrm{Pr}(\exists h\in {\mathcal{H}}_{\epsilon }:R_S(h)=0)\\ & \le \sum _{h\in {\mathcal{H}}_{\epsilon }}\mathrm{Pr}(R_S(h)=0)\\ & \le |{\mathcal{H}}_{\epsilon }|e^{-\epsilon m}\\ & \le |\mathcal{H}|e^{-\epsilon m}.\end{array}$$

To make this at most $\delta$, it is sufficient that

$$|\mathcal{H}|e^{-\epsilon m}\le \delta ⟺m\ge \frac{\ln |\mathcal{H}|+\ln (1/\delta )}{\epsilon }.$$

Hence, for all $m$ satisfying this bound,

$$\underset{S\sim P^m}{\mathrm{Pr}}(R_P(h_S)\le \epsilon )\ge 1-\delta ,$$

so finite $\mathcal{H}$ is realisable PAC-learnable by ERM.