Why Deep Neural Networks for Function Approximation?

Abstract

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 $\epsilon$ uniformly over the interval. We show that shallow networks (i.e., networks whose depth does not depend on $\epsilon$) require $\Omega (\text{poly}(1/\epsilon ))$ neurons while deep networks (i.e., networks whose depth grows with $1/\epsilon$) require $\mathcal{O}(\text{polylog}(1/\epsilon ))$ 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.

The paper is published at the 5th International Conference on Learning Representations (ICLR)

Cited by in corpus (38)

• Learning to Optimize: Training Deep Neural Networks for Wireless Resource Management
• Deep Potentials for Materials Science
• Learning New Physics from a Machine
• A Review on Deep Learning in Medical Image Reconstruction
• Convergence of the Deep BSDE Method for Coupled FBSDEs
• The Modern Mathematics of Deep Learning
• SelectNet: Self-paced Learning for High-dimensional Partial Differential Equations
• Analyzing Upper Bounds on Mean Absolute Errors for Deep Neural Network Based Vector-to-Vector Regression
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• On Interpretability of Artificial Neural Networks: A Survey
• Learning Based User Scheduling in Reconfigurable Intelligent Surface Assisted Multiuser Downlink
• Deep Learning-based Prediction of Key Performance Indicators for Electrical Machine
• Interpretable Polynomial Neural Ordinary Differential Equations
• Meta-learning Pseudo-differential Operators with Deep Neural Networks
• DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow
• Mathematical Models of Overparameterized Neural Networks
• Training Shallow and Thin Networks for Acceleration via Knowledge Distillation with Conditional Adversarial Networks
• A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
• HINNPerf: Hierarchical Interaction Neural Network for Performance Prediction of Configurable Systems
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Data-Driven Optimal Control of Tethered Space Robot Deployment with Learning Based Koopman Operator
• CovNet: Covariance Networks for Functional Data on Multidimensional Domains
• Data Augmentation for Bayesian Deep Learning
• Universal Approximation with Quadratic Deep Networks
• Optimal Function Approximation with Relu Neural Networks
• Universal Approximation of Input-Output Maps by Temporal Convolutional Nets
• Layer Folding: Neural Network Depth Reduction using Activation Linearization
• Rational Neural Networks for Approximating Jump Discontinuities of Graph Convolution Operator
• A Polynomial-Based Approach for Architectural Design and Learning with Deep Neural Networks
• On a Sparse Shortcut Topology of Artificial Neural Networks
• Benchmarking Energy-Conserving Neural Networks for Learning Dynamics from Data
• The Teaching Dimension of Kernel Perceptron
• Learning to Embed Categorical Features without Embedding Tables for Recommendation
• Application of Bounded Total Variation Denoising in Urban Traffic Analysis
• Lyapunov-Net: A Deep Neural Network Architecture for Lyapunov Function Approximation
• No one-hidden-layer neural network can represent multivariable functions