1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – Martin Thoma Feb 16 '18 at 6:07
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.