<p>No, you cannot. See Thm 2.1 of <a href="http://link.springer.com/article/10.1007%2FBF02187833">http://link.springer.com/article/10.1007%2FBF02187833</a> (it says that a random family gives an example, with appropriately chosen parameters).</p>

CC BY-SA 3.0
2013-04-15T01:08:11.407Z
2013-04-15T01:08:11.407Z
domotorp
<p>I have a range space <span class="math-container">$(X,R)$</span>, were <span class="math-container">$R$</span> is a collection of subsets of <span class="math-container">$R$</span> and I have an upper bound <span class="math-container">$d$</span> to the VC-dimension of <span class="math-container">$(X,R)$</span>. Suppose for simplicity that <span class="math-container">$X$</span> is finite. Given <span class="math-container">$\delta\in(0,1)$</span> and an integer <span class="math-container">$m&gt;1$</span>, I know that if I have a random sample <span class="math-container">$S$</span> from X of size <span class="math-container">$|S|=m$</span>, then for <span class="math-container">$\varepsilon=\sqrt{\frac{d+\log(1/\delta)}{m}}$</span>, we have
<span class="math-container">$\Pr\left(\exists r\in R ~:~ \left|\frac{|r|}{|X|}-\frac{|r\cap S|}{|S|}\right|&gt;\varepsilon \right)&lt;\delta$</span>.</p>
<p>Notice how <span class="math-container">$\varepsilon$</span> does not depend on the sizes of the members of <span class="math-container">$R$</span>. I was wondering whether I can get a smaller <span class="math-container">$\varepsilon$</span> if I know that all members of <span class="math-container">$R$</span> have a specific size, or better, if I know that there is a <span class="math-container">$\phi\in(0,1)$</span> such that <span class="math-container">$\frac{|r|}{|X|}=\phi$</span> for all <span class="math-container">$r\in R$</span>.</p>
<p>Thanks.</p>

<lg.learning><vc-dimension><sample-complexity>
VC-Dimension and sample complexity dependent on size of subsets
Matteo
# VC-Dimension and sample complexity dependent on size of subsets

(Asked by: username_0 on 2013-04-15)

I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ and an integer $m>1$, I know that if I have a random sample $S$ from X of size $|S|=m$, then for $\varepsilon=\sqrt{\frac{d+\log(1/\delta)}{m}}$, we have
$\Pr\left(\exists r\in R ~:~ \left|\frac{|r|}{|X|}-\frac{|r\cap S|}{|S|}\right|>\varepsilon \right)<\delta$.

Notice how $\varepsilon$ does not depend on the sizes of the members of $R$. I was wondering whether I can get a smaller $\varepsilon$ if I know that all members of $R$ have a specific size, or better, if I know that there is a $\phi\in(0,1)$ such that $\frac{|r|}{|X|}=\phi$ for all $r\in R$.

Thanks.

**Tags:** lg.learning, vc-dimension, sample-complexity

---

## 1 answers

### Answer by username_1 on 2013-04-15. Score: 6 | Accepted answer

No, you cannot. See Thm 2.1 of <http://link.springer.com/article/10.1007%2FBF02187833> (it says that a random family gives an example, with appropriately chosen parameters).


---

