5
$\begingroup$

A random variable $X$ is sub-Gaussian if there exists a $b>0$ such that for all $t \in \mathbb{R}$ we have $$\mathbb{E}(\exp(tX)) \leq \exp(b^2t^2/2).$$ According to some sources online such as here we have that $\mathbb{E}(X)=0$ (see proposition 2.1). Another source (see definition 1.2) defines random variables as sub Gaussian if it satisfies the above equation and that $\mathbb{E}(X)=0$.

I've been reading into a variant of the multi armed bandit problem recently called rotting bandits. The latest version of the preprint is here, where the authors state:

When arm $i$ is pulled for the $n^{th}$ time, the agent receives a time-independent, $σ^2$ sub-Gaussian random reward, $r_t$, with mean $\mu_i(n).$

Another paper on the more general problem of Multi-Armed Bandits with Non-Stationary Rewards references the previously linked paper saying the authors analyze

the setting where the rewards are $\sigma^2$ sub-Gaussian rewards with mean $\mu_i^c+t^{-\theta_i^*}$ at time $t$ for $\theta_i^* \in \Theta=\{\theta_1\,\theta_2,\ldots\}.$

My confusion here is that the reward in the rotting bandit scenario are sub-Gaussian with potentially non-zero means, contradiction my linked reading into sub-Gaussian distributions. Can anyone identify where I have made a mistake here?

Note: I'm aware Arxiv is not a peer-reviewed platform however the authors come from reputable institutions.

$\endgroup$
  • 2
    $\begingroup$ I suppose it's just a matter of translating the variable by adding or subtracting a constant $\mu$. The definitions you give initially only want to treat standardized variables for convenience. But I don't see the problem to consider variables that would have a non-zero mean. $\endgroup$ – Raskolnikov Nov 9 '17 at 18:52
  • $\begingroup$ @Raskolnikov After reading the papers some more I think you're right. Am I correct in thinking that formally if a random variable is sub-Gaussian it has zero mean and that the bandit papers are actually suggesting the reward is the sum of some random variable (which defines the mean) plus a sub-Gaussian? I just feel like the bandit papers are abusing the definition a bit by calling the shifted sub-Gaussian a sub-Gaussian. I come from more of a math/computer-science background so I'm not sure if this is common in statistics. $\endgroup$ – HBeel Nov 9 '17 at 21:41
5
$\begingroup$

It is standard in the bandit literature to abuse notation by considering a random variable $X$ to be $\sigma$-subgaussian if the noise $X - \mathbb{E}[X]$ is $\sigma$-subgaussian.

See the note on page 78 of Tor Lattimore and Csaba Szepesvari's book

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

The first comment on this question is incorrect strictly speaking; the proposition you link to shows that having zero mean is a necessary condition for being sub-Gaussian.

In some sense, you can still get a useful notion for non-centered random variables to be sub-Gaussian, but only if you change the definition.

If you look at one of the other sources you linked to, if you look at the "converse proposition", which shows that the tail bounds imply the MGF bound up to a multiplicative constant in the exponent, you will see that the assumption that $\mathbb{E}Y=0$ is used implicitly. (It appears to be a typo that Lemma 1.5 omits the assumption in its statement, but it is clearly used in the proof, and when my professor assigned it as a homework assignment, he specifically made sure to add the assumption to the problem.) In order for this Taylor expansion of the MGF to be correct: $$\mathbb{E}e^{\lambda Y} = 1 + \sum\limits_{k=2}^{\infty} \frac{\lambda^k \mathbb{E}Y^k}{k!} \,, $$ for all $\lambda \in \mathbb{R}$, we need that $\mathbb{E}Y=0$. Admittedly the assumption does not appear to be used in an essential way in that lemma, since we can still bound $\mathbb{E}Y$ by $\mathbb{E}|Y| \le \sigma \sqrt{2\pi}$, and this doesn't appear large enough to prevent the upper bounds user later in the proof from working.

To show more convincingly that the definition of sub-Gaussian as stated just doesn't work when $\mathbb{E}Y\not=0$, let's try to show that if $\mathbb{E}Y \not=0$ and $Y \in SG(\sigma^2)$, then $(Y - \mathbb{E}Y) \in SG(\sigma^2)$, which we would need to be true for it to be the case that , for any mean-zero sub-Gaussian $X$, $X+b$ is also sub-Gaussian for any constant $b \not=0$. The proof founders on an irresolvable problem.

