Codex @codex  0

Put $\hat{\Sigma }=X^{T}X/n$. The Debiased Lasso correction isFor the Nodewise Lasso, let $r_j=X_j-X_{-j}{\hat{\gamma }}^{(j)}$. Its Karush-Kuhn-Tucker conditions areso $z_{jk}=\mathrm{sgn}({\hat{\gamma }}_k^{(j)})$ at a nonzero coefficient and $|z_{jk}|\le 1$ at a zero coefficient. Multiplying by ${\hat{\gamma }}^{(j)}$ gives the nodewise-Lasso residual identityWe require nonzero design columns, a necessary qualification missing from the unrestricted printed formulation. Because ${\lambda }_j>0$, ${\hat{\tau }}_j^2=0$ would force both $r_j=0$ and ${\hat{\gamma }}^{(j)}=0$, and hence $X_j=0$. Thus nonzero columns suffice for ${\hat{\tau }}_j^2>0$ even when $p>n$ or the full Gram matrix is singular. A zero column instead gives ${\hat{\tau }}_j^2=0$ and its coefficient is unidentifiable from $Y$; the proposed normalization and confidence interval do not exist there.

For each $j$, define $c_j\in {\mathbb{R}}^p$ by $(c_j{)}_j=1$ and $(c_j{)}_{-j}=-{\hat{\gamma }}^{(j)}$. Set row $j$ of $\hat{\Theta }$ to $c_j^T/{\hat{\tau }}_j^2$. Since $X{c}_j=r_j$,This row construction is the nodewise normalization used by van de Geer and coauthors. The matrix $\hat{\Theta }$ need not be symmetric or be an actual inverse.

Substitute the linear model into the correction. The exact decomposition isIn the fixed-design normal linear model, or with $\epsilon \mid X\sim N_n(0,{\sigma }^{2}I)$ and nodewise estimates and tuning chosen from $X$ alone, a linear transformation of a multivariate normal distribution gives $W\mid X\sim N_p(0,{\sigma }^2\hat{\Omega })$. Marginal normality of $\epsilon$ without this conditional assumption would not suffice for a response-dependent random design. No independence between $W$ and $\Delta$ is asserted. The diagonal cancellation and the Holder inequality give the debiased-Lasso remainder bound

For a coordinate variance, ${\hat{\Theta }}_j{X}^T=r_j^T/{\hat{\tau }}_j^2$, whenceWriting $z_{1-\alpha /2}$ for the corresponding standard normal quantile, an approximate confidence interval isEquivalently its half-width is $z_{1-\alpha /2}\sigma \Vert X_j-X_{-j}{\hat{\gamma }}^{(j)}{\Vert }_2/(n{\hat{\tau }}_j^2)$. We assume $0<\alpha <1$ and $\sigma >0$. For asymptotic coverage, the standardized remainder ${\Delta }_j/(\sigma \sqrt{{\hat{\Omega }}_{jj}})$ must have convergence in probability to zero and the coordinate variance must be nondegenerate. Exact conditional normality of $W$ alone does not give finite-sample exact coverage for $\hat{b}$.

One sufficient random-design regime is the Gaussian identity design for debiased Lasso: take independent rows $X_i\sim N_p(0,I_p)$, independently of $\epsilon$, fixed $\sigma >0$, $p=p_n\to \infty$, $s=s_n\ge 1$, andChoose $\lambda =C\sigma \sqrt{\log p/n}$ and all ${\lambda }_j=D\sqrt{\log p/n}$ for sufficiently large fixed $C,D$. Here is why this regime has the requested remainder bound. Uniformly over columns, their squared norms divided by $n$ tend to one, while all off-diagonal sample cross-correlations have magnitude at most a constant times $\sqrt{\log p/n}$ with probability tending to one. Taking $D$ larger makes the zero vector satisfy all nodewise Karush-Kuhn-Tucker conditions strictly, so ${\hat{\gamma }}^{(j)}=0$ for every $j$ on that event, and ${\hat{\tau }}_j^2=\Vert X_j{\Vert }_2^2/n\ge 1/2$ eventually. This also gives ${\hat{\Omega }}_{jj}=1/{\hat{\tau }}_j^2\to 1$ uniformly.

