On the Expected Complexity of Maxout Networks
Authors: Hanna Tseran
Guido Montufar
Venue: NeurIPS 2021 Poster (2021)
Keywords: linear regions of neural networks
maxout units
expected complexity
decision boundary
parameter initialisation

Abstract: Learning with neural networks relies on the complexity of their representable functions, but more importantly, their 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. 


On the Expected Complexity of Maxout Networks
Hanna Tseran
Max Planck Institute for Mathematics in the Sciences
04103 Leipzig, Germany
hanna. tseran@mis. wtw.dmii..mm.d.....mmmm mpg.de
Guido Montúfar
Department of Mathematics and Department of Statistics, UCLA
Los Angeles, CA 90095, USA; Max Planck Institute for Mathematics in the Sciences 04103 Leipzig, Germany montuf anntufrr@math.. www.rrtttttttttate.eeeeeeeeaaeee ucla..ll....
Abstract
Learning with neural networks relies on the complexity of the representable func- tions, 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 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, investigate different parameter initialization procedures and show that they can increase the speed of convergence in training.
Introduction
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 (81...., . + max(s1,- 8x} and can be regarded as natural generalization of ReLUs, which have single-argumen activation function s + max(0, (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 (affine) linear. We 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 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 func- tions, 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, [aascanu al. (2013); Montúfar 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 (NcurIPS 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 innction-preserving 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 re 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 (guyyen et al. 2020
transformations of the network weights (Phuong and Lampert
Maximum number of regions Especially the maximum number of linear regions has been studied intensively. In particular, Montúfar )0: [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 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. (0200), 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, 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 by for the case of ReLU networks or single- argument piecewise linear activations. They show that if one has 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 arrange- ments, which have been investigated since the 19th century (Steiner) 1826 [uck 1943 Zaslavsky 1975). Hence, the main challenge in these works 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.] (213)); Montúfar et al. (2014); /Serra et al. (2018). Recently, Monttfar 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.
The activation regions of neural networks can be approached from several per- spectives. In particular, the functions represented by networks with piecewise linear activations correspond so-called tropical rational functions and can be studied from the perspective of tropical geometry (Zhang et al. 22018] 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 mieddinnnioonal paths on the input space, which also leads to depth separation results. Recent work (Hanin et al.)
Related notions
202T 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 B) These results advance the maximum complexity analysis of Montúfar et al. (202T) 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
2

---

dimensions is polynomial in the number of units (Theorem 10 These results correspond to maxout versions of results from Hanin and Rolnick (2019b) and and Hanin and Rolnick (2019a).
For class classifiers, we obtain an upper bound on the expected number of linear pieces
(Theorem [1 and the expected volume (Theorem 12) of the decision boundary, along with lower
bound on the expected distance between input points and decision boundaries (Corollary [3].
We provide an algorithm and implementation for counting the number of linear regions of maxout networks (Algorithm D
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. 2013). and observe experimentally that these can lead to faster convergence traiiig.
2
Activation regions of maxout networks
We consider feedforward neural networks with ng inputs, hidden layers of widths ni ....... nT, and no skip connections, which implement functions of the form f = sb tb. .... Φ1. The I-th hidden layer implements a function Φt: _R - R with output coordinates, i.e. units, given by trainable affine functions followed by fixed real-valued activation function, and : R + R is linear output layer. We denote the total number of hidden units by V = 71 + .... + nL and index them by E [A] == (1, N.}. The collection of all trainable parameters is denoted by 0.
We consider networks with maxout units, introduced by Goodfellow et al. (003)). rank-K maxout by where wp E RR"
unit with n inputs implements function R - I;; x + maX R] 20g and by E R,, l E [K], are trainable weights and biases. The activation function (81,-.., ,8x) + .1.......... .K) } can be regarded as multi-argumenn generalization of the rectified linear unit (RcLU) activation function + ma s). The K arguments of the maximum are called the pre-activation features of the maxout unit. For unit z in maxout network, we denote C2 0) its k-th antivvtivttion feature, considered as function of the input to the network.
For any choice of the trainable parameters, the function represented by maxout network is piecewise linear, meaning it splits the input space into countably many regions over each of which it is linear.
Definition (Linear regions). Let f: R + R a piecewise linear function. A linear region of f is a maximal connected subset of th which f has 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 network with N rank-K maxout units is an assignment of a non-empty set J. S [K] to each unit 2 E [N]. An activation pattern (Jz) [JM)) with ΣxE[N] 1) 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 denoted P,. An activation sub-pattern is pattern where we disregard all J3 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 S,.
Definition 3 (Activation regions). Consider a network N with N maxout units. For any parameter value 0 and any activation pattern J, the corresponding activation region is
R(J, 0) == {x E R"
argmax Ço, (x; = J2 for each 2 E [N]]. kE(K]
For any r e {O.....mo) no we denote the union of r parrtil activation regions by
Xv,r(0) (0)
U RJ:6)). JEP,
By these definitions, we have decomposition of the input space disjoint union of activation regions, R = L[J, 8). See Figure [ Next we observe that for almost every choice of 6, r-partial activation regions are either empty or relatively open convex polyhedra of co-dimension In particular, for almost every choice of the parameters, if is larger than ng, the r-partial activation regions are empty. Therefore, in our discussion we only need to consider up 1ag-
Lemma 4 (r-partial activation regions are relatively open convex polyhedra). Consider a maxout network N. Let r E (O..... ..)) and J E Py. Then for any 0, R(J,0) relatively open convex polyhedron in no For almost every 0, it is either empty or has co-dimension
3

