A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time

Jonathan Allcock; Chang-Yu Hsieh

doi:10.22331/q-2020-10-15-342

A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time

Jonathan Allcock and Chang-Yu Hsieh

Tencent Quantum Laboratory

Published:	2020-10-15, volume 4, page 342
Eprint:	arXiv:2006.10299v3
Doi:	https://doi.org/10.22331/q-2020-10-15-342
Citation:	Quantum 4, 342 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We propose a quantum algorithm for training nonlinear support vector machines (SVM) for feature space learning where classical input data is encoded in the amplitudes of quantum states. Based on the classical SVM-perf algorithm of Joachims [1], our algorithm has a running time which scales linearly in the number of training examples $m$ (up to polylogarithmic factors) and applies to the standard soft-margin $\ell_1$-SVM model. In contrast, while classical SVM-perf has demonstrated impressive performance on both linear and nonlinear SVMs, its efficiency is guaranteed only in certain cases: it achieves linear $m$ scaling only for linear SVMs, where classification is performed in the original input data space, or for the special cases of low-rank or shift-invariant kernels. Similarly, previously proposed quantum algorithms either have super-linear scaling in $m$, or else apply to different SVM models such as the hard-margin or least squares $\ell_2$-SVM which lack certain desirable properties of the soft-margin $\ell_1$-SVM model. We classically simulate our algorithm and give evidence that it can perform well in practice, and not only for asymptotically large data sets.

► BibTeX data

@article{Allcock2020quantumextensionof,
  doi = {10.22331/q-2020-10-15-342},
  url = {https://doi.org/10.22331/q-2020-10-15-342},
  title = {A quantum extension of {SVM}-perf for training nonlinear {SVM}s in almost linear time},
  author = {Allcock, Jonathan and Hsieh, Chang-Yu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {342},
  month = oct,
  year = {2020}
}

► References

[1] Thorsten Joachims. Training linear SVMs in linear time. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 217–226. ACM, 2006. 10.1145/1150402.1150429.
https://doi.org/10.1145/1150402.1150429

[2] Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory, pages 144–152. ACM, 1992. 10.1145/130385.130401.
https://doi.org/10.1145/130385.130401

[3] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20 (3): 273–297, 1995. 10.1023/A:1022627411411.
https://doi.org/10.1023/A:1022627411411

[4] Christopher JC Burges. A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2 (2): 121–167, 1998. 10.1023/A:1009715923555.
https://doi.org/10.1023/A:1009715923555

[5] Michael C Ferris and Todd S Munson. Interior-point methods for massive support vector machines. SIAM Journal on Optimization, 13 (3): 783–804, 2002. 10.1137/S1052623400374379.
https://doi.org/10.1137/S1052623400374379

[6] Olvi L Mangasarian and David R Musicant. Lagrangian support vector machines. Journal of Machine Learning Research, 1 (Mar): 161–177, 2001. 10.1162/15324430152748218.
https://doi.org/10.1162/15324430152748218

[7] S Sathiya Keerthi and Dennis DeCoste. A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6 (Mar): 341–361, 2005.

[8] Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. Mathematical programming, 127 (1): 3–30, 2011. 10.1145/1273496.1273598.
https://doi.org/10.1145/1273496.1273598

[9] Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.

[10] Christopher KI Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems, pages 682–688, 2001.

[11] Shai Fine and Katya Scheinberg. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2 (Dec): 243–264, 2001.

[12] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pages 1177–1184, 2008.

[13] Thorsten Joachims. Making large-scale SVM learning practical. In Advances in Kernel Methods-Support Vector Learning. MIT-press, 1999.

[14] John C Platt. Fast training of support vector machines using sequential minimal optimization. MIT press, 1999.

[15] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2 (3): 27, 2011. 10.1145/1961189.1961199.
https://doi.org/10.1145/1961189.1961199

[16] Ronan Collobert and Samy Bengio. SVMTorch: Support vector machines for large-scale regression problems. Journal of Machine Learning Research, 1 (Feb): 143–160, 2001. 10.1162/15324430152733142.
https://doi.org/10.1162/15324430152733142

[17] Thorsten Joachims and Chun-Nam John Yu. Sparse kernel SVMs via cutting-plane training. Machine Learning, 76 (2-3): 179–193, 2009. 10.1007/s10994-009-5126-6.
https://doi.org/10.1007/s10994-009-5126-6

[18] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113 (13): 130503, 2014. 10.1103/PhysRevLett.113.130503.
https://doi.org/10.1103/PhysRevLett.113.130503

[19] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209–212, 2019. 10.1038/s41586-019-0980-2.
https://doi.org/10.1038/s41586-019-0980-2

[20] Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical Review Letters, 122 (4): 040504, 2019. 10.1103/PhysRevLett.122.040504.
https://doi.org/10.1103/PhysRevLett.122.040504

[21] Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi. Quantum algorithms for second-order cone programming and support vector machines. arXiv preprint arXiv:1908.06720, 2019.
arXiv:1908.06720

[22] Tomasz Arodz and Seyran Saeedi. Quantum sparse support vector machines. arXiv preprint arXiv:1902.01879, 2019.
arXiv:1902.01879

[23] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Proceedings of the 36th International Conference on Machine Learning. PMLR, 2019.

[24] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100 (16): 160501, 2008. 10.1103/PhysRevLett.100.160501.
https://doi.org/10.1103/PhysRevLett.100.160501

[25] Anupam Prakash. Quantum algorithms for linear algebra and machine learning. PhD thesis, UC Berkeley, 2014.

[26] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217–228, 2019. 10.1145/3313276.3316310.
https://doi.org/10.1145/3313276.3316310

[27] Ewin Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv preprint arXiv:1811.00414, 2018.
arXiv:1811.00414

[28] András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv preprint arXiv:1811.04909, 2018.
arXiv:1811.04909

[29] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. Quantum, 4: 307, 2020. 10.22331/q-2020-08-13-307.
https://doi.org/10.22331/q-2020-08-13-307

[30] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. 10.1017/CBO9780511804441.
https://doi.org/10.1017/CBO9780511804441

[31] Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6 (Sep): 1453–1484, 2005.

[32] Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang. Quantum algorithms for feedforward neural networks. ACM Transactions on Quantum Computing, 1 (1), 2020. 10.1145/3411466.
https://doi.org/10.1145/3411466

[33] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 10.4230/LIPIcs.ITCS.2017.49.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49

[34] Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O’Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brandão, and Garnet Kin-Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16 (2): 205–210, 2020. 10.1038/s41567-019-0704-4.
https://doi.org/10.1038/s41567-019-0704-4

[35] Chang-Yu Hsieh, Qiming Sun, Shengyu Zhang, and Chee Kong Lee. Unitary-coupled restricted boltzmann machine ansatz for quantum simulations. https://arxiv.org/abs/1912.02988, 2019.
arXiv:1912.02988

[36] Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik. Quantum autoencoders for efficient compression of quantum data. Quantum Science and Technology, 2 (4): 045001, 2017. 10.1088/2058-9565/aa8072.
https://doi.org/10.1088/2058-9565/aa8072

[37] Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv preprint arXiv:1802.06002, 2018.
arXiv:1802.06002

[38] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Isaac, and Nathan Killoran. Quantum embeddings for machine learning. arXiv preprint arXiv:2001.03622, 2020.
arXiv:2001.03622

[39] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002.

Cited by

[1] Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi, "Quantum algorithms for Second-Order Cone Programming and Support Vector Machines", Quantum 5, 427 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2021-08-01 13:50:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2021-08-01 13:50:15).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.