PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum-Inspired Support Vector Machine

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

arXiv:1906.08902v5cs.LGcs.CCquant-phstat.ML

TL;DR

Classical SVM algorithms scale polynomially with data size, motivating methods that could match quantum SVM speedups. The paper proposes a quantum-inspired classical LS-SVM based on indirect sampling of the kernel matrix. Theoretical analysis and experiments support exponential speedup and competitive classification under low-rank conditions, while broader applicability and tighter guarantees remain open.

  • Problem

    Classical SVM algorithms have polynomial complexity in data sizes, motivating a classical approach that can match the claimed exponential speedup of quantum SVM.

  • Method

    The paper develops a quantum-inspired classical LS-SVM using indirect sampling, arborescent data structures, sampled kernel-matrix approximations, and classification from solved parameters.

  • Results

    Exponential speedup is reported for low-rank, low-condition-number, high-dimensional data, with experiments showing about 5% higher average classification rates than LIBSVM on low-rank approximated datasets.

  • Takeaways & Limitations

    The method can achieve quantum-SVM-like logarithmic runtime without quantum resources when the data matrix is low rank or well approximated by a low-rank matrix.

  • Takeaways & Limitations

    The method remains designed for low-rank data, and reducing data-matrix conditions, complexity, and theoretical error bounds requires further work.

Abstract

from arXiv · show

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, a 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 non-linear 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.

I. INTRODUCTION

The paper asks whether classical algorithms can match quantum speedups and proposes a quantum-inspired classical SVM using indirect sampling to avoid polynomial-size kernel computations. The approach targets LS-SVM and achieves exponential speedup under low-rank, low-condition-number, high-dimensional conditions.

  • Motivation: Quantum-inspired classical algorithms seek to match quantum speedups without quantum resources.The introduction frames the broader question of whether classical computation can reach quantum-algorithm complexity.
  • Motivation: Existing classical SVM algorithms have polynomial time complexity, whereas quantum SVM has complexity polynomial in logarithms of data sizes.The paper positions its method against this classical–quantum complexity gap.
  • Method: The proposed method uses arborescent data structures, subsampling, approximate kernel-matrix singular value decomposition, and optimization for classification.Labeled vectors are sampled by both number and length to obtain a smaller dataset before solving the classification problem.
  • Method: Indirect sampling avoids direct multiplication of vectors or matrices with kernel-scale dimensions, preserving the intended speedup.The method is developed because direct access to the kernel matrix is inefficient for the required matrix inversion.
  • Scope: The initial analysis assumes linear LS-SVM without regularization or bias, while extensions address regularization, non-linear kernels, and nonzero bias.The zero-bias assumption is represented by b = 0, with a generalized method discussed for b ≠ 0.

C. The sampling technique

The sampling technique constructs normalized submatrices through length-square sampling of columns and rows, enabling unbiased matrix estimates and efficient trace, product, and related computations. The method uses repeated sampling and controlled-error estimation rather than full-matrix operations.

  • Submatrix construction: Submatrix sampling first selects r columns from X, then c rows from the selected columns to form X′ and X′′.The row sampling chooses columns uniformly from the previously selected set.
  • Submatrix construction: The normalized submatrices satisfy E[X′X′^T] = XX^T and E[X′′^TX′′] = X′^TX′.These equalities make the sampled products unbiased estimators of the corresponding full products.
  • Sampling technique: The technique samples matrix indices according to norm-squared probabilities and normalizes the resulting rows and columns.This produces representative low-dimensional projections instead of computing with the entire matrix.
  • Efficient access: Arborescent data structures support logarithmic-time sampling of vector and matrix components.Matrices are stored as lists of row or column trees, while calculations reveal only sampled low-dimensional projections.
  • Trace estimation: Trace inner products are estimated by sampling rows and entries, averaging repeated estimates, and taking a median for controlled relative error and success probability.The estimator targets Tr[AB] using length-square sampling access to A and query access to B.

2) Rejection sampling:

