A Lower Bound for the Number of Linear Regions of Ternary ReLU Regression Neural Networks
This provides a theoretical explanation for the practical success of ternary neural networks in reducing computational complexity and memory consumption, though it is incremental as it extends known theoretical results to ternary networks.
The paper tackles the theoretical understanding of ternary neural networks by analyzing their expressivity through the number of linear regions, proving that this number grows polynomially with width and exponentially with depth, similar to standard networks, and showing that squaring the width or doubling the depth achieves a lower bound comparable to general ReLU networks.
With the advancement of deep learning, reducing computational complexity and memory consumption has become a critical challenge, and ternary neural networks (NNs) that restrict parameters to $\{-1, 0, +1\}$ have attracted attention as a promising approach. While ternary NNs demonstrate excellent performance in practical applications such as image recognition and natural language processing, their theoretical understanding remains insufficient. In this paper, we theoretically analyze the expressivity of ternary NNs from the perspective of the number of linear regions. Specifically, we evaluate the number of linear regions of ternary regression NNs with Rectified Linear Unit (ReLU) for activation functions and prove that the number of linear regions increases polynomially with respect to network width and exponentially with respect to depth, similar to standard NNs. Moreover, we show that it suffices to either square the width or double the depth of ternary NNs to achieve a lower bound on the maximum number of linear regions comparable to that of general ReLU regression NNs. This provides a theoretical explanation, in some sense, for the practical success of ternary NNs.