An efficient augmented Lagrangian method for support vector machine

References

• D. Basak, S. Pal, and D. Patranabis, Support vector regression, Neural Inform. Process. Lett. Rev. 11(10) (2007), pp. 203–224.
   Google Scholar
• B.E. Boser, I.M. Guyon, and V.N. Vapnik, A training algorithm for optimal margin classifiers, COLT'92: Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, Pittsburgh, PA, 27–29 July 1992, pp. 144–152.
   Google Scholar
• O. Chapelle, Training a support vector machine in the primal, Neural Comput. 19(5) (2007), pp. 1155–1178. doi: 10.1162/neco.2007.19.5.1155
   PubMed Web of Science ®Google Scholar
• V.K. Chauhan, K. Dahiya, and A. Sharma, Problem formulations and solvers in linear SVM: A review, Artif. Intell. Rev. 52(2) (2019), pp. 803–855. doi:10.1007/s10462-018-9614-6.
   Web of Science ®Google Scholar
• F.H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons, New York, 1933.
   Google Scholar
• M. Collins, A. Globerson, T. Koo, X. Carreras, and P. Bartlett, Exponentiated gradient algorithms for conditional random elds and max-margin Markov networks, J. Mach. Learn. Res. 9 (2008), pp. 1775–1822.
   Web of Science ®Google Scholar
• C. Cortes and V.N. Vapnik, Support-vector networks, Mach. Learn. 20(3) (1995), pp. 273–297.
   Web of Science ®Google Scholar
• H. Drucker, C.J.C. Burges, L. Kaufman, A.J. Smola, and V.N. Vapnik, Support vector regression machines, Adv. Neural. Inf. Process. Syst. 28 (1997), pp. 779–784.
   Google Scholar
• R. Fan, K. Chang, C. Hsieh, X. Wang and C. Lin, LIBLINEAR: A library for large linear classification, JMLR 9 (2008), pp. 1871–1874.
   Web of Science ®Google Scholar
• W. Gu, W.P. Chen, and C.H. Ko, Two smooth support vector machines for ε-insensitive regression, Comput. Optim. Appl. 70 (2018), pp. 1–29. doi: 10.1007/s10589-017-9975-9
   Web of Science ®Google Scholar
• M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand. 49 (1952), pp. 409–436. doi: 10.6028/jres.049.044
   Google Scholar
• C.H. Ho and C.-J. Lin, Large-scale linear support vector regression, J. Mach. Learn. Res. 13(Nov) (2012), pp. 3323–3348.
   Google Scholar
• C.J. Hsieh, K.W. Chang, C.-J. Lin, S.S. Keerthi, and S. Sundararajan, A dual coordinate descent method for large-scale linear SVM, Proceedings of the 25th International Conference on Machine Learning, Helsinki, pp. 408–415.
   Google Scholar
• N. Ito, A. Takeda and K.-C. Toh, A unified formulation and fast accelerated proximal gradient method for classification, JMLR 18(1) (2017), pp. 510–558.
   Google Scholar
• T. Joachims, Making large-scale support vector machine learning practical, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, and A. Smola, eds., MIT Press, Cambridge, MA, 1999, pp. 169–184.
   Google Scholar
• T. Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Philadelphia, 2006, pp. 217–226.
   Google Scholar
• C. Kanzow, Inexact semismooth Newton methods for large-scale complementarity problems, Optim. Methods Softw. 19(3–4) (2004), pp. 309–325. doi: 10.1080/10556780310001636369
   Web of Science ®Google Scholar
• J. Kivinen, A.J. Smola, and R.C. Williamson, Online learning with kernels, IEEE Trans. Signal Process. 52(8) (2002), pp. 2165–2176. doi: 10.1109/TSP.2004.830991
   Web of Science ®Google Scholar
• Q.N. Li and H.-D. Qi, A sequential semismooth Newton method for the nearest low-rank correlation matrix problem, SIAM J. Optim. 21(4) (2011), pp. 1641–1666. doi: 10.1137/090771181
   Web of Science ®Google Scholar
• X.D. Li, D.F. Sun, and K.-C. Toh, A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems, SIAM J. Optim. 28(1) (2018), pp. 433–458. doi: 10.1137/16M1097572
   Web of Science ®Google Scholar
• Y.-J. Liu, D.F. Sun, and K.-C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Math. Program. 133(12) (2012), pp. 399–436. doi:10.1007/s10107-010-0437-8.
   Google Scholar
• Z.Y. Luo, D.F. Sun, and K.-C. Toh, Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method, preprint (2018). Available at arXiv, math. OC/1803.10740.
   Google Scholar
• R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim. 15(6) (1977), pp. 959–972. doi: 10.1137/0315061
   Web of Science ®Google Scholar
• J.J. Moreau, Proximite dt dualite dans un espace hilbertien, Bulletin de la Societe Mathematique de France 93 (1965), pp. 273–299. doi: 10.24033/bsmf.1625
   Google Scholar
• F. Nie, Y. Huang, X. Wang, and H. Huang, New primal SVM solver with linear computational cost for big data classifications, Proceedings of the 31st International Conference on Machine Learning, Beijing, Vol. 32, 2014, pp. II-505–II-513.
   Google Scholar
