A hypothesis class $\mathcal{H}$ is Probably Approximately Correct (PAC) learnable with respect to a set $Z:=\mathcal{X}\times \mathcal{Y}$and a loss function $l:\mathcal{H}\times Z\to {\mathbb{R}}_{+}$, if there exists a function $m_{\mathcal{H}}:(0,1{)}^2\to \mathbb{N}$ and a learning algorithm with the following property: For every $ϵ,\delta \in (0,1)$ and for every distribution $\mathcal{D}$ over $Z$, running the learning algorithm on $m>m_{\mathcal{H}}(ϵ,\delta )$ i.i.d. examples generated by $\mathcal{D}$ returns a hypothesis $h\in \mathcal{H}$ such that, with probability of at least $1-\delta$ (over the choice of the $m$ training examples),

where $L_D(h)={\mathbb{E}}_{z\sim D}[l(h,z)]$. The function $m_{\mathcal{H}}$ determines the sample complexity of learning $\mathcal{H}$.

Under a realizability assumption ($\mathrm{\exists }{h}^{\ast }\in \mathcal{H}\text{ s.t. }{L}_{\mathcal{D},f}(h^{\ast })=0$), we can guarantee an absolute level of error instead of just a relative one w.r.t. some minimizer within the hypothesis class. For example, under the realizability assumption, every finite hypothesis class for a binary classification task is PAC learnable ($L_{\mathcal{D}}(h)\le ϵ$ with probability $\ge 1-\delta$) with sample complexity:

Uniform convergence

A sufficient condition for PAC learnability is the uniform convergence condition, which essentially states that a sample training set is large enough that the empirical risks for all hypotheses in $\mathcal{H}$ are good approximations of their true risks. Formally a training set $S$ is said to be $ϵ-$representative if

We say that the hypothesis class has the uniform convergence property (w.r.t. domain $Z$, hypothesis class $\mathcal{H}$, loss function $l$, and distribution $\mathcal{D}$) if there exists a function $m_{\mathcal{H}}^{\text{UC}}:(0,1{)}^2\to \mathbb{N}$ such that for every $ϵ,\delta \in (0,1)$ and for every distribution $\mathcal{D}$ over $Z$, if $S$ is a sample of $m>m_{\mathcal{H}}^{\text{UC}}(ϵ,\delta )$ i.i.d. examples from $\mathcal{D}$, then, with probability of at least $1-\delta$, $S$ is $ϵ-$representative.

If a training set is $\frac{ϵ}{2}-$representative, then any output $h_S$ of ${\text{ERM}}_{\mathcal{H}}(S)$ satisfies $L_{\mathcal{D}}(h_s)\le \underset{h\in \mathcal{H}}{L_{\mathcal{D}}(h)}+ϵ$. This means that if a class $\mathcal{H}$ has the uniform convergence property with a function $m_{\mathcal{H}}^{\text{UC}}$, then the class is PAC learnable with sample complexity $m_{\mathcal{H}}(ϵ,\delta )\le m_{\mathcal{H}}^{\text{UC}}(\frac{ϵ}{2},\delta )$. This can be used to prove that any finite hypothesis class is PAC learnable using the ERM algorithm with sample complexity:

dropping the realizability assumption from above (now for general loss functions).