# (eps,delta)-approx with VC-Dimension 1?

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?

• 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? Jul 6, 2013 at 2:07
• Yes @RobinKothari . Jul 6, 2013 at 8:29
• 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 Jul 6, 2013 at 12:38