The following Bernstein-type inequality can be found in Introduction to the non-asymptotic analysis of random matrices.

Theorem Let $X_1,\ldots X_n$ be mean-zero sub-exponential random variables with $\Vert X_i \Vert \leq K$, then for any $a \in \mathbb{R}^n$ $$ \mathbb{P}(\sum_{i=1}^n a_i X_i > t) \leq \exp(-c\min(\frac{t^2}{K^2\Vert a\Vert_2^2 }, \frac{t}{K\Vert a \Vert_\infty}))$$

Proof By appropriate rescaling of $X_i$ and $t$ we may assume that $K = 1$. Now the markov inequality yields that for any $\lambda > 0$ \begin{align*}\mathbb{P}(\sum_{i=1}^n a_i X_i > t) &= \mathbb{P}(\exp(\lambda \sum_{i=1}^n a_i X_i) > \exp(\lambda t))\\ &\leq \exp(-\lambda t)\mathbb{E}(\exp(\lambda\sum_{i=1}^n a_i X_i))\\ &= \exp(-\lambda t) \prod_{i=1}^n\mathbb{E}\exp(\lambda a_i X_i)\\ &\leq \exp(-\lambda t) \prod_{i=1}^n \exp(C\lambda^2 a_i^2) \qquad \forall \lambda < \frac{C}{\Vert a\Vert_\infty } \end{align*} where the last inequality uses an equivalent definition of subexponential random variables. Finally, minimalisation of the second order polynomial $-\lambda t + C \lambda^2 \Vert a \Vert_2^2$ for $\lambda <\frac{C}{\Vert a \Vert_\infty}$ yields the result. $\square$

My confusion is due to the minimalisation of this second order polynomial. If I understand rightly the optimisation uses $\lambda = \frac{t}{2C\Vert a \Vert_2^2}$ if this is possible but the boundary value otherwise which is why we have to put a minimum.

Why can't we just use the boundary value instead of adding a minimum? It appears to me that this would yield a stronger result.


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.