Gaussian and Sub-Gaussian Assumptions in Covariance Rates

Why Tail Assumptions Matter for Covariance Rates

Covariance estimators can have the same formula and very different error behavior. The key distinction is often not the estimator but the tails of the observations. Gaussian and sub-Gaussian coordinates make large deviations exponentially unlikely, allowing the largest of many covariance-entry errors to be controlled with a logarithmic dependence on the number of coordinates. With heavier tails, that conclusion may require stronger moment assumptions, a different rate, or a different estimator.

This distinction is especially important for entrywise thresholding. Thresholding works by comparing estimated covariance entries to a noise level. If that level is too small for the actual tails, noise entries can survive thresholding and undermine an operator-norm guarantee. We make the dependence on the tail condition explicit, then compare it with what finite fourth moments alone provide.

Covariance Error and Tail Conditions

Let $X_1,\ldots,X_n$ be independent, identically distributed random vectors in $\mathbb{R}^p$, with mean $\mu=E[X_i]$ and covariance matrix $\Sigma$. Write $\bar X=n^{-1}\sum_{i=1}^n X_i$, and use the sample covariance with denominator $n$:

\widehat{\Sigma} = \frac{1}{n}\sum_{i=1}^n (X_i-\bar X)(X_i-\bar X)^\top.

For a scalar random variable $Z$, its sub-Gaussian norm is $\|Z\|_{\psi_2}=\inf\{c>0:E[\exp(Z^2/c^2)]\leq 2\}$; its sub-exponential norm is $\|Z\|_{\psi_1}=\inf\{c>0:E[\exp(|Z|/c)]\leq 2\}$. These norms quantify tail decay. A vector is coordinatewise sub-Gaussian here if each centered coordinate has a finite sub-Gaussian norm relative to its marginal standard deviation.

Definition: Suppose $M=\max_{1\leq j\leq p}\Sigma_{jj}$. We say the coordinates are uniformly sub-Gaussian with constant $K$ if, for every $j$ with $\Sigma_{jj}>0$, $$ \|X_{ij}-\mu_j\|_{\psi_2}\leq K\sqrt{\Sigma_{jj}}. $$ A coordinate with zero variance is constant almost surely and needs no separate tail bound. The constant $K$ is dimensionless; Gaussian coordinates satisfy this condition with a universal $K$.

This is a coordinatewise condition, not a claim that the coordinates of $X_i$ are independent. Dependence among coordinates is allowed. In particular, bounding the maximum over covariance entries will use a union bound, not coordinate independence.

Entrywise Concentration Under Sub-Gaussian Tails

The central step is that products of sub-Gaussian coordinates are sub-exponential. We use the following scalar Bernstein inequality: if $Z_1,\ldots,Z_n$ are independent, mean-zero random variables and $\|Z_i\|_{\psi_1}\leq B$, then for a universal constant $c>0$,

P\left(\left|\frac{1}{n}\sum_{i=1}^n Z_i\right|>t\right) \leq 2\exp\left\{-cn\min\left(\frac{t^2}{B^2},\frac{t}{B}\right)\right\}.

The quadratic part of the exponent governs moderate deviations; the linear part accounts for larger deviations. The resulting covariance bound therefore includes both a square-root term and a linear term.

Theorem: Under the coordinatewise sub-Gaussian condition above, there are universal constants $C,c>0$ such that for every $u\geq 0$, with probability at least $1-2e^{-u}$, $$ \max_{j,k}\left| \frac{1}{n}\sum_{i=1}^n(X_{ij}-\mu_j)(X_{ik}-\mu_k)-\Sigma_{jk} \right| \leq C K^2 M\left( \sqrt{\frac{\log(2p)+u}{n}}+ \frac{\log(2p)+u}{n} \right). $$ For the sample covariance $\widehat{\Sigma}$, the same bound holds with a possibly larger universal $C$. In particular, for fixed failure probability and $\log(2p)\leq n$, $$ \max_{j,k}|\widehat{\Sigma}_{jk}-\Sigma_{jk}| = O_P\left(K^2 M\sqrt{\frac{\log(2p)}{n}}\right). $$

