Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper presents a bound on the generalization error of a deep network in terms of margin at each layer of the network.  The starting premise is that extending the existing margin generalization bounds to deep networks worsen exponentially with the depth of the
network. Recent work which removed that exponential dependency is
claimed to require a more involved proof and complicated dependence on
input.  The paper provides a new bound that is simpler
and tighter.

A second contribution is to extend their bounds to robust classifier.
Since their bounds depend on instance-specific margins, the extension
to the robust case is straightforward. They just need to relax the
margin to the robustness boundary of the input. 

Finally, they present a new algorithm motivated by their bounds, that
maximized margin on all layers.  They show that the resultant network has much lower error than standard training.

The paper is well-presented and in spite of being theoretical is very nicely developed so that the main contributions come out clearly to non-specialists too.  

A few minor comments:
The inner min in Equation 2.2 seems to be a typo.

In Theorem 2.1, there is typo around the definition of \xi.
Below thoerem 2.1, the phrase "depend on the q-th moment" has 'q' undefined.

Typo "is has a" in Theorem 3.1

review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: The paper presents a novel and interesting way to measure the margin in the context of deep networks that removes the exponential dependency of depth in the corresponding generalization bounds. The key idea is to stabilize not only with respect to the input perturbations (which most existing works do and end up obtaining an exponential dependency), but simultaneous perturbations at every layer. It also shown that these ideas readily can be extended to provide bounds in the adversarial classification case. Finally, preliminary positive results on benchmarks showing how such an all-layer margin can be maximized during training are presented.

Major comments:
1. I really like the fresh idea of simultaneous perturbations based analysis. Though it is clear that the proposed all-layer margin is upper bounded by margins with single perturbation, it is indeed non-trivial and insightful to understand that the same alleviates the exponential dependency of depth. More specifically, I think claim 2.1 is the the most insightful result, though simple to prove in hindsight. It would greatly help the readers if simple figures are used to explain this insightful result in the final manuscript. 

2. I think overall the paper was a pleasure to read especially with the way simplified analysis is presented in the main paper while postponing details to the Appendix.  It will be great if theorem 3.1 can further be simplified in notation and details just to present the main result that linear dependency is achieved via the lower bound for all-layer margin and to show improvement over existing bounds.

Minor comments:
1. Though results in sec5 are encouraging it would have been nice if it is shown that narrow and deep architectures benefit from such a regularization. As per the authors of WRN, the optimal architectures are not very deep.

2. Though linear dependency is a useful step, it does not still reflect the observation in practice that in many applications deep networks generalize better than the shallow ones. Any comments towards this might help.

3. There seem to be some typos: second min in (2.2) etc.
review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: 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.

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proves generalization bounds for Neural networks in terms of all layer margins. All layer margins are the smallest relative perturbations  of outputs of each layer, that result in misclassification. This new quantity allows to show generalization bounds that scales as sum of complexities of each layer and inversely scales with the all layer margin. The resulting bound does not have an explicit exponential dependence on depth, unlike some earlier bounds in terms of output margin.

The paper makes strong claims in the abstract and introduction that the analysis removes exponential dependency of capacity on depth. However I don’t think this is possible in the worst case. The exponential dependency is now hidden in the all layer margin (please correct me if I am mistaken). Note that the bound could still be interesting if this quantity is small for real world networks of interest. However the paper currently lacks this discussion. The paper need to make it clear that the bound only avoids explicit exponential dependence on depth. This brings me to another major drawback of the all layer margin. 

This quantity is not computable as it requires solving a min-max problem, to find the best perturbation for each data point. So we cannot easily test if real networks that generalize well do have smaller all layer margin. The paper provides a lower bound for this quantity in terms of layer norms, network Jacobian norms, and output margin - which can be large. While all layer margin is certainly interesting from analysis perspective, as it allows to show bounds that are relatively cleaner, and behaves well with composition functions, it is not clear to me that it doesn’t decrease exponentially for deeper networks. A discussion on this can help the paper. 

This paper is along the recent line of work on data dependent generalization bounds by Nagarajan  & Kolter 2019, Wei & Ma 2019.  Note that these earlier papers also prove generalization bounds that also do not have explicit exponential dependence on depth. This point also needs to be made clearer. 

Given the adversarial nature of the definition of the all layer margin, the same framework is used to show a robust generalization bound, which is nice. However, the bound again depends on a hard to compute quantity - \kapp^{adv}, making it less clear about the utility of such a bound.

Finally the paper presents experiments, where to encourage higher all layer margin, the paper relies on min max gradient updates, similar to adversarial training, and shows better performance with this. I am curious if authors experiments with dropout, as it also adds “perturbations” to the output activations of each layer, and if the gains are orthogonal to dropout. Also how does the performance of AMO compared with  adversarial training methods (PGD) with small \epsilon? The experiments currently are lacking to compare AMO with existing techniques.

Overall I believe the paper needs to be rewritten with correctly stated contributions and need a more nuanced discussion of the benefits and drawbacks of the all layer margin and the  corresponding generalization bounds. 

** Post response comments **
Authors have clarified some of my earlier concerns. But the paper still requires rewriting to properly emphasize that it does not avoid exponential dependence on depth, but rather avoids an explicit dependence. Also there needs to be discussion about the computability of  \kapp^{adv}. Finally adding experiments with dropout should make it more clear about the advantages of the proposed training method. Because the current draft does not address these yet, I am leaving my score at 3. My actual rating is more on the borderline (5), but the current system does not allow such scores. 

review_title: Official Blind Review #1

Meta-review: This works presents a new and interesting notion of margin for deep neural networks (that incorporates representation at all layers). It then develops generalization bounds based on the introduced margin. The reviewers pointed some concerns, including some notation issues, complexity in case of residual networks, removal of exponential dependence on depth,  and dependence on a hard to compute quantity - \kapp^{adv}. Some of these concerns were addressed by the authors. At the end, most of the reviewers find the notion of all-layer margin introduced in this paper a very novel and promising idea for characterizing generalization in deep networks. Agreeing with reviewers, I recommend accept. However, I request the authors to accommodate remaining comments /concerns raised by R1 in the final version of your paper. In particular, in your response to R1 you mentioned for one case you saw improvement even with dropout, but that is not mentioned in the revision; Please include related details in the draft.

Decision: Accept (Poster)