Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions

• URL: http://arxiv.org/abs/2004.10756v2
• Date: Mon, 9 Nov 2020 20:07:42 GMT
• Title: Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions
• Authors: Hayata Yamasaki, Sathyawageeswar Subramanian, Sho Sonoda, Masato Koashi
• Abstract summary: We develop a quantum algorithm for sampling from an optimized distribution over runtime features. Our algorithm achieves an exponential speedup in $D$ compared to any known classical algorithm for this sampling task.
• Score: 8.08640000394814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 papers

• Optimal sampling of tensor networks targeting wave function's fast decaying tails [0.0]
  We introduce an optimal strategy to sample quantum outcomes of local measurement strings for isometric tensor network states. The algorithm avoids sample repetition and, thus, is efficient at sampling distribution with exponentially decaying tails.
  arXiv  Detail & Related papers  (2024-01-18T19:00:05Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Sequential minimum optimization algorithm with small sample size estimators [0.06445605125467573]
  Sequential minimum optimization is a machine-learning global search training algorithm. We apply it to photonics circuits where the additional challenge appears: low frequency of coincidence events lowers the speed of the algorithm.
  arXiv  Detail & Related papers  (2023-03-02T06:02:46Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• An optimal scheduled learning rate for a randomized Kaczmarz algorithm [1.2183405753834562]
  We study how the learning rate affects the performance of a relaxed randomized Kaczmarz algorithm for solving $A x approx b + varepsilon$.
  arXiv  Detail & Related papers  (2022-02-24T17:38:24Z)
• Adaptive Random Quantum Eigensolver [0.0]
  We introduce a general method to parametrize and optimize the probability density function of a random number generator. Our optimization is based on two figures of merit: learning speed and learning accuracy.
  arXiv  Detail & Related papers  (2021-06-28T12:01:05Z)
• Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning [8.98526174345299]
  An algorithm for machine learning by quantum computer, quantum machine learning (QML), can exponentially speed up sampling of optimized random features. We here construct a QML algorithm for a classification task accelerated by the optimized random features. We prove that the QML algorithm for optimized random features, combined with gradient descent (SGD), can achieve state-of-the-art exponential convergence speed.
  arXiv  Detail & Related papers  (2021-06-16T18:00:00Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)

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.