Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes using a budget generator to generate non-uniform radii for certification. The budget generator is trained jointly with the certified defense to change the shape of the perturbation set while maintaining the volume to improve certified error. 

On motivation: the paper could use some more justification or motivation for why we would want to change our perturbation radius during training to maximize certified performance. Typically this the other way around: we have a set we want to defend against, and so the certified defense optimizes for this specified set since we're trying to defend against a particular attack. The setup here is strange in this regard, because rather than adapting a defense to a threat model, the threat model is being adapted to the defense, where the defense is defined by a fixed volume but is otherwise whatever the defender trains it to be. Since an attacker would not conveniently restrict themselves to  the radius learned during training, this doesn't really make much sense from the point of view of certifying robustness to adversarial examples (since it doesn't defend against *all* perturbation sets with the specified volume, it only defends against one which isn't specified a priori). 

On comparisons: The authors compare their certified defense with non-uniform budgets to certified defenses with uniform budgets. In its current form, this is completely incomparable: the uniform budgets are trained and certified with uniform radius, while the learned budgets are trained and certified with learned budgets. Since the learned budgets are almost certainly different from the uniform budgets, these are completely different threat models. It would be much more informative to the reader to report results on *both* types of budgets for *both* models instead, rather than only showing half of the story. Specifically, this means 
(a) evaluating all the models trained with learned budgets using the uniform budgets that are more typical in the literature and reflect what they were actually trained for (e.g. <= 0.4 for MNIST, <= 8/255 for CIFAR10)
(b) evaluating the models trained with uniform budgets using the learned budgets  to compare against the models trained with learned budgets
It's quite possible that the learned budgets, while capable of certifying more volume due to the changed threat model, comes at the cost of worse certified performance for a uniform bound of a *smaller* volume (e.g. at uniform radius 0.1 or 0.3 for MNIST, as is commonly reported in the literature). This would also help provide a more realistic and fair comparison to certified defenses with uniform budgets: the current tables report certified accuracy at an extremely large radii well beyond what they were trained for, and so this winds up being a rather a misleading comparison that is not very useful. 

On related work and comparisons thereof: The authors seem to be unaware of the ICML 2019 publication "On Certifying Non-Uniform Bounds against Adversarial Attacks" by Liu et al., which has studied the problem of certifying non-uniform bounds which maximize the volume (exactly the same type of bound studied in this work). There is still a difference, in that they optimize the budget to maximize the volume rather than use a generator to produce perturbation budgets, and do not train. Nonetheless, this is arguably the most relevant work and has been out for quite a while, and so it would be fair to expect some sort of comparison here. For example, a reasonable experiment could be to simply calculate the non-uniform bounds from Liu et al. on the model trained with a non-uniform budget vs the uniform budget. 

Minor comment: The authors mention that the joint training of the classifier and the perturbation budget generator is somehow more difficult for PGD adverarial training "as it is not fully differentiable w.r.t. perturbation budgets". I don't quite get what the authors are trying to say here. My understanding is that the authors perform joint training by backpropagating the robust loss through both the classifier and the perturbation budget generator, since there is no auxiliary loss for the perturbation budget generator. Shouldn't this imply that the standard loss is in fact differentiable with respect to the perturbation budgets, and so PGD is just as applicable as before? 

Update: 
I thank the authors for their response. I've read the other reviews as well, and indeed R2 had similar concerns to my own. I'm glad to see the more comprehensive comparison to Liu et al., which paints a fuller picture of the effects and trade-offs of the approach. 

The argument behind the motivation, however, feels much like setting up a straw man for Lp robustness. For example, the authors argue that their approach is label and semantics preserving unlike uniform perturbations; however this is quite frankly only the case for extremely large perturbations in MNIST-like settings which are unrealistic by design (most papers do not consider such large radii for exactly this reason). Uniform perturbations seen commonly in CIFAR10/Imagenet settings are practically invisible and consequently are equally semantics preserving and close to human perception. If the authors do wish to pursue this argument that these are truly more semantics preserving, then this needs to be backed by evidence. The authors weakly suggest this is the case because the budgets look similar to the content in the images. However, this does not imply that an adversarial attack within this budget is label preserving (i.e. many of the presented examples have large budgets in the background directly adjacent to the label-content of the image, which can easily change how the content looks), and so this needs to be justified carefully if this claim is to be made. 

