# Optimal approximation of piecewise smooth functions using deep ReLU neural networks

arXiv: https://arxiv.org/abs/1709.05289 · HTML: https://mlsanity.com/paper/1709.05289/

## Key facts

- Cited by 179 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2017.

## Built on by (most cited first, 30 of 179)

- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Exponential Convergence of Deep Operator Networks for Elliptic Partial Differential Equations](https://mlsanity.com/paper/2112.08125/) (2021)
- [Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons](https://mlsanity.com/paper/2107.02397/) (2021)
- [An error analysis of generative adversarial networks for learning distributions](https://mlsanity.com/paper/2105.13010/) (2021)
- [Deep Learning Methods for Partial Differential Equations and Related Parameter Identification Problems](https://mlsanity.com/paper/2212.03130/) (2022)
- [Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input](https://mlsanity.com/paper/2305.18699/) (2023)
- [Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces](https://mlsanity.com/paper/2104.02746/) (2021)
- [Generalization Ability of Wide Neural Networks on ℝ](https://mlsanity.com/paper/2302.05933/) (2023)
- [Sumformer: Universal Approximation for Efficient Transformers](https://mlsanity.com/paper/2307.02301/) (2023)
- [Learning elliptic partial differential equations with randomized linear algebra](https://mlsanity.com/paper/2102.00491/) (2021)
- [wPINNs: Weak Physics informed neural networks for approximating entropy solutions of hyperbolic conservation laws](https://mlsanity.com/paper/2207.08483/) (2022)
- [Flow matching achieves almost minimax optimal convergence](https://mlsanity.com/paper/2405.20879/) (2024)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [A Deep Learning approach to Reduced Order Modelling of Parameter Dependent Partial Differential Equations](https://mlsanity.com/paper/2103.06183/) (2021)
- [Consistent Sparse Deep Learning: Theory and Computation](https://mlsanity.com/paper/2102.13229/) (2021)
- [Wasserstein Generative Learning of Conditional Distribution](https://mlsanity.com/paper/2112.10039/) (2021)
- [Theory of Deep Convolutional Neural Networks III: Approximating Radial Functions](https://mlsanity.com/paper/2107.00896/) (2021)
- [Approximation bounds for norm constrained neural networks with applications to regression and GANs](https://mlsanity.com/paper/2201.09418/) (2022)
- [Distribution learning via neural differential equations: a nonparametric statistical perspective](https://mlsanity.com/paper/2309.01043/) (2023)
- [The Geometry of Adversarial Training in Binary Classification](https://mlsanity.com/paper/2111.13613/) (2021)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [On the capacity of deep generative networks for approximating distributions](https://mlsanity.com/paper/2101.12353/) (2021)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Neural Network Architecture Beyond Width and Depth](https://mlsanity.com/paper/2205.09459/) (2022)
- [Lyapunov-Net: A Deep Neural Network Architecture for Lyapunov Function Approximation](https://mlsanity.com/paper/2109.13359/) (2021)
- [Mixtures of Neural Operators Reduce Active Complexity in Operator Learning](https://mlsanity.com/paper/2404.09101/) (2024)
- [Layer Folding: Neural Network Depth Reduction using Activation Linearization](https://mlsanity.com/paper/2106.09309/) (2021)
- [Neural Scaling Laws of Deep ReLU and Deep Operator Network: A Theoretical Study](https://mlsanity.com/paper/2410.00357/) (2024)
- [On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks](https://mlsanity.com/paper/2409.00901/) (2024)

## Abstract (arXiv)

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 L2. As a model class, we consider the set Eβ (mathbb Rd) of possibly discontinuous piecewise Cβ functions f : [-1/2, 1/2]d → mathbb R, where the different smooth regions of f are separated by Cβ hypersurfaces. For dimension d ≥ 2, regularity β > 0, and accuracy varepsilon > 0, we construct artificial neural networks with ReLU activation function that approximate functions from Eβ(mathbb Rd) up to L2 error of varepsilon. The constructed networks have a fixed number of layers, depending only on d and β, and they have O(varepsilon-2(d-1)/β) many nonzero weights, which we prove to be optimal. In addition to the optimality in terms of the number of weights, we show that in order to achieve the optimal approximation rate, one needs ReLU networks of a certain depth. Precisely, for piecewise Cβ(mathbb 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 circ τ. We show that in this case the approximation rate depends only on the dimension of the feature space and not the input dimension.