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