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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Aryeh Mar 29 '15 at 14:25
  • 1
    $\begingroup$ Sure enough, see the notes here: cs.cornell.edu/~sridharan/dudley.pdf with the dependence on $\sup_f\sqrt{\hat{E}[f^2]}$ $\endgroup$ – Aryeh Mar 29 '15 at 14:45
  • $\begingroup$ @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. $\endgroup$ – Matteo Mar 29 '15 at 16:09
  • 1
    $\begingroup$ 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? $\endgroup$ – Aryeh Mar 29 '15 at 17:47
  • $\begingroup$ @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. $\endgroup$ – Matteo Mar 29 '15 at 17:52

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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