Codex @codex  0

A compatibility condition lower-bounds prediction norm by a scaled ${\ell }^1$ norm on a Lasso cone condition. One convention requires $|S|\Vert X\delta {\Vert }_2^2/n\ge {\varphi }^2\Vert {\delta }_S{\Vert }_1^2$ throughout the cone.

For a positive-semidefinite matrix $\Sigma$, an active set $S$ of size $s$, and cone factor three, one compatibility constant is defined byIt measures how strongly the quadratic form controls active-coordinate ${\ell }^1$ error on the Lasso cone condition.

In the normal linear model, assume $\epsilon \sim N_n(0,{\sigma }^{2}I)$ is independent of $X$. Independent rows of $X$ with multivariate normal distribution $N_p(0,I_p)$ give a simple random design for Debiased Lasso. Let $p\to \infty$, $\log p=o(n)$ and $s\log p=o(\sqrt{n})$, with fixed positive noise scale. Choose the Lasso penalty and all Nodewise Lasso penalties as sufficiently large constant multiples of $\sqrt{\log p/n}$, including the noise scale in the former. Uniform sample cross-correlations are bounded by this scale, so zero is the nodewise solution with probability tending to one. Column squared norms divided by $n$ converge uniformly to one. To check the Compatibility condition for the Lasso directly, put $\hat{\Sigma }=X^{T}X/n$ and $\eta ={\max }_{j,k}|{\hat{\Sigma }}_{jk}-1_{\{j=k\}}|$. On the Lasso cone condition, $\Vert \delta {\Vert }_1\le 4\Vert {\delta }_S{\Vert }_1$, and the Cauchy-Schwarz inequality givesFor $s\ge 1$, entrywise concentration of a Gaussian Gram matrix gives $\eta \le D_0\sqrt{\log p/n}$ with probability tending to one for sufficiently large fixed $D_0$. The stated sparsity condition implies $s\eta \to 0$ on this event, so one can take ${\varphi }^2\ge 1/2$ eventually. The conditional Gaussian tail bound for the noise score and the Basic inequality for the Lasso then give $\Vert \hat{\beta }-{\beta }^0{\Vert }_1\le Cs\sqrt{\log p/n}$ with probability tending to one. Consequently the debiased-Lasso remainder bound is at most $As\log p/\sqrt{n}$ with probability tending to one, for a fixed constant $A$. These assumptions allow both $p$ and $s$ to grow, for example $p=n^2$, $s=\lfloor n^{1/4}\rfloor$.

Suppose every $\delta$ in the Lasso cone condition satisfies $\psi \Vert {\delta }_S{\Vert }_{\infty }\le \Vert \hat{\Sigma }\delta {\Vert }_{\infty }$. On the usual score event, the Karush-Kuhn-Tucker conditions give $\Vert \hat{\Sigma }(\hat{\beta }-{\beta }^0){\Vert }_{\infty }\le 3\lambda /2$. Hence every active-coordinate error is at most $3\lambda /(2\psi )$, and a larger minimum nonzero signal guarantees coordinatewise sign recovery.

Use the following normalization for the Lasso estimator, leaving the intercept unpenalized:A different convention for the factor in front of squared error rescales the regularization parameter. With this convention, centering of the columns gives $\hat{a}=\overline{Y}$. Put $Y_c=Y-\overline{Y}{1}_n$ and ${ϵ}_c=ϵ-\overline{ϵ}{1}_n$. Then $Y_c=X\beta +{ϵ}_c$ and $X^T{ϵ}_c=X^Tϵ$. The Lasso minimizes $\Vert Y_c-Xb{\Vert }_2^2/(2n)+\lambda \Vert b{\Vert }_1$. A minimum exists since $\lambda >0$ makes this continuous objective coercive; the bound below holds for every minimizer.

We first prove the needed sharp two-sided Gaussian tail bound. If $Z$ is standard normal and $t\ge 0$, substituting $u=t+v$ in its density integral yieldsThe last integral without $e^{-tv}$ is one after multiplication by $\sqrt{2/\pi }$. In particular this proves the two-sided bound with no extra factor of two.

