Deep Neural Network Approximation Theory

2019/01/08 by Dennis Elbrachter, Dennis Elbrächter, Elbrächter, Dennis +7 · 70 citations
Computer Science · Mathematics · #Applied mathematics #Approximation error #Approximation theory #Artificial intelligence #Artificial neural network #Class (philosophy) #Combinatorics #Computer science #Deep learning #Discrete mathematics #Exponential function #Fractal #Function (biology) #Function approximation #Image and Signal Denoising Methods #Mathematical Approximation and Integration #Mathematical analysis #Mathematics #Multiplication (music) #Neural Networks and Applications #Topology (electrical circuits) #cs.IT #cs.LG #math.IT #stat.ML

paper · pdf · open access · doi:10.1109/tit.2021.3062161

published in IEEE Transactions on Information Theory 67(5), 2581-2623 (Institute of Electrical and Electronics Engineers) · minor revision

openalex publication_date 2021/02/24 · arxiv created 2021/03/12 · arxiv updated 2021/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

This paper develops fundamental limits of deep neural network learning by characterizing what is possible if no constraints are imposed on the learning algorithm and on the amount of training data. Concretely, we consider Kolmogorov-optimal approximation through deep neural networks with the guiding theme being a relation between the complexity of the function (class) to be approximated and the complexity of the approximating network in terms of connectivity and memory requirements for storing the network topology and the associated quantized weights. The theory we develop establishes that deep networks are Kolmogorov-optimal approximants for markedly different function classes, such as unit balls in Besov spaces and modulation spaces. In addition, deep networks provide exponential approximation accuracy - i.e., the approximation error decays exponentially in the number of nonzero weights in the network - of the multiplication operation, polynomials, sinusoidal functions, and certain smooth functions. Moreover, this holds true even for one-dimensional oscillatory textures and the Weierstrass function - a fractal function, neither of which has previously known methods achieving exponential approximation accuracy. We also show that in the approximation of sufficiently smooth functions finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.

Citations

• ImageNet classification with deep convolutional neural networks

Cited by

• Theory-to-Practice Gap for Neural Networks and Neural Operators
• Time-Frequency Analysis for Neural Networks
• Dropout Neural Network Training Viewed from a Percolation Perspective
• Data-driven modelling of autonomous and forced dynamical systems
• Parametric Numerical Integration with (Differential) Machine Learning
• Bases of Lebesgue spaces formed by neural networks
• Performance Guarantees for Quantum Neural Estimation of Entropies
• A Quantifier-Reversal Approximation Paradigm for Recurrent Neural Networks
• Incremental Generation is Necessary and Sufficient for Universality in Flow-Based Modelling
• Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data
• Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Network
• On Representing (Anti)Symmetric Functions
• Assessing the Advantages and Limitations of Quantum Neural Networks in Regression Tasks
• C¹-approximation with rational functions and rational neural networks
• Deviation Inequalities for Rényi Divergence Estimators via Variational Expression
• Sparse super resolution is Lipschitz continuous
• Selection dynamics for deep neural networks
• Sharp uniform approximation for spectral Barron functions by deep neural networks
• The phase diagram of approximation rates for deep neural networks
• Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems
• Convergence Rates of Variational Inference in Sparse Deep Learning
• Neural Drift Estimation for Ergodic Diffusions: Non-parametric Analysis and Numerical Exploration
• Convergence of Deep ReLU Networks
• Nonlocal techniques for the analysis of deep ReLU neural network approximations
• Neural Collaborative Filtering with Ontologies for Integrated Recommendation Systems. [europepmc]
• Design and Implementation of Low-Complexity Multiple Symbol Detection Algorithm Using Hybrid Stochastic Computing in Aircraft Wireless Communications. [europepmc]
• A novel deep learning technique for multi classify Alzheimer disease: hyperparameter optimization technique. [europepmc]

Related

• Optimal Approximation with Sparsely Connected Deep Neural Networks
• Approximation spaces of deep neural networks
• The universal approximation power of finite-width deep ReLU networks
• Optimal Approximation with Sparse Neural Networks and Applications
• Optimal Approximation Complexity of High-Dimensional Functions with Neural Networks