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

Gilad Yehudai; Ohad Shamir

Source-linked AI summary

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

Gilad Yehudai, Ohad Shamir

arXiv:1904.00687v4Apr 1, 2019cs.LGcs.NEstat.ML

TL;DR

The paper asks whether random-feature explanations account for the learnability of neural networks. It reviews their connection to over-parameterized training and proves that learning even one ReLU neuron can require exponential resources, leaving the general explanation incomplete.

Problem
Theoretical understanding of neural networks remains incomplete, including whether random features explain the learnability produced by over-parameterized training.
Method
The paper reviews over-parameterized one-hidden-layer training and analyzes arbitrary fixed random features for learning targets under standard Gaussian inputs.
Results
Random features cannot efficiently approximate a suitably chosen single ReLU neuron unless the feature count or weight magnitude is exponential in dimension d.
Takeaways & Limitations
Random features capture important aspects of neural-network training but cannot by themselves provide a satisfying general explanation for empirical neural-network success.

Abstract

from arXiv · show

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.

1 Introduction

The paper connects over-parameterized neural-network training to random features, then shows that this framework cannot explain learning even a single ReLU neuron without exponential resources.

Connection to random features: Over-parameterized networks can leave some first-layer weights nearly unchanged, making gradient descent resemble learning linear predictors over fixed random features.This connection is presented for one-hidden-layer networks with sufficiently large width and standard random initialization.
Conclusion: Overall, random features capture important aspects of neural-network training but omit representation learning and are not a complete explanation of empirical success.The paper frames its analysis as progress toward, rather than a general resolution of, the theory of neural networks.
Limitations: The paper proves that random features cannot efficiently approximate a suitably chosen single ReLU neuron under standard Gaussian inputs.The target can use a weight vector with norm d^2, and the result applies broadly to arbitrary fixed-distribution features with non-exponential norm.
Limitations: Either the number of features r or the weight magnitude must be exponential in dimension d, even though single ReLU neurons are easily learnable with gradient-based methods.This gap shows that random features cannot explain the learnability of even this simple neural-network target.
Positive analysis: The paper also gives a self-contained proof that stochastic gradient descent can learn bounded-degree, bounded-coefficient polynomials with over-parameterized one-hidden-layer networks.The required network size is exponential in the polynomial degree, so this positive result does not contradict the negative random-feature result.
Connection to random features: Random features train only the output weights over randomly chosen nonlinear functions, making the optimization problem as easy as training linear predictors.With enough features, this representation can express arbitrarily complex functions, but only within the fixed random feature span.

2 Analysis of Neural Networks as Random Features

The paper reviews two ways over-parameterized neural-network training can be analyzed as learning with random features: coupling with a fixed output layer, and keeping inner layers near initialization. Both reduce optimization to linear prediction over an obliviously chosen random representation, whose expressiveness is the central limitation.

2.1 Optimization with Coupling, Fixing the Output Layer: Coupling views a ReLU neuron as a linear predictor multiplied by a threshold, then tracks neurons whose activation signs change during training.The analysis relies on limited iterations and suitable learning rates to keep sign changes small.
2.1 Optimization with Coupling, Fixing the Output Layer: With a fixed output layer, ReLU homogeneity lets the trained network be analyzed as a linear predictor over features x ↦ x_j1⟨w_i^(0),x⟩≥0.The first-layer weights are treated as randomly initialized and effectively fixed.
2.2 Optimization on all the Layers: Optimizing all layers instead chooses a learning rate and iteration limit so the inner layers remain close to their initialization.The resulting analysis again reduces the network to a linear predictor over random features.
2.2 Optimization on all the Layers: The random-feature reduction applies beyond ReLU, but the key challenge is finding functions approximable with only polynomially many neurons.This expressiveness constraint is the common difficulty across both approaches.

3 Over-Parameterized Neural Networks Learn Polynomials

This section gives a self-contained analysis of one-hidden-layer networks trained by SGD and shows that, under analytic-activation assumptions, they can learn bounded-degree, bounded-coefficient polynomials. The proof reduces training to random features, approximates the target through feature expectations, and uses concentration to obtain a finite-feature network.

