3
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Fast Quantum Algorithm for Learning with Optimized Random Features

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Kernel methods augmented with random features give scalable algorithms for learning from big data. But it has been computationally hard to sample random features according to a probability distribution that is optimized for the data, so as to minimize the required number of features for achieving the learning to a desired accuracy. Here, we develop a quantum algorithm for sampling from this optimized distribution over features, in runtime \(O(D)\) that is linear in the dimension \(D\) of the input data. Our algorithm achieves an exponential speedup in \(D\) compared to any known classical algorithm for this sampling task. In contrast to existing quantum machine learning algorithms, our algorithm circumvents sparsity and low-rank assumptions and thus has wide applicability. We also show that the sampled features can be combined with regression by stochastic gradient descent to achieve the learning without canceling out our exponential speedup. Our algorithm based on sampling optimized random features leads to an accelerated framework for machine learning that takes advantage of quantum computers.

          Related collections

          Author and article information

          Journal
          22 April 2020
          Article
          2004.10756
          274ff705-2d1b-4c2d-920f-eb6951715ed2

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          32 pages, 2 figures, comments are welcome
          quant-ph cs.LG stat.ML

          Quantum physics & Field theory,Machine learning,Artificial intelligence
          Quantum physics & Field theory, Machine learning, Artificial intelligence

          Comments

          Comment on this article