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

CC BY-SA 4.0
2021-01-14T20:47:59.967Z
2021-01-14T20:47:59.967Z
Matteo
<p>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. </p>

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

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

CC BY-SA 3.0
2013-07-06T02:07:41.123Z
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?
Robin Kothari
CC BY-SA 3.0
2013-07-06T08:29:48.783Z
Yes @RobinKothari .
Matteo
CC BY-SA 3.0
2013-07-06T12:38:29.857Z
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: http://dl.acm.org/citation.cfm?id=76371
Robin Kothari
<cg.comp-geom><lg.learning><vc-dimension>
(eps,delta)-approx with VC-Dimension 1?
Matteo
# (eps,delta)-approx with VC-Dimension 1?

(Asked by: username_0 on 2013-07-05)

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?

**Tags:** cg.comp-geom, lg.learning, vc-dimension
> **Comments:**
> **username_1**: 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?  
> **username_0**: Yes @RobinKothari .  
> **username_1**: 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: http://dl.acm.org/citation.cfm?id=76371  

---

## 1 answers

### Answer by username_0 on 2021-01-14. Score: 0 | Accepted answer

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


---

