Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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:
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.
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.
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.
