An Efficient Algorithm for Computing the HHSVM and Its Generalizations

Abstract

The hybrid Huberized support vector machine (HHSVM) has proved its advantages over the ℓ₁ support vector machine (SVM) in terms of classification and variable selection. Similar to the ℓ₁ SVM, the HHSVM enjoys a piecewise linear path property and can be computed by a least-angle regression (LARS)-type piecewise linear solution path algorithm. In this article, we propose a generalized coordinate descent (GCD) algorithm for computing the solution path of the HHSVM. The GCD algorithm takes advantage of a majorization–minimization trick to make each coordinatewise update simple and efficient. Extensive numerical experiments show that the GCD algorithm is much faster than the LARS-type path algorithm. We further extend the GCD algorithm to solve a class of elastic net penalized large margin classifiers, demonstrating the generality of the GCD algorithm. We have implemented the GCD algorithm in a publicly available R package gcdnet.

Key Words:

• Coordinate descent
• Elastic net
• Hubernet
• Large margin classifiers
• Majorization–minimization
• SVM

ACKNOWLEDGMENTS

The authors thank the editor, an associate editor, and two referees for their helpful comments and suggestions. This work is supported in part by NSF grant DMS-08-46068.