Learning Halfspaces and Neural Networks with Random Initialization

Abstract

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 $\epsilon >0$. The time complexity is polynomial in the input dimension $d$ and the sample size $n$, but exponential in the quantity $(L/{\epsilon }^2)\log (L/\epsilon )$. 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 $\gamma >0$, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin $\Omega (\gamma )$. As a consequence, the algorithm achieves arbitrary generalization error $\epsilon >0$ with $\mathrm{poly}(d,1/\epsilon )$ sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability $\eta <1/2$.

31 pages

References in corpus (4)

• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Norm-Based Capacity Control in Neural Networks
• Sparse Activity and Sparse Connectivity in Supervised Learning
• Efficient Learning of Linear Separators under Bounded Noise

Cited by in corpus (15)

• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Robust Large Margin Deep Neural Networks
• Escaping Saddles with Stochastic Gradients
• Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks
• Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization
• Distribution-Specific Hardness of Learning Neural Networks
• Convexified Convolutional Neural Networks
• A Provably Correct Algorithm for Deep Learning that Actually Works
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ${\ell }^1$ and ${\ell }^0$ Controls
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
• On the Learnability of Deep Random Networks
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Learning Graph Neural Networks with Approximate Gradient Descent
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations