# Multi-layer random features and the approximation power of neural networks

arXiv: https://arxiv.org/abs/2404.17461 · HTML: https://mlsanity.com/paper/2404.17461/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 32 references that are in the map.
- First posted on arXiv 26 Apr 2024.

## Builds on (most cited first, 12 of 12)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Generative Moment Matching Networks](https://mlsanity.com/paper/1502.02761/) (2015)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [Sparse Gaussian Processes with Spherical Harmonic Features](https://mlsanity.com/paper/2006.16649/) (2020)
- [On the ability of neural nets to express distributions](https://mlsanity.com/paper/1702.07028/) (2017)
- [Random Features for Compositional Kernels](https://mlsanity.com/paper/1703.07872/) (2017)

## Built on by (most cited first, 2 of 2)

- [On the Intrinsic Dimensions of Data in Kernel Learning](https://mlsanity.com/paper/2601.16139/) (2026)
- [Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding](https://mlsanity.com/paper/2605.26067/) (2026)

## Abstract (arXiv)

A neural architecture with randomly initialized weights, in the infinite width limit, is equivalent to a Gaussian Random Field whose covariance function is the so-called Neural Network Gaussian Process kernel (NNGP). We prove that a reproducing kernel Hilbert space (RKHS) defined by the NNGP contains only functions that can be approximated by the architecture. To achieve a certain approximation error the required number of neurons in each layer is defined by the RKHS norm of the target function. Moreover, the approximation can be constructed from a supervised dataset by a random multi-layer representation of an input vector, together with training of the last layer's weights. For a 2-layer NN and a domain equal to an n-1-dimensional sphere in mathbb Rn, we compare the number of neurons required by Barron's theorem and by the multi-layer features construction. We show that if eigenvalues of the integral operator of the NNGP decay slower than k^-n-frac23 where k is an order of an eigenvalue, then our theorem guarantees a more succinct neural network approximation than Barron's theorem. We also make some computational experiments to verify our theoretical findings. Our experiments show that realistic neural networks easily learn target functions even when both theorems do not give any guarantees.