Optimal Approximation Rate of ReLU Networks in terms of Width and Depth

Abstract

This paper concentrates on the approximation power of deep feed-forward neural networks in terms of width and depth. It is proved by construction that ReLU networks with width $\mathcal{O}(\max \{d\lfloor N^{1/d}\rfloor ,N+2\})$ and depth $\mathcal{O}(L)$ can approximate a Hölder continuous function on $[0,1{]}^d$ with an approximation rate $\mathcal{O}(\lambda \sqrt{d}(N^2{L}^2\ln N{)}^{-\alpha /d})$, where $\alpha \in (0,1]$ and $\lambda >0$ are Hölder order and constant, respectively. Such a rate is optimal up to a constant in terms of width and depth separately, while existing results are only nearly optimal without the logarithmic factor in the approximation rate. More generally, for an arbitrary continuous function $f$ on $[0,1{]}^d$, the approximation rate becomes $\mathcal{O}\left(\sqrt{d}{\omega }_f\right((N^2{L}^2\ln N{)}^{-1/d}))$, where ${\omega }_f(\cdot )$ is the modulus of continuity. We also extend our analysis to any continuous function $f$ on a bounded set. Particularly, if ReLU networks with depth $31$ and width $\mathcal{O}(N)$ are used to approximate one-dimensional Lipschitz continuous functions on $[0,1]$ with a Lipschitz constant $\lambda >0$, the approximation rate in terms of the total number of parameters, $W=\mathcal{O}(N^2)$, becomes $\mathcal{O}(\frac{\lambda }{W\ln W})$, which has not been discovered in the literature for fixed-depth ReLU networks.

References in corpus (15)

• On the Number of Linear Regions of Deep Neural Networks
• Deep Network Approximation for Smooth Functions
• The loss surface of deep and wide neural networks
• ResNet with one-neuron hidden layers is a Universal Approximator
• Optimal approximation of continuous functions by very deep ReLU networks
• Neural Network Approximation: Three Hidden Layers Are Enough
• A Priori Estimates of the Population Risk for Two-layer Neural Networks
• Deep Network Approximation Characterized by Number of Neurons
• Nonlinear Approximation via Compositions
• Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• The phase diagram of approximation rates for deep neural networks
• A Priori Estimates of the Population Risk for Residual Networks
• On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamics
• Make ${\ell }_1$ Regularization Effective in Training Sparse CNN

Cited by in corpus (7)

• Neural Network Approximation: Three Hidden Layers Are Enough
• Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Solving PDEs on Unknown Manifolds with Machine Learning
• Convergence of Deep ReLU Networks
• Synthesizing Particle-in-Cell Simulations Through Learning and GPU Computing for Hybrid Particle Accelerator Beamlines
• Convergence of Deep Convolutional Neural Networks