One form of characterizing the expressiveness of a piecewise linear neural network is by the number of linear regions, or pieces, of the function modeled. We have observed substantial progress in this topic through lower and upper bounds on the maximum number of linear regions and a counting procedure. However, these bounds only account for the dimensions of the network and the exact counting may take a prohibitive amount of time, therefore making it infeasible to benchmark the expressiveness of networks. In this work, we approximate the number of linear regions of specific rectifier networks with an algorithm for probabilistic lower bounds of mixed-integer linear sets. In addition, we present a tighter upper bound that leverages network coefficients. We test both on trained networks. The algorithm for probabilistic lower bounds is several orders of magnitude faster than exact counting and the values reach similar orders of magnitude, hence making our approach a viable method to compare the expressiveness of such networks. The refined upper bound is particularly stronger on networks with narrow layers.
Summary:
This paper builds off of previous work that has studied the counting of linear regions in deep neural networks. The function learned by a deep neural network with piecewise linear activations (such as Relus) is itself piecewise linear on the input, and a measure of expressiveness of the network has been to count the number of linear regions.
However counting linear regions in a typical neural network is usually intractable, and there have been a sequence of upper and lower bounds proposed. Upper bounds are based on counting hyperplane arrangements (Zaslavsky, 1975; Raghu 2017; Montufar 2017; Serra 2018), and lower bounds based on counting regions in specific networks.
This paper improves the upper bound proposed in Serra (2018) by improving on a dimensionality constraint: the upper bound can be tightened if the dimensionality of the ambient space is shown to be smaller than the maximum possible value (number of neurons.) The paper defines A_l(k) -- the number of active neurons in layer l given k active neurons in layer l-1, and I_l(k) similar for inactive neurons, and proves an improved upper bound. 
For the lower bound, the paper extends the existing MBound algorithm to probabilistically count the number of linear regions, with experiments (Figure 1) demonstrating the speed of this lower bound algorithm compared to counting.
Clarity: The presentation for this paper is relatively clear, but it is quite technical, so some parts are hard to follow, without knowing the prior work in detail.
Originality: Defining A_l(k) and I_l(k) for a refined upper bound, as well as the idea of using a probabilistic lower bound is new compared to prior work.
Comments on Quality and Significance: 
The theoretical results presented in this paper are interesting and novel, both the bounds and the adaptation of existing methods (Nemhauser 1978; Gomes 2006) for purposes of estimating bounds. However, I'm uncertain as to the practical applications. One thing that was unclear to me was what Proposition 3, 4 mean for the quantities A_l(k) and I_l(k) in practice (in trained networks). The text makes a comment on the weights and biases having the same number of positive/negative elements but that is likely to only be true for random networks.  It would be interesting to see Figure 1 left for random and trained networks. 
Given the long line of work in this area however, I think this paper will be interesting to the community.