5
$\begingroup$

There are loads of concentration results for sums of scalar-valued independent sums $X_1,X_2,\ldots, X_N$ with $\mathbb E[X_n]=0$. For example Hoeffding's Inequality says if all $|X_1|\le 1$ then $\mathbb E\left[ \left|\sum_{i=1}^N X_i\right|\right] = O (\sqrt N)$.

These concentration results can be generalised for example to vector-valued random variables with $\|X_n\| \le 1$ for $\| \cdot \|$ the Euclidean norm.

Suppose instead we have $\|\cdot\|_\infty$ norm bounds. That means $X_1,X_2,\ldots, X_N \in \mathbb R^d$ are independent with $\mathbb E[X_n]=0$ and $\|X_n\|_\infty \le 1$. Since $\|X_n\|_2 \le \sqrt d \|X_n\|_\infty \le \sqrt d$ we can use concentration results for the Euclidean norm to get $\mathbb E\left[ \left\|\sum_{i=1}^N X_i\right\|_\infty\right] = O (\sqrt {dN})$.

Does anyone know an example of when this dependence on $\sqrt d$ actually occurs?

Note: This is a bit informal. What I'm really asking is if the $O(\sqrt{dN})$ bound can be improved. I imagine a negative answer would be a family of examples of i.i.d sequences $X_n^{(d)}$, one for each value of $d$, such that $\mathbb E\left[ \left\|\sum_{i=1}^N X_i^{(d)}\right\|_\infty\right] \ge F(\sqrt {dN})$ for some common $\Omega(\sqrt{dN})$ function $F$.

I suspected such an example might be $X_n = (B_1^1,\ldots, B^1_d)$ for all $B^i_j$ independent and taking values $\pm 1$ with probability $1/2$. However the expectation seems more like $O (\sqrt {\log(d)N})$. To see this apply scalar concentration to each $j$ coordinate to get, up to coefficients:

$$P\left( \Big\|\sum_{i=1}^N X_i \Big\|_\infty <t\right)= P\left(\text{all } \Big|\sum_{i=1}^N X_i(j)\Big| <t \right)=\prod_{j=1}^d P\left(\Big|\sum_{i=1}^N X_i(j)\Big| <t \right) \ge (1-e^{-t^2 /N})^d.$$

$$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty = \int_0^\infty P\left( \Big\|\sum_{i=1}^N X_i(j)\Big\|_\infty >t\right)dt \le \int_0^\infty (1-(1-e^{-t^2/N})^d )dt$$

I don't know if the integral has a closed form. What I do know is the same argument gives $$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty ^2 \le \int_0^\infty (1-(1-e^{-t/N})^d )dt$$

which I do know how to solve. Substitute $x = e^{-t/N}$ to get $dt = - (N/x)dx$ and the integral becomes

$$ N \int_0^1 \frac{(1-(1-x)^d )}{x}dx$$

which equals $N$ times the $d$-th harmonic number, which is $O(N \log d)$. So we have $$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty ^2 \le O\left(N \log(d) \right)$$ and by the Jensen inequality $$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty \le O\left(\sqrt{\log(d) N}\right).$$

$\endgroup$
1
  • $\begingroup$ For the general case, apply concentration to each coordinate as you did for the independent case, but then use the union bound instead of taking the product. This should give you that sqrt d is impossible $\endgroup$ – alesia Apr 6 '20 at 23:59
7
$\begingroup$

Let $X_i=(X_{i,1},\dots,X_{i,d})$, $S:=(S_1,\dots,S_d)$, $S_j:=\sum_{i=1}^d X_{i,j}/\sqrt n$. Then, by Hoeffding's inequality, for $s\ge0$ $$P(|S_j|\ge s)\le2e^{-s^2/2},$$ whence $$E\|S\|_\infty=\int_0^\infty ds\,P(\|S\|_\infty\ge s) \le\int_0^\infty ds\,\min(1,2d\,e^{-s^2/2}) =O(1+\sqrt{\ln d});$$ here we used the inequality $$\int_t^\infty ds\,e^{-s^2/2}\le e^{-t^2/2}/2$$ for $t\ge0$. So, for $d\ge2$ you get $$E\Big\|\sum_{i=1}^n X_i\Big\|_\infty=O(\sqrt{n\ln d}),$$ without the assumption of the independence of the coordinates and without any other additional assumptions.

$\endgroup$
1
  • $\begingroup$ Thanks for answering my silly probability questions again. This is a very nice trick, and the sort of thing that might come to me in a dream five or ten years down the line. $\endgroup$ – Daron May 5 '20 at 15:27

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.