• D. Niu, C. Wang, P. Tang, Q. Wang, and E. Song, A sparse semismooth Newton based augmented Lagrangian method for large-scale support vector machines, 2019. Available at arXiv, math. OC/1910.01312.
   Google Scholar
• J.C. Platt, Fast training of support vector machines using sequential minimal optimization, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, and A. Smola, eds., MIT Press, Cambridge, MA, 1998, pp. 185–208.
   Google Scholar
• H.-D. Qi, A semismooth Newton method for the nearest Euclidean distance matrix problem, SIAM J. Matrix Anal. Appl. 34(1) (2013), pp. 67–93. doi: 10.1137/110849523
   Web of Science ®Google Scholar
• L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program. 58(1–3) (1993), pp. 353–367. doi: 10.1007/BF01581275
   Web of Science ®Google Scholar
• H.-D. Qi and D.F. Sun, A quadratically convergent Newton method for computing the nearest correlation matrix, SIAM J. Matrix Anal. Appl. 28(2) (2006), pp. 360–385. doi: 10.1137/050624509
   Web of Science ®Google Scholar
• H.-D. Qi and X.M. Yuan, Computing the nearest Euclidean distance matrix with low embedding dimensions, Math. Program. 147(1–2) (2014), pp. 351–389. doi: 10.1007/s10107-013-0726-0
   Web of Science ®Google Scholar
• R.T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1(2) (1976), pp. 97–116. doi: 10.1287/moor.1.2.97
   Google Scholar
• R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976), pp. 877–898. doi: 10.1137/0314056
   Web of Science ®Google Scholar
• S. Shalev-Shwartz, Y. Singer, and N. Srebro, Pegasos: Primal estimated sub-gradient solver for SVM, International Conference on Machine Learning, Oregon State University, Corvallis, 2007.
   Google Scholar
• A.J. Smola, Regression estimation with support vector learning machines, Master thesis, Technische Universität München, 1996.
   Google Scholar
• A.J. Smola, S.V.N. Vishwanathan, and Q. Le, Bundle methods for machine learning, in Advances in Neural Information Processing Systems 20, J.C. Platt, D. Koller, Y. Singer, and S. Roweis, eds., MIT Press, Cambridge, MA, 2008, pp. 1377–1384.
   Google Scholar
• J. Sun, On monotropic piecewise quadratic programming, PhD thesis, Department of Mathematics, University of Washington, 1986.
   Google Scholar
• D.F. Sun and J. Sun, Semismooth matrix-valued functions, Math. Oper. Res. 27 (2002), pp. 150–169. doi: 10.1287/moor.27.1.150.342
   Web of Science ®Google Scholar
• D.F. Sun, K.-C. Toh, and L.Q. Yang, An efficient inexact ABCD method for least squares semidefinite programming, SIAM J. Optim. 26(2) (2016), pp. 1072–1100. doi: 10.1137/15M1021799
   Web of Science ®Google Scholar
• D.F. Sun, K.-C. Toh, and Y.C. Yuan, Convex clustering: Model, theoretical guarantee and efficient algorithm, preprint (2018). Available at arXiv, cs. LG/1810.02677.
   Google Scholar
• D.F. Sun, K.-C. Toh, Y.C. Yuan, and X.Y. Zhao, SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0), Optim. Methods Softw. (2019), pp. 1–29. Available at arXiv, math. OC/1710.10604.
   Google Scholar
• M. Takáč, A. Bijral, P. Richtárik, and N. Srebro, Mini-batch primal and dual methods for SVMs, Proceedings of the 30th International Conference on Machine Learning, Atlanta, 2013.
   Google Scholar
• L.Q. Yang, D.F. Sun, and K.-C. Toh, SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput. 7(3) (2015), pp. 331–366. doi: 10.1007/s12532-015-0082-6
   Web of Science ®Google Scholar
• J. Yin and Q.N. Li, A semismooth Newton method for support vector classification and regression, Comput. Optim. Appl. 73(2) (2019), pp. 477–508. doi:10.1007/s10589-019-00075-z.
   Web of Science ®Google Scholar
• K. Yosida, Functional Analysis, Springer Verlag, Berlin, 1964.
   Google Scholar
• F.Z. Zhai and Q.N. Li, A Euclidean distance matrix model for protein molecular conformation, J. Global Optim. (2019). doi:10.1007/s10898-019-00771-4
   Web of Science ®Google Scholar
• T. Zhang, Solving large scale linear prediction problems using stochastic gradient descent algorithms, Proceedings of the 21th International Conference on Machine Learning, Banff, Alberta, 2004.
   Google Scholar
• X.Y. Zhao, A semismooth Newton-CG augmented Lagrangian method for large scale linear and convex quadratic SDPS, Ph.D. diss., National University of Singapore, 2009.
   Google Scholar
• X.Y. Zhao, D.F. Sun, and K.-C. Toh, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim. 20 (2010), pp. 1737–1765. doi: 10.1137/080718206
   Web of Science ®Google Scholar
• P. Zhong and M. Fukushima, Regularized nonsmooth Newton method for multi-class support vector machines, Optim. Methods Softw. 22(1) (2007), pp. 225–236. doi: 10.1080/10556780600834745
   Web of Science ®Google Scholar