The Expressive Power of Neural Networks: A View from the Width
By Zhou Lu, Hongming Pu, Feicheng Wang, Liwei Wang. 2017
1,013 citations recorded by the source corpus.
The expressive power of neural networks is important for understanding deep learning. Most existing works consider this problem from the view of the depth of a network. In this paper, we study how width affects the expressiveness of neural networks. Classical results state that depth-bounded (e.g. depth-$2$) networks with suitable activation functions are universal approximators. We show a universal approximation theorem for width-bounded ReLU networks: width-$(n+4)$ ReLU networks, where $n$ is the input dimension, are universal approximators. Moreover, except for a measure zero set, all functions cannot be approximated by width-$n$ ReLU networks, which exhibits a phase transition. Several recent works demonstrate the benefits of depth by proving the depth-efficiency of neural networks. That is, there are classes of deep networks which cannot be realized by any shallow network whose size is no more than an exponential bound. Here we pose the dual question on the width-efficiency of ReLU networks: Are there wide networks that cannot be realized by narrow networks whose size is not substantially larger? We show that there exist classes of wide networks which cannot be realized by any narrow network whose depth is no more than a polynomial bound. On the other hand, we demonstrate by extensive experiments that narrow networks whose size exceed the polynomial bound by a constant factor can approximate wide and shallow network with high accuracy. Our results provide more comprehensive evidence that depth is more effective than width for the expressiveness of ReLU networks.
Subfields: Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, 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 Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Andrew Zisserman
- Xiaogang Wang
- Jitendra Malik
- Alan L. Yuille
In Electrical and Electronic Engineering
- Tony Q. S. Quek
- Sang Hyun Lee
- Hoon Lee
- Lu Lu
- G. Em Karniadakis
- Zheng Wen
- Benjamin Van Roy
- Ian Osband
In Scaling & Learning Theory
- Quanquan Gu
- Jason D. Lee
- Aaron C. Courville
- Quoc V. Le
- Simon Shaolei Du
- Amnon Shashua
- Or Sharir
- Yuanbin Cao
Citations in the corpus
- Train Large, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers (2020, background): “, 2018), characterizes the expressivity of deep models (Raghu et al., 2017; Lu et al., 2017), and bounds the neural network generalization error (Du et al.”
- EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks (2019, background): “Although prior studies (Raghu et al., 2017; Lin & Jegelka, 2018; Sharir & Shashua, 2018; Lu et al., 2018) have shown that network deep and width are both important for ConvNets’ expressive power, it still remains an open question of how to effectively scale a ConvNet to achieve better efficiency and”
- Deep Learning for Distributed Optimization: Applications to Wireless Resource Management (2019, background): “Recently, it is revealed in [30] that, for any ε > 0 and Lebesgue-integrable function z C ( a ) , i.e., A | z C ( a ) | d a < ∞ , there exists a fully-connected DNN φ C ( a ; θ C ) with rec-tified linear unit (ReLU) activations that satisfy , the maximum number of nodes in hidden layers is bounded…”
- Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “For example, Lu et al. (2017) proved that except for a measure zero set, all functions cannot be approximated by ReLU networks with a width less than the input dimension.”
- 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).”
- On the Spectral Bias of Neural Networks (2018, background): “Lu et al. (2017) show that networks with bounded width are also universal approximators.”
- Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets (2020, background): “On the one hand, when one wants to approximate an arbitrary continuous function the number of required hidden units may be prohibitively large (Lu et al., 2017) as the error (cid:15) vanishes.”
- Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, background): “, the depth or width approaches infinity) are already universal function approximators [15, 30, 34].”
- A Review of Deep Learning with Special Emphasis on Architectures, Applications and Recent Trends (2019, background): “1: The Perceptron Learning Model an ANN provided that it has a sufficient number of neurons in a sufficient number of layers with a specific activation function [10] [11] [12] [13].”
- 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).”
- Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, methodology): “The proof of this lemma is inspired by the proof of Theorem 1 in Mei et al. (2016) and Lemma 3 in Fu et al. (2018).”
- 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.”
- 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].”
- Optimal approximation of continuous functions by very deep ReLU networks (2018, background): “Hanin and Sellke (2017); Lu et al. (2017) establish the universal approximation property and convergence rates for deep and “narrow” (fixed-width) networks.”
- Hypermodels for Exploration (2020, background): “O’Donoghue et al. (2018) consider such an approach for approximating Thompson sampling in reinforcement learning.”