Neural networks have been widely used in machine learning and artificial intelligence, but the theoretical understanding of neural network learning has lagged its practical successes. In this talk, we study several provable algorithms for learning multi-layer and fully connected neural networks for binary classification.

We make two critical assumptions on the class of neural networks to be learnt. First, we assume that the L1-norm of the incoming weights of any neuron is bounded by a constant. Second, we assume that there is an oracle neural network which separates all positive and negative examples by a constant margin. Under these assumptions, we present an efficient algorithm which learns a neural network with arbitrarily small generalization error $\epsilon > 0$. The algorithm’s sample complexity and time complexity have polynomial dependence on the input dimension and on $1/\epsilon$. We also present a kernel-based improper learning algorithm which achieves the same learnability result, but not relying on the separability assumption. Experiments on synthetic and real datasets demonstrate that the proposed algorithms are not only understandable in theory, but also useful in practice.