Body: <p>The Universal Approximation Theorem states (roughly) that any continuous function can be approximated to within an arbitrary precision <span class="math-container">$\varepsilon&gt;0$</span> by a feedforward neural network with one hidden layer (a Shallow Neural Network) with sufficient width.</p>
  <p>I remember stumbling upon articles showing that for some functions the necessary number of hidden neurons tends to infinity as <span class="math-container">$\varepsilon$</span> tends to zero (similar to this one by <a href="https://openreview.net/forum?id=rkevSgrtPr" rel="nofollow noreferrer">A closer look at the approximation capabilities of neural networks</a>), but I have not had success finding them again. Is my memory incorrect or is it merely my searching skills that are insufficient?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-01T11:00:09.830Z
Comments.Text: This is obviously not true for some functions, e.g. the ones produced by neural networks with N hidden neurons :) For an example of one where it is true, try something like the Weierstrass function.
Comments.UserDisplayName: Criticize SE actions means ban
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-01T13:15:08.563Z
Comments.Text: @user253751 You  are right, it is of course not true for all functions! I have tried to make the question more precise: I am looking for certain functions for which it is not true. Regarding the Weierstraß function: I am not certain that the number of neurons tends to infinity, since in [Universal Approximation with Deep Narrow Networks](http://proceedings.mlr.press/v125/kidger20a/kidger20a.pdf) it is shown that for some networks with continuous activation functions that are nowhere differentiable, they still have the uniform approximation property.
Comments.UserDisplayName: GraftCraft
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-01T14:02:41.377Z
Comments.Text: I would suspect the need for infinite neurons to reach 0 error is for *most* functions. user253751 gives one obvious exception - i.e. functions that are naturally expressed by a neural network architcture that you are allowed to use in the approximation. However, even $f(x) = x$ cannot be approximated with zero error by a finite neural network once you add a hidden layer with a non-linear activation function.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-01T15:02:40.210Z
Comments.Text: @NeilSlater You are probably right that this applies for most functions, but I am still hoping to find a paper giving a proper example or proof, since I would prefer not having to either state it without a reference, come up with a proper example/ proof or just using handwaving. Looking at Lemma 4.1 in [Universal Approximation with Deep Narrow Networks](http://proceedings.mlr.press/v125/kidger20a/kidger20a.pdf) I think $f(x)=x$ can actually be approximated arbitrarily well by a shallow neural network with a nonlinear activation function and just a single hidden node.
Comments.UserDisplayName: GraftCraft
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-01T16:48:27.047Z
Comments.Text: Yes, I missed that sigmoid is approximately linear at $x=0$, so you can magnify that by having a tiny weight to the hidden layer followed by a gigantic weight to the output. However, "arbitrarily well" does not equate to "zero error" - it is just that you don't gain anything by adding more neurons, the approximation can be improved by manipulating the weights for a single neuron.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-01T19:13:10.480Z
Comments.Text: @NeilSlater True, but I am looking for a function that forces me to add more nodes, if I want to decrease the approximation error.
Comments.UserDisplayName: GraftCraft
Tags: <neural-networks><reference-request><feedforward-neural-networks><function-approximation><universal-approximation-theorems>
Title: Does there exist functions for which the necessary number of nodes in a shallow neural network tends to infinity as approximation error tends to 0?
UserDisplayName: GraftCraft
ThreadText: # Does there exist functions for which the necessary number of nodes in a shallow neural network tends to infinity as approximation error tends to 0?
  
  (Asked by: username_0 on 2021-11-01)
  
  The Universal Approximation Theorem states (roughly) that any continuous function can be approximated to within an arbitrary precision $\varepsilon>0$ by a feedforward neural network with one hidden layer (a Shallow Neural Network) with sufficient width.
  
  I remember stumbling upon articles showing that for some functions the necessary number of hidden neurons tends to infinity as $\varepsilon$ tends to zero (similar to this one by [A closer look at the approximation capabilities of neural networks](https://openreview.net/forum?id=rkevSgrtPr)), but I have not had success finding them again. Is my memory incorrect or is it merely my searching skills that are insufficient?
  
  **Tags:** neural-networks, reference-request, feedforward-neural-networks, function-approximation, universal-approximation-theorems
  
  > **Comments:**
  > **username_1**: This is obviously not true for some functions, e.g. the ones produced by neural networks with N hidden neurons :) For an example of one where it is true, try something like the Weierstrass function.  
  > **username_0**: @user253751 You  are right, it is of course not true for all functions! I have tried to make the question more precise: I am looking for certain functions for which it is not true. Regarding the Weierstraß function: I am not certain that the number of neurons tends to infinity, since in [Universal Approximation with Deep Narrow Networks](http://proceedings.mlr.press/v125/kidger20a/kidger20a.pdf) it is shown that for some networks with continuous activation functions that are nowhere differentiable, they still have the uniform approximation property.  
  > **username_2**: I would suspect the need for infinite neurons to reach 0 error is for *most* functions. user253751 gives one obvious exception - i.e. functions that are naturally expressed by a neural network architcture that you are allowed to use in the approximation. However, even $f(x) = x$ cannot be approximated with zero error by a finite neural network once you add a hidden layer with a non-linear activation function.  
  > **username_0**: @username_2 You are probably right that this applies for most functions, but I am still hoping to find a paper giving a proper example or proof, since I would prefer not having to either state it without a reference, come up with a proper example/ proof or just using handwaving. Looking at Lemma 4.1 in [Universal Approximation with Deep Narrow Networks](http://proceedings.mlr.press/v125/kidger20a/kidger20a.pdf) I think $f(x)=x$ can actually be approximated arbitrarily well by a shallow neural network with a nonlinear activation function and just a single hidden node.  
  > **username_2**: Yes, I missed that sigmoid is approximately linear at $x=0$, so you can magnify that by having a tiny weight to the hidden layer followed by a gigantic weight to the output. However, "arbitrarily well" does not equate to "zero error" - it is just that you don't gain anything by adding more neurons, the approximation can be improved by manipulating the weights for a single neuron.  
  > **username_0**: @username_2 True, but I am looking for a function that forces me to add more nodes, if I want to decrease the approximation error.  
  
  ---
  
  ## 0 answers
  
  