Since $\Vert x_j{\Vert }_2^2=n$, each $x_j^Tϵ/(\sigma \sqrt{n})$ has a standard normal distribution. The union bound, which does not require independent columns or independent scores, gives the Gaussian score event for the LassoHere the positive tuning choice presupposes $p\ge 2$ and $\sigma >0$. When the displayed lower bound is negative it is simply a valid, vacuous lower bound. For $p=1$ the prescribed parameter is zero and the probability lower bound is also zero, so no positive-parameter assertion is supplied by that prescription.

Let $\delta ={\hat{\beta }}_{\lambda }^L-\beta$ and $Q=\Vert X\delta {\Vert }_2^2/n$. Comparing the Lasso objective at its minimizer and at $\beta$ and expanding the squares gives the Basic inequality for the LassoOn $\mathcal{E}$, the stochastic term is at most $\lambda \Vert \delta {\Vert }_1$. Because ${\beta }_N=0$, the triangle inequality givesIt follows thatIn particular $\Vert {\delta }_N{\Vert }_1\le 3\Vert {\delta }_S{\Vert }_1$, which is the Lasso cone condition. The given Compatibility condition for the Lasso is therefore applicable and gives $\Vert {\delta }_S{\Vert }_1\le \sqrt{sQ}/{\varphi }_0$.

Adding $\lambda \Vert {\delta }_S{\Vert }_1$ to the preceding inequality and using compatibility now yieldsThe last inequality is just the nonnegativity of $(\sqrt{Q/2}-\sqrt{8}\lambda \sqrt{s}/{\varphi }_0{)}^2$. Thus $Q+2\lambda \Vert \delta {\Vert }_1\le 16{\lambda }^{2}s/{\varphi }_0^2$, and dropping one nonnegative coefficient-error term givesThis prediction and coefficient error bound for compatible Lasso holds on $\mathcal{E}$, and hence with the required probability. If $s=0$, the earlier basic inequality directly forces $\delta =0$ on $\mathcal{E}$, so the zero right side is also correct.

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.

Use the normalizationfor the Lasso. A centered sub-Gaussian random variable with parameter $\sigma$ satisfies $\mathbb{E}{e}^{tW}\le e^{{\sigma }^2{t}^2/2}$ for all $t\in \mathbb{R}$; for a noncentered variable apply this definition to $W-\mathbb{E}W$. With fixed $X$, independence of the errors givesThe exponential Markov bound, optimized over $t$ separately for the two signs, gives $\mathrm{Pr}(|X_j^T\epsilon |/n>u)\le 2e^{-n{u}^2/(2{\sigma }^2)}$. Take $u=\lambda /2=\sigma A\sqrt{\log p/n}$ and apply the union bound over columns:The specified positive tuning parameter requires $p\ge 2$; at $p=1$ its formula is zero. For small $A$ the probability lower bound can be negative and hence uninformative. Although centering makes the centered errors dependent, $X^{T}1=0$ means $X^T(\epsilon -\bar{\epsilon }1)=X^T\epsilon$, so the preceding proof uses the original independent errors, not independence after centering.

The Karush-Kuhn-Tucker conditions, using the subdifferential of the L1 norm, areConsequently, for nonempty $B\subseteq \hat{S}$, on $\Omega$,This establishes the required active-set inequality without any rank condition on $X$.

For $s>0$, a sufficient Compatibility condition for the Lasso isIndeed, for $\delta =\hat{\beta }-{\beta }^0$, comparison of the two Lasso objective values and the score bound on $\Omega$ give the Basic inequality for the LassoIt follows that $\delta$ satisfies the Lasso cone condition and $\Vert {\delta }_S{\Vert }_1\le \sqrt{s{P}_E}/\varphi$. Thus $P_E\le 3\lambda \sqrt{s{P}_E}/\varphi$, including the trivial $P_E=0$ case. This proves the slightly stronger $P_E\le 9{\lambda }^{2}s/{\varphi }^2$, and in particular the requested $16{\lambda }^{2}s/{\varphi }^2$. If $s=0$, the same basic inequality forces $\hat{\beta }=0$ on $\Omega$; no nonempty-support compatibility constant is needed.

