<p>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. </p>

CC BY-SA 3.0
2015-03-24T19:18:31.273Z
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.
Aryeh
CC BY-SA 3.0
2015-03-24T18:10:28.900Z
2015-03-24T18:10:28.900Z
Vitaly
<p>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:
<a href="http://www0.cs.ucl.ac.uk/staff/G.Lever/pubs/ALTfinal.pdf" rel="nofollow">http://www0.cs.ucl.ac.uk/staff/G.Lever/pubs/ALTfinal.pdf</a></p>

<p>Any other methods for making clever use of $P$?</p>

<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}$?]</p>

<machine-learning><lg.learning>
How to exploit knowledge of the sampling distribution for better generalization bounds?
Aryeh
# How to exploit knowledge of the sampling distribution for better generalization bounds?

(Asked by: username_0 on 2015-03-24)

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 username_1'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}$?]

**Tags:** machine-learning, lg.learning


---

## 1 answers

### Answer by username_1 on 2015-03-24. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, username_1! 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.  

---

