Document Open Access Logo

What Circuit Classes Can Be Learned with Non-Trivial Savings?

Authors Rocco A. Servedio, Li-Yang Tan

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2017.30.pdf
  • Filesize: 0.63 MB
  • 21 pages

Document Identifiers

Subject Classification

Keywords
  • computational learning theory
  • circuit complexity
  • non-trivial savings

Metrics

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

Abstract

Despite decades of intensive research, efficient - or even sub-exponential time - distribution-free PAC learning algorithms are not known for many important Boolean function classes. In this work we suggest a new perspective on these learning problems, inspired by a surge of recent research in complexity theory, in which the goal is to determine whether and how much of a savings over a naive 2^n runtime can be achieved.

We establish a range of exploratory results towards this end. In more detail, 

(1)  We first observe that a simple approach building on known uniform-distribution learning results gives non-trivial distribution-free learning algorithms for several well-studied classes including AC0, arbitrary functions of a few linear threshold functions (LTFs), and AC0 augmented with mod_p gates.

(2) Next we present an approach, based on the method of random restrictions from circuit complexity, which can be used to obtain several distribution-free learning algorithms that do not appear to be achievable by approach (1) above.  The results achieved in this way include learning algorithms with non-trivial savings for LTF-of-AC0 circuits and improved savings for learning parity-of-AC0 circuits. 

(3) Finally, our third contribution is a generic technique for converting lower bounds proved using Neciporuk's method to learning algorithms with non-trivial savings. This technique, which is the most involved of our three approaches, yields distribution-free learning algorithms for a range of classes where previously even non-trivial uniform-distribution learning algorithms were not known; these classes include full-basis formulas, branching programs, span programs, etc. up to some fixed polynomial size.

Cite As Get BibTex

Rocco A. Servedio and Li-Yang Tan. What Circuit Classes Can Be Learned with Non-Trivial Savings?. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.30

Author Details

Rocco A. Servedio
Li-Yang Tan

