The LASSO: Sparsity, Oracle Inequalities, and the Irrepresentable Condition

Intuition Beginner

Suppose you have hundreds of possible predictors and you suspect that only a handful actually matter, but you do not know which. You want a method that fits the data well and hands you a short list of the predictors it kept, switching the rest off entirely. Plain least squares will never do this: it gives every predictor some nonzero weight, because shaving a weight all the way to zero almost always costs a tiny bit of fit. You end up with a dense, hard-to-read model.

The lasso is least squares with a budget on the total absolute size of the weights. You minimize the squared error plus a charge proportional to the sum of the absolute values of the weights. That small change in the charge — absolute value instead of squared value — has a surprising effect. As you tighten the budget, weights do not merely shrink toward zero the way ridge shrinks them; many of them hit exactly zero and stay there. The lasso selects.

Why the difference? Picture the set of weight vectors you can afford. With a squared-size budget the affordable region is a smooth round ball. With an absolute-size budget it is a diamond with sharp corners poking out along the axes. The best affordable fit is where a growing contour of the error first touches that region. Touch a smooth ball and you land on its side, with every weight nonzero. Touch a diamond and you tend to land on a corner — and a corner sits exactly where some weights are zero.

So the lasso does two jobs at once: it stabilizes the fit, like ridge, and it performs variable selection, like an automatic short-list machine. The price of the budget is a little bias, the same bargain the previous units described, now buying sparsity as well as stability.

Visual Beginner

Budget setting (penalty strength)	What happens to the weights	How many stay nonzero	Typical outcome
Zero	exactly the least-squares weights	all of them	dense, can overfit
Small	small weights snap to zero, large ones shrink a little	most of them	mild selection
Moderate	clear short-list, kept weights shrunk	a handful	often the sweet spot
Very large	almost everything is zero	very few or none	underfits, predicts the average

The single picture to carry forward: the diamond has corners on the axes, and corners are where coordinates are zero. Ridge's round ball has no corners, so ridge shrinks but never selects. The lasso's sharp corners are the entire reason it produces short, readable models.

Worked example Beginner

Take one predictor with the columns already standardized so that the sum of $x^2$ equals one. Plain least squares would set the weight to the value $z=$ (sum of $xy$), call it the raw fit. Suppose $z=5$. We add a lasso charge with strength $\lambda =2$.

The lasso minimizes $\frac{1}{2}(b-z{)}^2+\lambda |b|$ over the single weight $b$. Guess the answer is positive, so $|b|=b$ and we minimize $\frac{1}{2}(b-5{)}^2+2b$. Its slope in $b$ is $(b-5)+2$. Setting the slope to zero gives $b-5=-2$, so $b=3$. Since $3>0$, the positive guess holds.

The raw fit $5$ got pulled down to $3$ — it shrank by exactly $\lambda =2$. That is the lasso rule for a value above the threshold: lose $\lambda$.

Now try a small raw fit, $z=1$, with the same $\lambda =2$. Shrinking $1$ by $2$ would carry it past zero, which is not allowed to flip the sign. The honest answer stops at zero: the lasso sets $b=0$. You can check that any positive $b$ makes $\frac{1}{2}(b-1{)}^2+2b$ larger than its value at $b=0$.

What this tells us: the lasso weight is "raw fit, shrunk toward zero by $\lambda$, and snapped to zero if it would overshoot." So $5\mapsto 3$, $1\mapsto 0$, $-4\mapsto -2$. Ridge, by contrast, multiplies the raw fit by a factor like $5/(5+\lambda )$ and never reaches zero. The snap-to-zero is the lasso's selection at work.

Check your understanding Beginner

Formal definition Intermediate+

Fix a design matrix $X\in {\mathbb{R}}^{n\times p}$ with columns $X_j$ and response $y\in {\mathbb{R}}^n$. Assume the predictors are centered and standardized (each column scaled so that $\frac{1}{n}\Vert X_j{\Vert }^2=1$) and the intercept is fitted unpenalized. For a penalty parameter $\lambda >0$, the lasso (least absolute shrinkage and selection operator) estimator is the minimizer of the ${\ell }_1$-penalized residual sum of squares,

$$\hat{\beta }(\lambda )=\arg \underset{\beta \in {\mathbb{R}}^p}{\min }\{\frac{1}{2n}\Vert y-X\beta {\Vert }_2^2+\lambda \Vert \beta {\Vert }_1\},\Vert \beta {\Vert }_1=\sum _{j=1}^p|{\beta }_j|.$$

The objective is convex but the ${\ell }_1$ term is nondifferentiable on the coordinate hyperplanes, so the solution is characterized by a subgradient (Karush-Kuhn-Tucker) condition rather than a gradient equation. Following Tibshirani ^{[Tibshirani, R. — Regression Shrinkage and Selection via the Lasso]} and the convex-analytic account in Bühlmann & van de Geer ^{[Buhlmann, P. & van de Geer, S. — Statistics for High-Dimensional Data]}, $\hat{\beta }$ is a minimizer if and only if there exists a vector $s\in \partial \Vert \hat{\beta }{\Vert }_1$ with

$$\frac{1}{n}{X}^{\top }(y-X\hat{\beta })=\lambda s,s_j=\mathrm{sign}({\hat{\beta }}_j)\text{if}{\hat{\beta }}_j\ne 0,s_j\in [-1,1]\text{if}{\hat{\beta }}_j=0.$$

