On the Expected Complexity of Maxout Networks
Year: 2021

Abstract:
Learning with neural networks relies on the complexity of the representable functions, but more importantly, the particular assignment of typical parameters to functions of different complexity. Taking the number of activation regions as a complexity measure, recent works have shown that the practical complexity of deep ReLU networks is often far from the theoretical maximum. In this work, we show that this phenomenon also occurs in networks with maxout (multi-argument) activation functions and when considering the decision boundaries in classification tasks. We also show that the parameter space has a multitude of full-dimensional regions with widely different complexity, and obtain nontrivial lower bounds on the expected complexity. Finally, we investigate different parameter initialization procedures and show that they can increase the speed of convergence in training.

heading: 1 Introduction
text: We are interested in the functions parametrized by artificial feedforward neural networks with maxout units. Maxout units compute parametric affine functions followed by a fixed multi-argument activation function of the form (s1, . . . , sK) 7→ max{s1, . . . , sK} and can be regarded as a natural generalization of ReLUs, which have a single-argument activation function s 7→ max{0, s}. For any choice of parameters, these networks subdivide their input space into activation regions where different pre-activation features attain the maximum and the computed function is (affine) linear. We are concerned with the expected number of activation regions and their volume given probability distributions of parameters, as well as corresponding properties for the decision boundaries in classification tasks. We show that different architectures can attain very different numbers of regions with positive probability, but for parameter distributions for which the conditional densities of bias values and the expected gradients of activation values are bounded, the expected number of regions is at most polynomial in the rank K and the total number of units.
Activation regions of neural networks For neural networks with piecewise linear activation functions, the number of activation regions serves as a complexity measure and summary description which has proven useful in the investigation of approximation errors, Lipschitz constants, speed of convergence, implicit biases of parameter optimization, and robustness against adversarial attacks. In particular, Pascanu et al. (2013); Montúfar et al. (2014); Telgarsky (2015, 2016) obtained depth separation results showing that deep networks can represent functions with many more linear regions than any of the functions that can be represented by shallow networks with the same number of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
units or parameters. This implies that certain tasks require enormous shallow networks but can be solved with small deep networks. The geometry of the boundaries between linear regions has been used to study function-preserving transformations of the network weights (Phuong and Lampert, 2019; Serra et al., 2020) and robustness (Croce et al., 2019; Lee et al., 2019). Steinwart (2019) demonstrated empirically that the distribution of regions at initialization can be related to the speed of convergence of gradient descent, and Williams et al. (2019); Jin and Montúfar (2020) related the density of breakpoints at initialization to the curvature of the solutions after training. The properties of linear regions in relation to training have been recently studied by Zhang and Wu (2020). The number of regions has also been utilized to study the eigenvalues of the neural tangent kernel and Lipschitz constants (Nguyen et al., 2020).
Maximum number of regions Especially the maximum number of linear regions has been studied intensively. In particular, Montúfar (2017); Serra et al. (2018) improved the upper bounds from Montúfar et al. (2014) by accounting for output dimension bottlenecks across layers. Hinz and Van de Geer (2019) introduced a histogram framework for a fine grained analysis of such dimensions in ReLU networks. Based on this, Xie et al. (2020); Hinz (2021) obtained still tighter upper bounds for ReLU networks. The maximum number of regions has been studied not only for fully connected networks, but also convolutional neural networks (Xiong et al., 2020), graph neural networks (GNNs) and message passing simplicial networks (MPSN) (Bodnar et al., 2021).
Expected number of regions Although the maximum possible number of regions gives useful complexity bounds and insights into different architectures, in practice one may be more interested in the expected behavior for typical choices of the parameters. The first results on the expected number of regions were obtained by Hanin and Rolnick (2019a,b) for the case of ReLU networks or singleargument piecewise linear activations. They show that if one has a distribution of parameters such that the conditional densities of bias values are bounded and the expected gradients of activation values are bounded, then the expected number of linear regions can be much smaller than the maximum theoretically possible number. Moreover, they obtain bounds for the expected number and volume of lower dimensional linear pieces of the represented functions. These results do not directly apply to the case of maxout units, but we will adapt the proofs to obtain corresponding results.
Regions of maxout networks Most previous works focus on ReLUs or single-argument activation functions. In this case, the linear regions of individual layers are described by hyperplane arrangements, which have been investigated since the 19th century (Steiner, 1826; Buck, 1943; Zaslavsky, 1975). Hence, the main challenge in these works is the description of compositions of several layers. In contrast, the linear regions of maxout layers are described by complex arrangements that are not so well understood yet. The study of maxout networks poses significant challenges already at the level of individual layers and in fact single units. For maxout networks, the maximum possible number of regions has been studied by Pascanu et al. (2013); Montúfar et al. (2014); Serra et al. (2018). Recently, Montúfar et al. (2021) obtained counting formulas and sharp (asymptotic) upper bounds for the number of regions of shallow (deep) maxout networks. However, their focus was on the maximum possible value, and not on the generic behavior, which we investigate here.
Related notions The activation regions of neural networks can be approached from several perspectives. In particular, the functions represented by networks with piecewise linear activations correspond to so-called tropical rational functions and can be studied from the perspective of tropical geometry (Zhang et al., 2018; Charisopoulos and Maragos, 2018). In the case of piecewise affine convex nonlinearities, these can be studied in terms of so-called max-affine splines (Balestriero et al., 2019). A related but complementary notion of network expressivity is trajectory length, proposed by Raghu et al. (2017), which measures transitions between activation patterns along one-dimensional paths on the input space, which also leads to depth separation results. Recent work (Hanin et al., 2021) shows that ReLU networks preserve expected length.
Contributions We obtain the following results for maxout networks.
• There are widely different numbers of linear regions that are attained with positive probability over the parameters (Theorem 7). There is a non-trivial lower bound on the number of linear regions that holds for almost every choice of the parameters (Theorem 8). These results advance the maximum complexity analysis of Montúfar et al. (2021) from the perspective of generic parameters.
• For common parameter distributions, the expected number of activation regions is polynomial in the number of units (Theorem 9). Moreover, the expected volume of activation regions of different
dimensions is polynomial in the number of units (Theorem 10). These results correspond to maxout versions of results from Hanin and Rolnick (2019b) and Hanin and Rolnick (2019a).
• For multi-class classifiers, we obtain an upper bound on the expected number of linear pieces (Theorem 11) and the expected volume (Theorem 12) of the decision boundary, along with a lower bound on the expected distance between input points and decision boundaries (Corollary 13).
• We provide an algorithm and implementation for counting the number of linear regions of maxout networks (Algorithm 1).
• We present parameter initialization procedures for maxout networks maximizing the number of regions or normalizing the mean activations across layers (similar to Glorot and Bengio 2010; He et al. 2015), and observe experimentally that these can lead to faster convergence of training.

heading: 2 Activation regions of maxout networks
text: We consider feedforward neural networks with n0 inputs, L hidden layers of widths n1, . . . , nL, and no skip connections, which implement functions of the form f = ψ ◦ φL ◦ · · · ◦ φ1. The l-th hidden layer implements a function φl : Rnl−1 → Rnl with output coordinates, i.e. units, given by trainable affine functions followed by a fixed real-valued activation function, and ψ : RnL → RnL+1 is a linear output layer. We denote the total number of hidden units by N = n1 + · · ·+ nL, and index them by z ∈ [N ] := {1, . . . , N}. The collection of all trainable parameters is denoted by θ. We consider networks with maxout units, introduced by Goodfellow et al. (2013). A rank-K maxout unit with n inputs implements a function Rn → R; x 7→ maxk∈[K]{wk · x+ bk}, where wk ∈ Rn and bk ∈ R, k ∈ [K], are trainable weights and biases. The activation function (s1, . . . , sK) 7→ max{s1, . . . , sK} can be regarded as a multi-argument generalization of the rectified linear unit (ReLU) activation function s 7→ max{0, s}. The K arguments of the maximum are called the pre-activation features of the maxout unit. For unit z in a maxout network, we denote ζz,k(x; θ) its k-th pre-activation feature, considered as a function of the input to the network.
For any choice of the trainable parameters, the function represented by a maxout network is piecewise linear, meaning it splits the input space into countably many regions over each of which it is linear. Definition 1 (Linear regions). Let f : Rn0 → R be a piecewise linear function. A linear region of f is a maximal connected subset of Rn0 on which f has a constant gradient.
We will relate the linear regions of the represented functions to activation regions defined next. Definition 2 (Activation patterns). An activation pattern of a network with N rank-K maxout units is an assignment of a non-empty set Jz ⊆ [K] to each unit z ∈ [N ]. An activation pattern J = (Jz)z∈[N ] with ∑ z∈[N ](|Jz| − 1) = r is called an r-partial activation pattern. The set of all possible activation patterns is denoted P , and the set of r-partial activation patterns is denoted Pr. An activation sub-pattern is a pattern where we disregard all Jz with |Jz| = 1. The set of all possible activation sub-patterns is denoted S, and the set of r-partial activation sub-patterns is denoted Sr. Definition 3 (Activation regions). Consider a network N with N maxout units. For any parameter value θ and any activation pattern J , the corresponding activation region is
R(J, θ) := { x ∈ Rn0 ∣∣ argmax k∈[K] ζz,k(x; θ) = Jz for each z ∈ [N ] } .
For any r ∈ {0, . . . , n0} we denote the union of r-partial activation regions by XN ,r(θ) := ⋃ J∈Pr R(J ; θ).
By these definitions, we have a decomposition of the input space as a disjoint union of activation regions, Rn0 = tJ∈PR(J, θ). See Figure 1. Next we observe that for almost every choice of θ, r-partial activation regions are either empty or relatively open convex polyhedra of co-dimension r. In particular, for almost every choice of the parameters, if r is larger than n0, the r-partial activation regions are empty. Therefore, in our discussion we only need to consider r up to n0. Lemma 4 (r-partial activation regions are relatively open convex polyhedra). Consider a maxout network N . Let r ∈ {0, . . . , n0} and J ∈ Pr. Then for any θ, R(J, θ) is a relatively open convex polyhedron in Rn0 . For almost every θ, it is either empty or has co-dimension r.
The proof of Lemma 4 is given in Appendix A. Next we show that for almost every choice of θ, 0-partial activation regions and linear regions correspond to each other. Lemma 5 (Activation regions vs linear regions). Consider a maxout networkN . The set of parameter values θ for which the represented function has the same gradient on two distinct activation regions is a null set. In particular, for almost every θ, linear regions and activation regions correspond to each other.
The proof of Lemma 5 is given in Appendix A. We note that for specific parameters, linear regions can be the union of several activation regions and can be non-convex. Such situation is more common in ReLU networks, whose units can more readily output zero, thereby hiding the activation pattern of the units in the previous layers.
To summarize the above observations, for almost every θ, the 0-partial activation regions are n0dimensional open convex polyhedra which agree with the linear regions of the represented function, and for r = 1, . . . , n0 the r-partial activation regions are co-dimension-r polyhedral pieces of the boundary between linear regions. Next we investigate the number non-empty r-partial activation regions and their volume within given subsets of the input space. We are concerned with their generic numbers, where we use “generic” in the standard sense, to refer to a positive Lebesgue measure event.

