# A Lower Bound for the Number of Linear Regions of Ternary ReLU Regression Neural Networks

arXiv: https://arxiv.org/abs/2507.16079 · HTML: https://mlsanity.com/paper/2507.16079/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 14 references that are in the map.
- First posted on arXiv 21 Jul 2025.

## Builds on (most cited first, 10 of 10)

- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Ternary Weight Networks](https://mlsanity.com/paper/1605.04711/) (2016)
- [ReActNet: Towards Precise Binary Neural Network with Generalized Activation Functions](https://mlsanity.com/paper/2003.03488/) (2020)
- [BinaryBERT: Pushing the Limit of BERT Quantization](https://mlsanity.com/paper/2012.15701/) (2020)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Theoretical Analysis of the Advantage of Deepening Neural Networks](https://mlsanity.com/paper/2009.11479/) (2020)

## Abstract (arXiv)

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 first double the width, then either square the width or double the depth of ternary NNs with alternating ReLU and identity layers to achieve a lower bound on the maximum number of linear regions comparable to that of general ReLU regression NNs. When using ReLU in all the layers, a similar bound is obtained by further doubling the width. This provides a theoretical explanation, in some sense, for the practical success of ternary NNs.