A tail inequality for quadratic forms of subgaussian random vectors

Introduction

Consider the special case where $x_{1},\ldots,x_{n}$ are independent standard Gaussian random variables. The following proposition provides an (upper) tail bound for $\|Ax\|^{2}$.

The proof, given in Appendix A.2, is straightforward given the rotational invariance of the multivariate Gaussian distribution, together with a tail bound for linear combinations of $\chi^{2}$ random variables due to Laurent and Massart (2000). We note that a slightly weaker form of Proposition 1 can be proved directly using Gaussian concentration (Pisier, 1989).

We provide a sharp upper tail bound for this case analogous to one that holds in the Gaussian case (indeed, the same as Proposition 1 when $\sigma=1$).

One motivation for our main result comes from the following observations about sums of random vectors. Let $a_{1},\dotsc,a_{n}$ be vectors in a Euclidean space, and let $A=[a_{1}|\dotsb|a_{n}]$ be the matrix with $a_{i}$ as its $i$th column. Consider the squared norm of the random sum

falls off exponentially fast. This can be shown, for instance, using the following lemma by taking $u_{i}=a_{i}x_{i}$ (the proof is standard, but we give it for completeness in Appendix A.1).

for all $i=1,\dotsc,n$, almost surely. For all $t>0$,

After squaring the quantities in the stated probabilistic event, Proposition 2 gives the bound

with probability at least $1-e^{-t}$ when the $x_{i}$ are almost surely bounded by $1$ (or any constant).

Unfortunately, this bound obtained from Proposition 2 can be suboptimal when the $x_{i}$ are subgaussian. For instance, if the $x_{i}$ are Rademacher random variables, so $\Pr[x_{i}=+1]=\Pr[x_{i}=-1]=1/2$, then it is known that

with probability at least $1-e^{-t}$. A similar result holds for any subgaussian distribution on the $x_{i}$ (Hanson and Wright, 1971). This is an improvement over the previous bound because the deviation terms (i.e., those involving $t$) can be significantly smaller, especially for large $t$.

In this work, we give a simple proof of (2) with explicit constants that match the analogous bound when the $x_{i}$ are independent standard Gaussian random variables.

Positive semidefinite quadratic forms

Our main theorem, given below, is a generalization of (2).

Note that when $\mu=0$ and $\sigma=1$ we have:

Our proof actually establishes the following upper bounds on the moment generating function of $\|Ax\|^{2}$ for $0\leq\eta<1/(2\sigma^{2}\|\varSigma\|)$:

where $z$ is a vector of $m$ independent standard Gaussian random variables.

Let $USV^{\top}$ be a singular value decomposition of $A$; where $U$ and $V$ are, respectively, matrices of orthonormal left and right singular vectors; and $S=\operatorname{diag}(\sqrt{\rho_{1}},\dotsc,\sqrt{\rho_{m}})$ is the diagonal matrix of corresponding singular values. Note that

By rotational invariance, $y:=U^{\top}z$ is an isotropic multivariate Gaussian random vector with mean zero. Therefore $\|A^{\top}z\|^{2}=z^{\top}US^{2}U^{\top}z=\rho_{1}y_{1}^{2}+\dotsb+\rho_{m}y_{m}^{2}$ and $\mu^{\top}A^{\top}z=\nu^{\top}y=\nu_{1}y_{1}+\dotsb+\nu_{m}y_{m}$, where $\nu:=SV^{\top}\mu$ (note that $\|\nu\|^{2}=\|SV^{\top}\mu\|^{2}=\|A\mu\|^{2}$). Let $\gamma:=\lambda^{2}\sigma^{2}/2$. By Lemma 1,

for $0\leq\gamma<1/(2\|\rho\|_{\infty})$. Combining (4), (5), and (6) gives

for $0\leq\gamma<1/(2\|\rho\|_{\infty})$ and $\varepsilon\geq 0$. Choosing

where $h_{1}(a):=1+a-\sqrt{1+2a}$, which has the inverse function $h_{1}^{-1}(b)=\sqrt{2b}+b$. The result follows by setting $\tau:=2\sqrt{\|\rho\|_{2}^{2}t}+2\|\rho\|_{\infty}t=2\sqrt{\operatorname{tr}(\varSigma^{2})t}+2\|\varSigma\|t$. ∎

The following lemma is a standard estimate of the logarithmic moment generating function of a quadratic form in standard Gaussian random variables, proved much along the lines of the estimate due to Laurent and Massart (2000).

The right-hand side can be bounded using the inequalities

We give a simple application of Theorem 1 to fixed-design linear regression with the ordinary least squares estimator.

for independent subgaussian zero-mean noise variables $\varepsilon_{1},\dotsc,\varepsilon_{n}$. Let $\varSigma:=\sum_{i=1}^{n}x_{i}x_{i}^{\top}/n$, which we assume is invertible without loss of generality. Let

be the coefficient vector of minimum expected squared error. The ordinary least squares estimator is given by

The excess loss $R(\hat{\beta})$ of $\hat{\beta}$ is the difference between the expected squared error of $\hat{\beta}$ and that of $\beta$:

so the tail inequality above is essentially tight when the $y_{i}$ are independent Gaussian random variables.

References

Appendix A Standard tail inequalities

The following is a standard form of Bernstein’s inequality stated for martingale difference sequences.

The proof of Proposition 2, which is entirely standard, is an immediate consequence of the following two lemmas together with Jensen’s inequality.

Let $u_{1},\dotsc,u_{n}$ be random vectors such that

for all $i=1,\dotsc,n$, almost surely. For all $t>0$,

Let $s_{n}:=u_{1}+\dotsb+u_{n}$. Define the Doob martingale

The claim now follows from Bernstein’s inequality (Lemma 2). ∎

Let $s_{i}:=u_{1}+\dotsb+u_{i}$ for $i=1,\dotsc,n$; we have

It is well-known that if $z\sim\mathcal{N}(0,1)$ is a standard Gaussian random variable, then $z^{2}$ follows a $\chi^{2}$ distribution with one degree of freedom. The following inequality due to Laurent and Massart (2000) gives a bound on linear combinations of $\chi^{2}$ random variables.

Let $V\Lambda V^{\top}$ be an eigen-decomposition of $A^{\top}A$, where $V$ is a matrix of orthonormal eigenvectors, and $\Lambda:=\operatorname{diag}(\rho_{1},\dotsc,\rho_{n})$ is the diagonal matrix of corresponding eigenvalues $\rho_{1},\dotsc,\rho_{n}$. By the rotational invariance of the distribution, $z:=V^{\top}x$ is an isotropic multivariate Gaussian random vector with mean zero. Thus, $\|Ax\|^{2}=z^{\top}\Lambda z=\rho_{1}z_{1}^{2}+\dotsb+\rho_{n}z_{n}^{2}$, and the $z_{i}^{2}$ are independent $\chi^{2}$ random variables, each with one degree of freedom. The claim now follows from a tail bound for $\chi^{2}$ random variables (Lemma 5, due to Laurent and Massart, 2000). ∎