Abstract
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 non-differentiable and makes the problem difficult to solve in particular for regularized SVMs, such as with \(\ell _1\)-regularization. This paper considers the Huberized SVM (HSVM), which uses a differentiable approximation of the hinge loss function. We first explore the use of the proximal gradient (PG) method to solving binary-class HSVM (B-HSVM) and then generalize it to multi-class HSVM (M-HSVM). Under strong convexity assumptions, we show that our algorithm converges linearly. In addition, we give a finite convergence result about the support of the solution, based on which we further accelerate the algorithm by a two-stage method. We present extensive numerical experiments on both synthetic and real datasets which demonstrate the superiority of our methods over some state-of-the-art methods for both binary- and multi-class SVMs.
Similar content being viewed by others
Notes
Without strong convexity of \(\xi _2\), we only have sublinear convergence as shown in [1].
Our algorithm and ADMM are both implemented in MATLAB, while the code of GCD is written in R. To be fair, we re-wrote the code of GCD and implemented it in MATLAB.
The Wilcoxon signed-ranks test is in general better than the paired \(t\)-test as demonstrated in [9].
The code of DDAG is available from http://theoval.cmp.uea.ac.uk/svm/toolbox/.
Our reported accuracies are lower than those in [20] because we used fewer training samples.
References
Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci 2(1):183–202
Bolte J, Daniilidis A, Lewis A (2007) The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J Optim 17(4):1205–1223
Bottou L, Cortes C, Denker JS, Drucker H, Guyon I, Jackel LD, LeCun Y, Muller UA, Sackinger E, Simard P et al (1994) Comparison of classifier methods: a case study in handwritten digit recognition. In: Proceedings of the 12th IAPR International Conference on Pattern Recognition, vol 2, pp 77–82. IEEE
Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge
Brown MPS, Grundy WN, Lin D, Cristianini N, Sugnet CW, Furey TS, Ares M, Haussler D (2000) Knowledge-based analysis of microarray gene expression data by using support vector machines. Proc Nat Acad Sci 97(1):262
Chen Zhen-Yu, Fan Zhi-Ping, Sun Minghe (2012) A hierarchical multiple kernel support vector machine for customer churn prediction using longitudinal behavioral data. Eur J Oper Res 223(2):461–472
Cortes C, Vapnik V (1995) Support-vector networks. Mach Learn 20(3):273–297
Czarnecki WM, Tabor J (2014) Two ellipsoid support vector machines. Exp Syst Appl 41:8211–8224
Demšar Janez (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30
Dudoit S, Fridlyand J, Speed TP (2002) Comparison of discrimination methods for the classification of tumors using gene expression data. J Am Stat Assoc 97(457):77–87
Fan Rong-En, Chang Kai-Wei, Hsieh Cho-Jui, Wang Xiang-Rui, Lin Chih-Jen (2008) Liblinear: a library for large linear classification. J Mach Learn Res 9:1871–1874
Friedman Milton (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J Am Stat Assoc 32(200):675–701
Friedman Milton (1940) A comparison of alternative tests of significance for the problem of m rankings. Ann Math Stat 11(1):86–92
Galar M, Fernandez A, Barrenechea E, Herrera F (2015) Drcw-ovo: Distance-based relative competence weighting combination for one-vs-one strategy in multiclass problems. Pattern Recognit 48:28–42
Galar Mikel, Fernández Alberto, Barrenechea Edurne, Bustince Humberto, Herrera Francisco (2011) An overview of ensemble methods for binary classifiers in multi-class problems: Experimental study on one-vs-one and one-vs-all schemes. Pattern Recognit 44(8):1761–1776
Golub TR, Slonim DK, Tamayo P, Huard C, Gaasenbeek M, Mesirov JP, Coller H, Loh ML, Downing JR, Caligiuri MA et al (1999) Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science 286(5439):531–537
Hale ET, Yin W, Zhang Y (2008) Fixed-point continuation for \(l_1\)-minimization: methodology and convergence. SIAM J Optim 19(3):1107–1130
Heisele B, Ho P, Poggio T (2001) Face recognition with support vector machines: Global versus component-based approach. In: Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, vol 2, pp 688–694. IEEE
Holm S (1979) A simple sequentially rejective multiple test procedure. Scand J Stat 65–70
Hsu CW, Lin CJ (2002) A comparison of methods for multiclass support vector machines. Neural Netw IEEE Trans 13(2):415–425
CVX Research, Inc. CVX: Matlab software for disciplined convex programming, version 2.0 beta (2012). http://cvxr.com/cvx, Sept 2012
Keerthi SS, DeCoste D (2006) A modified finite newton method for fast solution of large scale linear svms. J Mach Learn Res 6(1):341
Khan J, Wei JS, Ringnér M, Saal LH, Ladanyi M, Westermann F, Berthold F, Schwab M, Antonescu CR, Peterson C et al (2001) Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks. Nat Med 7(6):673–679
Kim KI, Jung K, Park SH, Kim HJ (2002) Support vector machines for texture classification. Pattern Anal Mach Intell IEEE Trans 24(11):1542–1550
Knerr S, Personnaz L, Dreyfus G (1990) Single-layer learning revisited: a stepwise procedure for building and training a neural network. In: Neurocomputing, pp 41–50. Springer
Krawcczyk B, Wozniak M, Cyganek B (2014) Clustering-based ensembles for one-class classification. Inf Sci 264:182–195
Kurdyka K (1998) On gradients of functions definable in o-minimal structures. In: Annales de l’institut Fourier, vol 48, pp 769–784. Chartres: L’Institut, 1950
Lacoste-Julien S, Jaggi M, Schmidt M, Pletscher P (2012) Block-coordinate frank-wolfe optimization for structural svms. arXiv preprint arXiv:1207.4747
Lee Y, Lin Y, Wahba G (2004) Multicategory support vector machines. J Am Stat Assoc 99(465):67–81
Li J, Jia Y (2010) Huberized multiclass support vector machine for microarray classification. Acta Autom Sin 36(3):399–405
Li Qi, Salman Raied, Test Erik, Strack Robert, Kecman Vojislav (2013) Parallel multitask cross validation for support vector machine using gpu. J Parallel Distrib Comput 73(3):293–302
Łojasiewicz S (1993) Sur la géométrie semi-et sous-analytique. Ann Inst Fourier (Grenoble) 43(5):1575–1595
Nesterov Y (2004) Introductory lectures on convex optimization vol 87. A basic course
Nesterov Y (2007) Gradient methods for minimizing composite objective function. CORE Discussion Papers
Ouyang H, He N, Tran L, Gray A (2013) Stochastic alternating direction method of multipliers. In: Proceedings of the 30th International Conference on Machine Learning, pp 80–88
Platt JC, Cristianini N, Shawe-Taylor J (2000) Large margin dags for multiclass classification. Adv Neural Inf Process Syst 12(3):547–553
Qi Zhiquan, Tian Yingjie, Shi Yong (2013) Structural twin support vector machine for classification. Knowl-Based Syst 43:74–81
Schmidt M, Roux NL, Bach F (2011) Convergence rates of inexact proximal-gradient methods for convex optimization. Arxiv preprint arXiv:1109.2415
Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Methods Softw 11(1–4):625–653
Tibshirani R (1996) Regression shrinkage and selection via the lasso. J R Stat Soc Ser B 58(1):267–288
Tsyurmasto P, Zabarankin M, Uryasev S (2014) Value-at-risk support vector machine: stability to outliers. J Comb Optim 1–15
Wang L, Shen X (2007) On \({L}_1\)-norm multiclass support vector machines. J Am Stat Assoc 102(478):583–594
Wang L, Zhu J, Zou H (2006) The doubly regularized support vector machine. Stat Sin 16(2):589
Wang L, Zhu J, Zou H (2008) Hybrid huberized support vector machines for microarray classification and gene selection. Bioinformatics 24(3):412–419
Wilcoxon F (1945) Individual comparisons by ranking methods. Biom Bull pp 80–83
Xu Y, Yin W (2013) A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J Imaging Sci 6(3):1758–1789
Xu Y, Yin W (2014) A globally convergent algorithm for nonconvex optimization based on block coordinate update. Arxiv preprint arXiv:1410.1386
Yang Yi, Zou Hui (2013) An efficient algorithm for computing the hhsvm and its generalizations. J Comput Graph Stat 22(2):396–415
Ye GB, Chen Y, Xie X (2011) Efficient variable selection in support vector machines via the alternating direction method of multipliers. In: Proceedings of the International conference on artificial intelligence and statistics
Zhang H, Liu Y, Wu Y, Zhu J (2008) Variable selection for the multicategory svm via adaptive sup-norm regularization. Electron J Stat 2:149–167
Zhang Yang, Meratnia Nirvana, Havinga Paul JM (2013) Distributed online outlier detection in wireless sensor networks using ellipsoidal support vector machine. Ad Hoc Netw 11(3):1062–1074
Zou J, Hastie T (2005) Regularization and variable selection via the elastic net. J R Stat Soc Ser B 67(1):301–320
Acknowledgments
The authors would like to thank three anonymous referees and the associate editor for their valuable comments and suggestions that improved the quality of this paper. The first author would also like to thank Professor Wotao Yin for his valuable discussion.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A: Proof of Proposition 1
First, we derive the convexity of each \(f_i\) from the composition of the convex function \(\phi _H\) and the linear transformation \(y_i(b+{\mathbf{x}}_i^\top {\mathbf{w}})\) (e.g., see [4]). Thus, \(f\) is also convex since it is the sum of \(n\) convex functions. Second, it is easy to verify that
and it is Lipschitz continuous, namely \(|\phi '_H(t)-\phi '_H(s)|\le \frac{1}{\delta }|t-s|,\) for any \(t,s\).
Using the notations in (7) and by the chain rule, we have \(\nabla f_i({\mathbf{u}})=\phi '_H({\mathbf{v}}_i^\top {\mathbf{u}}){\mathbf{v}}_i\), for \(i=1,\ldots ,n\) and
Hence, for any \({\mathbf{u}},\hat{\mathbf{u}}\), we have
which completes the proof.
Appendix B: Proof of Theorem 1
We begin our analysis with the following lemma, which can be shown through essentially the same proof of Lemma 2.3 in [1].
Lemma 2
Let \(\{\mathbf{u}^k\}\) be the sequence generated by (5) with \(L_k\le L\) such that for all \(k\ge 1\),
Then for all \(k\ge 1\), it holds for any \({\mathbf{u}}\in \mathcal {U}\) that
We also need the following lemma, which is the KL property for strongly convex functions:
Lemma 3
Suppose \(\xi\) is strongly convex with constant \(\mu >0\). Then for any \({\mathbf{u}},{\mathbf{v}}\in \mathrm {dom}(\partial \xi )\) and \({\mathbf{g}}_{\mathbf{u}}\in \partial \xi ({\mathbf{u}})\), we have
Proof
For any \({\mathbf{g}}_{\mathbf{u}}\in \partial \xi ({\mathbf{u}})\), we have from the strong convexity of \(\xi\) and the Cauchy-Schwarz inequality that
which completes the proof. \(\square\)
Global convergence
We first show \({\mathbf{u}}^k\rightarrow {\mathbf{u}}^*\). Letting \({\mathbf{u}}={\mathbf{u}}^{k-1}\) in (25) gives
Summing up the inequality (27) over \(k\), we have
which implies \({\mathbf{u}}^k-{\mathbf{u}}^{k-1}\rightarrow {\mathbf {0}}\) since \(\xi ({\mathbf{u}}^k)\) is lower bounded.
Note that \(\{{\mathbf{u}}^k\}\) is bounded since \(\xi\) is coercive and \(\{\xi ({\mathbf{u}}^k)\}\) is upper bounded by \(\xi ({\mathbf{u}}^0)\). Hence, \(\{{\mathbf{u}}^k\}\) has a limit point \(\bar{\mathbf{u}}\), so there is a subsequence \(\{{\mathbf{u}}^{k_j}\}\) converging to \(\bar{\mathbf{u}}\). Note \({\mathbf{u}}^{k_j+1}\) also converges to \(\bar{\mathbf{u}}\) since \({\mathbf{u}}^k-{\mathbf{u}}^{k-1}\rightarrow {\mathbf {0}}\). Without loss of generality, we assume \(L_{k_j+1}\rightarrow \bar{L}\). Otherwise, we can take a convergent subsequence of \(\{L_{k_j+1}\}\). By (5), we have
Letting \(j\rightarrow \infty\) in the above formula and observing \(\hat{\mathbf{u}}^{k_j}\rightarrow \bar{\mathbf{u}}\) yield
which indicates \(-\nabla \xi _1(\bar{\mathbf{u}})\in \partial \xi _2(\bar{\mathbf{u}})\). Thus \(\bar{\mathbf{u}}\) is the minimizer of \(\xi\).
Since \(\{\xi ({\mathbf{u}}^k)\}\) is nonincreasing and lower bounded, it converges to \(\xi (\bar{\mathbf{u}})=\xi (\mathbf{u}^*)\). Noting \(\frac{\mu }{2}\Vert {\mathbf{u}}^k-{\mathbf{u}}^*\Vert ^2\le \xi ({\mathbf{u}}^k)-\xi ({\mathbf{u}}^*),\) we have \({\mathbf{u}}^k\rightarrow {\mathbf{u}}^*.\)
Convergence rate
Next we go to show (19). Without loss of generality, we assume \(\xi ({\mathbf{u}}^*)=0\). Otherwise, we can consider \(\xi -\xi ({\mathbf{u}}^*)\) instead of \(\xi\). In addition, we assume \(\xi ({\mathbf{u}}^k)>\xi ({\mathbf{u}}^*)\) for all \(k\ge 0\) because if \(\xi ({\mathbf{u}}^{k_0})=\xi ({\mathbf{u}}^*)\) for some \(k_0\), then \({\mathbf{u}}^k={\mathbf{u}}^{k_0}={\mathbf{u}}^*\) for all \(k\ge k_0\).
For ease of description, we denote \(\xi _k=\xi ({\mathbf{u}}^k)\). Letting \({\mathbf{v}}={\mathbf{u}}^*\) in (26), we have
Noting \(-\nabla \xi _1(\hat{\mathbf{u}}^{k-1})-L_k({\mathbf{u}}^k-\hat{\mathbf{u}}^{k-1})+\nabla \xi _1({\mathbf{u}}^k)\in \partial \xi ({\mathbf{u}}^k)\) and \(L_k\le L\), we have for all \(k\ge K\),
Noting \(\sqrt{\xi _k}-\sqrt{\xi _{k+1}}\ge \frac{\xi _k-\xi _{k+1}}{2\sqrt{\xi _k}}\) and using (27) yield
after rearrangements. Take \(0<\delta <\frac{1}{2}(\sqrt{L+\mu }-\sqrt{L})\). Using the inequalities \(a^2+b^2\le (a+b)^2\) and \(\sqrt{ab}\le ta+\frac{1}{4t}b\) for \(a,b,t>0\), we have from the above inequality that
Summing up the above inequality over \(k\) and noting \(\Vert {\mathbf{u}}^k-{\mathbf{u}}^{k+1}\Vert \rightarrow 0, \xi _k\rightarrow 0\) yield
which together with \(\sqrt{L+\mu }-\sqrt{L}\le \sqrt{L_k+\mu }-\sqrt{L_k}\) for all \(k\ge 0\) implies
where
Denote \(S_m=\sum _{k=m}^\infty \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k+1}\Vert\) and write (30) as
which together with (29) gives
Let \(\tau =\sqrt{\frac{C_3}{1+C_3}}\) and \(C=S_0\). Then we have \(S_m\le C\tau ^m, \forall m\ge 0.\) Note \(\Vert {\mathbf{u}}^m-{\mathbf{u}}^*\Vert \le S_m\), and thus we complete the proof.
Rights and permissions
About this article
Cite this article
Xu, Y., Akrotirianakis, I. & Chakraborty, A. Proximal gradient method for huberized support vector machine. Pattern Anal Applic 19, 989–1005 (2016). https://doi.org/10.1007/s10044-015-0485-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10044-015-0485-z