Provable Algorithms for Learning Neural Networks

  • Yuchen Zhang | University of California, Berkeley

We study the learning of fully connected neural networks for binary classification. For the networks of interest, we assume that the L1-norm of the incoming weights of any neuron is bounded by a constant. We further assume that there exists a neural network which separates the positive and negative samples by a constant margin. Under these assumptions, we present an efficient algorithm which learns a neural network with arbitrary generalization error ε>0. The algorithm’s sample complexity and time complexity are polynomial in the input dimension and in 1/ε. 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.

Speaker Details

Yuchen Zhang is a Ph.D. candidate in computer science at University of California, Berkeley. His research interests span machine learning, optimization and statistics. At Berkeley, he works in the AMP Lab under the joint supervision of Michael I. Jordan and Martin J. Wainwright. He obtained his MA in statistics from Berkeley and received a BS in computer science from Tsinghua University

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks