Sparsity Inducing Property

In the previous page, we derived the Lasso objective and examined the mathematical properties of the L1 norm. We saw that unlike the L2 penalty, the L1 penalty has a constant derivative (in magnitude) as coefficients approach zero. But this mathematical property alone doesn't fully explain why optimization settles at exactly zero.

This page answers the central question: Why does L1 regularization produce sparse solutions?

Sparsity—having many coefficients equal exactly zero—is not merely a mathematical curiosity. It represents automatic feature selection, where the model identifies which variables truly matter and discards the rest. This has profound implications:

• Interpretability: A model with 10 non-zero coefficients out of 1,000 features tells a clear story
• Computational efficiency: Sparse models require less memory and compute faster
• Generalization: Eliminating irrelevant features reduces overfitting
• Scientific discovery: Sparsity reveals which factors drive outcomes

The most intuitive explanation for L1 sparsity comes from constrained optimization geometry. Let's develop this carefully.

Setup:

Consider the 2D case with coefficients $(\beta_1, \beta_2)$. The Lasso solves:

$$\min_{\beta_1, \beta_2} |\mathbf{y} - \beta_1\mathbf{x}_1 - \beta_2\mathbf{x}_2|_2^2 \quad \text{subject to} \quad |\beta_1| + |\beta_2| \leq t$$

The Constraint Regions:

• L1 constraint ($|\beta_1| + |\beta_2| \leq t$): A diamond with corners at $(t, 0)$, $(-t, 0)$, $(0, t)$, $(0, -t)$
• L2 constraint ($\beta_1^2 + \beta_2^2 \leq t^2$): A circle of radius $t$

The Objective Function's Level Sets:

The residual sum of squares $|\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2$ is a quadratic function of $\boldsymbol{\beta}$. Its level sets (curves of constant RSS) are ellipses centered at the OLS solution $\hat{\boldsymbol{\beta}}^{\text{OLS}}$.

Finding the Optimum:

We seek the point in the constraint region that achieves minimum RSS. Geometrically, we expand ellipses outward from the OLS solution until they first touch the constraint boundary.

Probability of Corner Contact:

Why are corners so likely to be optimal? Consider the geometric degrees of freedom:

• An ellipse tangent to a smooth curve has one degree of freedom removed (normal vectors align)
• An ellipse tangent to a corner has two degrees of freedom removed (the corner is a constraint from two directions)

Corners are "stickier"—the optimization must work harder to escape them. Unless the OLS solution aligns precisely with non-corner directions, the Lasso solution lands on a corner.

Formal Statement:

For generic data (OLS solution in general position), as we vary $t$ from 0 to $\infty$:

• The Lasso solution path traces through faces of increasing dimension
• Solutions spend "time" (range of $t$ values) at each face proportional to its dimension
• Vertices (full sparsity) are passed through unless the OLS solution is perfectly aligned with them
• Most solutions lie on low-dimensional faces (high sparsity)

The geometric intuition from corners can be made rigorous through subdifferential calculus. This provides the mathematical machinery to understand why zero is a stable solution.

The Subdifferential of |β|:

Recall that for $f(\beta) = |\beta|$:

$$\partial f(\beta) = \begin{cases} {+1} & \beta > 0 \ {-1} & \beta < 0 \ [-1, +1] & \beta = 0 \end{cases}$$

Optimality at Zero:

For the Lasso objective $L(\beta) = \frac{1}{2}(y - x\beta)^2 + \lambda|\beta|$ in one dimension:

The condition for $\beta = 0$ to be optimal is:

$$0 \in \partial L(0) = {-xy} + \lambda \cdot [-1, 1] = [-xy - \lambda, -xy + \lambda]$$

This holds when $|xy| \leq \lambda$, i.e., when the correlation between feature and response is below the threshold.

Why This Creates Exact Zeros:

The interval subdifferential at zero provides "slack" in the optimality conditions. Compare:

The Critical Insight:

For L2 regularization, the subdifferential at zero is just ${0}$. To have $\beta = 0$ optimal, the data term's gradient must be exactly zero—a measure-zero event that essentially never happens.

For L1 regularization, the subdifferential at zero is the interval $[-1, 1]$. To have $\beta = 0$ optimal, the data term's gradient just needs to be bounded by $\lambda$—a condition with positive probability.

Mathematical Formulation (Multivariate):

For the full Lasso problem, the KKT conditions at an optimal $\hat{\boldsymbol{\beta}}$ are:

$$-\frac{1}{n}\mathbf{X}^T(\mathbf{y} - \mathbf{X}\hat{\boldsymbol{\beta}}) + \lambda \hat{\mathbf{s}} = \mathbf{0}$$

where $\hat{s}_j \in \partial|\hat{\beta}_j|$.

For components where $\hat{\beta}_j = 0$:

$$\left|\frac{1}{n}\mathbf{x}_j^T\mathbf{r}\right| \leq \lambda$$

