Estimation Error Rates For Sparse Precision Matrices

Why Estimation Error Is a Separate Question

A sparse precision estimate can be useful even when some individual entries are not classified correctly as zero or nonzero. Conversely, selecting the right edges does not by itself quantify how close the estimated precision values are to their targets. This tutorial studies estimation error: distances between an estimated precision matrix and the population precision matrix.

The rates depend on several ingredients. The penalty controls the amount of shrinkage, while the sample covariance score fluctuates around its population value. Likelihood curvature translates those fluctuations into parameter error. Sparsity reduces the effective number of entries that contribute to a matrix-norm bound, but an entrywise bound requires an additional stability condition. These are estimation statements, not claims of exact graph recovery.

Setup and Norms

Let $X_1,\ldots,X_n$ be independent observations from $N_p(0,\Sigma_0)$, where $\Sigma_0$ is positive definite and $\Theta_0=\Sigma_0^{-1}$ is the population precision matrix. Write $S=n^{-1}\sum_{k=1}^n X_kX_k^\top$ for the sample covariance matrix. The Gaussian graphical lasso estimate minimizes the negative log-likelihood, penalized on off-diagonal entries:

\widehat{\Theta}\in\arg\min_{\Theta\succ 0} \left\{-\log\det(\Theta)+\operatorname{tr}(S\Theta) +\lambda\sum_{i\ne j}|\theta_{ij}|\right\}.

Here the off-diagonal sum counts both $(i,j)$ and $(j,i)$, as does the matrix inner product $\langle A,B\rangle=\operatorname{tr}(A^\top B)$. The diagonal is not penalized. We assume a finite positive-definite solution exists. Define $\|\cdot\|_{\max}$ as the largest absolute entry, $\|\cdot\|_F$ as the Frobenius norm, and $\|\cdot\|_{\mathrm{op}}$ as the spectral norm.

Definition: Let $\mathcal S=\{(i,j):i\ne j,\ \theta_{0,ij}\ne0\}$ be the ordered off-diagonal support, and let $s=|\mathcal S|$. If the largest graph degree is $d$, then $s\le pd$. A degree bound controls the number of nonzero off-diagonal entries, while the $p$ diagonal entries remain present whether or not the graph is sparse.

A Frobenius-Norm Bound

The first result makes the role of likelihood curvature explicit. It uses a spectral bound on the line segment joining the true and estimated precision matrices. Such a bound is an assumption about the fit; it does not follow merely from sparsity.

Theorem: Suppose $\|S-\Sigma_0\|_{\max}\le\lambda/2$, and suppose every matrix $\Theta_t=\Theta_0+t(\widehat{\Theta}-\Theta_0)$, $0\le t\le1$, has largest eigenvalue at most $M$. Then $$ \|\widehat{\Theta}-\Theta_0\|_F \le M^2\lambda\left(3\sqrt{s}+\sqrt p\right). $$ Consequently, $\|\widehat{\Theta}-\Theta_0\|_{\mathrm{op}}$ is bounded by the same right-hand side.

Proof. Write $\Delta=\widehat{\Theta}-\Theta_0$, and let $f(\Theta)=-\log\det(\Theta)+\operatorname{tr}(S\Theta)$. The Hessian of the log-determinant part in a symmetric direction $A$ is $\operatorname{tr}(\Theta^{-1}A\Theta^{-1}A)$. Taylor's formula with an integral remainder gives

D_f(\widehat{\Theta},\Theta_0) :=f(\widehat{\Theta})-f(\Theta_0) -\langle S-\Sigma_0,\Delta\rangle =\int_0^1(1-t)\operatorname{tr} (\Theta_t^{-1}\Delta\Theta_t^{-1}\Delta)\,dt.

Since $\lambda_{\max}(\Theta_t)\le M$, every eigenvalue of $\Theta_t^{-1}$ is at least $1/M$. Diagonalizing $\Theta_t^{-1}$, or applying this lower bound on both sides of $\Delta$, yields $\operatorname{tr}(\Theta_t^{-1}\Delta\Theta_t^{-1}\Delta)\ge M^{-2}\|\Delta\|_F^2$. Also $\int_0^1(1-t)\,dt=1/2$. Thus $D_f\ge\|\Delta\|_F^2/(2M^2)$.

