Quantum algorithms for hedging and the learning of Ising models

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 $T$ time steps and $N$ strategies, we exhibit run times of about $O\left(\mathrm{poly}(T)\sqrt{N}\right)$ for estimating the losses and for betting on individual strategies by sampling. In addition, we discuss a quantum analogue 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.

arXiv comment16 pages

References in corpus (13)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum random access memory
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (1999)
• Quantum SDP-Solvers: Better upper and lower bounds
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum algorithms and lower bounds for convex optimization
• Convex optimization using quantum oracles
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Quantum Speedup in Adaptive Boosting of Binary Classification
• Quantum Boosting
• Sample-Optimal and Efficient Learning of Tree Ising models

Cited by in corpus (4)

• Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states
• Improved Quantum Boosting
• Quantum Alphatron: quantum advantage for learning with kernels and noise
• Multi-Armed Bandits and Quantum Channel Oracles