The algorithm indirectly samples the training matrix, decomposes a smaller matrix spectrally, estimates the relevant eigenvectors and classification expression, and outputs a class from its sign. Its analysis gives polylogarithmic dependence on data dimensions under stated rank, condition-number, and accuracy assumptions.

  • Rejection sampling:: The input consists of m labeled training points, an error bound ϵ, and success probability bound 1 − η; the goals are approximating α and classifying any x.The target coefficient vector is α = (X^T X)+y.
  • Rejection sampling:: Indirect sampling subsamples columns and then rows of X to construct smaller matrices A′ and A′′ for processing.The sampled matrices are defined as A′ = X′T X′ and A′′ = X′′T X′′.
  • Rejection sampling:: The algorithm spectrally decomposes A′′ and represents it using eigenvectors V′′ and squared eigenvalues.For an r×r symmetric matrix, classical spectral decomposition has complexity O(r^3).
  • Rejection sampling:: It estimates an approximate coefficient vector ˜α from ˜R^T u, then evaluates x^T X˜α to determine the classification sign.Positive values correspond to class 1, while negative values correspond to class −1.
  • Rejection sampling:: The theorem bounds classification-expression error below ϵκ^2√m∥x∥ and states that runtime is polylogarithmic in m and n, polynomial in k, κ, ϵ, and η.The theorem assumes data matrix X has size m×n, rank k, norm 1, and condition number κ.
  • Rejection sampling:: The coefficient matrix can be extended from X^T X to X^T X + γ^-1I by shifting the calculated eigenvalues by γ^-1.The eigenvectors remain unchanged under this shift.

IV. ACCURACY

The accuracy analysis decomposes approximation error across subsampling, eigenvalue and query estimation, and proves that the constructed inverse approximation remains close to A^-1. The resulting classification expression has a bounded error, and reducing ε enables arbitrarily high success probability.

  • Error decomposition: The analysis bounds the classification-expression error by ε κ^2√m∥x∥.This bound is established for computing x^T X̃α.
  • Error decomposition: The proof decomposes total error into contributions from subsampling and eigenvector approximation, eigenvalue approximation, and querying R and α.These contributions are analyzed as E1, E2, and E3, with an additional estimation error E4.
  • Classification guarantee: For accurate classification, the relative error in x^TXα only needs to be less than 1, achievable by reducing ε over a chosen probability range.The algorithmic steps separately guarantee bounds for the query and estimation errors.
  • Inverse approximation: Five theorems establish that ṼΣ^-2Ṽ^T is functionally close to the inverse of matrix A.The target relation is ∥ṼΣ^-2Ṽ^TA−I_m∥≤ε.
  • Sampling and eigenvectors: Random subsampling keeps the operator-norm distance between X'^TX' and X''^TX'' small with high probability.This supports transferring approximate eigenvector information from A'' toward A'.
  • Sampling and eigenvectors: If A' and A'' are close in operator norm, eigenvectors of A'' approximately work as eigenvectors for A'.Theorem 4 further relates this approximation to the sampled data matrices.

V. COMPLEXITY

The complexity analysis partitions the main algorithm into four groups of steps and analyzes both computation and query costs, because several variables are queried rather than explicitly calculated.

  • Complexity analysis: The complexity analysis divides the algorithm into Steps 1–3, Step 4, Steps 5–6, and Steps 7–8.The corresponding groups are analyzed in Subsections V-A through V-D.

A. Sampling of columns and rows

The first three steps sample row and column indices using arborescent vector and matrix data structures, producing logarithmic sampling costs in the data dimensions.

  • Sampling of columns and rows: Steps 1–3 have overall time complexity O(r log2 m + cr log2 n).Step 2 samples r indices, while Step 3 samples c indices using the arborescent data structures.

B. The spectral decomposition

The spectral-decomposition stage costs O(r^3) for an r×r symmetric matrix, while later steps query sampled quantities and estimate the final classification expression through trace computation.

  • B. The spectral decomposition: Step 4 performs spectral decomposition of an r×r symmetric matrix with classical complexity O(r^3).The analysis identifies the classical symmetric QR method as the fastest cited approach for this step.
  • B. The spectral decomposition: The algorithm first establishes query access to R and α̃ before estimating the final trace.A query to α̃ costs r k Q(R) and has error ε1 with success probability greater than 1−rη1.
  • B. The spectral decomposition: R is queried through entries derived from X'^TX, with each required trace estimated using Algorithm 1.The query analysis separates the costs of R, α̃, and the final classification expression.

VI. EXPERIMENTS

