A lattice-based approach to the expressivity of deep ReLU neural networks

2019/02/28 by Vincent Corlay, Joseph J. Boutros, Corlay, Vincent +5
Computer Science · Physics and Astronomy · #FOS: Computer and information sciences #Fuzzy Logic and Control Systems #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.1902.11294

openalex publication_date 2019/02/28 · openalex created_date 2019/03/02 · openalex updated_date 2026/07/28

Abstract

We present new families of continuous piecewise linear (CPWL) functions in Rn having a number of affine pieces growing exponentially in n. We show that these functions can be seen as the high-dimensional generalization of the triangle wave function used by Telgarsky in 2016. We prove that they can be computed by ReLU networks with quadratic depth and linear width in the space dimension. We also investigate the approximation error of one of these functions by shallower networks and prove a separation result. The main difference between our functions and other constructions is their practical interest: they arise in the scope of channel coding. Hence, computing such functions amounts to performing a decoding operation.

Citations

• On the Expressive Power of Deep Neural Networks
• Depth Separation for Neural Networks
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks

Related

• Better Neural Network Expressivity: Subdividing the Simplex
• Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ²
• Optimal approximation of continuous functions by very deep ReLU networks
• Theoretical Exploration of Solutions of Feedforward ReLU Networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width