Improved Quantum Boosting
arXiv:2009.08360
Abstract
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity gave the first quantum improvement for boosting, by combining Freund and Schapire's AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner's hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio's SmoothBoost algorithm.
arXiv comment16 pages
References in corpus (7)
- Quantum Machine Learning
- Quantum Amplitude Amplification and Estimation
- Improvements in Quantum SDP-Solving with Applications
- A Survey of Quantum Learning Theory
- Quantum Speed-ups for Semidefinite Programming
- Quantum algorithms for hedging and the learning of Ising models
- Quantum Speedup in Adaptive Boosting of Binary Classification