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

By Gilad Yehudai, Ohad Shamir. 2019

196 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

Citations in the corpus

When do neural networks outperform kernel methods? (2020, background): “target functions f∗ that can be represented and possibly efficiently learnt using neural networks, but not in the corresponding RKHS [32, 6, 17, 16, 1, 2].”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “This is particularly important in light of a few recent literature [17, 23, 56] suggesting a significant gap between generalization capabilities of kernel methods/linearized neural nets when compared with neural nets operating beyond a linear or NTK learning regime (e.”
On Lazy Training in Differentiable Programming (2018, background): “In some of these references, the relevance of this regime to understand the good performance of neural networks is also questioned [43].”
Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks (2020, background): “However, this regime does not explain why NNs can effectively learn representative features, and the expressive power of random kernels is limited Yehudai & Shamir (2019).”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “Suzuki (2018); Allen-Zhu and Li (2019); Yehudai and Shamir (2019) demonstrated that neural network outperforms linear estimators (including kernel methods) in learning various target functions.”
Dynamics of Deep Neural Networks and Neural Tangent Hierarchy (2019, unknown): “It has been constructed in [1,17,46] that there are simple functions that can be eﬃciently learnt by ﬁnite width neural networks, but not the kernel regression using the limiting NTK.”
A Theoretical Analysis of Deep Q-Learning (2019, background): “eep learning (Du et al., 2019b,a; 10 Zou et al., 2018; Chizat et al., 2019; Allen-Zhu et al., 2019a,b; Jacot et al., 2018; Cao and Gu, 2019; Arora et al., 2019; Weinan et al., 2019; Mei et al., 2019; Yehudai and Shamir, 2019) has established global convergence of gradient-based algorithms for empiri”
Limitations of Lazy Training of Two-layers Neural Networks (2019, background): “A specific counterexample is given in [25]: if the function to be learnt is a single neuron f∗(x) = σ(〈w∗,x〉) then gradient descent (in the space of neural networks with N = 1 neurons) efficiently learns it [20]; on the other hand, RF or NT require a number of neurons exponential in the dimension to”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “For such reason, it is not surprising that most existing theoretical works on the efficient learning regime of neural networks either focus on (1) two-layer networks [9, 10, 12, 22, 23, 36, 41, 41, 42, 46, 50, 51, 53, 54, 56, 58, 61] which do not have any hierarchical structure, or (2) a multi-layer”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, background): “…Many recent works leveraged arguments based on random features to explain the empirical success of local descent algorithms to train neural networks (see e.g. (Jacot et al., 2018; Allen-Zhu et al., 2018; Oymak and Soltanolkotabi, 2019; Yehudai and Shamir, 2019; Ma et al., 2019; Du et al., 2018)).”
Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks (2019, methodology): “Compared with recent results by Yehudai and Shamir [37], E et al.”
Proving the Lottery Ticket Hypothesis: Pruning is All You Need (2020, background): “A few recent works (e.g. [36], [12], [11]) studied the limitations of random features.”
On Learning Over-parameterized Neural Networks: A Functional Approximation Prospective (2019, background): “Recently, a handful of work studied linearized neural networks in high dimen-sion [GMMM19, YS19, VW18].”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “Yehudai and Shamir [73] also prove a lower bound on the learnability of neural net kernels.”
Training BatchNorm and Only BatchNorm: On the Expressive Power of Random Features in CNNs (2020, methodology): “…overparameterized networks, recent work has used two layer models in which the ﬁrst layer is sufﬁciently wide that it changes little during training (e.g., Du et al., 2019); in the limit, these networks may be modeled with the ﬁrst layer frozen at its random initialization (Yehudai & Shamir, 2019).”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, background): “Consider the ReLU random feature kernel and let H K denote the RKHS associated with this kernel.”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “…(2016); Soltanolkotabi et al. (2017); Tian (2017); Brutzkus and Globerson (2017); Boob and Lan (2017); Vempala and Wilmes (2018); Oymak and Soltanolkotabi (2019); Bakshi et al. (2018); Yehudai and Shamir (2019); Zhang et al. (2018); Li and Liang (2017); Li and Dou (2020); Allen-Zhu and Li (2020b).”