I am following these [lecture notes](http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf):

Given the i.i.d. $\mathcal{Z}$-valued random variables $Z\_1,\dotsc,Z\_m$ and $\mathcal{G}$ is a set of bounded functions $g\colon \mathcal{Z}\to[a,b]$.

Corollary 2.3 says:

> 
> With probability at least $1-\delta$, 
>  $$ \sup\_{g\in\mathcal{G}} \left(
>  \mathbb{E}[g(Z)]-\frac{1}{m}\sum\_{i=1}^mg(Z\_i) \right) \leq
>  2\mathfrak{R}\_m(\mathcal{G})+(b-a)\sqrt{\frac{\ln(1/\delta)}{2m}} 
> $$
> 
> 
> 

where $\mathfrak{R}\_m(\mathcal{G})$ is the Rademacher average:

> 
> Let $\epsilon\_1,\dotsc,\epsilon\_m$ be i.i.d. $\{\pm\}$-valued random
>  variables with $\mathbb{P}(\epsilon\_i = +1)=\mathbb{P}(\epsilon\_i =
>  -1)=1/2$. These are also independent of the sample $Z\_1,\dotsc,Z\_m$. Define the *empirical Rademacher average* of $\mathcal{G}$ as
> 
> 
> $$ \hat{\mathfrak{R}}\_m(\mathcal{G}) = \mathbb{E}\left[
>  \sup\_{g\in\mathcal{G}} \frac{1}{m} \sum\_{i=1}^m \epsilon\_i g(Z\_i)
>  \Bigg\vert Z\_1^m \right]. $$
> 
> 
> The *Rademacher average* of $\mathcal{G}$ is defined as
> 
> 
> $$ 
> \mathfrak{R}\_m(\mathcal{G}) = \mathbb{E}\left[
> \hat{\mathfrak{R}}\_m(\mathcal{G}) \right]. 
> $$
> 
> 
> 

From Corollary 2.3 using $\epsilon = 2 \mathfrak{R}\_m(\mathcal{G})+(b-a)\sqrt{\frac{\ln(1/\delta)}{2m}}$ it follows

\begin{align}
\mathbb{P}\left(\sup\_{g\in\mathcal{G}} \left(
 \mathbb{E}[g(Z)]-\frac{1}{m}\sum\_{i=1}^mg(Z\_i) \right) \geq\epsilon\right) 
\leq
\exp\left(-\frac{2m(\epsilon-2\mathfrak{R}\_m(\mathcal{G}))^2}{(b-a)^2} \right)
\quad \quad (1)
\end{align}

---

I try to compare this to [Hoeffding's Inequality](http://en.wikipedia.org/wiki/Hoeffding's_inequality) for real valued random variables.
Therefore assume that $Z\_1,\dotsc,Z\_m$ are real-valued random variables with $\mathbb{P}(Z\_i\in[a,b]) = 1$, and let $g$ be the identity function and $\mathcal{G} = \{g\}$.

Then $(1)$ becomes

\begin{align}
\mathbb{P}\left(
 \mathbb{E}[Z]-\frac{1}{m}\sum\_{i=1}^mZ\_i \geq\epsilon\right) 
\leq
\exp\left(-\frac{2m(\epsilon-2\mathfrak{R}\_m(\mathcal{G}))^2}{(b-a)^2} \right)
\end{align}
which seems to be an improvement over Hoeffding's Inequality whenever $\mathfrak{R}\_m(\mathcal{G}) > \epsilon$.

Is there a way to tell $\mathfrak{R}\_m(\mathcal{G}) \leq \epsilon$ or is this a better bound than the one of Hoeffding?

---

**Edit:**

My question seems to be more fundamental: Let 
$$
S: {Z}^m \mapsto \left\lVert\frac{1}{m}\sum\_{i=1}^mZ\_i - \mathbb{E} \left[\frac{1}{m}\sum\_{i=1}^m Z\_i\right]\right\rVert.
$$
Then $S$ fulfills the bounded difference property with $c = \frac{(b-a)}{m}$ e.g.
$$
\sup\_{Z\_i'\in\mathcal{Z}} | S(Z\_1,\dots,Z\_i,\dots,Z\_m) - S(Z\_1,\dots,Z\_i',\dots,Z\_m) | \leq c
$$
and hence with $v=\frac{mc^2}{4}$
\begin{align}
\mathbb{P}\left(S-\mathbb{E}[S] \geq t \right) \leq \exp\left( -\frac{t^2}{2v} \right)
\end{align}
for $t> 0$. Using $\epsilon = t + \mathbb{E}[S]$ we get
\begin{align}
\mathbb{P}\left(S \geq \epsilon \right) &\leq \exp\left( -\frac{(\epsilon-\mathbb{E}[S])^2}{2v} \right) \\
\mathbb{P}\left(\left\lVert\frac{1}{m}\sum\_{i=1}^mZ\_i - \mathbb{E} \left[\frac{1}{m}\sum\_{i=1}^m Z\_i\right]\right\rVert \geq \epsilon \right) &\leq \exp\left( -\frac{2m(\epsilon-\mathbb{E}[S])^2}{(b-a)^2} \right) 
\end{align}
The Rademacher average was only used to upper bound $\mathbb{E}[S]$ on the RHS.

I again, compare this to [Hoeffding's](http://en.wikipedia.org/wiki/Hoeffding's_inequality) or [Azuma's Inequality](http://en.wikipedia.org/wiki/Azuma%27s_inequality) and wonder which one to use.
Is there anything that can be said about the behaviour of $\mathbb{E}[S]$?