where $\mathbf{r} = \mathbf{y} - \mathbf{X}\hat{\boldsymbol{\beta}}$ is the residual. Features with correlations below $\lambda$ are perfectly happy at zero.

The Lasso has an elegant Bayesian interpretation: it corresponds to Maximum A Posteriori (MAP) estimation under a Laplace prior on the coefficients.

The Laplace Distribution:

The Laplace (double-exponential) distribution has density:

$$p(\beta | b) = \frac{1}{2b} \exp\left(-\frac{|\beta|}{b}\right)$$

with scale parameter $b > 0$. It's symmetric around zero with heavier tails than the Gaussian and a sharp peak at zero—this peak is key to sparsity.

Prior Distribution on Coefficients:

Assume i.i.d. Laplace priors on each coefficient:

$$p(\boldsymbol{\beta}) = \prod_{j=1}^p \frac{1}{2b} \exp\left(-\frac{|\beta_j|}{b}\right) = \frac{1}{(2b)^p} \exp\left(-\frac{|\boldsymbol{\beta}|_1}{b}\right)$$

MAP Estimation:

With Gaussian likelihood $\mathbf{y} | \mathbf{X}, \boldsymbol{\beta} \sim \mathcal{N}(\mathbf{X}\boldsymbol{\beta}, \sigma^2\mathbf{I})$, the posterior is:

$$p(\boldsymbol{\beta} | \mathbf{y}, \mathbf{X}) \propto \exp\left(-\frac{1}{2\sigma^2}|\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2 - \frac{|\boldsymbol{\beta}|_1}{b}\right)$$

Taking the negative log and minimizing (MAP):

$$\hat{\boldsymbol{\beta}}^{\text{MAP}} = \underset{\boldsymbol{\beta}}{\arg\min}\left{\frac{1}{2\sigma^2}|\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2 + \frac{1}{b}|\boldsymbol{\beta}|_1\right}$$

This is exactly the Lasso with $\lambda = \sigma^2/b$.

Why the Laplace Prior Induces Sparsity:

The Laplace density has a cusp at zero—a discontinuous derivative. This creates a probability "spike" at exactly zero.

Intuitively, the prior strongly believes most coefficients should be near zero, with occasional large values (heavy tails). This matches our scientific intuition: in high-dimensional problems, most features are probably irrelevant, but a few might have substantial effects.

Contrast with the Gaussian:

The Gaussian prior has a smooth dome at zero. There's no particular attraction to exactly zero—coefficients near zero have similar prior probability to those exactly at zero. This smoothness translates to the inability to produce exact sparsity.

Hyperprior Perspective:

The Laplace prior can be written as a scale mixture of normals:

$$\beta_j | \tau_j^2 \sim \mathcal{N}(0, \tau_j^2), \quad \tau_j^2 \sim \text{Exponential}(\lambda^2/2)$$

This representation connects Lasso to hierarchical Bayesian models and enables extensions like the Bayesian Lasso, which provides full posterior inference rather than just point estimates.

Given that L1 produces sparsity, a natural question arises: How sparse will the solution be? The answer depends on $\lambda$, the data distribution, and the true underlying signal.

The Sparsity-λ Relationship:

As $\lambda$ increases, more coefficients become zero. We can characterize this relationship:

For $\lambda \geq \lambda_{\max}$:

$$\lambda_{\max} = \frac{1}{n}|\mathbf{X}^T\mathbf{y}|_\infty = \max_j \left|\frac{1}{n}\mathbf{x}_j^T\mathbf{y}\right|$$

All coefficients are zero. This is the first $\lambda$ value where sparsity = $p$ (all features removed).

As $\lambda \downarrow 0$:

More coefficients become non-zero. As $\lambda \to 0$, the Lasso solution approaches the OLS solution (if $n > p$) or a minimum-norm solution (if $n < p$).

The Active Set:

Define the active set as $\mathcal{A}(\lambda) = {j : \hat{\beta}_j(\lambda) eq 0}$. Its cardinality $|\mathcal{A}(\lambda)|$ is the degrees of freedom of the model.

As $\lambda$ decreases, $|\mathcal{A}(\lambda)|$ generally increases, though coefficients can also exit the active set (become zero again) in some cases.

Factors Affecting Sparsity:

1. Signal Strength: Strong true signals (large $|\beta_j^*|$) remain non-zero even at large $\lambda$. Weak signals are eliminated first.

2. Feature Correlations: Highly correlated features compete for selection. Lasso tends to select one and zero out others (instability).

3. Sample Size: More data provides better estimation of which features matter, stabilizing the active set.

4. Noise Level: Higher noise requires larger $\lambda$ for good prediction, which increases sparsity.

Degrees of Freedom of Lasso:

An important theoretical result: for the Lasso, the expected degrees of freedom equals the expected number of non-zero coefficients:

$$\mathbb{E}[\text{df}_{\text{lasso}}(\lambda)] = \mathbb{E}[|\mathcal{A}(\lambda)|]$$

