2
$\begingroup$

I am learning the Rademacher complexity and have a question on the definition of it. Let $\mathcal{H}$ be a hypothesis class and $m$ is the number of iid samples from a distribution $\mathcal{D}$, say, $S=\{x_i\}_{i=1}^m$. Then the Rademacher complexity is defined to be $$ R_s(\mathcal{H}) := \mathbb{E}_{\sigma} \sup_{h \in \mathcal{H}} \frac{1}{m}\left|\sum_{i=1}^m \sigma_i \ell(h,x_i) \right|, $$ where $\sigma_i$'s are iid uniform on $\{-1, 1\}$. It seems that the more appropreate definition should be $$ \tilde{R}_s(\mathcal{H}) := \mathbb{E}_{\sigma} \sup_{h \in \mathcal{H}}\left| \frac{1}{|S_+|}\sum_{i \in S_+} \ell(h,x_i) - \frac{1}{|S_-|}\sum_{i \in S_-} \ell(h,x_i)\right|, $$ where $S_+ = \{i \in [m] | \sigma_i = 1\}$ and $S_+ = \{i \in [m] | \sigma_i = -1\}$. This is because the cross-validation should take the normalization constants into account. But I am not sure why the definition does not reflect the normalization constants.

Any comments/suggestions/answers will be very appreciated.

$\endgroup$
1
$\begingroup$

The Rademacher complexity is not directly related to the cross-validation . If you want an intuitive explanation for RC think of it as the degree in which a family of functions can fit purely random noise .

$\endgroup$
  • $\begingroup$ Thanks for your answer. I am not sure why we want to fit purely random noise and why it is related to the genearlization. I thought we are looking for a quantity which can measure the genearlization. $\endgroup$ – induction601 Mar 26 at 17:19
  • 1
    $\begingroup$ We don't want to fit random noise . The idea is that if we look at two families of functions , the one that can fit better random noise is richer , "more complex" . Think about two extremities : first a hypothesis class with only one function and second the set of all functions defined on the domain with values in $\{,1\}. The first class has $R_{S} = 0$ and the second 1 (assume a suitable loss function) , .The first is as simple as we can get and the second is the most complex possible . $\endgroup$ – Popescu Claudiu Mar 26 at 18:14
  • 1
    $\begingroup$ RC is mearly a convenient theoretical measure of complexity that can be computed or estimated for important sets of functions . Regarding the generalisation , as with any other measure of complexity, a lower RC is better . $\endgroup$ – Popescu Claudiu Mar 26 at 18:14

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.