Learning Halfspaces and Neural Networks with Random Initialization

We study non-convex empirical risk minimization for learning halfspaces and neural networks. For loss functions that are L-Lipschitz continuous, we present algorithms to learn halfspaces and multi-layer neural networks that achieve arbitrarily small excess risk ε>0. The time complexity is polynomial in the input dimension d and the sample size n, but exponential in the quantity (L/ε2)log(L/ε). These algorithms run multiple rounds of random initialization followed by arbitrary optimization steps. We further show that if the data is separable by some neural network with constant margin γ>0, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin Omega(γ). As a consequence, the algorithm achieves arbitrary generalization error ε>0 with rm poly(d,1/ε) sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability η<1/2.