Representation Benefits of Deep Feedforward Networks

By Matus Telgarsky. 2015

264 citations recorded by the source corpus.

This note provides a family of classification problems, indexed by a positive integer $k$, where all shallow networks with fewer than exponentially (in $k$) many nodes exhibit error at least $1/6$, whereas a deep network with 2 nodes in each of $2k$ layers achieves zero error, as does a recurrent network with 3 distinct nodes iterated $k$ times. The proof is elementary, and the networks are standard feedforward networks with ReLU (Rectified Linear Unit) nonlinearities.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

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 Computer Vision and Pattern Recognition

Citations in the corpus

Representing smooth functions as compositions of near-identity functions with implications for deep network optimization (2018, background): “A number of authors have investigated how using deep architecture affects the set of functions computed by a network (see Montufar et al., 2014; Telgarsky, 2015; Poole et al., 2016; Mhaskar et al., 2016).”
On the Expressive Power of Deep Neural Networks (2016, background): “In response, several recent papers have focused on understanding the beneﬁts of depth for neural networks (Pas-canu et al., 2013; Montufar et al., 2014; Eldan and Shamir, 2015; Telgarsky, 2015; Martens et al., 2013; Bianchini and Scarselli, 2014).”
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).”
Benefits of Depth in Neural Networks (2016, background): “Most closely to the present work (excluding (Telgarsky, 2015), which is a vastly simplified account), Eldan and Shamir (2015) analyze 2- and 3-layer networks with general activation functions composed with affine mappings, showing separations which are exponential in the input dimension.”
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]).”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, background): “Forexample,aseriesofworktriestounderstandhowthe expressivepowerofdeepneuralnetworksarerelatedtotheirarchitecture,includingthewidth 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).”
Bounding and Counting Linear Regions of Deep Neural Networks (2017, background): “…range. researchers toward mathematical modeling of the expressive power of DNNs (Cybenko, 1989; Anthony & Bartlett, 1999; Pascanu et al., 2014; Mont ´ ufar et al., 2014; Bianchini & Scarselli, 2014; Eldan & Shamir, 2016; Telgarsky, 2015; Mhaskar et al., 2016; Raghu et al., 2017; Mont ´ ufar, 2017).”
Learning Functions: When Is Deep Better Than Shallow (2016, background): “Examples of functions that cannot be represented eﬃciently by shallow networks have been given very recently by [Telgarsky, 2015].”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “A line of research has shown that deeper neural networks have higher expressive power (Telgarsky, 2015, 2016; Lu et al., 2017; Liang and Srikant, 2016; Yarotsky, 2017, 2018; Hanin, 2017; Hanin and Sellke, 2017) than shallow neural networks.”
Learning Real and Boolean Functions: When Is Deep Better Than Shallow (2016, background): “We remark that a nice theorem was recently published (Telgarsky, 2015), showing that a certain family of classification problems with real-valued inputs cannot be approximated well by shallow networks with fewer than exponentially many nodes whereas a deep network achieves zero error.”
On the Expressive Power of Deep Learning: A Tensor Analysis (2015, unknown): “Telgarsky (2015) shows a simple construction of a depth d width 2 ReLU network that operates on one-dimensional inputs, realizing a function that cannot be approximated by ReLU networks of depth o ( d/ log d ) and width polynomial in d .”
Optimal approximation of piecewise smooth functions using deep ReLU neural networks (2017, methodology): “Since A := Hess f ( x 0 ) is symmetric, the spectral theorem shows that there is an orthonormal basis ( b 1 , . . . , b d ) of R d that consists of eigenvectors for A , and at least one of these eigenvectors needs to correspond to a non-zero eigenvalue; by rearranging we can assume By using the resu”
Error bounds for approximations with deep ReLU networks (2016, background): “Telgarsky 2015, 2016 provides specific examples of classification problems where deep networks are provably more efficient than shallow ones.”
The loss surface and expressivity of deep convolutional neural networks (2017, background): “Recently, many results have be 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; Poggio et al., 2016; Liang & Srikant, 2017; Mhaskar & Poggio, 2016;…”
Deep vs. shallow networks : An approximation theory perspective (2016, background): “• Examples of functions that cannot be represented eﬃciently by shallow networks have been given very recently by [27].”
The Expressive Power of a Class of Normalizing Flow Models (2020, background): “There is a body of work on analyzing the approximation properties of neural networks [Cybenko, 1989, Hornik et al., 1989, Hornik, 1991, Montufar et al., 2014, Telgarsky, 2015, Lu et al., 2017, Hanin, 2017, Raghu et al., 2017].”