This elegant result (proved via Stein's Lemma) enables unbiased estimation of prediction risk and informs model selection criteria like AIC and Cp.

A fundamental question in high-dimensional statistics: Under what conditions does Lasso correctly identify the truly non-zero coefficients?

This is the problem of support recovery or variable selection consistency. The answer involves conditions on the design matrix $\mathbf{X}$ that govern whether Lasso can distinguish signal from noise.

The Irrepresentable Condition:

Let $S = {j : \beta_j^* eq 0}$ be the true support (indices of non-zero coefficients) and $S^c$ its complement (zero coefficients).

Partition the Gram matrix $\mathbf{C} = \frac{1}{n}\mathbf{X}^T\mathbf{X}$:

$$\mathbf{C} = \begin{pmatrix} \mathbf{C}{SS} & \mathbf{C}{SS^c} \ \mathbf{C}{S^cS} & \mathbf{C}{S^cS^c} \end{pmatrix}$$

The Irrepresentable Condition states:

$$|\mathbf{C}{S^cS}\mathbf{C}{SS}^{-1}\text{sign}(\boldsymbol{\beta}S^*)|\infty < 1$$

Interpretation:

This condition limits how much the irrelevant features ($S^c$) can be represented by the relevant features ($S$). If irrelevant features correlate too strongly with relevant ones weighted by the true coefficient signs, Lasso may include spurious variables.

When the Condition Fails:

If the irrepresentable condition fails, there exists a noise feature $j \in S^c$ that is "too well represented" by signal features. This noise feature can enter the Lasso model even in the large-sample limit.

Example of Failure:

Consider two features with correlation $\rho$:

• Feature 1: truly relevant ($\beta_1^* = 1$)
• Feature 2: irrelevant ($\beta_2^* = 0$)

If $|\rho| > 0.5$, the irrepresentable condition fails for some sign configurations, and Lasso may include Feature 2 even with infinite data.

Practical Implications:

1. In highly correlated designs, Lasso may not achieve exact support recovery
2. For prediction purposes, this may not matter—correlated features are interchangeable
3. For interpretability/discovery, consider Elastic Net (stabilizes selection) or multi-step procedures

The Beta-Min Condition:

Beyond structural conditions on $\mathbf{X}$, we also need the true non-zero coefficients to be large enough:

$$\min_{j \in S} |\beta_j^*| \geq c \cdot \sqrt{\frac{\log p}{n}}$$

for some constant $c > 0$. Coefficients below this threshold are undetectable in high-dimensional settings—they blend into the noise floor.

The theoretical guarantee of sparsity meets practical reality in ways that require understanding. Let's examine how sparsity manifests in real applications.

When Sparsity Assumptions Hold:

Lasso's sparsity assumption is that the true model involves a small number of features. This assumption is reasonable in many domains:

When Sparsity Fails:

Not all domains exhibit true sparsity:

• Dense signals: If outcomes genuinely depend on many features (e.g., complex traits influenced by many genes with small effects), forcing sparsity introduces bias
• Correlated predictors: When features come in groups (e.g., related genes), Lasso arbitrarily selects within groups
• Nonlinear effects: True sparsity in expanded feature space doesn't imply sparsity in original features

Practical Sparsity Patterns:

In practice, the distinction between "exactly zero" and "negligibly small" coefficients matters for different purposes.

Exact Sparsity in Theory:

Mathematically, Lasso produces solutions where some $\hat{\beta}_j = 0$ exactly. This is a genuine zero, not a floating-point approximation.

Numerical Considerations:

In floating-point arithmetic, what we observe is that some coefficients are set to values like $10^{-16}$, which is effectively zero. Software implementations typically threshold coefficients below $10^{-10}$ or similar.

Approximate Sparsity:

The concept of approximate sparsity (or effective sparsity) is often more useful:

• Exact $s$-sparse: Exactly $s$ non-zero coefficients, rest exactly zero
• Approximately sparse: Many small coefficients, few large ones
• $\ell_q$ ball: $\sum_j |\beta_j|^q \leq R$ for some $0 < q < 1$ (not really sparse, but compressible)

Real data often exhibits approximate sparsity: a few dominant coefficients, many small but non-zero contributions.

Thresholding for Interpretation:

For model interpretation, practitioners often apply a secondary threshold to Lasso coefficients:

1. Fit Lasso, obtaining $\hat{\boldsymbol{\beta}}$
2. Apply threshold $\tau$: keep $\hat{\beta}_j$ only if $|\hat{\beta}_j| > \tau$
3. Optionally, refit OLS on selected features (de-biasing)

This two-stage approach separates selection (Lasso) from estimation (clean-up). The threshold $\tau$ can be chosen via stability selection (see below).

Stability Selection:

A robust approach to determine which zeros are "real":

1. Subsample data many times
2. Run Lasso on each subsample
3. Track how often each feature is selected (has non-zero coefficient)
4. Features selected frequently across subsamples are stable; occasional selections are spurious

This addresses the instability of Lasso selection under perturbation, particularly with correlated features.