A Near-Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms

Abstract

Using quantum algorithms, we obtain, for accuracy $\epsilon,0<\epsilon<1/4$ and confidence $1-\delta,0<\delta<1,$ a new sample complexity upper bound of $O((\mbox{log}(\frac{1}{\delta}))/\epsilon)$ as $\epsilon,\delta\rightarrow 0$ (up to a polylogarithmic factor in $\epsilon^{-1}$) for a general agnostic learning model, provided the hypothesis class is of finite cardinality. This greatly improves upon a corresponding sample complexity of asymptotic order $\Theta((\mbox{log}(\frac{1}{\delta}))/\epsilon^{2})$ known in the literature to be attainable by means of classical (non-quantum) algorithms for an agnostic learning problem also with hypothesis set of finite cardinality (see, for example, Arunachalam and de Wolf (2018) and the classical statistical learning theory references cited there). Thus, for general agnostic learning, the quantum speedup in the rate of learning that we achieve is quadratic in $\epsilon^{-1}$ (up to a polylogarithmic factor).