Efficient uniform approximation using Random Vector Functional Link
  networks
Palina Salanevich Olov Schavemaker
A Random Vector Functional Link (RVFL) network is a depth-2 neural network
with random inner weights and biases. As only the outer weights of such
architectures need to be learned, the learning process boils down to a linear
optimization task, allowing one to sidestep the pitfalls of nonconvex
optimization problems. In this paper, we prove that an RVFL with ReLU
activation functions can approximate Lipschitz continuous functions provided
its hidden layer is exponentially wide in the input dimension. Although it has
been established before that such approximation can be achieved in $L_2$ sense,
we prove it for $L_\infty$ approximation error and Gaussian inner weights. To
the best of our knowledge, our result is the first of this kind. We give a
nonasymptotic lower bound for the number of hidden layer nodes, depending on,
among other things, the Lipschitz constant of the target function, the desired
accuracy, and the input dimension. Our method of proof is rooted in probability
theory and harmonic analysis.