Document Open Access Logo

Optimal Quantum Sample Complexity of Learning Algorithms

Authors Srinivasan Arunachalam, Ronald de Wolf

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.25.pdf
  • Filesize: 0.65 MB
  • 31 pages

Document Identifiers

Author Details

Srinivasan Arunachalam
Ronald de Wolf

Cite As Get BibTex

Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 25:1-25:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.25

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(d/eps + log(1/delta)/eps)

examples are necessary and sufficient for a learner to output, with probability 1-delta, a hypothesis h that is eps-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(d/eps^2 + log(1/delta)/eps^2)

examples are necessary and sufficient to output an hypothesis h in C whose error is at most eps 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, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, 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(d^{1-eta}/eps + d + log(1/delta)/eps) 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/eps) 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.

Subject Classification

Keywords
  • Quantum computing
  • PAC learning
  • agnostic learning
  • VC dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aaronson. The learnability of quantum states. Proceedings of the Royal Society of London, 463(2088), 2007. quant-ph/0608142. Google Scholar
  2. S. Aaronson. Quantum machine learning algorithms: Read the fine print. Nature Physics, 11(4):291-293, April 2015. Google Scholar
  3. E. Aïmeur, G. Brassard, and S. Gambs. Machine learning in a quantum world. In Proceedings of Advances in Artificial Intelligence, 19th Conference of the Canadian Society for Computational Studies of Intelligence, volume 4013 of Lecture Notes in Artificial Intelligence, pages 431-442, 2006. Google Scholar
  4. E. Aïmeur, G. Brassard, and S. Gambs. Quantum speed-up for unsupervised learning. Machine Learning, 90(2):261-287, 2013. Google Scholar
  5. A. Ambainis and A. Montanaro. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information & Computation, 14(5-6):439-453, 2014. arXiv:1210.1148. Google Scholar
  6. D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2(4):343-370, 1988. Google Scholar
  7. M. Anthony and P. L. Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009. Google Scholar
  8. B. Apolloni and C. Gentile. Sample size lower bounds in PAC learning by algorithmic complexity theory. Theoretical Computer Science, 209:141-162, 1998. Google Scholar
  9. S. Arunachalam and R. de Wolf. A survey of quantum learning theory, 2017. To appear as Computational Complexity Column in SIGACT News, June 2017. Preprint at arxiv:1606.08920. Google Scholar
  10. A. At\ic\i and R. Servedio. Improved bounds on quantum learning algorithms. Quantum Information Processing, 4(5):355-386, 2005. quant-ph/0411140. Google Scholar
  11. A. At\ic\i and R. Servedio. Quantum algorithms for learning and testing juntas. Quantum Information Processing, 6(5):323-348, 2009. arXiv:0707.3479. Google Scholar
  12. J. Audibert. Fast learning rates in statistical inference through aggregation, 2008. Research Report 06-20, Certis - Ecole des Ponts. math/0703854. Google Scholar
  13. J. Audibert. Fast learning rates in statistical inference through aggregation. The Annals of Statistics, 37(4):1591-1646, 2009. arXiv:0909.1468v1. Google Scholar
  14. D. Bacon, A. Childs, and W. van Dam. Optimal measurements for the dihedral hidden subgroup problem. Chicago Journal of Theoretical Computer Science, 2006. Earlier version in FOCS'05. quant-ph/0504083. Google Scholar
  15. H. Barnum and E. Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics, 43:2097-2106, 2002. quant-ph/0004088. Google Scholar
  16. E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. Earlier version in STOC'93. Google Scholar
  17. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, 1989. Google Scholar
  18. N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing, 28(3):1136-1153, 1999. Earlier version in COLT'95. Google Scholar
  19. H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16), 2001. quant-ph/0102001. Google Scholar
  20. A. Daniely and S. Shalev-Shwartz. Complexity theoretic limitations on learning DNF’s. In Proceedings of the 29th Conference on Learning Theory (COLT'16), 2016. Google Scholar
  21. A. Ehrenfeucht, D. Haussler, M. J. Kearns, and L. G. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-261, 1989. Earlier version in COLT'98. Google Scholar
  22. Y. C. Eldar and G. D. Forney Jr. On quantum detection and the square-root measurement. IEEE Transactions and Information Theory, 47(3):858-872, 2001. quant-ph/0005132. Google Scholar
  23. Y. C. Eldar, A. Megretski, and G. C. Verghese. Designing optimal quantum detectors via semidefinite programming. IEEE Transactions Information Theory, 49(4):1007-1012, 2003. quant-ph/0205178. Google Scholar
  24. D. Gavinsky. Quantum predictive learning and communication complexity with single input. Quantum Information and Computation, 12(7-8):575-588, 2012. Earlier version in COLT'10. arXiv:0812.3429. Google Scholar
  25. C. Gentile and D. P. Helmbold. Improved lower bounds for learning from noisy examples: An information-theoretic approach. Information and Computation, 166:133-155, 2001. Google Scholar
  26. L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212-219, 1996. quant-ph/9605043. Google Scholar
  27. S. Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1-15, 2016. arXiv:1507.00473. Google Scholar
  28. A. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 103(15):150502, 2009. arXiv:0811.3171. Google Scholar
  29. P. Hausladen, R. Jozsa, B. Schumacher, M. Westmoreland, and W. K. Wootters. Classical information capacity of a quantum channel. Physical Review A, 54:1869-1876, 1996. Google Scholar
  30. P. Hausladen and W. K. Wootters. A ‘pretty good’ measurement for distinguishing quantum states. Journal of Modern Optics, 41:2385-2390, 1994. Google Scholar
  31. D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-150, 1992. Google Scholar
  32. M. Hunziker, D. A. Meyer, J. Park, J. Pommersheim, and M. Rothstein. The geometry of quantum learning. Quantum Information Processing, 9(3):321-341, 2010. quant-ph/0309059. Google Scholar
  33. J. C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414-440, 1997. Earlier version in FOCS'94. Google Scholar
  34. J. C. Jackson, C. Tamon, and T. Yamakami. Quantum DNF learnability revisited. In Proceedings of 8th COCOON, pages 595-604, 2002. quant-ph/0202066. Google Scholar
  35. R. Jain and S. Zhang. New bounds on classical and quantum one-way communication complexity. Theoretical Computer Science, 410(26):2463-2477, 2009. arXiv:0802.4101. Google Scholar
  36. M. J. Kearns, R. E. Schapire, and L. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):115-141, 1994. Earlier version in COLT'92. Google Scholar
  37. M. J. Kearns and L. G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1):67-95, 1994. Google Scholar
  38. M. J. Kearns and U. V. Vazirani. An introduction to computational learning theory. MIT Press, 1994. Google Scholar
  39. A. Kontorovich and I. Pinelis. Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model, 2016. Preprint at arxiv:1606.08920. Google Scholar
  40. R. Kothari. An optimal quantum algorithm for the oracle identification problem. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pages 482-493, 2014. arXiv:1311.7685. Google Scholar
  41. A. Montanaro. On the distinguishability of random quantum states. Communications in Mathematical Physics, 273(3):619-636, 2007. quant-ph/0607011. Google Scholar
  42. A. Montanaro. The quantum query complexity of learning multilinear polynomials. Information Processing Letters, 112(11):438-442, 2012. arXiv:1105.3310. Google Scholar
  43. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  44. R. Servedio and S. Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067-1092, 2004. Combines earlier papers from ICALP'01 and CCC'01. quant-ph/0007036. Google Scholar
  45. S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. Google Scholar
  46. H. U. Simon. General bounds on the number of examples needed for learning probabilistic concepts. Journal of Computer and System Sciences, 52(2):239-254, 1996. Earlier version in COLT'93. Google Scholar
  47. H. U. Simon. An almost optimal PAC algorithm. In Proceedings of the 28th Conference on Learning Theory (COLT), pages 1552-1563, 2015. Google Scholar
  48. M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28-76, 1994. Google Scholar
  49. L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984. Google Scholar
  50. V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability &Its Applications, 16(2):264-280, 1971. Google Scholar
  51. V. N. Vapnik and A. Ya. Chervonenkis. Theory of Pattern Recognition. Nauka, 1974. In Russian. Google Scholar
  52. K. A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory (COLT'90), pages 314-326, 1990. Google Scholar
  53. N. Wiebe, A. Kapoor, and K. M. Svore. Quantum deep learning, 2014. Preprint at arXiv:1412.3489. Google Scholar
  54. N. Wiebe, A. Kapoor, and K. M. Svore. Quantum perceptron models, 2016. Preprint at arXiv:1602.04799. Google Scholar
  55. C. Zhang. An improved lower bound on query complexity for quantum PAC learning. Information Processing Letters, 111(1):40-45, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact