Lasso

The Lasso minimizes regression error plus an ${\ell }^1$ penalty.

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.

The Lasso regularization path follows its coefficients as the penalty or constraint radius changes. Under the usual least-angle construction, the coefficient path is piecewise linear between knots, and variables can enter or leave the active set. Reading support at a selected cross-validation fraction requires checking which coefficients are actually zero at that fraction, rather than retaining only visibly large traces.

At a positive penalty level, let $E$ be the residual-score equality set, $s_j$ its signs and $N$ the nonzero regression coefficient support. With full column rank, the displayed strictly convex quadratic program selects the direction for a small decrease of the penalty. Existing nonzero regression coefficients have unrestricted tangent components; tied zero regression coefficients may move only with their residual signs. Stationarity gives $X_j^{T}Xv=s_j$ for $j\in N$ and for entering zero coordinates, and $s_j{X}_j^{T}Xv\ge 1$ for tied coordinates that remain zero. These are exactly the first-order Karush-Kuhn-Tucker conditions for the Lasso along the next segment. Normalize $Xv$ to obtain the corresponding least-angle direction. This resolves simultaneous entries or dropouts without adding a generic-position assumption.

// Target: mathematical-optimization.bigb

On a least-angle segment $\beta (\gamma )=\beta +\gamma d$, a nonzero active regression coefficient reaches zero at the displayed first positive root. Continue only as far as the first dropout, inactive-entry event or zero-correlation endpoint. At a dropout remove the vanishing regression coefficient from the active direction and recompute. This preserves agreement between nonzero regression coefficient signs and residual-score signs, which the Karush-Kuhn-Tucker conditions for the Lasso require. A removed regression coefficient may re-enter later; the active set need not grow monotonically.

Let $0<c<1$, $A>0$, $\sigma >0$ and $p\ge 2$. For design matrix columns of norm $\sqrt{n}$ and $\epsilon \sim N_n(0,{\sigma }^{2}I)$, the event $\Vert X^T\epsilon {\Vert }_{\infty }/n\le c\lambda$ has probability at least $1-p^{1-A^2{c}^2/2}$ when $\lambda =A\sigma \sqrt{\log (p)/n}$. Apply the sharp two-sided Gaussian tail bound to each standardized score and then the union bound; independence of the scores is not required.

For a design matrix $X$ with $p$ columns, define ${\kappa }_m^2={\max }_{|M|=m}{\lambda }_{\max }(X_M^T{X}_M/n)$ for $1\le m\le p$. Equivalently this bounds $\Vert Xv{\Vert }_2^2/(n\Vert v{\Vert }_2^2)$ for vectors supported on at most $m$ coordinates. These quantities are nondecreasing: extend the support of a maximizing vector by zero coordinates and use the variational characterization of the largest eigenvalue. Values at $m>p$, including infinity, require a separate convention.

For $\lambda >0$ and $\varphi >0$, use the Lasso objective $\Vert Y-X\beta {\Vert }_2^2/(2n)+\lambda \Vert \beta {\Vert }_1$. Suppose the noise score has maximum norm at most $\lambda /2$, the true support has size $s$, and $\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2/n\le 16{\lambda }^{2}s/{\varphi }^2$. For any nonempty $B\subseteq \hat{S}$, the Karush-Kuhn-Tucker conditions implyThe upper bound is the Cauchy-Schwarz inequality. Hence $|B|\le 64{\kappa }_{|B|}^{2}s/{\varphi }^2$. A finite first index $m_{\ast }$ violating this inequality must exceed $|\hat{S}|$. Its minimality also gives $|\hat{S}|\le 64{\kappa }_{m_{\ast }}^{2}s/{\varphi }^2$. If no such index exists within $1,\dots ,p$, use the always defined bound $|\hat{S}|\le 64{\kappa }_p^{2}s/{\varphi }^2$.

The Lava estimator minimizes $\Vert Y-X(\delta +\beta ){\Vert }_2^2/(2n)+{\lambda }_1\Vert \delta {\Vert }_1+{\lambda }_2\Vert \beta {\Vert }_2^2$. It combines a component selected by Lasso with a component shrunk by ridge regression. Profiling the latter yields a transformed Lasso problem; this is not the same coefficient penalty as elastic net regularization.