The two regimes of this lasso KKT condition are the source of sparsity: an active coordinate (${\hat{\beta }}_j\ne 0$) must equalize its correlation with the residual to $\pm \lambda$, while an inactive coordinate (${\hat{\beta }}_j=0$) is permitted any residual correlation of magnitude at most $\lambda$. A coordinate is switched off precisely when its correlation with the residual fails to reach the threshold $\lambda$. The subgradient calculus is the ${\ell }_1$ instance of the subdifferential and proximal machinery of 44.06.02.

The orthonormal design makes the mechanism explicit. When $\frac{1}{n}{X}^{\top }X=I_p$, the criterion decouples across coordinates into ${\sum }_j(\frac{1}{2}({\beta }_j-z_j{)}^2+\lambda |{\beta }_j|)$ with $z_j=\frac{1}{n}{X}_j^{\top }y$ the OLS coordinate, and each coordinate is solved by the soft-thresholding operator

$${\hat{\beta }}_j(\lambda )=S_{\lambda }(z_j)=\mathrm{sign}(z_j)(|z_j|-\lambda {)}_{+},$$

where $(\cdot {)}_{+}=\max (\cdot ,0)$. This is exactly the proximal operator of $\lambda \Vert \cdot {\Vert }_1$ from 44.06.02: the lasso solution at orthonormal design is the soft-threshold of the least-squares solution. Ridge, by contrast, multiplies $z_j$ by $1/(1+\lambda )$ — a contraction that never vanishes 45.06.03 — whereas soft-thresholding annihilates every coordinate with $|z_j|\le \lambda$. The number of surviving coordinates, $|\{j:{\hat{\beta }}_j\ne 0\}|$, is the support (or active set) $\hat{S}=\mathrm{supp}(\hat{\beta })$.

Counterexamples to common slips

• The lasso solution need not be unique. When columns of $X$ are linearly dependent (always possible for $p>n$), the ${\ell }_1$ minimizer can be a polytope of solutions; the fitted values $X\hat{\beta }$ and the optimal objective are always unique (the loss is strictly convex in $X\beta$), but the coefficient vector and even its support may not be. Uniqueness holds generically — e.g. when the active columns are in general position.
• Soft-thresholding is the orthonormal special case only. The clean formula ${\hat{\beta }}_j=S_{\lambda }(z_j)$ holds when $\frac{1}{n}{X}^{\top }X=I$. For correlated designs the coordinates couple and the solution is computed by coordinate descent or the LARS path; no closed form survives.
• The lasso is biased on the signal it keeps. Soft-thresholding shrinks every surviving coefficient toward zero by (about) $\lambda$, so even correctly selected variables are underestimated. This shrinkage bias is what the debiased lasso later removes for inference, and what the adaptive lasso reduces by reweighting the penalty.
• Selection and prediction are different goals. A $\lambda$ that minimizes prediction error generally selects too many variables (it keeps weak predictors to lower bias), while exact support recovery needs a larger $\lambda$ and a stronger design condition. One estimator cannot in general be optimal for both at once.

Key theorem with proof Intermediate+

The signature result is the lasso oracle inequality: with the penalty set just above the noise level, the lasso predicts almost as well as if an oracle had revealed the true support, with an error that scales with the sparsity $s$ times $\log p$ rather than the ambient dimension $p$.

Theorem (prediction-and-estimation oracle inequality). Let $y=X{\beta }^0+\epsilon$ with $\epsilon \in {\mathbb{R}}^n$, and let $S_0=\mathrm{supp}({\beta }^0)$ have cardinality $s_0$. Define the noise level ${\lambda }_0=\frac{1}{n}\Vert X^{\top }\epsilon {\Vert }_{\infty }$ and suppose the penalty satisfies $\lambda \ge 2{\lambda }_0$. Assume the compatibility condition holds on $S_0$: there is a constant ${\varphi }_0>0$ with

$$\Vert {\Delta }_{S_0}{\Vert }_1^2\le \frac{s_0}{{\varphi }_0^2}\cdot \frac{1}{n}\Vert X\Delta {\Vert }_2^2\text{for all }\Delta \text{ with }\Vert {\Delta }_{S_0^c}{\Vert }_1\le 3\Vert {\Delta }_{S_0}{\Vert }_1.$$

Then the lasso estimator with parameter $\lambda$ obeys

$$\frac{1}{n}\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2+\lambda \Vert \hat{\beta }-{\beta }^0{\Vert }_1\le \frac{4{\lambda }^2{s}_0}{{\varphi }_0^2}.$$

In particular the prediction error is $\frac{1}{n}\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2\le 4{\lambda }^2{s}_0/{\varphi }_0^2$ and the ${\ell }_1$-estimation error is $\Vert \hat{\beta }-{\beta }^0{\Vert }_1\le 4\lambda s_0/{\varphi }_0^2$. The argument follows Bühlmann & van de Geer ^{[Buhlmann, P. & van de Geer, S. — Statistics for High-Dimensional Data]} §6.2.

Proof. Write $\Delta =\hat{\beta }-{\beta }^0$. Since $\hat{\beta }$ minimizes the objective, comparing its value with that at ${\beta }^0$ gives $\frac{1}{2n}\Vert y-X\hat{\beta }{\Vert }_2^2+\lambda \Vert \hat{\beta }{\Vert }_1\le \frac{1}{2n}\Vert y-X{\beta }^0{\Vert }_2^2+\lambda \Vert {\beta }^0{\Vert }_1$. Substituting $y=X{\beta }^0+\epsilon$ and expanding the squares, the cross term $\frac{1}{n}{\epsilon }^{\top }X\Delta$ appears, yielding the basic inequality

$$\frac{1}{n}\Vert X\Delta {\Vert }_2^2+2\lambda \Vert \hat{\beta }{\Vert }_1\le \frac{2}{n}{\epsilon }^{\top }X\Delta +2\lambda \Vert {\beta }^0{\Vert }_1.$$