The authors also incorrectly equate the restrictions imposed on an attacker from learned perturbation radii to that of a uniform radius. These are *not* equivalent, especially in the security setting where these are night and day; the first amounts to the defender choosing the rules of the game that work optimally for them, whereas the latter is a *defense agnostic* rule that both the defender and attacker must obey. This is a significantly easier setting for the defender that needs to be properly motivated, as restricting an adversary to a fixed perturbation set is inherently different from restricting the adversary to a fixed perturbation set that the defender gets to choose. The reason why one would want to maximize certification volume needs to be properly motivated, as it is no longer applicable to the usual adversarial security setting and comes at a cost to the usual robustness considerations. 

To recognize the addition of the necessary comparison to past work, I have improved my score slightly. However, I would still argue that this is below the threshold, as their central claim of learning *semantic preserving* perturbation budgets is not justified despite being a central component of the paper, as well as the motivation for why it's considered beneficial to choose the most easily certified volumes for robustness in the first place (and certainly not helpful from a security perspective). 
review_title: Uses a deep network to learn non-uniform radii for certified defenses, comparisons are not great

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper address the problem of training robust neural networks with non-uniform perturbation budgets on different input pixels. In practice, a perturbation budget generator is introduced to generate the context-aware perturbation budget (i.e. conditioned on the input) for each pixel of the input image. A “robustness volume” constraint on generated perturbation budgets to control the robustness intensity is also proposed. Extensive experiments on MNIST and CIFAR10 demonstrate the proposed outperform SOTA method under various uniform perturbation budgets.


From my perspective, the writing of this paper is good, and contributions are well presented and demonstrated by extensive experiments. So I vote for accepting

Comments:

- How to determine the hyper-parameters \bar{alpha} and \underline{alpha} for each benchmark is still unknown. Are the final results sensitive to these hyper-parameters? Does it take a high cost to adjust these hyper-parameters for different benchmarks?
- How about the performance by using IBP?

- In Eqn.2, The index i indicates the i-th pixel. But in Eqn.3, it denotes the i-th category label. Please modify this to avoid misunderstanding.

- Since I'm not very well versed with the current baseline and state-of-art for variable robust training of DNN, it would be good to compare with other SOTA methods.
review_title: Contributions are well presented and demonstrated

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes to change the perturbation budget for adversarial attacks to a non-uniform setting where differet input pixels have different perturbation budgets. To achieve this, an additional network is trained to learn the perturbation budget for each part of the input. The approach seems to perform better than a uniform perturbation budget and also learns semantically meaningful budgets for the input.

I am not an expert on this topic and will, therefore, keep my review quite short.

The idea that not all parts of the input should be treated equally makes sense and is well motivated.

Questions/remarks:
- What is the exact architecture of the network that learns the perturbation budged? Is it purely convolutional? Will it easily scale to larger inputs?
- It would be interesting to see the performance of your model on more complicated datasets, e.g. Tiny-ImageNet
- How much overhead (training time, model size, etc) does the training of the additional network for the perturbation budget introduce?
- For the visualization of learned pertubation budget: it would be interesting to also run some analysis/visualization of what parts of the input have the strongest effect on the final prediction to see if this correlated with your learned perturbation budged (i.e. if the parts of the input that have the strongest effect on the final classification also have the smallest perturbation budget)
review_title: Review for "Learning Contextual Perturbation Budgets for Training Robust Neural Networks"

final_score: rating: 5: Marginally below acceptance threshold
review_content: Update after the rebuttal:

I read response from the authors and other reviews. I have increased my score to 5 given that authors now performed some
comparison with Liu et al. However, I still believe that the threat model is not realistic and that attacker can not be bounded by the 
budget that is produced by generator network here. While authors wrote quite detailed response, I did not find it convincing enough. As R5 points out similar issues, I would encourage authors to think more on how to tackle the problem better. Perhaps the threat model can limit the attacker to all possible perturbations under the certain volume budget, but that would be quite different from the idea in this paper.  Thus, I can not recommend acceptance at the current state.

============================================================================

-> Summary:

Authors propose to train provably robust models with respect to the threat model
that assumes non-uniform perturbation budget for the attacker. Under this threat model,
attacker is allowed to perturb some pixels more than the others, unlike for the standard
l_p threat model here each pixel has a maximum perturbation value. In this work, authors
propose perturbation generator which produces bounds for each pixel and certified defense
to train provably robust model with respect to the generated perturbation bounds. They show
that trained models have lower natural and verified error than models trained with uniform
bounds of equivalent volume.

-> Reasons for score:

I vote for rejecting this paper. The biggest issue I have is that authors do not compare (and do not cite) 
with the work of Liu et al. [1] whose contributions I believe substantially overlap with contributions of
this submission. The other concern I have is that the idea of learning a perturbation budget which
the attacker should obey seems somewhat unrealistic.

-> Pros:

- I like the general idea of a threat model where maximum perturbations is different for each pixel.
- Paper is well written, easy to follow and manages to bring across the main points.
- The authors perform experiments on several datasets and present visualizations which help to understand
what the method has actually produced.

-> Cons:

- The biggest issue I have with this paper is omission of a prior work of Liu et al. [1] which 
was the first paper to consider non-uniform perturbation bounds. Liu et al. consider same
volume constraint as in Equation (4) in this submission and propose a Lagrangian method to maximize
log of the volume. I think it is essential that authors compare their perturbation generator in section 3.2
with the Lagrangian method from Liu et al. and check which of the two methods can generate larger volume. 
One contribution that this submission has and Liu et al. does not is that of certified defense as Liu et al.
focus only on certification of already trained networks (I am not sure if their method can be trivially extended 
for training). However, given that authors simply use auto_lirpa library for certified defense, contributions there
are also limited.
- I am not sure that idea of generating perturbation budget is feasible in practice. What happens here
is that we generate the threat model under which attacker operates by ourselves and then we somehow expect 
that attacker should obey this threat model. For example, let's say that proposed procedure results in 
eps(x) = [0.3, 0.1, 0.1]. Why would attacker have to obey the fact that third pixel is perturbed by at most 0.1?
Essentially, the method here learns eps(x) such that attacker can't find adversarial example, but I don't understand
in what scenario would attacker be limited by the *particular* eps(x) that this method has produced?
I think it would be more sensible to have a defense which guarantees that model is robust under all threat models
which have volume below some constant V_0, but on the other hand this would be strictly more difficult than the 
uniform baseline.
- Another thing I think is missing is some baseline for computing perturbation budget introduced in 3.3.
This relates to work of Liu et al. who proposed Lagrangian method to do this. Given that algorithm in 3.3 
is perhaps the biggest contribution of this work, I would have expected there to be at least some baseline to compare with.

[1] Liu, Chen, Ryota Tomioka, and Volkan Cevher. "On certifying non-uniform bound against adversarial attacks." ICML 2019.


-> Questions:

- Can authors comment on the work of Liu et al. [1] and what they think are main contributions of their work
which are not already present in Liu et al.? Ideally, authors should also compare to their method (at least
certification part as they have no training).
- Can you explain what would be realistic scenario where attacker has to obey perturbation budget generated by this method?

-> Minor comments:

- typo: "generailized"
- In "Refining the perturbation budgets", third line, should it be [g_\theta(x)]_i under the summand?

review_title: Review for "Learning Contextual Perturbation Budgets for Training Robust Neural Networks"

Meta-review: Reviewers raised various concerns about the motivation, unclear justification of the idea and claim, insufficient comparison with related work, and weak experimental results. While authors had made efforts to improve some of these issues in the rebuttal, the revision was not satisfied for publication quality. Overall, the paper has some interesting idea, but is not ready for publication.  
Decision: Reject