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
  • 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
    Commented Feb 16, 2018 at 6:07

1 Answer 1

Reset to default
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$
5
  • $\begingroup$ Actually, it seems you accidentally misquoted the paper you referenced. The rate $\epsilon^{-d/n}$ assumes that the weights in the networks depend continuously on the function $f$ (Theorem 3). However, Theorem 4 in that same chapter provides the answer if we allow discontinuous dependence of the weights. Namely, the approximation rate is lower bounded by $\epsilon^{-d/2n}$ (Theorem 4). Note that it matters whether we want to use the same architecture for any $f$ or not. For this matter, compare Theorems 4 and 5 in the above paper. $\endgroup$
    – Florian R
    Commented Apr 21, 2020 at 14:20
  • $\begingroup$ I would like to add that, up to logarithmic factors, the rate $\epsilon^{-d/2n}$ can be achieved, see arxiv.org/pdf/2001.03040.pdf. Lastly, sigmoidal networks achieve the same rate, but for these it is not known whether it is optimal. $\endgroup$
    – Florian R
    Commented Apr 21, 2020 at 14:21
  • $\begingroup$ My statement refers to Theorem 4 b) of the paper. $\endgroup$
    – pcp
    Commented Apr 21, 2020 at 14:48
  • $\begingroup$ Theorem 4b) puts an extra restriction on the architecture, though, assuming the depth grows only logarithmically in the reciprocal of the accuracy. Theorem 4a) is the general statement. I would point this out in the answer. $\endgroup$
    – Florian R
    Commented Apr 21, 2020 at 14:51
  • $\begingroup$ L (the depth) is considered a fixed natural number in my answer. $\endgroup$
    – pcp
    Commented Apr 21, 2020 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .