Answers.Body: <h2>&quot;Modern&quot; Guarantees for <a href="https://en.wikipedia.org/wiki/Feedforward_neural_network" rel="noreferrer">Feed-Forward Neural Networks</a></h2>
  <p>My answer will complement nbro's above, which gave a very nice overview of universal approximation theorems for different types of commonly used architectures, by focusing on recent developments specifically for feed-forward networks.  I'll try an emphasis <a href="https://ai.stackexchange.com/questions/1742/what-is-the-difference-between-machine-learning-and-deep-learning">depth</a> over breadth (sometimes called width) as much as possible.  <em>Enjoy!</em></p>
  <hr />
  <p><strong>Part 1: Universal Approximation</strong></p>
  <p><em>Here I've listed a few recent universal approximation results that come to mind.</em>  Remember, <em>universal approximation</em> asks if feed-forward networks (or some other architecture type) can <em>approximate</em> any (in this case continuous) function to arbitrary accuracy (I'll focus on the : <em><a href="https://math.stackexchange.com/questions/560978/what-is-topology-of-compact-convergence">uniformly on compacts</a></em> sense).</p>
  <p>Let me mention, that there are two types of guarantees: <em>quantitative ones</em> and <em>qualitative ones</em>.  The latter are akin to <a href="https://www.sciencedirect.com/science/article/pii/0893608089900208" rel="noreferrer">Hornik's results (Neural Networks - 1989)</a> which simply state that some neural networks can approximate a given (continuous) function to arbitrary precision.  The former of these types of guarantees quantifies the number of parameters required for a neural network to actually perform the approximation and are akin to <a href="https://ieeexplore.ieee.org/document/256500" rel="noreferrer">Barron's (now) classical paper (IEEE - 1993)</a>'s breakthrough results.</p>
  <ol>
  <li><p><strong>Shallow Case:</strong>  If you want quantitative results only for <em>shallow</em> networks:
  Then <a href="https://www.sciencedirect.com/science/article/pii/S0893608020301891#b9" rel="noreferrer">J. Siegel and J. Xu (Neural Networks - 2020)</a> will do the trick but (note: The authors deal with the Sobolev case but you get the continuous case immediately via the <a href="https://mathoverflow.net/questions/127259/sharpness-of-the-sobolev-embedding-theorem">Soblev-Morrey embedding theorem</a>.)</p>
  </li>
  <li><p><strong>Deep (not narrow) <a href="https://ai.stackexchange.com/questions/6468/why-do-we-prefer-relu-over-linear-activation-functions">ReLU</a> Case:</strong>  If you want a quantitative proof for deep networks (but not too narrow) with ReLU activation function then <a href="http://proceedings.mlr.press/v75/yarotsky18a/yarotsky18a.pdf" rel="noreferrer">Dimity Yarotsky's result (COLT - 2018)</a> will do the trick!</p>
  </li>
  <li><p><strong>Deep and Narrow:</strong> To the best of my knowledge, the first quantitative proof for deep and narrow neural networks with general input and output spaces has recently appeared here:
  <a href="https://arxiv.org/abs/2101.05390" rel="noreferrer">https://arxiv.org/abs/2101.05390 (preprint - 2021)</a>.<br />
  The article is a constructive version of <a href="http://proceedings.mlr.press/v125/kidger20a.html" rel="noreferrer">P. Kidger and T. Lyon's recent deep and narrow universal approximation theorem (COLT - 2020)</a> (qualitative) for functions from <span class="math-container">$\mathbb{R}^p$</span> to <span class="math-container">$\mathbb{R}^m$</span> and <a href="https://proceedings.neurips.cc/paper/2020/file/786ab8c4d7ee758f80d57e65582e609d-Paper.pdf" rel="noreferrer">A. Kratsios and E. Bilokpytov's recent Non-Euclidean Universal Approximation Theorem (NeurIPS - 2020).</a></p>
  </li>
  </ol>
  <hr />
  <p><strong>Part 2: Memory Capacity</strong></p>
  <p><em>A related concept is that of</em> <strong>&quot;memory capacity of a deep neural network&quot;</strong>.<br />
  These results seek to quantify the number of parameters needed for a deep network to learn (exactly) the assignment of some input data <span class="math-container">$\{x_n\}_{n=1}^N$</span> to some output data <span class="math-container">$\{y_n\}_{n=1}^N$</span>.  For example; you may want to take a look here:</p>
  <ol start="4">
  <li><strong>Memory Capacity of Deep ReLU networks:</strong> R. Vershynin's very recent publication <a href="https://epubs.siam.org/doi/pdf/10.1137/20M1314884" rel="noreferrer">Memory Capacity of Neural Networks with Threshold and Rectified Linear Unit Activations - (SIAM's SIMODS 2020)</a></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T13:03:28.217Z