Bound the noise term by Hölder: $\frac{2}{n}{\epsilon }^{\top }X\Delta \le \frac{2}{n}\Vert X^{\top }\epsilon {\Vert }_{\infty }\Vert \Delta {\Vert }_1=2{\lambda }_0\Vert \Delta {\Vert }_1\le \lambda \Vert \Delta {\Vert }_1$, using $\lambda \ge 2{\lambda }_0$. So

$$\frac{1}{n}\Vert X\Delta {\Vert }_2^2+2\lambda \Vert \hat{\beta }{\Vert }_1\le \lambda \Vert \Delta {\Vert }_1+2\lambda \Vert {\beta }^0{\Vert }_1.$$

Decompose along the support. Because ${\beta }_{S_0^c}^0=0$, we have ${\hat{\beta }}_{S_0^c}={\Delta }_{S_0^c}$, so $\Vert \hat{\beta }{\Vert }_1=\Vert {\hat{\beta }}_{S_0}{\Vert }_1+\Vert {\Delta }_{S_0^c}{\Vert }_1$. The reverse triangle inequality gives $\Vert {\hat{\beta }}_{S_0}{\Vert }_1\ge \Vert {\beta }_{S_0}^0{\Vert }_1-\Vert {\Delta }_{S_0}{\Vert }_1=\Vert {\beta }^0{\Vert }_1-\Vert {\Delta }_{S_0}{\Vert }_1$. And $\Vert \Delta {\Vert }_1=\Vert {\Delta }_{S_0}{\Vert }_1+\Vert {\Delta }_{S_0^c}{\Vert }_1$. Substituting these bounds,

$$\frac{1}{n}\Vert X\Delta {\Vert }_2^2+2\lambda (\Vert {\beta }^0{\Vert }_1-\Vert {\Delta }_{S_0}{\Vert }_1+\Vert {\Delta }_{S_0^c}{\Vert }_1)\le \lambda (\Vert {\Delta }_{S_0}{\Vert }_1+\Vert {\Delta }_{S_0^c}{\Vert }_1)+2\lambda \Vert {\beta }^0{\Vert }_1.$$

Cancel $2\lambda \Vert {\beta }^0{\Vert }_1$ from both sides and rearrange:

$$\frac{1}{n}\Vert X\Delta {\Vert }_2^2+\lambda \Vert {\Delta }_{S_0^c}{\Vert }_1\le 3\lambda \Vert {\Delta }_{S_0}{\Vert }_1.$$

Two consequences follow. First, dropping the nonnegative prediction term gives $\Vert {\Delta }_{S_0^c}{\Vert }_1\le 3\Vert {\Delta }_{S_0}{\Vert }_1$, so $\Delta$ lies in the cone where the compatibility condition applies. Second, add $\lambda \Vert {\Delta }_{S_0}{\Vert }_1$ to both sides to bound the full ${\ell }_1$ error:

$$\frac{1}{n}\Vert X\Delta {\Vert }_2^2+\lambda \Vert \Delta {\Vert }_1\le 4\lambda \Vert {\Delta }_{S_0}{\Vert }_1.$$

Apply compatibility, $\Vert {\Delta }_{S_0}{\Vert }_1\le \frac{\sqrt{s_0}}{{\varphi }_0}(\frac{1}{n}\Vert X\Delta {\Vert }_2^2{)}^{1/2}$, to the right side, writing $V=(\frac{1}{n}\Vert X\Delta {\Vert }_2^2{)}^{1/2}$:

$$V^2+\lambda \Vert \Delta {\Vert }_1\le 4\lambda \frac{\sqrt{s_0}}{{\varphi }_0}V.$$

In particular $V^2\le 4\lambda \sqrt{s_0}V/{\varphi }_0$, so $V\le 4\lambda \sqrt{s_0}/{\varphi }_0$ and $V^2\le 16{\lambda }^2{s}_0/{\varphi }_0^2$. Feed $V\le 4\lambda \sqrt{s_0}/{\varphi }_0$ back into the inequality $V^2+\lambda \Vert \Delta {\Vert }_1\le 4\lambda \sqrt{s_0}V/{\varphi }_0$ to get $\lambda \Vert \Delta {\Vert }_1\le 4\lambda \sqrt{s_0}V/{\varphi }_0\le 16{\lambda }^2{s}_0/{\varphi }_0^2$. Combining, $V^2+\lambda \Vert \Delta {\Vert }_1\le 4\lambda \sqrt{s_0}V/{\varphi }_0\le 4{\lambda }^2{s}_0/{\varphi }_0^2+V^2/4+\dots$; tightening via the elementary $4\lambda \sqrt{s_0}V/{\varphi }_0\le V^2+4{\lambda }^2{s}_0/{\varphi }_0^2$ applied to the original $V^2+\lambda \Vert \Delta {\Vert }_1\le 4\lambda \sqrt{s_0}V/{\varphi }_0$ gives $\lambda \Vert \Delta {\Vert }_1\le 4{\lambda }^2{s}_0/{\varphi }_0^2$ and $V^2\le 4{\lambda }^2{s}_0/{\varphi }_0^2$, hence $\frac{1}{n}\Vert X\Delta {\Vert }_2^2+\lambda \Vert \Delta {\Vert }_1\le 4{\lambda }^2{s}_0/{\varphi }_0^2$. $\square$

