Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks

By Itay Safran, Ohad Shamir. 2016

186 citations recorded by the source corpus.

We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger. This includes indicators of balls and ellipses; non-linear functions which are radial with respect to the $L_1$ norm; and smooth non-linear functions. We also show that these gaps can be observed experimentally: Increasing the depth indeed allows better learning than increasing width, when training neural networks to learn an indicator of a unit ball.

Subfields: Computational Mechanics, Statistical and Nonlinear Physics

How researchers see this paper

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

In Computational Mechanics

In Statistical and Nonlinear Physics

Citations in the corpus

Optimal approximation of continuous functions by very deep ReLU networks (2018, background): “Depth-separation results for some explicit families of functions have been obtained in Safran and Shamir (2016); Telgarsky (2016).”
Training Shallow and Thin Networks for Acceleration via Knowledge Distillation with Conditional Adversarial Networks (2017, background): “More recent theoretical results show depth is indeed beneficial for the expressive capacity of networks [9, 39, 23, 33].”
Mixing Complexity and its Applications to Neural Networks (2017, background): “This has led many researchers to attempt to understand the reasons for the astonishing success despite the proven hardness (Shamir, 2016; Safran & Shamir, 2016; Eldan & Shamir, 2016; Daniely et al., 2016; Raghu et al., 2016; Arora et al., 2014; Livni et al., 2014).”
Training Student Networks for Acceleration with Conditional Adversarial Networks (2018, background): “More recent theoretical results show depth is indeed beneﬁcial for the expressive capacity of networks [8, 22, 29, 34].”
Optimization Landscape and Expressivity of Deep CNNs (2017, background): “…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., 2014; Pascanu et al.,…”
The loss surface and expressivity of deep convolutional neural networks (2017, background): “…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; Montufar et al., 2014; Pascanu et al.,…”
Is Out-of-Distribution Detection Learnable? (2022, background): “Note that in some works [78], bg is fixed to 0.”
Optimal approximation of piecewise smooth functions using deep ReLU neural networks (2017, methodology): “Nevertheless, our result still yields a generalization of that in [46, Theorem 4]: First, we are able to cover approximation in L for arbitrary p ∈ [1,∞), while in [46], only the case p = 2 is considered.”