Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes two properties for certified robustness (local) -- relaxed top-k robustness, and affinity robustness. The importance of such properties is discussed in light of how many datasets contain some class hierarchy (such as superclasses), or inputs that may belong to multiple classes. The introduction of such relaxations is proposed to serve as a means for being analogs to the top-k robustness or directed attack robustness, which are often discussed in empirical settings. The paper also demonstrates how these objectives can be put to practice by making modifications to the training objective of GloRo Nets. These relaxed robust networks are also shown to demonstrate properties of class hierarchy.


main_review: ### Writing
The paper is well written and easy to follow. The extensive case-studies of datasets are helpful in motivating the method to the reader. However, I believe that this comes at the expense of *significant* technical detail. In a revised version, I would expect to see a much larger amount of details regarding how the method can be re-implemented (Section 5.2). 

### Significance
This work would be useful to the progress of certifiable robustness to larger datasets, especially those that contain class similarities and hierarchies.

### Problems
1. Considering that CIFAR100 superclass (20 classes) is a significantly relaxed version of the CIFAR100 problem, I would have expected the certified accuracies to be closer to CIFAR10. However, the reported numbers appear much lower? This makes it difficult to quantify the utility of the relaxation. Can you provide a comparison for CIFAR10 and CIFAR100 (say 10 super classes of CIFAR100) on the same norm and same radius? Is the lack of certified accuracy because of resorting to GloRo nets?
2. Can this also be adapted to non-l2 norms? Moreover, I could not find anywhere in the paper where the authors clearly specified the norm type (apart from using the symbol, which is often used to denote any lp norm in literature). 


### Questions
1. The paper highlights how "the classes that are “grouped” by the model typically follow a logical structure, even without supervision". What is your observation of this logical structure in (a) standard training; and (b) standard locally robust training. It is fair to say that this is a phenomenon that occurs *exclusively* because of RTK training? I would expect otherwise.

2. Do you think there may exist adaptations of other certification techniques (apart from GloRo nets) that can incorporate these objectives in future work? This would include both deterministic and stochastic certification paradigms.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes two relaxations of local robustness: relaxed top-k robustness, and affinity robustness, which are more natural notions of robustness in certain settings. One asks for one of the top-k labels to be correct in a certain radius, and the other allows for certain similar classes to be perturbed to each other. This paper leverages prior work to train models that can be efficiently certified for each of the robustness properties, and shows new experimental results on common and relatively new datasets.
main_review: Overall, this paper is borderline for me. I would rate it as a weak accept, and I would appreciate it if the authors could address some of my questions and concerns.

The paper is relatively original; although there are other works that try to establish similar notions of top-k robustness or hierarchical robustness (e.g., https://arxiv.org/abs/2102.09012, which the authors don’t cite, and https://arxiv.org/abs/1912.09899, which the authors do cite), the authors do so in a relatively new setting. The definitions that the authors propose are quite natural for certain problems, so I believe that the significance of the work is good, and the authors perform experiments on both very common datasets like CIFAR-100 and Tiny-ImageNet, as well as an interesting and relatively newer dataset called EuroSAT where their notions of robustness seem to work well. Overall, the paper is fairly clear.

I do have some questions and concerns, and would like to hear back from the authors regarding the following.
1) My main concern is that the certification method that the authors use is somewhat non-standard; they use GloRo Nets and a method that involves computing the Lipschitz constant between logits. While this leads to efficient certification and clean proofs, it is not clear how close to state of the art this method is, as the authors acknowledge such a method can lead to loose bounds in L198. Thus, I think it is important for the authors to add in a baseline and a comparison to more standard and state-of-the-art certification methods like using convex relaxations (https://arxiv.org/abs/1711.00851), or to explain why GloRo Nets are a better choice here. Next, a quick question; in L196 - is the approximation always an upper bound on the global Lipschitz constant, or is it sometimes less? It’s not clear to me from the writing if it’s always an upper bound but the bound is not tight, or if it’s an approximation of the value of an upper bound.
2) Table 1 - what does the “clean accuracy” column mean for the “CIFAR-100 standard” and “CIFAR-100 RT5” rows? Does each row correspond to a model trained in a different way, but evaluated in the same way when measuring “clean accuracy”? If so, how is the “clean accuracy” so low for “CIFAR-100 standard”? I would expect that standard training should have the highest (or at least very close to the highest) clean accuracy.
3) Figure 3 - please add a vertical line separating the images in (b) and the images in (c)
4) L134-136: The paper discusses something that has not been presented clearly yet (the hierarchical nature of the resulting RTK-trained model, which the authors discuss more in section 6.3). Perhaps the authors could include a reference to the part of the text that presents this result more clearly?
5) Section 6.3 - what does the hierarchy have to do with the RT5 training? Does the same hierarchy occur even for a model trained with a standard loss?

