Rademacher average based Hoeffding Inequality

Question

I am following these lecture notes:

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 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 or Azuma's Inequality and wonder which one to use. Is there anything that can be said about the behaviour of $\mathbb{E}[S]$?

Answer 1

It is unclear what your $S$ is; you wrote it as a map defined on a set of $m$-tuples of random variables, and then it is unclear how the expectation of such a map could be defined.

If in fact your $S$ is just the random variable $\sup_{g\in\mathcal{G}} \left( \mathbb{E}[g(Z)]-\frac{1}{m}\sum_{i=1}^mg(Z_i) \right)$, then clearly $$\mathbb{E}S\ge\sup_{g\in\mathcal{G}} \mathbb{E}\left( \mathbb{E}[g(Z)]-\frac{1}{m}\sum_{i=1}^mg(Z_i) \right) =\sup_{g\in\mathcal{G}}0=0.$$ So, $\mathbb{E}S\ge0$, as you seemed to desire.

Answer 2

I am only able to answer my question partially and would be happy if one could check my line of thinking.

$$ S: {Z}^m \mapsto \sup_{g\in\mathcal{G}} \left( \mathbb{E}[g(Z)]-\frac{1}{m}\sum_{i=1}^mg(Z_i) \right). $$ 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 according to the bounded difference inequality it holds that for all $t> 0$ \begin{align} \mathbb{P}\left(S-\mathbb{E}[S] \geq t \right) \leq \exp\left( -\frac{t^2}{2v} \right) \end{align} with $v=\frac{mc^2}{4}$. 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(\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-\mathbb{E}[S])^2}{(b-a)^2} \right) \end{align} So the Rademacher average was used to upper bound $\mathbb{E}[S]$ on the RHS.

Now if $\mathbb{E}[S] \geq \epsilon$ it follows that $\mathbb{E}[S] \geq t+\mathbb{E}[S]$ and hence $t \leq 0$, which is a contradiction to the bounded difference inequality. Hence the inequality only holds for $\mathbb{E}[S] < \epsilon$.

In the same line of argument follows that if $\mathfrak{R}_m(\mathcal{G})$ was used to upper bound $\mathbb{E}[S]$ with the substitution $\epsilon = t + \mathfrak{R}_m(\mathcal{G})$ that the inequality only holds for $\mathfrak{R}_m(\mathcal{G}) < \epsilon$.

It is left to show that $\mathbb{E}[S] \geq 0$.