I'm trying to prove that any agnostic PAC learnable class $\mathcal{H}$ of binary classifiers is PAC learnable (with respect to the 0-1 loss function), which means that for any density distribution $\mathcal{D}$, $\min_{h \in \mathcal{H} }L_{\mathcal{D}}(h)=0$, but I don't see why that would be the case if $\mathcal{H},\mathcal{D},f$ is not realizable.

If $\mathcal{H}=\{h_{0}\}$ with $h_{0}$ an arbitrary hypothesis, $\mathcal{H}$ should be agnostic learnable because $\forall \epsilon,\delta > 0 \:, m\geq 1, \mathbb{P}\big[L_{\mathcal{D}}(h)<\min_{h' \in \mathcal{H}}(L_{\mathcal{D}}(h'))+\epsilon\big] \geq 1- \delta$, yet it is not PAC learnable.

Can someone point me to the right direction?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.