Optimal Quantum Sample Complexity of Learning Algorithms.

Srinivasan Arunachalam, Ronald de Wolf

TL;DR

This paper demonstrates that, contrary to some prior beliefs, quantum examples don't offer a significant advantage over classical examples for learning in general settings (PAC and agnostic models). The authors prove that the sample complexity for learning with quantum examples is fundamentally limited by the same factors as classical learning, specifically the VC dimension of the concept class.

What Problem Does This Paper Address?

In machine learning, a key question is how many examples are needed to learn a concept (like a classification rule). This is quantified by "sample complexity." For classical learning, the VC dimension of a concept class is a fundamental measure of its complexity, tightly determining the sample complexity. Quantum computing offers the possibility of using "quantum examples" – coherent superpositions of classical examples. While some specific scenarios showed quantum examples could be more powerful, it was unclear if this advantage held in general, robust learning settings like the PAC (Probably Approximately Correct) and agnostic models, which require learning under any distribution. This paper addresses whether quantum examples can fundamentally reduce the sample complexity required for learning in these general settings.

Methods

The authors employ two main proof strategies:

  1. Information-Theoretic Argument: This approach uses a clever argument based on information theory to establish lower bounds on sample complexity. It quantifies how much information a learner can extract from a given number of examples. For quantum examples, this involves analyzing the information content of quantum states. This method yields bounds that are close to optimal but include a logarithmic factor.
  2. State-Identification Argument: This more advanced technique frames the learning problem as a quantum state identification task. The learner is given multiple copies of a quantum state representing a concept and must identify which concept it is. The authors leverage the "Pretty Good Measurement" (PGM), a well-established tool for state identification, and analyze its performance. By connecting the PGM's success probability to the learning problem, they derive tighter lower bounds that eliminate the logarithmic factor, matching the classical bounds.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • No General Quantum Speedup in Sample Complexity: The most significant finding is that quantum examples do not offer a general advantage in sample complexity for PAC and agnostic learning. This challenges the intuition that quantum computation always leads to speedups.
  • VC Dimension Reigns Supreme: The VC dimension of a concept class remains the dominant factor determining sample complexity, even when using quantum examples in these general learning models.
  • The Power of the Pretty Good Measurement: The PGM, a standard tool in quantum information theory, proves to be a powerful analytical tool for deriving tight lower bounds in quantum learning. Its analysis reveals limitations on how much information can be extracted from quantum examples.
  • Bridging Classical and Quantum Bounds: The paper successfully shows that the well-established classical lower bounds for PAC and agnostic learning also apply to the quantum setting, up to constant factors.

Key Results

  • PAC Learning: The authors prove that the sample complexity for quantum PAC learning is $\Omega\left(\frac{d}{\epsilon} + \frac{\log(1/\delta)}{\epsilon}\right)$, matching the optimal classical bound. This is achieved by removing a logarithmic factor present in previous quantum lower bounds.
  • Agnostic Learning: Similarly, for quantum agnostic learning, they establish a lower bound of $\Omega\left(\frac{d}{\epsilon^2} + \frac{\log(1/\delta)}{\epsilon^2}\right)$, also matching the optimal classical bound.
  • Random Classification Noise: The paper extends these results to the case of learning under random classification noise, showing that quantum examples still do not offer a significant advantage in sample complexity.

Limitations and Future Work

The authors acknowledge that their results focus on "passive" learning (where examples are given upfront) and do not preclude quantum advantages in "active" learning settings (where the learner can query for specific examples). They also highlight several open questions:

  • Other Noise Models: Investigating sample complexity for quantum learning under more adversarial noise models.
  • Quantum Proper PAC Learning: Determining if the $\log(1/\delta)$ factor can be removed for proper PAC learning (where the hypothesis must be from the concept class itself).
  • Fixed-Distribution Speedups: Exploring if quantum examples can offer significant speedups in sample complexity for learning under specific, non-uniform distributions.
  • Quantum Speedups in Time Complexity: Investigating further examples of quantum speedups in the time complexity of learning, particularly for specific circuit classes.
  • Learning Non-Binary Concepts: Extending the analysis to learning concepts with ranges beyond $\{0,1\}$.

Summary updated

Abstract

In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its “richness.” A fundamental result says that the number of examples needed to learn an unknown target concept $c\in C$ under an unknown distribution $D$, is tightly determined by the VC dimension $d$ of the concept class $C$. Specifically, in the PAC model $$ \Theta\Big(\frac{d}{\epsilon} + \frac{\log(1/\delta)}{\epsilon}\Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-\delta$, a hypothesis $h$ that is $\epsilon$-close to the target concept $c$ (measured under $D$). In the related agnostic model, where the samples need not come from a $c\in C$, we know that $$ \Theta\Big(\frac{d}{\epsilon^2} + \frac{\log(1/\delta)}{\epsilon^2}\Big) $$ examples are necessary and sufficient to output an hypothesis $h\in C$ whose error is at most $\epsilon$ worse than the error of the best concept in $C$. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atıcı and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is $$ \Omega\Big(\frac{d^{1-\eta}}{\epsilon} + d + \frac{\log(1/\delta)}{\epsilon}\Big)\mbox{ for arbitrarily small constant }\eta>0. $$ Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a $\log(d/\epsilon)$ factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the “Pretty Good Measurement” on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class $C$.
BibTeX
@article{arunachalam2018optimal,
  author = {Srinivasan Arunachalam and Ronald de Wolf},
  title = {{Optimal Quantum Sample Complexity of Learning Algorithms.}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=FFsEaQxSfoD},
}
Figure