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
    Commented 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$ Commented 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$ Commented 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
    Commented Jun 6, 2023 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .