Fix $d\in \mathbb{N}$. Let $F_1$ be the set of all 1-Lipschitz functions mapping $[0, 1]^d$ to $\mathbb{R}$.

For $\varphi: \mathbb{R} \rightarrow \mathbb{R}$ and $m \in \mathbb{N}$, let $N_\varphi^m$ be the set of feed-forward neural network functions with input dimension $d$, output dimension 1, hidden dimension m, two layers and activation function $\varphi$. That means $N_\varphi^m$ is the set of functions $h: \mathbb{R}^d \rightarrow \mathbb{R}$ such that $h(x) = b_0 + \sum_{i=1}^m b_i \varphi(a_0 + \sum_{j=1}^d a_j x_j)$ for $x\in \mathbb{R}^d$, where $a_0, ..., a_d \in \mathbb{R}$ and $b_0, ..., b_m \in \mathbb{R}$ are the weights of the network.

I am looking for the following result, which I expect to exist somewhere in the literature (for a suitable activation function $\varphi$):

Does the following hold?

For any $\varepsilon > 0$, there exists some $m \in \mathbb{N}$, such that for any $f \in F_1$ there exists $f^m \in N_\varphi^m$ so that for all $x \in [0, 1]^d$ it holds $|f(x)-f^m(x)|<\varepsilon$.

More abstractly, I am looking for a standard universal approximation result for neural networks, but the necessary hidden dimension $m$ should only depend on the function class (Lipschitz functions), not on the specific function.

In this paper the authors achieve this kind of result (Theorem 1), but they require deep neural networks instead of shallow ones.


Maybe you can check Theorem 4 in Poggio et al. "Why and When Can Deep-but Not Shallow-Networks Avoid the Curse of Dimensionality: A Review"

  • $\begingroup$ Thanks, this indeed looks like the kind of result I need. However, I'll leave the check mark open for now, as there might be results out there with a more direct proof or more general activation functions! $\endgroup$
    – Steve
    May 15 '20 at 10:35

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.