Error bounds for approximations with deep ReLU networks

By Dmitry Yarotsky. 2016

1,527 citations recorded by the source corpus.

We study expressive power of shallow and deep neural networks with piece-wise linear activation functions. We establish new rigorous upper and lower bounds for the network complexity in the setting of approximations in Sobolev spaces. In particular, we prove that deep ReLU networks more efficiently approximate smooth functions than shallow networks. In the case of approximations of 1D Lipschitz functions we describe adaptive depth-6 network architectures more efficient than the standard shallow architecture.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, methodology): “Yarotsky (2017, 2018) and Bartlett, Harvey, Liaw, and Mehrabian (2017) are important building blocks for our results.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…of work tries to understand how the expressive power of deep neural networks are related to their architecture, including the width of each layer and depth of the network (Telgarsky, 2015, 2016; Lu et al., 2017; Liang and Srikant, 2016; Yarotsky, 2017, 2018; Hanin, 2017; Hanin and Sellke, 2017).”
The loss surface and expressivity of deep convolutional neural networks (2017, neutral): “…to shallow networks in terms of expressiveness (Delalleau & Bengio, 2011; Telgarsky, 2016; 2015; Eldan & Shamir, 2016; Safran & Shamir, 2017; Yarotsky, 2016; Poggio et al., 2016; Liang & Srikant, 2017; Mhaskar & Poggio, 2016; Montufar et al., 2014; Pascanu et al., 2014; Raghu et al., 2017).”
Deep Network Approximation for Smooth Functions (2020, methodology): “This conclusion is given in Theorem 3 of [44], which is a corollary of Theorem 4.”
Posterior Concentration for Sparse Deep Learning (2018, background): “ ≤ 94p2(α+1)2pN (L⋆ +⌈log 2p⌉) (16) such that kfb− f 0k∞ ≤ (2kf 0kHα +1)3 p+1N n +kf 0kHα2 αN−α/p. Proof. Apply Theorem 3 of Schmidt-Hieber (2017) with m = ⌊log 2(n)⌋. Remark5.1. In a related result, Yarotsky (2017) shows that there exists a ReLU network that satisﬁes kf − fbDLk ∞ ≤ ε with sparsity ”
Universality of Deep Convolutional Neural Networks (2018, methodology): “If we take r = d+1 2 + 2 as in our previous discussion, we see that for d ≥ 6, the deep net constructed in Theorem 1 of [29] for achieving an accuracy ∈ (0, 1) for approximating f ∈ C([0, 1]) has at least 2 −d/r free parameters and at least C0d 4 (log(1/ ) + d) layers.”
Neural-Fly enables rapid learning for agile flight in strong winds (2022, background): “Finally, since deep neural networks are universal approximators for polynomials [56], Theorem 3 immediately guarantees the expressiveness of our learning structure, i.e., ϕ ( x ) a ( w ) can approximate f ( x, w ) with arbitrary precision, where ϕ ( x ) is a deep neural network and ˆ a includes the…”
Activation functions in deep learning: A comprehensive survey and benchmark (2021, background): “The lower and upper bounds are established for network complexity to realize that the ReLU in deep networks approximates the smooth functions more efficiently as compared to shallow networks [128].”
Estimates on the generalization error of physics-informed neural networks for approximating a class of inverse problems for PDEs (2020, background): “e any continuous function can be approximated by DNNs, see [3, 16, 24, 63] and references therein, it is natural to use them as ansatz spaces for the solutions of PDEs, in particular by collocating the PDE residual at suitably chosen training points.”
Neural network approximation (2020, methodology): “A partial list of prominent papers using this method are (Yarotsky 2017), (Opschoor, Schwab & Zech 2019), (Bölcskei, Grohs, Kutyniok & Petersen 2019), (Gühring, Raslan & Kutyniok 2020), (Grohs, Perekrestenko, Elbrächter & Bölcskei 2019), (Petersen & Voigtlaender 2018),”
Optimization Landscape and Expressivity of Deep CNNs (2017, result): “…to shallow networks in terms of expressiveness (Delalleau & Bengio, 2011; Telgarsky, 2016; 2015; Eldan & Shamir, 2016; Safran & Shamir, 2017; Yarotsky, 2016; Pog-gio et al., 2016; Liang & Srikant, 2017; Mhaskar & Poggio, 2016; Montufar et al., 2014; Pascanu et al., 2014; Raghu et al., 2017)…”
ResNet with one-neuron hidden layers is a Universal Approximator (2018, background): “Also, by imposing stronger smoothness assumptions, this number may be reducible dramatically [2, 22, 33].”
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks (2016, background): “As mentioned earlier, the re-sults and techniques in this section are closely related to the independent results of (Yarotsky, 2016; Liang & Srikant, 2016), but our emphasis is on L 2 rather than L ∞ approximation bounds, and we focus on somewhat different network architectures and function classes.”
Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks (2017, background): “Yarotsky (2017) shows that any C n -function on [0 , 1] d can be approximated with (cid:15) error in L ∞ by a ReLU network with O (log(1 /(cid:15) )) layers and O (( 1 ) d/n log(1 /(cid:15) )) weights.”
On universal approximation and error bounds for Fourier Neural Operators (2021, background): “Finally, following (Yarotsky, 2017), we observe that the product ab of two numbers a, b can be expressed in the form”
Approximation rates for neural networks with general activation functions (2019, background): “Approximation estimates for multilayer convolutional neural networks are considered in [25] and multilayer networks with rectified linear activation functions in [24].”