An Equivalence between the Lasso and Support Vector Machines

By Martin Jaggi. 2013

57 citations recorded by the source corpus.

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.

Subfields: Rheumatology, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Rheumatology

In Statistics and Probability

Citations in the corpus

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “It turns out that prox h,α ( z ) for Lasso is equal to the soft-thresholding operator S λα ( z ) [Tib15], which, for j ∈ [ d ] , is deﬁned as • SVM dual: Jaggi [Jag13] showed an equivalence between the dual formulation of Support Vector Machine (SVM) and Lasso.”
Empirical Asset Pricing via Machine Learning (2018, background): “4See, for example, Jaggi (2013) and Hastie et al. (2009), who discuss the equivalence of support vector machines with the lasso.”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, methodology): “ons [31]; see, e.g., the overview in [30]. While the prototype methods of these problem formulations|SVM for the L 2-regularized case and Lasso for the L 1-regularized case|are indeed closely related [11], rigorous derivations of primal-dual methods with convergence rates for the accuracy certicates”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, background): “The dual formulation of SVM with squared hinge loss can be solved as a quadratic minimization over the simplex (Jaggi (2013); Li et al.”
A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing (2014, methodology): “If λ 2 → 0 the Elastic Net becomes LASSO [12], which has previously been shown to be equivalent to the hard-margin SVM [15].”