Lasso Regression (L1 Regularization)

Mathematics provides the precision, but geometry provides the intuition. The geometric interpretation of Lasso versus Ridge regularization is one of the most illuminating visualizations in all of machine learning—it makes immediately clear why L1 produces sparsity while L2 does not.

This page develops that geometric understanding systematically. We will:

1. Visualize the constraint regions (L1 diamonds vs. L2 circles)
2. Understand the loss function's level sets (elliptical contours)
3. See how these geometric objects interact to determine optimal solutions
4. Generalize to higher dimensions and understand the geometry of sparsity

By the end, you will have a mental picture that lets you reason about regularization geometrically—an intuition that transfers to many other constrained optimization problems.

Let's begin by visualizing the constraint regions for L1 and L2 regularization in two dimensions. Consider coefficients $(\beta_1, \beta_2)$.

The L2 Constraint (Ridge):

$$\beta_1^2 + \beta_2^2 \leq t^2$$

This defines a disk of radius $t$ centered at the origin. Its boundary is a circle—perfectly smooth with no corners or edges. Every point on the boundary has a unique normal direction.

The L1 Constraint (Lasso):

$$|\beta_1| + |\beta_2| \leq t$$

This defines a diamond (rotated square) with vertices at $(t, 0)$, $(-t, 0)$, $(0, t)$, $(0, -t)$. The boundary consists of four straight edges meeting at four corners. Corners lie exactly on the coordinate axes.

Key Geometric Properties:

Why Corner Geometry Matters:

The crucial difference is the presence of corners (vertices) in the L1 constraint set. Corners are points where the boundary is not smooth—the normal direction is not uniquely defined.

At a corner, multiple normal directions are valid. This geometric property translates to the subdifferential being an interval rather than a single point at $\beta_j = 0$. The optimization can "rest" at a corner because there's no unique direction to move that decreases both the constraint violation and objective.

Higher-Dimensional Constraint Sets:

In $p$ dimensions:

• L2 constraint: $\sum_j \beta_j^2 \leq t^2$ is a hypersphere—smooth everywhere
• L1 constraint: $\sum_j |\beta_j| \leq t$ is a cross-polytope (hyperoctahedron)—with $2p$ vertices on coordinate axes and $2^p$ facets

The cross-polytope's vertices are ${\pm t \cdot \mathbf{e}j}{j=1}^p$ where $\mathbf{e}_j$ is the $j$-th standard basis vector. These vertices are the most sparse points—having only one non-zero coordinate.

To understand the constrained optimization geometry, we need to visualize the level sets (contour curves) of the loss function.

The Ordinary Least Squares Loss:

$$\mathcal{L}(\boldsymbol{\beta}) = |\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2 = (\boldsymbol{\beta} - \hat{\boldsymbol{\beta}}^{\text{OLS}})^T \mathbf{X}^T\mathbf{X} (\boldsymbol{\beta} - \hat{\boldsymbol{\beta}}^{\text{OLS}}) + \text{const}$$

This is a quadratic form centered at the OLS solution $\hat{\boldsymbol{\beta}}^{\text{OLS}}$.

Level Set Geometry:

The level sets ${\boldsymbol{\beta} : \mathcal{L}(\boldsymbol{\beta}) = c}$ are ellipsoids (ellipses in 2D) centered at $\hat{\boldsymbol{\beta}}^{\text{OLS}}$:

• Shape: Determined by the eigenvalues of $\mathbf{X}^T\mathbf{X}$
• Orientation: Determined by the eigenvectors of $\mathbf{X}^T\mathbf{X}$
• Center: Located at $\hat{\boldsymbol{\beta}}^{\text{OLS}} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$
• Nested structure: Smaller ellipses = lower loss, expanding outward from center

Special Cases:

1. Orthogonal design ($\mathbf{X}^T\mathbf{X} = n\mathbf{I}$): Level sets are circles (spheres) centered at OLS
2. Correlated features: Level sets are elongated ellipses aligned with correlation structure
3. Multicollinearity: Extremely elongated "cigar-shaped" ellipses nearly parallel to coefficient space

The constrained optimization problem seeks the point within the constraint region that minimizes the loss. Geometrically, we find where the smallest possible loss ellipse contacts the constraint boundary.

The Constrained Optimization View:

Starting from the OLS solution, we expand level set ellipses outward (increasing loss) until the first contact with the constraint boundary. This contact point is the constrained optimum.

For L2 (Circle) Constraint:

The first contact typically occurs at a point where the ellipse is tangent to the circle. Tangency means:

$$\nabla \mathcal{L}(\boldsymbol{\beta}^) = \mu \nabla g(\boldsymbol{\beta}^)$$

where $g(\boldsymbol{\beta}) = |\boldsymbol{\beta}|_2^2 - t^2$ is the constraint function and $\mu > 0$ is the Lagrange multiplier.

