Understanding Deep Neural Networks with Rectified Linear Units

Abstract

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give an algorithm to train a ReLU DNN with one hidden layer to *global optimality* with runtime polynomial in the data size albeit exponential in the input dimension. Further, we improve on the known lower bounds on size (from exponential to super exponential) for approximating a ReLU deep net function by a shallower ReLU net. Our gap theorems hold for smoothly parametrized families of "hard" functions, contrary to countable, discrete families known in the literature. An example consequence of our gap theorems is the following: for every natural number $k$ there exists a function representable by a ReLU DNN with $k^2$ hidden layers and total size $k^3$, such that any ReLU DNN with at most $k$ hidden layers will require at least $\frac{1}{2}{k}^{k+1}-1$ total nodes. Finally, for the family of ${\mathbb{R}}^n\to \mathbb{R}$ DNNs with ReLU activations, we show a new lowerbound on the number of affine pieces, which is larger than previous constructions in certain regimes of the network architecture and most distinctively our lowerbound is demonstrated by an explicit construction of a *smoothly parameterized* family of functions attaining this scaling. Our construction utilizes the theory of zonotopes from polyhedral theory.

The poly(data) exact training algorithm has been improved to now be applicable to any single hidden layer R^n-> R ReLU DNN and there is a cleaner pseudocode for it given on page 8. Also now on page 7 there is a more precise description about when and how the Zonotope construction improves on the Theorem 4 of this paper, arXiv:1402.1869

References in corpus (7)

• Sequence to Sequence Learning with Neural Networks
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• On the Expressive Power of Deep Neural Networks
• Reliably Learning the ReLU in Polynomial Time
• Bounding and Counting Linear Regions of Deep Neural Networks
• Distribution-Specific Hardness of Learning Neural Networks
• Deep Learning without Poor Local Minima

Cited by in corpus (46)

• Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations
• Script Identification in Natural Scene Image and Video Frame using Attention based Convolutional-LSTM Network
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• Impossibility Theorems for Feature Attribution
• Depth Creates No Bad Local Minima
• Controlling Neural Level Sets
• Deep Neural Networks with Trainable Activations and Controlled Lipschitz Constant
• Optimal Control Via Neural Networks: A Convex Approach
• On the Number of Linear Regions of Convolutional Neural Networks
• ConFoc: Content-Focus Protection Against Trojan Attacks on Neural Networks
• A Tropical Approach to Neural Networks with Piecewise Linear Activations
• Learning Hard Optimization Problems: A Data Generation Perspective
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• Robust Training and Initialization of Deep Neural Networks: An Adaptive Basis Viewpoint
• Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
• Deep Ritz revisited
• Chart Auto-Encoders for Manifold Structured Data
• Depth-Width Trade-offs for Neural Networks via Topological Entropy
• Approximation capabilities of neural networks on unbounded domains
• Hierarchical Decomposition of Nonlinear Dynamics and Control for System Identification and Policy Distillation
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• A representer theorem for deep neural networks
• A Deep Conditioning Treatment of Neural Networks
• SMILE: Self-Distilled MIxup for Efficient Transfer LEarning
• Geometry of Deep Convolutional Networks
• Depth separation beyond radial functions
• Pareto GAN: Extending the Representational Power of GANs to Heavy-Tailed Distributions
• Interpreting and Disentangling Feature Components of Various Complexity from DNNs
• DetectX -- Adversarial Input Detection using Current Signatures in Memristive XBar Arrays
• Error Estimation and Correction from within Neural Network Differential Equation Solvers
• Piecewise Linear Functions Representable with Infinite Width Shallow ReLU Neural Networks
• AReN: Assured ReLU NN Architecture for Model Predictive Control of LTI Systems
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
• A Constructive Approach for One-Shot Training of Neural Networks Using Hypercube-Based Topological Coverings
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• How Could Polyhedral Theory Harness Deep Learning?
• Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem
• On Symmetry and Initialization for Neural Networks
• A simple geometric proof for the benefit of depth in ReLU networks
• Analytical Probability Distributions and EM-Learning for Deep Generative Networks
• Almost Uniform Sampling From Neural Networks
• PINFER: Privacy-Preserving Inference for Machine Learning
• Exploiting Spline Models for the Training of Fully Connected Layers in Neural Network
• Fast Jacobian-Vector Product for Deep Networks