Depth-Bounds for Neural Networks via the Braid Arrangement
This work addresses a foundational theoretical question in neural network architecture for researchers in machine learning theory, providing incremental progress on lower bounds for layer depth.
The paper tackles the problem of determining the minimum number of hidden layers needed in ReLU networks to exactly represent continuous piecewise linear functions, proving a lower bound of Ω(log log d) layers for representing the maximum of d numbers under specific assumptions and showing that 3 layers are necessary for 5 numbers.
We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on $\mathbb{R}^d$. While the question has been resolved in special cases, the best known lower bound in general is still 2. We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan. For such neural networks, we prove a non-constant lower bound of $Ω(\log\log d)$ hidden layers required to exactly represent the maximum of $d$ numbers. Additionally, under our assumption, we provide a combinatorial proof that 3 hidden layers are necessary to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far. Finally, we show that a natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that a rank-3 maxout layer followed by a rank-2 maxout layer is sufficient to represent the maximum of 7 numbers.