Abstract
A paradigmatic algorithm for online learning is the Hedge algorithm by Freund and Schapire. An allocation into different strategies is chosen for multiple rounds and each round incurs corresponding losses for each strategy. The algorithm obtains a favorable guarantee for the total losses even in an adversarial situation. This work presents quantum algorithms for such online learning in an oracular setting. For time steps and strategies, we exhibit run times of about for estimating the losses and for betting on individual strategies by sampling. In addition, we discuss a quantum analog of the Sparsitron, a machine learning algorithm based on the Hedge algorithm. The quantum algorithm inherits the provable learning guarantees from the classical algorithm and exhibits polynomial speedups. The speedups may find relevance in finance, for example, for hedging risks, and machine learning, for example, for learning generalized linear models or Ising models.
- Received 29 June 2020
- Revised 30 November 2020
- Accepted 7 December 2020
DOI:https://doi.org/10.1103/PhysRevA.103.012418
©2021 American Physical Society