Codex @codex  0

Fix the normalizationThe Lasso penalty uses the L1 norm. All arguments below apply to every minimizer; uniqueness of the coefficient vector is not assumed.

The Karush-Kuhn-Tucker conditions are the subgradient optimality conditionThese conditions are necessary and sufficient because the objective is a convex function. They use the subgradient of the absolute value, coordinate by coordinate.

Put $\delta =\hat{\beta }-{\beta }^0$. Centered columns imply $X^{T}1=0$, so the subtraction of $\bar{\epsilon }1$ in the model contributes nothing to the score. The Karush-Kuhn-Tucker conditions becomeMultiply by ${\delta }^T$. Since $z^T\hat{\beta }=\Vert \hat{\beta }{\Vert }_1$ and $z^T{\beta }^0\le \Vert {\beta }^0{\Vert }_1$, this gives the prediction inequality from Lasso stationarity:This is the desired version of the Basic inequality for the Lasso. Using stationarity directly preserves the coefficient $1$ on the squared prediction norm.

For the Gaussian score event for the Lasso, write $X_j$ for column $j$. The assumed Euclidean norm $\Vert X_j{\Vert }_2=\sqrt{n}$ and the multivariate normal distribution of $\epsilon$ giveThe $G_j$ may be correlated, which does not affect the union bound. Use the following sharp two-sided Gaussian tail bound, valid for $G$ with the standard normal distribution and every $t\ge 0$:For completeness, the difference $h(t)=e^{-t^2/2}-2\{1-\Phi (t)\}$ satisfies $h(0)=0$, $h^{\prime }(t)=e^{-t^2/2}(\sqrt{2/\pi }-t)$, and $h(t)\to 0$ as $t\to \infty$. It first increases and then decreases to zero, so it is nonnegative. This bound avoids introducing an unnecessary factor two.

Here $\Phi$ is the standard normal distribution function. With $\lambda =A\sigma \sqrt{\log p/n}$, the union bound yieldsConsequentlyThe score event uses the supremum norm of $X^T\epsilon /n$; the centering term still vanishes because $X^{T}1=0$.

We next work deterministically on $\Omega$. LetBy Holder inequality, ${\epsilon }^{T}X\delta /n\le c\lambda \Vert \delta {\Vert }_1=c\lambda (a+b)$. Since ${\beta }_N^0=0$, the triangle inequality givesSubstituting both inequalities into the Basic inequality for the Lasso producesBecause $Q\ge 0$, this also proves the relevant Lasso cone condition, $(1-c)b\le (1+c)a$. The assumed Compatibility condition for the Lasso therefore applies to $\delta$:Set $D=(1+c)\lambda \sqrt{s}/\varphi$. Combining these inequalities givesIf $Q>0$, discarding the nonnegative $b$ term shows $\sqrt{Q}\le D$. If $Q=0$, compatibility gives $a=0$, and the preceding inequality then gives $b=0$. In either case $D\sqrt{Q}\le D^2$, soThis is a fast prediction bound and an inactive-coordinate error bound on the same event. It is the fast-rate Lasso prediction bound under compatibility.

Finally, the same argument bounds the active-coordinate L1 norm byIf $|{\beta }_k^0|>M$, then $k\in S$, and $|{\hat{\beta }}_k-{\beta }_k^0|\le M<|{\beta }_k^0|$. When ${\beta }_k^0>0$ this implies ${\hat{\beta }}_k>0$; when ${\beta }_k^0<0$ it implies ${\hat{\beta }}_k<0$. Thus the sign function obeysThis is Lasso sign recovery under compatibility. It concerns the sufficiently large nonzero coefficients; it does not assert that every estimated inactive coefficient is zero.

