A Primal-Dual Witness Proof Of Graph Selection Consistency

Why a Primal-Dual Witness Is Needed

A sparse precision-matrix estimate can have no false edges and still fail to recover the graph: it may omit an edge that is truly present. A support-recovery proof must therefore establish two distinct facts. The coordinates outside the true support must satisfy the graphical-lasso KKT inequalities, and every true edge must remain nonzero with its correct sign. The primal-dual witness argument constructs a candidate estimate by solving first on the true support, then checks whether that candidate satisfies the full optimization problem.

The proof is useful because it separates the roles of the assumptions. An incoherence condition limits how much active coordinates influence the excluded coordinates. A residual condition controls the finite-sample and nonlinear errors in that calculation. Neither condition, by itself, prevents the restricted estimate from dropping a true edge; that must be ruled out explicitly.

Setup and Notation

Let \(X\) be a \(p\)-dimensional Gaussian random vector with mean zero, covariance matrix \(\Sigma^*\), and positive-definite precision matrix \(\Theta^*=(\Sigma^*)^{-1}\). Let \(S\) be the sample covariance matrix and let \(\lambda>0\). We use the graphical-lasso objective

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

The penalty sums over ordered off-diagonal entries, so each undirected edge is counted twice. The KKT equations below use the corresponding symmetric matrix subgradient convention.

Definition: Let \(T=\{(i,j):\Theta^*_{ij}\ne0\}\), including every diagonal coordinate, and let \(T^c\) be its complement among matrix coordinates. The true edge set consists of the off-diagonal coordinates in \(T\), with \((i,j)\) and \((j,i)\) representing the same undirected edge. For any matrix \(M\), \(P_T M\) retains entries in \(T\) and sets the others to zero; \(P_{T^c}\) is defined analogously. Write \(\|M\|_\infty=\max_{i,j}|M_{ij}|\) and \(W=S-\Sigma^*\).

All matrix spaces below are restricted to symmetric matrices. Define the population Hessian operator \(\Gamma(U)=\Sigma^*U\Sigma^*\). Its restriction to matrices supported on \(T\), followed by projection onto \(T\), is \(\Gamma_{TT}U=P_T\Gamma(U)\). This operator is invertible on that finite-dimensional space: for any nonzero symmetric \(U\),

\langle U,\Gamma(U)\rangle_F =\operatorname{tr}(U\Sigma^*U\Sigma^*) =\left\|(\Sigma^*)^{1/2}U(\Sigma^*)^{1/2}\right\|_F^2>0.

Here \(\langle A,B\rangle_F=\operatorname{tr}(A^\mathsf{T}B)\). The cross-support operator and its induced entrywise norm are

A=\Gamma_{T^cT}(\Gamma_{TT})^{-1}, \qquad \|A\|_{\infty\to\infty} =\sup_{\substack{U=P_TU\\ \|U\|_\infty\le1}}\|AU\|_\infty,

where \(\Gamma_{T^cT}U=P_{T^c}\Gamma(U)\). This definition makes the incoherence condition precise without relying on a particular coordinate vectorization convention.

The Restricted Problem and Its Expansion

The restricted problem minimizes the graphical-lasso objective over positive-definite matrices constrained to have zeros on \(T^c\). Denote a restricted solution by \(\widetilde{\Theta}\), and set \(\Delta=\widetilde{\Theta}-\Theta^*\). Since both matrices have zeros on \(T^c\), \(P_{T^c}\Delta=0\). The restricted KKT equations hold on \(T\), but they say nothing yet about whether the full problem’s KKT inequalities hold on \(T^c\).

For the expansion, define

R(\Delta)=\Sigma^*\Delta\Sigma^*\Delta\widetilde{\Theta}^{-1}.

This is a remainder term, not an assumed approximation. The inverse identity giving rise to it follows by applying the resolvent identity twice. With \(\widetilde{\Theta}=\Theta^*+\Delta\), it is

\widetilde{\Theta}^{-1} =\Sigma^*-\Sigma^*\Delta\Sigma^* +\Sigma^*\Delta\Sigma^*\Delta\widetilde{\Theta}^{-1} =\Sigma^*-\Gamma(\Delta)+R(\Delta).

In particular, the restricted KKT equations can be written

P_T\{W+\Gamma(\Delta)-R(\Delta)+\lambda\widetilde Z\}=0,

where \(\widetilde Z\) is a subgradient of the off-diagonal penalty at \(\widetilde{\Theta}\): it is zero on the diagonal, equals \(\operatorname{sign}(\widetilde{\Theta}_{ij})\) at nonzero off-diagonal entries, and belongs to \([-1,1]\) at zero off-diagonal entries. Solving on \(T\) gives

\Delta =(\Gamma_{TT})^{-1} \{-P_TW+P_TR(\Delta)-\lambda\widetilde Z\}.

The exact remainder identity above is important: replacing it by a first-order approximation without bounding its error would not establish a finite-sample dual-feasibility claim.

A Deterministic Primal-Dual Witness Theorem

