For linear classifiers, the relationship between (normalized) output margin and generalization is captured in a clear and simple bound -a large output margin implies good generalization. Unfortunately, for deep models, this relationship is less clear: existing analyses of the output margin give complicated bounds which sometimes depend exponentially on depth. In this work, we propose to instead analyze a new notion of margin, which we call the "all-layer margin." Our analysis reveals that the all-layer margin has a clear and direct relationship with generalization for deep models. This enables the following concrete applications of the all-layer margin: 1) by analyzing the all-layer margin, we obtain tighter generalization bounds for neural nets which depend on Jacobian and hidden layer norms and remove the exponential dependency on depth 2) our neural net results easily translate to the adversarially robust setting, giving the first direct analysis of robust test error for deep networks, and 3) we present a theoretically inspired training algorithm for increasing the all-layer margin. Our algorithm improves both clean and adversarially robust test performance over strong baselines in practice.
The paper proposes a new generalization bound for deep neural networks and develops a regularizer which optimize quantities related to the bound and improve generalization error on competitive baselines. The paper treats deep neural network as a composition of functions (i.e. the layers) and introduces a new complexity measure, all layer margins, which depends on norm-based perturbation simultaneously applied to all the hidden layers of the neural networks. The all-layer margin can be seen as a generalization of the popular margin definition in SVM’s. Similarly, a generalization bound can be derived based on such all layer margins. The paper also shows that the bound has nice properties that improve upon some short-comings of previous efforts and compare favorably in terms of tightness. The paper also shows that this bound can be adapted to adversarial robustness of the deep model. Finally, a practical algorithm is proposed to optimize the approximation of the all-layer margin and improve upon the baseline models (i.e. trained with only cross-entropy) in a non-trivial manner.
I really like the paper! Jiang et al. 19 showed a surprisingly strong correlation between the margins at the hidden layers and generalization, which begs the question whether a generalization bound can be proven based on these perturbations. This paper shows that it is indeed the case with a much more sophisticated yet intuitive definition of margin that depends all hidden layers at the same time. Other than the nice theoretical properties outlined in the paper, the most exciting property of the all layer margin is that it can be directly optimized which the paper shows at the end. On the technical front, I have carefully read section 2 and Appendix A and read the other proofs at a coarser granularity. Barring some small notational errors, I did not find major errors in the derivation since standard techniques are used after the definition of the all layer margin. For the algorithm, while I have some questions about the thoroughness and accuracy of the approximation the results are quite compelling.
I think this paper should be accepted as I consider generalization to be one of the most important topics in deep learning and the paper is a valuable contribution both for theory and practices. In addition, the paper is relatively easy to follow for a topic so technically involved. 
Barring my endorsement, I have some small complaints and questions:
    1. The notation for summation in the definition of \psi is quite difficult to parse. It would be good to either adopt a more explicit notation or have some extra clarification.
    2. The symbol for function F and the symbol for function class \mathcal{F} are sometimes mixed. For example, in lemma 2.1, the m_F on LHS should be m \circ \mathcal{F}.
    3. I am a little confused on the role of section 3 since, like the paper states, the bound in section 3 is always looser than section 2. Is this bound just for comparison with previous work or provide a tractable upper bound? If so this should be discussed.
    4. In lemma B.1, why are there 2 reference matrices and how should they be chosen?
    5. Condition A.1 assumes the function classes of each layer have some kind of bounded complexity. In a feedforward neural network, a single \mathcal{F}_i is just a linear operator which has pretty small complexity, but how about networks with residual connections? Is this assumption still reasonable? Likewise, since the proposed AMO is applied to residual networks, I want to hear the authors thought on this.
    6. Following the previous point, perhaps it would be nice to have some experiments on conventional feedforward networks and applied the proposed algorithm to all layers instead of skipping the contents of the residual block.
    7. Can the bound be accurately approximated? To me this seems almost combinatorially hard. If so, do the authors expect it to be non-vacuous? Given the results of Jiang et al., it seems that it is plausible to obtain fairly tight bound conditioned on the data and architecture.
    8. Adversarial robustness is a highly active and empirical-results-driven field, so some experiments on the defense against adversarial attack would greatly strengthen the theoretical results. Otherwise it’s hard to gauge how useful it is.