Main theorem: Theorem 3.1 shows that SGD learns every polynomial of degree at most k with coefficients bounded by α, under the theorem’s activation and initialization assumptions.With probability greater than 1−δ, some iteration t achieves E[L_D(W_t,U_t)] ≤ L_D(P(x)) + ϵ.
Interpretation: For a finite sample set, choosing D uniformly over the samples makes the theorem guarantee average loss close to the best bounded-degree, bounded-coefficient polynomial predictor.The expectation in the SGD guarantee is over the random training example selected at each iteration.
Proof strategy: The proof first shows that SGD keeps the inner weights near initialization, allowing analysis as a linear predictor over random features.An online-convex-optimization argument then bounds the loss relative to a sufficiently small-norm target output vector.
Random-feature approximation: A sufficiently large random-feature sample approximates an expectation of the form E_w[σ(⟨w,x⟩)g(w)], with concentration controlled by measure-concentration and Rademacher-complexity arguments.Theorem 3.3 states that random features concentrate around their expectation as the feature count increases.
Polynomial approximation: Analyticity enables a Taylor expansion, while finite weighted sums of Legendre polynomials construct g(w) so the expectation represents bounded-degree polynomials.Theorem 3.4 formalizes this approximation when the polynomial’s monomials occur with nonzero coefficients in the activation’s Taylor series.

4 Limitations of Random Features

The paper shows that random-feature predictors face inherent limits: approximating even simple linear or single-neuron targets can require exponentially large networks or weights under the stated settings.

4.2 Single ReLU neurons: For a single ReLU target with Gaussian inputs, either the number of features or coefficient magnitude must be exponential in d when target weights and bias are polynomially bounded.The theorem covers broad feature families with norms bounded by exp(c2d), and the construction includes random-linear-transformation features.
4.1 Warm up: Linear predictors: Ω(d) random features are required with high probability to approximate a unit-norm linear predictor under the warm-up setting.The lower bound follows because the target must lie near the random span of the feature vectors.
4.1 Warm up: Linear predictors: The linear lower bound arises because random features constrain predictors to an obliviously chosen random r-dimensional subspace, which is typically poorly aligned with the target vector.The target's component orthogonal to that subspace remains large when r is sufficiently small relative to d.
General limitations: Random features restrict learning to a fixed, randomly chosen representation, so their provable scope is limited to hypothesis classes learnable through that representation.This includes features produced by randomized linear transformations and encompasses one-hidden-layer and some multilayer networks.
4.3 General Features and Kernel Methods: The general random-feature result includes one-hidden-layer networks, multilayer neurons with randomized first-layer transformations, and kernel methods.The paper therefore rules out a broad fixed-feature explanation for efficiently learning single ReLU neurons in the worst case.
4.2 Single ReLU neurons: The nonlinear theorem retains a restriction on the maximum coefficient magnitude, and the authors conjecture that this dependence may be removable.They leave removal of this dependence to future work.

A.1 Optimization with Coupling

Prior analyses use fixed output-layer weights and optimize only ReLU activations, establishing bounds or optimization guarantees under varying data assumptions. This setup preserves expressive power for ReLU networks but differs from practice, where all layers are optimized.

Prior applications: Several works apply the subsection’s method to generalization bounds or optimization guarantees for ReLU networks.The cited results include separability-based bounds, polynomial-time convergence to empirical-risk minima, and guarantees with few distributional assumptions.
Shared restriction: All these analyses fix the output-layer weights and optimize only the ReLU activation components.This is the shared architectural restriction across the listed approaches.
Practical boundary: For ReLU networks, fixing the output layer does not change expressive power, but it may differ from practical optimization of all layers.The passage explicitly notes that optimization may not work as well when some layers are fixed.

A.2 Optimization on all the Layers

A second group of methods studies networks by optimizing across layers or using broader activation and architecture classes. Their guarantees rely on specialized settings or may concern empirical rather than population risk.

Optimization on all the layers: One approach approximates polynomials using complex-valued weights, exponential activation, and data uniform on the complex unit circle.The resulting optimization occurs over a nonstandard complex domain.
Optimization on all the layers: Conjugate-kernel methods extend generalization analyses to deeper networks and architectures beyond simple feed-forward models.The conjugate kernel is determined by the network’s activation and architecture.
Optimization on all the layers: Other work considers many activations and architectures, including ResNets and convolutional ResNets, but its empirical-risk bound does not imply a population-risk bound.The methods use the same assumptions as the cited ReLU analysis.

B Proofs from section 4

The section proves approximation and lower-bound results through Gaussian projection properties, periodic odd functions, least-squares geometry, concentration, and probabilistic selection of a target weight. These ingredients establish the stated propositions and theorem extensions.

Proofs from section 4: For standard Gaussian inputs, projecting onto any fixed weight direction yields a standard Gaussian variable, enabling the norm calculations used in the proofs.The argument also uses the corresponding fourth moment, which is 3.
Proofs from section 4: The linearized optimization problem reduces to least squares, whose minimum is characterized using the pseudoinverse and an SVD of the random feature matrix.The residual is expressed through the projection onto the matrix’s column space.
Proofs from section 4: Concentration on the unit sphere controls the norm of a diagonal projection matrix whose entries contain d−r ones and r zeros.Symmetry makes the transformed target weight uniformly distributed on the sphere, allowing Lipschitz concentration to be applied.
Proofs from section 4: The constructed function ψ is periodic and odd, with these properties established from its piecewise-linear behavior and symmetry.Its period is 4 on the relevant interval, and oddness extends through periodicity.
Proofs from section 4: The proof of Proposition 4.2 bounds the difference between a periodic extension and ψ outside the defining interval before combining the resulting terms.The argument uses Cauchy–Schwarz, a prior claim, and r=d.
Proofs from section 4: Theorem 4.2 samples target weights uniformly from a sphere, selects one with suitable expected behavior, and then applies Markov’s inequality to obtain a high-probability statement.The remaining argument follows Theorem 4.1 after fixing the selected target weight.

