9
$\begingroup$

The universal approximation theorem is a quite famous result for neural networks, basically stating that under some assumptions, a function can be uniformly approximated by a neural network withing any accuracy.

Is there some analogous result that applies to convolutional neural networks?

$\endgroup$
  • 1
    $\begingroup$ Does anyone have an answer for such a good question? $\endgroup$ – Jie.Zhou Mar 2 '18 at 13:10
3
$\begingroup$

This is an interesting question, however, it does lack a proper clarification what is considered a convolutional neural network.

Is the only requirement that the network has to include a convolution operation? Does it have to only include convolution operations? Are pooling operations admitted? Convolutional networks used in practice use a combination of operations, often including fully connected layers (as soon as you have a fully connected layers, you have theoretical universal approximation ability).

To provide you with some answer, consider the following case: A fully connected layer with $D$ inputs and $K$ outputs is realized using a weight matrix $W \in \mathbb R ^{K\times D} $. You can simulate this operation using 2 convolution layers:

  1. The first one has $K\times D$ filters of shape $D$. Element $d$ of filter $k,d$ is equal to $W_{k,d}$, the rest are zeros. This layer transforms the input into $KD$-dimensional intermediate space where every dimension represents a product of a weight and its corresponding input.

  2. The second layer contains $K$ filters of shape $KD$. Elements $kD\ldots(k+1)D$ of filter $k$ are ones, the rest are zeros. This layer performs the summation of products from the previous layer.

Such convolutional network simulates a fully connected network and thus has the same universal approximation capabilities. It is up to you to consider how useful such an example is in practice, but I hope it answers your question.

$\endgroup$
  • $\begingroup$ Such a construction is rather obvious, but holds only with e.g. zero padding boundary conditions. With the more natural requirement of e.g. periodic boundary conditions (making the operator translation equivariant) it fails. $\endgroup$ – Jonas Adler May 24 '18 at 9:52
  • $\begingroup$ Yes, this obvious construction assumes convolution is only applied on the input (no padding). As I said, unless you specify what is allowed and what is not under your definition of CNN, I assume this is a valid approach. Also, note that the practical implications of the UAT are virtually none, so I'm not sure if it even makes sense dig too deep into this, specifying various versions of CNN and demonstrating something similar for each of them. $\endgroup$ – Jan Kukacka May 24 '18 at 10:15
2
$\begingroup$

It seems this question has been answered in the affirmative in this recent article by Dmitry Yarotsky: Universal approximations of invariant maps by neural networks.

The article shows that any translation equivariant function can be approximated arbitrarily well by a convolutional neural network given that it is sufficiently wide, in direct analogy to the classical universal approximation theorem.

$\endgroup$

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.