5
$\begingroup$

I was looking at the differences between these mathematical theorems:

Both of these theorems concern themselves with function approximating other functions through compositions.

In the case of the Universal Approximation Theorem, it has been shown that sums of function compositions (in the form of a Neural Network) have the ability to approximate any function to any level of error. The Universal Approximation Theorem is said to be the main mathematical theorem that justifies the success of Neural Networks. Mathematically, Neural Networks can be interpreted as "affine compositions of functions".

In the case of the Kolmogorov Representation Theorem, it has been shown that any function can be fully represented (i.e. no error) also through finite sums of compositions. The Kolmogorov Representation Theorem has a "similar" form as the Universal Approximation Theorem - although they are both different.

If I have understood all this correctly - both of these theorems make claims about the ability to approximate any function using compositions of functions - however, one of these theorems is specifically called the "Universal Approximation Theorem".

If I have understood all this correctly - it seems to me that the Kolmogorov's Representation Theorem only guarantees the existence of such a function, yet provides us no meaningful method to "recover" this function ... whereas the Universal Approximation Theorem is effectively making a similar claim about an already existing method (i.e. neural networks) of recovering such a function.

  • Is my understanding of the above correct?
  • Have I correctly identified the differences between the Universal Approximation Theorem and Kolomogorov's Representation Theorem?
  • Why are neural networks based on the "Universal Approximation Theorem" and not the "Kolmogorov Representation Theorem"?

Thank you!

$\endgroup$
3
  • $\begingroup$ The kolmogorov theorem is not about approximating. It is about exactly representing (approximating with zero error if you want). $\endgroup$
    – PhoemueX
    Mar 16, 2022 at 7:45
  • $\begingroup$ Thank you! I was just wondering : why are neural networks based on the 'universal approximation theorem" and not the "kolmogorov representation theorem"? thanks! $\endgroup$
    – stats_noob
    Mar 16, 2022 at 19:37
  • $\begingroup$ "In the case of the UAT, it has been shown that sums of function compositions (in the form of a Neural Network) have the ability to approximate any function to any level of error." Please, please, please, always make sure to take into account the limitations. UAT only gives guarantees for continuous functions on a compact domain. $\endgroup$
    – Hyperplane
    Jan 26, 2023 at 21:40

2 Answers 2

4
$\begingroup$

Note that in Kolmogorov's Representation theorem, the choice of the outer function $\Phi$ depends on the function $f$ we wish to represent.

In contrast, the outer function in neural networks is the fixed activation function $\sigma$ that is used for any $f$ we wish to approximate. What we adjust here are the weights of the (inner) affine map. The universal approximation theorem makes the observation that this works arbitrarily well:

If $f$ is continuous and $\sigma$ is non-polynomial (e.g. sigmoidal or piecewise linear) then there exists a sequence of functions $f_n$ (each a neural network of one hidden layer and $n$ neurons) such that $|f_n - f| \rightarrow 0$ uniformly on every compact set as $n \rightarrow \infty$.

That is not to say that there isn't some specific activation function that does a better job (i.e. needs even less neurons):

In fact, there exists a special universal activation function $\sigma^*$ that is so powerful that we can approximate any continuous function on a compact set by a neural network of just one hidden layer consisting of one neuron! Great right? Well, not really.

This $\sigma^*$ is constructed by putting all polynomials with rational coefficients (a countable set!) next to each other and smoothly interpolating between them. It is entirely useless in practice.

So from my point of view, we mostly use the universal approximation theorem to be certain that the networks we could use in practice (for example using one hidden layer and ReLU activation) can at least in theory approximate any function arbitrarily well when the number of neurons goes to infinity.

$\endgroup$
2
$\begingroup$

They indeed seem similar but their different nature is emphasised in the formal statements and also reflects there intended use:

The Universal Approximation Theorem approximates any function $f(x)$ arbitrarily well in a compact subset $\mathcal{X}$ of $\mathbb{R}^{d}$. This explains why NNs or random forests or KNN can fit arbitrary training sets. You are able to approximate the underlying "generative model" of your data to arbitrary precision.

The Kolmogorov–Arnold representation theorem on the other hand is about representing a given function as a composition of univariate functions. The theorem is pertinent for casting a given function in another representation, but at least from the statement it seems to have no approximation power, as missing even one of the functions in the composition could potentially give unbounded errors.

$\endgroup$

You must log in to answer this question.

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