0
$\begingroup$

Let $A\in\mathbb{R}^{n^k}$ be a $k$-dimensional tensor with $n$ elements along each dimension. Moreover suppose $u_1,u_2,\dots,u_k\sim\text{Unif}(\pm1)^n$ are $n$ dimensional vectors with each of their components drawn iid from Rademacher distribution, and let $U:=u_1\otimes u_2 \otimes \dots \otimes u_k$ be a rank-1 random tensor constructed from these vectors. Finally, let $X:=\langle A, U \rangle$, in which by $\langle, \rangle$ we simply mean the inner product of tensor if we flatten them as vectors.

Question:: What is the concentration of $X^2$ around its mean? As it is shown at the bottom of the post, $\mathbb{E} X^2=\lVert A\rVert_F^2$, i.e., the sum of the square of all elements in the tensor. How can the tails of the distribution around the mean be bounded: $P\left(|X^2-\mathbb{E} X^2|\ge x \right)$? Alternatively, as is typical in many concentration bounds, can the probability be bounded as an $\epsilon$-deviation from the mean: $P\left(|X^2-\mathbb{E} X^2|\ge \epsilon \left(\mathbb{E} X^2\right) \right)$?

Follow-up as @IosifPinelis has pointed out in their answer, moments of $X$, $\mathbb{E} X^{2p}$, can be effectively bounded, leading to a tail bound roughly of type $P(X\ge x)\le \exp(-x^{2/k})$. However, the main question was to bound the tail bounds of $X^2$ around its mean, which is $P(|X^2-\mathbb{E} X^2| \ge x)$. Taking a similar approach as @IosifPinelis, one could try to bound the tails of $Y:=X^2 - \lVert A\rVert_F^2$ by bounding its moments $\mathbb{E} Y^p$. Is that a sound approach?

Context: given that tails are light, this can be seen as sketching the Frobenius norm of a tensor. More so to the point, if $A,B$ are tensors, if we compute $v=\langle A,u_1\otimes \dots\otimes u_k\rangle$ and $w=\langle B,u_1\otimes \dots\otimes u_k\rangle$, then $\mathbb{E}(v-w)^2 = \lVert A-B\rVert_F^2$ and if the concentration is high, it can be seen as a distance-preserving embedding of tensors into the $L^2$-norm. The reason for choosing a rank-1 random tensor as opposed to a fully random one, which makes the bound trivial to compute, is that for certain applications the product with a rank-1 tensor can be computed much more efficiently and hence the sketching is faster to compute.

Derivation of $\mathbb{E} X^2$: \begin{align*} \mathbb{E} X^2 &= \mathbb{E}\sum_{i_1,j_1, \dots,i_k,j_k} a_{i_1, \dots,i_k} a_{j_1,\dots,j_k} u_{1,i_1}\dots u_{k,i_k} u_{1,j_1}\dots u_{k,j_k}\\ &= \sum_{i_1,j_1, \dots,i_k,j_k\le n} a_{i_1, \dots,i_k} a_{j_1,\dots,j_k} \Pi_{m=1}^k \mathbb{E}(u_{m,i_m} u_{m,j_m}) &&\rhd \text{L.o.E, and $u_i$s independence}\\ &= \sum_{i_1,\dots,i_k\le n} a_{i_1,\dots,i_k}^2 && \rhd i_m\neq j_m: \mathbb{E} u_{i_m}u_{j_m} = 0\\ &= \sum_{i_1,\dots,i_k\le n} a_{i_1,\dots,i_k}^2=\lVert A \rVert_F^2 && \rhd \mathbb{E} u_{i_m}^2 = \mathrm{Var}(u_{i_m}) = 1 \end{align*}

$\endgroup$
1
$\begingroup$

The tail probability $P(X\ge x)$ is in general like $e^{-x^{2/k}}$ for large $x>0$.