For $Q=(X^{T}X+2n{\lambda }_{2}I{)}^{-1}$ and $A=(I-XQ{X}^T{)}^{1/2}$, profiling the dense coefficient gives $\hat{\beta }=Q{X}^T(Y-X\hat{\delta })$. The sparse coefficient minimizes $\Vert AY-AX\delta {\Vert }_2^2/(2n)+{\lambda }_1\Vert \delta {\Vert }_1$. The transformation uses the principal square root of a positive semidefinite matrix and remains valid for rank-deficient designs.

The fused Lasso adds an L1 norm penalty on adjacent coefficient differences to a squared-error objective, optionally together with an L1 norm penalty on the coefficients themselves. The differences penalty encourages neighbouring coefficients to coincide.

This version of the fused Lasso penalizes only adjacent differences. It estimates a piecewise-constant signal while preserving an unpenalized constant level. Larger penalties generally favour fewer fitted changes.

The Dantzig selector minimizes the coefficient ${\ell }^1$ norm subject to an ${\ell }^{\infty }$ bound on residual correlations.

The square-root Lasso uses the unsquared residual norm plus an ${\ell }^1$ penalty.

For a fixed residual direction $R=Z-X{\tilde{\beta }}_{\gamma }\ne 0$ obtained by Square-root Lasso, its optimality condition gives $\Vert X^{T}R{\Vert }_{\infty }\le \sqrt{n}\gamma \Vert R{\Vert }_2$. In a fixed-design normal linear model, the score $R^T(Y-X\hat{\beta })/\Vert R{\Vert }_2$ equals a $N(0,{\sigma }^2)$ component plus a remainder bounded by $\sqrt{n}\gamma \Vert {\beta }^0-\hat{\beta }{\Vert }_1$. The direction must be fixed or independent of the response noise for that normality claim.

A Lasso minimizer with positive residual scale ${\hat{\sigma }}_{\lambda }=\Vert Y-X{\hat{\beta }}_{\lambda }{\Vert }_2/\sqrt{n}$ also minimizes the Square-root Lasso objective at the displayed tuning parameter. Divide its Karush-Kuhn-Tucker conditions by the residual scale and use the subgradient optimality condition.

The group Lasso partitions a coefficient vector into groups $G_1,\dots ,G_q$ and replaces the coordinatewise ${\ell }^1$ penalty with a weighted sum of group norms,It tends to retain or discard an entire group at once. Its dual norm isso the corresponding Holder inequality is $|u^{T}v|\le P(u)P^{\ast }(v)$.

Joint squared-error nodewise regression with this penalty groups the two coefficients of each unordered edge. Its norm is nonsmooth only when the whole pair is zero, encouraging edge-wise sparsity. A fitted edge is present when its pair norm is positive. The penalty does not require equal directional coefficients, two nonzero entries in every selected group, or a symmetric positive definite precision matrix.

For each unordered pair, $g=({\Theta }_{jk},{\Theta }_{kj})$ and $c=(X_j^{\mathsf{T}}{r}_k/n,X_k^{\mathsf{T}}{r}_j/n)$ with centred columns and regression residuals. The subdifferential of the Euclidean norm is the unit ball at zero and $g/\Vert g{\Vert }_2$ otherwise. These KKT conditions are necessary and sufficient for the convex paired objective and explain joint edge deletion.

Comparing the Lasso objective at an estimate $\hat{\beta }$ and a target ${\beta }^0$, then expanding the squared loss, bounds the prediction error by a noise-score term and the decrease in the ${\ell }^1$ penalty.

