Realisable PAC-Learnable Hypothesis Class

machine-learning learning-theory

Definition

Realisable PAC-Learnable Hypothesis Class

A hypothesis class is realisable PAC-learnable if there exists a learning algorithm and a sample complexity function such that for any parameters and any distribution satisfying the realisability assumption, the following holds:

provided that the sample size . The produced hypothesis is approximately correct (error ) with a probability of at least (probably).

Empirical Risk Minimisation

A hypothesis class 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 . For infinite classes, learnability is guaranteed if and only if the VC dimension is finite, with the complexity bounded by:

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 be finite, , and assume the realisability assumption, i.e. there exists with . Let be an ERM algorithm and let for .
Here denotes the true risk of under distribution (equivalently when is implicit).

Since , we have for every sample , hence ERM can return a consistent hypothesis and therefore .

Define the bad set

Fix any . Under binary classification with 0-1 loss,

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

Since implies , we obtain

By i.i.d. sampling,

Thus a fixed bad hypothesis is consistent with probability at most .

Now consider the failure event . Because is consistent, failure implies that at least one bad hypothesis is consistent with . Therefore, by the union bound,

To make this at most , it is sufficient that

Hence, for all satisfying this bound,

so finite is realisable PAC-learnable by ERM.