[edit]
PAC Learning Depth-3 AC0 Circuits of Bounded Top Fanin
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:667-680, 2017.
Abstract
An important and long-standing question in computational learning theory is how to learn AC0 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. \newline In this paper we present an algorithm to PAC learn depth-3 AC0 circuits of bounded top fanin over (x1,⋯,xn,¯x1,⋯,¯xn). Our result is that every depth-3 AC0 circuit of top fanin K can be computed by a polynomial threshold function (PTF) of degree ˜O(K⋅n12), which means that it can be PAC learned in time 2˜O(K⋅n12). In particular, when K=O(nϵ0) for any ϵ0<12, the time for learning is sub-exponential. We note that instead of employing some known tools we use some specific approximation in expressing such circuits in PTFs which can thus save a factor of polylog(n) in degrees of the PTFs.