Proof. For any pair $j,k$, the product $(X_{ij}-\mu_j)(X_{ik}-\mu_k)$ has sub-exponential norm at most $C K^2\sqrt{\Sigma_{jj}\Sigma_{kk}}\leq C K^2M$. One way to see the product bound is to apply Cauchy–Schwarz to its exponential moment, using the sub-Gaussian exponential-square bounds for the two factors. Centering the product changes its sub-exponential norm by at most a universal factor. Thus the centered products across $i$ satisfy the scalar Bernstein inequality with $B=C K^2M$.

Apply Bernstein to each of the $p^2$ ordered pairs $(j,k)$, and take $t=C_1K^2M(\sqrt{(\log(2p)+u)/n}+(\log(2p)+u)/n)$, with $C_1$ sufficiently large. The exponent is then at least a sufficiently large multiple of $\log(2p)+u$. A union bound over $p^2$ pairs gives the displayed probability bound, after adjusting constants.

For the sample covariance, apply the raw-covariance bound above and the following mean bound with parameter $u+\log 2$. Each bound then fails with probability at most $e^{-u}$, so their intersection has probability at least $1-2e^{-u}$. Writing $L=\log(2p)+u$, we have $L\geq\log 2$ and hence $L+\log 2\leq2L$; the resulting changes in the square-root and linear terms are absorbed into universal constants. Let $Y_i=X_i-\mu$. Expanding the definition gives $\widehat{\Sigma}=n^{-1}\sum_iY_iY_i^\top-\bar Y\bar Y^\top$, where $\bar Y=\bar X-\mu$. The sub-Gaussian tail bound for each coordinate, followed by a union bound over $p$ coordinates, gives, with probability at least $1-e^{-u}$, $\max_j|\bar Y_j|\leq C K\sqrt{M(\log(2p)+u+\log 2)/n}$. Consequently, $\max_{j,k}|\bar Y_j\bar Y_k|\leq C K^2M(\log(2p)+u+\log 2)/n$. This is covered by the linear term already in the bound. Finally, when $\log(2p)\leq n$ and $u$ is fixed, that linear term is at most a constant times the square-root term. This proves both claims. \(\square\став>

The $\log(2p)$ form also avoids a degenerate expression when $p=1$: it remains positive in that case. If observations are Gaussian, the stated coordinatewise condition holds with universal $K$, so the same entrywise rate applies. Gaussianity is sufficient but not necessary; coordinatewise sub-Gaussian tails give the same order.

Worked Example: Gaussian Covariance Entries at a Fixed Dimension

Suppose $X_i\sim N(0,I_{100})$ independently, where $I_{100}$ is the $100$-dimensional identity matrix, and first consider the raw covariance $400^{-1}\sum_i X_iX_i^\top$, whose mean is known to be zero. For a diagonal entry, $X_{ij}^2$ has mean $1$ and variance $2$. For an off-diagonal entry $j\ne k$, independence of the two standard normal coordinates gives $E[X_{ij}X_{ik}]=0$ and $\operatorname{Var}(X_{ij}X_{ik})=E[X_{ij}^2]E[X_{ik}^2]=1$.

Thus the standard deviation of a single diagonal raw covariance entry is $\sqrt{2/400}\approx0.0707$; for an off-diagonal entry it is $1/\sqrt{400}=0.05$. These are single-entry standard deviations, not simultaneous bounds over all $100^2$ entries. The theorem’s uniform scale uses $\sqrt{\log(200)/400}\approx0.115$, up to universal constants. The logarithmic factor reflects controlling the maximum across entries.

Worked Example: Bounded Coordinates Are Also Sub-Gaussian

Let each observation have independent coordinates taking values $+1$ and $-1$ with equal probability, with $p=100$. Then $\mu=0$, $\Sigma=I_{100}$, $M=1$, and each coordinate has sub-Gaussian norm bounded by a universal constant. With $n=400$, the theorem gives a simultaneous entrywise scale proportional to $\sqrt{\log(200)/400}+\log(200)/400\approx0.128$, with constants and a chosen failure probability determining the actual bound.

For distinct coordinates $j\ne k$, each product $X_{ij}X_{ik}$ is itself a mean-zero variable taking values $+1$ and $-1$. The entry is an average of such bounded products, so exponential concentration is natural. For diagonal entries, $X_{ij}^2=1$ exactly in the raw covariance with known mean. This example illustrates why the sub-Gaussian rate is not specific to normal data.

From Entrywise Error to a Thresholding Guarantee

An entrywise bound becomes useful for sparse covariance estimation when the target matrix has few nonzero entries per row. Define hard thresholding off the diagonal by retaining $\widehat{\Sigma}_{jk}$ when its absolute value exceeds $\tau$, setting it to zero otherwise, and leaving the diagonal unchanged. Denote the result by $\widehat{\Sigma}^{\,H}_\tau$. Assume $\Sigma$ has at most $s$ nonzero entries in every row, counting the diagonal.

Theorem: If $\max_{j,k}|\widehat{\Sigma}_{jk}-\Sigma_{jk}|\leq\delta$ and $\tau=2\delta$, then $$ \|\widehat{\Sigma}^{\,H}_\tau-\Sigma\|_{\mathrm{op}}\leq 3s\delta. $$ Here $\|A\|_{\mathrm{op}}=\sup_{\|v\|_2=1}\|Av\|_2$. Combining this result with the sub-Gaussian concentration theorem gives an operator-norm rate of order $sK^2M\sqrt{\log(2p)/n}$ when $\log(2p)\leq n$ and the threshold is set at a constant multiple of that entrywise noise level.

Proof. Work on the event that every entry error is at most $\delta$. If $\Sigma_{jk}=0$, then $|\widehat{\Sigma}_{jk}|\leq\delta$, so an off-diagonal zero is removed by thresholding at $\tau\geq2\delta$. If a nonzero entry is removed, its magnitude satisfies $|\Sigma_{jk}|\leq|\Sigma_{jk}-\widehat{\Sigma}_{jk}|+|\widehat{\Sigma}_{jk}|\leq\delta+\tau$. For the particular choice $\tau=2\delta$, this is at most $3\delta$; retained entries have estimation error at most $\delta$. The diagonal is not thresholded and also has error at most $\delta$. Hence, when $\tau=2\delta$, each row of the error matrix has at most $s$ potentially nonzero entries, each bounded by $3\delta$, so its absolute row sum is at most $3s\delta$.

The matrices are symmetric. For a symmetric matrix $A$, every eigenvalue $\lambda$ satisfies $|\lambda|\leq\max_j\sum_k|A_{jk}|$: take an eigenvector and a coordinate whose absolute value is largest, then apply the triangle inequality to that coordinate of $Av=\lambda v$. The spectral theorem therefore gives $\|A\|_{\mathrm{op}}\leq\max_j\sum_k|A_{jk}|$. Applying this to the error matrix proves the result for $\tau=2\delta$. A larger threshold can remove additional nonzero entries with magnitude as large as $\tau+\delta$, so the stated $3s\delta$ guarantee is for the specified threshold $2\delta$, not arbitrary $\tau\geq2\delta$. $\square$

Worked Example: Applying the Sparse Threshold Bound

Suppose $p=100$, each row of $\Sigma$ has at most $s=2$ nonzero entries including its diagonal, and the observed entrywise error is at most $\delta=0.04$. Threshold off-diagonal entries at $\tau=2\delta=0.08$. Every true zero off-diagonal entry is removed, since its estimate has magnitude at most $0.04<0.08$. Any nonzero entry that is mistakenly removed has magnitude at most $0.04+0.08=0.12$. A retained entry has error at most $0.04$, and each diagonal entry has error at most $0.04$.

There are at most two nonzero entries in each row of the target, so the absolute row sum of the thresholded error is at most $2(3)(0.04)=0.24$. By symmetry and the row-sum bound, the operator-norm error is at most $0.24$. The bound is conservative: it uses only sparsity and the largest entrywise error, not the particular pattern or signs of the errors.

What Changes Under Heavier Tails?

Without sub-Gaussian tails, the product argument need not give an exponential bound. A useful comparison is available if fourth moments are uniformly bounded. Suppose the mean is known and $E[(X_{ij}-\mu_j)^4]\leq B_4$ for every coordinate. By Cauchy–Schwarz, $E[(X_{ij}-\mu_j)^2(X_{ik}-\mu_k)^2]\leq B_4$. Thus each centered product has variance at most $B_4$. Chebyshev’s inequality for each entry, followed by a union bound over $p^2$ entries, yields

P\left( \max_{j,k}\left| \frac{1}{n}\sum_{i=1}^n \left\{(X_{ij}-\mu_j)(X_{ik}-\mu_k)-\Sigma_{jk}\right\} \right|>t \right) \leq \frac{p^2B_4}{nt^2}.

For example, setting $t=p\sqrt{B_4/(n\alpha)}$ makes this upper bound $\alpha$. This is a polynomial-probability bound, and its dependence on $p$ is generally worse than the logarithmic dependence obtained from exponential concentration. The derivation concerns covariance around a known mean; estimating the mean requires additional control.

Worked Example: Finite Covariance Does Not Ensure a Gaussian Rate

Consider a symmetric scalar random variable $X$ with $P(|X|>x)=x^{-3}$ for $x\geq1$. It has finite second moment: using the tail integral, $E[X^2]=\int_0^\infty 2xP(|X|>x)\,dx =1+2\int_1^\infty x^{-2}\,dx=3$. But $E[X^4]=\int_0^\infty 4x^3P(|X|>x)\,dx$ is infinite, because the integral over $x\geq1$ is $4\int_1^\infty 1\,dx$.

For $Y=X^2$, $P(Y>y)=y^{-3/2}$ for $y\geq1$, so the squared observations have a polynomial rather than exponential tail. In a sample of size $n$, the probability that the maximum squared observation exceeds $n^{2/3}$ is $1-(1-1/n)^n$, which tends to $1-e^{-1}$. On that event, at least one term in the raw second-moment average is at least $n^{2/3}/n=n^{-1/3}$. This calculation shows why extreme observations cannot be dismissed using a Gaussian-style tail argument. Finite covariance alone does not supply the fourth-moment control used in the preceding bound, let alone the sub-Gaussian concentration used for the logarithmic entrywise rate.

Common Pitfall and Practical Interpretation

A common mistake is to take the familiar sub-Gaussian threshold level, proportional to $\sqrt{\log(p)/n}$, and use it for any data with a finite covariance matrix. Finite covariance controls second moments of coordinates, whereas covariance estimation involves products of coordinates. Concentration of those products needs additional tail or moment control. Without it, the usual entrywise noise bound—and therefore the thresholding guarantee built from that bound—has not been established.

The assumptions determine which conclusion is justified: Gaussian or coordinatewise sub-Gaussian tails support exponential entrywise concentration and, under row sparsity, the corresponding thresholding operator-norm bound. Uniform fourth moments support a Chebyshev-and-union-bound comparison, usually with weaker dimension dependence. With still heavier tails, even that argument may fail. Robust procedures can address some such settings, but their guarantees require their own assumptions and analysis.

Key takeaway: A sparse-thresholding rate inherits the tail assumptions used to control entrywise covariance noise. Check the coordinate tails or product moments before choosing the threshold; sparsity alone cannot justify the noise level.

Check Your Understanding

Use the assumptions as well as the formulas when answering.

Why does a union bound over covariance entries introduce a logarithm of the dimension under exponential concentration?
What additional term appears when the mean is estimated, and why is it absorbed when $\log(2p)\leq n$?
Under the thresholding theorem, what entrywise error condition ensures that true zero off-diagonal entries are removed?
Why does a uniform fourth-moment bound lead to a different dimension dependence than the sub-Gaussian assumption?
In the heavy-tailed example, which moment is finite and which is infinite, and why does that matter for covariance concentration?