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

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

<p>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|&gt; 2 R_n(\mathcal{F}(C))+\sqrt{\frac{2\log\frac{2}{\delta}}{n}}\right]&lt;\delta.$$</p>

<p>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|&gt; 2\sqrt{\frac{2\log\mathbb{S}_{\mathcal{F}(C)}}{n}} +\sqrt{\frac{2\log\frac{2}{\delta}}{n}}\right]&lt;\delta.$$</p>

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

<p>Am I missing something obvious that would invalidate the above reasoning?</p>

<p>[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 <a href="http://www.econ.upf.edu/~lugosi/esaimsurvey.pdf" rel="nofollow">http://www.econ.upf.edu/~lugosi/esaimsurvey.pdf</a></p>

CC BY-SA 3.0
2012-05-30T02:20:27.127Z
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: http://goo.gl/bB1uL
Sasho Nikolov
CC BY-SA 3.0
2012-06-10T18:34:48.990Z
As @SashoNikolov pointed out, this is not a real question, and I have voted to close as such.
Artem Kaznatcheev
CC BY-SA 3.0
2012-09-06T21:13:06.937Z
It would probably be better to directly ask for references in place of checking what you have written is correct.
Kaveh
<reference-request><lg.learning><vc-dimension>
Rademacher Averages, VC shatter coefficient, and eps-approximations
Matteo
# Rademacher Averages, VC shatter coefficient, and eps-approximations

(Asked by: username_0 on 2012-05-29)

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>

**Tags:** reference-request, lg.learning, vc-dimension

> **Comments:**
> **username_1**: username_0, 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: http://goo.gl/bB1uL  
> **username_2**: As @SashoNikolov pointed out, this is not a real question, and I have voted to close as such.  
> **username_3**: It would probably be better to directly ask for references in place of checking what you have written is correct.  

---

## 0 answers