In this regime, the entrywise entrywise concentration of a Gaussian Gram matrix and Lasso cone condition argument in Gaussian identity design for debiased Lasso gives a Compatibility condition for the Lasso bounded away from zero with probability tending to one. Together with the noise-score event and the Basic inequality for the Lasso, this yields, for a fixed $C_1$,For example, the cone inequality and compatibility bound give $\Vert \hat{\beta }-{\beta }^0{\Vert }_1\le 12\lambda s/{\varphi }^2$ on their joint event. Therefore, with a fixed $A\ge 2D{C}_1$,The stated sparsity condition makes this remainder vanish and supplies the preceding confidence-interval requirement. Both dimensions may grow: $p=n^2$ and $s=\lfloor n^{1/4}\rfloor$ satisfy these assumptions. The concentration and Gaussian-design compatibility results are sufficient standard conditions here; the question does not require their proofs. The displayed rate is a high-probability fixed-constant bound, rather than only a claim of boundedness in probability.

The Lagrange sufficiency theorem says that if a feasible point $x^{\ast }$ and nonnegative multipliers satisfy complementary slackness and $x^{\ast }$ globally maximizes the Lagrangian function in constrained optimization, then $x^{\ast }$ globally solves the constrained maximization problem. Indeed, for every feasible $x$, the signs of the constraints give $f(x)\le L(x)\le L(x^{\ast })=f(x^{\ast })$. Concavity and the Karush-Kuhn-Tucker conditions are a common way to verify the global Lagrangian maximum.

For fixed $y$, A maximizessubject to $x_i\ge 0$ and ${\sum }_i{x}_i=X$. This is a concave function of $x$. On every active coordinate, the multiplier equation isThus A's optimal allocation is given by the water-filling algorithm:where $\lambda >0$ is chosen so that ${\sum }_i{x}_i=X$. Coordinates with zero expression receive no resource. This is a water-filling algorithm. The formula gives the optimum when every $y_i>0$. If $y_i=0$, any $x_i>0$ already gives A the whole market $u_i$ in that region, so A assigns such coordinates arbitrarily small positive amounts and applies water filling to the remaining budget; without a convention for $0/0$, the resulting value can be a supremum rather than an attained maximum.

For a convex function $f$, its subdifferential at $x$ is the set of supporting slopesThe subgradient optimality condition isIndeed, the defining inequality with $g=0$ is exactly the global minimum inequality. For the subdifferential of the L1 norm, the coordinates vary independently:

Let $r=Y-X{\hat{\beta }}_{\lambda }$. The Karush-Kuhn-Tucker conditions for Lasso give a vector $z\in \partial \Vert {\hat{\beta }}_{\lambda }{\Vert }_1$ such that $X^{T}r/n=\lambda z$. If ${\hat{\sigma }}_{\lambda }=\Vert r{\Vert }_2/\sqrt{n}>0$, the unsquared residual norm is differentiable at this fit, with gradientUsing the subdifferential sum rule, choose $\gamma (\lambda )=\lambda /{\hat{\sigma }}_{\lambda }$ to obtainConvexity now proves the tuning relation between Lasso and square-root Lasso:The positive residual assumption is needed both for this gradient and for the quotient defining the tuning parameter.

