An Equivalence between the Lasso and Support Vector Machines

Abstract

We investigate the relation of two fundamental tools in machine learning and signal processing, that is the support vector machine (SVM) for classification, and the Lasso technique used in regression. We show that the resulting optimization problems are equivalent, in the following sense. Given any instance of an ${\ell }_2$-loss soft-margin (or hard-margin) SVM, we construct a Lasso instance having the same optimal solutions, and vice versa. As a consequence, many existing optimization algorithms for both SVMs and Lasso can also be applied to the respective other problem instances. Also, the equivalence allows for many known theoretical insights for SVM and Lasso to be translated between the two settings. One such implication gives a simple kernelized version of the Lasso, analogous to the kernels used in the SVM setting. Another consequence is that the sparsity of a Lasso solution is equal to the number of support vectors for the corresponding SVM instance, and that one can use screening rules to prune the set of support vectors. Furthermore, we can relate sublinear time algorithms for the two problems, and give a new such algorithm variant for the Lasso. We also study the regularization paths for both methods.

Book chapter in Regularization, Optimization, Kernels, and Support Vector Machines, Johan A.K. Suykens, Marco Signoretto, Andreas Argyriou (Editors), 2014

References in corpus (5)

• Lasso Screening Rules via Dual Polytope Projection
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Complexity Analysis of the Lasso Regularization Path
• Efficient Learning with Partially Observed Attributes
• Linear Regression with Limited Observation

Cited by in corpus (6)

• Quantum Differentially Private Sparse Regression Learning
• Safe Sample Screening for Support Vector Machines
• A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing
• Equivalence of Learning Algorithms
• The Parameter Houlihan: a solution to high-throughput identifiability indeterminacy for brutally ill-posed problems
• Fast and Scalable Lasso via Stochastic Frank-Wolfe Methods with a Convergence Guarantee