Skip to main content
3 of 3
added 1588 characters in body

Orlicz norms are the general framework used for these sorts of results, though much of the Orlicz norm literature is concerned with concentration of sums $\sum_i X_i$ or suprema $\sup_i X_i$, rather than $\ell_2$ norms. If you want less theoretical literature recommendations, some authors have been looking into "sub-weibull" random variables lately. If one defines $\psi_\alpha(x) = \exp(x^\alpha)-1$, and examines the Orlicz norm $\lVert X\rVert_{\psi_\alpha}$ associated with this Young function, then

  • $\alpha = 2$ yields precisely the Sub-gaussian parameter of $X$,
  • $\alpha = 1$ yields precisely the sub-exponential parameter.

For $\alpha < 1$ one no longer has that $\lVert \cdot\rVert_{\psi_\alpha}$ is a norm (essentially because the function $\psi_\alpha$ is no longer convex). Still, some can try to recover parts of the general theory, which is precisely what the papers on "sub-weibull" random variables try to do.

Decreasing $\alpha$ is of interest because $\lVert X^2\rVert_{\psi_\alpha} = \lVert X\rVert_{\psi_{\alpha/2}}$, i.e. if one starts with sub-gaussian bounds on $X$, then one gets sub-exponential bounds on $\lVert X\rVert_2$.


One can convert Orlicz norm bounds to concentration bounds as follows. A typical definition of an Orlicz norm is for $\Psi:\mathbb{R}^+\to\mathbb{R}^+$ an increasing function that

$$\lVert X\rVert_\Psi = \inf\{c>0\mid \mathbb{E}\left[\Psi(\lVert X\rVert_2/c)\right] \leq 1\}.$$

For this to be a norm generally one assumes $\Psi$ is what is called a Young's function, namely $\Psi(0)= 0$, $\lim_{x\to\infty}\Psi(x) = \infty$, and $\Psi$ is convex and increasing on $[0,\infty)$.

Markov's inequality then gives that $$ \Pr[\lVert X\rVert_2\geq c] = \Pr[1+\Psi(\lVert X\rVert_2/\lVert X\rVert_\Psi) \geq 1+\Psi(c/\lVert X\rVert_\Psi)] \leq \frac{1+\mathbb{E}[\Psi(\lVert X\rVert_2/\lVert X\rVert_\Psi)]}{1+\Psi(c/\lVert X\rVert_\Psi)} \leq \frac{2}{1+\Psi(c/\lVert X\rVert_\Psi)}. $$

For example, for the Young's function $\Psi_2(x) = \exp(x^2)-1$, we get that

$$\Pr[\lVert X\rVert_2\geq c] \leq \frac{2}{\exp((c/\lVert X\rVert_{\Psi_2})^2)}\implies \Pr[\lVert X\rVert_2 \geq c\lVert X\rVert_{\Psi_2}] \leq 2\exp(-c^2),$$

i.e. something akin to a standard concentration bound. Note that the quantity $\lVert X\rVert_{\Psi_2}$ is defined here in terms of $\lVert X\rVert_2$, rather than something like $\langle t, X\rangle$. To pass between the two, I am pretty sure you write $\lVert X\rVert_2 = \sup_{\lVert t\rVert_2 = 1}\langle X,t\rangle$, and then apply an $\epsilon$-net argument to the set $\{t\mid \lVert t\rVert_2 = 1\}$, but I was never very good with $\epsilon$-net arguments, so perhaps shouldn't be the person to discuss their finer details. I have in mind something like theorem 8.3 of this though.

An alternative way to handle this all is to appeal to the $\lVert X^2\rVert_{\psi_a} = \lVert X\rVert_{\psi_{a/2}}$ equality mentioned before, to note that (in the case of i.i.d. components for simplicity) $\lVert \lVert X\rVert_2^2\rVert_{\Psi_a} \leq n \lVert X_i\rVert_{a/2}$. This simply applies the above equality, and then triangle inequality. As mentioned though, for $a < 1$, $\lVert X\rVert_{\psi_a}$ is not convex (so does not satisfy triangle equality). Various things can be done to try to fix this, for example

  • settle for triangle equality up to some multiplicative constant (see section 4 of this), or
  • modify $\psi_a$ near zero to be convex, see problem 4 of this.