Theorem: Suppose the restricted problem has a positive-definite solution \(\widetilde{\Theta}\). Assume that for some \(0<\alpha\le1\):

(1) \(\|A\|_{\infty\to\infty}\le1-\alpha\);
(2) \(\|AW_T-W_{T^c}\|_\infty\le\alpha\lambda/4\), where \(W_T=P_TW\) and \(W_{T^c}=P_{T^c}W\);
(3) \(\|R_{T^c}(\Delta)-A R_T(\Delta)\|_\infty\le\alpha\lambda/4\);
(4) \(\operatorname{sign}(\widetilde{\Theta}_{ij})=\operatorname{sign}(\Theta^*_{ij})\) for **every** true off-diagonal edge \((i,j)\in T\).

Then \(\widetilde{\Theta}\) is the unique solution of the full graphical-lasso problem, and its off-diagonal support is exactly the true edge set.

Conditions (2) and (3) are deterministic bounds; in an application, probabilistic arguments can be used to show that they hold with high probability. Condition (4) is a separate sign-persistence requirement. It includes the assertion that each true edge is nonzero in the restricted solution.

Proof. Define the candidate dual subgradient on the excluded coordinates by the full KKT equation:

\widehat Z_{T^c} =\frac{P_{T^c}(\widetilde{\Theta}^{-1}-S)}{\lambda}.

The restricted KKT equation already supplies \(\widehat Z_T=\widetilde Z_T\), with diagonal entries zero and \(\|\widehat Z_T\|_\infty\le1\). Using the inverse expansion and the expression for \(\Delta\), the excluded-coordinate certificate becomes

\begin{aligned} \widehat Z_{T^c} &=\frac{-W_{T^c}-\Gamma_{T^cT}\Delta+R_{T^c}(\Delta)}{\lambda}\\ &=A\widehat Z_T+ \frac{AW_T-W_{T^c}+R_{T^c}(\Delta)-A R_T(\Delta)}{\lambda}. \end{aligned}

For the second equality, substitute \(\Delta=(\Gamma_{TT})^{-1}(-W_T+R_T(\Delta)-\lambda\widehat Z_T)\) into \(\Gamma_{T^cT}\Delta\). The resulting signs give \(+AW_T\), \(-AR_T(\Delta)\), and \(+\lambda A\widehat Z_T\) in the numerator.

Now apply the three norm bounds and \(\|\widehat Z_T\|_\infty\le1\):

\begin{aligned} \|\widehat Z_{T^c}\|_\infty &\le \|A\|_{\infty\to\infty}\|\widehat Z_T\|_\infty +\frac{\|AW_T-W_{T^c}\|_\infty+ \|R_{T^c}(\Delta)-AR_T(\Delta)\|_\infty}{\lambda}\\ &\le 1-\alpha+\frac{\alpha}{4}+\frac{\alpha}{4} =1-\frac{\alpha}{2}<1. \end{aligned}

Thus every excluded off-diagonal coordinate has a valid penalty subgradient strictly between \(-1\) and \(1\). By construction, the restricted KKT equations hold on \(T\), and the definition of \(\widehat Z_{T^c}\) makes the full KKT equation \(S-\widetilde{\Theta}^{-1}+\lambda\widehat Z=0\) hold on \(T^c\) as well. The KKT conditions are sufficient for optimality of this convex objective on the positive-definite cone, so \(\widetilde{\Theta}\) is a full-problem optimizer. The term \(-\log\det(\Theta)\) is strictly convex on that cone; adding a linear function and a convex penalty preserves strict convexity. Hence the optimizer is unique. Strict dual feasibility forces every coordinate in \(T^c\) to be zero, while condition (4) forces every true edge in \(T\) to be nonzero. Therefore the off-diagonal support is exactly the true edge set. \(\square\)

Worked Examples

Worked Example: A Two-Variable Empty Graph

Take \(p=2\), \(\Theta^*=I_2\), and an observed covariance \(S=\begin{pmatrix}1&0.01\\0.01&1\end{pmatrix}\), with \(\lambda=0.05\). This \(S\) is positive definite because its eigenvalues are \(1.01\) and \(0.99\). The true support \(T\) consists of the two diagonal coordinates.

The restricted solution is \(\widetilde{\Theta}=I_2\): each diagonal KKT equation is \(S_{ii}-(\widetilde{\Theta}^{-1})_{ii}=1-1=0\). Here \(\Sigma^*=I_2\), so \(\Gamma(U)=U\); consequently \(A=0\) and \(R(\Delta)=0\). With \(\alpha=1\), the incoherence condition holds. Also \(W_T=0\), \(W_{T^c}\) has off-diagonal entries \(0.01\), and \(\|AW_T-W_{T^c}\|_\infty=0.01\le\alpha\lambda/4=0.0125\).

The witness gives \(\widehat Z_{12}=\widehat Z_{21}=-0.01/0.05=-0.2\), strictly inside \([-1,1]\). The true graph is empty and the full solution has no edge, as certified by the theorem.

Worked Example: A True Edge That Persists

