Consider i.i.d random vectors $Y_{1},..,Y_{n}$ and they are chosen uniformly at random from $\{e_{1},..,e_{L}\}$ where $e_{i}$ is a $L\times 1$ vector with $i$th component be 1 and the others be 0. Given weights $h=(h_1,h_2,..,h_n)\in R^n$ that satisfy $\sum h_k=0 $, we would like to study the tail probability bounds of $$S^2(h)\triangleq\|\sum_{k=1}^n h_kY_k\|^2_2 $$
- some simple calculations give $ES^2(h)=\|h\|_2^2+\sum_{k\neq k'}h_kh_{k'}\frac1L=(1-\frac1L)\|h\|_2^2$. Note that for distinct $k_1,k_2,k_3$, $Y_{k_1}^TY_{k_2}$ and $Y_{k_1}^TY_{k_3}$ are uncorrelated, thus $$Var(S^2(h))=4Var(\sum_{k< k'} h_kh_{k'}Y_k^TY_{k'}) $$ $$=4\sum_{k< k'} h_k^2h_{k'}^2Var(Y_k^TY_{k'})\ $$ $$= 4\sum_{k< k'} h_k^2h_{k'}^2\frac1L(1-\frac1L) \leq\frac{2\|h\|_2^4}{L}(1-\frac1L)$$Then Chebyshev inequality yields $\forall t>0$ $$P(\frac{S^2(h)-ES^2(h)}{ES^2(h)}>t)\leq \frac{Var(S^2(h))}{t^2(ES^2(h))^2}\leq \frac2{t^2(L-1)}$$
Direct apply a Bernstein inequality for suprema of empirical process (Thm 8.42 in the book 'Mathematical Introduction to Compressed Sensing')
Theorem 8.42 Let $\cal{F}$ be a countable set of functions $F:R^L\rightarrow R$. Let $Y_1,..,Y_n$ be independent random vectors in $R^L$ such that $E(F(Y_k))=0$ and $F(Y_k)\leq K$ almost surely for all $k\in {1,2,.,,n}$ and for all $F\in \cal{F}$ for some constant K>0. Introduce $$Z=\sup_{F\in \cal{F}}\sum_{k=1}^nF(Y_k)$$ Let $\sigma^2_k>0$ such that $E(F(Y_k)^2)\leq \sigma^2_k$ for all $k\in {1,2,.,,n}$ and for all $F\in \cal{F}$. Then for all $t>0$, $$P(Z>EZ+t)\leq \exp{(-\frac{t^2/2}{\sigma^2 + 2KEZ +tK/3})}$$ where $\sigma^2=\sum_k \sigma^2_k$.
Back to our problem, we apply this theorem to $\tilde{Y}_k:=h_k(Y_k-EY_k)$, $F_x(\tilde{Y}_k):=<x,\tilde{Y}_k>$ and $\cal{F}$ $ = \{ F_x, x\in Q^L,\|x\|_2=1 , <1,x>=0 \}$. Then $Z$ in the theorem above is exactly our $S(h)$. Further, we can choose $K=(1-\frac1L)|h|_{\infty}$ and $\sigma^2_k=\frac{h^2_K}{L}$ Then we have $$P(S(h)\geq ES(h)+t)\leq \exp(-\frac{t^2/2}{\|h\|^2_2/L+|h|_{\infty}(2ES(h)+t/3)})$$
Actually, we are interested in the tail bound $P(S(h)\geq 1)$ when the weights satisfy $\|h\|^2_2 \asymp \frac{L}{n}$, $|h|_{\infty} \asymp \frac{L}{n}$ and $\frac{L}{n}=o(1)$ From the Bernstein inequality for suprema of emprical process, we have $$P(S(h)\geq 1)\leq \exp(-c_{1}\frac{n}{L})$$ where $c_1$ is some positive universal constant. This bound is not good when $\frac{L}{n}$ goes to zero very slowly. It may be even worse than the bound given by Chebyshev inequality : $$P(S(h)\geq 1)\leq c_2\frac{L}{n^2}$$where $c_2$ is some positive universal constant. We are aiming at finding some improved exponential tail bound. Specifically, can we get $$P(S(h)\geq 1)\leq C\exp(-cn)$$ for some universal positive constants $C,c$ under the assumption or some stronger assumptions? (This bound improve both the two known bounds and is true if we think those $Y_i's$ are i.i.d multivariate normal with the same convariance matrix with that of the original random vector).
From another angle, we would like find some analogue to the inequality $$P(\|\sum_{k=1}^n h_kX_k\|_2\geq \|h\|_2u)\leq \exp(-\frac{L}{2}(u^2-\log(u^2)-1))$$ for all $u>1$ and $h_1,..,h_n$, where $X_1,..,X_n$ are i.i.d uniformly distributed on the unit sphere $S^{n-1}=\{x\in R^L, \|x\|=1\}$. This inequality can be found here Thm 4.2 in this paper. The prove of this inequality relies on an extension of the Kintchine inequality to sum of independent random vectors that are rotationally invariant. See here extension of Kintchine inequality .
Any thoughts, comments, references are welcomed! Thanks!
