16
$\begingroup$

The Wikipedia article for the universal approximation theorem cites a version of the universal approximation theorem for Lebesgue-measurable functions from this conference paper. However, the paper does not include the proofs of the theorem. Does anybody know where the proof can be found?

$\endgroup$
0
19
$\begingroup$

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 (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 (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. 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, 2]) 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 (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 page 632 of Recurrent Neural Networks Are Universal Approximators (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 (1992, COLT) by Siegelmann and Sontag. This answer could also be useful.

$\endgroup$
0
5
$\begingroup$

"Modern" Guarantees for Feed-Forward Neural Networks

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 depth 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 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) 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)'s breakthrough results.

  1. Shallow Case: If you want quantitative results only for shallow networks: Then J. Siegel and J. Xu (Neural Networks - 2020) 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.)

  2. Deep (not narrow) ReLU 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) 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).
    The article is a constructive version of P. Kidger and T. Lyon's recent deep and narrow universal approximation theorem (COLT - 2020) (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).


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:

  1. 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)
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – nbro
    Jan 22 at 13:03
  • 1
    $\begingroup$ @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!) $\endgroup$
    – AIM_BLB
    Jan 22 at 13:18
  • 1
    $\begingroup$ 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. See this, this and this and maybe also this (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) ;) $\endgroup$
    – nbro
    Jan 22 at 14:23
  • $\begingroup$ @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 $\endgroup$
    – AIM_BLB
    Jan 22 at 15:16
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Leroy Od
    Jul 14 '20 at 8:38
  • $\begingroup$ 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 papers.nips.cc/paper/…). (Note to self: update the wikipedia entry.) Also, of course, Google Scholar has lots of papers that reference it, are related, etc. $\endgroup$ Jul 17 '20 at 0:33

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.