PAC Learning Depth-3 $extrm{AC}^0$ Circuits of Bounded Top Fanin

摘要

An important and long-standing question in computational learning theory is how to learn $extrm{AC}^0$ circuits with respect to any distribution (i.e. PAC learning). All previous results either require that the underlying distribution is uniform Linial et al. (1993) (or simple variants of the uniform distribution) or restrict the depths of circuits being learned to 1 Valiant (1984) and 2 Klivans and Servedio (2004). As for the circuits of depth 3 or more, it is currently unknown how to PAC learn them. ewline In this paper we present an algorithm to PAC learn depth-3 $extrm{AC}^0$ circuits of bounded top fanin over $(x_1,cdots,x_n,overline{x}_1,cdots,overline{x}_n)$. Our result is that every depth-3 $extrm{AC}^0$ circuit of top fanin $K$ can be computed by a polynomial threshold function (PTF) of degree $widetilde{O}(Kcdot n^{rac{1}{2}})$, which means that it can be PAC learned in time $2^{widetilde{O}(Kcdot n^{rac{1}{2}})}$. In particular, when $K=O(n^{epsilon_0})$ for any $epsilon_0