Now we definitionally have that $(Y - \mathbb{E}Y) \in SG(\sigma^2) \iff \forall \lambda \in \mathbb{R}, \mathbb{E}e^{\lambda(Y-\mathbb{E})} \le \exp(\frac{1}{2} \sigma^2 \lambda^2)$.

Before going any further, let's just note that we shouldn't expect this to work out well. $\exp(\frac{1}{2} \sigma^2 \lambda^2)$ is the MGF bound for a Gaussian centered at 0. So even if we had a "sub-Gaussian" random variable $Y$ which wasn't centered at $0$, we still wouldn't expect it to satisfy this MGF bound (thus it couldn't satisfy the conventional definition of sub-Gaussian), we would expect it to an MGF bound corresponding to $\mathscr{N}(\mathbb{E}Y, \sigma^2)$, which is different than the one above, for $\mathscr{N}(0,\sigma^2)$.

Anyway, $$\mathbb{E}e^{\lambda(Y - \mathbb{E}Y)} = e^{-\lambda \mathbb{E}Y} \mathbb{E}e^{\lambda Y} \le e^{-\lambda \mathbb{E}Y} e^{\frac{1}{2}\lambda^2 \sigma^2} = \exp\left( \frac{1}{2}\lambda^2\left(\sigma^2 - \frac{2 \mathbb{E}Y}{\lambda}\right) \right)\,.$$ So if we want to show that this is sub-Gaussian, there needs to exists a constant $\tau >0$, such that for all $\lambda \in \mathbb{R}$, one has $$ \tau^2 \ge \sigma^2 - \frac{2 \mathbb{E}Y}{\lambda} \,,$$ which is clearly impossible, since as one "ranges over" all possible values of $\lambda \in \mathbb{R}$, $-\frac{1}{\lambda}$ is a function of $\lambda$ which is unbounded from above.

Note also that the tail bound definitions are in terms of $t \ge 0$, i.e. they implicitly assume/require that the random variable is centered around $0$, i.e. has zero expectation. Thus heuristically we should also expect the tail bound definitions to fail when $\mathbb{E}Y \not=0$, or at least become very messy.

One consequence of the tail bound definition is that $\mathbb{P}(|Y| > t) \le \exp\left( \frac{-t^2}{2\sigma^2} \right)$ for all $t \ge 0$. If $Y - \mathbb{E}Y$ is also to be sub-Gaussian, then we would need that $$\mathbb{P}(|Y - \mathbb{E}Y| > t) \le \exp\left( \frac{-t^2}{2\sigma^2} \right) \quad \text{for all }t \ge 0 \,. $$

Now the event $\{ | Y - \mathbb{E}Y| > t\}$ is equal to the event $$ \{ Y > t + \mathbb{E}Y \} \cup \{ Y < -(t - \mathbb{E}Y) \} \,. $$ Even if it is possible for the required bound on the probability of these events, for all $t \ge 0$, to hold if $Y$ were sub-Gaussian but $\mathbb{E}Y \not=0$ (I'm not sure how to prove or disprove that it is or isn't though - intuitively, since the events aren't centered at $0$, but range over all possible values of $t \ge 0$, conceivably we might get two contradictory bounds from two different values of $t$), the fact that it holds would not follow from the assumption that $Y$ was sub-Gaussian. This also means (or at least suggests) that in general we cannot conclude that translates of sub-Gaussian random variables will still be sub-Gaussian.

This is all perhaps somewhat disingenuous though, since even to the extent that any of it is true, I have yet to acknowledge how these arguments all suggest the same way to generalize the definition of sub-Gaussian. Namely, I claim that the following three definitions are equivalent:

  • $Y$ is sub-Gaussian sensu lato if and only if $(Y - \mathbb{E}Y)$ is sub-Gaussian sensu stricto.
  • $Y$ is sub-Gaussian sensu lato if and only if its moment generating function is bounded by the moment generating function of $\mathscr{N}(\mathbb{E}Y, \sigma^2)$ for some $\sigma > 0$.
  • $Y$ is sub-Gaussian sensu lato if and only if for some $\sigma >0$, for all $t \ge 0$, $$\mathbb{P}(Y > \mathbb{E}Y + t) \le \exp\left( \frac{-t^2}{2\sigma^2} \right) \quad \text{and} \quad \mathbb{P}(Y < \mathbb{E}Y - t) \le \exp\left( \frac{-t^2}{2\sigma^2} \right) \,. $$
| cite | improve this answer | |
$\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.