Benefits of Depth in Neural Networks

By Matus Telgarsky. 2016

707 citations recorded by the source corpus.

For any positive integer $k$, there exist neural networks with $\Theta(k^3)$ layers, $\Theta(1)$ nodes per layer, and $\Theta(1)$ distinct parameters which can not be approximated by networks with $\mathcal{O}(k)$ layers unless they are exponentially large --- they must possess $\Omega(2^k)$ nodes. This result is proved here for a class of nodes termed "semi-algebraic gates" which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: $\Omega(2^{k^3})$ total tree nodes are required).

Subfields: Artificial Intelligence, Scaling & Learning Theory

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 Scaling & Learning Theory

Citations in the corpus

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].”
Robust Large Margin Deep Neural Networks (2016, background): “The work in [12] shows that for a given number of parameters and a given depth, there always exists a DNN that can be approximated by a shallower network only if the number of parameters in the shallow network is exponential in the number of layers of the deep network.”
Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, background): “These choices can be difﬁcult and only preliminary research has been done (see, e.g., Daniely (2017), Telgarsky (2016) and references therein).”
Are Markets Truly Efficient? Experiments Using Deep Learning Algorithms for Market Movement Prediction (2018, neutral): “This goal is supported by the Universal Approximation Theorem, which asserts that a neural net with a single hidden layer, a large number of nodes, with continuous, bounded, and non-constant activation functions can approximate any function arbitrarily closely ([7]), though this has been debated by ”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “More recently, interesting results have focused on the expressive ability of deeper and sparser architectures [9], [27], [48], [52].”
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.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…of work tries to understand how the expressive power of deep neural networks are related to their architecture, including the width of each layer and depth of the network (Telgarsky, 2015, 2016; Lu et al., 2017; Liang and Srikant, 2016; Yarotsky, 2017, 2018; Hanin, 2017; Hanin and Sellke, 2017).”
Generalization in Deep Learning (2017, background): “From the viewpoint of compact representation related to small capacity, it has been shown that deep model classes have an exponential advantage to represent certain natural target functions when compared to shallow model classes (Pascanu et al., 2014; Montufar et al., 2014; Livni et al., 2014; Telga”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “The remarkable results of NNs on complex tasks in computer vision and natural language processing inspired works on the expressive power of NNs (Co-hen et al., 2016; Cohen & Shashua, 2016; Raghu et al., 2016; Daniely et al., 2016; Poole et al., 2016; Montufar et al., 2014; Telgarsky, 2016).”
Mean Field Analysis of Neural Networks: A Law of Large Numbers (2018, background): “However, the existing literature is relatively limited, with only a few recent papers such as [5], [36], and [52].”
A Primer on Neural Network Models for Natural Language Processing (2015, methodology): “Similarly, Van de Cruys (2014) used the ranking loss in a selectional-preferences task, in which the network was trained to rank correct verb-object pairs above incorrect, automatically derived ones, and Weston, Bordes, Yakhnenko, and Usunier (2013) trained a model to score correct (head,relation,tr”
On the Spectral Bias of Neural Networks (2018, background): “There have been various results of the benefits of depth for efficient approximation (Poole et al., 2016; Telgarsky, 2016; Eldan & Shamir, 2016).”
Deep Learning for Mortgage Risk* (2016, background): “In early work, von Furstenberg (1969) establishes the influence on home mortgage default rates of variables such as income, loan age, and loan-to-value ratio.”
Graph Neural Networks Exponentially Lose Expressive Power for Node Classification (2019, methodology): “For such models, we have theoretical and empirical justiﬁcation that deep and non-linear architectures can enhance representation power (Telgarsky, 2016; Chen et al., 2018b; Zhou & Feng, 2018).”