6
$\begingroup$

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]$?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.