# Why Deep Neural Networks for Function Approximation?

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

## Key facts

- Cited by 82 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2016.

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

- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition](https://mlsanity.com/paper/2102.01063/) (2021)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Interpretable Polynomial Neural Ordinary Differential Equations](https://mlsanity.com/paper/2208.05072/) (2022)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [Lyapunov-Net: A Deep Neural Network Architecture for Lyapunov Function Approximation](https://mlsanity.com/paper/2109.13359/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Layer Folding: Neural Network Depth Reduction using Activation Linearization](https://mlsanity.com/paper/2106.09309/) (2021)
- [Non-deep Networks](https://mlsanity.com/paper/2110.07641/) (2021)
- [Rethinking the Stability-Plasticity Trade-off in Continual Learning from an Architectural Perspective](https://mlsanity.com/paper/2506.03951/) (2025)
- [The Serial Scaling Hypothesis](https://mlsanity.com/paper/2507.12549/) (2025)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [A Simple Single-Scale Vision Transformer for Object Localization and Instance Segmentation](https://mlsanity.com/paper/2112.09747/) (2021)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [Born-Infeld (BI) for AI: Energy-Conserving Descent (ECD) for Optimization](https://mlsanity.com/paper/2201.11137/) (2022)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)
- [Statistical guarantees for sparse deep learning](https://mlsanity.com/paper/2212.05427/) (2022)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [Adaptive Ensemble Q-learning: Minimizing Estimation Bias via Error Feedback](https://mlsanity.com/paper/2306.11918/) (2023)
- [Polynomial Composition Activations: Unleashing the Dynamics of Large Language Models](https://mlsanity.com/paper/2411.03884/) (2024)
- [Sibyl: Adaptive and Extensible Data Placement in Hybrid Storage Systems Using Online Reinforcement Learning](https://mlsanity.com/paper/2205.07394/) (2022)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [Deep Neural Networks with ReLU-Sine-Exponential Activations Break Curse of Dimensionality in Approximation on H"older Class](https://mlsanity.com/paper/2103.00542/) (2021)
- [A Theory-Driven Self-Labeling Refinement Method for Contrastive Representation Learning](https://mlsanity.com/paper/2106.14749/) (2021)

## Abstract (arXiv)

Recently there has been much interest in understanding why deep neural networks are preferred to shallow networks. We show that, for a large class of piecewise smooth functions, the number of neurons needed by a shallow network to approximate a function is exponentially larger than the corresponding number of neurons needed by a deep network for a given degree of function approximation. First, we consider univariate functions on a bounded interval and require a neural network to achieve an approximation error of varepsilon uniformly over the interval. We show that shallow networks (i.e., networks whose depth does not depend on varepsilon) require Omega(poly(1/varepsilon)) neurons while deep networks (i.e., networks whose depth grows with 1/varepsilon) require O(polylog(1/varepsilon)) neurons. We then extend these results to certain classes of important multivariate functions. Our results are derived for neural networks which use a combination of rectifier linear units (ReLUs) and binary step units, two of the most popular type of activation functions. Our analysis builds on a simple observation: the multiplication of two bits can be represented by a ReLU.