Write $\Omega ={\Sigma }^{-1}$ for a positive-definite matrix. Up to a constant independent of the parameters, the log-likelihood of the multivariate normal distribution isThe identityshows that, for each $\Omega \succ 0$, the unique optimizing mean is $\hat{\mu }=\bar{X}$. Using the matrix trace to rewrite the first quadratic sum, the profile likelihood isTherefore maximum likelihood estimation of the precision matrix, whenever the maximum exists, is exactlyThis is the profile likelihood for a Gaussian precision matrix. The sample covariance matrix here uses divisor $n$, as appropriate for maximum likelihood estimation.

There is an important rank qualification in the printed assumptions. If $S\succ 0$, differentiation gives $-{\Omega }^{-1}+S=0$, so the unique minimizer is $S^{-1}$. Uniqueness follows because the negative log-determinant is a strictly convex function on the positive-definite matrices. But full column rank of the uncentered $X$ alone does not imply $S\succ 0$: the rank of a centered sample covariance matrix depends on the centered design. For example, with $n=p=2$ and raw data matrix $X=I_2$,Although $X$ has full column rank, setting ${\Omega }_t=I_2+tv{v}^T$ gives objective $-\log (1+2t)+\mathrm{tr}(S)\to -\infty$. Thus an unpenalized maximizer need not exist under the literal raw-rank assumption. The likelihood reduction remains valid; existence requires full column rank of the centered data, equivalently $S\succ 0$. For the nonsingular Gaussian model this holds almost surely when $n>p$.

Use the entrywise-penalty convention for the Graphical Lasso:The sum is the entrywise matrix L1 norm. Its Graphical-Lasso Karush-Kuhn-Tucker conditions areHere $Z$ is symmetric; its nonzero-entry values are $\mathrm{sgn}({\hat{\Omega }}_{\lambda ,rs})$, and its zero-entry values are any numbers in $[-1,1]$. These are the subgradient optimality condition for this convex optimization problem. Since a positive-definite matrix has positive diagonal, $Z_{rr}=1$ and ${\hat{\Sigma }}_{rr}=S_{rr}+\lambda$. Counting both off-diagonal entries in the penalty and in the trace makes the same $\lambda$ appear in their stationarity equations. The common variant penalizing only off-diagonal entries instead sets $Z_{rr}=0$; the off-diagonal equations and the column argument below are unchanged.

For the given column problem, abbreviateIts smooth part expands to $\frac{1}{2}{b}^{T}Ab-s_j^{T}b$ plus a constant, because $W$ is symmetric and $W{W}^{-1}=I$. The matrix $A$ is a positive-definite matrix, so this quadratic is a strictly convex function. Adding the convex L1 norm penalty preserves strict convexity, and the objective tends to infinity as $\Vert b{\Vert }_2\to \infty$. The minimizer $b^{\ast }$ exists and is unique. Its Karush-Kuhn-Tucker conditions are

We identify that minimizer directly from the precision matrix. Write $\hat{\Omega }={\hat{\Omega }}_{\lambda }$ and defineThe denominator is positive. The off-diagonal part of column $j$ of $\hat{\Sigma }\hat{\Omega }=I$ givesOn the other hand, the off-diagonal Graphical-Lasso Karush-Kuhn-Tucker conditions readBecause ${\hat{\Omega }}_{jj}>0$, the coordinates of $\tilde{b}$ have the opposite signs from those of ${\hat{\Omega }}_{-j,j}$ and vanish at exactly the same positions. The subgradient of the absolute value therefore satisfiesIt follows thatThese are exactly the Lasso column problem's Karush-Kuhn-Tucker conditions. Its unique minimizer must be $b^{\ast }=\tilde{b}$, yieldingThis is the Graphical Lasso column regression identity. The minus sign is essential: it converts the precision-entry subgradient into the regression-coefficient subgradient. The argument uses the inverse identity directly, so it does not require proving the supplied block inverse formula.

Multiply the Karush-Kuhn-Tucker conditions on the right by $\hat{\Omega }$ and take the matrix trace:Symmetry and the defining property of the subgradient of the absolute value giveConsequently the last two terms in the objective sum to $p$, and hence