References

  1. D. Angluin. Learning Regular Sets from Queries and Counterexamples. Information and Computation, 75(2):87-106, 1987. Google Scholar
  2. D. Angluin. Queries and concept learning. Machine Learning, 2:319-342, 1988. Google Scholar
  3. Ya M Barzdin and RV Freivald. Prediction of general recursive functions. Doklady Akademii Nauk SSSR, 206(3):521, 1972. Google Scholar
  4. P. Beame, R. Impagliazzo, and S. Srinivasan. Approximating AC⁰ by Small Height Decision Trees and a Deterministic Algorithm for #AC⁰-SAT. In CCC, pages 117-125, 2012. Google Scholar
  5. R. Beigel. The polynomial method in circuit complexity. In Proceedings of the Eigth Conference on Structure in Complexity Theory, pages 82-95, 1993. Google Scholar
  6. A. Beimel, F. Bergadano, N. Bshouty, E. Kushilevitz, and S. Varricchio. On the applications of multiplicity automata in learning. In Proceedings of the Thirty-Seventh Annual Symposium on Foundations of Computer Science, pages 349-358, 1996. Google Scholar
  7. Andreas Björklund. Counting perfect matchings as fast as Ryser. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 914-921, 2012. Google Scholar
  8. Avrim Blum. Separating distribution-free and mistake-bound learning models over the boolean domain. SIAM J. Comput., 23(5):990-1000, 1994. Google Scholar
  9. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, 1989. Google Scholar
  10. N. Bshouty. Exact learning via the monotone theory. Information and Computation, 123(1):146-153, 1995. Google Scholar
  11. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/http://dx.doi.org/10.4230/LIPIcs.CCC.2016.10.
  12. Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman. Mining circuit lower bound proofs for meta-algorithms. Computational Complexity, 24(2):333-392, 2015. Google Scholar
  13. P. Fischer and H. Simon. On learning ring-sum expansions. SIAM Journal on Computing, 21(1):181-192, 1992. Google Scholar
  14. Fedor V Fomin and Dieter Kratsch. Exact exponential algorithms. Springer Science &Business Media, 2010. Google Scholar
  15. P. Gopalan and R. Servedio. Learning and lower bounds for AC⁰ with threshold gates. In Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM), pages 588-601, 2010. Google Scholar
  16. Parikshit Gopalan, Adam R. Klivans, and Raghu Meka. Learning functions of halfspaces using prefix covers. Journal of Machine Learning Research - Proceedings Track, 23:15.1-15.10, 2012. Google Scholar
  17. Johan Håstad. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA, 1986. Google Scholar
  18. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing, 43(5):1699-1708, 2014. Google Scholar
  19. L. Hellerstein and R. Servedio. On PAC learning algorithms for rich boolean function classes. Theoretical Computer Science, 384(1):66-76, 2007. Google Scholar
  20. D. Helmbold, R. Sloan, and M. Warmuth. Learning integer lattices. SIAM Journal on Computing, 21(2):240-266, 1992. Google Scholar
  21. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC⁰. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 961-972, 2012. Google Scholar
  22. Taisuke Izumi and Tadashi Wadayama. A new direction for counting perfect matchings. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 591-598, 2012. Google Scholar
  23. Stasys Jukna. Boolean Function Complexity. Springer, 2012. Google Scholar
  24. Daniel M. Kane. The correct exponent for the gotsman-linial conjecture. In Proc. 28th Annual IEEE Conference on Computational Complexity (CCC), 2013. Google Scholar
  25. M. Karchmer and A. Wigderson. On span programs. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993), pages 102-111. IEEE Comput. Soc. Press, Los Alamitos, CA, 1993. URL: http://dx.doi.org/10.1109/SCT.1993.336536.
  26. A. Klivans, R. O'Donnell, and R. Servedio. Learning intersections and thresholds of halfspaces. Journal of Computer &System Sciences, 68(4):808-840, 2004. Google Scholar
  27. A. Klivans and R. Servedio. Learning DNF in time 2^Õ(n^1/3). Journal of Computer &System Sciences, 68(2):303-318, 2004. Google Scholar
  28. Adam Klivans, Pravesh Kothari, and Igor Carboni Oliveira. Constructing hard functions using learning algorithms. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, pages 86-97, 2013. Google Scholar
  29. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM, 40(3):607-620, 1993. Google Scholar
  30. N. Littlestone. Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm. Machine Learning, 2:285-318, 1988. Google Scholar
  31. W. Maass and G. Turan. How fast can a threshold gate learn? In Computational Learning Theory and Natural Learning Systems: Volume I: Constraints and Prospects, pages 381-414. MIT Press, 1994. Google Scholar
  32. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. J. ACM, 52(3):337-364 (electronic), 2005. URL: http://dx.doi.org/10.1145/1066100.1066101.
  33. Ramamohan Paturi, Pavel Pudlák, and Francis Zane. Satisfiability coding lemma. Chicago J. Theoret. Comput. Sci., pages Article 11, 19 pp. (electronic), 1999. Google Scholar
  34. Pavel Pudlák. The hierarchy of boolean circuits. Computers and artificial intelligence, 6(5):449-468, 1987. Google Scholar
  35. A. Razborov. Lower bounds on the monotone complexity of some boolean functions. Dokl. Akad. Nauk SSSR, 281:798-801, 1985. English translation in: Soviet Math. Dokl. 31:354-357, 1985. Google Scholar
  36. Alexander A. Razborov. On the method of approximations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 167-176, 1989. Google Scholar
  37. Ben W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560-569. SIAM, Philadelphia, PA, 2011. Google Scholar
  38. R. Rivest. Learning decision lists. Machine Learning, 2(3):229-246, 1987. Google Scholar
  39. T Schoning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 410-414. IEEE, 1999. Google Scholar
  40. Rainer Schuler. An algorithm for the satisfiability problem of formulas in conjunctive normal form. J. Algorithms, 54(1):40-44, 2005. Google Scholar
  41. A. Tal. Tight Bounds on The Fourier Spectrum of AC⁰. ECCC report TR14-174 Revision #1, 2015. URL: http://eccc.hpi-web.de/report/2014/174/.
  42. L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984. Google Scholar
  43. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 231-240. ACM, New York, 2010. Google Scholar
  44. Ryan Williams. Non-uniform ACC circuit lower bounds. In 26th Annual IEEE Conference on Computational Complexity, pages 115-125. IEEE Computer Soc., Los Alamitos, CA, 2011. Google Scholar
  45. Virginia V. Williams. Hardness of easy problems: basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis. In 10th International Symposium on Parameterized and Exact Computation, volume 43 of LIPIcs. Leibniz Int. Proc. Inform., pages 17-29. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact