Approximation rates of Neural Networks

In the worst-case scenario, asymptotically how many non-zero weights must a neural network $\phi$ at least have such that , for $\varepsilon ∈ (0, 1/2)$, and $f \in \cal C$, there holds $|| f - R_{\sigma}(\phi)|| < \varepsilon$, where $\sigma$ denotes the ReLU?

We write $\Phi = ((A_l,b_l))^{L}_{l=1}$ as our neural network with input dimension $d$, where $L$ is the number of layers, $N_0 (=d), N_1,..., N_L$ the number of neurons in each layer, $A_l \in \mathbb R^{N_{l-1} \times N_{l}}$ the weights and $b_l \in \mathbb R^{N_l}$ the biases. $\sigma: \mathbb R \to \mathbb R$ is our activation function.

$R_{\sigma}(\Phi): \mathbb R^d \to \mathbb R^{N_L}$ then denotes the realization of $\Phi$, where $R_{\sigma}(\Phi)(x) = x_L$ with $x_0 := x$, $x_l:=\sigma(A_lx_{l-1}+b_l)$ for $l=1,...,L-1$ and $x_L:=A_Lx_{L-1}+b_L$.

• As it is phrased right now, there is no finite boundary. You should at least state for $f: \mathbb{R}^n \rightarrow \mathbb{R}^m$ what $n$ and $m$ are. Let's assume, for the sake of simplicity, $n=m=1$. Even then it is likely not a finite number. I'll post an answer as soon as you define $R_\sigma$ – Martin Thoma Feb 16 '18 at 6:07

The answer depends of course on the function class $\mathcal{C}$ that you are using here. If $\mathcal{C}$ is a set of continuously differentiable functions, then the answer can be found in Chapter 4 of this paper https://arxiv.org/pdf/1610.01145.pdf. In short, if $\mathcal{C}$ is the set of $d$-dimensional functions which are $n$ times differentiable with derivatives bounded by a constant, then the number of weights that you are looking for is (up to a multiplicative constant) $\varepsilon^{-d/n}$.
If you specify any other function class $\mathcal{C}$, I will be more than happy to find a reference for that.