# Are (empirical) Rademacher complexity always positive?

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.

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$.
• 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"? – Tim Dec 14 '14 at 1:30