Experiments evaluate QISVM on artificial low-rank and low-rank-approximated datasets, compare it with LIBSVM, and test sensitivity to algorithm parameters and nonlinear-kernel extensions.

  • Experiment I: Comparison with LIBSVM: QISVM and LIBSVM are evaluated on 10000×11000 datasets containing 11000 vectors of length 10000, with low-rank and rank-10000 scenarios.The data use 6000 training vectors and 5000 testing vectors.
  • Experiment I: Comparison with LIBSVM: QISVM achieves an average classification rate about 5% higher than LIBSVM on low-rank-approximated datasets.Both algorithms perform better on strictly low-rank datasets than on low-rank-approximated datasets.
  • Experiment II: Discussion on algorithm parameters: With practical subsampling sizes, QISVM maintains a classification rate around 0.90 across tested choices of 𝜖, 𝜂, and 𝑏.Each parameter choice is tested 50 times over 𝜖 from 1 to 10, 𝜂 from 0.1 to 1, and 𝑏 from 1 to 10.
  • Nonlinear kernels: For nonlinear kernels, polynomial-kernel sampling uses tensor powers so that the kernel matrix satisfies Z^T Z = K^p.General nonlinear kernels can be approximated by linear combinations of polynomial kernels when the corresponding feature function is continuous.

D. General LS-SVM

The general LS-SVM extension establishes sampling access to the kernel matrix, subsamples the associated system, solves it, and evaluates classification without direct full-size matrix operations.

  • General LS-SVM: The method extends from linear LS-SVM with b=0 to general LS-SVM by incorporating the kernel matrix into the sampled linear-system pipeline.The extension follows techniques analogous to Algorithm 3.
  • General LS-SVM: Kernel sampling access is established first, after which a sampled matrix A′′ is related to A through eigenvalue relations.The analysis uses theorems similar to Theorems 2 and 4.
  • General LS-SVM: After subsampling A∈R^m×m to A′′∈R^r×r, the algorithm continues with Steps 3–7 of Algorithm 3.Solving Equation (8) yields query access to α.
  • General LS-SVM: Classification is evaluated using y_j+(x−x_j)^T Xα−γ^-1α_j for an index j with α_j≠0.The index can be found by rejection sampling on α or by checking α_j after sampling X.
  • Scope and limitations: The proposed algorithm is reported to work well on low-rank or well low-rank-approximated datasets, while nonlinear SVM and LS-SVM extensions require further analysis and empirical evaluation.The conclusion also states that reducing data-matrix conditions, complexity, and error bounds remains future work.

APPENDIX A PROOF OF THEOREMS IN IV

The appendix proof decomposes the theorem verification into separate matrix-error and related bound arguments, using previously established techniques where applicable.

  • First bound: The first item is treated using a condition involving ∥A′−A′′∥≤β and relations involving V′′.The displayed proof details are not fully represented in the supplied passages.
  • Proof structure: The proof is organized by splitting the target statement into two items and handling each item through separate bounds.Several proof steps explicitly introduce the decomposition before presenting the corresponding arguments.
  • Proof structure: The appendix identifies one final step as using the same technique as the proof of Theorem 3.This connects the appendix argument to an earlier theorem-proving technique.

C. Proof of Theorem 6

Theorem 6 is supported by constructing artificial low-rank or low-rank-approximated datasets and showing that polynomial-kernel sampling can be performed from sampling access to the original data.

  • Dataset construction: Artificial datasets are generated by multiplying random n×k and k×m matrices, producing a matrix X with rank at most k.Matrix entries are sampled uniformly from [−0.5, 0.5].
  • Dataset construction: Adding bounded random turbulence makes X no longer low-rank but preserves a low-rank approximation.The perturbation is uniformly distributed in [−0.1x, 0.1x].
  • Dataset construction: The columns are normalized, divided into two classes by a random hyperplane, and split randomly into training and testing sets.The construction ensures both classes appear in the training set.
  • Polynomial-kernel sampling: Algorithm 4 samples a column and row index from Z, where each column is a p-th tensor power of an input vector.Its column-index steps sample from the column norm vector of Z using sampling access to X.
  • Polynomial-kernel sampling: Repeating sampling on x_j p times produces outcome probabilities matching sampling from the corresponding tensor-power column.This establishes the row-sampling component of the polynomial-kernel procedure.
Loading 1906.08902v5…