Spectrally-normalized margin bounds for neural networks
This paper presents a margin-based multiclass generalization bound for neural networks that scales with their margin-normalized spectral complexity: their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor. This bound is empirically investigated for a standard AlexNet network trained with SGD on the mnist and cifar10 datasets, with both original and random labels; the bound, the Lipschitz constants, and the excess risks are all in direct correlation, suggesting both that SGD selects predictors whose complexity scales with the difficulty of the learning task, and secondly that the presented bound is sensitive to this complexity.
This paper proposes analysing the margin distributions of deep neural network to analyse their generalization properties. In particular they propose a normalized margin estimator, which is shown to reflect generalization properties of certain neural networks much better than the naive margin computation.
Your notion of margin is different than what I'm used to. (I usually hear margin defined as the minimum distance in input space to a point of a different class, as SVMs are commonly depicted). Maybe just take a few words to stress this?
Why does the x axis on some (if not all?) your figures not start at 0? Shouldn't the margin always be positive? Unless you're not taking y to be the argmax of F(x) but instead the true class, in which case it would be negative for a missclassification. Maybe mention this.
What is the data distribution in your plots? Train, validation, or test? I general your plots should have clearer axes or captions.
In Theorem 1.1 it's not clear to me what B and W are (without the appendix), maybe just briefly mention what they are.
CIFAR and MNIST are acronyms, and should be capitalized. Ditto for SGD.
There are some typos throughout, and I feel like the writing is slightly "casual" and could be improved.
Your section on adversarial examples is somewhat puzzling to me. The margins, let's say M1, that you describe initially are in Y-space, they're the distance between the prediction f(x)_y and the next bess guess max_i!=y f(x)_i. This is different than the input space margin, let's say M2, which is something like `min_u ||u-x|| s.t. f(u) \neq f(x)`. As such when you say "The margin is nothing more than the distance an input must traverse before its label is flipped", you're clearly referring to M2, while it would seem your contribution revolves around M1 concept of margin.
While intuitively M1 and M2 are probably related, unless I'm missing something about your work relating them, claiming "low margin points are more susceptible to adversarial noise than high margin points" is a much stronger statement than you may realise.
Overall I quite like this paper, both in terms of the questions it is trying to answer, and in the way in does. 
On the other hand, the presentation could be better, and I'm still not convinced that the margin in output space has too much value in the way we currently train neural networks. We know for example that the output probabilities of neural networks are not predictive of confidence (even to an extent for Bayesian neural networks). I think more work relating the input margin with the output margin might be more revealing.
I've given myself a 2/5 confidence because I am not super familiar with the math used here, so I may be failing to get deeper implications. Hopefully I'll have time to go through this soon.