Why Deep Neural Networks for Function Approximation?

By Shiyu Liang, Rayadurgam Srikant. International Conference on Learning Representations, 2016

412 citations recorded by the source corpus.

Recently there has been much interest in understanding why deep neural networks are preferred to shallow networks. We show that, for a large class of piecewise smooth functions, the number of neurons needed by a shallow network to approximate a function is exponentially larger than the corresponding number of neurons needed by a deep network for a given degree of function approximation. First, we consider univariate functions on a bounded interval and require a neural network to achieve an approximation error of $\varepsilon$ uniformly over the interval. We show that shallow networks (i.e., networks whose depth does not depend on $\varepsilon$) require $\Omega(\text{poly}(1/\varepsilon))$ neurons while deep networks (i.e., networks whose depth grows with $1/\varepsilon$) require $\mathcal{O}(\text{polylog}(1/\varepsilon))$ neurons. We then extend these results to certain classes of important multivariate functions. Our results are derived for neural networks which use a combination of rectifier linear units (ReLUs) and binary step units, two of the most popular type of activation functions. Our analysis builds on a simple observation: the multiplication of two bits can be represented by a ReLU.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/87524c2bb725f967b7fac73442d6412b43d422d1

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

Citations in the corpus

Collapse of Deep and Narrow Neural Nets (2018, background): “In Liang & Srikant (2017) (see also Yarotsky (2017)), the authors claimed that for (cid:15) -approximation of a large class of piecewise smooth functions using the rectiﬁed linear unit (ReLU) max( x, 0) activation function, a multilayer NN using Θ(log(1 /(cid:15) )) layers only needs O (poly log(1…”
Optimization Landscape and Expressivity of Deep CNNs (2017, neutral): “…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., 2014; Raghu et al., 2017) While most of these results are…”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, background): “For example, a series of work tries to understand how the expressive power of deep neural networks are related to their architecture, including thewidth 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 Se”
Wide Activation for Efficient and Accurate Image Super-Resolution (2018, background): “The increasing of depth brings beneﬁts to representation power [2, 5, 18, 28] but meanwhile under-use the feature information from shallow layers (usually represent low-level features).”
Do Deep Convolutional Nets Really Need to be Deep and Convolutional? (2016, background): “Cohen and Shashua (2016); Liang and Srikant (2016) suggest that the representational efficiency of deep networks scales exponentially with depth, but it is unclear if this applies only to pathological problems, or is encountered in practice on data sets such as TIMIT and CIFAR.”
Learning to optimize: Training deep neural networks for wireless resource management (2017, background): “We note that in [32] the authors have shown that the function z = x2 can be approximated by a neural network with ReLU units and binary units.”
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].”
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks (2016, background): “As mentioned earlier, the re-sults and techniques in this section are closely related to the independent results of (Yarotsky, 2016; Liang & Srikant, 2016), but our emphasis is on L 2 rather than L ∞ approximation bounds, and we focus on somewhat different network architectures and function classes.”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “Neural Networks Substantial progress has been made to understand the expressive power of DNNs, in connection to the network depth (Telgarsky, 2015; 2016; Liang & Srikant, 2016; Yarotsky, 2017; 2018; Hanin, 2017), as well as network width (Lu et al., 2017; Hanin & Sellke, 2017).”
The Expressive Power of Neural Networks: A View from the Width (2017, background): “For example, Liang et al.[11] showed that in order to approximate a function which is Θ(log 1 )-order derivable with error universally, a deep network with O(log 1 ) layers and O(poly log 1 ) weights can do but Ω(poly 1 ) weights will be required if there is only o(log 1 ) layers.”
Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks (2017, background): “Liang and Srikant (2017) show that a sufficiently smooth univariate function can be approximated with error in L∞ by a network with ReLU and threshold gates with Θ(log(1/ )) layers and O(polylog(1/ )) weights, but that Ω(poly(1/ )) weights would be required if there were only o(log(1/ )) layers;…”
Learning to Optimize: Training Deep Neural Networks for Interference Management (2017, background): “Our construction of xy follows that in [28], while the construction of the division operation x/y appears to be new.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “For example, a series 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 ”
Deep Potentials for Materials Science (2022, background): “Many researchers have subsequently investigated the approximation ability of DNNs with P > 1 [59–62] and explained why the DNN is more successful (and widely used) than wide neural networks (many neurons in one hidden layer).”
Improving Non-autoregressive Neural Machine Translation with Monolingual Data (2020, background): “Since the neural networks can be near-perfect nonlinear function approximators (Liang and Srikant, 2016), we can expect an NAR model to learn the AR translation process quite well, as long as the model has enough capacity.”