Understanding Weight Normalized Deep Neural Networks with Rectified Linear Units
This paper presents a general framework for norm-based capacity control for L p,q weight normalized deep neural networks. We establish the upper bound on the Rademacher complexities of this family. With an L p,q normalization where q ≤ p * and 1/p+1/p * = 1, we discuss properties of a width-independent capacity control, which only depends on the depth by a square root term. We further analyze the approximation properties of L p,q weight normalized deep neural networks. In particular, for an L 1,∞ weight normalized network, the approximation error can be controlled by the L 1 norm of the output layer, and the corresponding generalization error only depends on the architecture by the square root of the depth.
This paper essentially seems to address 2 questions (a) Under certain natural weight constraints what is the Rademacher complexity upperbound for nets when we allow for bias vectors in each layer? and (b) How well can such weight constrained nets approximate Lipschitz functions in the sup norm over compact domains?   There is a section 4.1 in the paper which is about generalization bounds for nets doing regression. but to me that does not seem to be an essential part of the paper.   Let me first say at the outset that the writing of the paper seems extremely bad and many of the crucial steps in the proofs look unfollowable. As it stands this paper is hardly fit to be made public and needs a thorough rewriting!   There are few issues that I have with the section on upperbounding Rademacher complexity as has been done between pages 15 to 19,   1. Isnt the entire point of this analysis is just to show that the Srebro-Tomioka-Neyshabur result (http://proceedings.mlr.press/v40/Neyshabur15.pdf) holds even with biases? If that is the entire point then why is this interesting? I am not sure why we should have expected anything much to change about their de-facto exponential dependances on depth with addition of bias!     A far more interesting analysis that could have been done and which would have led to a far more interesting paper is if one could have lifted the Rakhlin-Golowich-Shamir analysis of Rademacher complexity (which does not have the exp(depth) dependance!) to nets with biases. I strongly feel thats the research that should have been done!   2. The writing of the proofs here are extremely difficult to follow and the only reason one can follow anything here is because one can often look up the corresponding step in Srebro-Tomioka-Neyshabur! There are just way too many steps here which make no sense to me : like what does "sup_{\x_i}" even mean in the lines below line 350? How did that appear and why is Massart's Lemma applicable for a sup over a continuum? It hardly makes any sense! I have no clue how equation 11(d) follows from equation 11(c). This is similar to Lemma 17 of Srebro-Tomioka-Neyshabur but this definitely needs a rederivation in this context. The steps following equation 12(b) also make little sense to me because they seem to indicate that one is taking \sigma of an innerproduct whereas this \sigma is I believe defined over vectors. Its again not clear as to how the composition structure below equation 12(d) got broken.    Now coming to the proof of Theorem 3 - its again fraught with too many problems. Lemma 9 is a very interesting proposition and I wish this proof were clear and convincing. As of now its riddled with too many ambiguous steps!   For example : below line 464 what is being computed are \floor(r_1/2) and \floor(r_2/2) number of linear functions apart from x and -x. Any linear function needs 2 ReLU gates for computation. But this doubling is not visible anywhere! Page 23 to 24, the argument gets even more difficult to follow :  I do not understand the point that is being made at the top of page 23 that there is somehow a difference between stating what the 2 hidden neurons are and what they compute. The induction is only more hairy and there is hardly any clear proof anywhere about why this composed function should be seen as computing the required function!   Maybe the argument of Theorem 3 is correct and it does seem plausible but as it stands I am unable to decide the correctness given how unintelligible the presentation is!    ============================================================== Response to "author response" :   I thank the authors for their detailed response. I do think its a very interesting piece of work and after the many discussions with the co-reviewers now I am more convinced of the correctness of the proofs. Though still there are major sections in the paper like the argument about Lemma 9/Theorem 3 which are still too cryptic for me to judge correctness with full certainty. This paper definitely needs a thorough rewriting with better notation and presentation.