Approximation power of random neural networks

2019/06/18 by Bolton Bailey, Bailey, Bolton, Ziwei Ji +5
Computer Science · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1906.07709

openalex publication_date 2019/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper investigates the approximation power of three types of random neural networks: (a) infinite width networks, with weights following an arbitrary distribution; (b) finite width networks obtained by subsampling the preceding infinite width networks; (c) finite width networks obtained by starting with standard Gaussian initialization, and then adding a vanishingly small correction to the weights. The primary result is a fully quantified bound on the rate of approximation of general general continuous functions: in all three cases, a function f can be approximated with complexity ‖f‖₁ (d/δ)^O(d), where δ depends on continuity properties of f and the complexity measure depends on the weight magnitudes and/or cardinalities. Along the way, a variety of ancillary results are developed: an exact construction of Gaussian densities with infinite width networks, an elementary stand-alone proof scheme for approximation via convolutions of radial basis functions, subsampling rates for infinite width networks, and depth separation for corrected networks.

Citations

• The Power of Depth for Feedforward Neural Networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Fine-Grained Analysis of Optimization and Generalization for\n Overparameterized Two-Layer Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• On the Approximation Properties of Random ReLU Features

Related

• Multi-layer random features and the approximation power of neural networks
• Finite-Dimensional Gaussian Approximation for Deep Neural Networks: Universality in Random Weights
• Approximation bounds for norm constrained deep neural networks
• Random Neural Networks in the Infinite Width Limit as Gaussian Processes
• Wide Deep Neural Networks with Gaussian Weights are Very Close to Gaussian Processes