# Understanding Deep Neural Networks with Rectified Linear Units

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

## Key facts

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

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

- [Activation Functions in Deep Learning: A Comprehensive Survey and Benchmark](https://mlsanity.com/paper/2109.14545/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification](https://mlsanity.com/paper/2110.14012/) (2021)
- [Impossibility Theorems for Feature Attribution](https://mlsanity.com/paper/2212.11870/) (2022)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Availability Attacks Create Shortcuts](https://mlsanity.com/paper/2111.00898/) (2021)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Out-of-distribution Detection with Implicit Outlier Transformation](https://mlsanity.com/paper/2303.05033/) (2023)
- [Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learning](https://mlsanity.com/paper/2406.06158/) (2024)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Locally Sparse Neural Networks for Tabular Biomedical Data](https://mlsanity.com/paper/2106.06468/) (2021)
- [Don't trust your eyes: on the (un)reliability of feature visualizations](https://mlsanity.com/paper/2306.04719/) (2023)
- [On the Existence of Universal Lottery Tickets](https://mlsanity.com/paper/2111.11146/) (2021)
- [Disentangling Epistemic and Aleatoric Uncertainty in Reinforcement Learning](https://mlsanity.com/paper/2206.01558/) (2022)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [Mixtures of Laplace Approximations for Improved Post-Hoc Uncertainty in Deep Learning](https://mlsanity.com/paper/2111.03577/) (2021)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Pareto GAN: Extending the Representational Power of GANs to Heavy-Tailed Distributions](https://mlsanity.com/paper/2101.09113/) (2021)
- [Adversarial Robustness against Multiple and Single lp-Threat Models via Quick Fine-Tuning of Robust Classifiers](https://mlsanity.com/paper/2105.12508/) (2021)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [Searching for Fast Model Families on Datacenter Accelerators](https://mlsanity.com/paper/2102.05610/) (2021)

## Abstract (arXiv)

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give an algorithm to train a ReLU DNN with one hidden layer to *global optimality* with runtime polynomial in the data size albeit exponential in the input dimension. Further, we improve on the known lower bounds on size (from exponential to super exponential) for approximating a ReLU deep net function by a shallower ReLU net. Our gap theorems hold for smoothly parametrized families of "hard" functions, contrary to countable, discrete families known in the literature. An example consequence of our gap theorems is the following: for every natural number k there exists a function representable by a ReLU DNN with k2 hidden layers and total size k3, such that any ReLU DNN with at most k hidden layers will require at least frac12kk+1-1 total nodes. Finally, for the family of ℝn→ ℝ DNNs with ReLU activations, we show a new lowerbound on the number of affine pieces, which is larger than previous constructions in certain regimes of the network architecture and most distinctively our lowerbound is demonstrated by an explicit construction of a *smoothly parameterized* family of functions attaining this scaling. Our construction utilizes the theory of zonotopes from polyhedral theory.