Optimality of $\widehat{\Theta}$ gives $D_f\le\langle\Sigma_0-S,\Delta\rangle+ \lambda(\|\Theta_{0,\mathrm{off}}\|_1-\|\widehat{\Theta}_{\mathrm{off}}\|_1)$, where the subscript indicates the ordered off-diagonal entries. On $\mathcal S$, the penalty difference is at most $\|\Delta_{\mathcal S}\|_1$; outside $\mathcal S$, it is at most $-\|\Delta_{\mathcal S^c}\|_1$. Split the score inner product into diagonal and off-diagonal terms. The score bound and these penalty inequalities imply

D_f\le \frac{3\lambda}{2}\|\Delta_{\mathcal S}\|_1 -\frac{\lambda}{2}\|\Delta_{\mathcal S^c}\|_1 +\frac{\lambda}{2}\|\Delta_{\mathrm{diag}}\|_1 \le \frac{\lambda}{2}(3\sqrt{s}+\sqrt p)\|\Delta\|_F.

The last inequality uses Cauchy–Schwarz on the $s$ supported entries and the $p$ diagonal entries, and discards the nonpositive term. Combining with the curvature lower bound, and dividing by $\|\Delta\|_F$ when it is nonzero, proves the Frobenius bound. Finally, $\|A\|_{\mathrm{op}}\le\|A\|_F$ for every matrix $A$. $\square$

Worked Example: Converting Sparsity Into a Frobenius Bound

Suppose $p=100$, the true precision matrix has $s=120$ ordered nonzero off-diagonal entries, the score satisfies $\|S-\Sigma_0\|_{\max}\le0.04$, and the penalty is $\lambda=0.08$. Assume the segment in the theorem has largest eigenvalue at most $M=2$. The score condition holds because $0.04=\lambda/2$. The theorem gives

\|\widehat{\Theta}-\Theta_0\|_F \le 2^2(0.08)(3\sqrt{120}+\sqrt{100}) =0.32(32.8634+10) \approx 13.716.

The spectral-norm error is also at most $13.716$. This is a valid but potentially conservative upper bound, not a prediction that the realized error will be close to that value.

Entrywise Error and Hessian Stability

A Frobenius bound controls every entry, but it can be much looser than a direct entrywise rate when the support is large. To get a bound proportional to $\lambda$ without a factor such as $\sqrt{s}$, one needs stability of the inverse likelihood Hessian in the entrywise norm. A pointwise bound on the inverse Hessian at each location along a segment is not enough: the relevant object in the argument is the inverse of the averaged Hessian.

Theorem: Suppose $\widehat{\Theta}$ is an interior minimizer of the off-diagonal-penalized objective, and let $\Delta=\widehat{\Theta}-\Theta_0$. Define the averaged linear operator on symmetric matrices by $$ \overline{\mathcal H}[A]=\int_0^1\Theta_t^{-1}A\Theta_t^{-1}\,dt, \qquad \Theta_t=\Theta_0+t\Delta. $$ Assume $\overline{\mathcal H}$ is invertible and its inverse obeys $\|\overline{\mathcal H}^{-1}[B]\|_{\max}\le K\|B\|_{\max}$ for every symmetric $B$. If $\|S-\Sigma_0\|_{\max}\le\lambda/2$, then $$ \|\widehat{\Theta}-\Theta_0\|_{\max}\le \frac{3}{2}K\lambda. $$

Proof. The first-order optimality condition is $S-\widehat{\Theta}^{-1}+\lambda Z=0$, where $Z_{ii}=0$, $Z_{ij}=\operatorname{sign}(\widehat{\theta}_{ij})$ when $\widehat{\theta}_{ij}\ne0$, and $|Z_{ij}|\le1$ otherwise. The derivative of $-\Theta^{-1}$ in direction $A$ is $\Theta^{-1}A\Theta^{-1}$. Integrating this derivative along the segment gives

\overline{\mathcal H}[\Delta] =-(S-\Sigma_0)-\lambda Z.

The score has maximum entry at most $\lambda/2$, and $\|Z\|_{\max}\le1$, so the right side has maximum entry at most $3\lambda/2$. Applying the assumed bound for the inverse of the averaged operator proves the result. $\square$

This hypothesis is deliberately explicit. It is not a consequence of the score bound alone, nor of sparsity alone. In applications, the value of $K$ depends on the model's conditioning and the way the Hessian couples matrix entries.

Worked Example: An Entrywise Bound Under Stability

Take $\lambda=0.08$ as above, and suppose the averaged-Hessian inverse satisfies the stated condition with $K=5$. Then

\|\widehat{\Theta}-\Theta_0\|_{\max} \le \frac{3}{2}(5)(0.08)=0.60.