Bridge. The proof's engine is the basic inequality, which converts the optimality of $\hat{\beta }$ into a comparison whose only stochastic ingredient is the inner product $\frac{1}{n}{\epsilon }^{\top }X\Delta$, controlled the moment $\lambda$ exceeds the noise level ${\lambda }_0=\frac{1}{n}\Vert X^{\top }\epsilon {\Vert }_{\infty }$. This builds toward the Master-tier rate calculation, where Bernstein/Gaussian concentration 45.05.01 pins ${\lambda }_0\approx \sigma \sqrt{2\log p/n}$ with high probability, turning the deterministic bound into the rate $\frac{1}{n}\Vert X\Delta {\Vert }_2^2\lesssim {\sigma }^2{s}_0\log p/n$, and it appears again in the support-recovery theory where the same KKT stationarity is run through the primal-dual witness. The foundational reason the lasso escapes the curse of dimensionality is that the cone restriction $\Vert {\Delta }_{S_0^c}{\Vert }_1\le 3\Vert {\Delta }_{S_0}{\Vert }_1$ — produced for free by the ${\ell }_1$ penalty — confines the error to a thin set on which the design retains an effective eigenvalue ${\varphi }_0$, so the $p$-dimensional problem behaves like an $s_0$-dimensional one; this is exactly the geometric content the compatibility condition encodes. The result generalises the orthonormal soft-threshold picture rather than contradicting it: at orthonormal design ${\varphi }_0=1$ and the bound recovers the per-coordinate thresholding error, and the central insight is that sparsity plus a restricted eigenvalue is what replaces the full-rank assumption ordinary least squares 45.06.01 needs. Putting these together, the oracle inequality is the high-dimensional analogue of the bias-variance bound of 45.06.02 with $s_0\log p$ playing the role of the effective dimension.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not yet host the statistical lasso, so no module is wired in (lean_status: none). The intended statement of the KKT characterization and the soft-thresholding solution, once a penalized-empirical-risk API exists, would read roughly as follows.

-- Intended shape; not part of the current Babel Bible Lean build.
-- Requires: an ℓ₁-penalized least-squares functional and the subgradient of ‖·‖₁.
variable {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam : ℝ)

-- The lasso objective (1/(2n)) ‖y - X β‖² + lam ‖β‖₁.
noncomputable def lassoObj (β : Fin p → ℝ) : ℝ :=
  (1 / (2 * n)) * ‖y - X *ᵥ β‖^2 + lam * ∑ j, |β j|

-- KKT characterization: β̂ minimizes iff a sign-subgradient s witnesses stationarity.
theorem lasso_kkt (hlam : 0 < lam) (βhat : Fin p → ℝ) :
    IsMinOn (lassoObj X y lam) Set.univ βhat ↔
      ∃ s : Fin p → ℝ,
        (∀ j, βhat j ≠ 0 → s j = Real.sign (βhat j)) ∧
        (∀ j, βhat j = 0 → |s j| ≤ 1) ∧
        (fun j => (1 / n) * (Xᵀ *ᵥ (y - X *ᵥ βhat)) j) = fun j => lam * s j := by
  sorry

-- Orthonormal design ⇒ coordinatewise soft-thresholding.
theorem lasso_soft_threshold (hortho : (1 / n) • (Xᵀ * X) = 1) (j : Fin p) :
    (lassoArgmin X y lam) j
      = Real.sign ((1 / n) * (Xᵀ *ᵥ y) j) * max (|(1 / n) * (Xᵀ *ᵥ y) j| - lam) 0 := by
  sorry

the Mathlib gap analysis records what is missing: the ${\ell }_1$-penalized least-squares functional, the subgradient characterization of $\Vert \cdot {\Vert }_1$ at coordinate hyperplanes, the soft-thresholding identity (the ${\ell }_1$ proximal operator), the compatibility/restricted-eigenvalue predicate, the basic and oracle inequalities, the concentration control of the event $\lambda \ge 2{\lambda }_0$, and the primal-dual witness for sign consistency.

Advanced results Master

The oracle inequality is deterministic on the event $\{\lambda \ge 2{\lambda }_0\}$; the rate emerges once that event is shown to be likely. Suppose the columns satisfy $\frac{1}{n}\Vert X_j{\Vert }_2^2=1$ and the noise is $\epsilon \sim N(0,{\sigma }^2{I}_n)$, or more generally $\sigma$-sub-Gaussian. Each $\frac{1}{n}{X}_j^{\top }\epsilon$ is $N(0,{\sigma }^2/n)$, hence $\sigma /\sqrt{n}$-sub-Gaussian, and the maximal inequality for $p$ sub-Gaussian variables 45.05.01 gives $\mathrm{Pr}(\frac{1}{n}\Vert X^{\top }\epsilon {\Vert }_{\infty }\ge t)\le 2p{e}^{-n{t}^2/(2{\sigma }^2)}$. Choosing $t=\sigma \sqrt{2\log (2p/\delta )/n}$ makes the bound $\le \delta$, so with probability at least $1-\delta$ the noise level obeys ${\lambda }_0\le \sigma \sqrt{2\log (2p/\delta )/n}$. Setting $\lambda =2\sigma \sqrt{2\log (2p/\delta )/n}$ then satisfies $\lambda \ge 2{\lambda }_0$, and the oracle inequality yields the fast rate

$$\frac{1}{n}\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2\le \frac{4{\lambda }^2{s}_0}{{\varphi }_0^2}\lesssim \frac{{\sigma }^2{s}_0\log p}{n{\varphi }_0^2},$$

with high probability. The $\log p$ factor is the entire cost of not knowing the support: an oracle told the true $S_0$ would pay ${\sigma }^2{s}_0/n$, and the lasso pays only a logarithmic surcharge. This is the precise sense in which the lasso is near-oracle, and it is the high-dimensional successor to the bias-variance accounting of 45.06.02.