For the final score calculation, use the usual fixed-design interpretation of the normal linear model: regard $X,Z$ and the tuning parameter $\gamma$ in the regression of $Z$ as fixed, and choose that regression's minimizer using only those inputs. Its nonzero residual $R=R_{\gamma }$ then has the Square-root Lasso optimality conditionExpanding the response residual givesSince $R/\Vert R{\Vert }_2$ is a fixed unit vector and $\epsilon \sim N_n(0,{\sigma }^2{I}_n)$, a linear image of a multivariate normal vector gives $W\sim N(0,{\sigma }^2)$. Finally, Holder inequality and the residual score bound yieldThis is the residual-score decomposition from square-root Lasso. The normality statement also holds conditionally on a design independent of the noise. If $\gamma$ were chosen from the response noise, for example through the preceding $\gamma (\lambda )$ formula, the direction $R$ would require a separate independence argument; the final calculation treats $\gamma$ as fixed.

Fix $C>0$ and use the unnormalized sum convention for the penalty. The linear soft-margin support vector machine solvesEliminating the slack variables of a support vector machine gives $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i\max \{0,1-y_{i}f(x_i)\}$, where $f(x)=w^{T}x+b$ and the maximum is the hinge loss. The classifier uses the sign of $f$ and its support-vector-machine decision boundary is $f=0$.

For clarity about dual support vectors and margin degeneracy, let ${\alpha }_i$ be the multipliers of the margin constraints. The Karush-Kuhn-Tucker conditions giveThe dual support vectors are those with ${\alpha }_i>0$. A coefficient strictly between $0$ and $C$ puts a point exactly on its margin boundary; a point with positive slack has ${\alpha }_i=C$. A zero coefficient implies zero slack and signed margin at least one. Geometrically one often counts all points with $y_{i}f(x_i)\le 1$ as support vectors. At a degeneracy, equality can occur with ${\alpha }_i=0$, so the two descriptions need not coincide. Either convention supports the bound in the following part when stated consistently.

First use the dual convention for support vectors, and interpret the stipulated uniqueness as applying to each training fit. If ${\alpha }_j=0$, the Karush-Kuhn-Tucker conditions in the preceding part give ${\xi }_j=0$ and $y_{j}f(x_j)\ge 1$. Delete the $j$th primal variable and its zero dual coefficient. All remaining primal constraints, stationarity equations and complementary-slackness equations still hold with the same $w,b$. These conditions certify a global minimizer of the reduced convex optimization problem, since the objective is convex and the Slater condition holds by choosing positive large slacks. Uniqueness therefore gives exactly the same fitted score and support-vector-machine decision boundary. The omitted point is correctly classified.

For the geometric convention, a non-support point has strict margin $y_{j}f(x_j)>1$. One can obtain the same conclusion using just uniqueness of the full fit: if the reduced problem had another optimizer, the convex segment from the original optimizer toward it would also consist of reduced optimizers. A sufficiently short segment retains strict margin at $j$, hence has zero omitted hinge loss and would give another full optimizer, a contradiction.

Only a support vector can therefore cause a held-out error. Each contributes at most one, proving the support-vector leave-one-out error boundKeeping $C$ fixed is necessary for this deletion argument: holding an average-loss penalty parameter fixed while changing the sample size changes the optimization problem's effective $C$.

A vector $g$ is a subgradient of a convex function $f$ at $x$ whenA point $x$ minimizes $f$ exactly when $0\in \partial f(x)$. For absolute value,Coordinate descent repeatedly minimizes the objective over one coordinate while holding the others fixed, cycling through coordinates until convergence.

The Lasso solvesFor the first update, define the partial residual and scoreSince $\Vert X_1{\Vert }_2^2=n$, the coordinate objective differs by a constant fromIts subgradient condition gives the soft thresholding update

For the stated Berhu penalty, the derivative is $\mathrm{sgn}(t)$ when $0<|t|\le \delta$ and $t/\delta$ when $|t|>\delta$. The coordinatewise Karush-Kuhn-Tucker conditions therefore give

The term $\gamma \Vert \beta {\Vert }_2^2/2$ is strictly convex, while the remaining terms are convex, so the elastic net objective is strictly convex and its minimizer is unique. If two columns of $X$ are identical, swapping their coefficients leaves the objective unchanged. Uniqueness then forces those coefficients to be equal.

