Abstract
Despite decades of intensive research, efficient  or even subexponential time  distributionfree 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 uniformdistribution learning results gives nontrivial distributionfree learning algorithms for several wellstudied 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 distributionfree learning algorithms that do not appear to be achievable by approach (1) above. The results achieved in this way include learning algorithms with nontrivial savings for LTFofAC0 circuits and improved savings for learning parityofAC0 circuits.
(3) Finally, our third contribution is a generic technique for converting lower bounds proved using Neciporuk's method to learning algorithms with nontrivial savings. This technique, which is the most involved of our three approaches, yields distributionfree learning algorithms for a range of classes where previously even nontrivial uniformdistribution learning algorithms were not known; these classes include fullbasis formulas, branching programs, span programs, etc. up to some fixed polynomial size.
BibTeX  Entry
@InProceedings{servedio_et_al:LIPIcs:2017:8172,
author = {Rocco A. Servedio and LiYang Tan},
title = {{What Circuit Classes Can Be Learned with NonTrivial Savingsl}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {30:130:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8172},
URN = {urn:nbn:de:0030drops81722},
doi = {10.4230/LIPIcs.ITCS.2017.30},
annote = {Keywords: computational learning theory, circuit complexity, nontrivial savings}
}
Keywords: 

computational learning theory, circuit complexity, nontrivial savings 
Collection: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

28.11.2017 