Optimal approximation of continuous functions by very deep ReLU networks

2018/02/10 by Dmitry Yarotsky, Yarotsky, Dmitry · 28 citations
Computer Science · Physics and Astronomy · #FOS: Computer and information sciences #Machine Learning and Algorithms #Model Reduction and Neural Networks #Neural Networks and Applications #Neural and Evolutionary Computing (cs.NE) #cs.NE

paper · pdf · doi:10.48550/arxiv.1802.03620

21 pages. In v2: more discussion of phase diagram, described approximation for $p\in(\frac{1}ν,\frac{2}ν)$

openalex publication_date 2018/02/10 · arxiv created 2018/06/06 · arxiv updated 2018/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider approximations of general continuous functions on finite-dimensional cubes by general deep ReLU neural networks and study the approximation rates with respect to the modulus of continuity of the function and the total number of weights W in the network. We establish the complete phase diagram of feasible approximation rates and show that it includes two distinct phases. One phase corresponds to slower approximations that can be achieved with constant-depth networks and continuous weight assignments. The other phase provides faster approximations at the cost of depths necessarily growing as a power law L∼ W^α, 0<α≤ 1, and with necessarily discontinuous weight assignments. In particular, we prove that constant-width fully-connected networks of depth L∼ W provide the fastest possible approximation rate ‖f-\widetilde f‖_∞ = O(ω_f(O(W^-2/ν))) that cannot be achieved with less deep networks.

Citations

• Benefits of depth in neural networks
• The Expressive Power of Neural Networks: A View from the Width
• Approximating Continuous Functions by ReLU Nets of Minimal Width

Cited by

• Approximation bounds for norm constrained deep neural networks
• Incremental Generation is Necessary and Sufficient for Universality in Flow-Based Modelling
• Minimum Width of Deep Narrow Networks for Universal Approximation
• General transformation neural networks: A class of parametrized functions for high-dimensional function approximation
• On Universality of Deep Equivariant Networks
• xLSTM Scaling Laws: Competitive Performance with Linear Time-Complexity
• Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributions
• Error analysis for learning the time-stepping operator of evolutionary PDEs
• Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data
• Deep Uzawa for Kinetic Transport with Lagrange-Enforced Boundaries
• Some Super-approximation Rates of ReLU Neural Networks for Korobov Functions
• Sharp uniform approximation for spectral Barron functions by deep neural networks
• Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networks
• Causal Inference of General Treatment Effects using Neural Networks with A Diverging Number of Confounders
• Approximation and Estimation for High-Dimensional Deep Learning Networks
• On Universality Classes of Equivariant Networks
• Why and When Deep is Better than Shallow: Implementation-Agnostic State-Transition Model of Deep Learning
• Approximation theory for 1-Lipschitz ResNets
• Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View
• Adaptive Learning on the Grids for Elliptic Hemivariational Inequalities
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Contextures: Representations from Contexts
• Approximation spaces of deep neural networks
• Semiparametric M-estimation with overparameterized neural networks
• Approximation Rates in Besov Norms and Sample-Complexity of Kolmogorov-Arnold Networks with Residual Connections
• Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective
• Statistically guided deep learning
• Minimum width for universal approximation using squashable activation functions
• Nonlocal techniques for the analysis of deep ReLU neural network approximations

Related

• Optimal Approximation Complexity of High-Dimensional Functions with Neural Networks
• The universal approximation power of finite-width deep ReLU networks
• Deep ReLU neural networks in high-dimensional approximation
• Approximation in L^p(μ) with deep ReLU neural networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width