Optimal approximation of piecewise smooth functions using deep ReLU neural networks

By Philipp Christian Petersen, Felix Voigtländer. Neural Networks, 2017

546 citations recorded by the source corpus.

We study the necessary and sufficient complexity of ReLU neural networks - in terms of depth and number of weights - which is required for approximating classifier functions in an Lp-sense. As a model class, we consider the set Eβ(Rd) of possibly discontinuous piecewise Cβ functions f:[-12,12]d→R, where the different "smooth regions" of f are separated by Cβ hypersurfaces. For given dimension d≥2, regularity β>0, and accuracy ε>0, we construct artificial neural networks with ReLU activation function that approximate functions from Eβ(Rd) up to an L2 error of ε. The constructed networks have a fixed number of layers, depending only on d and β, and they have O(ε-2(d-1)∕β) many nonzero weights, which we prove to be optimal. For the proof of optimality, we establish a lower bound on the description complexity of the class Eβ(Rd). By showing that a family of approximating neural networks gives rise to an encoder for Eβ(Rd), we then prove that one cannot approximate a general function f∈Eβ(Rd) using neural networks that are less complex than those produced by our construction. In addition to the optimality in terms of the number of weights, we show that in order to achieve this optimal approximation rate, one needs ReLU networks of a certain minimal depth. Precisely, for piecewise Cβ(Rd) functions, this minimal depth is given - up to a multiplicative constant - by β∕d. Up to a log factor, our constructed networks match this bound. This partly explains the benefits of depth for ReLU networks by showing that deep networks are necessary to achieve efficient approximation of (piecewise) smooth functions. Finally, we analyze approximation in high-dimensional spaces where the function f to be approximated can be factorized into a smooth dimension reducing feature map τ and classifier function g - defined on a low-dimensional feature space - as f=g∘τ. We show that in this case the approximation rate depends only on the dimension of the feature space and not the input dimension.

Subfields: Computational Mechanics, Ocean Engineering, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/8d4f727b181e14632b7dd15435e4f756e2926ad9

How researchers see this paper

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

In Computational Mechanics

In Ocean Engineering

In Statistical and Nonlinear Physics

Citations in the corpus

Crop Yield Prediction Using Deep Reinforcement Learning Model for Sustainable Agrarian Applications (2020, background): “For each RNN layer, a ReLU [57] activation function and L1 regularization [58], [59] Say initially at each time step t, the experience replay saves the agent’s experience resulting in a collection of speciﬁc sets of experiences.”
Collapse of Deep and Narrow Neural Nets (2018, methodology): “LU networks are inevitable in constructing ﬁnite element’s basis functions. This represents an application of deep ReLU networks in ﬁnite element method for solving PDEs. Also, many theoretical works [18, 38, 54] on the expressivity of ReLU networks rely heavily on deep and narrow networks in approx”
Neural network approximation (2020, unknown): “…2017), (Opschoor, Schwab & Zech 2019), (Bölcskei, Grohs, Kutyniok & Petersen 2019), (Gühring, Raslan & Kutyniok 2020), (Grohs, Perekrestenko, Elbrächter & Bölcskei 2019), (Petersen & Voigtlaender 2018), 78 (Petersen 2020), (Wang et al. 2018), (Shen et al. 2019), (Lu, Shen, Yang & Zhang 2020).”
Universality of Deep Convolutional Neural Networks (2018, background): “In particular, it was shown in [27, 28] that the rate of approximaton of some function classes by multi-layer fully connected neural networks may be achieved by networks with sparse connection matrices T , but the locations of the sparse connections are unknown.”
Machine Learning Approximation Algorithms for High-Dimensional Fully Nonlinear Partial Differential Equations and Second-order Backward Stochastic Differential Equations (2017, unknown): “Neural networks combine representational power (cf., e.g., Barron 1993; Cybenko 1989; Hornik et al. 1989; Petersen and Voigtlaender 2017) with computational feasibility (cf., e.g., Rumelhart et al. 1985).”
Posterior Concentration for Sparse Deep Learning (2018, background): “n a related result, Yarotsky (2017) shows that there exists a ReLU network that satisﬁes kf − fbDLk ∞ ≤ ε with sparsity s = c · ε− p α /log 2(1/ε) + 1 and depth L = c·(log 2(1/ε)+1) where c = c(p,α). Petersen and Voigtlaender (2017) extend this result to L2-smooth functions. We assume that p = O(1) ”
DGM: A deep learning algorithm for solving partial differential equations (2017, unknown): “…approximation power of neural networks we refer the interested reader to classical works [11, 25, 26, 39] and we also mention the recent work by [38], where the authors study the necessary and suﬃcient complexity of ReLU neural networks that is required for approximating classiﬁer functions in…”
Deep Network Approximation for Smooth Functions (2020, background): “, smooth functions [14, 13, 21, 8], piecewise 84 smooth functions [17], band-limited functions [15], continuous functions [22].”
Deep Neural Network Concepts for Background Subtraction: A Systematic Review and Comparative Evaluation (2018, methodology): “fferentactivationfunctionscan 2http://www.asimovinstitute.org/neural-network-zoo/ 6 Thierry Bouwmans, Sajid Javed, Maryam Sultana, Soon Ki Jung befoundasthesigmoidfunction[48],RectiﬁedLinearUnit(ReLU)[148],andProbabilistic ReLU (PReLU) [74]. Once the architecture is determined and the activation fun”
Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality (2018, methodology): “Petersen & Voigtlaender (2017) generalized the analysis by Yarotsky (2016) to the class of piece-wise smooth functions.”