Approximation power of random neural networks

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 $\Vert f{\Vert }_1(d/\delta {)}^{\mathcal{O}(d)}$, where $\delta$ 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.

arXiv commentThis submission constitutes a poor approach to the problem, and has no scientific purpose. A superior (different) approach (and stronger final result, also treating the NTK) has appeared in arXiv:1910.06956 ; please see that work instead

References in corpus (13)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• The Power of Depth for Feedforward Neural Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Representation Benefits of Deep Feedforward Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• A mean-field limit for certain deep neural networks
• On the Approximation Properties of Random ReLU Features
• How do infinite width bounded norm networks look in function space?

Cited by in corpus (5)

• A Corrective View of Neural Networks: Representation, Memorization and Learning
• How Powerful are Shallow Neural Networks with Bandlimited Random Weights?
• Any Target Function Exists in a Neighborhood of Any Sufficiently Wide Random Network: A Geometrical Perspective
• Global Capacity Measures for Deep ReLU Networks via Path Sampling
• Learning Barrier Functions with Memory for Robust Safe Navigation