norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fraction of the input features in making decisions, and is especially useful when the total number of features,

p

, approaches or exceeds the number of training samples,

m

. We prove a

Ω(m)

worst-case lower bound for computational complexity of any quantum training algorithm relying on black-box access to training samples; quantum sparse SVM has at least linear worst-case complexity. However, we prove that there are realistic scenarios in which a sparse linear classifier is expected to have high accuracy, and can be trained in sublinear time in terms of both the number of training samples and the number of features.

DOI: 10.48550/arxiv.1902.01879

Related papers

Quantum Sparse Support Vector Machines

Tomasz Arodź, Seyran Saeedi

We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the $L_1$ norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fraction of the input features in making decisions, and is especially useful when the total number of features, $p$ , approaches or exceeds the number of training samples, $m$ . We prove a $\Omega(m)$ worst-case lower bound for computational complexity of any quantum training algorithm relying on black-box access to training samples; quantum sparse SVM has at least linear worst-case complexity. However, we prove that there are realistic scenarios in which a sparse linear classifier is expected to have high accuracy, and can be trained in sublinear time in terms of both the number of training samples and the number of features.We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the $L_1$ norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fraction of the input features in making decisions, and is especially useful when the total number of features, $p$, approaches or exceeds the number of training samples, $m$. We prove a $\Omega(m)$ worst-case lower bound for computational complexity of any quantum training algorithm relying on black-box access to training samples; quantum sparse SVM has at least linear worst-case complexity. However, we prove that there are realistic scenarios in which a sparse linear classifier is expected to have high accuracy, and can be trained in sublinear time in terms of both the number of training samples and the number of features.

Feb 5, 20198 citations

SPARSITY AND WEAK SUPERVISION IN QUANTUM MACHINE LEARNING

Seyran Saeedi

Quantum computing is an interdisciplinary field at the intersection of computer science, mathematics, and physics that studies information processing tasks on a quantum computer. A quantum computer is a device whose operations are governed by the laws of quantum mechanics. As building quantum computers is nearing the era of commercialization and quantum supremacy, it is essential to think of potential applications that we might benefit from. Among many applications of quantum computation, one of the emerging fields is quantum machine learning. We focus on predictive models for binary classification and variants of Support Vector Machines that we expect to be especially important when training data becomes so large that a quantum algorithm with a guaranteed speedup becomes useful. We present a quantum machine learning algorithm for training Sparse Support Vector Machine for problems with large datasets that require a sparse solution. We also present the first quantum semi-supervised algorithm, where we still have a large dataset, but only a small fraction is provided with labels. While the availability of data for training machine learning models is steadily increasing, oftentimes it is much easier to collect feature vectors to obtain the corresponding labels. Here, we present a quantum machine learning algorithm for training Semi-Supervised Kernel Support Vector Machines. The algorithm uses recent advances in quantum sample-based Hamiltonian simulation to extend the existing Quantum LS-SVM algorithm to handle the semi-supervised term in the loss while maintaining the same quantum speedup as the Quantum LS-SVM.Quantum computing is an interdisciplinary field at the intersection of computer science, mathematics, and physics that studies information processing tasks on a quantum computer. A quantum computer is a device whose operations are governed by the laws of quantum mechanics. As building quantum computers is nearing the era of commercialization and quantum supremacy, it is essential to think of potential applications that we might benefit from. Among many applications of quantum computation, one of the emerging fields is quantum machine learning. We focus on predictive models for binary classification and variants of Support Vector Machines that we expect to be especially important when training data becomes so large that a quantum algorithm with a guaranteed speedup becomes useful. We present a quantum machine learning algorithm for training Sparse Support Vector Machine for problems with large datasets that require a sparse solution. We also present the first quantum semi-supervised algorithm, where we still have a large dataset, but only a small fraction is provided with labels. While the availability of data for training machine learning models is steadily increasing, oftentimes it is much easier to collect feature vectors to obtain the corresponding labels. Here, we present a quantum machine learning algorithm for training Semi-Supervised Kernel Support Vector Machines. The algorithm uses recent advances in quantum sample-based Hamiltonian simulation to extend the existing Quantum LS-SVM algorithm to handle the semi-supervised term in the loss while maintaining the same quantum speedup as the Quantum LS-SVM.

Jan 1, 20200 citations

Quantum algorithm for training nonlinear SVMs in almost linear time.

Jonathan Allcock, Chang‐Yu Hsieh

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 algorithm of Joachims, our algorithm has a running time which scales linearly in the number of training examples (up to polylogarithmic factors) and applies to the standard soft-margin $\ell_1$ -SVM model. In contrast, the best classical algorithms have super-linear scaling for general feature maps, and achieve linear $m$ scaling only for linear SVMs, where classification is performed in the original input data space, or for the special case of feature maps corresponding to 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.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 algorithm of Joachims, our algorithm has a running time which scales linearly in the number of training examples (up to polylogarithmic factors) and applies to the standard soft-margin $\ell_1$-SVM model. In contrast, the best classical algorithms have super-linear scaling for general feature maps, and achieve linear $m$ scaling only for linear SVMs, where classification is performed in the original input data space, or for the special case of feature maps corresponding to 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.

Jun 18, 20200 citations

Quantum-Inspired Support Vector Machine

Chen Ding, Tian-Yi Bao, He-Liang Huang

