2026-07-22T21:50:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8172 2024-03-06T10:39:19Z ddc:004 open_access

What Circuit Classes Can Be Learned with Non-Trivial Savings? Servedio, Rocco A. Tan, Li-Yang computational learning theory circuit complexity non-trivial savings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rocco A. Servedio and Li-Yang Tan 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.30 urn:nbn:de:0030-drops-81722 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.30 eng https://creativecommons.org/licenses/by/3.0/legalcode