0
$\begingroup$

Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant \Psi \left( \| t \|_2 \right)$$ for some well-behaved function $\Psi$.

My question: What are the { simplest, sharpest } { MGF bounds, concentration inequalities, etc. } which are available for $\| X \|_2$, ideally phrased in terms of $\Psi$?

I acknowledge that some conditions on $\Psi$ will inevitably be necessary (probably e.g. control on growth, smoothness, maybe monotonicity / convexity, etc.), but I emphasise that I would still like relatively general results, e.g. having a result for only quadratic $\Psi$ would not be fully satisfactory. A result for only polynomial-type $\Psi$ (i.e. $\Psi: t \mapsto t^\alpha$ for $\alpha$ in some nontrivial interval) would be somewhat narrow, but still valuable to me, since my experience is that such results are likely to generalise well.

I also acknowledge that the "{ simplest, sharpest }" in the framing of the question perhaps induces some tension / subjectivity; I included these qualifiers just to give a sense of what sort of results I seek, rather than to penalise people for giving non-sharp bounds, or similar.

$\endgroup$
3
  • $\begingroup$ If the downvote comes with any feedback attached, then I'd be happy to adapt the question to improve it! $\endgroup$
    – πr8
    Jun 4, 2023 at 16:26
  • $\begingroup$ One approach is studying the Orliz norms. Good books are the Boucheron book on concentration inequalities and the Talagrand book on probability in Banach spaces. $\endgroup$ Jun 5, 2023 at 18:03
  • $\begingroup$ The question can have many different answers depending on the law of X. For example, a subGaussian X has different bounds than power tail variables. The closest to general results that I've personally seen are the Orliz norm based concentrations. $\endgroup$ Jun 5, 2023 at 18:04

1 Answer 1

2
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ Thank you, I agree that Orlicz norms are well-adapted to treating 'non-standard' tail decay estimates, and suprema. For concreteness, would you be prepared to sketch out how the display in the OP (CGF ≤ Psi) could be translated into an estimate on some relevant Orlicz norm of X? $\endgroup$
    – πr8
    Jun 6, 2023 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.