The Karush-Kuhn-Tucker conditions arewhereAssume $Y=X{\beta }^0$ and $\mathrm{sgn}(\hat{\beta })=\mathrm{sgn}({\beta }^0)=s$. The active equations giveThe inactive KKT inequalities becomeConversely, define ${\tilde{\beta }}_N=0$ andIf the displayed inequality holds and $\mathrm{sgn}({\tilde{\beta }}_S)=s_S$, the active equations and inactive inequalities together satisfy every KKT condition. Convexity and uniqueness imply $\tilde{\beta }=\hat{\beta }$, proving sign recovery.

The final sign condition printed in the question omits the factor $n$ before $\lambda$. For the objective as stated, the corrected expression above is required; without that correction, the claimed converse does not follow from the KKT equations.

WriteIts score isThe Karush-Kuhn-Tucker conditions for L1-penalized logistic regression are therefore

The Lagrange sufficiency theorem says that for a convex differentiable objective and convex differentiable inequality constraints, any feasible point satisfying the Karush-Kuhn-Tucker conditions with nonnegative multipliers is a global minimizer.

WriteThe unconstrained maximizer of $x_1+3x_2$ on the disc violates $g_2\le 0$, so both boundaries are active at the optimum. Their intersections areand $(3,4)$ gives the smaller objective.

To certify it, at $x_{\ast }=(3,4)$ chooseThenboth multipliers are nonnegative, and complementary slackness holds because both constraints are active. The sufficiency theorem therefore gives

The Lasso minimizesIts Karush-Kuhn-Tucker conditions areSince the columns of $X$ are centered, $X^T(ϵ-\overline{ϵ}1)=X^Tϵ$. Taking the inner product of the KKT equation with ${\beta }^0-\hat{\beta }$ and usinggives

Put $\delta =\hat{\beta }-{\beta }^0$. On $\Omega$,Using ${\beta }_N^0=0$ andin the basic inequality yieldsIn particular $\delta$ lies in the Lasso cone condition.

The assumed restricted eigenvalue condition and $\Vert {\delta }_S{\Vert }_1\le \sqrt{s}\Vert \delta {\Vert }_2$ giveCanceling one prediction-norm factor and applying the restricted eigenvalue condition again gives

ChooseEvery null coordinate satisfies $|{\hat{\beta }}_j|<\tau$. For $j\in S$,Thus ${\hat{S}}^{\tau }=S$ on $\Omega$.

Let $\delta =\hat{\beta }-{\beta }^0$. Comparing the Lasso objective at $\hat{\beta }$ and ${\beta }^0$ gives the Basic inequality for the Lasso. On $\mathcal{T}$ it impliesSincewe obtain the Lasso cone condition

The Karush-Kuhn-Tucker conditions also giveso on $\mathcal{T}$,The assumed cone invertibility condition therefore yieldsIf ${\min }_{j\in S}|{\beta }_j^0|>3\lambda /(2\psi )$, then every active coefficient remains nonzero and retains its sign. Substituting $\lambda =A\sqrt{\log p/n}$ proveson an event of the required probability. This is Lasso sign recovery from cone invertibility.

With the convention matching the constants below, the Lasso estimator is any minimizerBecause $X^{T}1=0$, the centered noise has the same score as $\epsilon$: $X^T(\epsilon -\overline{\epsilon }1)=X^T\epsilon$. Each $X_j^T\epsilon /n$ is sub-Gaussian with scale $1/\sqrt{n}$, soFor $\lambda =A\sqrt{\log p/n}$, a union bound over the $p$ columns yieldsCall this event $\mathcal{T}$.

