Sparsity and Smoothness Via the Fused Lasso

Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, Keith KnightJournal of the Royal Statistical Society Series B: Statistical Methodology 2004 · DOI

TL;DR

The Fused Lasso is a powerful regularization technique that simultaneously encourages sparsity in regression coefficients and their successive differences. By penalizing the $L_1$-norm of both the coefficients and their "jumps," it produces models that are both sparse and piecewise constant, making it ideal for high-dimensional data with a natural feature ordering.

What Problem Does This Paper Address?

In many modern statistical problems, we have far more features ($p$) than observations ($N$). The standard Lasso (Least Absolute Shrinkage and Selection Operator) is a go-to tool here because it enforces sparsity—it sets many coefficients to exactly zero, effectively performing feature selection.

However, the Lasso treats features as exchangeable; it doesn't care about their order. In fields like proteomics (mass spectrometry) or genomics, features often have a meaningful sequence (e.g., time-of-flight or chromosomal position). If a specific protein peak is a good predictor, its immediate neighbors likely are too. Standard Lasso might pick one noisy feature and drop its neighbors, leading to "wiggly," unstable coefficient profiles that are hard to interpret. The authors tackle this by introducing a "fusion" penalty to ensure that neighboring features have similar coefficients.

Methods

The authors propose the Fused Lasso, which modifies the standard least-squares optimization by adding two $L_1$ constraints:

  1. Sparsity Constraint: $\sum_{j=1}^p |\beta_j| \le s_1$ (The standard Lasso penalty).
  2. Fusion Constraint: $\sum_{j=2}^p |\beta_j - \beta_{j-1}| \le s_2$ (The new penalty on differences).

The combination of these two $L_1$ penalties is the "secret sauce." The first encourages many coefficients to be zero, while the second encourages adjacent coefficients to be identical (i.e., "fused"). This results in a piecewise constant coefficient profile.

Schematic of the Fused Lasso geometry. The intersection of the two $L_1$ constraints (the shaded regions) creates a unique search space that favors both zero coefficients and equal adjacent coefficients.

Computationally, this is a convex optimization problem. For small to medium datasets, it can be solved via quadratic programming. For larger problems, the authors utilize the SQOPT solver, which is optimized for sparse linear constraints. They also extend the method to classification by applying the fused penalty to the hinge loss function used in Support Vector Machines (SVMs).

Datasets

The paper evaluates the method using:

  • Simulated Data: Controlled environments with $p=100$ and $N=20$ to demonstrate how well the method recovers "blocks" of active features.
  • Prostate Cancer Protein Mass Spectrometry: A massive dataset with 48,538 $m/z$ sites (features) and 324 patients. The goal is to identify protein signatures that distinguish healthy patients from those with cancer.
  • Leukemia Microarray Data: 7,129 gene expression levels across 72 samples. Since genes don't have a natural 1D order, the authors use hierarchical clustering to estimate a meaningful sequence before applying the Fused Lasso.

Key Insights and Ideas

  • Local Constancy: The primary innovation is the "fusion" of coefficients. This reflects the prior belief that in many physical systems, underlying signals are "blocky" or smooth rather than isolated spikes.
  • Sparsity of Differences: By using an $L_1$ penalty on the differences ($\beta_j - \beta_{j-1}$), the model doesn't just make the profile smooth (like a squared $L_2$ penalty would); it makes it flat over long stretches, with occasional sharp jumps.
  • Handling Unordered Features: While designed for ordered data, the authors show that you can apply this to unordered data (like gene expression) by first using clustering to find a "pseudo-order." This allows the model to group correlated features together into active blocks.

Key Results

The Fused Lasso consistently outperformed or matched the standard Lasso in terms of interpretability and predictive accuracy, especially when the true underlying signal was block-like.

Comparison of methods on simulated data. (a) Univariate regression is noisy. (b) Lasso is sparse but misses the block structure. (c) Fusion alone is blocky but not sparse. (d) Fused Lasso recovers the true underlying blocks (black lines) most accurately.
  • Mass Spectrometry: On the prostate cancer data, the Fused Lasso achieved a validation error of 16/108, identical to the Lasso, but it identified 218 active sites in meaningful clusters rather than 40 isolated, potentially noisy sites.
  • Microarrays: In the Leukemia study, the Fused Lasso SVM was highly competitive, achieving only one misclassification error in both cross-validation and the test set.

Limitations and Future Work

  • Computational Complexity: The main drawback is speed. While the standard Lasso has very efficient algorithms like LARS (Least Angle Regression), the Fused Lasso requires more intensive quadratic programming. The authors note that for $p > 2000$, computation time becomes a significant hurdle.
  • Higher Dimensions: The paper focuses on 1D ordering. The authors suggest extending this to 2D grids (e.g., for image pixels), but acknowledge this would explode the number of constraints to $O(p^2)$, presenting a major computational challenge.
  • Algorithm Development: A major area for future work is developing a LARS-like path algorithm specifically for the Fused Lasso to allow for faster computation across the entire regularization path.

Summary updated

Abstract

Summary The lasso penalizes a least squares regression by the sum of the absolute values (L1-norm) of the coefficients. The form of this penalty encourages sparse solutions (with many coefficients equal to 0). We propose the ‘fused lasso’, a generalization that is designed for problems with features that can be ordered in some meaningful way. The fused lasso penalizes the L1-norm of both the coefficients and their successive differences. Thus it encourages sparsity of the coefficients and also sparsity of their differences—i.e. local constancy of the coefficient profile. The fused lasso is especially useful when the number of features p is much greater than N, the sample size. The technique is also extended to the ‘hinge’ loss function that underlies the support vector classifier. We illustrate the methods on examples from protein mass spectroscopy and gene expression data.
BibTeX
@article{tibshirani2004sparsity,
  author = {Robert Tibshirani and Michael Saunders and Saharon Rosset and Ji Zhu and Keith Knight},
  title = {{Sparsity and Smoothness Via the Fused Lasso}},
  journal = {Journal of the Royal Statistical Society Series B: Statistical Methodology},
  year = {2004},
  doi = {10.1111/j.1467-9868.2005.00490.x},
}
Figure