  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\|_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.