Indeed, we have \begin{equation*} X=\sum_{i_1,\dots,i_k\le n} a_{i_1,\dots,i_k}u_{1,i_1}\dots u_{k,i_k}, \end{equation*} where the $u_{i,j}$'s are assumed to be independent Rademacher random variables. Without loss of generality, $|a_{i_1,\dots,i_k}|\le1$ for all $i_1,\dots,i_k$ in $[n]:=\{1,\dots,n\}$. So, for any natural $p$ and $Z\sim N(0,1)$, \begin{align*} EX^{2p}&=E\prod_{j=1}^{2p}\,\sum_{i_{1,j},\dots,i_{k,j}\le n} a_{i_{1,j},\dots,i_{k,j}}u_{1,i_{1,j}}\dots u_{k,i_{k,j}} \\ &=\sum_{j\le2p;\ i_{1,j},\dots,i_{k,j}\le n}\, \Big(\prod_{j=1}^{2p}\,a_{i_{1,j},\dots,i_{k,j}}\Big)\, E\prod_{j=1}^{2p}(u_{1,i_{1,j}}\dots u_{k,i_{k,j}}) \\ &\le\sum_{j\le2p;\ i_{1,j},\dots,i_{k,j}\le n}\, E\prod_{j=1}^{2p}\,(u_{1,i_{1,j}}\dots u_{k,i_{k,j}}) \\ &=E\Big(\sum_{i_1,\dots,i_k\le n} u_{1,i_1}\dots u_{k,i_k}\Big)^{2p} \\ &=E\Big(\sum_{i_1\le n} u_{1,i_1}\cdots \sum_{i_k\le n} u_{k,i_k}\Big)^{2p} \\ &=E\Big(\sum_{i_1\le n} u_{1,i_1}\Big)^{2p}\cdots E\Big(\sum_{i_k\le n} u_{k,i_k}\Big)^{2p} \\ &=\Big(E\Big(\sum_{i\le n} u_{1,i}\Big)^{2p}\Big)^k \\ &\le\Big(E(Z\sqrt n)^{2p}\Big)^k \\ &\le (np)^{kp}. \end{align*} The first inequality in the above multiline display follows because $|a_{i_1,\dots,i_k}|\le1$ and $E\prod_{j=1}^{2p}(u_{1,i_{1,j}}\dots u_{k,i_{k,j}})$ is either $0$ or $1$ and hence $\ge0$; the penultimate inequality there holds by the Whittle--Haagerup inequality; and the last inequality follows because $EZ^{2p}=(2p-1)!!\le p^p$, as easy to check by induction.

So, by Markov's inequality, for $x>0$ \begin{equation*} P(X\ge x)\le R(p):=EX^{2p}/x^{2p}\le e^{g(p)}, \end{equation*} where \begin{equation*} g(p):=g_x(p):=-p\ln(x^2)+kp\ln(np). \end{equation*} The minimizer of $g(p)$ in all real $p>0$ is $p_x:=x^{2/k}/(en)$, and $R(p_x)=\exp\{-kx^{2/k}/(en)\}$. However, $p_x$ does not have to be an integer. Rounding it to the closest integer and using the facts that $g'(p_x)=0$ and $g''(p)=k/p\to0$ for $p\in[p_x-1/2,p_x+1/2]$ and $x\to\infty$, we conclude that \begin{equation*} P(X\ge x)\le \exp\{-kx^{2/k}/(en)\}(1+o(1)) \end{equation*} as $x\to\infty$, as claimed. Also, looking back at the above proof, it is easy to see that the obtained upper bound on $P(X\ge x)$ cannot be substantially improved in general.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there a way bound $\mathbb{E}(|X|^p)$ for general $p$ (not limited to integers)? In particular, I'm curious if the result on Khintchine inequality with both $L^1$ and $L^2$-norms terms, can be generalized to the tensor case? (talking about this: en.wikipedia.org/wiki/Khintchine_inequality#Generalizations) $\endgroup$ – kvphxga Jul 31 '19 at 1:42
  • $\begingroup$ I can show that, again in the Rademacher case, $$E|X|^q\le(nq)^{kq}\exp\Big\{\frac k{4\max(1,q-2)}\Big\}$$ for all real $q\ge2$. However, in more ways than one, it is better to post additional questions separately. $\endgroup$ – Iosif Pinelis Jul 31 '19 at 13:47
  • $\begingroup$ how do you convert this result back a concentration for $X^2$ after centering (subtracting its mean)? The upper side is trivial as $X^2-E(X^2)>=t$ implies $X^2>t$, but what about its lower tail? Also, I got a bound of $P(X\ge x)\le exp(-x^2/(8n^L)$ using the Taylor expansion of $exp$ and then Markov, I did it because it doesn't need the rounding, but which one is stronger? This bound or the one you've given here? $\endgroup$ – kvphxga Aug 29 '19 at 16:00
  • 1
    $\begingroup$ (i) The expectation of the product of powers with integer exponents of independent Rademacher random variables can only be $1$ (if all the exponents are even) or $0$ (otherwise). So, such an expectation cannot be negative. (ii) $\prod_{j=1}^{2p}$ was missing/misplaced in two places; these typos are now corrected. (iii) At this point, I don't have good ideas about bounding the lower tail. $\endgroup$ – Iosif Pinelis Aug 30 '19 at 15:29
  • 1
    $\begingroup$ Also, the best possible Markov bound derived from the moments directly should always be better than the best possible Markov bound derived from the moment generating function -- because the latter is just a particular mixture of the moments. $\endgroup$ – Iosif Pinelis Aug 30 '19 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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