Rademacher complexity and empirical Rademacher complexity are used to provide upper bound on the loss of solving an learning problem. That seems to imply that Rademacher complexity and empirical Rademacher complexity can't be negative.

But from their definitions, I can't figure out if they are indeed always nonnegative. So what is the truth? Thanks.

For their definitions, I refer to http://www.cc.gatech.edu/~ninamf/ML11/lect1115.pdf.


Yes, the empirical Rademacher complexity is non-negative, and this follows from Jensen's inequality.

For completeness, the empirical Rademacher complexity $\hat{R}(\mathcal{F}, X)$ given a sample $X = \{x_1, \ldots, x_m\}$ and a class of real-valued functions $\mathcal{F}$ whose domain contains $X$ is $$ \hat{R}(\mathcal{F}, X) := \mathbb{E}_\sigma \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)}, $$ where the expectation is over $m$ independent random variables $\sigma:= (\sigma_1, \ldots, \sigma_m)$ sampled uniformly from $\{-1, 1\}$.

Notice that $\sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)}$ is a convex function of $\sigma$, because it is the supremum of linear functions. Then, by Jensen and linearity of expectation, $$ \mathbb{E}_\sigma \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)} \geq \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\mathbb{E}[\sigma_i] f(x_i)} = 0. $$

The final equality follows because $\mathbb{E}[\sigma_i] = 0$ for all $i$.

  • $\begingroup$ Thanks. About your last,sentence, isn't $E_y F(y) \geq F(E y) = F(0)$ by Jensen'e inequality alone? Why need "the same proof"? $\endgroup$
    – Tim
    Dec 14 '14 at 1:30
  • $\begingroup$ Hmm ya, actually the symmetrization is unnecessary. $\endgroup$ Dec 14 '14 at 2:18

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.