Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks

Abstract

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.

Cited by in corpus (43)

• Efficient representation and approximation of model predictive control laws via deep learning
• Optimal approximation of continuous functions by very deep ReLU networks
• The Modern Mathematics of Deep Learning
• Understanding Deep Neural Networks with Rectified Linear Units
• Probabilistic performance validation of deep learning-based robust NMPC controllers
• Two-hidden-layer Feedforward Neural Networks are Universal Approximators: A Constructive Approach
• Efficient approximation of high-dimensional functions with neural networks
• DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow
• Training Shallow and Thin Networks for Acceleration via Knowledge Distillation with Conditional Adversarial Networks
• On the Modularity of Hypernetworks
• Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
• Theoretical guarantees for sampling and inference in generative models with latent diffusions
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
• What Do Deep Nets Learn? Class-wise Patterns Revealed in the Input Space
• Overview of image-to-image translation by use of deep neural networks: denoising, super-resolution, modality conversion, and reconstruction in medical imaging
• Deep Learning and Hierarchal Generative Models
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
• On the Privacy Risks of Cell-Based NAS Architectures
• Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis
• Optimal Function Approximation with Relu Neural Networks
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• Hierarchically Compositional Tasks and Deep Convolutional Networks
• Layer Folding: Neural Network Depth Reduction using Activation Linearization
• Function approximation by deep networks
• On the Optimal Memorization Power of ReLU Neural Networks
• A Systematic Comparison of Deep Learning Architectures in an Autonomous Vehicle
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Depth separation beyond radial functions
• Realizing data features by deep nets
• Realization of spatial sparseness by deep ReLU nets with massive data
• On the Approximation Power of Two-Layer Networks of Random ReLUs
• Theory-training deep neural networks for an alloy solidification benchmark problem
• Scalable Unidirectional Pareto Optimality for Multi-Task Learning with Constraints
• A lattice-based approach to the expressivity of deep ReLU neural networks
• A case where a spindly two-layer linear network whips any neural network with a fully connected input layer
• Meta Internal Learning
• Grow-Push-Prune: aligning deep discriminants for effective structural network compression
• On-lattice voxelated convolutional neural networks for prediction of phase diagrams and diffusion barriers in cubic alloys
• When Can Neural Networks Learn Connected Decision Regions?
• Bayesian Deep Learning Hyperparameter Search for Robust Function Mapping to Polynomials with Noise