KKT Conditions And Sparsity In The Graphical Lasso

Why the KKT Conditions Matter

The graphical lasso estimates a sparse precision matrix by balancing likelihood fit against an entrywise penalty. The Karush–Kuhn–Tucker (KKT) conditions make that balance explicit: they say how large the likelihood gradient must be at an estimated edge, and how small it must be for an edge to be zero. This is more informative than treating the penalty as a black box.

The key distinction is between a nonzero estimated precision entry, where the penalty has a fixed sign, and a zero entry, where its subgradient can take any value in an interval. That interval gives a direct threshold condition. The results below concern the optimization problem itself; they do not by themselves guarantee recovery of the population graph.

Objective and Subgradient Convention

Let $S$ be a symmetric $p\times p$ sample covariance matrix, and let $\lambda>0$. We minimize over symmetric positive definite matrices $\Theta$ the negative Gaussian log-likelihood, up to constants and scaling, plus an off-diagonal $\ell_1$ penalty:

Q(\Theta)=\operatorname{tr}(S\Theta)-\log\det(\Theta) +\lambda\sum_{i\ne j}|\theta_{ij}|, \qquad \Theta\succ0.

The penalty sum is over ordered index pairs: for a symmetric matrix, each distinct off-diagonal entry appears twice. This convention is common and convenient for writing the KKT equations as matrix equations. The diagonal is not penalized.

Definition: For a scalar $x$, the subgradient of $|x|$ is $\operatorname{sign}(x)$ if $x\ne0$, and is any number in $[-1,1]$ if $x=0$. A subgradient matrix $\Gamma$ for the penalty has $\gamma_{ii}=0$, and, for $i\ne j$, $$ \gamma_{ij}= \begin{cases} \operatorname{sign}(\theta_{ij}),&\theta_{ij}\ne0,\\ \text{any value in }[-1,1],&\theta_{ij}=0. \end{cases} $$ It is symmetric, with $\gamma_{ji}=\gamma_{ij}$.

The smooth part has gradient $S-\Theta^{-1}$ under the matrix inner product $\langle A,B\rangle=\operatorname{tr}(A^\mathsf{T}B)$. In particular, the derivative of $-\log\det(\Theta)$ is $-\Theta^{-1}$. Since both $\Theta$ and its perturbations are symmetric, the two appearances of each off-diagonal entry in the penalty are matched by the two corresponding entries in the matrix gradient. Thus the stationarity equation has $\lambda$, not $2\lambda$, in each off-diagonal position.

The KKT Conditions

Theorem: Suppose $\hat{\Theta}\succ0$ minimizes $Q$. Then there is a symmetric subgradient matrix $\hat{\Gamma}$ of the form above such that $$ S-\hat{\Theta}^{-1}+\lambda\hat{\Gamma}=0. $$ Conversely, any $\Theta\succ0$ and subgradient matrix $\Gamma$ satisfying $S-\Theta^{-1}+\lambda\Gamma=0$ give a global minimizer. The minimizer, if it exists, is unique.

Proof. The domain of positive definite matrices is open within the vector space of symmetric matrices, so a positive definite minimizer is an interior point. The first-order condition for minimizing a differentiable convex function plus a convex function is that zero belong to the sum of the smooth gradient and the penalty subdifferential. The smooth gradient is $S-\Theta^{-1}$, and the penalty subgradient is $\lambda\Gamma$ with the entries specified above. This gives the stated equation.

For sufficiency, let $\Theta$ satisfy the equation and let $U\succ0$. Convexity of the smooth part gives $g(U)\ge g(\Theta)+\langle S-\Theta^{-1},U-\Theta\rangle$, where $g(V)=\operatorname{tr}(SV)-\log\det(V)$. The subgradient inequality for the penalty $h(V)=\lambda\sum_{i\ne j}|v_{ij}|$ gives $h(U)\ge h(\Theta)+\langle\lambda\Gamma,U-\Theta\rangle$. Adding these inequalities and using stationarity yields $Q(U)\ge Q(\Theta)$. Finally, $-\log\det(\Theta)$ is strictly convex on the positive definite cone: its second directional derivative in any nonzero symmetric direction $H$ is $\operatorname{tr}(\Theta^{-1}H\Theta^{-1}H)>0$. The trace term is linear and the penalty is convex, so $Q$ is strictly convex and cannot have two distinct minimizers. $\square$

