Source-linked AI summary
Universality of Deep Convolutional Neural Networks
Ding-Xuan Zhou
TL;DR
Deep CNNs lack a theoretical account of which functions their convolutional architectures can approximate. This paper develops a rigorous theory and proves that sufficiently deep CNNs universally approximate continuous functions, with a parameter estimate independent of input dimension.
Problem
For deep CNNs without fully connected layers, it was unknown which functions their convolutional structures could approximate, limiting theoretical understanding of their efficiency.
Method
The paper establishes approximation theory for deep CNNs by factorizing finitely supported sequences into convolutions of filter masks.
Results
Deep CNNs can approximate any continuous function on a compact subset of R^d to arbitrary accuracy, with a free-parameter estimate independent of d.
Takeaways & Limitations
The results provide a rigorous theoretical foundation for deep CNN approximation and evidence for the power of convolutions in high-dimensional data.
Takeaways & Limitations
Approximation in C(Ω) is restricted to Sobolev spaces embedded in continuous functions, and approximation rates require r > d.
Abstract
from arXiv · showhide
Deep learning has been widely applied and brought breakthroughs in speech recognition, computer vision, and many other domains. The involved deep neural network architectures and computational issues have been well studied in machine learning. But there lacks a theoretical foundation for understanding the approximation or generalization ability of deep learning methods generated by the network architectures such as deep convolutional neural networks having convolutional structures. Here we show that a deep convolutional neural network (CNN) is universal, meaning that it can be used to approximate any continuous function to an arbitrary accuracy when the depth of the neural network is large enough. This answers an open question in learning theory. Our quantitative estimate, given tightly in terms of the number of free parameters to be computed, verifies the efficiency of deep CNNs in dealing with large dimensional data. Our study also demonstrates the role of convolutions in deep CNNs.
1 Introduction and Main Results
The paper develops a rigorous theory showing that purely convolutional deep CNNs can approximate every continuous function on compact domains, while achieving quantitative efficiency through sparse convolutional structures. It also establishes approximation rates for Sobolev functions and explains convolution’s role in efficient feature extraction.
- Parameter efficiency: (5s + 2)J + 2d −2s −1 free parameters are sufficient for the considered deep CNN, demonstrating computational efficiency relative to fully connected networks.Each deep-CNN iteration involves 3s + 2 free parameters, while fully connected layers use d_jd_{j−1} parameters for their full connection matrices.
- Universality: Deep CNNs can approximate any continuous function on a compact subset of R^d to arbitrary accuracy when their depth is sufficiently large.This is the paper’s first main universality result for convolutional networks without fully connected layers.
- Approximation rates: The paper derives approximation rates for deep CNNs representing functions in Sobolev spaces H^r(Ω) with integer r > 2 + d/2.The stated setting assumes 2 ≤ s ≤ d, Ω ⊆ [−1, 1]^d, and f is the restriction of an H^r(R^d) function.
- Parameter efficiency: 75d free parameters provide a relative-error bound under the paper’s choice L = 1 and τ = 1/2, with the bound decreasing as dimension d increases.The passage presents this dimension-dependent parameter behavior as a new observation for deep CNNs and links it to their approximation ability.
- Theoretical contribution: The theory overcomes convolutional sparsity by factorizing arbitrary finitely supported sequences into convolutions of filter masks.This factorization supplies the key mechanism distinguishing the analysis from results for fully connected neural networks.