C Approximating Polynomials Using Expectation of Random Features

The section constructs polynomial approximations using multivariate Legendre polynomials and change-of-basis operators. Orthogonality determines coefficients, while coefficient and supremum-norm bounds yield the theorem’s two stated conclusions.

Basis construction: Multivariate Legendre polynomials form an orthogonal basis for polynomials under the Gaussian-related inner product used in the construction.They are tensor products of one-variable Legendre polynomials.
Coefficient construction: Change-of-basis operators convert between monomials and Legendre polynomials, allowing the constructed feature expectation to match polynomial coefficients.The operators are denoted E and F, with coefficients indexed by multi-indices.
Coefficient construction: The coefficients are chosen so monomials of degree at most k receive the target coefficients, while higher-degree monomial coefficients are set to zero.This is the coefficient-matching condition required to approximate the target polynomial.
Norm bounds: Bounds on Legendre coefficients, polynomial norms, and the maximum of the constructed function control the approximation quantities in the theorem.The proof separately bounds coefficient terms and the supremum over w.
Norm bounds: The construction uses the uniform bound max_{w∈[-1,1]} |p_i(w)| ≤ 1 for one-variable Legendre polynomials and its multivariate consequence.This bound is inserted into the preceding coefficient estimates.
Conclusion: Substituting the chosen degree parameter into the derived estimates proves items (1) and (2) of the theorem.The cited passages mark the final substitutions and conclusions of the proof.

D Random Features Concentrate Around their Expectation

This section bounds a random-feature quantity using McDiarmid’s inequality and Rademacher complexity under boundedness assumptions, obtaining a high-probability concentration statement.

McDiarmid’s inequality bounds how h changes when one weight is replaced by another function with norm at most one.The argument establishes a bounded-difference condition for each of the r components.
Rademacher complexity is used to bound the expectation of h(x), with independent Rademacher variables introduced in the analysis.The activation is shifted as σ′(x) = σ(x) − α so that σ′(0) = 0.
Cauchy–Schwarz, assumptions ∥x∥, ∥w∥≤1, and properties of the activation are combined to obtain the intermediate bound.
With probability greater than 1 − δ, the resulting concentration bound follows after replacing the right-hand side by δ.

E SGD on Over-Parameterized Networks Competes with Random Features

This section analyzes SGD on over-parameterized networks by controlling parameter movement and applying online convex-learning bounds, thereby relating the procedure to expected population loss.

Lemma E.1 considers SGD with bounded initial parameters ∥W0∥, ∥U0∥≤B for B≥2 and learning rate η tied to ε.
An induction argument establishes parameter bounds across iterations, with the update analysis controlling changes in W and U.
The gradients of LD(U, W) are derived and bounded using the activation assumptions, Eq. (37), Eq. (38), and ∥x∥≤1.The notation ˜Ui = ui · σ′(⟨wi, x⟩) is used in the gradient representation.
Theorem E.1 supplies an online-learning inequality for L-Lipschitz convex functions under gradient updates, which is applied to the gt functions.
The proof defines gt(U) as the loss on the example sampled at SGD round t and observes that these functions are convex and Lipschitz.
Taking expectations identifies E[gt(U)] with LD(Wt, U), and the resulting averaged bound implies that at least one iteration satisfies the target guarantee.

F Approximating polynomials with ReLU networks

The section explains how the polynomial-approximation argument extends to ReLU networks by adding biases and non-standard architectural terms that reproduce the required integral representation.

The ReLU modification adds a bias term and uses a non-standard network architecture rather than the analytic-activation construction.
The architecture duplicates ReLU neurons with a negative sign and includes linear and constant factors, while biases are initialized uniformly on [0, 1].The initialization of wi and ui remains as in Theorem 3.1.
The construction combines positive-part terms, signed reflected terms, and linear and constant components in the integral representation.
For |z|≤1, the weighted ReLU integral identity yields ez, providing the key approximation relation.
Substituting g(w, b) and z = ⟨wi, x⟩ uses the bound |⟨wi, x⟩|≤1 to approximate the desired integral.
The extra linear and constant terms are required for the construction and align with Fourier-transform representations approximable by combinations of ReLUs.