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

<p>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\}$.</p>

<p>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.
$$</p>

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

CC BY-SA 3.0
2014-12-14T01:30:38.383Z
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
CC BY-SA 3.0
2014-12-14T02:18:48.950Z
Hmm ya, actually the symmetrization is unnecessary.
Sasho Nikolov
CC BY-SA 4.0
2021-12-26T06:38:01.647Z
Can't F contain nonlinear functions?
Moon
CC BY-SA 4.0
2022-01-02T15:17:44.283Z
@Moon The class of functions $\mathcal{F}$ is arbitrary, they do not need to be linear. What is meant is that for any $f \in \mathcal{F}$ the function $\sigma \to \sum_{i=1}^m \sigma_i f(x_i)$ is a linear function of $\sigma$. This is true no matter what $f$ is.
Sasho Nikolov
CC BY-SA 4.0
2022-01-21T14:16:43.240Z
Yeah, I got it after I commented, thanks!
Moon
CC BY-SA 3.0
2014-12-14T00:58:31.143Z
2014-12-14T02:22:46.123Z
2014-12-14T02:22:46.123Z
Sasho Nikolov
<p>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. </p>

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

<p>For their definitions, I refer to  <a href="http://www.cc.gatech.edu/~ninamf/ML11/lect1115.pdf" rel="noreferrer">http://www.cc.gatech.edu/~ninamf/ML11/lect1115.pdf</a>. </p>

<machine-learning>
Are (empirical) Rademacher complexity always positive?
Tim
# Are (empirical) Rademacher complexity always positive?

(Asked by: username_0 on 2014-12-13)

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>.

**Tags:** machine-learning

---

## 1 answers

### Answer by username_1 on 2014-12-14. Score: 7

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

> **Comments:**
> **username_0**: 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"?  
> **username_1**: Hmm ya, actually the symmetrization is unnecessary.  
> **username_2**: Can't F contain nonlinear functions?  
> **username_1**: @Moon The class of functions $\mathcal{F}$ is arbitrary, they do not need to be linear. What is meant is that for any $f \in \mathcal{F}$ the function $\sigma \to \sum_{i=1}^m \sigma_i f(x_i)$ is a linear function of $\sigma$. This is true no matter what $f$ is.  
> **username_2**: Yeah, I got it after I commented, thanks!  

---