For Lasso loss $\Vert Y-X\beta {\Vert }_2^2/(2n)+\lambda \Vert \beta {\Vert }_1$ and $Y=X{\beta }^0+\eta$, stationarity with a penalty subgradient gives $\Vert X\delta {\Vert }_2^2/n\le {\eta }^{T}X\delta /n+\lambda (\Vert {\beta }^0{\Vert }_1-\Vert \hat{\beta }{\Vert }_1)$, $\delta =\hat{\beta }-{\beta }^0$. This follows by multiplying the Karush-Kuhn-Tucker conditions by $\delta$ and using $z^T\hat{\beta }=\Vert \hat{\beta }{\Vert }_1$ and $z^T{\beta }^0\le \Vert {\beta }^0{\Vert }_1$.

For $Y=X{\beta }^0+\eta$, the Lasso objective $\Vert Y-X\beta {\Vert }_2^2/(2n)+\lambda \Vert \beta {\Vert }_1$ has this prediction bound whenever $\Vert X^T\eta {\Vert }_{\infty }/n\le \lambda$. Compare its value at $\hat{\beta }$ and ${\beta }^0$, apply Holder inequality to the score, and use the triangle inequality. No restricted eigenvalue condition is required.

On an event where the noise-score infinity norm is at most half the penalty, the Lasso error $\delta$ obeys $\Vert {\delta }_{S^c}{\Vert }_1\le 3\Vert {\delta }_S{\Vert }_1$.

A design matrix satisfies a restricted eigenvalue condition with constant $\gamma >0$ on a cone $C$ when $\Vert X\delta {\Vert }_2^2/n\ge \gamma \Vert \delta {\Vert }_2^2$ for every nonzero $\delta \in C$.

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.

Let $\delta =\hat{\beta }-{\beta }^0$, $s=|S|>0$ and $\varphi >0$. On the score event $\Vert X^T\eta {\Vert }_{\infty }/n\le c\lambda$ with $0<c<1$, the prediction inequality from Lasso stationarity gives $Q+(1-c)\lambda \Vert {\delta }_{S^c}{\Vert }_1\le (1+c)\lambda \Vert {\delta }_S{\Vert }_1$. If the Compatibility condition for the Lasso with constant $\varphi$ holds on this cone, then $Q+(1-c)\lambda \Vert {\delta }_{S^c}{\Vert }_1\le (1+c{)}^2{\lambda }^{2}s/{\varphi }^2$. Here $Q=\Vert X\delta {\Vert }_2^2/n$ and $S$ is the true support of a vector.

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.

The fast-rate Lasso prediction bound under compatibility implies $\Vert {\hat{\beta }}_S-{\beta }_S^0{\Vert }_1\le (1+c)\lambda s/{\varphi }^2$. Each true coefficient larger in absolute value than this bound has the correct estimated sign. This conclusion alone does not ensure absence of false positives.

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.

If $\Vert \Theta -\Sigma {\Vert }_{\max }\le {\varphi }_{\Sigma }^2/(32s)$, then ${\varphi }_{\Theta }^2\ge {\varphi }_{\Sigma }^2/2$. Indeed, every normalized cone vector has $\Vert \delta {\Vert }_1\le 4$, so its quadratic form changes by at most $16\Vert \Theta -\Sigma {\Vert }_{\max }\le {\varphi }_{\Sigma }^2/(2s)$.

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.

The debiased Lasso adds an approximate inverse-Gram correction to a Lasso estimate so that each corrected coordinate has an asymptotically linear expansion.

Let $\hat{\Sigma }=X^{T}X/n$ and use Nodewise Lasso with ${\lambda }_j>0$ and nonzero design columns. Form $c_j$ with entry $j$ equal to one and other entries $-{\hat{\gamma }}^{(j)}$, and put row $j$ of $\hat{\Theta }$ equal to $c_j^T/{\hat{\tau }}_j^2$. The nodewise-Lasso residual identity and the Karush-Kuhn-Tucker conditions show that the diagonal of $\hat{\Theta }\hat{\Sigma }$ equals one and its row-$j$ off-diagonal entries have magnitude at most ${\lambda }_j/{\hat{\tau }}_j^2$. For the Debiased Lasso,The displayed bound follows row by row from Holder inequality. If the noise is conditionally multivariate normal with covariance ${\sigma }^{2}I$, and the nodewise fits and tuning parameters depend only on $X$, the first term is conditionally normal with covariance ${\sigma }^2\hat{\Theta }\hat{\Sigma }{\hat{\Theta }}^T$.

