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$.



1 Answer 1


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.