Towards Lower Bounds on the Depth of ReLU Neural Networks

Abstract

We contribute to a better understanding of the class of functions that can be represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning any function. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). As a by-product of our investigations, we settle an old conjecture about piecewise linear functions by Wang and Sun (2005) in the affirmative. We also present upper bounds on the sizes of neural networks required to represent functions with logarithmic depth.

Authors' accepted manuscript for SIAM Journal on Discrete Mathematics. A preliminary conference version appeared at NeurIPS 2021

References in corpus (5)

• Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study
• Reliably Learning the ReLU in Polynomial Time
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• Size and Depth Separation in Approximating Benign Functions with Neural Networks
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums

Cited by in corpus (2)

• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation