3
$\begingroup$

I have a domain $X$ and a set system $R$ on $X$, such that the sets in $R$ are one included in the other, that is, for any $A,B\in R$, either $A\subseteq B$ or $B\subseteq A$. The sets are not all equal: there is at least a pair of sets $A,B\in R$ such that $A\subsetneq B$ The VC-dimension for this set is therefore 1.

I seem to recall that the usual random sampling theorem to obtain an $(\varepsilon,\delta)$ approximation of the sizes of all the sets in $R$ can be used only if the range space has VC-dimension at least 2, but now I cannot find this explicitly stated anywhere. Could anyone please tell me whether I am just remembering it wrong and the theorem can be used for range spaces of any VC-dimension?

If not, are there other techniques I can use or do I have to resort to Chernoff+union bounds?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't work in the area, but since no one has responded.. Are you asking about the usual PAC learning setting where elements from X are being sampled according to D, and you are given X and whether it is contained in some A in R, and after some samples you want to determine A up to error epsilon and confidence 1-delta? $\endgroup$ – Robin Kothari Jul 6 '13 at 2:07
  • $\begingroup$ Yes @RobinKothari . $\endgroup$ – Matteo Jul 6 '13 at 8:29
  • 1
    $\begingroup$ Then yes, the standard PAC learning algorithm should work, even for VCdim=1. When I studied PAC learning, VCdim=1 was the first example I saw. This is the original paper that shows the upper bound: dl.acm.org/citation.cfm?id=76371 $\endgroup$ – Robin Kothari Jul 6 '13 at 12:38
0
$\begingroup$

So the answer is yes, as pointed out by in one comment with reference to the original paper.

Improve this answer
$\endgroup$

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.