Answers.Text: Thanks for contributing to our site! I really appreciate that :) It's important to note that some of these papers are very recent (2020 or 2021) and they are still pre-prints, so they may contain some inaccuracies (as they have not been formally reviewed yet). Of course, it will take some time to go through those technical papers and understand them. I had already come across Dimity Yarotsky's paper, so I may read it later. Given that this answer emphasizes "more recent work" (maybe you can provide the years when they have been released).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T13:18:33.560Z
Answers.Text: @nbro That's a great idea; As you suggested, I added the dates and venues they were published/peer-reeved at (with the exception of the 2021 preprint).  Also, I added a title to emphasise the fact that my answer focuses on feed-forward networks (rather than your overview discussion; it's very nice idea' thanks!)
Answers.UserDisplayName: ABIM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T14:23:08.773Z
Answers.Text: Regarding the "memory capacity of a deep neural network" part (2nd part), this just looks like a regular question that you would ask in [**computational learning theory**](https://ai.stackexchange.com/q/20355/2444). See [this](https://ai.stackexchange.com/q/17870/2444), [this](https://ai.stackexchange.com/q/18220/2444) and [this](https://ai.stackexchange.com/q/25527/2444) and maybe also [this](https://ai.stackexchange.com/q/17839/2444) (if you're not familiar with the field). Maybe you're able to answer some of those questions (after having read the paper you linked there) ;)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T15:16:14.683Z
Answers.Text: @nbro Wow thanks for the links.  I didn't know much about this field... I'll read those posts and definitely will have to give some of the questions a shot :D
Answers.UserDisplayName: ABIM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T12:25:26.100Z
Answers.LastActivityDate: 2021-01-22T15:17:02.490Z
Answers.LastEditDate: 2021-01-22T15:17:02.490Z
Answers.UserDisplayName: ABIM
Answers.Body: <p>Just wanted to add that the new text <em>Deep Learning Architectures
  A Mathematical Approach</em> mentions this result, but I'm not sure if it gives a proof. It does mention an improved result by Hanin (<a href="http://arxiv.org/abs/1708.02691" rel="nofollow noreferrer">http://arxiv.org/abs/1708.02691</a>) for which I think it does give at least a partial proof. The original paper by Hanin seems to omit some proofs as well, but the published version (<a href="https://www.mdpi.com/2227-7390/7/10/992/htm" rel="nofollow noreferrer">https://www.mdpi.com/2227-7390/7/10/992/htm</a>) may be more complete.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T08:38:23.180Z
Answers.Text: I've found the proof eventually. It turned out to be very technical and is only interesting from a theoretical view point. What about the book that you mention ? Do you read it ? Can you recommend it ? @loren-rosen
Answers.UserDisplayName: Leroy Od
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-17T00:33:26.103Z
Answers.Text: I've only read the preface, and looked to see if it had the proof. Anyway, I do see that the conference proceedings have a link to an appendix with the proof (see https://papers.nips.cc/paper/7203-the-expressive-power-of-neural-networks-a-view-from-the-width-supplemental.zip). (Note to self: update the wikipedia entry.) Also, of course, Google Scholar has lots of papers that reference it, are related, etc.
Answers.UserDisplayName: Loren Rosen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T01:22:11.070Z
Answers.LastActivityDate: 2020-07-14T01:22:11.070Z
Answers.UserDisplayName: Loren Rosen
Answers.Body: <p>There are multiple papers on the topic because there have been multiple attempts to prove that neural networks are universal (i.e. they can <strong>approximate</strong> any <strong>continuous</strong> function) from slightly different perspectives and using slightly different assumptions (e.g. assuming that certain activation functions are used). Note that these proofs tell you that neural networks can <strong>approximate</strong> any <strong>continuous</strong> function, but they do not tell you <strong>exactly</strong> how you need to train your neural network so that it approximates your desired function. Moreover, most papers on the topic are quite technical and mathematical, so, if you do not have a solid knowledge of approximation theory and related fields, they may be difficult to read and understand. Nonetheless, below there are some links to some possibly useful articles and papers.</p>
  <p>The article <a href="http://neuralnetworksanddeeplearning.com/chap4.html" rel="noreferrer">A visual proof that neural nets can compute any function</a> (by Michael Nielsen) should give you some intuition behind the <em>universality</em> of neural networks, so this is probably the first article you should read.</p>
  <p>Then you should probably read the paper <a href="https://link.springer.com/content/pdf/10.1007/BF02551274.pdf" rel="noreferrer">Approximation by Superpositions of a Sigmoidal Function</a> (1989), by G. Cybenko, who proves that <strong>multi-layer perceptrons</strong> (i.e. feed-forward neural networks with at least one hidden layer) can approximate any <a href="https://en.wikipedia.org/wiki/Continuous_function" rel="noreferrer">continuous function</a>. However, he assumes that the neural network uses sigmoid activations functions, which, nowadays, have been replaced in many scenarios by ReLU activation functions. Other works (e.g. <a href="https://archive.nyu.edu/jspui/bitstream/2451/14329/1/IS-92-13.pdf" rel="noreferrer">[1]</a>, <a href="https://pinkus.net.technion.ac.il/files/2021/02/acta.pdf" rel="noreferrer">[2]</a>) showed that you don't necessarily need sigmoid activation functions, but only certain classes of activation functions do not make neural networks universal.</p>
  <p>The universality property (i.e. the ability to approximate any continuous function) has also been proved in the case of <strong>convolutional neural networks</strong>. For example, see <a href="https://www.sciencedirect.com/science/article/abs/pii/S1063520318302045" rel="noreferrer">Universality of Deep Convolutional Neural Networks</a> (2020), by Ding-Xuan Zhou, which shows that convolutional neural networks can approximate any continuous function to an arbitrary accuracy when the depth of the neural network is large enough. See also <a href="https://ieeexplore.ieee.org/document/9126188" rel="noreferrer">Refinement and Universal Approximation via Sparsely Connected ReLU Convolution Nets</a> (by A. Heinecke et al., 2020)</p>
  <p>See also page 632 of <a href="https://link.springer.com/chapter/10.1007/11840817_66" rel="noreferrer">Recurrent Neural Networks Are Universal Approximators</a> (2006), by Schäfer et al., which shows that <strong>recurrent neural networks</strong> are universal function approximators. See also <a href="http://binds.cs.umass.edu/papers/1992_Siegelmann_COLT.pdf" rel="noreferrer">On the computational power of neural nets</a> (1992, COLT) by Siegelmann and Sontag. <a href="https://stats.stackexchange.com/a/221142/82135">This answer</a> could also be useful.</p>
  <p>For <strong>graph neural networks</strong>, see <a href="https://proceedings.neurips.cc//paper/2020/hash/e4acb4c86de9d2d9a41364f93951028d-Abstract.html" rel="noreferrer">Universal Function Approximation on Graphs</a> (by Rickard Brüel Gabrielsson, 2020, NeurIPS)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-16T11:14:34.487Z
Answers.Text: Cybenko's proof is more general. Definition 1, top of pg. 306, is for a "discriminatory" function $\sigma$. This includes many activation functions, including sigmoid. Theorem 1 applies to any $\sigma$ and says the closure of finite sums of the typical form is the space of continuous functions. What is "discriminatory"? It requires the expectation of an activation function over a bounded region is 0 for all parameters iff the probability of an input in the bounded region is 0. I.e., if there is any data in the bounded region then for some parameter, the expected output of the network $\neq 0$.
Answers.UserDisplayName: Anirban Mukherjee
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-11T09:05:24.107Z
Answers.LastActivityDate: 2021-12-16T11:41:15.140Z
Answers.LastEditDate: 2021-12-16T11:41:15.140Z
Answers.UserDisplayName: nbro
Body: <p>The <a href="https://en.wikipedia.org/wiki/Universal_approximation_theorem" rel="noreferrer">Wikipedia article for the universal approximation</a> theorem cites a version of the universal approximation theorem for Lebesgue-measurable functions from <a href="https://arxiv.org/pdf/1709.02540.pdf" rel="noreferrer">this conference paper</a>. However, the paper does not include the proofs of the theorem. Does anybody know where the proof can be found?</p>
  
Tags: <neural-networks><reference-request><proofs><function-approximation><universal-approximation-theorems>
Title: Where can I find the proof of the universal approximation theorem?
UserDisplayName: Leroy Od
ThreadText: # Where can I find the proof of the universal approximation theorem?
  
  (Asked by: username_0 on 2019-07-11)
  
  The [Wikipedia article for the universal approximation](https://en.wikipedia.org/wiki/Universal_approximation_theorem) theorem cites a version of the universal approximation theorem for Lebesgue-measurable functions from [this conference paper](https://arxiv.org/pdf/1709.02540.pdf). However, the paper does not include the proofs of the theorem. Does anybody know where the proof can be found?
  
  **Tags:** neural-networks, reference-request, proofs, function-approximation, universal-approximation-theorems
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2019-07-11. Score: 31 | Accepted answer
  
  There are multiple papers on the topic because there have been multiple attempts to prove that neural networks are universal (i.e. they can **approximate** any **continuous** function) from slightly different perspectives and using slightly different assumptions (e.g. assuming that certain activation functions are used). Note that these proofs tell you that neural networks can **approximate** any **continuous** function, but they do not tell you **exactly** how you need to train your neural network so that it approximates your desired function. Moreover, most papers on the topic are quite technical and mathematical, so, if you do not have a solid knowledge of approximation theory and related fields, they may be difficult to read and understand. Nonetheless, below there are some links to some possibly useful articles and papers.
  
  The article [A visual proof that neural nets can compute any function](http://neuralnetworksanddeeplearning.com/chap4.html) (by Michael Nielsen) should give you some intuition behind the *universality* of neural networks, so this is probably the first article you should read.
  
  Then you should probably read the paper [Approximation by Superpositions of a Sigmoidal Function](https://link.springer.com/content/pdf/10.1007/BF02551274.pdf) (1989), by G. Cybenko, who proves that **multi-layer perceptrons** (i.e. feed-forward neural networks with at least one hidden layer) can approximate any [continuous function](https://en.wikipedia.org/wiki/Continuous_function). However, he assumes that the neural network uses sigmoid activations functions, which, nowadays, have been replaced in many scenarios by ReLU activation functions. Other works (e.g. [[1]](https://archive.nyu.edu/jspui/bitstream/2451/14329/1/IS-92-13.pdf), [[2]](https://pinkus.net.technion.ac.il/files/2021/02/acta.pdf)) showed that you don't necessarily need sigmoid activation functions, but only certain classes of activation functions do not make neural networks universal.
  
  The universality property (i.e. the ability to approximate any continuous function) has also been proved in the case of **convolutional neural networks**. For example, see [Universality of Deep Convolutional Neural Networks](https://www.sciencedirect.com/science/article/abs/pii/S1063520318302045) (2020), by Ding-Xuan Zhou, which shows that convolutional neural networks can approximate any continuous function to an arbitrary accuracy when the depth of the neural network is large enough. See also [Refinement and Universal Approximation via Sparsely Connected ReLU Convolution Nets](https://ieeexplore.ieee.org/document/9126188) (by A. Heinecke et al., 2020)
  
  See also page 632 of [Recurrent Neural Networks Are Universal Approximators](https://link.springer.com/chapter/10.1007/11840817_66) (2006), by Schäfer et al., which shows that **recurrent neural networks** are universal function approximators. See also [On the computational power of neural nets](http://binds.cs.umass.edu/papers/1992_Siegelmann_COLT.pdf) (1992, COLT) by Siegelmann and Sontag. [This answer](https://stats.stackexchange.com/a/221142/82135) could also be useful.
  
  For **graph neural networks**, see [Universal Function Approximation on Graphs](https://proceedings.neurips.cc//paper/2020/hash/e4acb4c86de9d2d9a41364f93951028d-Abstract.html) (by Rickard Brüel Gabrielsson, 2020, NeurIPS)
  
  > **Comments:**
  > **username_4**: Cybenko's proof is more general. Definition 1, top of pg. 306, is for a "discriminatory" function $\sigma$. This includes many activation functions, including sigmoid. Theorem 1 applies to any $\sigma$ and says the closure of finite sums of the typical form is the space of continuous functions. What is "discriminatory"? It requires the expectation of an activation function over a bounded region is 0 for all parameters iff the probability of an input in the bounded region is 0. I.e., if there is any data in the bounded region then for some parameter, the expected output of the network $\neq 0$.  
  
  ---
  
  ### Answer by username_1 on 2021-01-22. Score: 6
  
  ## "Modern" Guarantees for [Feed-Forward Neural Networks](https://en.wikipedia.org/wiki/Feedforward_neural_network)
  
  My answer will complement username_2's above, which gave a very nice overview of universal approximation theorems for different types of commonly used architectures, by focusing on recent developments specifically for feed-forward networks. I'll try an emphasis [depth](https://ai.stackexchange.com/questions/1742/what-is-the-difference-between-machine-learning-and-deep-learning) over breadth (sometimes called width) as much as possible. *Enjoy!*
  
  ---
  
  **Part 1: Universal Approximation**
  
  *Here I've listed a few recent universal approximation results that come to mind.* Remember, *universal approximation* asks if feed-forward networks (or some other architecture type) can *approximate* any (in this case continuous) function to arbitrary accuracy (I'll focus on the : *[uniformly on compacts](https://math.stackexchange.com/questions/560978/what-is-topology-of-compact-convergence)* sense).
  
  Let me mention, that there are two types of guarantees: *quantitative ones* and *qualitative ones*. The latter are akin to [Hornik's results (Neural Networks - 1989)](https://www.sciencedirect.com/science/article/pii/0893608089900208) which simply state that some neural networks can approximate a given (continuous) function to arbitrary precision. The former of these types of guarantees quantifies the number of parameters required for a neural network to actually perform the approximation and are akin to [Barron's (now) classical paper (IEEE - 1993)](https://ieeexplore.ieee.org/document/256500)'s breakthrough results.
  
  1. **Shallow Case:** If you want quantitative results only for *shallow* networks:
     Then [J. Siegel and J. Xu (Neural Networks - 2020)](https://www.sciencedirect.com/science/article/pii/S0893608020301891#b9) will do the trick but (note: The authors deal with the Sobolev case but you get the continuous case immediately via the [Soblev-Morrey embedding theorem](https://mathoverflow.net/questions/127259/sharpness-of-the-sobolev-embedding-theorem).)
  2. **Deep (not narrow) [ReLU](https://ai.stackexchange.com/questions/6468/why-do-we-prefer-relu-over-linear-activation-functions) Case:** If you want a quantitative proof for deep networks (but not too narrow) with ReLU activation function then [Dimity Yarotsky's result (COLT - 2018)](http://proceedings.mlr.press/v75/yarotsky18a/yarotsky18a.pdf) will do the trick!
  3. **Deep and Narrow:** To the best of my knowledge, the first quantitative proof for deep and narrow neural networks with general input and output spaces has recently appeared here:
     [https://arxiv.org/abs/2101.05390 (preprint - 2021)](https://arxiv.org/abs/2101.05390).  
     The article is a constructive version of [P. Kidger and T. Lyon's recent deep and narrow universal approximation theorem (COLT - 2020)](http://proceedings.mlr.press/v125/kidger20a.html) (qualitative) for functions from $\mathbb{R}^p$ to $\mathbb{R}^m$ and [A. Kratsios and E. Bilokpytov's recent Non-Euclidean Universal Approximation Theorem (NeurIPS - 2020).](https://proceedings.neurips.cc/paper/2020/file/786ab8c4d7ee758f80d57e65582e609d-Paper.pdf)
  
  ---
  
  **Part 2: Memory Capacity**
  
  *A related concept is that of* **"memory capacity of a deep neural network"**.  
  These results seek to quantify the number of parameters needed for a deep network to learn (exactly) the assignment of some input data $\{x\_n\}\_{n=1}^N$ to some output data $\{y\_n\}\_{n=1}^N$. For example; you may want to take a look here:
  
  4. **Memory Capacity of Deep ReLU networks:** R. Vershynin's very recent publication [Memory Capacity of Neural Networks with Threshold and Rectified Linear Unit Activations - (SIAM's SIMODS 2020)](https://epubs.siam.org/doi/pdf/10.1137/20M1314884)
  
  > **Comments:**
  > **username_2**: Thanks for contributing to our site! I really appreciate that :) It's important to note that some of these papers are very recent (2020 or 2021) and they are still pre-prints, so they may contain some inaccuracies (as they have not been formally reviewed yet). Of course, it will take some time to go through those technical papers and understand them. I had already come across Dimity Yarotsky's paper, so I may read it later. Given that this answer emphasizes "more recent work" (maybe you can provide the years when they have been released).  
  > **username_1**: @username_2 That's a great idea; As you suggested, I added the dates and venues they were published/peer-reeved at (with the exception of the 2021 preprint).  Also, I added a title to emphasise the fact that my answer focuses on feed-forward networks (rather than your overview discussion; it's very nice idea' thanks!)  
  > **username_2**: Regarding the "memory capacity of a deep neural network" part (2nd part), this just looks like a regular question that you would ask in [**computational learning theory**](https://ai.stackexchange.com/q/20355/2444). See [this](https://ai.stackexchange.com/q/17870/2444), [this](https://ai.stackexchange.com/q/18220/2444) and [this](https://ai.stackexchange.com/q/25527/2444) and maybe also [this](https://ai.stackexchange.com/q/17839/2444) (if you're not familiar with the field). Maybe you're able to answer some of those questions (after having read the paper you linked there) ;)  
  > **username_1**: @username_2 Wow thanks for the links.  I didn't know much about this field... I'll read those posts and definitely will have to give some of the questions a shot :D  
  
  ---
  
  ### Answer by username_3 on 2020-07-14. Score: 2
  
  Just wanted to add that the new text *Deep Learning Architectures
  A Mathematical Approach* mentions this result, but I'm not sure if it gives a proof. It does mention an improved result by Hanin (<http://arxiv.org/abs/1708.02691>) for which I think it does give at least a partial proof. The original paper by Hanin seems to omit some proofs as well, but the published version (<https://www.mdpi.com/2227-7390/7/10/992/htm>) may be more complete.
  
  > **Comments:**
  > **username_0**: I've found the proof eventually. It turned out to be very technical and is only interesting from a theoretical view point. What about the book that you mention ? Do you read it ? Can you recommend it ? @username_3  
  > **username_3**: I've only read the preface, and looked to see if it had the proof. Anyway, I do see that the conference proceedings have a link to an appendix with the proof (see https://papers.nips.cc/paper/7203-the-expressive-power-of-neural-networks-a-view-from-the-width-supplemental.zip). (Note to self: update the wikipedia entry.) Also, of course, Google Scholar has lots of papers that reference it, are related, etc.  
  
  ---
  
  