Poster
On the Power and Limitations of Random Features for Understanding Neural Networks
Gilad Yehudai · Ohad Shamir
Recently, a spate of papers have provided positive theoretical results for training overparameterized neural networks (where the network size is larger than what is needed to achieve low error). The key insight is that with sufficient overparameterization, gradientbased 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 \emph{explicitly} leads to the wellknown approach of learning with random features (e.g. \citep{rahimi2008random,rahimi2009weighted}). 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 \emph{even a single ReLU neuron} (over standard Gaussian inputs in $\reals^d$ and $\text{poly}(d)$ weights), unless the network size (or magnitude of its weights) is exponentially large in $d$. Since a single neuron \emph{is} known to be learnable with gradientbased 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 selfcontained proof, using a random features technique, that onehiddenlayer neural networks can learn lowdegree polynomials.
Author Information
Gilad Yehudai (Weizmann Institute of Science)
Ohad Shamir (Weizmann Institute of Science)
More from the Same Authors

2018 Poster: Are ResNets Provably Better than Linear Predictors? »
Ohad Shamir 
2018 Poster: Global Nonconvex Optimization with Discretized Diffusions »
Murat Erdogdu · Lester Mackey · Ohad Shamir 
2016 Poster: DimensionFree Iteration Complexity of Finite Sum Optimization Problems »
Yossi Arjevani · Ohad Shamir 
2016 Poster: WithoutReplacement Sampling for Stochastic Gradient Methods »
Ohad Shamir 
2016 Oral: WithoutReplacement Sampling for Stochastic Gradient Methods »
Ohad Shamir 
2015 Poster: Communication Complexity of Distributed Convex Learning and Optimization »
Yossi Arjevani · Ohad Shamir 
2014 Poster: Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation »
Ohad Shamir 
2014 Poster: On the Computational Efficiency of Training Neural Networks »
Roi Livni · Shai ShalevShwartz · Ohad Shamir 
2013 Poster: Online Learning with Switching Costs and Other Adaptive Adversaries »
NicolĂ˛ CesaBianchi · Ofer Dekel · Ohad Shamir