Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.




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.

Many 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. 

The 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.

Questions to the authors:

The 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? 

A 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)? 
limitations_and_societal_impact: none
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

Although 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.

I 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.

Questions and comments to the authors:
- In line 19, what do you mean by "generic"?
- In line 122, why does r go up to n_0?
- Do activation regions correspond to linear regions (line 130) and vice versa (line 133)? The paragraph says one thing, and the result says another.
- Figure 1 Right is not clear. Can you please describe it in more detail?
- 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)?
- How can a linear region have finite volume (line 158), if in some cases it is unbounded?
- Theorem 8 seems to be more of a Lemma or even a Proposition that could also apply to ReLU given hyperplanes in general position. 
- In section 5, can you provide a clear definition by what you mean with the pieces of the decision boundary?

Other stylistic comments:
- In line 159, add "about" between question and which.
- 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.
- First bullet point of Theorem 7 could be a corollary.
- Second bullet point of Theorem 7 could be a separate result.
- Remove repeated for in line 203.

Literature review:
- In line 33, another related work on function-preserving transformations is [1].
- In line 34, another related work on robustness based on linear regions is [2].
- 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].
- In line 304, is Xavier and He a missing reference?

[1] https://arxiv.org/abs/2001.00218

[2] https://arxiv.org/abs/1907.03207

[3] https://arxiv.org/abs/1810.03370

[4] https://arxiv.org/abs/2102.11535
limitations_and_societal_impact: Limitations and social impact are clearly discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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). 

After rebuttal: I am satisfied with the replies of thr authors and am raising my score by 1.
main_review: Strengths:

1. I found this article to be clearly written.

2. I believe most of the results in this article are correct and correctly proved (see point 2 in weaknesses below for a concern).

3. 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. 

4. It was interesting to see the difference between ReLU and max-out complexity, even for one layer networks. 


Weaknesses:

1. 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. 

2. 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.


Minor Remarks/Comments:

1. In Definition 1: why the word continuous? 
2. In Theorem 7: The notation S \subseteq \binom{[n_1]}{j} should probably be defined? 
3. In Theorem 9: “for for” in condition 3
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

The experiments are certainly useful but they do not demonstrate clear applications of this work.

Note: rating changed from 5 to 6 following discussion.
limitations_and_societal_impact: N/A
review_title: null

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)