Design Concentration in Fixed-Dimensional Regression

Why Concentration of the Design Matters

In fixed-dimensional regression, the empirical Gram matrix summarizes how the observed covariates vary jointly. Its population counterpart describes the corresponding average under the covariate distribution. If the empirical matrix is close to a nonsingular population matrix, the sample design inherits a stable amount of variation in every direction. This is the design condition used in random-design least squares arguments: a well-behaved population matrix is useful only when the realized sample matrix is likely to approximate it.

The earlier material on convergence of the empirical Gram matrix establishes the basic consistency question. Here the emphasis is on rates and quantitative concentration conditions: how quickly the difference shrinks, how tail assumptions produce probability bounds, and how those bounds imply nonsingularity of the sample matrix with high probability. Throughout, the dimension $p$ is fixed unless otherwise stated.

Definition: Let $X_1,\ldots,X_n$ be independent random vectors in $\mathbb{R}^p$, with finite second moments. The empirical Gram matrix is $$ G_n=\frac{1}{n}\sum_{i=1}^n X_iX_i^{\mathsf T}. $$ For identically distributed covariates, the population Gram matrix is $Q=E[X_iX_i^{\mathsf T}]$. For a triangular array, write $Q_n=E[G_n]$. A population Gram matrix is nonsingular if its smallest eigenvalue is positive.

This definition includes an intercept if the first coordinate of $X_i$ is fixed at one. It does not require the covariates to have mean zero: $Q$ is a second-moment matrix, not necessarily a covariance matrix. In the identically distributed case, a finite second moment gives entrywise convergence $G_n\xrightarrow{p}Q$ by the law of large numbers. A rate or an exponential tail bound requires stronger assumptions.

A General Route from Concentration to Nonsingularity

For a symmetric matrix $A$, let $\|A\|_{\mathrm{op}}$ denote its operator norm. The eigenvalue perturbation inequality gives $\left|\lambda_{\min}(G_n)-\lambda_{\min}(Q)\right|\leq\|G_n-Q\|_{\mathrm{op}}$. Thus, if $\lambda_{\min}(Q)=\lambda_0>0$, the event $\|G_n-Q\|_{\mathrm{op}}<\lambda_0/2$ implies that the sample Gram matrix is nonsingular and that its smallest eigenvalue is at least $\lambda_0/2$.

Theorem: Suppose $Q$ is positive definite and $\lambda_{\min}(Q)=\lambda_0>0$. For any $0<\varepsilon<\lambda_0$, $$ P\{\lambda_{\min}(G_n)\leq \lambda_0-\varepsilon\} \leq P\{\|G_n-Q\|_{\mathrm{op}}\geq\varepsilon\}. $$ In particular, if $\|G_n-Q\|_{\mathrm{op}}\xrightarrow{p}0$, then $P\{\lambda_{\min}(G_n)\geq\lambda_0/2\}\to1$.

Proof. The eigenvalue perturbation inequality implies $\lambda_{\min}(G_n)\geq\lambda_{\min}(Q)-\|G_n-Q\|_{\mathrm{op}}$. Therefore, if $\lambda_{\min}(G_n)\leq\lambda_0-\varepsilon$, then $\|G_n-Q\|_{\mathrm{op}}\geq\varepsilon$. Taking probabilities proves the bound. Setting $\varepsilon=\lambda_0/2$ and using convergence in probability proves the final claim. $\square$

This result separates two requirements. The population design must be identified in all directions, through $\lambda_0>0$; sampling must approximate that design, through concentration. Concentration cannot compensate for a singular population matrix.

Bounded Covariates: An Exponential Bound

Suppose the covariates are independent and satisfy $\|X_i\|_2\leq B$ almost surely. They need not be identically distributed: define $Q_n=E[G_n]$. Each entry of $X_iX_i^{\mathsf T}$ lies in $[-B^2,B^2]$, so Hoeffding's inequality can be applied entry by entry. In fixed dimension, controlling all entries controls the operator norm.