heading: 3 Numbers of regions attained with positive probability
text: We start with a simple upper bound. Lemma 6 (Simple upper bound on the number of r-partial activation patterns). Let r ∈ N0. The number of r-partial activation patterns and sub-patterns in a network with a total of N rank-K maxout units are upper bounded by |Pr| ≤ ( rK 2r )( N r ) KN−r and |Sr| ≤ ( rK 2r )( N r ) respectively.
The upper bound has asymptotic order O(NrKN+r) in K and N . The proof of Lemma 6 is given in Appendix A, where we also provide an exact but unhandy counting formula.
By definition, the number of r-partial activation patterns is a trivial upper bound on the number of non-empty r-partial activation regions for any choice of parameters. Depending on the network architecture, this bound may not be attainable for any choice of the parameters. Montúfar et al. (2021, Theorems 3.7 and 3.12) obtained bounds for the maximum number of linear regions. For a shallow network with n0 inputs and a single layer of n1 rank-K maxout units it has order Θ((n1K)n0) in K and n1, and for a deep network with n0 inputs and L layers of n1, . . . , nL rank-K maxout units it has order Θ( ∏L l=1(nlK)
n0) in K and n1, . . . , nL. Hence the maximum number of non-empty activation regions can be very large, especially for deep networks.
Intuitively, linear regions have a non-zero volume and cannot ‘disappear’ under small perturbations of parameters. This raises the question about which numbers of linear regions are attained with positive probability, i.e. over positive Lebesgue measure subsets of parameter values. Figure 1 shows that the number of linear regions of a maxout network is a very intricate function of the parameter values. For a network with n0 inputs and a single layer of n1 ReLUs, the maximum number of linear regions is ∑n0 j=0 ( n1 j ) , and is attained for almost all parameter values. This is a consequence of the generic behavior of hyperplane arrangements (see Buck, 1943; Zaslavsky, 1975; Montúfar et al., 2014). In contrast, shallow maxout networks can attain different numbers of linear regions with positive probability. The intuitive reason is that the nonlinear locus of maxout units is described not only by linear equations 〈wi, x〉+ bi = 〈wj , x〉+ bj but also linear inequalities 〈wi, x〉+ bi ≥ 〈wk, x〉+ bk. See Figure 1 for an example. We obtain the following result. Theorem 7 (Numbers of linear regions).
• Consider a rank-K maxout unit with n0 inputs. This corresponds to a network with an input layer of size n0 and single maxout layer with a single maxout unit. For each 1 ≤ k ≤ K, there is a set of parameter values for which the number of linear regions is k. For min{K,n0 + 1} ≤ k ≤ K, the corresponding set has positive measure, and else it is a null set.
• Consider a layer of n1 rank-K maxout units with n0 inputs. This corresponds to a network with a single maxout layer, L = 1, and nL = n1. For each choice of 1 ≤ k1, . . . , kn1 ≤ K, there are parameters for which the number of linear regions is ∑n0 j=0 ∑ S∈([n1]j ) ∏ i∈S(ki − 1). For
min{K,n0 +1} ≤ k1, . . . , kn1 ≤ K, the corresponding set has positive measure. Here S ∈ ( [n1] j ) means that S is a subset of [n1] := {1, . . . , n1} of cardinality |S| = j.
• Consider a network with n0 inputs and L layers of n1, . . . , nL rank-K maxout units, K ≥ 2, nln0 even. Then, for each choice of 1 ≤ kli ≤ K, i = 1, . . . , n0, l = 1, . . . , L, there are parameters for which the number of linear regions is ∏L l=1 ∏n0 i=1( nl n0
(kli − 1) + 1). There is a positive measure subset of parameters for which the latter is the number of linear regions over (0, 1)n0 .
The proof is provided in Appendix B. The result shows that maxout networks have a multitude of positive measure subsets of parameters over which they attain widely different numbers of linear regions. In the last statement of the theorem we consider inputs from a cube, but qualitatively similar statements can be formulated for the entire input space.
There are specific parameter values for which the network represents functions with very few linear regions (e.g., setting the weights and biases of the last layer to zero). However, the smallest numbers of regions are only attained over null sets of parameters: Theorem 8 (Generic lower bound on the number of linear regions). Consider a rank-K maxout network, K ≥ 2, with n0 inputs, n1 units in the first layer, and any number of additional nonzero width layers. Then, for almost every choice of the parameters, the number of linear regions is at least∑n0 j=0 ( n1 j ) and the number of bounded linear regions is at least ( n1−1 n0 ) .
This lower bound has asymptotic order Ω(nn01 ) in K and n1, . . . , nL. The proof is provided in Appendix B. To our knowledge, this is the first non-trivial probability-one lower bound for a maxout network. Note that this statement does not apply to ReLU networks unless they have a single layer of ReLUs. In the next section we investigate the expected number of activation regions for given probability distributions over the parameter space.

heading: 4 Expected number and volume of activation regions
text: For the expected number of activation regions we obtain the following upper bound, which corresponds to a maxout version of (Hanin and Rolnick, 2019b, Theorem 10). Theorem 9 (Upper bound on the expected number of partial activation regions). Let N be a fullyconnected feed-forward maxout network with n0 inputs and a total of N rank K maxout units. Suppose we have a probability distribution over the parameters so that:
1. The distribution of all weights has a density with respect to the Lebesgue measure on R#weights.
2. Every collection of biases has a conditional density with respect to Lebesgue measure given the values of all other weights and biases.
3. There exists Cgrad > 0 so that for any t ∈ N and any pre-activation feature ζz,k,
sup x∈Rn0
E[‖∇ζz,k(x)‖t] ≤ Ctgrad.
4. There exists Cbias > 0 so that for any pre-activation features ζ1, . . . , ζt from any neurons, the conditional density of their biases ρb1,...,bt given all the other weights and biases satisfies
sup b1,...,bt∈R
ρb1,...,bt(b1, . . . , bt) ≤ Ctbias.
Fix r ∈ {0, . . . , n0} and let T = 25CgradCbias. Then, there exists δ0 ≤ 1/(2CgradCbias) such that for all cubes C ⊆ Rn0 with side length δ > δ0 we have
E[# r-partial activation regions of N in C] vol(C) ≤  ( rK 2r )( N r ) KN−r, N ≤ n0
(TKN)n0(n0K2n0 ) (2K)rn0! , N ≥ n0 .
Here the expectation is taken with respect to the distribution of weights and biases inN . Of particular interest is the case r = 0, which corresponds to the number of linear regions.
The proof of Theorem 9 is given in Appendix E. The upper bound has asymptotic order O(Nn0K3n0−r) in K and N , which is polynomial. In contrast, Montúfar et al. (2021) shows that the maximum number of linear regions of a deep network of width n is Θ((nK) n0 n N ), which for constant width is exponential in N ; see Appendix B. We present an analogue of Theorem 9 for networks without biases in Appendix G.
When the rank is K = 2, the formula coincides with the result obtained previously by Hanin and Rolnick (2019b, Theorem 10) for ReLU networks, up to a factor Kr. For some settings, we expect that the result can be further improved. For instance, for iid Gaussian weights and biases, one can show that the expected number of regions of a rank K maxout unit grows only like logK, as we discuss in Appendix C.
We note that the constants Cbias and Cgrad only need to be evaluated over the inputs in the region C. Intuitively, the bound on the conditional density of bias values corresponds to a bound on the density of non-linear locations over the input. The bound on the expected gradient norm of the pre-activation features is determined by the distribution of weights. We provide more details in Appendix F.
For the expected volume of the r-dimensional part of the non-linear locus we obtain the following upper bound, which corresponds to a maxout version of (Hanin and Rolnick, 2019a, Corollary 7). Theorem 10 (Upper bound on the expected volume of the non-linear locus). Consider a bounded measurable set S ⊂ Rn0 and the settings of Theorem 9 with constants Cgrad and Cbias evaluated over S. Then, for any r ∈ {1, . . . , n0},
E[voln0−r(XN ,r ∩ S)] voln0(S)
≤ (2CgradCbias)r ( rK
2r
)( N
r
) .
The proof of Theorem 10 is given in Appendix D. When the rank is K = 2, the formula coincides with the result obtained previously by Hanin and Rolnick (2019a, Corollary 7) for ReLU networks. A table comparing the results for maxout and ReLU networks is given in Appendix E.

heading: 5 Expected number of pieces and volume of the decision boundary
text: In the case of classification problems, we are primarily interested in the decision boundary, rather than the overall function. We define an M -class classifier by appending an argmax gate to a network with M outputs. The decision boundary is then a union of certain r-partial activation regions for the network with a maxout unit as the output layer. For simplicity, here we present the results for
the n0 − 1-dimensional regions, which we call ‘pieces’, and present the results for arbitrary values of r in Appendix H. The number of pieces of the decision boundary is at most equal to the number of activation regions in the original network times ( M 2 ) . A related statement appeared in Alfarra et al. (2020). For specific choices of the network parameters, the decision boundary does intersects most activation regions and can have as many as Ω(M2 ∏L l=1(nlK)
n0) pieces (see Appendix H). However, in general this upper bound can be improved. For the expected number of pieces and volume of the decision boundary we obtain the following results. We write XDB for the decision boundary, and XDB,r for the union of r-partial activation regions which include equations from the decision boundary (generically these are the co-dimension-r pieces of the decision boundary).
Theorem 11 (Upper bound on the expected number of linear pieces of the decision boundary). LetN be a fully-connected feedforward maxout network, with n0 inputs, a total of N rank-K maxout units, and M linear output units used for multi-class classification. Under the assumptions of Theorem 9, there exists δ0 ≤ 1/(2CgradCbias) such that for all cubes C ⊆ Rn0 with side length δ > δ0,
E [
# linear pieces in the decision boundary ofN in C ] vol(C) ≤  ( M 2 ) KN , N ≤ n0 (24CgradCbias) n0 (2KN)n0−1
(n0−1)! ( M 2 )( K(n0−1) 2(n0−1) ) , N ≥ n0 .
Here the expectation is taken with respect to the distribution of weights and biases in N .
For binary classification, M = 2, this bound has asymptotic order O((K3N)n0−1) in K and N . For the expected volume we have the following.
Theorem 12 (Upper bound on the volume of the (n0 − r)-skeleton of the decision boundary). Consider a bounded measurable set S ⊂ Rn0 . Consider the notation and assumptions of Theorem 9, whereby the constants Cgrad and Cbias are over S. Then, for any r ∈ {1, . . . , n0} we have
E[voln0−r(XDB,r ∩ S)] voln0(S)
≤ (2CgradCbias)r min{M−1,r}∑
i=1
( M
i+ 1 )( K(r − i) 2(r − i) )( N r − i ) .
Moreover, the expected distance to the decision boundary can be bounded as follows.
Corollary 13 (Distance to the decision boundary). Suppose N is as in Theorem 9. For any compact set S ⊂ Rn0 let x be a uniform point in S. There exists c > 0 independent of S so that
E[distance(x,XDB)] ≥ c
2CgradCbiasMm+1m ,
where m := min{M − 1, n0}.
The proofs are presented in Appendix H, where we also extend Theorem 11 to address the expected number of co-dimension-r pieces of the decision boundary. A corresponding result applies for the case of ReLU networks (see details in Appendix H).

heading: 6 Experiments
text: In the experiments we used fully-connected networks. We describe the network architecture in terms of the depth and total number of units, with units evenly distributed across the layers with larger lower layers if needed. For instance, a network of depth 3 with 110 units has 3 hidden layers of widths 37, 37, 36. Details and additional experiments are presented in Appendix K. The computer implementation of the key functions is available on GitHub at https://github.com/ hanna-tseran/maxout_complexity.
Initialization procedures We consider several initialization procedures detailed in Appendix J: 1) ReLU-He initializes the parameters as iid samples from the distribution proposed by He et al. (2015) for ReLUs. 2) Maxout-He follows a similar reasoning to normalize the expected norm of activation vectors across layers, but for the case of maxout networks. The weight distribution has standard deviation depending on K and the assumed type of data distribution, as shown in Table 1. 3) “Sphere” ensures each unit has the maximum number of regions. 4) “Many regions” ensures each layer has the maximum number of regions.
Algorithm for counting activation regions Several approaches for counting linear regions of ReLU networks have been considered (e.g., Serra et al., 2018; Hanin and Rolnick, 2019b; Serra and Ramalingam, 2020; Xiong et al., 2020). For maxout networks we count the activation regions and pieces of the decision boundary by iterative addition of linear inequality constraints and feasibility verification using linear programming. Pseudocode and complexity analysis are provided in Appendix I.
Number of regions and decision boundary for different networks Figure 2 shows a close agreement, up to constants, of the theoretical upper bounds on the expected number of activation regions and on the expected number of linear pieces of the decision boundaries with the empirically obtained values for different networks. Further comparisons with constants and different values of K are provided in Appendix K. Figure 3 shows that for common parameter distributions, the growth of the expected number of activation regions is more significantly determined by the total number of neurons than by the network’s depth. In fact, we observe that for high rank units and certain types of distributions, deeper networks may have fewer activation regions. We attribute this to the fact that higher rank units tend to have smaller images (since they compute the max of more pre-activation features). Figure 4 shows how n0 and K affect the number of activation regions. For small input dimension, the number of regions per unit tends to be smaller than K. Indeed, for iid Gaussian parameters the number of regions per unit scales as logK (see Appendix C).
Number of regions during training We consider the 10 class classification task with the MNIST dataset (LeCun et al., 2010) and optimization with Adam (Kingma and Ba, 2015) using different initialization strategies. Notice that for deep skinny fully connected networks the task is non-trivial. Figure 5 shows how the number of activation regions evolves during training. Shown are also the linear regions and decision boundaries over a 2D slice of the input space through 3 training data points. Figure 6 shows the training loss and accuracy curves for the different initializations. We observe that maxout networks with maxout-He, sphere, and many regions converge faster than with naive He initialization.

