# Rademacher Averages, VC shatter coefficient, and eps-approximations

I am learning about Rademacher averages and their relation to VC-dimension for a project I am working on, but I am not sure I got everything right, so I will recap what I understood below and I would be really thankful if someone can comment and/or correct the following reasoning. It should be fairly easy for someone familiar with these tools. I also need a couple of pointers for the correct original references of some results I'll be using, and possibly pointers to sharper versions if they exist. I assume that most/all what I am saying in the following is common knowledge and it is probably already written somewhere, but I want to be sure (pointers to references are appreciated and encouraged). Thank you in advance.

Let $\mathcal{S}=(X,R)$ be a range space, where $X$ is a set of points in $\Re^d$, and $R$ is a subset of $2^X$ (i.e., a collection of subsets of $X$). I want to build an $\varepsilon$-approximation of $X$, that is, a subset $A$ of $X$ such that, for each $B\in R$, we have $\left|\frac{|B|}{|X|}-\frac{|B\cap A|}{|A|}\right|\le\varepsilon$. It is easy to obtain such a $A$ probabilistically by using random sampling and a classic result from statistical learning theory which involves the VC-dimension of the range space $\mathcal{S}$. Can we build a smaller sample if we can do more than just give a bound (or compute) this quantity? Specifically, consider a set $C=\{x_1,\dotsc,x_n\}$ of $n$ points drawn uniformly at random from $X$. Let $\mathcal{F}(C)$ be the class of $n$-vectors $(\mathbb{1}_D(x_1),\mathbb{1}_D(x_2),\dotsc,\mathbb{1}_D(x_n))$ with $D\in R$. Let $R_n(\mathcal{F}(C))$ be the (conditional? I'm not sure about the correct name) Rademacher average associated with $\mathcal{F}(C)$, i.e., $$R_n(\mathcal{F}(C))=E_\sigma\left[\sup_{a\in\mathcal{F}(C)}\frac{1}{n}\left|\sum_{i=1}^n\sigma_i a_i\right|\right],$$ where the $\sigma_i$'s are independent Rademacher random variables.

Now, according to [1,Thm. 3.2] (modified for our case, and for which I would appreciate a pointer to the original version and if there exists a sharper version), with probability at least $1-\delta$, $$\sup_{D\in R}\left|\frac{|D|}{|X|}-\frac{|D\cap C|}{|C|}\right|\le 2 R_n(\mathcal{F}(C))+\sqrt{\frac{2\log\frac{2}{\delta}}{n}},$$ where the probability is on the choice of $C$. Note that this is equivalent to say that $$\Pr\left[\exists D\in R \mbox{ s.t. } \left|\frac{|D|}{|X|}-\frac{|D\cap C|}{|C|}\right|> 2 R_n(\mathcal{F}(C))+\sqrt{\frac{2\log\frac{2}{\delta}}{n}}\right]<\delta.$$

Also, from [1,Eq. 6], we have that $$R_n(\mathcal{F}(C))\le\sqrt{\frac{2\log\mathbb{S}_{\mathcal{F}(C)}}{n}},$$ where $\mathbb{S}_{\mathcal{F}(C)}$ is the VC shatter coefficient of $\mathcal{F}(C)$", that is the size of the set $\mathcal{F}(C)$. Plugging this result in the previous equation we obtain $$\Pr\left[\exists D\in R \mbox{ s.t. } \left|\frac{|D|}{|X|}-\frac{|D\cap C|}{|C|}\right|> 2\sqrt{\frac{2\log\mathbb{S}_{\mathcal{F}(C)}}{n}} +\sqrt{\frac{2\log\frac{2}{\delta}}{n}}\right]<\delta.$$

In the case I have at hand, it is very easy to give an upper bound $\mathbb{U}$ to $\mathbb{S}_{\mathcal{F}(C)}$ independent from $C$. It is also easy, given $C$ to directly compute the shatter coefficient $\mathbb{S}_{\mathcal{F}(C)}$. Therefore, fixed $\varepsilon$, it is possible to compute how many points to sample at random from $X$ to obtain an $\varepsilon$-approximation of $X$ with probability at least $1-\delta$ by setting $$2\sqrt{\frac{2\log\mathbb{U}}{n}} +\sqrt{\frac{2\log\frac{2}{\delta}}{n}} = \varepsilon$$ and solving for $n$. Alternatively, fixed $n$ and extracted a sample $C$ from $X$ of size $n$, I can compute $\phi=2\sqrt{\frac{2\log\mathbb{S}_{\mathcal{F}(C)}}{n}} +\sqrt{\frac{2\log\frac{2}{\delta}}{n}}$ and say that $C$ is a $\phi$-approximation of $X$ with probability at least $1-\delta$.

Am I missing something obvious that would invalidate the above reasoning?

[1] S. Boucheron, O. Bousquet, and G. Lugosi, (2005), Theory of Classification: a Survey of Recent Advances. ESAIM: Probability and Statistics, 9: 323--375. Available from http://www.econ.upf.edu/~lugosi/esaimsurvey.pdf

• Matteo, there is no question here: "here is what I think I know, is it ok?" is not usually considered the most productive way of using this site. Besides that, [1] has many references. Finally, the use of Rademacher averages strikes me as just a way of bounding the (hereditary) red-blue discrepancy of $R$. See the transference lemma (prop. 1.8) in the book by Matousek for the connection between discrepancy and $\epsilon$-nets: goo.gl/bB1uL – Sasho Nikolov May 30 '12 at 2:20
• As @SashoNikolov pointed out, this is not a real question, and I have voted to close as such. – Artem Kaznatcheev Jun 10 '12 at 18:34
• It would probably be better to directly ask for references in place of checking what you have written is correct. – Kaveh Sep 6 '12 at 21:13