---

The proof of Lemma 4 is given in Appendix A Next we show that for almost every choice of A, O-partial activation regions and linear regions correspond to each other.
Lemma (Activation regions vs linear regions). Consider maxoul network N. The set of parameter values 0 for which the represented function has the same gradient on two distinct activation regions a null set. In particular, for almost every 8, linear regions and activation regions correspond to each other.
The proof of Lemma 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 0, the O-partial activation regions are no- dimensional open convex polyhedra which agree with the linear regions of the represented function, and for ....., Ng 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 imput space. We are concerned with their generic numbers, where we use "generic" in the standard sense, to refer to positive I Lebesgue measure event.
3 Numbers of regions attained with positive probability
We start with a simple upper bound.
Lemma 6 (Simple upper bound on the number of r-partial activation patterns), Let r E No. The number of r-partial activation patterns and sub sub-patterns in network with a total of N rank-K maxout units are upper bounded by (Pr
(
KN-r and |S,| S (2x) (+) respectively.
The upper bound has asymptotic order ONNKK*+ in and N. The proof of Lemma Appendix A where we also provide an exact but unhandy counting formula.
6 is given in
By definition, the number of r-partial activation patterns is 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.) obtained bounds for the maximum number linear regions. For a shallow network with no inputs and a single layer of n, rank-K maxout units it has order O((n, ))))) in K and n, and for a deep network with no inputs and L layers of n,,,.., 7, rank-K K maxout units it has
order @ (m: (o) in K and Ri,.... Pz., Hence the maximum number of non-empty activation regions can 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.c. over positive Lebesgue measure subsets of parameter values. number of linear regions of maxout network a very intricate function of the parameter values.
shows that the
For a network with no inputs and a single layer of nı ReLUs, the maximum number of linear regions is Eno (")), , and is attained for almost all parameter values. This is 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) + by = (w,, x) + by but also linear inequalities (wi, x) + b; 2 (Wk, x) + bu- See Figure for example. We obtain the following result.
Theorem 7 (Numbers of linear regions).
Consider rank-K, K maxout unit with no inputs. This corresponds to network with an imput layer of size no and single maxout layer with a single maxout unit. For each < K, there a of parameter values for which the number of linear regions is k. For min K, no + < k < K, the corresponding set has positive measure, and else it a null set.
Consider a layer of nı rank-K maxout units with no inputs. This corresponds to a network with a single maxout layer, L = 1, and nt, n4. For each choice of & kl,..., Kny < K, there are parameters for which the number of linear regions is E/e Ese((mn)) IIees (k: 1). For

---

Activation regions
Number of linear regions
S
R[L.1]
R0.33 3)
22
003.3)
E1
21
Figure I: Left: Shown is piecewise linear function IR? - IR represented by a network with layer of two rank-3 maxout units for choice the parameters. The input space is subdivided into activation regions R(J;0) 0) with linear regions separated by Xi (0). Right: Shown is the number of linear regions of layer maxout network over a portion of the input space as function of 2D affine subspace of parameter values ((E1. E2). Shown are also two examples of the input-space subdivisions of functions represented by the network for different parameter values. More details about this figure are given in Appendix K As the figure illustrates, the function taking parameters to number of regions is rather intricate. In this work we characterize values attained with positive probability and upper bound the expected value given parameter distribution.
min{K, K, To +1 S ki,...., kin I K, the corresponding set has positive measure. Here S E ((rss)) means that S is subset of [m1] == (L,...,m1} of cardinality [S]
Consider network with no inpuls and L, layers of ..,..... Y. runk-K K maxout units, K 2 2, even. Then, for each choice of 1 I kni < K, i L, Ro. L 1, ..... L, there parameters for which the number of linear regions is II I nL (ku 1) + 1). There is positive measure subset of parameters for which the latter the number of linear regions over (0, 1)
The proof is provided in Appendix B The result shows that maxout networks have 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 cube, but qualitatively similar statements can 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 zero). However, the smallest numbers of regions are only attained over null sets of parameters:
Theorem (Generic lower bound on the number of linear regions). Consider a rank- maxout network, K 2 2, with ng inputs, units in the first layer, and any number additional nonzero width layers. Then, for almost every choice of the parameters, the number of linear regions is at least En (?)) and the number of bounded linear regions at least (P1-1))
This lower bound has asymptotic order ((n in K and Ri....,, nhg The proof is provided in Appendix [ To our knowledge, this the first non-trivial probability-one lower bound for 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.
Expected number and volume of activation regions
For the expected number activation regions we obtain the following upper bound, which corre- sponds maxout version of (Hanin and Rolnick 2019b Theorem 10).
Theorem 9 (Upper bound on the expected number of partial activation regions). Let N be fully- connected feed-forwatt maxout network with no inputs and a total of N rank K maxout units. Suppose have a probability distribution over the parameters that:
5

---

1. The distribution of all weights has a density with respect to the Lebesgue measure on R Wweightss
2. Every collection of biases has a conditional density with respect to Lebesgue measure given the values of all other weights and biases.
There exists Cgrad > 0 so that for any and any pre-activation feature Sa.k
sup
"rad-
xER
There exists Chins 0 so that for any pre-activation features Ct,..., from any neurons, the conditional density of their biases Pbu....b given all the other weights and biases satisfies
sup Pbi bbb.....b....... (bI...., by) S Chius
bi.....bEE EB
Fix r E (0....,,10) and let 2 Cona Then, there exists ån S 1/((Ogrrat graag Chins) such that for all cubes C C IR no with side length 8 >> ōg we have
(*)
N S n1
Ei# r-partial activation regions of N Wnn vol(C)
(TKN) (PO
(2K)-mo!
n1
Here the expectation is taken with respect to the distribution of weights and biases in N. Of particular interest is the case r = 0, which corresponds to the number of linear regions.
The proof of Theorem is given in Appendix E The upper bound has asymptotic order O K3no-T) in and N, which is polynomial. In contrast, Montúfar et al. (2021) shows
that the maximum number of linear regions of deep network of width is ((nn)) = N), which for constant width is exponential in N: see Appendix B
We present an analogue of Theorem for
9
networks without biases in Appendix G
When the rank is K the formula coincides with the result obtained previously by Hanin and Rolnick (2019b] Theorem 10) for ReLU networks, up to a factor K". 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 log K, 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 bound the density of non-linear locations over the input. The bound on the expected gradient norm of the pre-activation features determined by the distribution of weights. We provide more details in Appendix FF
For the expected volume of the r-dimensional part the non-linear locus we obtain the following upper bound, which corresponds to maxout version of (Hanin and Rolnick] 2019a Corollary 7).
Theorem 10 (Upper bound on the expected volume of the non- non-linear locus). Consider bounded measurable set RS and the settings of Theorem 9 with constants Cerad and Coius evaluated over S. Then, for any r E (l,..., no)
E E|volno- (Nv. (NS)
(rK) 2r
(2Cggmarina
volng (S)
The proof of Theorem 10 is given in Appendix D W When the rank 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
5 Expected number of pieces and volume of the decision boundary
In the case of classification problems, we are primarily interested in the decision boundary, rather than the overall function. We define M-class classifier by appending argmax gate to network with M outputs. The decision boundary then a union of certain r-partial activation regions for the network with maxout unit as the output layer. For simplicity, here we present the results for

---

the no 1-dimensional regions, which we call 'pieces', and present the results for arbitrary values of Appendix H The number of pieces of the decision boundary is most equal the number of activation regions in the original network times (2) A related statement appeared in Alfarra
et al. (2200). For specific choices of the network parameters, the decision boundary does intersects most activation regions and can have many S2(M2 IT (m; )*)) 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 XDn for the decision boundary, and AD for the union of r-partial activation regions which include equations from the decision boundary (generically these the co-dimension-r pieces of the decision boundary).
Theorem 11 (Upper bound the expected number of linear pieces of the decision boundary). Let A be a fully-connected feedforward maxout network, with no 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 dn S 12(Carra Criis) such that for all cubes C C Re with side length o > do.
E linear pieces decision boundary of N in C.
()) (2' 3 (2KK)))0
N 110
CCl
(K ( (((m-1))
N no
(ng-1)) 1
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((K2N))0-)) in K and N. For the expected volume we have the following.
Theorem 12 (Upper bound on the volume of the (no - rk-skeleton of the decision boundary). Consider bounded measurable S C R Consider the notation and assumptions of Theorem
whereby the constants Cgrad and Crius are over S. Then, for any r E {1,..., .oo we have
E|volno- Silio-rr(nnn (XDB,r (S))] I (2Cgraa )"
min
Σ
M
K(r 1) ( N..
1((=1) 2(r
volng (S)
i+1)
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 C Rn let be a uniform point in S. There exists e independent of S so that
[]distance(x,xXonn 2 20 Chias M Mm++mm
where := min(fM 1, n.
The proof's are presented in Appendix H. where we also extend Theorem I1 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..
to address the expected
Experiments
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, 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: /eggtgttuuuub com/ hanna- www.sserranmaxouu...m. complexity
Initialization procedures We consider several initialization procedures detailed in Appendix [ 1) ReLU-He initializes the parameters as iid samples from the distribution proposed by HH 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 [ 3) "Sphere" ensures each unit has the maximum number of regions. 4) "Many regions" ensures each layer has the maximum number of regions.
7

---

Table 1: Standard deviation of the weight distribution for maxout-He initialization.
Maxout rank
Standard deviation
2
3
V V 12T/((3333 2m)m)
4
R/ 7/(333 x)m) v 0.55555mm Tu
5
ReLU
22mm
Number of activation regions
Number of pieces in the decision boundary
procktdd granch
202
Figure 2: Shown are means and stds for 30 maxout-He normal initializations for networks with K" = and no = 2. Left: Comparison of the theoretically predicted growth O(N" //n!) and the experimentally obtained number of regions for networks with different architectures. Right: Comparison of the theoretically predicted growth O(N) and the experimentally obtained number of linear pieces of the decision boundary for networks with different architectures.
Algorithm for counting activation regions Several approaches for counting linear regions of ReLU networks have been considered Be.g..,Serra et al.) 2018 Hanin and Rolnick] 20196 [Seraa and Rama
[ingam] 2020; Xiong al. 2020p. For maxout networks 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 !|
Number of regions and decision boundary for different networks Figure shows a close agree- ment, up to constants, of the theoretical upper bounds on the expected number of activation regions and the expected number of linear pieces 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 [ 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 '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 no and K affect the number of activation regions. For small input dimension, the number regions per unit tends to be smaller than K. Indeed, for iid Gaussian parameters the number of regions per unit scales as log K (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 Baj 2015) using different initialization strategies. Notice that for deep skinny fully connected networks the task is non-triviaa trivil.. Figure 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.

---

Maxout rank K = 2
Maxout rank K
Figure 3: Effect of the depth and number of neurons on the number of activation regions at initializa- tion for networks with no 2. Shown means and stds for 30 maxout-Hi He normal initializations.
Contribution per unit in a shallow network
Effect of the maxout rank
Figure 4: Left: Plotted is #regions 1/N for shallow network with N = 5. The multiplicative contribution per unit increases with the input dimension until the trivial upper bound K is reached. Right: Number of regions of 3 layer networks with no depending on K. Shown are means and stds for ReLU-He normal initializations.
Number of regions during training
Before training
After 100 epachs
Linear regions
400
Opech
Number pieces during training
Before training
After 100 epochs
Decision boundary
Strees
Figure 5: Evolution of the linear regions and the decision boundary during training on the MNIST dataset in slice determined by three random points from different classes. The network had 100 maxout units of rank K 2, and was initialized using maxout-He normal initialization. The right panel is for the 3 layer network. As expected, for the shallow rank-2 network, the number of regions is approximately constant. For deep networks observe moderate increase in the number of regions as training progresses, especially around the training data. However, the number of regions remains far from the theoretical maximum. This is consistent with previous observations for ReLU networks. There is also a slight increase the number of linear pieces in the decision boundary, and the end of training the decision boundary clearly separates the three reference points.

---

Loss the training set
Accuracy the validation
214
Adbtile socel eacct utteod.
3344
15
23
Figure 6: Comparison of training on MNIST with different initializations. All networks had 200 units, 10 layers, and maxout networks had rank K 5. Shown are averages and std (barely noticeable) over 30 repetitions. The type of initialization has significant impact on the training time of maxout networks, with maxout-He, sphere, and many regions giving better results for deep networks and larger maxout rank (more details on this in Appendix K
Discussion
We advance line of analysis recently proposed by Hanin and Rolnick (2019a|b), where the focus lies 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 types of motivations, one increase the number of regions, and second, normalize the variance of the activations similar to Glorot and Bengio (20T0) and He et al. (2013), 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 interesting extensions. By design, the results focus on parameter distributions which have a density.
Future work In future work we would like to obtain 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 parameter distributions, including such which do not have density those 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 n 757983).
10

---

References
Adiprasito, K. (2017). Lefschetz and lower bound theorems for Minkowski sums. arXiv:1711.072/8.
arXiv preprint
Alfarra, M., Bibi, A., Hammoud, H., Gaafar, M., and Ghanem, B. (2020). On the decision boundaries of deep
neural networks: A tropical geometry perspective. arXiv preprint axXiv:2002.88::1
Anstreicher, K. M. (1999). Lincar programming in O([n / In [))] operations. SIAM Journal on Optimization, 9(4):803-88) 812.
Balestriero, R., Cosentino, R., Aazhang, B., and Baraniuk, R. (2019). The geometry of deep networks: Power diagram subdivision. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems 32, pages 18832-15841. Curran Associates, Inc.
Bodnar, C., Frasca, F., Wang, G., Otter, N., Montúfar, G., Liò, P., and Bronstein, M. (2021). Weisfeiler and Lehman go topological: Message passing simplicial networks. arXiv preprint arXiv:2103.0321
Buck, R. C. (1943). Partition of space. The American Mathematical Monthly, 50(9):541-544
Bárány, I. and Vu, V. (2007). Central limit theorems for Gaussian polytopes. 35(4):1593- 1621.
The Annals of Probability,
Caron, R. and Traynor, T. (2005). The zero set of polynomial. WSMR Report, pages 05-02.
Chandru, V. and Hooker, J. (201 Optimization methods for logical inference, volume 34, John Wiley & Sons.
Charisopoulos, V. and Maragos, P. (2018). A tropical approach to neural networks with piecewise linear activations. arXiv preprint 1805vv1805.008
Croce, F,, Andriushenko, M., and Hein, M. (2019), Provable robustness ReLU networks via maximization of linear regions. In Proceedings of the Twenty- Second International Conference on Artificial Intelligence and Statisticy, volume 89 of Proceedings of Muchine Learning Research, pages 2057-2066, PMLR.
Dalcin, I., D., Paz, R. R., Kler, P. A., and Cosimo, A. (2011). Parallel distributed computing using python. Advonces in Water Resources, 34(9)1124-1139.
Glorot, X. and Bengio, Y. (2010). Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 249-256.
Goodfellow, I., Warde-Farley, D., Mirza, M., Courville, A., and Bengio, Y. (2013). Maxout networks. In International conference machine learning, pages 1319-1327.
Gover, F. and Krikorian, N. (2010). Determinants and the volumes of parallelotopes and zonotopes. Linear Algehra and its Applications, 433(1):28-40
Hanin, B., Jeong, R., and Rolnick, D. (2021), Deep ReLU networks preserve expected length. arXiv preprint arXiv:2102.1 10492.
Hanin, B. and Rolnick, D. (2019a). Complexity of linear regions in deep networks. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages
Long Beach, California, USA. PMLR.
Hanin, B. and Rolnick, D. (2019h). Deep ReLU networks have surprisingly few activation patterns. In Wallach, H., Larochelle, H., Beygelzimer, A., Alché-Buse F., Fox, E.,, and Garnett, R., editors, Advances Neural Information Processing Systems 32, pages 361-370. Curran Associates, Inc.
Harris, C. R.. Millman, K. J., der Walt,
Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J.. Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., Río, J. F., Wiebe, M., Peterson, P., Gérard- Marchant, P., Sheppard, K., Reddy, T., Weekesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. (2020). Array programming with NumPy. Nature, 585(7825):377-33 336-66..
He, K., Zhang, X., Ren. S., and Sun, J. (2015). Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026- 1034-
Hinz, P. (2021). Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networks, arXiv preprint 171144

---

Hinz, P. and Van de Geer. S. (2019). A framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networks. IEEE Transactions Information Theory, 65(11):7304-3224
Hug, D., Munsonius, G. O., and Reitzner, M. (2004). Asymptotic mean values of Gaussian polytopes. Beiträge zur Algebra und Geometrie, 45(2):531-548.
Hug. D. and Reitzner, M. (2005). Gaussian polytopes: Variances and limit theorems. Advances in Applied Probubility, 37(2)2977-320
Hunter, D. (2007). Matplotlib: 2D graphics environment. Computing in Science Engineering. 933)990-95.
Jameson, G. (2013). Inequalities for gamma function ratios. The American Mathematical Monthly, 120(10))936 940.
Jin, H. and Montúfar, G. (2020). Implicit bias of gradient descent for mean squared emoor regression with wide neural networks. arXiv preprint arXiv:2006.077 07356.
Jones, E., Oliphant, T., Peterson, P., al. (2001). SciPy: Open source scientific tools for Python.
Joswig, M. (2022). Essentials of Tropical Combinatorics. Graduate Studies in Mathematics. AMS. In preparation.
https://page. mat.//ah........................ math. bu-berlin... de/" derddd//"jjjj"/eeee jtsww//ttc///eee..eeee.....eoeet wentt/////e..eeeeeeeeeeeeeeeee.t .ttml
Kingma, D. P. and Ba. (2015). Adam: A method for stochastic optimization. In Bengio, Y. and LeCun, Y.. editors, 3rd International Conference on Learning Reprexentatinss ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
LeCun, Y., Cortes, C., and Burges, (2010). Mnist handwritten digit database. ATT Labs [Online]. Available: http://amm.lecun.comee www..//w..../eeb//miiiiiii 2.
Lee, G.-H., Alvarez-Melis, D., and Jaakkola, T. S. (2019). Towards robust, locally linear deep networks. arXiv preprint arXiv:1907.032000
Maclagan, D. and Sturmfels, B. (2015). Introduction to tropical geometry, volume 161. Providence, RI: American Mathematical Society (AMS).
McMullen, P. (1970). The maximum numbers of faces of a convex polytope. Mathematika, 17(2):19-1184
Montúfar, (2017). Notes on the number of linear regions deep neural networks. SampTA. sttps://wwz httt::://ww..eeearree researchgate http:////ttclttctto/////222/ Bttpsis222NNottt_e_e on the the__tteehuuee___ www.nruerr...... of
linear regions of deep a networks
Montúfar, G., Pascanu, R., Cho, K., and Bengio, Y. (2014), On the number of linear regions of deep neural networks. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q. editors, Advonces in Neural Information Processing Systems 27, pages 9924-2932. Curran Associates, Inc.
Montáfar, G.. Ren, Y.. and Zhang, L. (2021). Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums. arXiv preprint arX1v:2104.08135
Nadarajah, S. (2008). Explicit expressions for moments of x2 order statistics. Bull. Inst. Math. Acad. (NS), 3:433 444.
Nguyen, Q. Mondelli, M., and Montúfar, G. (2020). Tight bounds the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. arXiv preprint 16X1v:2012.11654.
Pascanu, R., Montúfar, G., and Bengio, Y. (2013). On the number of response regions of deep feed forward networks with piece-wise linear activations. In International Conference on Learning Representations 2014 (ICLR 2014), Banff, Alberta, Canada.
Paszke, A., Gross, S., Massa, F. Lerer, A., Bradbury, Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga,
L., Desmaison, A., Kopf, A., Yang. E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. (2019). Pytorch: An imperative style, high-performance deep learning library. In Advonces in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc.
Phuong, M. and Lampert, C. H. (2019). Functional vs. parametric equivalence of RcLU networks. In International Conference on Learning Representations.
Raghu, M., Poole, B., Kleinberg. J., Ganguli, S., and Sohl- Shhl-Dicsttei, J. (2017). On the expressive power of deep neural networks. In international conference machine learning, pages 2847-2854, PMLR
12

---

Serra, T., Kumar. A., and Ramalingam, S. (2020). Lossless compression of deep neural networks. In International Conference Integration of Construint Programming, Artificial Intelligence, and Operations Research, pages 417-430. Springer.
Serra, T. and Ramalingam. S. (2020). Empirical bounds linear regions of deep rectifier networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 0028-5635.
Serra, T., Tjandraatmadja. C.. and Ramalingam, S. (2018). Bounding and counting linear regions of deep neural networks. In International Conference Machine Learning, pages 4558 4566. PMLR.
Steiner, J. (1826). Einige Gesetze über die Theilung der Ebene und des Raumes. Journal für die reine und angewandte Mathematik, 1:349-364.
Steinwart, I. (2019). A sober look neural network initializations. arXiv preprint arXiv: 1903.1 11482.
Sun, W. Su, F., and Wang. L. (2018). Improving deep neural networks with multi- maxout networks and novel initialization method. Neurocomputing, 278:34-40.
Telgarsky, M. (2015). Representation benefits of deep feedforward networks. arXiv preprint arXiv: 1500:0150000801
Telgarsky, M. (2016), Benefits of depth in neural networks. In Feldman, V., Rakhlin, A., and Shamir, O., editors, 29th Annual Conference Learning Theory, volume 49 of Proceedings Machine Learning Research, pages 1517-1539, Columbia University, New York, New York, USA. PMLR.
Weibel, C. (2012). Maximal f-vectors of Minkowski sums of large numbers of polytopes. Discrete Computational Geometry, 47:519-537.
Williams, F., Trager, M., Panozzo, D., Silva, C.,, Zorin, D., and Bruna, J. (2019). Gradient dynamics of shallow univariate ReLU networks. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Gareett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Xic, Y., Chen, G., and Q (2020). general computational framework measure the expressiveness of complex networks using a tighter upper bound linear regions. arXiv preprint Xiv:20012.0442
Xiong, H., Huang, I.., Yu, M., Liu, I.., Zhu, F., and Shao, I., (2020). On the number of linear regions of convolutional neural networks. II, H. D. and Singh, A., editors, Proceedings gs of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10514- 10523. PMLR.
7aslavsky, T. (1975). Facing to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes. American Mathematical Snciety: Memoirs of the American Mathematical Society, American Mathematical Society.
Zhang, L.. Naitzat, G., and Lim, L.-H. (2018). Tropical geometry of deep neural networks. In Dy. J. and Krause, A., editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5824-5832, Stockholmsmässan. Stockholm Sweden. PMLR.
Zhang, and Wu, (2020). Empirical studies on the properties linear regions deep neural networks. International Conference on Learning Representations.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section] 7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Appendix [ and Appendix for the algorithms and Appendix for the experimental details. The
code with main routines will be submitted in the supplementary material. Complete
experimental code will not be included because it is specific to the cluster.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix K
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See beginning of Appendix K
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See beginning of Appendix|K] K
(b) Did you mention the license of the assets? [Yes] See beginning of Appendix K
(c) Did you include any new assets either the supplemental material or as URL.? (Yes]
We are including computer code as described above.
(d) Did you discuss whether and how consent
obtained from people whose data you's 're
using/curating? [N/A] We do not use any personal data.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We only use the MNIST dataset, which does not have such content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "iSidmz2r78g", "reviewer": "Reviewer_Udb7", "summary": "EDIT: I have read the authors' response and decided to keep my (positive) score.\n\nThe 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}.\n\nA 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. \n\nThe 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.\n\nBriefly, 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.\n\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "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": "", "main_review": "This is an interesting paper on a very timely topic for deep learning theory. It gives several upper and lower bounds for the activation regions of maxout networks, capturing prior works on ReLU nets.\n\nMany of the technical details rely on the works of Hanin and Rolnick and ideas in Montufar et al., however dealing with maxout activations is certainly more challenging. The techniques for analyzing ReLUs need significant changes for the arguments to pass through and altough it may appear straightforward, it certainly isn't. \n\nThe main result itself may not be too surprising given the prior results for ReLUs however the authors analyze several related questions and give a nice collection of results that deepens our understanding of activation regions, expected volume of activation regions, initialization schemes and their behavior and because of that I vote for weak accept.\n\nQuestions to the authors:\n\nThe initialization process used here is similar to Hanin and Rolnick and it seems to imply that linear regions depend only the size of the network (and only with polynomial dependence) while Telgarsky's result states that in worst-case there is exponential dependence on the depth. On the other hand, several follow-up works have shown that Telgarsky's triangle wave construction is not the only to yield exponential dependence on depth; in fact, the reason behind such exponential dependencies actually comes from ideas in dynamical systems and in particular chaos theory (see more on \"Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem\", \"Exponential expressivity in deep neural networks through transient chaos\", and \"Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems\"). The reviewer is curious to see how the parameter settings used in the present paper (and Hanin's works for that matter) can break such worst-case results since they do not particularly depend on exact parameter settings like Telgarsky's? \n\nA bit more braodly, the results in the paper seem to suggest that depth doesn't matter. Can you elaborate on why depth stops being important in such settings and only the size of the network matters? Is this sth that the authors think is in accordance with what practitioners seem to be using in practice? If not, why should we even use deep nets, if initiliazation tells us that linear regions won't significantly change (as long as size is same, we can just increase width not depth)? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_AHCM4iO7GK", "reviewer": "Reviewer_9cCV", "summary": "This paper studies the complexity of deep maxout networks from the point of view of (expected or maximal) number of linear regions. Theoretical lower and upper bound are derived, and the paper concludes with experiments to assess the quality of the theoretical bounds in trained networks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "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": "", "main_review": "The theoretical bounds are derived thoroughly. The paper puts particular emphasis on expected behavior, which should have more relevance in practice. Bounds for the expected complexity of ReLU networks were already found before, so the main novelty of this paper lies in the consideration of maxout networks instead of ReLU networks. This appears to me as a modest contribution. Perhaps the authors should consider to add a more explicit comparison of the bounds for ReLU and maxout networks and of the qualitative difference between ReLU and maxout cases, which could help appreciate the challenges and novelties of the maxout case.\n\nThe experiments are certainly useful but they do not demonstrate clear applications of this work.\n\nNote: rating changed from 5 to 6 following discussion.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FVqqZ7JeBmb", "reviewer": "Reviewer_dn4N", "summary": "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). \n\nAfter rebuttal: I am satisfied with the replies of thr authors and am raising my score by 1.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "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": "", "main_review": "Strengths:\n\n1. I found this article to be clearly written.\n\n2. I believe most of the results in this article are correct and correctly proved (see point 2 in weaknesses below for a concern).\n\n3. I thought the authors did a good job of comparing and contrasting their results on average case complexity and the results on worst case complexity. \n\n4. It was interesting to see the difference between ReLU and max-out complexity, even for one layer networks. \n\n\nWeaknesses:\n\n1. The proofs in this article for results on average number/volume of activation patterns and linear regions follow very closely prior work of Hanin and Rolnick, and I view them as incremental. \n\n2. I am not sure whether the constant C_bias and C_grad in the average case results are actually bounded as in Appendix F. The issue is that I am not certain if the analysis from the prior work Hanin and Nica extends directly to max-out units. If it does, I think the authors should consider explaining how. Otherwise, this strikes me as a major weakness since I view average case results as primarily interesting when averaging with respect to the initialization schemes really used in practice.\n\n\nMinor Remarks/Comments:\n\n1. In Definition 1: why the word continuous? \n2. In Theorem 7: The notation S \\subseteq \\binom{[n_1]}{j} should probably be defined? \n3. In Theorem 9: “for for” in condition 3", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DbCf43-zNZ", "reviewer": "Reviewer_4fmj", "summary": "This paper presents several results on the expected number of linear regions in maxout networks under mild assumptions on the parameter space. These results address a void of understanding in comparison to ReLU networks.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "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": "", "main_review": "For the most part, this paper can be regarded as an extension to maxout networks of the results in the couple of 2019 papers by Hanin and Rolnick on the expected number of linear regions of ReLU networks. However, it is a bit more than that because the multiple affine functions of maxout units make it more difficult to analyze their number of linear regions. Hence, the authors had to first characterize linear regions according to the number of affine functions being maximized per unit, and then show that under mild assumptions on their parameters those regions with multiple affine functions being simultaneously maximized are usually empty. \n\nAlthough maxout networks are not as often used as ReLU networks, I believe that this study is both valid and needed because we never know what may happen to deep learning a few years down the road. Given that maxout is also a generalization of ReLU, some of the results discussed in the paper also apply to ReLU. However, the authors interestingly observe that Lemma 5 does not apply to ReLU because of the sizeable part of the input that is mapped to 0 by each unit.\n\nI must also state that this is a mathematically heavy paper, and I cannot say that I have carefully evaluated all of their results yet. Hence, I appreciate having feedback of the authors regarding my questions below to help me complete my evaluation of their paper.\n\nQuestions and comments to the authors:\n- In line 19, what do you mean by \"generic\"?\n- In line 122, why does r go up to n_0?\n- Do activation regions correspond to linear regions (line 130) and vice versa (line 133)? The paragraph says one thing, and the result says another.\n- Figure 1 Right is not clear. Can you please describe it in more detail?\n- Would it be correct to say that Lemma 6 corresponds to every possible partial activation pattern being valid? If so, what is the purpose of stating it if there is a sharper bound in Montufar et. al. (2021)?\n- How can a linear region have finite volume (line 158), if in some cases it is unbounded?\n- Theorem 8 seems to be more of a Lemma or even a Proposition that could also apply to ReLU given hyperplanes in general position. \n- In section 5, can you provide a clear definition by what you mean with the pieces of the decision boundary?\n\nOther stylistic comments:\n- In line 159, add \"about\" between question and which.\n- Misuse of n_0 as size of maxout input, since n_0 refers to size of input layer, starting in Theorem 7. Likewise for the use of n_1 for size of the layer output.\n- First bullet point of Theorem 7 could be a corollary.\n- Second bullet point of Theorem 7 could be a separate result.\n- Remove repeated for in line 203.\n\nLiterature review:\n- In line 33, another related work on function-preserving transformations is [1].\n- In line 34, another related work on robustness based on linear regions is [2].\n- In line 268, another related work on counting linear regions is [3] and you should also refer to the sampling method in Xiong et al. (2020), which is applied in [4].\n- In line 304, is Xavier and He a missing reference?\n\n[1] https://arxiv.org/abs/2001.00218\n\n[2] https://arxiv.org/abs/1907.03207\n\n[3] https://arxiv.org/abs/1810.03370\n\n[4] https://arxiv.org/abs/2102.11535", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and social impact are clearly discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the number of linear regions (and pieces of the decision boundary) of maxout networks at initialization, showing that these numbers grow polynomially in expectation, instead of exponentially as in the worst case. This is an interesting theoretical investigation building on prior work answering the same question for ReLU networks. The reviewers note that the approaches used in this paper are somewhat incremental to this prior work, and that the upper bound on the constant C_grad presented in the paper's formal results has an exponential dependence on depth for natural initializations. However, the reviewers agree that these points do not detract from the interest and validity of the paper's results, and I recommend acceptance. 
Decision: Accept (Poster)