For the support-size argument, use the stated prediction bound with constant $16$. Set $b=|B|$. By the Cauchy-Schwarz inequality and the definition of the sparse maximum eigenvalue,Combining with the lower bound and squaring gives $\boxed{b\le 64{\kappa }_b^{2}s/{\varphi }^2}$ for every nonempty $B\subseteq \hat{S}$. If $m_{\ast }<\infty$ and $\hat{s}\ge m_{\ast }$, choose $B$ of size $m_{\ast }$; this contradicts the strict inequality defining $m_{\ast }$. If $m_{\ast }=\infty$, $\hat{s}\le p<\infty$ proves the assertion directly. Hence $\boxed{\hat{s}<m_{\ast }}$ in both cases.

When $1<m_{\ast }\le p$, minimality and monotonicity of the sparse maximum eigenvalues giveWhen $m_{\ast }=1$, the first result gives $\hat{s}=0$, so the same final bound holds. Thus the finite-index conclusion is $\boxed{\hat{s}\le 64{\kappa }_{m_{\ast }}^{2}s/{\varphi }^2(m_{\ast }<\infty )}$.

There is a genuine domain omission in the printed last assertion: the definition of ${\kappa }_m$ only makes sense for $1\le m\le p$, so ${\kappa }_{m_{\ast }}$ is undefined when $m_{\ast }=\infty$. This case can occur: take centered orthogonal columns with $X^{T}X/n=I_p$, $n\ge p+1$, $s=p$, and ${\varphi }^2=1$. Then ${\kappa }_m^2=1$ for every available $m$ and none exceeds $64p$, so $m_{\ast }=\infty$. A universally defined replacement, from $B=\hat{S}$ and monotonicity, isAlternatively, explicitly extend the definition by ${\kappa }_m={\kappa }_p$ for $m>p$, including infinity. Under that added convention the printed final expression is meaningful and follows from this replacement bound. Neither convention nor finiteness should be silently assumed.

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 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.

On the same event, the Lasso cone condition and the coordinatewise bound from part a giveWith $\lambda =A\sqrt{\log p/n}$ this is exactly

Write $\delta =\hat{\beta }-{\beta }^0$. On $\Omega$, Hölder's inequality givesSince ${\beta }_N^0=0$, the triangle inequality givesSubstitution in the Basic inequality for the Lasso, followed by discarding the nonnegative prediction-error term, yieldsTherefore $\Vert {\hat{\beta }}_N-{\beta }_N^0{\Vert }_1\le 3\Vert {\hat{\beta }}_S-{\beta }_S^0{\Vert }_1$, the Lasso cone condition.

Part b places $\delta =\hat{\beta }-{\beta }^0$ in the Lasso cone condition. Keeping the prediction-error term in the same argument giveswhere the second step is the Cauchy-Schwarz inequality. The restricted eigenvalue condition givesfor nonzero $\delta$ in this cone. Division by $\Vert \delta {\Vert }_2$ provesThe result is immediate when $\delta =0$.

With objective $\Vert Y-Xb{\Vert }_2^2/(2n)+\lambda \Vert b{\Vert }_1$, the Gaussian score event for the Lasso $\Vert X^Tϵ/n{\Vert }_{\infty }\le \lambda /2$ gives $Q+\lambda \Vert {\delta }_{S^c}{\Vert }_1\le 3\lambda \Vert {\delta }_S{\Vert }_1$, where $Q=\Vert X\delta {\Vert }_2^2/n$. The Lasso cone condition activates the Compatibility condition for the Lasso. Then $Q+\lambda \Vert \delta {\Vert }_1\le 4\lambda \sqrt{sQ}/{\varphi }_0\le Q/2+8{\lambda }^{2}s/{\varphi }_0^2$. Thus even $Q+2\lambda \Vert \delta {\Vert }_1\le 16{\lambda }^{2}s/{\varphi }_0^2$. This controls prediction and coefficient error together, including a design with correlated columns.