limitations_and_societal_impact: Yes. I appreciate that this paper was one of the few papers I have seen that addresses ethics, even if it is just a few sentences.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes top-k robustness, where the top-k predictions should not change if the input is perturbed by a small amount. The authors propose an algorithm that extends GloRo to achieve certifiable (relaxed) top-k robustness. 

main_review: 
Pro:

To my knowledge, the problem definition is novel and interesting. The authors propose that the top-k predictions should be robust to perturbations of the input. I really like the idea that for different samples, the model has certified robustness for different values of k, which seems to be a very useful flexibility when there is some label ambiguity.  

The proposed algorithm to achieve the proposed top-k robustness seems very reasonable. Empirically the performance is better than the baselines. 

Questions:

My main concern is the lack of discussion on the several problem parameters that are critical for understanding the performance of the algorithm. I believe these should be extensively discussed in the main paper. 
1. There is very little mention of the maximum label set size K in the paper, which seems to be a critical hyper-parameter that affects performance. For example, if K is very large (e.g. close to the total number of classes) then the performance number is less meaningful than a small K. 
2. The actual set size output by the model is also an important performance metric, which should be highlighted. A small prediction set is certainly preferable to a large prediction set
3. The choice of robustness norm ball size (denoted \epsilon in the paper) can be discussed.

There seems to be some ambiguity with the number of labels k to select. Traditionally the number of labels k is selected based on the predicted probability (e.g. select the smallest k such that the top-k labels account for 99% of the predicted probability). This paper proposes a different criteria for selecting k (some k where the top-k prediction set is robust to perturbations). This begs the question of which k to select in practice.

It would be interesting to see the connection to Lipschitness of the output logits. Suppose each logit vector f_i(x) is Lipschitz with respect to the input (e.g. this can be achieved by randomized smoothing), then would it be possible to naturally derive an RTK prediction function? (For example, just check that the top-k logit scores are far enough from the remaining logit scores). I would imagine that this will be a very competitive alternative. 

Writing: 

The writing is generally very clear and easy to follow. There are a few locations where clarity could be improved. 
1. Section 4 needs more motivation. The jump from RTK to affinity robustness is somewhat abrupt.
2. The problem definition can be further clarified. Does the prediction model output an integer k along with a set of labels? In other words, should the prediction model know which set size k it is robust to. This is not clear from Definition 3 as the statement says “\exists k” rather than “there is an algorithm to find k.”
3. Following up on 2, Definition 3 should be written with more rigor. For example, is it \forall x \forall x’ \exists k, or \forall x’, \exists k, \forall x? These two have completely different interpretations. I do not think the current statement interpreted rigorously reflects the intuition the authors want to convey. 
limitations_and_societal_impact: See above
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduced two relaxed safety properties for classifiers: (1) relaxed top-k robustness, which is different from traditional top-1 classifier; and (2) affinity robustness, which specifies which sets of labels must be separated by a robustness margin, and which can be close a perturbation set. The experimental results on EuroSAT, CIFAR-100, Tiny-Imagenet and ACAS Xu demonstrated the effectiveness of the proposed method.
main_review: Originality:

