The Power of Depth for Feedforward Neural Networks

By Ronen Eldan, Ohad Shamir. 2015

799 citations recorded by the source corpus.

We show that there is a simple (approximately radial) function on $\reals^d$, expressible by a small 3-layer feedforward neural networks, which cannot be approximated by any 2-layer network, to more than a certain constant accuracy, unless its width is exponential in the dimension. The result holds for virtually all known activation functions, including rectified linear units, sigmoids and thresholds, and formally demonstrates that depth -- even if increased by 1 -- can be exponentially more valuable than width for standard feedforward neural networks. Moreover, compared to related results in the context of Boolean functions, our result requires fewer assumptions, and the proof techniques and construction are very different.

Subfields: Artificial Intelligence, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

Citations in the corpus

The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “their ability to build complex functions with a much smaller number of parameters than needed for shallow networks [9–13].”
Understanding deep learning requires rethinking generalization (2016, background): “In contrast to existing depth separations (Delalleau & Bengio, 2011; Eldan & Shamir, 2016; Telgarsky, 2016; Cohen & Shashua, 2016) in function space, our result shows that even depth-2 networks of linear size can already represent any labeling of the training data.”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “Superior expressiveness of deeper networks, long suspected, is now conﬁrmed by theory, albeit for fairly limited learning problems (Eldan & Shamir, 2015; Raghu et al., 2016; Lee et al., 2017; Cohen et al., 2017; Daniely, 2017; Arora et al., 2018).”
Theoretical Guarantees for Model Auditing with Finite Adversaries (2019, background): “The latter results characterize how well certain functions can be approximated using neural networks, see [16, 17, 20–25] and references therein.”
Training Neural Networks Using Features Replay (2018, background): “The growth of the depths of the neural networks is one of the most critical factors contributing to the success of deep learning, which has been verified both in practice [8, 10] and in theory [2, 7, 35].”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, background): “The ﬁfth investigates the expressive ability of neural networks and analyzing what types of mappings they can learn (e.g. [Cohen et al., 2015, Eldan and Shamir, 2015]).”
Training Deeper Neural Machine Translation Models with Transparent Attention (2018, background): “While there are multiple approaches to increase capacity, deeper models have been shown to extract more expressive features (Mhaskar et al., 2016; Telgarsky, 2016; Eldan and Shamir, 2015), and have resulted in significant gains for vision tasks over the past few years (He et al.”
Benefits of Depth in Neural Networks (2016, background): “Standard neural networks appear to have received less study; closest to the present work is an investigation by Eldan and Shamir (2015) analyzing the case k = 2 when the dimension d is large, showing an exponential separation between 2- and 3-layer networks, a regime not handled by Theorem 1.”
Inductive Bias of Deep Convolutional Networks through Pooling Geometry (2016, background): “In recent years, a large body of research was devoted to proving existence of depth efﬁciency under different types of architectures (see for example [9, 23, 21, 28, 10, 24, 20]).”
Deep Learning for Mortgage Risk* (2016, background): “Campbell & Dietrich (1983), Cunningham & Hendershott (1986), Elul et al. (2010), Agarwal et al.”
On the Ability of Neural Nets to Express Distributions (2017, methodology): “This parallels —and is inspired by—the separation between 2-layer and 3-layer neural networks in [ES15].”
Optimization Landscape and Expressivity of Deep CNNs (2017, background): “…results have shown why deep networks are superior to shallow networks in terms of expressiveness (Delalleau & Bengio, 2011; Telgarsky, 2016; 2015; Eldan & Shamir, 2016; Safran & Shamir, 2017; Yarotsky, 2016; Pog-gio et al., 2016; Liang & Srikant, 2017; Mhaskar & Poggio, 2016; Montufar et al.,…”
Deep Semi-Supervised Anomaly Detection (2019, background): “The study of the theoretical foundations of deep learning is an active and ongoing research effort [43, 66, 14, 18, 46, 52, 73, 1, 5, 6, 70, 36].”
A survey on modern trainable activation functions (2020, background): “In (Eldan and Shamir, 2016) an activation function is clearly defined as any f : R → R function.”
Collapse of Deep and Narrow Neural Nets (2018, background): “In Eldan & Shamir (2016), the authors showed that a simple approximately radial function can be approximated by a small 3-layer feed-forward NN, but it cannot be approximated by any 2-layer network with the same accuracy irrespective of the activation function, unless its width is exponential in…”
Why Deep Neural Networks for Function Approximation? (2016, background): “Eldan & Shamir (2015) have shown that, to approximate a speciﬁc function, a two-layer network requires an exponential number of neurons in the input dimension, while a three-layer network requires a polynomial number of neurons.”