2
$\begingroup$

In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using PAC-Bayesian techniques to convert the distribution over $X$ into a distribution over hypotheses, which is what I think this paper is doing: http://www0.cs.ucl.ac.uk/staff/G.Lever/pubs/ALTfinal.pdf

Any other methods for making clever use of $P$?

[Edit 25.03.2015: In light of Vitaly's answer, let me sharpen the question. Suppose that I know the sampling distribution only approximately as $Q$. Can we formulate a generalization bound in terms of $D(Q||P)$ or $||P=Q||_{TV}$?]

$\endgroup$
2
$\begingroup$

For specific distribution over $X$ uniform convergence bounds scale linearly with the logarithm of the size of the (smallest) $\epsilon$-cover of the concept class $C$ (the cover can use any functions over $X$). This is proved in "Learnability with respect to fixed distributions" paper of Benedek and Itai. As a result sample complexity of PAC learning scales linearly with this parameter.

$\endgroup$
  • $\begingroup$ Thanks, Vitaly! I actually knew about this paper. I guess I was hoping for something more modern (along the lines of that paper I linked), but the Benedek and Itai in some sense gives an exhaustive answer. $\endgroup$ – Aryeh Mar 24 '15 at 19:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.