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

• URL: http://arxiv.org/abs/2006.10299v3
• Date: Fri, 9 Oct 2020 11:19:44 GMT
• Title: A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time
• Authors: Jonathan Allcock and Chang-Yu Hsieh
• Abstract summary: We propose a quantum algorithm for training nonlinear support vector machines (SVM) for feature space learning. Based on the classical SVM-perf algorithm of Joachims, our algorithm has a running time which scales linearly in the number of training examples.
• Score: 0.2855485723554975
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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, 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.

Related papers

• Local Binary and Multiclass SVMs Trained on a Quantum Annealer [0.8399688944263844]
  In the last years, with the advent of working quantum annealers, hybrid SVM models characterised by quantum training and classical execution have been introduced. These models have demonstrated comparable performance to their classical counterparts. However, they are limited in the training set size due to the restricted connectivity of the current quantum annealers.
  arXiv  Detail & Related papers  (2024-03-13T14:37:00Z)
• Sparse Learning and Class Probability Estimation with Weighted Support Vector Machines [1.3597551064547502]
  weighted Support Vector Machines (wSVMs) have shown great values in robustly predicting the class probability and classification for various problems with high accuracy. We propose novel wSVMs frameworks that incorporate automatic variable selection with accurate probability estimation for sparse learning problems. The proposed wSVMs-based sparse learning methods have wide applications and can be further extended to $K$-class problems through ensemble learning.
  arXiv  Detail & Related papers  (2023-12-17T06:12:33Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice [79.48432795639403]
  Mirror descent value iteration (MDVI) is an abstraction of Kullback-Leibler (KL) and entropy-regularized reinforcement learning (RL) We study MDVI with linear function approximation through its sample complexity required to identify an $varepsilon$-optimal policy. We present Variance-Weighted Least-Squares MDVI, the first theoretical algorithm that achieves nearly minimax optimal sample complexity for infinite-horizon linear MDPs.
  arXiv  Detail & Related papers  (2023-05-22T16:13:05Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• LQF: Linear Quadratic Fine-Tuning [114.3840147070712]
  We present the first method for linearizing a pre-trained model that achieves comparable performance to non-linear fine-tuning. LQF consists of simple modifications to the architecture, loss function and optimization typically used for classification.
  arXiv  Detail & Related papers  (2020-12-21T06:40:20Z)
• AML-SVM: Adaptive Multilevel Learning with Support Vector Machines [0.0]
  This paper proposes an adaptive multilevel learning framework for the nonlinear SVM. It improves the classification quality across the refinement process, and leverages multi-threaded parallel processing for better performance.
  arXiv  Detail & Related papers  (2020-11-05T00:17:02Z)
• A Semismooth-Newton's-Method-Based Linearization and Approximation Approach for Kernel Support Vector Machines [1.177306187948666]
  Support Vector Machines (SVMs) are among the most popular and the best performing classification algorithms. In this paper, we propose a semismooth Newton's method based linearization approximation approach for kernel SVMs. The advantage of the proposed approach is that it maintains low computational cost and keeps a fast convergence rate.
  arXiv  Detail & Related papers  (2020-07-21T07:44:21Z)
• Unified SVM Algorithm Based on LS-DC Loss [0.0]
  We propose an algorithm that can train different SVM models. UniSVM has a dominant advantage over all existing algorithms because it has a closed-form solution. Experiments show that UniSVM can achieve comparable performance in less training time.
  arXiv  Detail & Related papers  (2020-06-16T12:40:06Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  We introduce algorithms for learning nonlinear dynamical systems of the form $x_t+1=sigma(Thetastarx_t)+varepsilon_t$. We give an algorithm that recovers the weight matrix $Thetastar$ from a single trajectory with optimal sample complexity and linear running time.
  arXiv  Detail & Related papers  (2020-04-30T10:42:48Z)
• On Coresets for Support Vector Machines [61.928187390362176]
  A coreset is a small, representative subset of the original data points. We show that our algorithm can be used to extend the applicability of any off-the-shelf SVM solver to streaming, distributed, and dynamic data settings.
  arXiv  Detail & Related papers  (2020-02-15T23:25:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.