This bound controls the largest absolute entrywise error. It does not say that entries smaller than $0.60$ are zero, or that thresholding at $0.60$ recovers the graph. Such support conclusions require additional conditions.

How Sample Size and Degree Enter

For Gaussian observations with bounded marginal variances, concentration of sample covariance entries gives a high-probability score bound of the form $\|S-\Sigma_0\|_{\max}\le C\sqrt{\log(2p/\delta)/n}$, for $n$ sufficiently large relative to $\log(2p/\delta)$. The constant $C$ depends on the variance bound. Choosing $\lambda$ at least twice this threshold makes the score condition hold with probability at least $1-\delta$. Thus the entrywise rate under Hessian stability is of order $\sqrt{\log p/n}$, while the Frobenius bound scales with the number of relevant entries as well.

Since $s\le pd$, the theorem gives the convenient, slightly conservative degree-based expression

\|\widehat{\Theta}-\Theta_0\|_F \le M^2\lambda\sqrt p\,(3\sqrt d+1), \qquad \|\widehat{\Theta}-\Theta_0\|_{\mathrm{op}} \le M^2\lambda\sqrt p\,(3\sqrt d+1).

With $\lambda$ proportional to $\sqrt{\log p/n}$, this is a matrix-norm rate proportional to $M^2\sqrt{p(d+1)\log p/n}$, up to constants. The displayed degree expression retains the theorem's constants; the order notation suppresses them. These bounds describe accuracy when the stated curvature and stability assumptions hold. They do not establish that the estimated and true supports coincide.

Worked Example: A Degree-Based High-Dimensional Rate

Suppose $p=500$, $n=5000$, and use $\delta=0.05$. For illustration, take the covariance concentration constant to be $C=1$ and set $\lambda=2\sqrt{\log(2p/\delta)/n}$. Since $2p/\delta=20000$,

\lambda=2\sqrt{\frac{\log(20000)}{5000}} =2\sqrt{\frac{9.90349}{5000}} \approx 0.08901.

If the maximum degree is $d=3$, then $s\le1500$. With $M=1.5$, the degree-based theorem gives

\|\widehat{\Theta}-\Theta_0\|_F \le (1.5)^2(0.08901)\sqrt{500}(3\sqrt3+1) \approx 27.75.

If, in addition, the entrywise stability condition holds with $K=4$, the elementwise bound is $\|\widehat{\Theta}-\Theta_0\|_{\max}\le(3/2)(4)(0.08901)\approx0.534$. The concentration constant and stability constant are assumptions for this illustration; the arithmetic does not verify those modeling conditions.

Reading the Rates Carefully

The bounds show why sample size, dimension, and degree should not be interpreted in isolation. Increasing $n$ lowers the score fluctuation and hence the penalty scale. Increasing $p$ raises the logarithmic cost in the entrywise score bound and contributes more diagonal directions to the Frobenius bound. Increasing $d$ raises the possible number of nonzero off-diagonal entries, so the Frobenius error bound grows with the size of the sparse support.

A common mistake is to take a small entrywise estimation error and conclude that the graph has been recovered exactly. The bound only says that every estimated value is close to its population counterpart under its assumptions. If a true nonzero entry is itself smaller than the error scale, the bound does not distinguish it reliably from zero. Conversely, a support-recovery theorem concerns whether zero and nonzero entries are classified correctly; it is not a substitute for a matrix-norm error bound.

Another pitfall is to claim an entrywise rate from an inverse-Hessian bound that applies separately at each point on the segment. The proof uses the inverse of the integrated operator $\overline{\mathcal H}$; bounds on the individual inverses do not automatically bound that inverse. The stability condition must apply directly to the averaged operator, or be justified by a separate condition that implies it.

Key takeaway: Under a score bound and likelihood curvature, the Frobenius error is controlled by the penalty times a sparsity-dependent factor. An entrywise rate proportional to the penalty additionally requires explicit stability of the inverse averaged Hessian. Neither rate alone guarantees exact graph recovery.

Check Your Understanding

Use the assumptions stated in each question rather than inferring conditions that are not given.

Why does the Frobenius bound include a $\sqrt p$ term even though the diagonal entries are not penalized?
If $s\le pd$, write the theorem's degree-based Frobenius bound in terms of $p$, $d$, $M$, and $\lambda$.
Which inverse-Hessian operator must satisfy the stability condition for the entrywise theorem?
If the penalty is proportional to $\sqrt{\log p/n}$, how does increasing $n$ affect the stated entrywise rate when $K$ is fixed?
Why does an entrywise estimation-error bound not, by itself, prove exact recovery of the graph support?