Since the circle is smooth everywhere, this tangency condition has no special preference for axis-aligned points. The contact point generically has both coordinates non-zero.

For L1 (Diamond) Constraint:

The first contact can occur either on an edge or at a corner:

Why Corners are Preferred:

Consider expanding an ellipse from the interior. The ellipse makes first contact with the closest point on the boundary. For the diamond:

• Corners are the boundary points closest to the origin in their respective directions
• The corners are extremal in the sense that they maximize the distance from the origin in axis directions
• Unless the ellipse is perfectly aligned with an edge (measure zero probability), corner contact is generic

Mathematical Argument:

The normal cone at a corner contains all directions pointing "outward" from the corner. At the vertex $(t, 0)$:

$$N_{(t,0)} = {(\alpha, \beta) : \alpha \geq |\beta|}$$

This is a large cone (45-degree angle in 2D). For the gradient of the loss to lie in this cone (the optimality condition), there's significant "room"—many possible gradient directions work.

At an edge point, the normal cone is just a single direction (the edge normal). Only when the loss gradient aligns exactly with this normal do we have an optimal edge point—a measure-zero event.

Probability Interpretation:

If we randomly generate problems (random $\mathbf{X}$, $\mathbf{y}$), the probability of corner contact approaches 1 for generic problem instances. Edge contact requires precise alignment that occurs with probability zero.

As we vary the constraint bound $t$ (equivalently, the regularization parameter $\lambda$), the solution traces a path through coefficient space. This path reveals the regularization-sparsity relationship geometrically.

The Lasso Path Geometrically:

1. $t = 0$ (or $\lambda = \infty$): The constraint region shrinks to the origin. Solution: $\hat{\boldsymbol{\beta}} = \mathbf{0}$ (maximum sparsity).

2. $t$ very small ($\lambda$ large): Small diamond with corners on axes. Most likely contact at a single corner—only one non-zero coefficient.

3. $t$ moderate ($\lambda$ moderate): Diamond grows. As corners pass the OLS solution's projections onto axes, more coefficients become non-zero.

4. $t$ large ($\lambda$ small): Diamond becomes large enough to contain the OLS solution. Solution approaches OLS (minimum regularization).

5. $t = \infty$ ($\lambda = 0$): No constraint. Solution equals OLS.

Sequential Feature Entry:

As $t$ increases (or $\lambda$ decreases), coefficients "enter" the model in order of their importance:

Geometric Interpretation of the Path:

The Lasso path traces through vertices and edges of the L1 polytope:

1. Starting at origin (all zeros, a vertex)
2. Moving along an edge (one coefficient varies, others zero)
3. Reaching a vertex (coefficient entry/exit event)
4. Turning onto a new edge
5. Eventually reaching a face or the interior (many non-zeros)

Between these transitions, the path is piecewise linear—coefficients change at constant rates. This remarkable property enables efficient Lasso path algorithms (LARS).

The Regularization Path Theorem:

For a fixed design matrix $\mathbf{X}$, as $\lambda$ decreases from $\lambda_{\max}$ to 0:

• The set of active variables changes at finitely many values of $\lambda$
• Between these change points, coefficients are linear in $\lambda$
• The entire path can be computed efficiently without evaluating at every $\lambda$

While we visualize in 2D or 3D, the geometric principles extend to arbitrary dimensions. High-dimensional geometry has counterintuitive properties that actually strengthen the sparsity argument.

The Cross-Polytope in p Dimensions:

The L1 ball ${\boldsymbol{\beta} : |\boldsymbol{\beta}|_1 \leq t}$ in $\mathbb{R}^p$ is a cross-polytope (or hyperoctahedron):

• Vertices: $2p$ points at ${\pm t \cdot \mathbf{e}j}{j=1}^p$ (each has exactly one non-zero coordinate)
• Edges: Connect vertices that differ in exactly one coordinate sign
• Faces: Defined by sign patterns on subsets of coordinates
• Facets (top faces): $2^p$ facets, each a $(p-1)$-simplex defined by fixing the signs of all coordinates

Concentration of Measure Phenomenon:

High-dimensional geometry exhibits surprising properties:

Volume Distribution:

Consider the volume of the L1 and L2 balls:

• L2 ball volume: $V_p^{L2}(t) = \frac{\pi^{p/2}}{\Gamma(p/2 + 1)} t^p$
• L1 ball volume: $V_p^{L1}(t) = \frac{2^p}{p!} t^p$

The ratio $V_p^{L1}(t) / V_p^{L2}(t)$ decreases rapidly with $p$. The L1 ball is much "pointier" than the L2 ball in high dimensions.

Probability of Sparse Solutions:

For a randomly oriented loss ellipsoid in $\mathbb{R}^p$, the probability of contacting a face of dimension $k$ (having $p-k$ zeros) is:

$$P(\text{$k$-dimensional face contact}) \propto \binom{p}{k} \cdot (\text{geometry factor})$$

The geometry factor favors lower-dimensional faces (more zeros). Combined with the combinatorial factor, this gives a concrete probability distribution over sparsity levels.

The Typical Solution:

In high dimensions with moderate $\lambda$, the typical Lasso solution has:

• Many exactly zero coefficients
• A few non-zero coefficients of varying magnitudes
• Sparsity level depending on $\lambda$, signal strength, and correlation structure

The Lasso can be formulated as either a penalized problem or a constrained problem. Geometrically, these formulations are dual perspectives on the same optimization.

Penalized Form:

$$\min_\boldsymbol{\beta} \left{ \frac{1}{2}|\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2 + \lambda|\boldsymbol{\beta}|_1 \right}$$

Geometric interpretation: Find the point where the sum of loss and penalty is minimized. The penalty "warps" the objective, creating valleys along coordinate axes.

Constrained Form:

$$\min_\boldsymbol{\beta} \frac{1}{2}|\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2 \quad \text{s.t.} \quad |\boldsymbol{\beta}|_1 \leq t$$

Geometric interpretation: Find the minimum loss point within the L1 diamond.

The Duality Correspondence:

For every $\lambda \geq 0$, there exists a unique $t \geq 0$ such that both formulations have the same solution. The correspondence is:**

Lagrangian Geometry:

The Lagrangian function combines both views:

$$L(\boldsymbol{\beta}, \mu) = \frac{1}{2}|\mathbf{y} - \mathbf{X}\boldsymbol{\beta}|_2^2 + \mu(|\boldsymbol{\beta}|_1 - t)$$

At optimality, $\mu = \lambda$ and the gradients balance:

$$\nabla_{\boldsymbol{\beta}} \text{(loss)} + \lambda \cdot \partial|\boldsymbol{\beta}|_1 \ni \mathbf{0}$$

Geometrically: the loss gradient points toward the OLS solution; the penalty subgradient points "outward" from the constraint boundary. At the optimum, these forces balance.

The Penalty as Constraint Enforcement:

Another way to see the equivalence: the penalty $\lambda|\boldsymbol{\beta}|_1$ acts as a "soft" version of the constraint $|\boldsymbol{\beta}|_1 \leq t$. Instead of a hard boundary, violations are penalized proportionally. The regularization parameter $\lambda$ is the "price per unit" of constraint violation.

The geometry of L1 regularization directly informs algorithm design. Understanding shape properties translates to understanding algorithmic behavior.

Why Coordinate Descent Works Well:

The L1 ball has axis-aligned faces and edges. Coordinate descent, which optimizes one coordinate at a time while holding others fixed, naturally navigates this geometry:

• Moving along a coordinate axis stays on the current face (if already on a face)
• Corner solutions are fixed points of coordinate updates
• The algorithm "walks" along edges and settles at corners

Soft Thresholding as Projection:

The soft thresholding operator $S_\lambda(z) = \text{sign}(z)\max(|z| - \lambda, 0)$ has a geometric interpretation:

It is the proximal operator of the L1 norm—the closest point in the L1-penalized objective sense. Geometrically, it shrinks points toward the coordinate axes, then snaps them to axes when close enough.

Active Set Methods:

The piecewise linear path structure suggests active set methods:

1. Maintain a set of potentially non-zero variables (active set)
2. Solve the reduced problem on active variables
3. Check optimality conditions to add/remove variables
4. Repeat until convergence

This exploits the geometry: most computation happens on low-dimensional faces.

Screening Rules:

Geometry also enables safe screening—provably eliminating variables before running the full algorithm:

If a feature $j$ satisfies $|\mathbf{x}_j^T\mathbf{y}| < \lambda - |\mathbf{x}_j|_2 \cdot \text{(geometric term)}$, then $\hat{\beta}_j = 0$ at optimum.

Geometrically: this identifies features whose gradient directions are "too far" from the contact region to possibly be non-zero.

Practical Impact:

In high-dimensional problems ($p \gg n$), most coefficients are zero. Geometric insights enable algorithms that:

• Focus computation on the few non-zero coefficients
• Provably skip irrelevant features
• Exploit sparsity for memory-efficient representations
• Provide path algorithms instead of single-λ solves

We've developed deep geometric intuition for why L1 regularization produces sparse solutions. Let's consolidate the visual and conceptual insights.

What's Next:

We've established the mathematical formulation, sparsity mechanics, and geometric interpretation. The next page addresses a crucial practical question: How do we actually solve the Lasso problem? We'll explore coordinate descent, the proximal gradient method (ISTA/FISTA), and the LARS algorithm—each exploiting the geometric insights developed here.