FAST SOLVER FOR INTERIOR POINT METHOD OF SVM TRAINING BY PARALLEL GMRES AND HSS
DOI:
https://doi.org/10.47839/ijc.13.2.626Keywords:
Interior Point Method, fast solver, parallel GMRES, Hermitian/Skew-Hermitian Separation, Support Vector Machine, Quadratic Programming.Abstract
Support Vector Machine (SVM) is one of the latest statistical models for machine learning. The key problem of SVM training is an optimization problem (mainly Quadratic Programming). Interior Point Method (IPM) is one of mainstream methods to solve Quadratic Programming problem. However, when large-scale dataset is used in IPM based SVM training, computational difficulty happens because of computationally expensive matrix operations. Preconditioner, such as Cholesky factorization (CF), incomplete Cholesky factorization and Kronecker factorization, is an effective approach to decrease time complexity of IPM based SVM training. In this paper, we reformulate SVM training into the saddle point problem. As the research question that motivates this paper, based on parallel GMRES and recently developed preconditioner Hermitian/Skew-Hermitian Separation (HSS), we develop a fast solver HSS-pGMRES-IPM for the saddle point problem from SVM training. Computational results show that, the fast solver HSS-pGMRES-IPM significantly increases the solution speed for the saddle point problem from SVM training than the conventional solver CF.References
N. Cristianini, and J. Shawe-Taylor, An Introduction to Support Vector Machines and other Kernel-based Learning Methods, Cambridge University Press, 2000.
J. A. K. Suykens, T. Van Gestel, and J. De Brabanter, Least Squares Support Vector Machines, World Scientific, 2002.
I. Steinwart, and A. Christmann, Support Vector Machines, Springer, 2008.
S. Abe, Support Vector Machines for Pattern Classification, Springer, 2010.
C. Campbell, and Y. Ying, Learning with Support Vector Machines, Morgan & Claypool Publishers, 2011.
A. Statnikov, C. F. Aliferis, and D. P. Hardin, A Gentle Introduction to Support Vector Machines in Biomedicine: Theory and Methods, World Scientific, 2011.
V. N. Vapnik, Statistical Learning Theory, Wiley, 1998.
V. Vapnik, The Nature of Statistical Learning Theory, Springer, 2000.
S. J. Wright, Primal-Dual Interior-Point Methods, Society for Industrial and Applied Mathematics, 1997.
Y. Ye, Interior Point Algorithms: Theory and Analysis, Wiley, 2011.
J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, Society for Industrial and Applied Mathematics, 2001.
C. Roos, T. Terlaky, and J. P. Vial, Interior Point Methods for Linear Optimization, Springer, 2006.
T. Terlaky, Interior Point Methods of Mathematical Programming, Springer, 1996.
Y. Zhang, User's guide to Lipsol linear-programming interior point solvers V0.4, Optimization Methods and Software, (11) 1-4 (1999), pp. 385-396.
I. Lustig, R. Marsten, and D. Shanno, On implementing Mehrotra’s predictor–corrector interior-point method for linear programming, SIAM Journal on Optimization, (2) 3 (1992), pp. 435-449.
R. Tapia, Y. Zhang, M. Saltzman, and A. Weiser, The Mehrotra predictor-corrector interior-point method as a perturbed composite Newton method, SIAM Journal on Optimization, (6) 1 (1996), pp. 47-56.
Y. Zhang, and D. Zhang, On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms, Mathematical Programming, (68) 1-3 (1995), pp. 303-318.
T. Carpenter, I. Lusting, J. Mulvey, and D. Shanno, Higher-order predictor-corrector interior point methods with application to quadratic objectives, SIAM Journal on Optimization, (3) 4 (1993), pp. 696-725.
M. Salahi, J. Peng, and T. Terlaky, On Mehrotra-type predictor-corrector algorithms, SIAM Journal on Optimization, (18) 4 (2008), pp. 1377-1397.
C. Cartis, Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming, Applied Numerical Mathematics, (59) 5 (2009), pp. 1110-1119.
J. Hefferon, Linear Algebra, Department of Mathematics & Applied Mathematics, Virginia Commonwealth University, 2009.
G. E. Shilov, Linear Algebra, Dover Publications, 2012.
L. N. Trefethen, and D. Bau, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997.
L. Smith, Linear Algebra, Springer, New York, 1998.
S. Lang, Linear Algebra, Springer, 1987.
G. Wu, Z. Zhang, and E. Chang, Kronecker factorization for speeding up kernel machines, Proceedings of the SIAM International Conference on Data Mining (SDM), 2005.
G. Wu, E. Chang, Y. K. Chen, and C. Hughes, Incremental approximate matrix factorization for speeding up support vector machines, Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, 2006.
D. Wanyu, Z. Kai, and Z. Qinghua, Speed Up Kernel Projection Vector Machine Using Kronecker Decomposition, Proceedings of the 6th International Conference on New Trends in Information Science and Service Science and Data Mining (ISSDM), 23-25 October 2012, pp. 722-725.
M. Benzi, G. H. Golub, J. Liesen, Numerical solution of saddle point problems, Acta Numerica, (14) (2005), pp. 1-137.
H. C. Elman, Preconditioners for saddle point problems arising in computational fluid dynamics, Applied Numerical Mathematics, (43) 1-2 (2002), pp. 75-89.
H. C. Elman, D. J. Silvester, and A. J. Wathen, Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations, Numer. Math., (90) 4 (2002), pp. 665-688.
M. Benzi, and A. Wathen, Some Preconditioning Techniques for Saddle Point Problems, Springer, Berlin Heidelberg, 2008.
Z.-Z. Bai, G. H. Golub, and M. K. Ng, Hermitian and Skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., (24) 3 (2002), pp. 603-626.
M. Benzi, M. Gander, and G. Golub, Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems, BIT Numerical Mathematics, (43) 5 (2003), pp. 881-900.
M. Benzi, and G. Golub, A preconditioner for generalized saddle point problems, SIAM Journal on Matrix Analysis and Applications, (26) 1 (2004), pp. 20-41.
Z.-Z. Bai, G. H. Golub, and J.-Y. Pan, Preconditioned Hermitian and Skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., (98) 1 (2004), pp. 1-32.
D. Bertaccini, G. H. Golub, S. S. Capizzano, and C. T. Possio, Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation, Numer. Math., (99) 3 (2005), pp. 441-484.
G. Golub, C. Greif, and J. Varah, An algebraic analysis of a block diagonal preconditioner for saddle point systems, SIAM Journal on Matrix Analysis and Applications, (27) 3 (2005), pp. 779-792.
Z.-Z. Bai, G. H. Golub, L.-Z. Lu, and J.-F. Yin, Block triangular and Skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., (26) 3 (2005), pp. 844-863.
M. Botchev, and G. Golub, A class of nonsymmetric preconditioners for saddle point problems, SIAM Journal on Matrix Analysis and Applications, (27) 4 (2006), pp. 1125-1149.
Z.-Z. Bai, On semi-convergence of Hermitian and Skew-Hermitian splitting methods for singular linear systems, Computing, (89) 3-4 (2010), pp. 171-197.
Z.-Z. Bai, G. H. Golub, and C.-K. Li, Optimal parameter in Hermitian and Skew-Hermitian splitting method for certain two-by-two block matrices, SIAM J. Sci. Comput., (28) 2 (2006), pp. 583-603.
S. Fine, and K. Scheinberg, Efficient SVM training using low-rank kernel representations, J. Mach. Learn. Res., (2) (2002), pp. 243-264.
K. Scheinberg, An efficient implementation of an active set method for SVMs, J. Mach. Learn. Res., (7) (2006), pp. 2237-2257.
S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, (2) 4 (1992), pp. 575-601.
A. Bhattacharjee, W. G. Richards, J. Staunton, C. Li, S. Monti, P. Vasa, C. Ladd, J. Beheshti, R. Bueno, M. Gillette, M. Loda, G. Weber, E. J. Mark, E. S. Lander, W. Wong, B. E. Johnson, T. R. Golub, D. J. Sugarbaker, and M. Meyerson, Classification of human lung carcinomas by mRNA expression profiling reveals distinct adenocarcinoma subclasses, Proceedings of the National Academy of Sciences, (98) 24 (2001), pp. 13790-13795.
T. R. Kruth, Interior-Point Algorithms for Quadratic Programming, Technical University of Denmark, Lyngby, Denmark, 2008.
E. Anderson, J. Gondzio, C. Meszaros, and X. Xu, Implementation of Interior Point Methods for Large Scale Linear Programming, Technical report, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, Geneva, Switzerland, January 1996.
G. H. Golub, and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, 2012.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