Let \(p=3\) and \(\Theta^*=\begin{pmatrix}1&0.2&0\\0.2&1&0\\0&0&1\end{pmatrix}\). Set \(S=\Sigma^*=(\Theta^*)^{-1}\) and \(\lambda=0.05\). The upper \(2\times2\) covariance block has diagonal \(s=1/(1-0.2^2)=25/24\) and off-diagonal \(-0.2s=-5/24\). The third variable is independent of the first two.

The restricted problem retains the edge \(12\) and all diagonal coordinates. By symmetry its first block has the form \(\widetilde{\Theta}_{1:2,1:2}=\begin{pmatrix}a&b\\b&a\end{pmatrix}\). For \(b>0\), its diagonal KKT equation is \(s=a/(a^2-b^2)\), and its off-diagonal equation is \(-0.2s+b/(a^2-b^2)+\lambda=0\). Put \(c=0.2-\lambda/s=0.152\). These equations are satisfied by \(a=0.96/(1-c^2)\) and \(b=ca\): indeed \(a^2-b^2=a^2(1-c^2)\), so \(a/(a^2-b^2)=1/[a(1-c^2)]=1/0.96=s\); also \(b/(a^2-b^2)=c/0.96\), giving \(-0.2s+c/0.96+0.05=0\). Numerically, \(a\approx0.9827\) and \(b\approx0.1494>0\); the block is positive definite since \(a>|b|\). The third diagonal entry is \(1\).

The restricted edge has the same positive sign as \(\Theta^*_{12}=0.2\). Since the covariance and precision are block diagonal between variables \(1,2\) and variable \(3\), \(\Gamma_{T^cT}=0\), so \(A=0\); the excluded-coordinate residual is also zero. The witness therefore has zero excluded dual coordinates. Both the true edge and the absence of edges to variable \(3\) are certified.

Worked Example: Incoherence Does Not Prevent a True Edge From Disappearing

Let \(\Theta^*=\begin{pmatrix}1&0.2&0\\0.2&1&0\\0&0&1\end{pmatrix}\), take \(S=\Sigma^*=(\Theta^*)^{-1}\), and set \(\lambda=0.25\). In the restricted problem, the diagonal candidate is \(\widetilde{\Theta}=\operatorname{diag}(0.96,0.96,1)\), because \(S_{11}=S_{22}=25/24\) and \(1/S_{11}=1/S_{22}=0.96\). Its restricted off-diagonal KKT condition on edge \(12\) holds: \(S_{12}=-5/24\), so \(|S_{12}|=5/24\approx0.20833<0.25\). The required subgradient there is \(z_{12}=z_{21}=5/6\), within \([-1,1]\).

The true edge \(12\) has been removed by the restricted solution. Yet the excluded coordinates are edges \(13\) and \(23\), which have zero cross-Hessian interaction with the coordinates in \(T\); thus \(A=0\). Their noise and remainder terms are zero because the third variable is independent and \(S=\Sigma^*\). Strict dual feasibility on those excluded coordinates therefore holds. But the sign condition on every true edge fails: \(\widetilde{\Theta}_{12}=0\), not a nonzero value with sign \(+1\). The hypotheses of the theorem are not all satisfied, and exact recovery cannot be concluded.

What the Conditions Do—and Do Not—Guarantee

The incoherence bound says that the Hessian’s transfer from active to excluded coordinates is not too strong in the specified norm. Combined with the noise and remainder bounds, it leaves a strict margin below one for the excluded-coordinate subgradient. This is the dual part of the argument: it rules out false edges in the optimizer certified by the witness.

The primal part is different. A restricted optimizer can set a true edge to zero while still satisfying its restricted KKT equations, as the last example shows. Incoherence and strict dual feasibility concern excluded coordinates; they do not supply the missing sign persistence on true edges. In applications, that persistence must be established from additional bounds on the restricted solution, rather than inferred from dual feasibility.

A common mistake is to say that the restricted estimate’s nonzero signs agree with the true signs and conclude that its support is correct. That statement only compares coordinates that the estimate has already kept: if it drops a true edge, the comparison says nothing about that edge. The needed condition is explicitly \(\operatorname{sign}(\widetilde{\Theta}_{ij})=\operatorname{sign}(\Theta^*_{ij})\) for every true off-diagonal edge \((i,j)\in T\). Since the right-hand side is nonzero, this also requires the restricted estimate to retain every true edge.

Key takeaway: The primal-dual witness certifies exact graph recovery only when the restricted solution has the correct nonzero signs on every true edge and its constructed dual variables are strictly feasible on every excluded edge.

Check Your Understanding

Use the support, KKT, and witness definitions above to answer these questions.

Why does the graphical-lasso penalty convention here count each undirected edge twice, and how is that reflected in the matrix KKT subgradient?
In the witness theorem, what does the strict bound \(\|\widehat Z_{T^c}\|_\infty<1\) establish?
Explain why \(\Gamma_{TT}\) is invertible on the symmetric matrices supported on \(T\).
Which terms in the excluded-coordinate witness formula are controlled by the noise and remainder assumptions?
Why is agreement of signs only on the restricted estimate’s nonzero edges insufficient for exact support recovery?