1-norm Support Vector Machines

Ji Zhu, Saharon Rosset, Trevor Hastie, Robert TibshiraniNeurIPS 2003 · OpenReview

Introduction

Standard Support Vector Machines (SVMs) are powerful classifiers, but they typically yield "dense" solutions, assigning non-zero weights to every input feature. In modern high-dimensional datasets—such as gene microarrays where thousands of features exist but only a few observations are available—many features are merely noise. The standard 2-norm SVM (which uses a ridge penalty) struggles to zero out these irrelevant features, which can degrade prediction accuracy. Furthermore, finding the optimal regularization strength usually requires a computationally expensive grid search.

This paper introduces the 1-norm Support Vector Machine, replacing the standard squared 2-norm penalty with an $L_1$ (Lasso) penalty to perform automatic feature selection. Crucially, the authors present an efficient algorithm that computes the entire solution path for all possible tuning parameters simultaneously, making it significantly easier to find the optimal model in high-dimensional settings.

The 1-norm SVM and Path Algorithm

The 1-norm SVM minimizes the standard hinge loss subject to an $L_1$ constraint: $$\min_{\beta_0, \beta} \sum_{i=1}^{n} [1 - y_i f(x_i)]_+ \quad \text{s.t.} \quad \|\beta\|_1 \leq s$$

The technical breakthrough of this work is the discovery that the solution path $\hat{\beta}(s)$ is piece-wise linear as a function of the tuning parameter $s$.

Instead of solving the optimization problem repeatedly for fixed values of $s$, the authors developed an algorithm (inspired by LARS for Lasso regression) that:

  1. Starts at $s=0$ (where all coefficients are zero).
  2. Identifies "joints"—specific values of $s$ where the set of active features or the set of points on the margin changes.
  3. Linearly interpolates between these joints to provide the exact solution for any $s$ between 0 and $\infty$.
Solution path, test error, and joint complexity

Experimental Results

The authors evaluated the 1-norm SVM on both simulated data and the classic Leukemia Gene Microarray dataset (Golub et al., 1999).

Robustness to Noise: In simulations, a two-class problem was sequentially augmented with up to 8 standard normal "noise" features. As the number of noise features increased, the error rate of the standard 2-norm SVM rose significantly. In contrast, the 1-norm SVM remained remarkably stable because its $L_1$ penalty successfully ignored the redundant features.

Simulation results showing test error across different penalties

Microarray Performance: On the high-dimensional Leukemia dataset (7,129 gene expression levels, 38 training samples), the 1-norm SVM achieved a test error of 2/34 using only 17 genes. This performance was comparable to, or better than, 2-norm SVMs combined with external feature selection methods (like Recursive Feature Elimination), which required 22 to 31 genes.

Key Insights and Limitations

  • Automatic Feature Selection & Sparsity: The 1-norm SVM acts as a built-in feature selector. Following the "Bet on Sparsity" principle, if the true underlying model is sparse, the 1-norm SVM will outperform the 2-norm. If the true model is dense, both will likely perform poorly in high dimensions due to a lack of data.
  • Computational Efficiency: The algorithm's complexity is roughly proportional to the number of joints in the path, empirically scaling as $O(\min(n, q))$. This makes it significantly faster than performing a dense grid search with standard solvers.
  • Limitations: The 1-norm SVM can select at most $n$ (the number of observations) features. If the number of truly relevant features exceeds $n$, the model may be forced to omit important information. Additionally, while the algorithm is highly efficient in practice, its theoretical worst-case complexity is $O(nq \cdot \min(n, q)^2)$, which could bottleneck extremely large datasets. Finally, extending this specific path algorithm to infinite-dimensional kernel spaces remains a complex challenge.

Summary updated

Abstract

The standard 2-norm SVM is known for its good performance in two- In this paper, we consider the 1-norm SVM. We class classi£cation. argue that the 1-norm SVM may have some advantage over the standard 2-norm SVM, especially when there are redundant noise features. We also propose an ef£cient algorithm that computes the whole solution path of the 1-norm SVM, hence facilitates adaptive selection of the tuning parameter for the 1-norm SVM.
BibTeX
@inproceedings{zhu2003norm,
  author = {Ji Zhu and Saharon Rosset and Trevor Hastie and Robert Tibshirani},
  title = {{1-norm Support Vector Machines}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2003},
  url = {https://openreview.net/forum?id=N8GROTKrFIj},
}
Figure