On the number of inference regions of deep feed forward networks with piece-wise linear activations
Authors: Razvan Pascanu, Guido F. Montufar, Yoshua Bengio
ICLR 2014

Abstract: This paper explores the complexity of deep feed forward networks with linear presynaptic couplings and rectified linear activations. This is a contribution to the growing body of work contrasting the representational power of deep and shallow network architectures. In particular, we offer a framework for comparing deep and shallow models that belong to the family of piece-wise linear functions based on computational geometry. We look at a deep (two hidden layers) rectifier multilayer perceptron (MLP) with linear outputs units and compare it with a single layer version of the model. In the asymptotic regime as the number of units goes to infinity, if the shallow model has $2n$ hidden units and $n_0$ inputs, then the number of linear regions is $O(n^{n_0})$. A two layer model with $n$ number of hidden units on each layer has $Omega(n^{n_0})$. We consider this as a first step towards understanding the complexity of these models and argue that better constructions in this framework might provide more accurate comparisons (especially for the interesting case of when the number of hidden layers goes to infinity).


Peer review:
[Review]:
I like the topic of this paper, but I found it very difficult to read.  

Although I don't have many specific suggestions along these lines, I feel like it could probably be made much easier to understand if the proofs were introduced with more simple English explanations of how the proofs work.  It seems like the main issue is generally showing how Zaslavsky's Theorem can be applied to specific scenarios that arise using deep networks.  

I think you should define what you mean by a 'region' or 'region of linearity' or 'input space partition region' and use one term consistently (I think these are all the same thing?)

In figure 2, I would add plots of what lower levels look like, so we can see how the final plot emerges.  

I don't follow the proofs of Proposition 8 or 9.

In proposition 8, I think the first summation should be up to n_1 and summing n_2 choose k?

I would move the definitions of big-O, Omega and Theta notation to the preliminaries.

You need to add Zaslavsky to the citations.

I think equation (13) has a typo.  Should 2n_0 be 2^{n_0}?   

I don't follow the part about how linearity is not a restriction in the Discussion; in fact, I'm not sure exactly what is meant by that statement.  



Little edits:
proof of lemma 4: 'the regions of linear behavior [...] ARE'

below equation (3) 'the first layer has TWO operational modes'

later that paragraph: 'gradient equal to vr_i' should just be r_i, I think.  

Proposition 6: your proof sketch only demonstrates the formula for r(A), not b(A); you should say that.  

Section 4:
you define but never use b(n_0,n_1).  You don't specify, but I assume that r and u mentioned below are the r(n_0,n_1), u(n_0,n_1) you define.  I would use n = n_1 and d = n_0 in this definition, for clarity.  

Discussion: say 'e.g.' or 'for example', but not 'for e.g.'