4
$\begingroup$

I'm looking for a concentration bound on the maximum of a collection of sub-exponential random variables, which are not necessarily independent. More specifically, I have the following collection:

\begin{align} X_i = |{\langle a^i, u\rangle}|, \; \| u \| = 1, \; a^i \sim \mathcal{N}(0, I_d), \; i = 1, \dots, m, \; m \geq d \end{align} I want to bound

$$ \max_i X_i \leq \max_i \|a^i\| $$

and my approach is bounding it via bounding $\max_i \|a^i\|^2$, which is the maximum over the sum of subexponential RVs. When the maximum is over a collection of subgaussians, I am aware of the bound $ \mathbb{E}[\max_i X_i] = \mathcal{O}(\sqrt{\sigma \log n})$ where $X_i$ are $\sigma$-subgaussian variables, not necessarily independent. Is there something similar for subexponentials (or some easier way of bounding $\max_i \| a^i \|$?)

Edit: Example 2.7 in [1] gives the following bound for $Z_1, \dots, Z_n \sim \chi^2_p$: $$ \mathbb{E}[\max_i Z_i - p] \leq \sqrt{2 p \log n} + 2 \log n $$ so for my case using Markov's inequality I get

$$ \mathbb{P}(\max_i \| a^i \| \leq t) = \mathbb{P}(\max_i \| a^i \|^2 \leq t^2) \geq 1 - \frac{d + 2 \log m + \sqrt{2 d \log m}}{t^2} $$ which implies that the smallest $t$ for which I can get concentration that increases with the number of measurements $m$ is something like $\sqrt{d \log m}$, which gives me $$ \mathbb{P}(\max_i \| a^i \| \leq t) \geq 1 - \frac{1}{\log m} - \frac{2}{d} - \sqrt{\frac{2}{d \log m}} $$

Can I get anything sharper than this?

Edit 2: If it helps, we may assume that $a^i$ is a "shifted" version of $a^j$, that is:

$$ \newcommand{\mmod}{\text{ mod }} a^i = \left( g_{i \mmod m}, g_{i+1 \mmod m}, \dots, g_{i+d-1 \mmod m} \right) \\ a^j = \left( g_{j \mmod m}, g_{j+1 \mmod m}, \dots, g_{j+d-1 \mmod m} \right) $$ where $g_1, \dots, g_m \overset{\text{i.i.d}}{\sim} \mathcal{N}(0, 1)$. In that case, we know that

$$ \max_i \| a^i \| \leq \| g \| \Rightarrow \mathbb{P}(\max_i X_i \leq \sqrt{m + 1}) \geq 1 - \exp\left(-\frac{m}{8}\right). $$ where the concentration inequality follows from [2], Example 2.5. However $\sqrt{m + 1}$ is still too bad of a scaling; I would ideally like something that scales logarithmically in $d$ and $m$. Any help or hints would be welcome.

Update: with $\| u \| = 1$, we know that $\langle a^i, u \rangle \sim \mathcal{N}\left(0, \sum_i u_i^2\right) = \mathcal{N}(0, 1)$. Additionally $\langle \cdot, u \rangle$ is 1-Lipschitz so we may use the Gaussian concentration inequality to obtain

$$ \mathbb{P}\left(| \langle a^i, u \rangle| \geq \sqrt{\frac{2}{\pi}}+ t\right) \leq \exp\left(-t^2 / 2 \right), \; \forall i $$ so setting $ t = \sqrt{2} \log m $ and taking a union bound over the whole set $[m]$ gives me $$ \mathbb{P}\left(\max_i X_i \leq \sqrt{2} \left( \log m + \frac{1}{\sqrt{\pi}} \right) \right) \geq 1 - m \exp(-\log^2 m) = 1 - m^{-1}. $$

Another attempt: if we take into account the special structure of the $a^i$'s mentioned above, we can see that

$$ \left| \max_i |\langle a^i, u \rangle| - \max_i | \langle b^i, u \rangle | \right| \leq \left| \max_i \left( | \langle a^i, u \rangle| - |\langle b^i, u \rangle| \right) \right| \\ \leq \max_i \left| \langle a^i - b^i, u \rangle \right| \leq \max_i \| a^i - b^i \| \leq \| a - b \| $$

which shows that $\max_i | \langle a^i, u \rangle|$ is a $1$-Lipschitz function of $g \sim \mathcal{N}(0, I_m)$. This gives

$$ \mathbb{P}\left(\left| \max_i X_i - \mathbb{E}(\max_i X_i) \right| \geq t\right) \leq 2e^{-\frac{t^2}{2}} $$

which gives us

$$ \mathbb{P}\left(\max_i X_i \leq c \sqrt{\log m} \right) \geq 1 - m^{-1} $$

Can we do better than this?

[1]: Boucheron, Stéphane, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.

[2]: Martin J. Wainwright. High Dimensional Statistics: A nonasymptotic viewpoint. Draft edition, 2015.

$\endgroup$
  • $\begingroup$ Hint: $|{\langle a, b\rangle}| \le || a|| \, || b ||$. Please add "self-education" tag to your question. $\endgroup$ – Viktor Jun 21 '18 at 1:37

Your Answer

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

Browse other questions tagged or ask your own question.