PAC Learnability

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: