1
$\begingroup$

This is related to my previous question, but is hopefully more precise.

I would like to reason about tail-bounds for polynomial products of concentrated random variables in $R:=\mathbb{R}[x]/(x^n-1)$. Note that for $f(x), g(x)\in R$, we have that the $d$th coefficient of the product is

$$ \sum_{i\in[n]}f_ig_{d-i\bmod n}, $$ where $f_i, g_i$ are the coefficients of $f$ and $g$.

Briefly, by $\psi_\alpha$ random variable I mean a random variable of bounded Orlicz norm for the Young function $\psi_\alpha(x) = \exp(x^\alpha)-1$. $\psi_2$ corresponds to sub-Gaussian random variables. $\psi_1$ corresponds to sub-Exponential random variables.

It is well-known that if we start with the assumption that $f, g$ are $\psi_2$ random variables, we can naively prove a $\psi_1$ bound on the polynomial product. This has two main issues for me

  1. The $\psi_1$ concentration is much weaker than one expects in practice, at least for $n$ large (so $f(x)g(x)$ will, under appropriate independence assumptions on the coefficeints of $f_i, g_i$ which are fine in my setting, will start approaching a Gaussian, e.g. $\psi_2$ concentration).

  2. It is not composable. If we get a $\psi_1$ bound on the product $f(x)g(x)$, it does not help with analysis of $f(x)g(x)h(x)$ for $h(x)$ independent of $f, g$, and satisfying a $\psi_2$ bound.

It appears there are Orlicz norms that fix my issue #1 above. Namely, the content of Bernstein's inequality is that the sum of many $\psi_1$ random variables will have a (small deviation) $\psi_2$ tail, and (large deviation) $\psi_1$ tail, e.g. at least for some parameter range I can start with (assumed) $\psi_2$ tails, and get a $\psi_2$ bound for some region of the tail.

I am curious if this can additionally be made composable as well. There are many ways this question can be answered. One natural conjecture is the following though.

Let $L>0$. Define the $L$-Bernstein-Orlicz norm as the Orlicz norm associated with the function $\Psi_L(x) = \exp\left(\left[\frac{\sqrt{1+2Lz}-1}{L}\right]^2\right)-1$. Then, is there some function $h(x,y)$ such that for any independent random variables $f(x), g(x)$ on $R$ that $$\lVert f(x)g(x)\rVert_{\Psi_{h(L,L')}} \leq \lVert f(x)\rVert_{\Psi_L}\lVert g(x)\rVert_{\Psi_{L'}}$$

Essentially, if we start with full $\psi_2$ variables, we still get $\psi_2$ behavior near the mean of $f(x)g(x)$. If we instead start with $\Psi_L$ random variables (which are $\psi_2$ near their means), do we still get $\psi_2$ behavior near the mean of the random variables (perhaps for some concretely smaller notion of "near")? It feels like the answer should be yes, but I am not a probabilist, so am not sure if this is already known.

$\endgroup$
1
  • $\begingroup$ You might want to check arxiv.org/pdf/1304.1826.pdf (Theorem 1.1) and references therein. This isn't quite stated in the language of Orlicz norms, but it looks like it should be applicable to the problem that motivated your question: the authors provides a concentration inequality for homogenous multi-linear polynomials of sub-gaussian random variables in terms of various norms of the matrices produces out of coefficients of this polynomial. The coefficients of the convolution in your question are such polynomials. $\endgroup$ Commented Sep 1, 2023 at 1:52

0

You must log in to answer this question.

Browse other questions tagged .