7
$\begingroup$

Suppose $X_1,X_2, \ldots, X_N \in \mathbb R^d$ are random variables with each $\|X_n\|_2 \le 1/2$ (this choice of the constant simplifies later formulae).

The simplest concentration inequality I know only applies in the case $d=1$ and only when $X_1,X_2, \ldots, X_N$ are i.i.d. The Hoeffding Lemma gives for each $\epsilon >0$ the bound

$$P(|X_1 + \ldots + X_N| \ge \epsilon) \le \exp\left (-\frac{2\epsilon^2}{N} \right).\tag{1}$$

On the other end of the spectrum are results that work under the weaker assumption that $X_1,X_2, \ldots, X_N$ is a martingale, and work for any $d \in \mathbb N$, or indeed for infinite dimensional Banach spaces provided some variant of the parallelogram is satisfied. For example Theorem 3.5 of this paper of Pinelis leads to the following variant of the Azuma-Hoeffding inequality.

$$P(\|X_1 + \ldots + X_n\|_2 \ge \epsilon \text{ for some }n\le N) \le \exp\left (-\frac{\epsilon^2}{2N} \right).\tag{2}$$

The exponent is the same as the scalar Azuma Hoeffding. Notice the $2$ is now downstairs rather than upstairs like before.

If we are only dealing with i.i.d scalars and only interested in the final element, we should use $(1)$ because it gives a better bound. If we are dealing with either vectors, martingales, or want a uniform inequality we better use $(2)$ instead.

My problem is between the two extremes. I am dealing with a sequence of i.i.d vectors in $\mathbb R^d$ and I am interested in a uniform bound. I wonder does there exist an appropriate middle-ground between these two results? Perhaps combining the $-2\epsilon^2/N$ of the first with the uniform nature of the second, at the expense of only applying to i.i.d sequences as opposed to martingales.

$\endgroup$
4
$\begingroup$

Other than the presence of an extra factor $D$ or $D^2$, depending on the context, the coefficients in the bounds for martingales in $(2,D)$-smooth spaces in the paper you cite are exactly the same as the ones for sums of independent real-valued random variables. There is no gap in this sense.

Also, you are citing Hoeffding's inequality incorrectly: the restriction on the $X_n$'s is of course in terms of the $\infty$-norm, rather than in terms of the $2$-norm.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for pointing this out! Clearly I have been staring at these things for too long to realize the generalsiation of $-1/2 \le X_n \le 1/2$ is not in fact $\|X_n\| \le 1$ but $\|X_n\| \le 1/2$. $\endgroup$ – Daron May 26 '19 at 16:14
  • $\begingroup$ To write out the restriction in full, should it be $\sup\{\|X(x)\|_2: x \in \Omega\} \le 1/2$ where $\Omega$ is the probability space and $\|\cdot\|_2$ is the $2$-norm on $\mathbb R^d$? $\endgroup$ – Daron May 26 '19 at 16:18
  • $\begingroup$ @Daron : Concerning your latest comment: that is right. $\endgroup$ – Iosif Pinelis May 26 '19 at 17:41
  • $\begingroup$ I wonder could you provide any reference for the following type of Martingale problem? Suppose $f_0,f_1,f_2,\ldots$ is an (infinite) martingale starting at $f_0=0$ and we want to bound the chance that after some big $N \in \mathbb N$ all the normalised values $\|\frac{f_n}{n}\|$ are less than $1$ say. We can of course take the exponential bound from one of your theorems, do a union bound, and estimate that by integrating the exponential. But that seems a pretty crude way to go about things. Are there any more sophisticated techniques available? $\endgroup$ – Daron May 28 '19 at 18:57
  • $\begingroup$ Doing the union bound gives something like $C e^{-cN}$ for some constants $C,c>0$. I tried to be clever and instead force some subsequence of $\|f_n\|/n$ to be less than $1/2$ say because this forces the elements in between to be less than $1$. That leads to integrating something like $\exp(ab^x)$ and I can only get a bound like $C e^{-cN}/N$. I can write this out as a full question if you like? $\endgroup$ – Daron May 28 '19 at 19:01

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.