  Using quantum algorithms, we obtain, for accuracy $\epsilon>0$ 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$
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 with respect to these
results is quadratic in $\epsilon^{-1}$.
