0
$\begingroup$

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?

$\endgroup$

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.