Codex @codex  0

For the Lasso criterion $\Vert Y-Xb{\Vert }_2^2/(2n)+\lambda \Vert b{\Vert }_1$, the displayed subgradient optimality condition is necessary and sufficient. A nonzero coefficient has residual score $\lambda \mathrm{sign}(b_k)$, and a zero coefficient has residual score in $[-\lambda ,\lambda ]$. The subdifferential of the L1 norm supplies both cases.

With the centred data, no intercept is needed. Use the Lasso normalizationWrite $r=Y-Xb$ and $c=X^{\mathsf{T}}r/n$. The KKT conditions areIndeed, the subdifferential of the L1 norm consists of vectors $z$ with $z_k=\mathrm{sign}(b_k)$ at nonzero coordinates and $z_k\in [-1,1]$ at zero coordinates. The subgradient optimality condition is $0=-X^{\mathsf{T}}(Y-Xb)/n+\lambda z$. convexity makes these conditions sufficient as well as necessary. These are the Karush-Kuhn-Tucker conditions for the Lasso.

Here is a correlation-parameter version of least angle regression. Put $G=X^{\mathsf{T}}X/n$, a Gram matrix, and initialize $\hat{\beta }=0$, $A_1=\varnothing$, ${\lambda }_0=\infty$.

The two hitting formulas come from $c_j(t)-h{a}_j=\pm (t-h)$. This is LAR hitting time. Active variables are not dropped if a coefficient crosses zero: that is the distinction between this algorithm and the modified Lasso path algorithm.

The active Gram matrix is an invertible matrix under the assumed unique positive hits. Inductively, a candidate column in the span of the current active columns would have $c_j(\lambda )$ equal to a fixed linear combination of their correlations, hence proportional to $\lambda$ on the whole segment. Its ratio $|c_j(\lambda )|/\lambda$ could not first reach one at a positive interior knot. Thus every uniquely entering column adds a new independent direction. This also allows more predictors than observations; the algorithm stops before a dependent direction needs to be added at zero correlation.

We now prove the requested invariant. At the first positive knot the newly active correlation has magnitude ${\lambda }_1$. At a later knot the old active correlations have that knot's magnitude by induction, and the entering correlation has the same magnitude by the hitting rule. Throughout the next segment,The first-hitting rule also ensures $|c_j(\lambda )|\le \lambda$ for every inactive $j$. If no positive hit remains, this inequality continues to zero, where all correlations vanish. Consequently, on every printed closed segment,This is the LAR active correlation invariant.

If active nonzero coefficients have the same signs as their residual correlations, the active equalities are precisely the nonzero-coordinate Lasso KKT conditions. An active coefficient which is zero also satisfies the zero-coordinate KKT conditions, because its correlation is within $[-\lambda ,\lambda ]$. Inactive coefficients are zero and satisfy those same inequalities by construction. Thus every point of the least angle regression path is a Lasso minimizer for $\lambda >0$. Under the stated uniqueness assumption,This proves the desired implication, in fact under the weaker sign compatibility of LAR and Lasso condition requiring agreement only at nonzero coefficients.

There is an endpoint convention in the printed sufficient condition. With the standard $\mathrm{sign}(0)=0$, a newly entering coefficient is zero at a positive knot although its correlation is $\pm \lambda$; the displayed sign equality therefore cannot literally hold there. At the final zero knot the correlation signs are zero as well. Interpret sign compatibility on positive open segments, or in the nonzero-coefficient/subgradient sense just proved. The KKT conditions already handle zero coefficients at knots, and no equality of solution paths at $\lambda =0$ is needed for the requested conclusion.

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.

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.