For a given hypothesis space $H$, assuming $f\in H$ where $f$ is the true classifier, you can choose a group $S~D$ where $D$ is a distribution, with a large enough sample complexity, such that the true error over $D$ is in the margin of $\pm \epsilon$ for all hypotheses $h\in H$ with a given probability.

I need to decide if this statement is true or false. On the one hand, if I choose $VCdim(H)=\infty$, than the statement is false since there is no finite number of examples sufficient to satisfy the PAC bound. on the other hand, having $f\in H$ where $f$ is the true classifier means that $H$ is PAC learnable, thus satisfies the statement, means the statement is true.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.