Published as a conference paper at ICLR 2018 UNDERSTANDING DEEP NEURAL NETWORKS WITH RECTIFIED LINEAR UNITS
In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give an algorithm to train a ReLU DNN with one hidden layer to global optimality with runtime polynomial in the data size albeit exponential in the input dimension. Further, we improve on the known lower bounds on size (from exponential to super exponential) for approximating a ReLU deep net function by a shallower ReLU net. Our gap theorems hold for smoothly parametrized families of "hard" functions, contrary to countable, discrete families known in the literature. An example consequence of our gap theorems is the following: for every natural number k there exists a function representable by a ReLU DNN with k 2 hidden layers and total size k 3 , such that any ReLU DNN with at most k hidden layers will require at least 1 2 k k+1 − 1 total nodes. Finally, for the family of R n → R DNNs with ReLU activations, we show a new lowerbound on the number of affine pieces, which is larger than previous constructions in certain regimes of the network architecture and most distinctively our lowerbound is demonstrated by an explicit construction of a smoothly parameterized family of functions attaining this scaling. Our construction utilizes the theory of zonotopes from polyhedral theory.
The paper presents a series of definitions and results elucidating details about the functions representable by ReLU networks, their parametrisation, and gaps between deep and shallower nets. 
The paper is easy to read, although it does not seem to have a main focus (exponential gaps vs. optimisation vs. universal approximation). The paper makes a nice contribution to the details of deep neural networks with ReLUs, although I find the contributed results slightly overstated. The 1d results are not difficult to derive from previous results. The advertised new results on the asymptotic behaviour assume a first layer that dominates the size of the network. The optimisation method appears close to brute force and is limited to 2 layers. 
Theorem 3.1 appears to be easily deduced from the results from Montufar, Pascanu, Cho, Bengio, 2014. For 1d inputs, each layer will multiply the number of regions at most by the number of units in the layer, leading to the condition w’ \geq w^{k/k’}. Theorem 3.2 is simply giving a parametrization of the functions, removing symmetries of the units in the layers. 
In the list at the top of page 5. Note that, the function classes might be characterized in terms of countable properties, such as the number of linear regions as discussed in MPCB, but still they build a continuum of functions. Similarly, in page 5 ``Moreover, for fixed n,k,s, our functions are smoothly parameterized''. This should not be a surprise. 
In the last paragraph of Section 3 ``m = w^k-1'' This is a very big first layer. This also seems to subsume the first condition, s\geq  w^k-1 +w(k-1) for the network discussed in Theorem 3.9. In the last paragraph of Section 3 ``To the best of our knowledge''. In the construction presented here, the network’s size is essentially in the layer of size m. Under such conditions, Corollary 6 of MPCB also reads as s^n. Here it is irrelevant whether one artificially increases the depth of the network by additional, very narrow, layers, which do not contribute to the asymptotic number of units. 
The function class Zonotope is a composition of two parts. It would be interesting to consider also a single construction, instead of the composition of two constructions. 
Theorem 3.9 (ii) it would be nice to have a construction where the size becomes 2m + wk when k’=k. 
Section 4, while interesting, appears to be somewhat disconnected from the rest of the paper. 
In Theorem 2.3. explain why the two layer case is limited to n=1. 
At some point in the first 4 pages it would be good to explain what is meant by ``hard’’ functions (e.g. functions that are hard to represent, as opposed to step functions, etc.)