Theorem: If $X_1,\ldots,X_n$ are independent, $\|X_i\|_2\leq B$ almost surely, and $Q_n=E[G_n]$, then for every $\varepsilon>0$, $$ P\{\|G_n-Q_n\|_{\mathrm{op}}\geq\varepsilon\} \leq 2p^2\exp\left(-\frac{n\varepsilon^2}{2p^2B^4}\right). $$ If $\lambda_{\min}(Q_n)\geq\lambda_0>0$, then the probability that $\lambda_{\min}(G_n)<\lambda_0/2$ is at most $2p^2\exp\{-n\lambda_0^2/(8p^2B^4)\}$.

Proof. For any $p$ by $p$ matrix $A$, $\|A\|_{\mathrm{op}}\leq p\max_{j,k}|A_{jk}|$. Thus, if $\|G_n-Q_n\|_{\mathrm{op}}\geq\varepsilon$, at least one entry differs from its expectation by at least $\varepsilon/p$. For a fixed entry $(j,k)$, the independent summands $X_{ij}X_{ik}$ lie in an interval of length at most $2B^2$. Hoeffding's inequality gives $$ P\{|(G_n-Q_n)_{jk}|\geq\varepsilon/p\} \leq 2\exp\left(-\frac{n\varepsilon^2}{2p^2B^4}\right). $$ A union bound over the $p^2$ entries proves the first inequality. If the minimum eigenvalue of $Q_n$ is at least $\lambda_0$, the eigenvalue perturbation inequality shows that $\lambda_{\min}(G_n)<\lambda_0/2$ requires $\|G_n-Q_n\|_{\mathrm{op}}>\lambda_0/2$. Substitution proves the second bound. $\square$

For fixed $p$ and fixed $B$, this bound decreases exponentially in $n$ for any fixed positive tolerance. The constants can be conservative; the useful point is the explicit dependence on dimension, covariate size, sample size, and the population eigenvalue.

Worked Example: A Two-Point Bounded Design

Let $X_i=(1,W_i)^{\mathsf T}$, where the $W_i$ are independent and take values $-1$ and $1$, each with probability $1/2$. Then $\|X_i\|_2=\sqrt{2}$, and direct calculation gives $$ Q=E[X_iX_i^{\mathsf T}] =\begin{pmatrix}1&0\\0&1\end{pmatrix}. $$ Hence $\lambda_{\min}(Q)=1$.

Write $\bar W=n^{-1}\sum_i W_i$. Since $W_i^2=1$, $$ G_n=\begin{pmatrix}1&\bar W\\\bar W&1\end{pmatrix}. $$ Its eigenvalues are $1+\bar W$ and $1-\bar W$, so its smallest eigenvalue is $1-|\bar W|$. The sample matrix is nonsingular exactly when $|\bar W|<1$. Hoeffding's inequality gives $P(|\bar W|\geq 1/2)\leq2\exp(-n/8)$. Consequently, with probability at least $1-2\exp(-n/8)$, the smallest eigenvalue of $G_n$ is greater than $1/2$. The bound uses $B=\sqrt{2}$, $p=2$, and $\varepsilon=1/2$ in the general theorem and is looser, but still valid.

Sub-Gaussian Covariates

Boundedness is sufficient but not necessary. A common alternative is a sub-Gaussian condition on every linear projection of the covariate vector. For a random variable $U$, define $\|U\|_{\psi_2}=\inf\{c>0:E[\exp(U^2/c^2)]\leq2\}$; the analogous $\psi_1$ norm replaces $U^2/c^2$ by $|U|/c$.

Definition: A random vector $X_i$ is sub-Gaussian with scale $K$ if $\|u^{\mathsf T}X_i\|_{\psi_2}\leq K\|u\|_2$ for every $u\in\mathbb{R}^p$. The sub-Gaussian scale is uniform across a sequence of designs if the same $K$ works for every row and sample size.

