19
$\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 within any accuracy.

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

$\endgroup$
0

3 Answers 3

10
$\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$
8
$\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$
2
  • 1
    $\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$ May 24, 2018 at 9:52
  • 1
    $\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$ May 24, 2018 at 10:15
6
$\begingroup$

See the paper Universality of Deep Convolutional Neural Networks by Ding-Xuan Zhou, who shows that convolutional neural networks are universal, that is, they can approximate any continuous function to an arbitrary accuracy when the depth of the neural network is large enough.

$\endgroup$
1
  • 1
    $\begingroup$ This seems to assume zero boundary conditions, so the result should be the same as jan-kukacka mentioned $\endgroup$ Jan 6, 2020 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.