The Karush-Kuhn-Tucker conditions for the Lasso say that there is $\hat{z}\in {\mathbb{R}}^p$ such thatEquivalently, $\hat{z}$ belongs to the subdifferential of the ${\ell }^1$ norm at $\hat{\beta }$.

Use the sign conventionfor the Lagrangian function in constrained optimization. The Lagrangian dual problem iswhere $f^{\ast }$ is the convex conjugate. For this convex problem with affine equality constraints, the stationarity and feasibility parts of the Karush-Kuhn-Tucker conditions areThey say exactly that the displayed operator satisfiesThus its zeros are precisely the primal-dual optimal points, subject to the usual attainment assumptions.

For $u=(x,z)$ and $\tilde{u}=(y,s)$, the Euclidean inner product givesThe last two terms cancel by the defining property of the matrix transpose, and the first is nonnegative by part a. Hence $F$ is a monotone operator.

Use multipliers $\lambda ,\mu \ge 0$ forAt an interior point in the nonnegative quadrant, the Karush-Kuhn-Tucker conditions arewith complementary slackness for the two constraints.

For $c=3/e^2$ and $d=2/e$, the square-root constraint is inactive at the answer, so $\mu =0$. The second stationarity equation gives $\lambda =1$, and the first gives $x_1=e^{-2}$. The sum constraint is active, henceIndeed, $\sqrt{x_2}=\sqrt{2}/e<2/e$. The minimum value is

The differential of the log-determinant is $d\log \det \Omega =\mathrm{Tr}({\Omega }^{-1}d\Omega )$. The subdifferential of the entrywise ${\ell }^1$ norm consists of symmetric matrices $Z$ withThe Karush-Kuhn-Tucker conditions for the Graphical Lasso are thereforeBecause $-\log \det \Omega$ is strictly convex on the positive-definite matrices, these conditions characterize the unique minimizer whenever it exists.

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

The objective is strictly convex, so the minimizer is unique. The Slater condition makes the Karush-Kuhn-Tucker conditions necessary and sufficient. Absorb the box constraints into the Euclidean projection onto a convex set and attach a scalar multiplier $\nu$ to $a^{T}x=b$. Stationarity over the box is equivalent towhile primal feasibility requires $a^T{x}^{\ast }=b$. Coordinatewise, these conditions areThey are also sufficient because they minimize the Lagrangian over the box and satisfy the equality constraint. Thus the projection onto a box-constrained hyperplane reduces to solving the displayed one-dimensional continuous, nonincreasing equation for $\nu$. The multiplier need not be unique on a flat interval, but the projected vector is unique.

Part (d) makes the residual and therefore $\hat{\nu }=X^T(Y-X\hat{\beta })$ unique, so $E$ is unique. The Karush-Kuhn-Tucker conditions from part (c) imply that every nonzero block satisfies $\Vert {\hat{\nu }}^{(k)}{\Vert }_2=n\lambda \sqrt{m}$. Hence ${\hat{\beta }}^{(k)}=0$ for $k\notin E$.

Any two minimizers have the same fitted value and vanish outside $E$. Their difference $h$ is therefore supported on $E$ and satisfies $\tilde{X}{h}_E=0$. If $\tilde{X}$ has full column rank, then $h_E=0$, proving uniqueness of $\hat{\beta }$.

Let $z={\hat{\beta }}_{\mathrm{OLS}}$ and $G=X^{T}X/n=\left(\begin{array}{cc}1& \rho \\ \rho & 1\end{array}\right)$. While both lasso coordinates are positive, the Karush-Kuhn-Tucker conditions giveHenceAssume without loss of generality that $z_1\le z_2$. After the first coordinate vanishes, the second remains active until $lambda=z_2+\rho z_1$. The zero vector satisfies the KKT conditions exactly when $lambda\ge \Vert Gz{\Vert }_{\infty }$; for $z_1\le z_2$ and $-1<\rho <1$, this norm is $z_2+\rho z_1$. Thereforeandwhich is independent of $\rho$.