What Circuit Classes Can Be Learned with Non-Trivial Savings?
What Circuit Classes Can Be Learned with Non-Trivial Savings?
复制标题
学习哪些电路课程可以节省不少费用？
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
R. Servedio;Li
尽管经过了几十年的深入研究，对于许多重要的布尔函数类来说，有效的甚至是次指数时间无分布的PAC学习算法还不为人所知。在这项工作中，我们提出了一个关于这些学习问题的新视角，受到最近复杂性理论研究的启发，其目标是确定是否以及在朴素的2^n运行时可以实现多少节省。
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.