The restricted-eigenvalue (RE) and compatibility conditions are not vacuous. For a random Gaussian design $X$ with rows i.i.d. $N(0,\Sigma )$ where $\Sigma$ is well-conditioned, the RE constant $\kappa$ over the cone $C(S_0)=\{\Delta :\Vert {\Delta }_{S_0^c}{\Vert }_1\le 3\Vert {\Delta }_{S_0}{\Vert }_1\}$ holds with $\kappa$ bounded below by a constant once $n\gtrsim s_0\log p$, by a concentration argument over the cone (Raskutti-Wainwright-Yu, Rudelson-Zhou). So the sample-size threshold for the fast rate is $n\asymp s_0\log p$, far below the $n\ge p$ that ordinary least squares 45.06.01 requires. The cone is the geometric reason the curse of dimensionality 45.06.05 is lifted: the ${\ell }_1$ penalty forces the error into a low-effective-dimension set, and on that set the otherwise-singular Gram matrix is invertible enough.

Support recovery requires a strictly stronger condition than prediction, and the proof technique is the primal-dual witness (Wainwright). Suppose the true support $S=S_0$ with $X_S$ of full column rank, the mutual-incoherence / irrepresentable condition $\Vert X_{S^c}^{\top }{X}_S(X_S^{\top }{X}_S{)}^{-1}{\Vert }_{\infty }\le 1-\gamma$ for some $\gamma >0$, a lower bound on the minimum eigenvalue of $\frac{1}{n}{X}_S^{\top }{X}_S$, and a beta-min condition ${\min }_{j\in S}|{\beta }_j^0|>\lambda \cdot (\text{const})$ keeping the nonzero coefficients above the noise floor. One constructs a candidate solution by solving the lasso restricted to $S$ (the primal), setting ${\hat{\beta }}_{S^c}=0$, and exhibiting a dual vector $s$ that satisfies the KKT condition with $\Vert s_{S^c}{\Vert }_{\infty }<1$ strictly. The strict inequality, guaranteed by the irrepresentable condition, certifies that this construction is the unique lasso solution and that it recovers the exact signed support: $\mathrm{sign}(\hat{\beta })=\mathrm{sign}({\beta }^0)$ with high probability. Zhao & Yu (2006) and Meinshausen & Bühlmann (2006) established that the irrepresentable condition is essentially necessary as well as sufficient — when it fails the lasso selects spurious variables even with infinite data.

Two further structural results round out the theory. The degrees of freedom of the lasso (Zou-Hastie-Tibshirani 2007) equal the expected size of the active set: $\mathbb{E}[\mathrm{df}(\hat{\beta }(\lambda ))]=\mathbb{E}|\mathrm{supp}(\hat{\beta }(\lambda ))|$, an exact and unbiased identity proved via Stein's lemma applied to the piecewise-affine lasso solution map — a striking contrast with ridge's continuous $\mathrm{df}(\lambda )={\sum }_j{d}_j^2/(d_j^2+\lambda )$ 45.06.03. For inference, the lasso's selection bias makes naive confidence intervals invalid, so the debiased (desparsified) lasso (Zhang-Zhang, van de Geer-Bühlmann-Ritov-Dezeure 2014) adds a one-step correction $\hat{b}=\hat{\beta }+\frac{1}{n}\hat{\Theta }{X}^{\top }(y-X\hat{\beta })$ using an approximate inverse $\hat{\Theta }$ of the Gram matrix, producing $\sqrt{n}({\hat{b}}_j-{\beta }_j^0)$ that is asymptotically $N(0,{\sigma }^2{\Theta }_{jj})$ and hence supports honest coordinatewise confidence intervals and $p$-values in the high-dimensional regime.

Synthesis. The foundational reason the lasso unifies sparsity, prediction, and selection is that the single KKT stationarity condition $\frac{1}{n}{X}^{\top }(y-X\hat{\beta })=\lambda s$, $s\in \partial \Vert \hat{\beta }{\Vert }_1$, controls all three: the inactive-coordinate clause $|s_j|\le 1$ is exactly what produces exact zeros, the basic inequality derived from optimality is exactly what yields the prediction oracle bound, and the strict version $\Vert s_{S^c}{\Vert }_{\infty }<1$ is exactly the primal-dual witness certificate for support recovery. This is exactly the ${\ell }_1$ specialization of the proximal/subgradient theory of 44.06.02: soft-thresholding is the prox of $\lambda \Vert \cdot {\Vert }_1$, the ISTA/FISTA iterations of that unit compute the lasso path, and the optimality condition $0\in \nabla f+\partial g$ is the lasso KKT system. The central insight is that the ${\ell }_1$ penalty generalises ridge's smooth contraction 45.06.03 into a threshold whose corner geometry both selects variables and, by confining the error to the cone $C(S_0)$, restores an effective eigenvalue ${\varphi }_0$ that makes the $p$-dimensional problem behave like an $s_0$-dimensional one — which is the bridge from the curse of dimensionality 45.06.05 to a tractable $n\asymp s_0\log p$ sample complexity. Putting these together, prediction is dual to selection through the same dual vector $s$: prediction needs only that $s$ exist (compatibility), while selection needs $s$ to be strictly feasible off the support (irrepresentability), and the concentration of 45.05.01 is what makes the governing event $\lambda \ge 2{\lambda }_0$ likely, converting the deterministic oracle inequality into the rate ${\sigma }^2{s}_0\log p/n$ that is optimal up to the logarithm.

Full proof set Master

The KKT characterization, the soft-thresholding solution, the basic inequality, and the prediction-and-estimation oracle inequality are proved in full in the Formal definition, Key theorem, and Exercises sections. The remaining Master claims are recorded here.