Products of sub-Gaussian random variables have sub-exponential tails: for coordinates $X_{ij},X_{ik}$, the centered product $X_{ij}X_{ik}-E[X_{ij}X_{ik}]$ has $\psi_1$ norm bounded by $C K^2$, where $C$ is a universal constant. Applying Bernstein's inequality to each entry and taking a union bound yields the following standard form. The constants $c,C>0$ below are universal and may change from line to line.

Theorem: For independent sub-Gaussian vectors with common scale bound $K$, let $Q_n=E[G_n]$. Then, for $t>0$, $$ P\{\|G_n-Q_n\|_{\mathrm{op}}\geq t\} \leq 2p^2\exp\left[-c n\min\left\{\frac{t^2}{p^2K^4},\frac{t}{pK^2}\right\}\right]. $$ For fixed $p$ and fixed $K$, this implies $\|G_n-Q_n\|_{\mathrm{op}}=O_p(n^{-1/2})$. If $\lambda_{\min}(Q_n)\geq\lambda_0>0$ uniformly, the empirical Gram matrices are nonsingular with probability tending to one.

To see the rate claim, take $t=M/\sqrt{n}$, where $M$ is a fixed positive number. For fixed $p$ and $K$, the quadratic term in the minimum governs for sufficiently large $n$, and the upper bound is at most $2p^2\exp(-cM^2/(p^2K^4))$. This can be made arbitrarily small by increasing $M$, which is the definition of the stated $O_p(n^{-1/2})$ rate. The nonsingularity conclusion follows from the eigenvalue perturbation bound with $t=\lambda_0/2$.

For a dimension that grows with $n$, the displayed probability bound still records the dimension dependence, but a fixed-dimensional rate conclusion does not automatically extend. The required comparison is between the resulting matrix error and the smallest population eigenvalue.

Worked Example: Gaussian Covariates With an Intercept

Let $X_i=(1,Z_i)^{\mathsf T}$, where $Z_i$ are independent $N(0,1)$ variables. The vector is sub-Gaussian with a fixed scale, and $$ Q=E[X_iX_i^{\mathsf T}]=\begin{pmatrix}1&0\\0&1\end{pmatrix}. $$ For $n=1000$, $$ G_n-Q=\begin{pmatrix}0&\bar Z\\\bar Z&\overline{Z^2}-1\end{pmatrix}, $$ where $\bar Z=n^{-1}\sum_i Z_i$ and $\overline{Z^2}=n^{-1}\sum_i Z_i^2$. A symmetric $2$ by $2$ matrix whose entries have absolute value at most $a$ has operator norm at most $2a$. Therefore, if both $|\bar Z|<1/4$ and $|\overline{Z^2}-1|<1/4$, then $\|G_n-Q\|_{\mathrm{op}}<1/2$, and $\lambda_{\min}(G_n)>1/2$.

The normal tail bound gives $P(|\bar Z|\geq1/4)\leq2\exp(-n/32)$. Since $n\overline{Z^2}$ has a chi-squared distribution with $n$ degrees of freedom, its Chernoff bounds give, for $0<t<1$, $$ P(\overline{Z^2}-1\geq t)\leq \exp\left[-\frac n2\{t-\log(1+t)\}\right],\qquad P(\overline{Z^2}-1\leq-t)\leq \exp\left[-\frac n2\{-t-\log(1-t)\}\right]. $$ At $t=1/4$, the exponents per observation are approximately $0.01343$ and $0.01884$, respectively. A union bound therefore gives $$ P\{\lambda_{\min}(G_n)\leq1/2\} \leq 2e^{-1000/32}+e^{-13.43}+e^{-18.84} < 2.0\times10^{-6}. $$ This calculation verifies a concrete high-probability eigenvalue bound using the structure of the Gaussian example.

