Optimal approximation of continuous functions by very deep ReLU networks

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\sim W^{\alpha },0<\alpha \le 1,$ and with necessarily discontinuous weight assignments. In particular, we prove that constant-width fully-connected networks of depth $L\sim W$ provide the fastest possible approximation rate $\Vert f-\tilde{f}{\Vert }_{\infty }=O({\omega }_f(O(W^{-2/\nu })))$ that cannot be achieved with less deep networks.

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

References in corpus (2)

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

Cited by in corpus (59)

• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• A Review on Deep Learning in Medical Image Reconstruction
• Deep Network Approximation for Smooth Functions
• ResNet with one-neuron hidden layers is a Universal Approximator
• Neural Network Approximation: Three Hidden Layers Are Enough
• The Modern Mathematics of Deep Learning
• Optimal Approximation Rate of ReLU Networks in terms of Width and Depth
• Nonlinear Approximation via Compositions
• Evolutional Deep Neural Network
• Int-Deep: A Deep Learning Initialized Iterative Method for Nonlinear Problems
• SelectNet: Self-paced Learning for High-dimensional Partial Differential Equations
• Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Deep ReLU network approximation of functions on a manifold
• A Constructive Prediction of the Generalization Error Across Scales
• Approximation and Estimation for High-Dimensional Deep Learning Networks
• Approximation spaces of deep neural networks
• On the capacity of deep generative networks for approximating distributions
• Factor Augmented Sparse Throughput Deep ReLU Neural Networks for High Dimensional Regression
• Exponential ReLU Neural Network Approximation Rates for Point and Edge Singularities
• On the rate of convergence of fully connected very deep neural network regression estimates
• Approximation bounds for norm constrained neural networks with applications to regression and GANs
• An error analysis of generative adversarial networks for learning distributions
• Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons
• Approximation in shift-invariant spaces with deep ReLU neural networks
• The gap between theory and practice in function approximation with deep neural networks
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Towards a regularity theory for ReLU networks -- chain rule and global error estimates
• Deep Quantile Regression: Mitigating the Curse of Dimensionality Through Composition
• Provable Memorization via Deep Neural Networks using Sub-linear Parameters
• Classification Logit Two-sample Testing by Neural Networks
• NEU: A Meta-Algorithm for Universal UAP-Invariant Feature Representation
• Optimal Nonparametric Inference via Deep Neural Network
• Solving PDEs on Unknown Manifolds with Machine Learning
• Partition of unity networks: deep hp-approximation
• Robust Nonparametric Regression with Deep Neural Networks
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
• MCMC-Net: Accelerating Markov Chain Monte Carlo with Neural Networks for Inverse Problems
• Error bounds for deep ReLU networks using the Kolmogorov--Arnold superposition theorem
• Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data
• Optimal Function Approximation with Relu Neural Networks
• Threshold-Based Retrieval and Textual Entailment Detection on Legal Bar Exam Questions
• Function approximation by deep networks
• Causal Inference of General Treatment Effects using Neural Networks with A Diverging Number of Confounders
• Size and Depth Separation in Approximating Benign Functions with Neural Networks
• Adaptive Learning on the Grids for Elliptic Hemivariational Inequalities
• On the approximation of functions by tanh neural networks
• Probabilistic partition of unity networks for high-dimensional regression problems
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• Collocation approximation by deep neural ReLU networks for parametric elliptic PDEs with lognormal inputs
• Universal Joint Approximation of Manifolds and Densities by Simple Injective Flows
• Sparsity-Probe: Analysis tool for Deep Learning Models
• Dialectical GAN for SAR Image Translation: From Sentinel-1 to TerraSAR-X
• Floating-Point Neural Networks Are Provably Robust Universal Approximators
• Approximating Probability Distributions by using Wasserstein Generative Adversarial Networks
• Deep Regression for Repeated Measurements
• Plant 'n' Seek: Can You Find the Winning Ticket?
• On the Existence of Universal Lottery Tickets