# Function approximation by deep networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

## Built on by (most cited first, 10 of 10)

- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [CNNs Avoid Curse of Dimensionality by Learning on Patches](https://mlsanity.com/paper/2205.10760/) (2022)
- [CP-PINNs: Data-Driven Changepoints Detection in PDEs Using Online Optimized Physics-Informed Neural Networks](https://mlsanity.com/paper/2208.08626/) (2022)
- [Assessing the performance of correlation-based multi-fidelity neural emulators](https://mlsanity.com/paper/2512.02868/) (2025)
- [Cybersecurity threat detection based on a UEBA framework using Deep Autoencoders](https://mlsanity.com/paper/2505.11542/) (2025)
- [BrowNNe: Brownian Nonlocal Neurons & Activation Functions](https://mlsanity.com/paper/2406.15617/) (2024)
- [The Finite Element Neural Network Method: One Dimensional Study](https://mlsanity.com/paper/2501.12508/) (2025)
- [On the algorithmic construction of deep ReLU networks](https://mlsanity.com/paper/2506.19104/) (2025)

## Abstract (arXiv)

We show that deep networks are better than shallow networks at approximating functions that can be expressed as a composition of functions described by a directed acyclic graph, because the deep networks can be designed to have the same compositional structure, while a shallow network cannot exploit this knowledge. Thus, the blessing of compositionality mitigates the curse of dimensionality. On the other hand, a theorem called good propagation of errors allows to `lift' theorems about shallow networks to those about deep networks with an appropriate choice of norms, smoothness, etc. We illustrate this in three contexts where each channel in the deep network calculates a spherical polynomial, a non-smooth ReLU network, or another zonal function network related closely with the ReLU network.