Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The paper discusses learning neural network models under weight parameter perturbations. In particular the paper motivates the use of a new loss function (equation 9) based on the analysis of neural network robustness (Section 3.2, 3.3) and generalization properties (Section 3.4) to perturbations of the weight parameters. Section 4 has experiments supporting the theory that the loss function in equation 9 is robust and has good generalization properties to weight perturbations.

Review: I think the loss function in equation 9 is well motivated and clearly explained. Also the experimental results can be reproduced as the code has been included as part of the submission. Overall the paper is well-written.

But I do have a few concerns regarding the comparison and interpretation of the results with prior work on generalization properties of neural networks. Firstly, the work does not cite some relevant papers to the topic a couple of which I list below:

a.	V. Nagarajan and J.Z. Kolter. Uniform convergence may be unable to explain generalization in deep learning. In NeurIPS 2019.
b.	N. Golowich, A. Rakhlin, and 0. Shamir. Size-independent sample complexity of neural networks. In COLT 2018.

I believe the discussion in Section 2 of Nagarajan and Kolter, 2019 is very relevant to the results in the paper. Nagarajan and Kolter, 2019 show that the norm bounds of the weight matrices increases with the number of samples and hence conclude that the generalization bound results in Bartlett et. al., 2017 are vacuous. The current paper uses the results in Bartlett et. al., 2017 to derive generalization error bounds and additionally has another term dependent on the norms of the weight matrices due to perturbation. Given the discussion in Section 2 of Nagarajan and Kolter, 2018 I am concerned if the bounds obtained in Section 3.2-3.5 are vacuous. I will like to see a discussion and experimental results in light of the observations in Nagarajan and Kolter, 2019.

In the experimental section, I am interested in also knowing the results for the case $\epsilon = 0$ in Figure 1(a). Also, if possible can the authors include a discussion or guidance on the sensitivity of the results to the hyper parameters $\mu$ and $\lambda$? For example the performance seems to get worse when moving from $\lambda = 0.01, 0.125$ to $\lambda = 0.015$ in Figure 1(b). 

review_title: A good paper but needs work comparing to prior literature and more experiments to support theory results

final_score: rating: 7: Good paper, accept
review_content: The paper investigates the effects of weight perturbations on the output margin for multiclass classifcation problems. The paper shows that robustness to weight perturbations can be bounded using the (1,\infty)-norm of the weight matrices. The paper then suggests that a low (1,\infty)-norm of the weight matrices leads to better generalization. Moreover, the robustness against weight perturbation implied by low (1,\infty)-norms of weight matrices should increase the robustness against adversarial perturbations. To support these claims, the paper presents a generalization bound using the (1,\infty)-norm of weight matrices as well as an empirical evaluation using a novel surrogate loss function that, when used in training, is empirically shown to reduce the generalization gap and increase the robustness against adversarial perturbations.

The paper is very well written and the theoretical analysis is sound. My only concern is that the generalization bound derived in theorem 4 might not be very informative or conclusive. The reason is that the Rademacher complexity becomes uninformative in the interpolation regime (i.e., neural network architectures that are complex enough to fit any practical training set perfectly). Since the generalization bound presented here relies on an upper bound on the Rademacher complexity using the already not too tight upper bound of Bartlett, 2017, it could be vacuous. In earlier works on input robustness [1], obtaining meaningful bounds required some covering of the input space with examples rather than a uniform bound over the model space. Since uniform bounds, such as uniform convergence, might not be meaningful at all in the interpolation regime [2] (and thus for most of deep learning), this could imply that the results in Thm. 4 in this paper are not conclusive. In [3], the robustness to weight perturbation was also used as a building block for a potentially non-vacuous generalization bound, so it might be worthwhile to discuss the relation to that paper.

Another line of work that might be worthwhile to discuss is weight noise injection during the training process, which leads to better generalization (e.g., [4]). That is, I would imagine the surrogate loss function is a more effective tool to improve generalization and robustness than random noise injection.  
 
Lastly, it should be discussed how practically applicable the surrogate loss function is. For that, at least a runtime analysis should be provided. 
 
In summary, the paper presents interesting theoretical findings and a potentially practically useful surrogate loss function. The paper is lacking some discussion, but overall I would argue that the paper makes a valid contribution. Thus, I tend to vote for acceptance. 

[1] Xu and Mannor. Robustness and generalization. Machine Learning, 2012.
[2] Nagarajan, et al. Uniform convergence may be unable to explain generalization in deep learning. NeurIPS, 2019.
[3] Petzka, et al. Relative Flatness and Generalization in the Interpolation Regime. arxiv preprint, 2020.
[4] An. The effects of adding noise during backpropagation training on generalization performance. Neural computation, 1996.


‐------------ After Discussion ---------
I am still of the opinion that the manuscript is not without flaws: the theoretical result is quite messy, the empirical evaluation is still limited, and the generalization bound could still be vacuous.

However, the authors provided new experiments that indicate that the bound might not be vacuous in the considered setting, though. The authors also provide a preliminary runtime analysis that suggests the costs for using the surrogate loss do not explode (please include a proper runtime analysis in any future version of this paper). Since the authors furthermore did address my main points in my review during the discussion, I have increased my score to 7.


review_title: Robustness Against Weight Perturbations in Neural Networks

final_score: rating: 7: Good paper, accept
review_content: 

In this work, the authors theoretically analyze the robustness against weight perturbations in neural networks. Upper bounds of the pairwise class margin for single-layer, all-layer, and selected-layer perturbation are established. Based on the analysis, the authors propose novel robust surrogate loss functions for 0-1 loss and cross-entropy.  Furthermore,  the authors analyze the Rademacher complexity of the perturbated network with the proposed loss, which leads to generalization bounds based on (Mohri et al. (2018)) and (Bartlett et al. (2017)). 