Support vector machine (SVM) is a particularly powerful and flexible supervised learning model that analyzes data for both classification and regression, whose usual algorithm complexity scales polynomially with the dimension of data space and the number of data points. To tackle the big data challenge, a quantum SVM algorithm was proposed, which is claimed to achieve exponential speedup for least squares SVM (LS-SVM). Here, inspired by the quantum SVM algorithm, we present a quantum-inspired classical algorithm for LS-SVM. In our approach, an improved fast sampling technique, namely indirect sampling, is proposed for sampling the kernel matrix and classifying. We first consider the LS-SVM with a linear kernel, and then discuss the generalization of our method to nonlinear kernels. Theoretical analysis shows our algorithm can make classification with arbitrary success probability in logarithmic runtime of both the dimension of data space and the number of data points for low rank, low condition number, and high dimensional data matrix, matching the runtime of the quantum SVM.Support vector machine (SVM) is a particularly powerful and flexible supervised learning model that analyzes data for both classification and regression, whose usual algorithm complexity scales polynomially with the dimension of data space and the number of data points. To tackle the big data challenge, a quantum SVM algorithm was proposed, which is claimed to achieve exponential speedup for least squares SVM (LS-SVM). Here, inspired by the quantum SVM algorithm, we present a quantum-inspired classical algorithm for LS-SVM. In our approach, an improved fast sampling technique, namely indirect sampling, is proposed for sampling the kernel matrix and classifying. We first consider the LS-SVM with a linear kernel, and then discuss the generalization of our method to nonlinear kernels. Theoretical analysis shows our algorithm can make classification with arbitrary success probability in logarithmic runtime of both the dimension of data space and the number of data points for low rank, low condition number, and high dimensional data matrix, matching the runtime of the quantum SVM.

arXiv:1906.08902IEEE Transactions on Neural Networks and Learning SystemsJun 10, 2021186 citations

Adiabatic Quantum Support Vector Machines

Dong Jun Woun, Prasanna Date

Machine learning's ability to analyze and predict complex data enables many scientific discoveries and industrial advances. However, state-of-the-art machine learning requires extensive computational resources for training. In machine learning, the training phase is crucial because it enables the model to acquire knowledge from the provided data. The duration of the training process varies significantly, ranging from a few hours to several months. As a result, the computational cost and time constraints hinder researchers from using machine learning. To address this issue, we investigated the possibility of using quantum computers for machine-learning tasks. We compared Date's [1] quantum support vector machine (SVM) approach on a D-Wave Advantage to a classical implementation on AMD Ryzen and Intel Xeon processors. We evaluated both the time-to-solution and the machine-learning performance of the quantum and classical systems. The results of our study demonstrated that SVMs scaled $O(N^{2})$ on the quantum computer and $O(N^{2}d)$ on the classical computer. Here, N represents the number of samples, and d represents the number of features. So, when trained with a data set with eight million features, we found that the quantum annealer outperformed the classical computer by 3.5-4.5x. The quantum approach maintained a comparable accuracy to the classical approach as well. In conclusion, quantum computers offer a computational advantage over classical computers for machine learning.Machine learning's ability to analyze and predict complex data enables many scientific discoveries and industrial advances. However, state-of-the-art machine learning requires extensive computational resources for training. In machine learning, the training phase is crucial because it enables the model to acquire knowledge from the provided data. The duration of the training process varies significantly, ranging from a few hours to several months. As a result, the computational cost and time constraints hinder researchers from using machine learning. To address this issue, we investigated the possibility of using quantum computers for machine-learning tasks. We compared Date's [1] quantum support vector machine (SVM) approach on a D-Wave Advantage to a classical implementation on AMD Ryzen and Intel Xeon processors. We evaluated both the time-to-solution and the machine-learning performance of the quantum and classical systems. The results of our study demonstrated that SVMs scaled$O(N^{2})$on the quantum computer and$O(N^{2}d)$on the classical computer. Here, N represents the number of samples, and d represents the number of features. So, when trained with a data set with eight million features, we found that the quantum annealer outperformed the classical computer by 3.5-4.5x. The quantum approach maintained a comparable accuracy to the classical approach as well. In conclusion, quantum computers offer a computational advantage over classical computers for machine learning.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 17, 20233 citations

Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent

Debbie Lim, Yixian Qiu, Patrick Rebentrost +1 more

Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of \hyperlink{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of $O(1/\sqrt{T})$ , where $T$ is the number of iterations.Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of \hyperlink{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of $O(1/\sqrt{T})$, where $T$ is the number of iterations.

arXiv:2411.03925Nov 6, 20240 citations

We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the

L_1

p

, approaches or exceeds the number of training samples,

m

. We prove a

Ω(m)

We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the

L_1

p

, approaches or exceeds the number of training samples,

m

. We prove a

\Omega(m)

\ell_1

-SVM model. In contrast, the best classical algorithms have super-linear scaling for general feature maps, and achieve linear

m

scaling only for linear SVMs, where classification is performed in the original input data space, or for the special case of feature maps corresponding to 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.

O(N^{2})

on the quantum computer and

O(N^{2}d)

on the classical computer. Here, N represents the number of samples, and d represents the number of features. So, when trained with a data set with eight million features, we found that the quantum annealer outperformed the classical computer by 3.5-4.5x. The quantum approach maintained a comparable accuracy to the classical approach as well. In conclusion, quantum computers offer a computational advantage over classical computers for machine learning.

O(1/\sqrt{T})

, where

T

is the number of iterations.