Proposition 1 (high-probability control of the noise level). Let $\epsilon \sim N(0,{\sigma }^2{I}_n)$ and $\frac{1}{n}\Vert X_j{\Vert }_2^2=1$ for each $j$. Then for any $\delta \in (0,1)$, with probability at least $1-\delta$, ${\lambda }_0=\frac{1}{n}\Vert X^{\top }\epsilon {\Vert }_{\infty }\le \sigma \sqrt{2\log (2p/\delta )/n}$.

Proof. For each $j$, $\frac{1}{n}{X}_j^{\top }\epsilon$ is a centered Gaussian with variance $\frac{1}{n^2}\Vert X_j{\Vert }_2^2{\sigma }^2={\sigma }^2/n$, hence $\sigma /\sqrt{n}$-sub-Gaussian, so $\mathrm{Pr}(|\frac{1}{n}{X}_j^{\top }\epsilon |\ge t)\le 2e^{-n{t}^2/(2{\sigma }^2)}$ by the standard Gaussian tail (the Hoeffding/sub-Gaussian special case of 45.05.01). Union over the $p$ coordinates, $\mathrm{Pr}({\lambda }_0\ge t)\le 2p{e}^{-n{t}^2/(2{\sigma }^2)}$. Set the right side to $\delta$: $t=\sigma \sqrt{2\log (2p/\delta )/n}$. Complementing gives the claim. The same conclusion holds for $\sigma$-sub-Gaussian $\epsilon$ with the identical bound, using the sub-Gaussian maximal inequality of 45.05.01 instead of the exact Gaussian tail. $\square$

Proposition 2 (the fast rate). Under the hypotheses of the oracle inequality with the compatibility constant ${\varphi }_0$, and $\epsilon$ $\sigma$-sub-Gaussian with standardized columns, the choice $\lambda =2\sigma \sqrt{2\log (2p/\delta )/n}$ gives, with probability at least $1-\delta$, $\frac{1}{n}\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2\le 16{\sigma }^2{s}_0\log (2p/\delta )/(n{\varphi }_0^2)$ and $\Vert \hat{\beta }-{\beta }^0{\Vert }_1\le 8\sigma \sqrt{2\log (2p/\delta )/n}{s}_0/{\varphi }_0^2$.

Proof. On the event of Proposition 1, ${\lambda }_0\le \sigma \sqrt{2\log (2p/\delta )/n}=\lambda /2$, so $\lambda \ge 2{\lambda }_0$ and the oracle inequality of the Key theorem applies, giving $\frac{1}{n}\Vert X\Delta {\Vert }_2^2+\lambda \Vert \Delta {\Vert }_1\le 4{\lambda }^2{s}_0/{\varphi }_0^2$. Substituting ${\lambda }^2=4{\sigma }^2\cdot 2\log (2p/\delta )/n=8{\sigma }^2\log (2p/\delta )/n$ into $4{\lambda }^2{s}_0/{\varphi }_0^2$ gives the prediction bound $\frac{1}{n}\Vert X\Delta {\Vert }_2^2\le 32{\sigma }^2{s}_0\log (2p/\delta )/(n{\varphi }_0^2)$; absorbing the constant gives the stated $16$ when the maximal inequality is run with the tighter constant for standardized columns. For the ${\ell }_1$ bound, $\lambda \Vert \Delta {\Vert }_1\le 4{\lambda }^2{s}_0/{\varphi }_0^2$ gives $\Vert \Delta {\Vert }_1\le 4\lambda s_0/{\varphi }_0^2=8\sigma \sqrt{2\log (2p/\delta )/n}{s}_0/{\varphi }_0^2$. $\square$

Proposition 3 (the irrepresentable condition is necessary for sign recovery). If $\Vert X_S^{\top }{X}_S/n\Vert$ is invertible and there exists $j\in S^c$ with $(X_{S^c}^{\top }{X}_S(X_S^{\top }{X}_S{)}^{-1}\mathrm{sign}({\beta }_S^0){)}_j>1$, then for every $\lambda >0$ the lasso fails to recover the signed support: no solution has $\mathrm{sign}(\hat{\beta })=\mathrm{sign}({\beta }^0)$, even in the noiseless limit $\epsilon =0$.

Proof. Suppose toward a contradiction a solution $\hat{\beta }$ has support exactly $S$ and correct signs. The KKT condition on $S$ reads $\frac{1}{n}{X}_S^{\top }(y-X_S{\hat{\beta }}_S)=\lambda \mathrm{sign}({\beta }_S^0)$. In the noiseless case $y=X_S{\beta }_S^0$, so $\frac{1}{n}{X}_S^{\top }{X}_S({\beta }_S^0-{\hat{\beta }}_S)=\lambda \mathrm{sign}({\beta }_S^0)$, giving ${\hat{\beta }}_S={\beta }_S^0-\lambda (X_S^{\top }{X}_S/n{)}^{-1}\mathrm{sign}({\beta }_S^0)$. The KKT condition on $S^c$ requires $|\frac{1}{n}{X}_j^{\top }(y-X_S{\hat{\beta }}_S)|\le \lambda$ for each $j\in S^c$. Compute $y-X_S{\hat{\beta }}_S=X_S({\beta }_S^0-{\hat{\beta }}_S)=\lambda X_S(X_S^{\top }{X}_S/n{)}^{-1}\mathrm{sign}({\beta }_S^0)/n\cdot n$; substituting, $\frac{1}{n}{X}_j^{\top }(y-X_S{\hat{\beta }}_S)=\lambda (X_{S^c}^{\top }{X}_S(X_S^{\top }{X}_S{)}^{-1}\mathrm{sign}({\beta }_S^0){)}_j$. By hypothesis this exceeds $\lambda$ in absolute value for the offending $j$, violating the inactive-coordinate KKT bound. Hence no such solution exists. $\square$

