Learning Functions: When Is Deep Better Than Shallow

By Hrushikesh Narhar Mhaskar, Qianli Liao, Tomaso A. Poggio. 2016

150 citations recorded by the source corpus.

While the universal approximation property holds both for hierarchical and shallow networks, we prove that deep (hierarchical) networks can approximate the class of compositional functions with the same accuracy as shallow networks but with exponentially lower number of training parameters as well as VC-dimension. This theorem settles an old conjecture by Bengio on the role of depth in networks. We then define a general class of scalable, shift-invariant algorithms to show a simple and natural set of requirements that justify deep convolutional networks.

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

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).”
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., 2015; Srivastava…”
Bounds on the Approximation Power of Feedforward Neural Networks (2018, background): “In particular, several works provided evidence that deeper networks perform better than shallow ones, given a fixed number of hidden units (Bianchini & Scarselli, 2014; Delalleau & Bengio, 2011; Liang & Srikant, 2017; Mhaskar et al., 2016; Pascanu et al., 2014; Telgarsky, 2015; 2016; Yarotsky, 2017)”
Optimal approximation of continuous functions by very deep ReLU networks (2018, background): “…Scarselli, 2014), Vapnik-Chervonenkis dimension (Bartlett et al., 1998; Sakurai, 1999) and fat-shattering dimension (Kearns and Schapire, 1990; Anthony and Bartlett, 2009), hierarchical decompositions of functions (Mhaskar et al., 2016), information theory (Petersen and Voigtlaender, 2017), etc.”
Hierarchical quantum classifiers (2018, background): “The hierarchical structure of deep neural networks can allow them to match the expressiveness of shallower models with exponentially fewer parameters [2, 3, 4].”
Model complexity of deep learning: a survey (2021, background): “In summary, the model reduction approaches reduce neural networks to some kind of functions [3, 13, 54, 67], and investigate the effects of model depth on the capacity to express function families.”
Deep Multiscale Model Learning (2018, background): “Many researches have focused on learning the expressivity of deep neural nets theoretically [19, 32, 18, 45, 44, 28].”
A high-bias, low-variance introduction to Machine Learning for physicists (2018, unknown): “Other works suggest that it is computationally and algorithmically easier to train deep networks rather than shallow, wider nets, though this is still an area of major controversy and active research (Mhaskar et al., 2016).”
Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations (2017, background): “well is in its infancy. Much of the work to date has focused on the problem of explaining and quantifying the expressivity − the ability to approximate a rich class of functions − of deep neural nets [1, 8, 9, 11, 12, 13, 15, 16, 17, 18]. Expressivity can be seen both as an eﬀect of both depth and w”
Impact of Fully Connected Layers on Performance of Convolutional Neural Networks for Image Classification (2019, methodology): “The eﬀect of deep or shallow networks on diﬀerent kind of datasets is well explored in the literature to study the behavioral interrelationship between depth of dataset and the CNN [12, 13].”
Depth Creates No Bad Local Minima (2017, background): “More accurately, a key aspect of the model classes in deep learning is the generalization property; despite its great expressivity, deep learning model classes can maintain great generalization properties (Livni et al., 2014; Mhaskar et al., 2016; Poggio et al., 2016).”
Why Does Deep and Cheap Learning Work So Well? (2016, background): “[15], Mhaskar and Poggio [16] focus on functions that have tree-like hierarchical compositional form, concluding that the flattening cost Cn is exponential for almost all functions in Sobolev space.”
Learning to optimize: Training deep neural networks for wireless resource management (2017, background): “In addition, Mhaskar et al. (2016) prove that “deep networks can approximate the class of compositional functions with the same accuracy as shallow networks but with exponentially lower number of training parameters”.”