The Power of Random Features and the Limits of Distribution-Free Gradient Descent

Recently, a spate of papers have provided positive theoretical results for training over-parameterized neural networks (where the network size is larger than what is needed to achieve low error). The key insight is that with sufficient overparameterization, gradient-based methods will implicitly leave some components of the network relatively unchanged, so the optimization dynamics will behave as if those components are essentially fixed at their initial random values. In fact, fixing these explicitly leads to the well-known approach of learning with random features (e.g. [27, 29] ). In other words, these techniques imply that we can successfully learn with neural networks, whenever we can successfully learn with random features. In this paper, we formalize the link between existing results and random features, and argue that despite the impressive positive results, random feature approaches are also inherently limited in what they can explain. In particular, we prove that random features cannot be used to learn even a single ReLU neuron (over standard Gaussian inputs in R d and poly(d) weights), unless the network size (or magnitude of its weights) is exponentially large in d. Since a single neuron is known to be learnable with gradient-based methods, we conclude that we are still far from a satisfying general explanation for the empirical success of neural networks. For completeness we also provide a simple self-contained proof, using a random features technique, that one-hidden-layer neural networks can learn low-degree polynomials. Recently, a spate of papers (such as [4, 11, 14, 2, 23, 15, 9, 3, 1]) provided positive results for training and learning with over-parameterized neural networks. Although they differ in details, they are all based on the following striking observation: When the networks are sufficiently large, standard 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada.