THE ROLE OF OVER-PARAMETRIZATION IN GENERALIZATION OF NEURAL NETWORKS
Despite existing work on ensuring generalization of neural networks in terms of scale sensitive complexity measures, such as norms, margin and sharpness, these complexity measures do not offer an explanation of why neural networks generalize better with over-parametrization. In this work we suggest a novel complexity measure based on unit-wise capacities resulting in a tighter generalization bound for two layer ReLU networks. Our capacity bound correlates with the behavior of test error with increasing network sizes (within the range reported in the experiments), and could partly explain the improvement in generalization with over-parametrization. We further present a matching lower bound for the Rademacher complexity that improves over previous capacity lower bounds for neural networks.
Let me start by apologizing for the delayed review - in fact I was asked today to replace an earlier assigned reviewer. Hopefully the clarifications I request won't be too time consuming to meet the deadline coming up. 
###
First of all, the problem which the authors are attempting to answer is quite important: the effect of over-parametrization is not well understood on a theoretical level. As the paper illustrate, 2-layer networks are already capable of generalizing while being over-parameterized, therefore justifying their setting. 
Next this paper motivates the study of complexity quantities that tend to decrease with the number of parameters, in particular figure 3 motivates the conjecture that the complexity measure in Theorem 2 can control generalization error. The paper also does a great job comparing related work, motivating their results. 
###
At this point, I would like to request a couple of clarifications in the proofs. Perhaps it's due to the fact that I only spent a day reading, but at least I think we could improve on its readability. Regardless, I currently do not yet trust a couple of the proofs, and I believe the acceptance of this paper should be conditioned on confirming the correctness of these proofs.
(1) Let's start with Lemma 10. In the middle equation block, we obtain a bound 
  \| alpha^prime \|_p^p <= beta^p ( 1 + D/K )
and the proof concludes alpha^prime is in Q. However this cannot be the case for all alpha^prime. 
Consider x=0 which is in S_{p, beta}^D, then we have alpha^prime = 0 as well. In the definition of Q, we require all the j's to sum up to K+D, which is not met here. 
At the same time, the next claim 
  \| alpha \|_2 <= D^{1/2 - 1/p} \| alpha^prime \|_p
does not seem to follow from the above calculations. In particular, alpha^prime seems to be defined with respect to an x in S_{p, beta}, however in this case we did not specify such an x. Perhaps did you mean there exist such an alpha^prime?
(2) In the proof of Theorem 3, there is an important inequality needed to complete the proof 
  max{ <s, f_i> , <s, -f_i> } >= 1/2 * ( <s, [f_i]_+> + <s, [-f_i]_+> )
Perhaps I am missing something obvious, but I believe this inequality fails when we choose s as a constant vector, and f_i to have the same number of positive and negative signs (which is possible in a Hadamard matrix). In this case, the left hand side should be equal to zero, where as the right hand side will be positive. 
###
To summarize, if these proofs can be confirmed, I believe this paper would have made significant contribution to the problem of over-parametrization in deep learning, and of course should be accepted. 
###
I corrected several typos and found minor issues as I read, perhaps this will be useful to improve readability as well.
Page 13, proof of Lemma 8
  - after the V_0 term is separated, there is a sup over \|V_0\|_F <= r in the expectation, which should be \|V-V_0\|_F <= r instead.
Page 14, Lemma 9
  - the lemma did not define rho_{ij} in the statement
Page 15, proof of Lemma 9
  - in equation (12), there is an x_y vector that should x_t
Page 15, proof of Theorem 1
  - while I eventually figured it out, it's unclear how Lemma 8 is applied here. Perhaps one more step identifying the exact matrices in the statement of Lemma 8 will be helpful to future readers, and maybe explain where the sqrt(2) factor come from as well. 
Page 16, proof of Lemma 10
  - in the beginning of the proof, to stay consistent with the notation, we should replace S_{p, beta} with S_{p, beta}^D
  - I believe the cardinality of Q should be (K + D - 1) choose (D - 1), as we need to choose positive j's to sum up to (K+D) in the definition of Q. This reduces down to the problem of choosing natural numbers j's summing K, which is (K+D-1) choose (D-1). Consider the stack exchange post here:
https://math.stackexchange.com/questions/919676/the-number-of-integer-solutions-of-equations
Page 16, proof and statement of Lemma 11
  - I believe in the first term, the factor should be m instead of sqrt(m). I think the mistake happened when applying the union bound, as it should only affect the term containing delta
Page 17, Lemma 12
  - same as Lemma 11, we should have m instead of sqrt(m)
Page 18, proof of Theorem 3
  - at the bottom the statement "F is orthogonal" does not imply the norm is less than 1, but rather we should say "F is orthonormal"
Page 19, proof of Theorem 3
  - at the top, "we will omit the index epsilon" should be "xi" instead
  - in the final equation block, we have the Rademacher complexity of F_{W_2}, instead it should be F_{W^prime}