Efficient variable selection in support vector machines via the alternating direction method of multipliers

This work develops an efficient algorithm based on the alternating direction method of multipliers (ADMM) to solve the optimization problem in DrSVM, a doubly regularized support vector machine.

Abstract

The support vector machine (SVM) is a widely used tool for classification. Although commonly understood as a method of finding the maximum-margin hyperplane, it can also be formulated as a regularized function estimation problem, corresponding to a hinge loss function plus an ℓ2-norm regulation term. The doubly regularized support vector machine (DrSVM) is a variant of the standard SVM, which introduces an additional ℓ 1-norm regularization term on the fitted coefficients. The combined ℓ 1 and ℓ 2 regularization, termed elastic net penalty, has the property of achieving simultaneous variable selection and margin-maximization within a single framework. However, because of the nondifferentiability of both the loss function and the regularization term, there is no efficient method available to solve DrSVM for large-scale problems. Here we develop an efficient algorithm based on the alternating direction method of multipliers (ADMM) to solve the optimization problem in DrSVM. The utility of the method is illustrated using both simulated and real-world data. Copyright 2011 by the authors.