The Expressive Power of Neural Networks: A View from the Width

Abstract

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.

arXiv commentaccepted by NIPS 2017 ( with some typos fixed)

References in corpus (2)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• The loss surface of deep and wide neural networks

Cited by in corpus (38)

• Impact of Fully Connected Layers on Performance of Convolutional Neural Networks for Image Classification
• SpookyNet: Learning Force Fields with Electronic Degrees of Freedom and Nonlocal Effects
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• PINNeik: Eikonal solution using physics-informed neural networks
• Optimal approximation of continuous functions by very deep ReLU networks
• The power of deeper networks for expressing natural functions
• Nonlinear Approximation via Compositions
• Machine Learning for Prediction with Missing Dynamics
• Multi-scale Convolutional Neural Networks for Inverse Problems
• Hyperbolic compactification of M-theory and de Sitter quantum gravity
• Exponential Convergence of the Deep Neural Network Approximation for Analytic Functions
• Robust learning with implicit residual networks
• Can Increasing Input Dimensionality Improve Deep Reinforcement Learning?
• Elvet -- a neural network-based differential equation and variational problem solver
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Deep Learning in Wide-field Surveys: Fast Analysis of Strong Lenses in Ground-based Cosmic Experiments
• Sparse Weight Activation Training
• Model reduction in acoustic inversion by artificial neural network
• On approximating $\nabla f$ with neural networks
• A Machine Learning Approach to Correcting Atmospheric Seeing in Solar Flare Observations
• Robust Nonparametric Regression with Deep Neural Networks
• Deep KKL: Data-driven Output Prediction for Non-Linear Systems
• Approximation capabilities of neural networks on unbounded domains
• Universal Approximation with Quadratic Deep Networks
• A Differential Topological View of Challenges in Learning with Feedforward Neural Networks
• On Universal Approximation by Neural Networks with Uniform Guarantees on Approximation of Infinite Dimensional Maps
• Neural Quantum State Study of Fracton Models
• Dynamic Neural Diversification: Path to Computationally Sustainable Neural Networks
• A Bregman Learning Framework for Sparse Neural Networks
• Image Restoration Using Deep Regulated Convolutional Networks
• Learning to Embed Categorical Features without Embedding Tables for Recommendation
• Scalable Unidirectional Pareto Optimality for Multi-Task Learning with Constraints
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• Scalable Partial Explainability in Neural Networks via Flexible Activation Functions
• Parallel frequency function-deep neural network for efficient complex broadband signal approximation
• Fourier Neural Networks for Function Approximation
• Bayesian inference of numerical modeling-based morphodynamics: Application to a dam-break over a mobile bed experiment
• MixMix: All You Need for Data-Free Compression Are Feature and Data Mixing