Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth

Abstract

A new network with super approximation power is introduced. This network is built with Floor ($\lfloor x\rfloor$) or ReLU ($\max \{0,x\}$) activation function in each neuron and hence we call such networks Floor-ReLU networks. For any hyper-parameters $N\in {\mathbb{N}}^{+}$ and $L\in {\mathbb{N}}^{+}$, it is shown that Floor-ReLU networks with width $\max \{d,5N+13\}$ and depth $64dL+3$ can uniformly approximate a Hölder function $f$ on $[0,1{]}^d$ with an approximation error $3\lambda d^{\alpha /2}{N}^{-\alpha \sqrt{L}}$, where $\alpha \in (0,1]$ and $\lambda$ are the Hölder order and constant, respectively. More generally for an arbitrary continuous function $f$ on $[0,1{]}^d$ with a modulus of continuity ${\omega }_f(\cdot )$, the constructive approximation rate is ${\omega }_f(\sqrt{d}{N}^{-\sqrt{L}})+2{\omega }_f(\sqrt{d})N^{-\sqrt{L}}$. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of ${\omega }_f(r)$ as $r\to 0$ is moderate (e.g., ${\omega }_f(r)\lesssim r^{\alpha }$ for Hölder continuous functions), since the major term to be considered in our approximation rate is essentially $\sqrt{d}$ times a function of $N$ and $L$ independent of $d$ within the modulus of continuity.

References in corpus (24)

• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Deep Network Approximation for Smooth Functions
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations
• A consensus-based model for global optimization and its mean-field limit
• Optimal approximation of continuous functions by very deep ReLU networks
• A Priori Estimates of the Population Risk for Two-layer Neural Networks
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• Deep Network Approximation Characterized by Number of Neurons
• Nonlinear Approximation via Compositions
• Approximation capability of two hidden layer feedforward neural networks with fixed weights
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
• The phase diagram of approximation rates for deep neural networks
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• A Priori Estimates of the Population Risk for Residual Networks
• Approximation spaces of deep neural networks
• Representation formulas and pointwise properties for Barron functions
• Exponential Convergence of the Deep Neural Network Approximation for Analytic Functions
• Approximation in shift-invariant spaces with deep ReLU neural networks
• Deep Learning via Dynamical Systems: An Approximation Perspective
• A consensus-based global optimization method for high dimensional machine learning problems

Cited by in corpus (15)

• Neural Network Approximation: Three Hidden Layers Are Enough
• Optimal Approximation Rate of ReLU Networks in terms of Width and Depth
• SelectNet: Self-paced Learning for High-dimensional Partial Differential Equations
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons
• Reproducing Activation Function for Deep Learning
• Solving PDEs on Unknown Manifolds with Machine Learning
• Convergence of Deep ReLU Networks
• The Discovery of Dynamics via Linear Multistep Methods and Deep Learning: Error Estimation
• Why Shallow Networks Struggle to Approximate and Learn High Frequencies
• Elementary superexpressive activations
• Don't Fear Peculiar Activation Functions: EUAF and Beyond
• Convergence of Deep Convolutional Neural Networks
• Stationary Density Estimation of Itô Diffusions Using Deep Learning
• Learning Quantized Neural Nets by Coarse Gradient Method for Non-linear Classification