Pros
1.  I think the theoretical analysis part is clear and systematic. Efforts of each term in the bounds are well explained. 

2. The analysis is useful for a better understanding of the robustness of networks against weight perturbation. 

3. The proposed loss is also interesting.  The explicit upper bound reduces the computation of the maximization step in adversary training of weight perturbations.


Cons
1. The product form in the bounds may grow fast and become loose.  I am not sure about the tightness since quite a few relaxations that rely on triangle inequality and maximum are used during the derivation.  It is better to report the value of each term in the bound in Theorem 2 or 3  for a better understanding of the bound.  The authors can employ the same experiment's setup in Figure 1.  

2. Similarly,  I concern about the worst-case error term in the proposed loss in Lemma 2.  If the value of this term is large, the margin term minus the worst-case error will always be negative. Thus, the loss will remain a constant one, which is very harmful to training and optimization. 

3. In the experiments, only a simple MNIST dataset is evaluated.  I concern about the performance of the proposed loss in more practical cases. As stated above,  I think the proposed loss may be challenging for optimization.  This phenomenon may become more significant in difficult datasets.

4. In Theorem 1, the definition of z^{N-1} is not given.  It is better to state it clearly to be self-contained.  In Theorem 2, the definition of W* is not given. The definition should be included in the main paper instead of in the appendix.




review_title: Interesting theoretical analysis of robustness against weight perturbations

final_score: rating: 3: Clear rejection
review_content: The draft proposes to bound the model generalization by controlling the adversarial perturbation of the model weights. If the weights in the neural network are bounded and the activation function is Lipschitz, the change of output of the network, as well as the Rademacher complexity of the hypothesis class, can be easily controlled. 

Connecting perturbation with the generalization is not something new no matter in theory or in practice. This is another draft formulating the network perturbation and generalization so that a norm product bound is derived. There are plenty of previous works on this already, e.g., the work by Neyshabur et. al. (perturb the parameters), and Bartlett et. al. (norm product bound). 

The generalization bound proposed in this work is a trivial application of Bartlett’s norm product bound. Perturbing the weights and directly applying norm product leads to a bound not as tight, to some extent, it is mostly vacuous. 

Frankly, the method gives a pessimistic norm product bound and ignores all the effects caused by the “alignment” between the internal coefficient matrix and the input vectors, which is crucial in terms of understanding how input signals are handled throughout the network. I would encourage the authors to read some recent work by Barron et.al. which reduces the generalization bound from norm product to product norm. 

review_title: a trivial application of the existing norm product bound

Meta-review: The authors study empirically and theoretically the behavior of neural networks under $l_\infty$-perturbations on the weight matrix.
For this purpose they first derive bounds on the logit-layer of the neural networks under perturbuations of a single or all layers. Then they propose to merge this bound (which depends on the product of the weight matrices) into a margin-based loss function/cross-entropy-loss and suggest to optimize this bound while simultaneously penalizing the 1,infty-norm of the weight matrices (which appears in the bound). Furthermore they derive a generalization bound for the robust error under weight perturbations.

There was a discussion among the reviewers over this paper. While several ones appreciated the setting, there was concern about that the bound is potentially vacuous and that the theoretical results are "messy". One reviewer criticized heavily the bound as not very useful and overly pessimistic.

This paper is in my point of view borderline but I argue for rejection. There are several reasons for this
- the motivation for this paper remains unclear. While the authors argue that a network could be attacked by changing logical values, this seems at the moment unrealistic as if the attacker has already hacked into the system much more harm can be caused in a much easier way e.g. by directly changing the output of the network. But even if one considers adversarial bit error attacks to be realistic, then the threat model would be completely different from $l_\infty$ and would rather be like $l_0$ (with potential unbounded changes if the network is not quantized). If the target is to study that more flat minima generalize better, then the target would not be a bound on the robust error but a bound on the normal test error which integrates an upper bound which measures "flatness" of the function. As the derived Theorem 4 contains a term where one has to take the supremum over the product of matrices over all functions in the derived function class, this is not true for the derived bound.
Thus I don't see why this bound is related to either of these two motivating topics.

- the bound is incomplete in the sense that it contains the sup_f of the product of 1,infty norms of the weight matrices. Why
did the authors not try to upper bound this term over the chosen function class? Even better would clearly to derive a bound on the Rademacher complexity in terms of the norms which are actually appearing in the bound. In the current way the terms in the bound and the chosen function class are mis-aligned.

- From a practical perspective the resulting loss is not useful for training deeper models (in the experiments a four layer network is used) as the product of the norm of the weight matrices grows exponentially in depth. Moreover, as pointed out the IBP bounds of Weng et al (2020) are much tighter than the bounds derived in this paper (and even IBP bounds are loose) 

- The experiments suggests that one gets a minor improvement in robustness while having to suffer from a significant drop in test accuracy (Figure 1b). Regarding the achieved robustness for epsilon=0.01 (it remains completely unclear how this noise model relates to the normal size of the model weights) one gets a robust error of around 30% on MNIST. This is much worse than what has been achieved for MNIST with much larger input perturbations (epsilon=0.3)

- The authors are missing an assumption on the activation function. With just non-negativity, monotonicity and 1-Lipschitz
the upper bound in A.2.1 (original version) cannot be derived. I guess you are implicitly assuming that rho(0)=0 but this assumption is not stated. There are other typos in the main text. In fact in the original version Theorem 4 did not contain the term
depending on b_h and s_j - this term was added in the revised version but not highlighted as all other changes.

In total there are too many open issues here. While I appreciate the hard work the authors put into the author rebuttal, I think that this paper needs a major revision before it can be published.


Decision: Reject