Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the worst-case perturbations in the weight-space for multi-layer networks. The authors first derive a robust surrogate loss which is an upper bound on the loss under norm-bounded weight perturbations based on a product of the 1-inf matrix norm of layer weight matrices. Then the authors derive a generalization bound based on the Rademacher complexity which motivates their new loss function which is evaluated empirically on MNIST.
main_review: **Overall assessment**:
- Originality: the derived bounds (both for the worst-case loss and for generalization) are to the best of my knowledge novel in the context of weight perturbations, although they seem to be directly inspired by similar bounds in the context of input perturbations. 
- Quality: the submission seems to be technically sound but the empirical evaluation can be significantly improved (see **Cons**).
- Clarity: the paper is clearly written and well-organized.
- Significance: on the one hand, theoretically characterizing generalization is an important contribution but on the other hand I have concerns about the tightness of the proposed bound and usefulness of the proposed loss function (see **Cons**).

**Pros**:
- Formal analysis of generalization and the behaviour of the worst-case loss with respect to weight-space perturbations is a valuable contribution.
- Novel theory-driven loss function that aims at improving generalization and robustness against weight perturbations, although I have some concerns about its effectiveness. 



**Cons**:
- My main concern is the tightness of the derived bounds on the worst-case loss. Analogous layerwise bounds are simple and known for a long time in the context of **input-space** perturbations (as opposed to the **weight-space** perturbations studied in this paper), e.g. see
[Certified Defenses against Adversarial Examples](https://arxiv.org/abs/1801.09344), Section 5 which can be trivially extended to multiple layers and to norms on weight matrices W^i other than the spectral one (e.g., including the 1-inf norm that this paper uses a lot). Although the loss function from Sec. 3.5 is not exactly the same as the objective that [Certified Defenses against Adversarial Examples](https://arxiv.org/abs/1801.09344) use as a baseline, they seem to be very connected since the proposed loss relies mainly on the 1-inf norm of the weights. Thus, it would be very useful if the authors could (1) discuss this connection and (2) empirically/theoretically justify the tightness of the proposed bound. The concern (2) comes from the fact that this layerwise bound is usually loose for the input-space perturbations, and thus has been used in the literature just as a baseline (and more involved approaches have been developed, e.g. the SDP relaxation of [Certified Defenses against Adversarial Examples](https://arxiv.org/abs/1801.09344)). There is an analysis of the tightness of the generalization bound in Appendix E but the tightness of the bounds on the worst-case loss doesn’t seem to be sufficiently discussed.
- The empirical evaluation part requires some natural baselines such as, e.g., standard L1/L2 weight regularization. It seems that both additional terms from the theory-driven loss (from Sec. 3.5) are based primarily on the 1-inf norm of the weights, so a natural question is how different it is from the standard weight regularization methods. I don’t think that the current experimental part really justifies the proposed method. Related to this, I don’t think that Fig. 3 in the appendix is informative enough since it shows just the generalization gap but what is more interesting is the absolute value of test accuracy.
- Another aspect of the empirical evaluation which is not very strong is that the evaluation is done only on one small-scale dataset (MNIST). As the authors note in the “Run-time analysis” paragraph, the method should be quite scalable, so it’s not clear to me why its applicability hasn’t been shown on more challenging datasets and models. I think this is an important point since the weight perturbations approaches from [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://arxiv.org/abs/2010.01412) and [Adversarial weight perturbation helps robust generalization](https://arxiv.org/pdf/2004.05884.pdf) are very scalable (lead to only 2x overhead during training) and easily applicable to arbitrary deep networks.
- A discussion on some of the relevant prior works is missing, namely to [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://arxiv.org/abs/2010.01412) (published at ICLR 2021) which is not cited and to [Adversarial weight perturbation helps robust generalization](https://arxiv.org/pdf/2004.05884.pdf) (published at NeurIPS 2020) which is cited but not discussed in detail. It is important to discuss them as the authors claim in the abstract: *“the first formal analysis”* and later in the text that: *“We note that previous methods use random weight perturbations to evaluate the generalization ability (e.g. sharpness), which we call a standard generalization setting. In contrast, we study a different problem setup: generalization of models trained under worst-case (adversarial) weight perturbation”*
Thus, I’d recommend the authors to discuss these references in detail and contrast their generalization bounds to the ones derived in this paper, potentially also including a numerical comparison between both. 


**Other points**:
- Line 20: *“weight quantification”* -> *“weight quantization”*
- Line 22-23: *“weight perturbation sensitivity is also used as a metric to **evaluate** the generalization gap”* -- I think it’s worth being more precise here. What is shown in those papers is merely a **correlation**, and its exact relation to the generalization gap is not completely clear. So sharpness can’t be used to **evaluate** generalization gap.
- Line 285-287: “**will** suffer from a notable generalization gap” -> “**can** suffer from a notable generalization gap” -- as the derived upper bound is only an upper bound and on the exact quantity of interest.
- Line 308: citation is missing.
- Citation style: consider using \citet instead of \cite when citation is used as a part of a sentence (e.g., “[1] showed ...”)
- I think Theorem 3 can be put to the appendix as it doesn’t seem to give any new insights compared to Theorem 2.
- It’s worth numbering equations.

limitations_and_societal_impact: I think the authors could have discussed better the tightness of their bound on the worst-case loss. The authors don’t discuss any negative societal impact of their work but I think it’s not necessary for this paper.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the effect of weight perturbations in a neural network on its performance in terms of generalization and adversarial robustness. Robustness to weight perturbations is important for improving a model’s fault tolerance and reducing its storage requirements without significantly compromising its performance. It uses Rademacher complexity to quantify the impact on generalization and pairwise class margins for adversarial robustness. It considers networks with non-negative monotone activation functions that are 1-Lipschitz. Using the theory developed in the paper, the authors propose a new loss function for training more generalizable and robust models.
main_review: Originality: To the best of my knowledge, this work is the first study in understanding the effects of weight perturbations on a neural network’s ability to generalize on unseen data and its adversarial robustness. It combines well-known mathematical techniques to quantify and characterize a model’s robustness and generalization capability.

Quality: The theoretical results appear to be technically sound though not particularly surprising. The experiments study how the generalization gap and robust accuracy vary with the parameters of the proposed loss terms. However, it is not clear how they affect the test accuracy. Fig 1(a) shows that the gap between train and test accuracies decreases as mu increases for different values of epsilon used during training. Does this drop in the gap result in any gain in test accuracy? Is there a setting of the parameters that helps achieve a better test accuracy than when the proposed loss function is not used? I believe showing an improvement in the test accuracy will better demonstrate the gain in generalization from the proposed loss function.

Clarity: The paper is well written.

Significance: The authors demonstrate through experiments that the proposed loss function helps improve robustness and generalization which are important qualities for any good machine learning model. However, it is difficult to determine the significance of this work without knowing the effect of the loss function parameters on test accuracy. One can always construct models that have high robustness and low generalization gap but have poor accuracy. I believe a study of how these parameters affect the accuracy of the model would help increase the impact of this paper.
limitations_and_societal_impact: This paper seeks to improve the robustness and generalizability of neural network models. The only limitation that comes to my mind of this type of work is its negative impact on the accuracy of the model. The authors have studied the trade-off between robustness and accuracy. However, as I mentioned in the main review a study of the test accuracy of the trained model with respect to the loss parameters is important to properly understand the gain in generalization capabilities.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors developed a formal analysis of the robustness associated with the pairwise class margin for neural networks against weight perturbations. The authors also characterized its generalization gap through Rademacher complexity and proposed a theory-driven loss function for robust generalization. The empirical results showed significantly improved performance in generalization and robustness.  
main_review: 1. The authors aim to study a new problem in neural networks’ robustness to weight perturbations. While the concept is kind of similar to adversarial examples, I would love to see some explanation on why the weight perturbation adopts the Linf norm constraint by default.   
2. One of the major issues in the paper is that it lacks necessary comments and intuitions for each theoretical result. For example, what does theorem 1 implies? Or how does this result help us? It is not clearly written. Readers need to go over the entire paper to understand the author's purpose to derive such an upper bound.
3. Theorem 3, what is the Error of Weight Perturbation term defined? Should make it clear in the main paper
4. Until Section 3.5, I start to understand that the authors are trying to propose a new surrogate loss for weight robust training. However, the question is: is this surrogate loss necessary? In the experiments, the authors only compare their own method in different parameter settings. However, a simple baseline to consider here is simple weight adversarial training (just like PGD attack to weight PGD attack, it is easy to build adversarial training to weight adversarial training). In this way, it does not require any surrogate loss derived in this paper. In other words, it makes much more sense in the case that weight adversarial training is performing poorly and the authors turn to study other surrogate losses for this problem. Yet if weight adversarial training is already doing ok, I don’t see the reason for proposing such a surrogate loss.  


Minor comments:

1 .   Line 308, typo (??)

limitations_and_societal_impact: see above
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this work the authors study the propagating effect of perturbing the weights of a neural network on the models final output. They use the resulting theorems to construct a bound on the Rademacher complexity of the model class under perturbed weights and provide regularizations terms to improve both the robustness against these weight perturbations and to reduce the generalization gap. 
main_review: Dear authors and AC, 

Below you will find my review for the paper in question. 

As very clearly laid out in the introduction, the study of a neural networks sensitivity to perturbations of its weights is an research area of practical importance. The first theoretical characterization provided in this present work is therefore of considerable importance and might have significant impact on future work. I must however admit that I am not entirely up to date with research regarding weight quantization and compression. For this reason I would like to leave judging the works novelty to the other reviewers. 

My main concerns however lie with the numerical validation performed and the unanswered questions regarding the practical usefulness of the bounds and regularization terms that arise from this section. 
- First and foremost, the experimental setup suggest that the additional of the surrogate loss might bring some serious computational restrictions. As far as I understand the experiments have been performed with only 1000 MNIST data samples for training. In the manuscript there is no explanation offered for this decision besides simply following related work. I would appreciate it if the authors could comment on this and/or provide some additional data showcasing the computational cost of training the model using the surrogate loss. The discussion offered in appendix section D.7 is in my opinion not clear enough. (eg. equation 2 referred to in this section seems to only take first layer perturbations into account)
- Second, in the experimental setup the authors mention that no bias terms were used. It would be good to clarify why these were excluded. And, if this is because of them not fitting in the framework, this limitation should be more clearly communicated.
- Third, I have my reservations regarding the effectiveness of the evaluation metric used. Specifically, I do not understand the use of the AUC metric. Even the best performing model in figure 1b quickly degrades to roughly 40% accuracy. At this level of accuracy the usability of the models is mostly completely gone. The further slow degradation after is therefore not really informative any more. In similar fashion, the supplementary experiment on weight quantization shows that the decrease in accuracy of a robust model is 3x less then a standard model for 2 bit quantization. However, this still degrades the model accuracy far enough to question its use. For 16-4 bit quantization the standard and robust model perform roughly the same. 
- Lastly, I believe that a comparison against standard L1 and L2 weight regularization is somewhat necessary. I suspect that keeping the norm of the weights small should suffice to see a lot of the same benefits as the proposed regularization terms. 

Despite the shortcomings of the numerical evaluation section mentioned above, I still believe that the theoretical study presented in the paper can be a valuable starting point for further studies. For this reason I am still inclined to vote for acceptance. If the concerns with the numerical evaluation above could be expanded upon by the authors I would be willing to improve my score. 

Some other minor remarks:
- I appreciate the use of colour to clarify the mathematical notation, but I don't think it is used very effectively in some cases. For example, I do not see the use of colouring the equation in sec. 3.5.
- There are numerous references to equation 2. These are broken and very  confusing. 
- Line 308 has a dead reference.
limitations_and_societal_impact: As I stated in my main review, the numerical evaluation (and more specifically the experimental setup) leave me to question a few practical implications of the theory presented. The authors should clarify these in their reply.
review_title: null

Meta-review: Even though the paper received mixed scores, all the reviewers agreed on the originality and the significance of the contributions of the paper. The authors’ extensive rebuttal letters later on clarified several concerns/confusions, especially in terms of lack of empirical evaluation. While the paper is borderline, I believe that most raised issues can be properly addressed **provided the authors implement all the required changes, which they addressed in their rebuttal**. Hence I am recommending a weak accept.
Decision: Accept (Poster)