Optimal approximation of piecewise smooth functions using deep ReLU neural networks

Westudy 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 L-p-sense. As a model class, we consider the set epsilon(beta) (R-d) of possibly discontinuous piecewise C-beta functions f : [-1/2, 1/2](d). R, where the different smooth regions'' of f are separated by C-beta hypersurfaces. For given dimension d >= 2, regularity beta > 0, and accuracy epsilon > 0, we construct artificial neural networks with ReLU activation function that approximate functions from epsilon beta(R-d) up to an L-2 error of e. The constructed networks have a fixed number of layers, depending only on d and beta, and they have O(epsilon (2(d- 1)/ beta)) 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 epsilon(beta) (R-d). By showing that a family of approximating neural networks gives rise to an encoder for epsilon(beta)(R-d), we then prove that one cannot approximate a general function f is an element of epsilon(beta) (R-d) 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-beta(R-d) functions, this minimal depth is given - up to a multiplicative constant - by beta/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 tau and classifier function g defined on a low-dimensional feature space - as f = g o tau. We show that in this case the approximation rate depends only on the dimension of the feature space and not the input dimension. (C) 2018 Elsevier Ltd. All rights reserved.