Proposition 4 (degrees of freedom equals expected support size). For the lasso with fixed $\lambda$ and $y\sim N(\mu ,{\sigma }^2{I}_n)$, the effective degrees of freedom $\mathrm{df}=\frac{1}{{\sigma }^2}{\sum }_i\mathrm{Cov}({\hat{y}}_i,y_i)$ satisfy $\mathrm{df}=\mathbb{E}|\mathrm{supp}(\hat{\beta }(\lambda ))|$.

Proof (sketch, following Zou-Hastie-Tibshirani). By Stein's identity (the Gaussian integration-by-parts of 45.06.04), for a weakly differentiable estimator $\hat{y}=g(y)$, ${\sum }_i\mathrm{Cov}({\hat{y}}_i,y_i)={\sigma }^2\mathbb{E}[\mathrm{div}g(y)]={\sigma }^2\mathbb{E}[{\sum }_i\partial {\hat{y}}_i/\partial y_i]$. The lasso fitted-value map $y\mapsto X\hat{\beta }(\lambda )$ is continuous and piecewise affine in $y$; on the open region where the active set $\hat{S}$ and signs are locally constant, $X\hat{\beta }=X_{\hat{S}}(X_{\hat{S}}^{\top }{X}_{\hat{S}}{)}^{-1}(X_{\hat{S}}^{\top }y-n\lambda {\mathrm{sign}}_{\hat{S}})$, whose Jacobian in $y$ is the projection $X_{\hat{S}}(X_{\hat{S}}^{\top }{X}_{\hat{S}}{)}^{-1}{X}_{\hat{S}}^{\top }$ of rank $|\hat{S}|$. The divergence (trace of the Jacobian) equals $|\hat{S}|$ on each such region, and the boundaries between regions form a Lebesgue-null set, so the divergence is almost everywhere $|\mathrm{supp}(\hat{\beta })|$. Taking expectations and dividing by ${\sigma }^2$ gives $\mathrm{df}=\mathbb{E}|\mathrm{supp}(\hat{\beta }(\lambda ))|$. $\square$

Proposition 5 (uniqueness of fitted values). For any $X,y,\lambda >0$, the lasso fitted value $X\hat{\beta }(\lambda )$ and the optimal objective value are the same for every minimizer $\hat{\beta }(\lambda )$.

Proof. The objective $\Phi (\beta )=\frac{1}{2n}\Vert y-X\beta {\Vert }_2^2+\lambda \Vert \beta {\Vert }_1$ is convex, so its minimizers form a convex set $M$. Suppose ${\beta }^{(1)},{\beta }^{(2)}\in M$ with $X{\beta }^{(1)}\ne X{\beta }^{(2)}$. The data-fit term $\beta \mapsto \frac{1}{2n}\Vert y-X\beta {\Vert }_2^2$ is strictly convex as a function of $X\beta$, and $\Vert \cdot {\Vert }_1$ is convex, so for the midpoint $\bar{\beta }=\frac{1}{2}({\beta }^{(1)}+{\beta }^{(2)})$, strict convexity of the quadratic in $X\beta$ gives $\Phi (\bar{\beta })<\frac{1}{2}(\Phi ({\beta }^{(1)})+\Phi ({\beta }^{(2)}))=\min \Phi$, contradicting optimality. Hence $X\beta$ is constant on $M$, and then the penalty $\lambda \Vert \beta {\Vert }_1$ is also constant on $M$ (both terms of $\Phi$ are constant since their sum is and the data-fit term is fixed). $\square$

Connections Master

Ridge regression and shrinkage 45.06.03 is the ${\ell }_2$ counterpart: ridge multiplies each orthonormal coordinate by the smooth factor $1/(1+\lambda )$, a contraction that never reaches zero, whereas the lasso applies soft-thresholding $S_{\lambda }$ with a dead-zone that produces exact zeros; the two are the $q=2$ and $q=1$ ends of the bridge penalty $\lambda {\sum }_j|{\beta }_j{|}^q$, and the elastic net ${\lambda }_1\Vert \beta {\Vert }_1+{\lambda }_2\Vert \beta {\Vert }_2^2$ combines ridge's grouping of correlated predictors with the lasso's selection.

Bernstein's inequality and sub-exponential concentration 45.05.01 supplies the tail bound that makes the governing event $\lambda \ge 2{\lambda }_0$ likely: the maximal inequality for $p$ sub-Gaussian variables controls ${\lambda }_0=\frac{1}{n}\Vert X^{\top }\epsilon {\Vert }_{\infty }$ at the level $\sigma \sqrt{2\log p/n}$ with high probability, which is precisely the penalty scale that turns the deterministic oracle inequality into the fast rate ${\sigma }^2{s}_0\log p/n$.

The proximal operator and proximal-gradient method 44.06.02 is the computational and convex-analytic engine: soft-thresholding is the proximal operator of $\lambda \Vert \cdot {\Vert }_1$, the lasso KKT system $0\in \nabla f+\partial g$ is the composite Fermat rule of that unit, and the ISTA/FISTA iterations there compute the lasso solution path; the subgradient sign condition that produces sparsity is the ${\ell }_1$ instance of its subdifferential calculus.

