On the Approximation Lower Bound for Neural Nets with Random Weights
  A random net is a shallow neural network where the hidden layer is frozen
with random assignment and the output layer is trained by convex optimization.
Using random weights for a hidden layer is an effective method to avoid the
inevitable non-convexity in standard gradient descent learning. It has recently
been adopted in the study of deep learning theory. Here, we investigate the
expressive power of random nets. We show that, despite the well-known fact that
a shallow neural network is a universal approximator, a random net cannot
achieve zero approximation error even for smooth functions. In particular, we
prove that for a class of smooth functions, if the proposal distribution is
compactly supported, then a lower bound is positive. Based on the ridgelet
analysis and harmonic analysis for neural networks, the proof uses the
Plancherel theorem and an estimate for the truncated tail of the parameter
distribution. We corroborate our theoretical results with various simulation
studies, and generally two main take-home messages are offered: (i) Not any
distribution for selecting random weights is feasible to build a universal
approximator; (ii) A suitable assignment of random weights exists but to some
degree is associated with the complexity of the target function.