Finite Fourth Moments and the Square-Root Rate

Exponential tails are not required for a square-root rate in fixed dimension. If $E\|X_i\|_2^4<\infty$ and the observations are identically distributed, then every entry $X_{ij}X_{ik}$ has finite variance. Chebyshev's inequality applied to each entry, followed by a finite union bound, gives $\|G_n-Q\|_{\mathrm{op}}=O_p(n^{-1/2})$. This route yields a polynomial probability bound rather than the exponential bounds above.

Worked Example: A Discrete Design and a Chebyshev Bound

Let $X_i=(1,W_i)^{\mathsf T}$, where $P(W_i=1)=1/4$, $P(W_i=-1)=1/4$, and $P(W_i=0)=1/2$, independently across observations. Then $E[W_i]=0$, $E[W_i^2]=1/2$, and $$ Q=\begin{pmatrix}1&0\\0&1/2\end{pmatrix},\qquad\lambda_{\min}(Q)=1/2. $$ Here $\operatorname{Var}(W_i)=1/2$, while $W_i^2$ is Bernoulli with success probability $1/2$, so $\operatorname{Var}(W_i^2)=1/4$. For $n=400$, Chebyshev's inequality gives $$ P(|\bar W|\geq0.1)\leq\frac{1/2}{400(0.1)^2}=0.125, \qquad P(|\overline{W^2}-1/2|\geq0.1)\leq\frac{1/4}{400(0.1)^2}=0.0625. $$ The only nonzero entries of $G_n-Q$ are the two off-diagonal entries $\bar W$ and the lower-right entry $\overline{W^2}-1/2$. On the event that both absolute deviations are below $0.1$, the operator norm is at most $0.2$, using $\|A\|_{\mathrm{op}}\leq2\max_{j,k}|A_{jk}|$. Thus $\lambda_{\min}(G_n)\geq0.5-0.2=0.3$. The union bound shows this conclusion holds with probability at least $1-0.125-0.0625=0.8125$.

Common Pitfall: Confusing Population Identification With Sample Concentration

A common error is to say, “The population Gram matrix is nonsingular, so the sample Gram matrix is nonsingular.” The conclusion does not follow for a finite sample without a probability or deterministic bound on the difference between the two matrices. The correct argument is to establish a concentration bound and compare its tolerance with $\lambda_{\min}(Q)$. If the error is less than that eigenvalue, the sample matrix is nonsingular; if the error is less than half that eigenvalue, its smallest eigenvalue is at least half the population value.

A second mistake is to infer an $n^{-1/2}$ rate from the law of large numbers alone. Finite second moments yield consistency of the entries, but a variance-based square-root rate for the Gram entries requires finite fourth moments. Bounded and sub-Gaussian assumptions provide stronger concentration; they are sufficient conditions, not necessary ones.

Key takeaway: In fixed dimension, concentration of $G_n$ around $Q$, combined with a positive lower bound on $\lambda_{\min}(Q)$, gives a quantitative guarantee that the realized design remains nonsingular. Boundedness yields an exponential Hoeffding bound, sub-Gaussian tails yield an exponential Bernstein bound, and finite fourth moments yield a square-root rate through Chebyshev's inequality.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

Why is $E[X_iX_i^{\mathsf T}]$ not generally the covariance matrix of $X_i$, and how does including an intercept affect its interpretation?
If $\lambda_{\min}(Q)=0.8$, what operator-norm error bound guarantees $\lambda_{\min}(G_n)\geq0.4$?
Which assumption supports the square-root rate obtained by entrywise Chebyshev bounds, and why is a finite second moment alone insufficient for that argument?
For bounded covariates, identify the two steps that turn entrywise Hoeffding bounds into an operator-norm probability bound.
In the Gaussian worked example, why does controlling both $|\bar Z|$ and $|\overline{Z^2}-1|$ control the smallest eigenvalue of $G_n$?