Reading the equation entry by entry makes the sparsity condition transparent. Diagonal entries satisfy $(\hat{\Theta}^{-1})_{ii}=S_{ii}$. For distinct $i,j$, a nonzero entry satisfies $(\hat{\Theta}^{-1})_{ij}-S_{ij}=\lambda\operatorname{sign}(\hat{\theta}_{ij})$. A zero entry instead satisfies an inequality:

\hat{\theta}_{ij}=0 \quad\Longleftrightarrow\quad \left|(\hat{\Theta}^{-1})_{ij}-S_{ij}\right|\le\lambda, \qquad i\ne j.

The equivalence is understood as part of the full KKT system: at a zero entry, the residual must fit within the interval $[-\lambda,\lambda]$; at a nonzero entry, it must equal the endpoint with the entry's sign. This is a condition involving the inverse of the estimated precision matrix, not just the raw covariance $S$.

Worked KKT Calculations

Worked Example: The Two-Variable Threshold

Let $S=\begin{pmatrix}1&r\\r&1\end{pmatrix}$, where $0\le r<1$. Test when the all-diagonal estimate is optimal, and calculate the active solution when $r=0.6$ and $\lambda=0.2$.

For a diagonal candidate, the diagonal KKT equations require $\hat{\Theta}^{-1}_{11}=\hat{\Theta}^{-1}_{22}=1$, so the candidate is $\hat{\Theta}=I$. Its off-diagonal inverse entries are zero. The zero-entry condition is therefore $|0-r|\le\lambda$, or $r\le\lambda$. Thus a nonzero sample covariance does not force a nonzero estimated precision entry.

For $r=0.6$ and $\lambda=0.2$, $r>\lambda$, so the off-diagonal entry is active. By symmetry write $\Theta=\begin{pmatrix}a&-t\\-t&a\end{pmatrix}$, with $t>0$. Its determinant is $a^2-t^2$, and its inverse is $(a^2-t^2)^{-1}\begin{pmatrix}a&t\\t&a\end{pmatrix}$. The diagonal equations give $a/(a^2-t^2)=1$, hence $a^2-t^2=a$. The off-diagonal equation, whose penalty sign is $-1$, gives $r-t/a-\lambda=0$, hence $t/a=0.4$. Substituting $t=0.4a$ into $a^2-t^2=a$ gives $0.84a^2=a$, so $a=25/21$ and $t=10/21$. The eigenvalues are $a+t=35/21$ and $a-t=15/21$, both positive. The resulting estimate is positive definite and has the required nonzero entry.

Worked Example: When a Diagonal Estimate Is Optimal

Consider $S=\begin{pmatrix}2&0.3&-0.5\\0.3&1&0.7\\-0.5&0.7&3\end{pmatrix}$ and $\lambda=0.7$. First check that $S$ is positive definite. Its first two leading principal minors are $2$ and $2(1)-0.3^2=1.91$. Its determinant is $2(3-0.7^2)-0.3(0.3\cdot3-0.7\cdot(-0.5))+(-0.5)(0.3\cdot0.7-1\cdot(-0.5))=5.02-0.375-0.355=4.29$. All three leading principal minors are positive, so $S\succ0$.

For the diagonal candidate, the diagonal KKT equations give $\Theta=\operatorname{diag}(1/2,1,1/3)$, whose inverse is $\operatorname{diag}(2,1,3)$. The off-diagonal residuals $(\Theta^{-1}-S)_{ij}$ are $-0.3$, $0.5$, and $-0.7$, for pairs $(1,2)$, $(1,3)$, and $(2,3)$, respectively. Their absolute values are $0.3$, $0.5$, and $0.7$, all at most $\lambda$. Choose the corresponding subgradients as $-3/7$, $5/7$, and $-1$; each is in $[-1,1]$, and stationarity holds. Thus the diagonal candidate is the unique minimizer. The third edge is exactly at the subgradient boundary, illustrating that equality in the zero-entry condition is allowed.

