Better Neural Network Expressivity: Subdividing the Simplex

This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that ⌈ log2(n+1) ⌉ hidden layers are sufficient to compute all continuous piecewise linear (CPWL) functions on ℝn. Hertrich, Basu, Di Summa, and Skutella (NeurIPS ’21 / SIDMA ’23) conjectured that this result is optimal in the sense that there are CPWL functions on ℝn, like the maximum function, that require this depth. We disprove the conjecture and show that ⌈log3(n−1)⌉+1 hidden layers are sufficient to compute all CPWL functions on ℝn.