Achieving Sharp Upper Bounds on the Expressive Power of Neural Networks via Tropical Polynomials

The expressive power of neural networks describes the ability to represent or approximate complex functions. The number of linear regions is the standard and most natural measure of expressive power. However, a major challenge in utilizing the number of linear regions as a measure of expressive power is the exponential gap between the theoretical upper and lower bounds, which becomes more pronounced as the neural network capacity increases. In this article, we aim to derive a sharp upper bound on piecewise linear neural networks (PLNNs) to bridge this gap. Specifically, we first establish the relationship between tropical polynomials and PLNNs. In the unexpanded tropical polynomials form, we make the proposition that hyperplanes are not all in the general positions, thereby reducing the number of intersecting hyperplanes. We propose a rank-based approach and present the empirical analysis that this approach outperforms previous Zaslavsky's theorem-based methods. In the expanded tropical polynomials form, accounting for limitations in weight initialization and model computational precision, we raise the concept that the values range of each term is bounded. We propose a precision-based approach that transforms the approximate exponential growth of the number of linear regions into polynomial growth with width, which is effective at larger layer widths. Finally, we compare the number of linear regions that can be represented by each hidden layer in both forms and derive a sharp upper bound for PLNNs. Empirical analysis and experimental results provide compelling evidence for the efficacy and feasibility of this sharp upper bound on both simulated experiments and real datasets.