On the Power and Limitations of Random Features for Understanding Neural Networks

Abstract

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 over-parameterization, 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. 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 first review these techniques, providing a simple and self-contained analysis for one-hidden-layer networks. We then argue that despite the impressive positive results, random feature approaches are also inherently limited in what they can explain. In particular, we rigorously show that random features cannot be used to learn even a single ReLU neuron with standard Gaussian inputs, unless the network size (or magnitude of the weights) is exponentially large. Since a single neuron is learnable with gradient-based methods, we conclude that we are still far from a satisfying general explanation for the empirical success of neural networks.

Comparison to previous version: Fixed a bug in Theorem 3.4 about approximating polynomials as an expectation of random features. Also added another assumption on the activaion function in theorem 3.1

References in corpus (6)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• On the Computational Efficiency of Training Neural Networks

Cited by in corpus (11)

• A Theoretical Analysis of Deep Q-Learning
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Limitations of Lazy Training of Two-layers Neural Networks
• Learning a Single Neuron with Gradient Methods
• Noether: The More Things Change, the More Stay the Same
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Learning time-scales in two-layers neural networks
• An Optimization and Generalization Analysis for Max-Pooling Networks
• Deep Networks Provably Classify Data on Curves
• ReLU Regression with Massart Noise