Universality of Deep Convolutional Neural Networks

By Ding-Xuan Zhou. Applied and Computational Harmonic Analysis, 2018

601 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/26b7aff0afc190666e6c0a60613b1a57059f8dae

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Deep Network Approximation for Smooth Functions (2020, background): “, in terms of combinatorics [16], 73 topology [4], Vapnik-Chervonenkis (VC) dimension [3, 18, 9], fat-shattering dimension 74 [12, 1], information theory [17], classical approximation theory [7, 11, 2, 22, 21, 5, 23, 6], 75 etc.”
Graph Neural Networks Exponentially Lose Expressive Power for Node Classification (2019, unknown): “, 1989; Barron, 1993; Mhaskar, 1993; Sonoda & Murata, 2017; Yarotsky, 2017) and Convolutional Neural Networks (CNNs) (Petersen & Voigtlaender, 2018; Zhou, 2018; Oono & Suzuki, 2019).”
A Deep Learning Framework for Optimization of MISO Downlink Beamforming (2019, methodology): “Motivated by the above facts and the universal approximation theorem [43, 44], we propose a general DL framework to achieve not only near-optimal beamforming matrix, but also reduce complexity and latency as compared to the iterative methods.”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, background): “Moreover, it is also interestingtoexplorehowouroptimizationguaranteesofover-parameterizedneuralnetworks canbeintegratedwithexistinguniversalapproximationabilityresultssuchasHornik(1991), Telgarsky (2016), Lin and Jegelka (2018), Zhou (2019).”
HARK Side of Deep Learning - From Grad Student Descent to Automated Machine Learning (2019, background): “…i.e., a single hidden layer network containing a ﬁnite number of neurons can approximate continuous functions with arbitrary precision [37, 38] (ii) the complexity of the computed function by a neural network grows exponentially with its depth, i.e., for every additional hidden layer, one…”
Deep Learning in Human Activity Recognition with Wearable Sensors: A Review on Advances (2021, background): “Second, deep neural networks have been shown to be universal function approximators, capable of approximating almost any function given a large enough network and sufficient observations [77, 243, 340].”
Relu Deep Neural Networks and Linear Finite Elements (2018, background): “[13] presents rates of approximation by deep CNNs for functions in the Sobolev space H(Ω) with r > 2+d/2.”