heading: 7 Discussion
text: We advance a line of analysis recently proposed by Hanin and Rolnick (2019a,b), where the focus lies on the expected complexity of the functions represented by neural networks rather than worst case bounds. Whereas previous works focus on single-argument activations, our results apply to networks with multi-argument maxout units. We observe that maxout networks can assume widely different numbers of linear regions with positive probability and then computed an upper bound on the expected number of regions and volume given properties of the parameter distribution, covering the case of zero biases. Further, taking the standpoint of classification, we obtained corresponding results for the decision boundary of maxout (and ReLU) networks, along with bounds on the expected distance to the decision boundary.
Experiments show that the theoretical bounds capture the general behavior. We present algorithms for enumerating the regions of maxout networks and proposed parameter initialization strategies with two types of motivations, one to increase the number of regions, and second, to normalize the variance of the activations similar to Glorot and Bengio (2010) and He et al. (2015), but now for maxout. We observed experimentally that this can improve training in maxout networks.
Limitations In our theory and experiments we have considered only fully connected networks. The analysis and implementation of other architectures for experiments with more diverse datasets are interesting extensions. By design, the results focus on parameter distributions which have a density.
Future work In future work we would like to obtain a fine grained description of the distribution of activation regions over the input space depending on the parameter distribution and explore the relations to speed of convergence and implicit biases in gradient descent. Of significant interest would be an extension of the presented results to specific types of parameter distributions, including such which do not have a density or those one might obtain after training.
Discussion of potential negative societal impacts This is foundational research and not tied to particular applications. To the best of our knowledge there are no direct paths to negative societal impacts.
Funding transparency statement This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no 757983).

