PREDICTING THE GENERALIZATION GAP IN DEEP NETWORKS WITH MARGIN DISTRIBUTIONS
Recent research has demonstrated that deep neural networks can perfectly fit randomly labeled data, but with very poor accuracy on held out data. This phenomenon indicates that loss functions such as cross-entropy are not a reliable indicator of generalization. This leads to the crucial question of how generalization gap can be predicted from training data and network parameters. In this paper, we propose such a measure, and conduct extensive empirical studies on how well it can predict the generalization gap. Our measure is based on the concept of margin distribution, which are the distances of training points to the decision boundary. We find that it is necessary to use margin distributions at multiple layers of a deep network. On the CIFAR-10 and the CIFAR-100 datasets, our proposed measure correlates very strongly with the generalization gap. In addition, we find the following other factors to be of importance: normalizing margin values for scale independence, using characterizations of margin distribution rather than just the margin (closest distance to decision boundary), and working in log space instead of linear space (effectively using a product of margins rather than a sum). Our measure can be easily applied to feedforward deep networks with any architecture and may point towards new training loss functions that could enable better generalization.
After author response, I have increased my score. I'm still not 100% sure about the interpretation the authors provided for the negative distances. 
The paper is well written and is mostly clear. (1st line on page 4 has a typo, \bar{x}_k in eq (4) should be \bar{x}^l?)
Novelty: I am not sure whether the paper adds any significant on top of what we know from Bartlett et al., Elsayed et al. since:
(i). The fact that "normalized" margins are strongly correlated with the test set accuracy was shown in Bartlett et al. (figure 1.). A major part of the definition comes from there or from the reference they cite; 
(ii). Taylor approximation to compute the margin distribution is in Elsayed et al.; 
(iii). I think the four points listed in page 2 (which make the distinction between related work) is misleading: the way I see it is that the authors use the margin distribution in Elsayed et al which simply overcomes some of the obstacles that norm based margins may face. The only novelty here seems to be that the authors use the margin distribution at each layer. 
Technical pitfalls: Computing the d_{f,x,i,j} using Equation (3) is missing an absolute value in the numerator as in equation (7) Elsayed et al.. The authors interpret the negative values as misclassification: why is it true? The margin distribution used in Bartlett et al. (below Figure 4 on page 5 in arxiv:1706.08498) uses labeled data and it is obvious in this case to interpreting negative values as misclassification. I don't see how this is true for eq (3) here in this paper. Secondly, why are negative points ignored?? Misclassified points in my opinion are equally important, ignoring the information that a point is misclassified doesn't sound like a great idea. How do the experiments look if we don't ignore them?
Experiments: Good set of experiments. However I find the results to be mildly taking the claims of the authors made in four points listed in page 2 away: Section 4.1, "Empirically, we found constructing this only on four evenly-spaced layers, input, and 3 hidden layers, leads to good predictors.". How can the authors explain this? 
By using linear models, authors implicitly assume that the relationship between generalization gaps and signatures are linear (in Eucledian or log spaces). However, from the experiments (table 1), we see that log models always have better results than linear models. Even assuming linear relationship, I think it is informative to also provide other metrics such as MSE, AIC, BIC etc..