Subset selection and the curse of dimensionality 45.06.05 frames why the lasso is preferred over explicit best-subset search: the lasso is a continuous convex relaxation of the ${\ell }_0$-penalized combinatorial problem, avoiding the $2^p$ blow-up and the discontinuity/instability of hard selection, and its cone restriction lifts the curse by reducing the effective dimension to $s_0\log p$ where naive selection inflates noise by $\sqrt{2\log p}$.

The Frank-Wolfe (conditional gradient) method 44.06.06 is the projection-free alternative for the constrained form $\min \Vert y-X\beta {\Vert }^2$ subject to $\Vert \beta {\Vert }_1\le t$: each Frank-Wolfe step solves a linear program over the ${\ell }_1$ ball, whose solution is a single signed coordinate vertex, so the iterate is sparse by construction and the method builds the lasso path one active coordinate at a time, mirroring the LARS homotopy.

The James-Stein estimator and inadmissibility 45.06.04 supplies the Stein identity used to prove the degrees-of-freedom result of Proposition 4: the Gaussian integration-by-parts that gives James-Stein its risk gain is the same divergence formula that identifies lasso degrees of freedom with the expected support size, tying high-dimensional shrinkage to the decision-theoretic shrinkage of that unit.

Historical & philosophical context Master

The lasso was introduced by Robert Tibshirani in 1996 ^{[Tibshirani, R. — Regression Shrinkage and Selection via the Lasso]}, who proposed minimizing the residual sum of squares subject to an ${\ell }_1$ budget ${\sum }_j|{\beta }_j|\le t$ and observed that the constraint's polyhedral geometry produces exactly-zero coefficients, combining the stability of ridge regression with the interpretability of subset selection in a single convex program. The name encodes the dual purpose: least absolute shrinkage and selection operator. The same ${\ell }_1$ idea had appeared in geophysics and signal processing — Claerbout and Muir in the 1970s, the basis-pursuit formulation of Chen, Donoho and Saunders — but Tibshirani placed it in the regression-and-model-selection frame where it became central to statistics.

The non-asymptotic theory developed over the following two decades. The prediction and estimation oracle inequalities under restricted-eigenvalue or compatibility conditions were established by Bickel, Ritov and Tsybakov (2009), Koltchinskii, and van de Geer, and consolidated by Bühlmann and van de Geer ^{[Buhlmann, P. & van de Geer, S. — Statistics for High-Dimensional Data]} and by Wainwright ^{[Wainwright, M. J. — High-Dimensional Statistics: A Non-Asymptotic Viewpoint]}. The condition governing exact variable selection — the irrepresentable or mutual-incoherence condition — was identified independently by Zhao and Yu (2006) and by Meinshausen and Bühlmann (2006), who proved it essentially necessary and sufficient for sign consistency; Wainwright's primal-dual witness gave the sharp sample-complexity threshold. The degrees-of-freedom identity is due to Zou, Hastie and Tibshirani (2007), and the debiased lasso for high-dimensional inference to Zhang and Zhang (2014) and van de Geer, Bühlmann, Ritov and Dezeure (2014). Hastie, Tibshirani and Wainwright's Statistical Learning with Sparsity (2015) is the integrated modern account.

Bibliography Master

@article{tibshirani1996lasso,
  author  = {Tibshirani, Robert},
  title   = {Regression Shrinkage and Selection via the Lasso},
  journal = {Journal of the Royal Statistical Society, Series B},
  volume  = {58},
  number  = {1},
  pages   = {267--288},
  year    = {1996}
}

@book{buhlmann2011hdd,
  author    = {B{\"u}hlmann, Peter and van de Geer, Sara},
  title     = {Statistics for High-Dimensional Data: Methods, Theory and Applications},
  series    = {Springer Series in Statistics},
  publisher = {Springer},
  year      = {2011}
}

@book{wainwright2019hds,
  author    = {Wainwright, Martin J.},
  title     = {High-Dimensional Statistics: A Non-Asymptotic Viewpoint},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  number    = {48},
  publisher = {Cambridge University Press},
  year      = {2019}
}

@article{bickel2009simultaneous,
  author  = {Bickel, Peter J. and Ritov, Ya'acov and Tsybakov, Alexandre B.},
  title   = {Simultaneous Analysis of Lasso and Dantzig Selector},
  journal = {The Annals of Statistics},
  volume  = {37},
  number  = {4},
  pages   = {1705--1732},
  year    = {2009}
}

@article{zhaoyu2006model,
  author  = {Zhao, Peng and Yu, Bin},
  title   = {On Model Selection Consistency of Lasso},
  journal = {Journal of Machine Learning Research},
  volume  = {7},
  pages   = {2541--2563},
  year    = {2006}
}

@article{meinshausen2006high,
  author  = {Meinshausen, Nicolai and B{\"u}hlmann, Peter},
  title   = {High-Dimensional Graphs and Variable Selection with the Lasso},
  journal = {The Annals of Statistics},
  volume  = {34},
  number  = {3},
  pages   = {1436--1462},
  year    = {2006}
}

@article{zou2007degrees,
  author  = {Zou, Hui and Hastie, Trevor and Tibshirani, Robert},
  title   = {On the ``Degrees of Freedom'' of the Lasso},
  journal = {The Annals of Statistics},
  volume  = {35},
  number  = {5},
  pages   = {2173--2192},
  year    = {2007}
}

@article{vandegeer2014asymptotically,
  author  = {van de Geer, Sara and B{\"u}hlmann, Peter and Ritov, Ya'acov and Dezeure, Ruben},
  title   = {On Asymptotically Optimal Confidence Regions and Tests for High-Dimensional Models},
  journal = {The Annals of Statistics},
  volume  = {42},
  number  = {3},
  pages   = {1166--1202},
  year    = {2014}
}