Review summaries:
This articles provides bounds for both average case and worst case complexity (in terms of number of linear regions and related measures) for max-out networks. I found the article to have a few results that were interesting (to do with the difference between ReLU and max-out), a few results that were correct but rather incremental (average case analysis of number of regions for max-out networks), and one result whose proof I cannot understand (though it may well be true).   After rebuttal: I am satisfied with the replies of thr authors and am raising my score by 1.

EDIT: I have read the authors' response and decided to keep my (positive) score.  The paper studies the problem of expressivity of feedforward neural networks with maxout (multi-argument) activation functions. Maxout units compute parametric affine functions followed by a fixed multi-argument activation function of the form (s1, . . . , sK)→max{s1, . . . , sK}.  A special case of course is ReLU nets, and many prior results have been obtained, showing how the activation patterns and linear regions of the network depend on the architecure of the network, mainly the depth and the width. For example, Telgarsky's "Benefits of depth in neural networks." paper, shows how depth in neural nets can be exponentially more efficient that width in representing certain functions like the triangular wave and compositions with itself.   The question that is raised here however is how do the linear regions of maxout nets look like for "practical" neural nets. Practical here, just means networks initialized with a multitude of different distributions that are common in practice. The importance of this question is motivated by understanding average case performance instead of worst-case performance. This reflects an approach originally put forth by two works of Hanin and Rolnick.  Briefly, the main results of the paper generalize prior results for ReLUs to the case of maxout networks. For example, the main result of the paper is Theorem 9 and 10 that state that for most parameter settings in the network, the expected number of activation regions is polynomial in the number of units. This comes in contrast with Telgarsky's and follow-up works that give exponential bounds for deep ReLU nets.