Worked Example: Checking a Mixed Zero and Nonzero Pattern

Set $\lambda=0.2$ and propose $\Theta=\begin{pmatrix}1&-1/4&0\\-1/4&1&0\\0&0&1\end{pmatrix}$. Its upper-left block has determinant $1-1/16=15/16$, so $\Theta\succ0$. Its inverse is $\Theta^{-1}=\begin{pmatrix}16/15&4/15&0\\4/15&16/15&0\\0&0&1\end{pmatrix}$. Let $S=\begin{pmatrix}16/15&7/15&1/10\\7/15&16/15&-3/20\\1/10&-3/20&1\end{pmatrix}$.

This $S$ is positive definite as well. Its leading $2\times2$ block $A$ has determinant $207/225=23/25$. With $c=(1/10,-3/20)^\mathsf{T}$, direct calculation gives $c^\mathsf{T}A^{-1}c=73/1380$. The Schur complement is $1-73/1380=1307/1380>0$; hence the full matrix is positive definite.

For pair $(1,2)$, the precision entry is $-1/4$, and $(\Theta^{-1}-S)_{12}=4/15-7/15=-1/5=\lambda\operatorname{sign}(-1/4)$. For the zero entry $(1,3)$, the residual is $0-1/10=-1/10$, whose absolute value is at most $0.2$. For the zero entry $(2,3)$, it is $0-(-3/20)=3/20$, also at most $0.2$. The diagonal inverse entries equal those of $S$. Choosing subgradients $\gamma_{12}=-1$, $\gamma_{13}=-1/2$, and $\gamma_{23}=3/4$ therefore makes every KKT equation hold. By sufficiency and uniqueness, $\Theta$ is the minimizer: one edge is nonzero while the other two are zero.

Interpretation and Common Pitfalls

The KKT conditions explain how the graphical lasso creates sparsity. At a zero edge, the likelihood residual can lie anywhere inside a band of width $2\lambda$; outside that band, a zero entry cannot satisfy stationarity. At a nonzero edge, the residual is pinned to the boundary, with sign determined by the precision entry. The residual involves $\hat{\Theta}^{-1}$, so the edge decisions are coupled across the matrix rather than being independent thresholding of $S_{ij}$.

A frequent mistake is to write $|S_{ij}|\le\lambda$ as the general criterion for a zero estimate. That criterion works for testing the particular diagonal candidate, because its inverse has zero off-diagonal entries. For a general estimate the correct condition is $|(\hat{\Theta}^{-1})_{ij}-S_{ij}|\le\lambda$. Another common error is to mix penalty conventions: if the objective instead sums $|\theta_{ij}|$ only over $i<j$, its derivative with respect to a distinct symmetric off-diagonal coordinate has a different factor. State the objective before writing KKT equations. Finally, equality at the threshold is valid for a zero entry; the subgradient interval includes both endpoints.

Key takeaway: Under the objective $\operatorname{tr}(S\Theta)-\log\det(\Theta)+\lambda\sum_{i\ne j}|\theta_{ij}|$, a zero off-diagonal precision estimate is characterized by $|(\hat{\Theta}^{-1})_{ij}-S_{ij}|\le\lambda$, while a nonzero entry has signed residual exactly $\lambda$.

Check Your Understanding

Use the stated off-diagonal penalty convention in answering these questions.

Write the KKT equation for a nonzero entry $\hat{\theta}_{ij}$, including its sign.
For a zero entry, does the residual condition allow equality at $\lambda$? Explain.
Why does $|S_{ij}|\le\lambda$ test a diagonal candidate but not give the general zero-entry condition?
For the two-variable covariance matrix with diagonal entries one, what condition makes the identity matrix satisfy the off-diagonal KKT condition?
What factor-of-two issue arises if the penalty is changed from a sum over $i\ne j$ to a sum over $i<j$?