A Lower Bound for the Number of Linear Regions of Ternary ReLU Regression Neural Networks
Authors: Yuta Nakahara
Manabu Kobayashi
Toshiyasu Matsushima
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (4/2026)
A Lower Bound for the Number of Linear Regions of Ternary ReLU Regression Neural Networks
Yuta Nakahara
y.nakcham&uussedo...
Center for Data Science Waseda University
Manabu Kobayashi
mkobaa@uascdd..pp
Center for Data Science Waseda University
Toshiyasu Matsushima
tostimnl@@ussedo.pp
Department of Applied Mathematics Waseda University
Reviewed on OpenReview: https: /ttps://openvee oww.re/eepereeeee..om net/ forum?
Abstract
With the advancement of doep learning, reducing computational complexity and memory consumption has become critical challenge, and ternary neural networks (NNs) that restrict parameters {-1,0, +1} have attracted attention as 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 ternary NNs from the perspective of the number linear regions. Specifically, we evaluate the number of linear regions of ternary regression NNs with Rectified Linear Unit (RcLU) for activation functions and prove that the number of linear regions increases polynomially with respect 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 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, some sense, for the practical success of ternary NNs.
1 Introduction
In recent years, with the rapid development of deep learning, neural networks (NNs) have achieved remarkable results in various fields. However, their large computational and memory consumption has become a scrious barrier to applications in mobile devices and edge computing. Particularly, considering implementation embedded systems that require real-time processing in environments with limited computational resources, memory and computation reduction of NNs an urgent issue.
As promising approach to this problem, methods for discretizing NN parameters have been proposed. Specifically, methods that restrict network weights to binary {-1,+1} or ternary {-1, 0, +1} values, quantize the output values of activation functions have been developed (Hubara el al. 2016 Liu el al. 2023). These methods have achieved performance comparable to conventional continuou--valut NNs in a wide range of tasks including image recognition (Rastegari al. 2016 Liu al. 2020 natural languago
processing (Bai et al. [2021] Wang et al., (2025), and speech recognition (Xiang et al. 2017 while successfully
achieving significant reductions in computational complexity and memory usage. Particularly noteworthy

---

Published in Transactions on Machine Learning Research (4/2026)
is the surprising fact that these discretized NNs can maintain high performance in practical tasks despite extremely restricting their parameters.
However, the theoretical understanding of why these discretization methods work effectively remains in- sufficient. The motivation of this study is to provide a theoretical explanation for the success of ternary NNs. When theoretically evaluating the performance of NNs, various perspectives can be considered, e-g, the expressivity, i.e,, the complexity of functions representable by NNs, the empirical error for training data, and the generalization error when applying the trained model to new data. In this work, we evaluate the expressivity of ternary NNs, as restricting the parameter space raises concerns about its significant impact on the class of functions that NNs can represent. It should also be noted that, since expressivity is defined as property of the NN itself independently of data, this study does not consider learning from data.
Various metrics can be considered for evaluating expressivity, For shallow NNs with three layers, Barron (1993) showed that, under certain conditions, any function can be universally approximated. On this basis, it was long believed that a depth of three layers is sufficient for NNs. Subsequently, as the superior performance of deep NNs was empirically demonstrated, theoretical researchers became interested in the advantages of increasing network depth. One of the early studies {Montúfar et al. 2014) on this topic evaluated the number of linear regions representable by NNs. This work showed that the maximum number of linear regions representable by deep NNs with ReLU activations grows polynomially in the width and exponentially in the depth of the network. Following this, various studies have evaluated different quantities related to linear regions (Pascanu et al.] 2014 Serra et al., 2018 Hanin & Rolnick 2019: Esaki et al. 2020). While these studies do not directly assess approximation accuracy of functions, it intuitively clear that functions with an insufficient number of linear regions cannot approximate complex functions well. For instance, a function with only one linear region can not approximate a smooth curve well. Subsequently, following the approach of Barron, the approximation accuracy of functions within some classes is evaluated. For example, Yarotsky (2017) demonstrated that increasing the depth of a NN is more efficient than increasing its width for approximating functions in Sobolcv spaces. Although Yarotsky (2017) did not directly used the results by Montúlar et al.] (2014), his proof relies on a similar sawlooth (lent map) construction used by Montúlar et al. (2044) count linear regions.
Thus, in the literature on the expressivity of deep NNs, the number of linear regions was historically evaluated first, then, approximation accuracy of functions was evaluated. In light of this background, we evaluate the number of linear regions of ternary NNs in this study. Our results may also provide some insights into evaluating the approximation accuracy of functions by ternary NNs, and it remains an important direction for future work. The main limitations of this study are as follows. While models such as BitNet b1.58 quantize not only the weights but also the outputs of activation functions, this aspect is outside the scope of this study.
The main contribution of this paper is to show that the maximum number of linear regions of ternary NNs also increases polynomially with respect to width and exponentially with respect to depth, similar to conventional NNs. More specifically, we prove that it suffices to first double the width, then either square the width or double the depth of lernary regression NNs with alternating ReLU and identity layers to obtain a lower bound on the maximum number of linear regions comparable to that for general ReLU regression NNs. When using ReLU in all the layers, a similar bound is obtained by further doubling the width. Although from the limited perspective of the number of linear regions of piecewise linear functions represented by ReLU NNs, and from the comparison between lower bounds on the maximum number of linear regions of conventional NNs and ternary NNs, these results provide one theoretical explanation for the practical success of ternary NNs.
The rest of this paper is structured as follows. Section 2 introduces notation for explaining this research and previous studies. Section 3 reviews existing research on the number of linear regions of general NNs. Section states the main theorem regarding the number of linear regions of ternary NNs and provides its proof. Section 5 discusses the significance and limitations of the obtained results and concludes this research.
2

---

Published in Transactions on Machine Learning Research (4/2026)
=
2
L
L
70
72
71
W
(2) 21
W
Figure 1: Illustration of NN. The weight of the edge extending from the j-th node of the (1 - 1)-th layer to the i-th node of the I-th layer corresponds to the (i,j) component w of the weight matrix w of the if linear function a The bent line inside the node represents that the activation function is ReLU. Each small black dot represents the constant term 1.
2 Preliminaries
Definition (Neural networks). Let an arbitrory natural number L E and natural numbers ny E N be given for integers 1 2,.,2 Then, we call the sollowing function Fg Rn + R=", which is expressed as composition of linear function f()) R - R W where & represents the vector (21, 22. Fm. 1]T, and nonlinear functions g R - R"; NN of depth L with width at the 1-th layer:
Fo(x) f(() o fll-1) .... o (x).
(1)
Here, no and ny represent the dimensions of input and output, respectively, and θ represents all parameters {W of the NN. In this paper, we only deal with regression NNs where the final layer is a linear function. The nonlinear function g( is called an activation function. In particular, we call regression NNs that use the following ReLU function for all the activation functions ReLU Regression NNs in this paper.
9 - (mx==max00,
(2)
① (x) and Fj represent the j-th components of 9 (ax) and x, respectively. Also, we call NNs where where 9j g all the paramelers of the linear function f(i) lake only values from {1,0,-1 -1] lernary NNs in this paper.
Limiting NN weights to ternary values is also performed in BitNet b1.58 Waag et al. 2025). While Bit- Net b1.58 additionally quantizes the output of activation functions, as mentioned in the introduction, this paper does not deal with quantization of activation functions. Evaluating the effect of activation function quantization on NN expressivity is future research topic.
NNs can be represented graphs as shown in Fig. 1 Each small black dot represents the constant term 1. In this paper, we do not distinguish the coefficients for input variables and those for constant terms, i.e., biases. Both are represented by w and called weights. In other words, if NNs are ternary, biases also restricted to (1,0,-1 - in our setting, If activation function used at node is ReLU, represent it by drawing the bent line inside the node.
Definition 2 (Linear regions (Montúfar et al. 2014)). For a function f D - R", we say that C D is linea region of f if the following holds:
In this paper, linear functions refer functions that form hyperplanc and do not necessurily pass through the origin. More precisely, such functions are called affine functions, but following the notation previous research (Montúifar 2014 call them linear functions this paper.
3

---

Published in Transactions on Machine Learning Research (4/2026)
The restriction of f to U, flo :U + R", is linear function.
For any V C D satisfying V 2 U, flv is not a linear function.
That is, locally matimal subset U of D where becomes linear function within that region is called linear region of f. Also, we denote the set of all linear regions of f as L(f) in this paper.
Example 1 (Linear regions of absolute value function). The linear regions of the absolute volue function f(x) = |z| are (-o0, 0] and 20), L(f) {(-20, 0), [0, oo)). Note that linear regions are closed sets, by ils defimition.
Here, note that when f D + I= is piecewise linear function, the following holds:
U U.D. UEC(F)
(3)
3 Previous Studies
Conventionally, it is known that the following holds for the number of linear regions [C(F) of ReLU Regression NN F R R"* with depth L and width n at each layer.
Proposition 1 (A lower bound for the number of linear regions of ReLU Regression NNs Montúlar et al. 2014)). For ReLU Regression NN Fg R - Th with depth and width n at each layer, let p = Li Then the following holds:
n
max [(F))) 2 2
(4)
This suggests that the number of linear regions of NNs increases in polynomial order with respect to network width and in exponent ial order with respect to depth, and is considered one piece of evidence showing that deepening the depth is more effective than widening the width for enhancing the expressivity of NNs.
The proof of Proposition 1 in (Montúfar et al., 2014) is given by specifically constructing a ReLU Regression NN such that the number of linear regions becomes poo(l-1), However, while Montúfar et al, (0144) shows the construction procedure of the ReLU Regression NN, it does not concisely state the mathematical formulas of the linear functions of each layer constructed by this procedure. To make it easier to use in the proof of our theorem described later, we express this using mathematical formulas here. In the ReLU Regression NN constructed by the method of (Montúfar et al. 2014), the nodes of each intermediate layer are divided into p groups of nn nodes each, and the linear function ((() f(22 ((-1))ots(a) (ar) corresponding to the j-th node of the i-th group in the I-th layer is expressed by the following formula (for the remaining n - pny nodes, all weights are set. to 0, so that identically output).
The first layer: for = 1, 1,2...., and 1, .,....nmu no. the ((i 1)mo +))th component (1) ( of (x) is expressed as follows:
((-1)no+ (x) = f ppa,,
(1)
i= 1,
(5)
2ppx, -2(i 2(i-1), 2
Intermediate layers: for 1 2,3,,... I- 1, 1,, j= 1,2,..., no, the ((i 1)no +
component p!!) [(-1)mo+,(2) (z) of (x) is expressed as follows:
0 f 1 mo (x)
Dimoti>
i= 1,
(6)
2p ( (-1) mIN- (- 2(i 1), 25i5
2 function that has the same input-output mapping but defined only on U.
4

---

Published in Transactions on Machine Learning Research (4/2026)
p13p
pno
pno
p
1
11g
2p
2p
2p
2
110
2p
2p
2p
2(p
1)
2(
nlp
Figure 2: ReLU Regression NN with number of linear regions equal to poll--1). 1)
The last layer: for I = L, 1,2,... ... as follows:
....... ne, the m-th component p (x) of ((1)(x) is expressed
ngg p (x) =
1)
j=1
We can represent these as a graph shown in Fig. 2
Although it is merely a rewrite of the proof in MMonúfaar et al. 2014) using equations equation 5 equation and equation 7 the proof that the number of linear regions of this ReL.U Regression NN is indeed p Po is summarized in Appendix.
4 Main Results
Before explaining the main results, show that bounded integer weight regression NNs can be represented by ternary NNs. First, any edge of bounded integer weight NN can be represented by a ternary regression NN with identity activation functions. Consider a NN where there exists some natural number M such that the weights linear functions are represented by integers in the range from -M to M. Suppose one edge has integer weight
shown in Fig. 3 (a). That is, suppose this NN partially includes the process of multiplying the input value by w. This process multiplying the input value by w can be represented in a two-layer ternary regression NN with identity activation functions, where the number of nodes in each layer
5

---

Published in Transactions on Machine Learning Research (4/2026)
Finite integer edge (-5 x
Ternary regression NN with identity activation functions
x w
x
(8)
(b-1)
(b-2)
Figure (a): A certain edge of a bounded integer weight NN. Here, the maximum weight is M 5 and the weight in this example w = 3. (b-1): Representation of (a) by ternary regression NN with identity activation functions. (b-2): Abbreviated notation of (b-1). Note that the number near by the triple lines between the square node and the round node represents not an edge weight but the sum of the original edge weights in (b-1).
being 7g = 1, n1 = M, 1, by setting
(x) = =,
(j= 1,2,...... M)
(8)
g 11) (z)) = =y.
(9)
|m] (0) sign(w)>)
(10)
where sign(w) represents the sign of w. This function is also represented a graph shown in Fig. 3 (b-1). Further, as shown in Fig. 3 (b-2), we represent the M nodes in the intermediate layer in this graph by square node and the M edges to or from these nodes by triple lines. Note that the number near by the triple lines represents not an edge weight but the sum of the original edge weights in Fig. 3 (b-1).
Furthermore, when representing not an edge but a bounded integer weight NN with a lernary regression NN with identity activation functions, it is sometimes possible to represent it with fewer nodes than replacing each edge with the aforementioned transformation by combining the nodes of the ternary NN. For example, Fig. shows ternary regression NNs with identity activation functions equivalent to bounded integer weight NN (a). In Fig. 4 (b) shows the ternary regression NN with identity activation functions by trivial transformation, (c-1) shows another representation of (a) by transformation with fewer nodes, and (c-2) shows its abbreviated notation. In Fig, | (c-2), edges extend from a square node to multiple nodes, with some numbers attached. Each of these edges represents the M edges extending from the M nodes in (c-1), which correspond to the square node in (c-2), and the number represents the sum of the weights of those M odges.
Next, state the main result of this research and its proof. In the following, for ReLU Regression NN with depth L and width n, consider a ternary regression NN with the same depth L and width n, and evaluate the lower bound of the maximun nunber of linear regions that can be represented by adjusting the edge weights. The proof strategy is as follows. We utilize the fact that the coefficients and biases of the lincar functions equation 5. equation G equation 7 used in the proof of Proposition D are bounded integers. We also leverage the relationship between bounded integer weight NNs and ternary regression NNs with identity activation functions mentioned above. Based on these observations, we first construct ternary regression NN with alternating ReLU and identity layers that represents functions of the same form equation 5 equation G equation 7 The lower bound when using ReLU in all the layers discussed later. The following is the main result of this research.
Theorem 1 (A lower bound of the number of linear regions of ternary NN with ReLU after even layer). For a ternary NN Fø:: : gade + IR with depth L and width n at each layer, where the activation function of odd-numbered layers is the identity function and the activation function of numneeemeeeed layers is ReLU, let. L' be the maximewn odd rember less than or equal to L and g = = Lzmottj] Then the following holds:
max [(Fo)] 2 8
( mmolL'
(11)
6

---

Published in Transactions on Machine Learning Research (4/2026)
Finite integer weight NN (-5
Temary regression NN with identity activation functions
5
-2
2
2
2
(a)
(b)
(0-1)
(c-2)
Figure 4: (a): A bounded integer weight NN where weight w satisfies -5 S w S (b): Representation of (a) by lernary regression NN with identity activation functions through trivial transformation. (c-1): Representation of (a) by a ternary regression NN with identity activation functions through transformation with fewer nodes. (c-2): Abbreviated notation of (c-1). Note that the number near by the triple lines between the square node and the round node represents not an edge weight but the sum of the original edge weights.
Proof. By constructing the ternary regression NN with alternating ReLU and identity layers shown in Fig. 5 the function represented by this NN becomes the function obtained by replacing p with g +()o++) in equation []] equation 6 equation 7 In the following, we describe the specific construction method of this NN and the mathematical expression of the function represented by it.
Let L' be the maximum odd number less than or equal to L. L even, we set the final layer to be an identity transformation, and hereafter we construct a ternary regression NN with depth T'' and width n each layer, where ReLU and identity layers are alternately used. Setting q In we divide the n nodes of the odd layers of this NN into no + groups of 2g nodes each. In Fig. these 2q nodes are represented by one square node. For the remaining n 2q(no + 1) nodes, all weights are set 0, making them functions that identically output 0. For the nodes of even layers, we create q groups of no nodes each, qmo nodes, all weights
and for the remaining equation equation 7 aalready takes only values from {1.0. -1} for any weights, we can use the linear function obtained by replacing with in equation equation for the L'-th layer. Next, for I = 1,2. {L' - 1), we define the (21 1)-th layer and the 21-th layer as follows:
set to 0, that they identically output O. First, since
For 1 1= 1:
Definition of ((): For j = 1,2,.... no + and ls = 1,2,... 24, define the (2q(i - 1) + k))-th (x) of (() follows:
component. [1] /24(j-1)44
Ij. j j= 11,2,...,,
12 1)4
(12)
1,
j j= j=ng no
Definition of f(2); For i = 1, 2..... and j = 1,2, 1,2,,..., define the (fi-1)no component (2)
(i-1) (x) of ((2) (x) as follows:
1 (e-1mots(0)) =
(2)
Ei 120(i-1]+kr
i=1
(13)
2q
x2c(j-1)+b + Σk=l 2(1-1)(-11, i= 2.3. ...
4.
For 1 2,3,..... ........3 [T/ 1)):

---

Published in Transactions on Machine Learning Research (4/2026)
Ro
2n(no + 1)
qmo
(n + 1)
qnto
nu
n2
2q
q
-2q
11p
:
24
24
29
2
2g
110
203
9
24
2q
29
1
-2(g
29
2(4
1)
Figure 5: A ternary regression NN whose number of linear regions equal to qà q where ReLU and identity layers are alternately used. Note that the number near by the triple lines between the square node and the round node represents not an edge weight but the sum of the original edge weights.

---

Published in Transactions on Machine Learning Research (4/2026)
Finite integer weight edge (-5 s w 5)
Temnary ReLU Regression NN
X = -2
W
-6
= O
-6
(a)
(b)
Figure 6: (a): A certain edge of a bounded integer weight NN (the same as in Fig. 3 (a)). Here, the maximum weight is M and the weight this example w 3. (b): Representation of (a) by a ternary ReLU Regression NN
Definition of (21-11); For j 1,2,...,
......,,, no + 1 and h: = 1,2,... 2g, define the (29(i - 1) + k-)thh 220 12)b (a) of (x)) follows:
component (2r-
(-1m ( 1)m- j j= ., j = no + 1.
121-1) 12 (z)
(14)
1,
Definition of (21); For 1,2...., and 1......, define the (m=1))no+ + ji component (21)
mi= (x) of (x) as follows:
f (z)))
i=
(15)
2q k= 12
2( (-1) Ek=1
i= 2. ..... q.
For activation functions, we use the identity function for odd layers and ReLU for even layers.
Since the activation function of odd layers the identity function, when we substitute f() into f(2), we can see that (() (1) of the ternary regression NN equals the function obtained by replacing p with q in the linear function equation 3 of the first layer of regular ReLU Regression NN. Also, for ( 3
when we substitute ((2 into f(2), we can see that f(2)) o f(t of the ternary regression NN equals the function obtained by replacing p with q the linear function equation t of the 1-th layer of regular NN. Therefore, the ternary regression NN shown here achieves the lower bound of the number of linear regions obtained by replacing p with q and L 1 with (L' 1) in the right-hand side of equation equation for regular ReLU Regression NN. That is, the number of linear regions of this ternary regression NN becomes q m -1).
Remark 1. Comparing equation equation 4 and equation equation I1 roughly speaking, to obtain lower bound of the marimum number of linear regions comparable to that for general ReLU Regression NNs, it suffices to first double the width, then square the width or double the depth of ternary NNs where the activation function of odd-nuun numberedd layers is the identäly function and the activation function of even-numbered layers is ReLU.
Remark 2. The identity function can be represented by two ReLU functions as follows: x = ReLU(x)) ReLU(-x). Using this equation, Theorem I can be extended to lernary regression NNs with ReLU U in all the layers. For example, a finite integer weight edge as shown in Fig. 6 (a), which is the same as in Fig (a), can be represented by a ternary ReLU Regression NN as shown in Fig. 6 (b). By replacing all the square nodes Fig. [ with this method, we can achieve a bound simslar Theorem I using ternary ReLU Regression NN with double the width of the ternary NN with alternating ReL. and identily layers.
9

---

Published in Transactions on Machine Learning Research (4/2026)
5 Conclusion and Future Work
We theoretically evaluated the expressivity of ternary NNs, which have achieved great practical success in memory and computation reduction of NNs, from the perspective of the number of linear regions. As a result, it was shown that the expressivity of ternary ReLU Regression NNs increases polynomially with respect to network width and exponentially with respect to depth, similar to general ReLU Regression NNs. Furthermore, it was found that it suffices to first double the width, then square the width or double the depth of ternary regression NÑs with alternating ReLU and identity layers to obtain a lower bound on the maximum number of lincar regions comparable to that for general ReLU Regression NNs. When using ReLU in all the layers, a similar bound is obtained by further doubling the width. We believe this provides explanation of part of the reason for the practical success of ternary NNs, albeit from the limited perspective of the number of linear regions of piecewise linear functions represented by ReLU NNs.
However, in actual applications such as BitNet b1.58, the output of activation functions are also quantized for further memory and computation reduction. Our method cannot be directly applied to such NNs. The- oretical evaluation of the expressivity of such NNs is a future research topic. Moreover, the evaluation of approximation accuracy of functions by ternary NNs remains an important direction for future work. Apply- ing the expressivity bound derived in this paper to a practical example is also important, e.g., investigating how well a real-world ternary network satisfics the bound.
Acknowledgments
We thank Professor Suko at Waseda University for providing the motivation for this research. This work was supported in part by JSPS KAKENHI Grant Numbers JP22K02811, JP23K03863, JP23K04293, JP24H00377 and 26K17386,
References
Haoli Bai, Wei Zhang, Lu Hou, Lifeng Shang, Jin Jin, Xin Jiang, Qun Liu, Michael Lyu, and Irwin King, BinaryBERT: Pushing the limit of BERT quantization. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1fth International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4334 4348, Online, August 2021, Association for Computational Linguistics. doi: 10.18653/ aac/222aacl-oongg33333333333 334. URL httts://aclanthooooy) wttp:///goo..rr//..aaaa------- /344
A.R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, (9(3):330-99) 945, 1993. doi: 10. 10.1109/18.29 00.911.255600.
Yasushi Esaki, Yuta Nakahara, and Toshiyasu Matsushima. Thcoretical analysis of the advantage of deepen- ing neural networks. In 2020 19th IEEE International Conference Machine Learning and Applicalions (TCMLA), pp. 479,484, 2020. doi: D0.110//CCMAA552224222000
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Reseorch, pp. 2596 2604. PMLR, 09- 15 Jun 2019. URL https://proceediin www.roceeding..mr..p.. www............e..m titess/v97/haniiee http:/aannnn9..hha..m
Ttay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https://rrooeediig .ddf
neurips. /ttp/////ee.ceaaaaa/a////////a//
Bin Liu, Fengfu Li, Xiaoxing Wang, Bo Zhang, and Junchi Yan. Ternary weight networks. In ICASSP 2023 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5, 2023. doi: 10.100//CAASSP04333.020300000000
10

---

Published in Transactions on Machine Learning Research (4/2026)
Zechun Liu, Zhiqiang Shen, Marios Savvides, and Kwang-Tineg Cheng. Reactnet: Towards precise binary neural network with generalized activation functions. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), Computer Vision ECCV 2020, pp. 143 159, Cham, 2020. Springer International Publishing. ISBN 978-3-030-58568-6.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua. Bengio. On the number of lin- ear regions of deep neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Newral Information Processing Systems, volume 27. Cur- ran Associates, Inc., 2014. URL https://proocedding heurips.com cc/paper ftlles/pappr//01///ftll// Paper. 2481244490c440111227777441111112 Paper.....f..
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations. In International Conference on Learning Representa- tions, 2014. URL https://openreviier http:pppwrreeeeeeeeeeororuaaaaaa pett/forum?id--SSattmnooo
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling (eds.), Computer Vision ECCV 2016, pp. 525 542, Cham, 2016. Springer International Publishing. ISBN 978-3-319-46493-00
Thiago Scrra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting lincar regions of deep neural networks. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. PMLR, 10 15 Jul 2018. URL https://prooceedngss mlr. wtt.:/swwwrrrreeeeeeeeeeeee preas//80/serrale0e html
Hongyu Wang, Shuming Ma, Lingxiao Ma, Lei Wang, Wenhui Wang, Dong, Shaohan Huang, Huaijie Wang, Jilong Xue, Ruiping Wang, Yi Wu, and Furu Wei. Bitnet: 1-bit pre-training for large language models. Journal of Machine Learning Research, 26(125):1 29, 2025. URL http://jmmr: httpmirrrl....a...e.mm........ .rg. org/papers/ 026/24-2050 html
Xu Xiang, Yanmin Qian, and Kai Yu. Binary deep neural networks for speech recognition, In Interspeech 2017, pp. 533-537, 2017. doi: 10.21437 10.21437/Intersppe htte///nncspccchh11111 2017-1333.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103 114, 2017. ISSN 0893-6080. doi: https///cbi.og////o000///eeuue
20tp://0....0...e............... URL https://wwt /www. stf.aaaciie..coo//ccccc.ceeeeeed
A Proof of Proposition
Before proving Proposition we show the following Lemma.
Lemma (The number of linear regions of a composite function of piecewise linear functions). Let g D1 + D2 be a piecewise linear function, and suppose that for any linear region U E L(g) of 9: 9 u is bijection from U to D2- Let f D2 + R a piecewise linear function. Note that the domain of f coincides with the range of g. Then, the sollowing holds for the number of linear regions of the composite function f o g:
[C( o gg) = =
(16)
Proof of Lemma 1 For any E C(g) and any e L(f), consider the inverse image of V under glu. denoted glū' (V). On glu (V), foglu clearly linear function. Also, on the set any point x E U g (V) g/ (V), fogl does not become linear function. This is because, due to the bijectivity of glu, have ( (V)U()) 2 V, and by the definition of linear region V, f f (V)U(*)) (V))())
{*} obtained by adding
does not become linear function. Therefore, (V) is linear region of f glu-
11

---

Published in Transactions on Machine Learning Research (4/2026)
Also, the following holds:
U g1
glo is bijection from U to D2
(17)
glū (Uveci)
piccewise linear function
(18)
U (V) VEC()
glu is bijection from U to D2
(19)
This indicates that U divided into |C())) linear regions (V) of f glo.. Since the same holds for any U C(g), we have [C( g)و (()))
Next, we prove Proposition
Proof of Proposition First, we define the following three functions f [0, 1| - Romo, j TRpnO - [0. 1|m0
and f [0, 1) + R Note the domain and range of each function.
Definition of f [0, 11 IR For any 1,2,..... -.. and 1,2,.... .... no, define the ((i-1)mu +
th component f(=-1)n++ (x) of f(x) as follows:
((-1)mo+)(2)
petj
i=
(20)
2pxr 2(2 11,, i= 2........
Definition of f IRPR0 - [0, 10:: For any = 1.2..... no, define the j-th component fz(2) of f(x) as follows:
.....
[()x) = - 1(k--))ntt>
(21)
Definition of f: [0, 1|"0 RTc; For any 1,2..... ne, define the m-th component fm)x) of f(x) as follows:
ng
Pm
>
Jzz
(22)
For simplicity, restrict the domain of the NN to [0,1] Then, Fo(x) can be expressed using these functions and ReLU g follows:
Fo(x) ( ((-1) f(l-1) o o.. o (()
(23)
= = j jogofo fogogoo jogof
(24)
= fohoho h.
(25)
Note that h = oogof
f f is a function from [0, 10 to [0, 1) Also, the j-th component of h(x) is expressed
as
hy(x) = max 0, pr,} - ma - 27+ (-1)p-1 max (0, 2prr, 2(p 1)}
(26)
and is one-dimensional piecewise linear function that depends only æj, shown in Fig. 7
12

---

Published in Transactions on Machine Learning Research (4/2026)
(x)
px, (2px, - 2) pxy +
pzj (2px) - 2) + (2pz) + +4) pxj 2
1
2
p
Xj
P
p
p
Figure 7: A graph of hy(x:)
Therefore, for any {0, ......p-- 1}, an interval
p becomes a linear region of hy, and hyl
be-
comes bijection to [0, 1]. Since h is function consisting of h2 as each component, for any (11, la 12.... {0, p 10 the Cartesian product I
4 y+1 becomes linear region of h, and h
r4 944
becomes bijection to [0, 1
Here, since |(() = and [c(h)] {(0, 1..... 10 pn using Lemma the following holds:
C c(f h [ = n = p0
(27)
Similarly, the following also holds:
|C o hoh)] |C(F k))l((h)) = p0 pnd p 2no
(28)
By repeating this recursively, obtain
[(F))) = |C( hohh h)] 1
(29)
Therefore, Proposition proven.
13


Reviews:
[{"review_id": "mmM6ONawNr", "reviewer": "Reviewer_cVFM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper contributes a theoretical result, which may help us better understand the representational capacities of low-precision neural networks. In particular, this paper studies deep ternary neural networks with ReLU activations, and analyzes the number of linear regions (in the fashion of Montufar et al. 2014) that can be generated by ternary weights instead of real-valued weights. The key proof idea is to construct a ternary two-layer ReLU(+Identity) network which can express a layer with bounded integer weights; that is, one can simply double the depth to approximate bounded-integer nets with ternary nets. This result directly translates the Montufar et al. result to handle the ternary weights.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The key theoretical ideas have been presented in the main sections very clearly.", "audience_yn": "Yes", "audience_explanation": "Theoretical understandings on what low-precision networks can express is of much interest. There has been several works on the direction function approximation side, but I have not seen much on the side of the number of linear regions.", "requested_changes": "- As a minor suggestion: as this paper is technically simple, it will be better if authors put more effort in describing the general landscape of the current theoretical understandings on the representational capacity of low-precision neural networks. In particular, please try to make connections with Barron-style universal representation works---what are the key advantages of studying the number of linear regions, and how this can helps understanding the approximation capacities.\n- In addition, please make it clearer what are the key assumptions of this work. In particular, the fact that one allows using \"Identity functions\" as the activations in the odd-numbered layers may be viewed as quite restrictive to the scope of this work, as many practical neural networks do not consider such activations. Also, whether the real-valued bias can be used is one of the key issues of theoretical works on low-precision neural networks. Please make a clear distinction between the \"weights\" and the \"biases,\" and which assumption has been applied on each.", "broader_impact_concerns": "This paper does not need a broader impact statement, as this work explores the mathematical nature of neural-network-configured functions.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "I8MMR8LwUn", "reviewer": "Reviewer_FGbB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors extend a theory about the expressiveness of ReLU regression networks to the case when parameters are quantized to ternary precision (-1, 0, or 1). The proposed approach is simple: first the authors review a proof shown in previous work for continuous parameters, and then demonstrate that any continuous-parameter ReLU regression network can have its input-output relationship replicated exactly by constructing a ternary network in a specific way that involves increasing width and depth. The bound derived for the continuous-parameters can thus apply to the ternary network, yielding a new scaling relationship since the ternary network requires different numbers of parameters and layers to implement the function.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I believe the derivation and construction of the examples to be correct.", "audience_yn": "Yes", "audience_explanation": "This work is useful in providing an intuition for how and why quantized neural networks work, what their limitations are, and what we can expect of their capabilities. This is important because compressing models via quantization is a relevant research area and is ubiquitous among practitioners, both of who comprise TMLR's audience.", "requested_changes": "While the paper provides a tight, intuitive theory, it would be interesting to see it applied to a practical example. For example, one could investigate how well a real-world ternary network satisfies the expressivity bound derived here and, by working backwards from the authors' ternary-network construction approach, infer what a continuous-parameter version of the network would look like. These are just some of the applications of this theory. Nevertheless, while it would make the work's results more interesting, I do not think that additional experimental work is necessary for my recommendation to accept the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "StCUuCQy2x", "reviewer": "Reviewer_nWkw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript presents a single mathematical result on the number of linear regions attainable in the output space of the ReLU neural network with weights constrained to three values: -1, 0, or 1, in terms of the network's depth and width. This result is compared with a seminal one of Montufar et al. (2014) on the number of linear regions of a ReLU network with (standard) real-valued weights", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper contribution is modest but interesting. It provides exactly the result its title announces. The main ideas are well explained, and the proofs are detailed. I appreciate that the authors do not oversell their results. It", "audience_yn": "Yes", "audience_explanation": "To my knowledge, the result is new. Given the empirical benefit of using a quantized network (in terms of memory reduction), this result is of interest.", "requested_changes": "### Critical (but easy to fix)\n\nPlease carefully proofread the bibliography. When a paper has been accepted after a peer-reviewed process, it is a duty to cite the published version instead of the arXiv preprint:\n- Courbariaux et al. (2016) corresponds to this NeurIPS paper: https://proceedings.neurips.cc/paper/2016/hash/d8330f857a17c53d217014ee776bfd50-Abstract.html\n- Li et al. (2022) is an ICASSP 2023 paper.\n- Pascanu et al. (2014) is an ICLR paper\n\n### Further recommendations\n\n1. I think the following paper deserves to be cited, as it provides a similar analysis of ReLU networks to that of Montufar et al. (2014), but in terms of approximation error instead of the number of regions:\n> Dmitry Yarotsky (2017). Error bounds for approximations with deep ReLU networks. Neural Networks.\n\n2. The depiction of the neural networks' decompositions in the figures is really helpful, but it took me a bit of time to grasp the meaning of the edge labels, as the meanings differ across figures. I would suggest clarifying the figures' explanation.", "broader_impact_concerns": "-", "additional_comments": "I think the following paper deserves to be cited, as it provides a similar analysis of ReLU networks to that of Montufar et al. (2014), but in terms of approximation error instead of the number of regions:\nDmitry Yarotsky (2017). Error bounds for approximations with deep ReLU networks. Neural Networks.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)