The proposed method basically based on the idea from global-robustness [22] but extended the method to a more general way, top-k accuracy or top set of labels robustness. The technique contribution is sound and straightforward, the idea also can be applied in some real-world use cases.
Specifically, the global-robustness is well defined in [22], the new problems proposed in this paper combining the idea from [12] but define a more general Top-k Robustness and Relaxed Top-K Robustness. It's an analog of changing the added class $\perp$ to the k-th class.
The implementation still using approximated upper bound of the global Lipschitz constant which is similar to [22]. 

Quality:

The paper is well-organized and easy to follow. Both theoretical analysis and experimental results are provided, especially the results on the EuroSAT dataset demonstrate the value of the Top-k Robustness.
After reading the paper I have some concerns about the experimental part:

1) The running time of the proposed method is not clear. Consider the paper claimed the efficiency in line 159,  the time complexity and robustness of the proposed method compared with existing top-1 global-robustness should be mentioned.
2) It looks like the $\epsilon$-ball is choose as $\ell_2$ norm perturbation, does the proposed method can be generalized to $\ell_\infty$ perturbation?
3) It's hard to evaluate the experimental results since all baselines are varieties of the GloRo Nets with fixed $\epsilon$. Also compare with some linear relaxation-based perturbation analysis methods like KW and IBP, they can also improve the top K robustness by constructing a specification matrix to improve the margin between a set of labels.

Significance:

To the best of my knowledge, the problem of certification in top-k robustness is novel and has real-world significance. But consider the method proposed in this work is based on existing work, global-robustness, with minor changes, so I doubt the novelty contribution on methodology.

During the rebuttal, I would like to raise my rating score if the authors can address my questions on 1) the implementation differences from [22] and 2) the running time of the proposed method comparing with nature training and global-robustness training.




limitations_and_societal_impact: No limitations and potential negative societal impact were found during my review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper describes a relaxation of local robustness to top-k robustness and affinity robustness. In addition, the authors connect the relaxation properties with the globally robust neural networks for certification. In the experimental results, the authors found lower rejection rates and higher certified accuracy in a few domains. 

main_review: - Originality:
  * This work introduces new concepts of top-k robustness, relaxed top-k robustness, and affinity robustness, which seems novel for robustness in some domains (e.g. medical prediction). 
The presented analysis on certification performance with RTK, affinity is also quite interesting.

- Quality:
  * In a way the main contribution of the work is the introduction of the relaxed robustness metrics, and extension to the GloRo Nets. Given such a new framework, there are less previous work for comparison. I wonder about the tightness and constraints of the proposed certification models, which is not discussed too much in the paper. I also wonder whether the proposed approach can be extended to other types of verifications (such as randomized smoothing, bound propagation).

- Clarity:
  * I found that the clarity of sections 5.1 and 5.2 can be improved. It is a bit dense and harder to read compared to other sections. 
  * It is not clear to me why the proposed approaches could improve clean accuracy over the standard guarantee. 

- Significance:
  * This work could be an interesting starting point for considering beyond conventional local robustness setup. The authors have shown interesting analysis and improved certificated accuracy / lower rejection rate compared to standard setup. 
limitations_and_societal_impact: It would be nice to explicitly talk about the limitation of the approach. For example, I wonder whether top-k robustness is too restricted (same top-k predictions) and whether other alternatives could be better. I am also concerned with the scalability of the certified models. Currently all the evaluated datasets and models are still quite small. Besides GloRo Nets, could the proposed properties be applied to other types of certified networks or certified training?
review_title: null

Meta-review: The authors propose relaxations of robustness which deal with the fact that tasks can have varying label ambiguity. All reviewers agreed on the quality of the work and its relevance to security/safety critical settings. In particular, this definition will likely help scale certification approaches to larger datasets where label ambiguity is more common. In addition to editing the paper to include new discussion presented in their responses, I encourage the authors to make their code public to facilitate reproducibility. In particular, it will be important to clarify in the writing that the focus in this paper is on deterministic certification of L2 robustness so that the choice of GloRo Nets is better motivated. The authors are also encouraged to outline clearly how follow-up on the work may study other certification techniques as suggested by the discussion with reviewer TzLt.
Decision: Accept (Poster)