<p>Converting the comment to an answer: See the notes here: 
cs.cornell.edu/~sridharan/dudley.pdf
with the dependence on $\sup_f \hat E[f^2]$</p>

CC BY-SA 3.0
2015-03-29T17:56:45.797Z
2015-03-29T17:56:45.797Z
Aryeh
<p>One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma:
$$
R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n}
$$
where $\|\cdot\|$ is the Euclidean norm.</p>

<p>Then, using Sauer's Lemma, one can obtain 
$$
R_n(A)\le C\max_{a\in A}\|a\|\sqrt{\frac{V\ln\frac{n}{V}}{n}},$$
where $V$ is the (empirical) VC-dimension.</p>

<p>Using chaining and a bound on covering numbers, one can get rid of the logarithmic factor and obtain
$$
R_n(A)\le C'\sqrt{\frac{V}{n}}.
$$</p>

<p>Looking at the proof that uses chaining, I can't seem to find a way to have $\max_{a\in A}\|a\|$ in the second bound. Is it even possible?</p>

<p>It may not change much in theory, but it does in practice, and (in my opinion), it intuitively makes sense that the bound should depend on it.</p>

CC BY-SA 3.0
2015-03-29T14:25:15.117Z
Clearly, the Rademacher complexity is homogeneous in the dilation constant -- $R_n(cA)=|c|R_n(A)$. The chaining bound you quote holds for bounded vectors, such as those restricted to $\{0,1\}^n$ or $\{-1,1\}^n$. I don't recall off-hand if the most general chainig bound can be stated with an explicit dependence on the $\ell_2$ radius of $A$.
Aryeh
CC BY-SA 3.0
2015-03-29T14:45:49.140Z
Sure enough, see the notes here: http://www.cs.cornell.edu/~sridharan/dudley.pdf with the dependence on $\sup_f\sqrt{\hat{E}[f^2]}$
Aryeh
CC BY-SA 3.0
2015-03-29T16:09:30.270Z
@Aryeh , thank you for the pointers. I was aware of the result about the dilation constant, but the situation is still not perfectly clear to me, so I would be thankful if you could elaborate a bit. I'm working in $\{0,1\}^n$ (edited the question). If I use $c=\max_{a\in A}\|a\|$, now my vectors are no longer in $\{0,1\}^n$, so you seems to be saying that I cannot actually use the chaining bound that I report, but I'm probably misunderstanding.
Matteo
CC BY-SA 3.0
2015-03-29T17:47:27.277Z
I don't understand the phrase "If I use $c=\max_a∥a∥$, now my vectors are no longer in $\{0,1\}^n$. If your vectors live in $\{0,1\}^n$, their $\ell_2$ norm is upper-bounded by $\sqrt n$. If you know more about the structure of your class (such as that the vectors are sparse), you can use that to get tighter VC bounds. Is that what you meant?
Aryeh
CC BY-SA 3.0
2015-03-29T17:52:20.007Z
@Aryeh, I didn't explain myself well, but never mind, I read the proof in the notes you linked and understood what I needed. Thanks a lot again for the help. If you convert your comments to an answer, I can accept it.
Matteo
CC BY-SA 3.0
2015-03-29T17:57:12.373Z
done, cheers! -Aryeh
Aryeh
<machine-learning><pr.probability><lg.learning><vc-dimension>
Bounding Rademacher Averages, with and without chaining
Matteo
# Bounding Rademacher Averages, with and without chaining

(Asked by: username_0 on 2015-03-29)

One can bound the Rademacher average $R\_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma:
$$
R\_n(A)\le \max\_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n}
$$
where $\|\cdot\|$ is the Euclidean norm.

Then, using Sauer's Lemma, one can obtain
$$
R\_n(A)\le C\max\_{a\in A}\|a\|\sqrt{\frac{V\ln\frac{n}{V}}{n}},$$
where $V$ is the (empirical) VC-dimension.

Using chaining and a bound on covering numbers, one can get rid of the logarithmic factor and obtain
$$
R\_n(A)\le C'\sqrt{\frac{V}{n}}.
$$

Looking at the proof that uses chaining, I can't seem to find a way to have $\max\_{a\in A}\|a\|$ in the second bound. Is it even possible?

It may not change much in theory, but it does in practice, and (in my opinion), it intuitively makes sense that the bound should depend on it.

**Tags:** machine-learning, pr.probability, lg.learning, vc-dimension
> **Comments:**
> **username_1**: Clearly, the Rademacher complexity is homogeneous in the dilation constant -- $R_n(cA)=|c|R_n(A)$. The chaining bound you quote holds for bounded vectors, such as those restricted to $\{0,1\}^n$ or $\{-1,1\}^n$. I don't recall off-hand if the most general chainig bound can be stated with an explicit dependence on the $\ell_2$ radius of $A$.  
> **username_1**: Sure enough, see the notes here: http://www.cs.cornell.edu/~sridharan/dudley.pdf with the dependence on $\sup_f\sqrt{\hat{E}[f^2]}$  
> **username_0**: @Aryeh , thank you for the pointers. I was aware of the result about the dilation constant, but the situation is still not perfectly clear to me, so I would be thankful if you could elaborate a bit. I'm working in $\{0,1\}^n$ (edited the question). If I use $c=\max_{a\in A}\|a\|$, now my vectors are no longer in $\{0,1\}^n$, so you seems to be saying that I cannot actually use the chaining bound that I report, but I'm probably misunderstanding.  
> **username_1**: I don't understand the phrase "If I use $c=\max_a∥a∥$, now my vectors are no longer in $\{0,1\}^n$. If your vectors live in $\{0,1\}^n$, their $\ell_2$ norm is upper-bounded by $\sqrt n$. If you know more about the structure of your class (such as that the vectors are sparse), you can use that to get tighter VC bounds. Is that what you meant?  
> **username_0**: @Aryeh, I didn't explain myself well, but never mind, I read the proof in the notes you linked and understood what I needed. Thanks a lot again for the help. If you convert your comments to an answer, I can accept it.  
> **username_1**: done, cheers! -Aryeh  

---

## 1 answers

### Answer by username_1 on 2015-03-29. Score: 1 | Accepted answer

Converting the comment to an answer: See the notes here:
cs.cornell.edu/~sridharan/dudley.pdf
with the dependence on $\sup\_f \hat E[f^2]$


---

