Proximal Gradient Method for Huberized Support Vector Machine

摘要

The Support Vector Machine (SVM) has been used in a wide variety of classification problems. The original SVM uses the hinge loss function, which is nondifferentiable and makes the problem difficult to solve in particular for regularized SVMs, such as with l₁-norm. The Huberized SVM (HSVM) is considered, which uses a differentiable approximation of the hinge loss function. The Proximal Gradient (PG) method is used to solving binary-class HSVM (BHSVM) and then generalized to multi-class HSVM (MHSVM). Under strong convexity assumptions, the algorithm converges linearly. A finite convergence result about the support of the solution is given, based on which the algorithm is further accelerated by a two-stage method.