A matrix $\Theta$ is an $\eta$-approximate inverse of a Gram matrix $\hat{\Sigma }$ in entrywise maximum norm whenThis turns the bias remainder of a Debiased Lasso into a product of $\eta$ and the coefficient ${\ell }^1$ error.

The nodewise Lasso regresses each design column on the remaining columns and uses its residual to estimate a column of the inverse covariance or inverse Gram matrix.

For Nodewise Lasso with objective $\Vert X_j-X_{-j}\gamma {\Vert }_2^2/(2n)+{\lambda }_j\Vert \gamma {\Vert }_1$, put $r_j=X_j-X_{-j}{\hat{\gamma }}^{(j)}$. Its Karush-Kuhn-Tucker conditions give $X_{-j}^T{r}_j/n={\lambda }_j{z}_j$ with $z_j\in \partial \Vert {\hat{\gamma }}^{(j)}{\Vert }_1$. HenceFor ${\lambda }_j>0$ this is positive whenever $X_j\ne 0$; if it were zero both nonnegative terms would vanish, forcing ${\hat{\gamma }}^{(j)}=0$ and $X_j=r_j=0$. Nonzero columns are therefore an essential hypothesis for division by this quantity.

Under sparsity, compatibility, and inverse-Gram estimation conditions, the standardized coordinatewise error of the Debiased Lasso converges in distribution to a standard normal distribution.

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

Soft thresholding maps $u$ to $\mathrm{sgn}(u)(|u|-\lambda {)}_{+}$ and is the proximal operator of the absolute-value penalty.

The Berhu, or reverse-Huber, penalty with threshold $\delta >0$ isIt behaves like the absolute value near zero and quadratically for large coefficients.

Elastic-net regression minimizes squared error plus both an ${\ell }^1$ coefficient penalty and a squared ${\ell }^2$ penalty. It combines exact sparsity with strict convexity when the quadratic penalty is positive.

Extend $J$ by infinity outside ${\ell }^1$. For a bounded linear operator $K:{\ell }^2\to {\ell }^2$, the objective $\Vert Ku-f{\Vert }_2^2/2+\alpha J(u)$ is coercive, weakly lower semicontinuous and strictly convex for $\alpha >0$, so it has a unique minimizer. The quadratic penalty ensures existence and uniqueness even if $K$ has a null space. Its limiting exact solution minimizes $J$ in the data fiber, which need not be the minimum-norm least-squares solution.

For fixed $\alpha >0$ and nonzero bounded $K$, the reconstruction vanishes when $\Vert K^{\ast }f{\Vert }_{\infty }\le \alpha$, which includes a neighborhood of zero. If it were linear it would vanish everywhere. Choose a coordinate $e_j$ with $K{e}_j\ne 0$ and data $f=tK{e}_j$ with $t\Vert K{e}_j{\Vert }^2>\alpha$; the optimality inequality at zero fails, so its minimizer is nonzero. Thus the map is nonlinear. The qualification $K\ne 0$ is essential: $K=0$ gives the zero linear map.

Assume an exact solution of finite penalty exists and select the unique $J$-minimizing exact solution $u^{†}$. Minimality gives $\Vert K{u}_{\alpha }^{\delta }-f^{\delta }{\Vert }^2/2+\alpha J(u_{\alpha }^{\delta })\le {\delta }^2/2+\alpha J(u^{†})$. If $\alpha \to 0$ and ${\delta }^2/\alpha \to 0$, boundedness, weak sequential compactness of bounded sequences in a reflexive Banach space and lower semicontinuity identify every weak limit with $u^{†}$. The separate lower semicontinuity of $\Vert u{\Vert }_1$ and $\Vert u{\Vert }_2^2$, together with the upper bound on $J$, forces the Hilbert norms to converge. The Radon-Riesz theorem then gives norm convergence.

The quadratic penalty encourages strongly correlated predictors to receive similar coefficients, so an elastic net tends to retain or discard correlated predictors as a group more readily than the Lasso.