  This paper considers the following question: how well can depth-two ReLU
networks with randomly initialized bottom-level weights represent smooth
functions? We give near-matching upper- and lower-bounds for
$L_2$-approximation in terms of the Lipschitz constant, the desired accuracy,
and the dimension of the problem, as well as similar results in terms of
Sobolev norms. Our positive results employ tools from harmonic analysis and
ridgelet representation theory, while our lower-bounds are based on (robust
versions of) dimensionality arguments.
