Relaxing Local Robustness
Authors: Klas Leino
Matt Fredrikson
Venue: NeurIPS 2021 Poster (2021)
Keywords: robustness
certification
safety
top-k
relaxations

Abstract: Certifiable local robustness, which rigorously precludes small-norm adversarial examples, has received significant attention as a means of addressing security concerns in deep learning. However, for some classification problems, local robustness is not a natural objective, even in the presence of adversaries; for example, if an image contains two classes of subjects, the correct label for the image may be considered arbitrary between the two, and thus enforcing strict separation between them is unnecessary. In this work, we introduce two relaxed safety properties for classifiers that address this observation: (1) relaxed top-k robustness, which serves as the analogue of top-k accuracy; and (2) affinity robustness, which specifies which sets of labels must be separated by a robustness margin, and which can be $\epsilon$-close in $\ell_p$ space. We show how to construct models that can be efficiently certified against each relaxed robustness property, and trained with very little overhead relative to standard gradient descent. Finally, we demonstrate experimentally that these relaxed variants of robustness are well-suited to several significant classification problems, leading to lower rejection rates and higher certified accuracies than can be obtained when certifying "standard" local robustness.

Relaxing Local Robustness
Klas Leino Carnegie Mellon University kleinoees. cmu. edu
Matt Fredrikson Carnegie Mellon University mfredrik&ce cmu. .dd
Abstract
Certifiable local robustness, which rigorously precludes small-norm adversarial examples, has received significant attention as a means of addressing security concerns in deep learning. However, for some classification problems, local robustness is not a natural objective, even in the presence of adversaries; for example, if an image contains two classes of subjects, the correct label for the image may be considered arbitrary between the two, and thus enforcing strict separation between them unnecessary. In this work, we introduce two relaxed safety properties for classifiers that address this observation: (1) relaxed top-k robustness, which serves as the analogue of top-k accuracy; and (2) affinity robustness, which specifies which sets of labels must be separated by robustness margin, and which can be e-close in Ep space. show how to construct models that can efficiently certified against each relaxed robustness property, and trained with very little overhead relative to standard gradient descent. Finally, we demonstrate experimentally that these relaxed variants of robustness well-suited to several significant classification problems, leading to lower rejection rates and higher certified accuracies than can be obtained when certifying "standard" local robustness
Introduction
The discovery of adversarial examples 9 24 28 has led to security concerns in deep learning. A
growing body of work has sought address this problem by providing provable guarantees that model's predictions are robust to small-norm perturbations B
22 29 31 32 33) This objective is typically captured by ensuring that a model satisfies point wise local robustness; i.., given a point, x, the model's predictions must remain invariant over the c-ball centered at a. Local robustness is accompanied by metric, verified-robus robust accuracy (VRA), which corresponds the fraction of points that are both correctly classified and locally robust.
g 13
16
21
In some contexts, however, it is not always clear that VRA is the most desirable objective or the most nat- ural metric for measuring model's success against adversaries. For example, in some contexts, not all adversarial examples equally bad-this may reflect simply that mistake is understandable, even if it was caused by an ad adversary (e.g., if model mistakenly predicts an image of a leopard to be jaguar); or that the correct label may be arbitrary certain cases (c.g., if an image contains two classes of subjects).
For similar sorts of reasons, some computer vision tasks often use top-k accuracy as benchmark metric that relaxes standard accuracy, allowing prediction to be considered correct so long as the correct label appears among the model's À highest logit outputs. In many applications, top-k accuracy is considered more suitable metric/objective than standard top-1 accuracy [[]; meanwhile, studied robustness properties are typically only defined with respect to a single predicted class. Thus, as part of this work, we introduce an analogous relaxation of local robustness to top-k accuracy, which we call relaxed top-K K (RTK) robustness (Section Definition Moreover, we demonstrate how
oour code is publicly available at
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

neural network can be instrumented in order to naturally incorporate certifiable RTK robustness into its learning objective, making runtime certification of this property essentially free (Section
In addition to applying to only top-1 predictions, standard robustness also focuses specifically on the problem of undirected adversarial examples. More concretely, adversarial examples are obtained broadly via two categories of attacks: (1) evasion (undirected) attacks, and (2) targeted (directed) attacks. Local robustness provides guarantees against the former, while the latter, which requires only a weaker guarantee, has remained largely unexplored by work on certifiable robustness. In this work we introduce affinity robustness (Section Definition 4). which captures resistance to specified sets of directed adversarial attacks. We show that certifiable affinity robustness can also be achieved in a manner similar RTK robustness (Section[3).
In recent work, Leino et al. 22 introduced a concept of c-global- which can be thought of requiring regions of the input space that are labeled different classes to be separated by a margin of e, with any interstitial space labeled as I., signifying rejection. By relaxing the notion of robustness, we essentially allow certain classes be grouped together without any intervening rejected space. hierarchy of classes that is conveyed through the robustness
This gives rise to a spatially-arrange guarantee (see Figure in (octionn3oor an example). Interestingly, we find that models trained with the objective of RTK robustness often form a logical hierarchy even without supervision. Additionally, affinity robustness provides a way to supervise the hierarchy that forms, giving finer control over the spatial relationships between the various labels in the model's 's decision surface.
In summary, the primary contributions in this work
follows:
We introduce RTK robustness, a notion of model robustness compatible with top-k accuracy. and affinity robustness, notion of model robustness that captures resistance to particular sets of directed ad adversarial attacks.
We show how to construct models that can be efficiently certified against these two properties.
We show that applying these relaxed robustness variants to suitable domains leads to certifiable models with lower rejection rates and higher certified accuracy.
We show that these relaxed robustness variants lead to interesting properties regarding how a network's s prediction space is laid out, and that this layout of classes can be supervised to impart a priori hierarchies.
2
Related Work
Robustness certification for deep networks has become a well-studied topic, and numerous certification approaches have been proposed 3 of this work has focused specifically on certifying guarantees against f, attacks a model's top prediction. By contrast, we introduce two relaxed variants of this standard robustness property that have not formerly been studied, which we subsequently show how to certify. Although our proposed definitions are agnostic to both the chosen norm and the method used to certify them, we focus on deterministic robustness certification (as opposed to stochastic certification, e.g., Randomized Smoothing 3 (00 for the fg norm. We build our certification approach from recently proposed method by Leino et al. [22], which has been demonstrated to be among the most scalable lfae-offthhe-ae art methods for deterministic &g certification.
5
g
13
16
21
22
25
29
31
32
33 However, virtually all undirected
Much of this work focuses on generalizing the most commonly threat model characterizing what it means to be "robust", namely, Ep local robustness, which stipulates prediction invariance over perturbations within a small l, ball. Other work has also considered generalizations of this robustness definition, though not typically in the context of certification. E.g.. previous literature has proposed invariance under unions of multiple &p invariance to inconspicuous, physically-realizan
balls 4 30), invariance to rotations and translations [6], and
perturbations 2 7 18 27
The first of the two robustness definitions we propose, RTK robustness, is closely related to top-k accuracy. Recently, Jia et al. [12 also proposed a definition that aims to capture certified robustmess for top-k predictions. However, their work differs from ours in two key ways. First, their certification method is derived from Randomized Smoothing, which gives stochastic guarantee and relies on hundreds of thousands of samples for conclusive certification. More importantly. Dia et al. evaluate their property with respect to the ground truth class of the point in question, making it unclear how

---

rolust
Log-2
robust
top
cobostt
(a)
(b)
a relaxation of standard local robustness, The gray arrows denote bounds on the amount each logit can change within a radius of c. We see that these bounds are not sufficient for class 2 surpass class I; however, the bounds are sufficient for class to surpass class 2. Therefore, the point in this example is top- 1 robust, but nor top-2 robust. (b) Example of network outputs that are simultaneously top-1 robust and top-2 robust.
Figure 1:
Example of network outputs that demonstrate top-k robustness
one might certify this property in such a manner on unlabeled points, e.g., those seen by the model in deployment. We provide more discussion on this problem and how our work addresses it in Appendix (i the supplementary material. As we will see, devising a robustness analogue to top-k accuracy in a manner that relaxes standard robustness and does not depend on the ground truth is subtle task-we we address this issue carefully in Section
Our second proposed robustness definition, affinity robustness, is related to targeted adversarial attacks 28), which have only rarely been studied the context of certifiable defenses [0]]
3 Relaxed Top-K Robustness
In this work, we consider relaxations of the standard notion of local robustness (Definition I that may serve as a better learning objective and evaluation metric in some contexts, e.g., those where not all adversarial examples are equally bad.
Definition (Local Robustness) A model, F. is e-locally- at point, w.E.f. norm, |1-11, if
Vsl
|
1| S
F(x')
We begin in this section by introducing notion of robustness that is inspired by the relaxed accuracy metric, top-k accuracy. Top-k accuracy is a common benchmark metric in vision applications such as Imagenet, where the class labels are particularly fine-grained, and may even be arbitrary on some instances. Furthermore, top-k accuracy has been studied as learning objective in its own right [I] and has been identified as desirable in the context of robustness certification [2]
In order to create notion of relaxed robustness that is analogous to top-k accuracy, we will consider the network to output set of classes rather than single class. Let define the following notation representing the set of the top & outputs of model: let be the function computing the logit values of neural network, and let (xx) be the highhi logit output of f on x. We then define F {j (z) 2 (x)), that is, F is the set of classes corresponding to the top k outputs of f. Using this notation, we define top-k robustness (Definition which requires that the set of classes with the highest logits remains invariant over small-norm perturbations. We note that if we had single class of interest, c, e.g., the ground truth, we could simply require that cremain in p under small perturbations [12] however, top-k accuracy useful precisely because any of the classes in 5* could be correct, meaning that all classes in F* should be treated equally and guarded against perturbations.
Definition (Top-k Robustness) model, F. top-k: e-locally- at point, x, w.E.t norm, ||- if
Yz' ||x-~' || - (=)= (x'(')
While top-k robustness may appear to capture the idea of top-k accuracy, we observe that the analogy fails, as top-k robustness is not relaxation of standard local robustness. For example, if model top-1 accurate, it is also top-2 accurate; however, if model is top-1 robust, may not be top-2 robust. Figure a provides an example illustrating this point.

---

(a)
(b)
(d)
Figure 2: (a) An example 2D synthetic dataset containing four classes. Decision boundary of
standard model trained on the synthetic dataset. (c) Decision boundary of a GloRo Net [22] trained
to be certifiably robust the synthetic dataset. (d) Decision boundary of an RT2 GloRo Net (see
Section(5) trained to be RT2 robust on the synthetic dataset. We observe that the RT2 GloRo Net can label the points accurately the standard model, while the GloRo Net must reject some point the manifold. The RT2 GloRo Net reports a relaxed robustness guarantee (indicated by orange, purple, and cyan) in the regions where the classes overlap. E.g., in the orange region, the RT2 GloRo Net guarantees that no adversary can change the label to blue or green with a small-norm perturbation.
We thus turn our attention to modification of Definition22 2 that does relax standard local robustness. prrvviss notion of what we call relaxed top-K K robustness, or RTK robustness, which is properly analogous to the concept of top-k accuracy. Essentially, point is considered RTK robust it top-k robust for some in (J....K}.
Definition (Relaxed Top-K Robustness) A model, F, is relaxed-top- K (RTK) c-locally-rouust point, I. w.r.f. norm, 11-11.2
Val
3
From the definition, it is clear that RTK robustness a relaxation of standard local robustness: first, RTI robustness is equivalent top-1 robustness, which is equivalent to local robustness; second, RT1 robustness implies RTK robustness for K > 1.
We can think of RTK robustness allowing the model output set of labels (with size most K) such that the output set remains invariant under bounded-now norm perturbations. In some cases there may be multiple such sets, e.g., if the model is both top-1 robust and top-2 robust the point (see Figure [b] for an example). These can be thought of as the sets of classes that are "safe" to predict on given point; if the only such is empty then no classes are safe, and the model abstains from predicting. This gives rise to a spatially-arrang robustness guarantee: each region the decision surface corresponds some (or sets) of classes that can be robustly predicted. Pelgives an example of how such decision surface might look on a synthetic 2D dataset, via a coloring that indicates the smallest safe set that can be predicted.
hierarchy of classes that conveyed through the
4 Affinity Robustness
we demonstrate how to relax local robustness in order to capture a robustness notion analogous to the concept of top-k accuracy. We observed that training for RTK robustness induces a decision surface with a apatially-arranger hierarchy of classes conveyed through the robustness guarantee. While we observed that this hierarchy arises naturally, in some cases we may wish guide the hierarchy that forms. F.g., we may have a priori knowledge of the class hierarchy that we would like to impart our model, or we may have a limited set of class groupings that are acceptable.
In Section 3
In this section, we demonstrate how the class hierarchy induced on the decision surface a model can be guided using pre- specified affinity sets, which define the sets of classes that can be grouped together without intervening rejected space on the decision surface. More formally, let S be collection of affinity sets, where each affinity set S E S is simply set of class labels. We will typically assume that for each class, j. 3S S such that j E S; that is, each class is included in at least one affinity set.
For given collection of affinity sets, we can define affinity robustness (Definition 4), which stipulates that points, J, may be top-k robust for any k. so long as F (xx) contained some affinity set. That is, classes may be "grouped" together in robust prediction set with other classes that share affinity set.

---

Definition 4 (Affinity Robustness) A model, F, is affuitt---occalyy-nbbst on point, I, W.E.f. collection of affinity sets, S, and norm |1-11. if
Vx || x' || SEEN (x)))=F"("") F A (S
Examples of Affinity Sets. Several common datasets offer natural instantiations of affinity sets. For example, CIFAR- 100 contains 100 classes that are grouped into 20 super-classes containing 5 related classes each. Additionally, Imagenet classes derived from tree structure from which many natural collections of affinity sets could be derived. Finally, affinity sets can be used to capture mistakes that may arise even without adversarial manipulation, e.g., by grouping classes that are visually similar; or to group classes that may naturally co-occur in the same instance, c.g., highways and pastures in EuroSAT [ satellite images (see Section
5 Efficiently-Ceriffabbl Construction
In this section we describe how to produce networks that incorporate certifiable RTK or affinity robust- ness into their training objectives. particular we follow a similar approach Leino al. [22], instru- menting the output of a neural network to return an added class, .,, in cases where the desired property cannot be certified. Perhaps surprisingly, our construction demonstrates that our proposed robustness properties can be certified efficiently, with little overhead compared to a forward pass of the network.
5.1 Background: Globally Robust Neural Networks
Recently, Leino al. 22 proposed Globally Robust Neural Networks (GloRo Nets) for training certifiably robust deep networks, an approach that has been found to be the current state-of-the-ar for deterministic l robustness certification. A GloRo Net encodes robustness certification into its architecture such that all points are either rejected (the network predicts an added class, 1), or certifiably e-locally-robust. GloRo Nets make use of the underlying network's global Lipschitz constant. Specifically, let f be a neural network, let j be the class predicted by I on point, x, and let K5; (for ( be the Lipschitz constant of fj .. GloRo Net adds an extra logit value, f=(x) (-)==)ni) =max f.f(()) cKj{}. If the margin between the highest logit output, (1). and the second- -iihndt logit output, fi fz),
smaller than eKji, yt, then fa (x) will be the maximal logit score in the GloRo Net, thus the point will be
rejected; otherwise the GloRo Net will not predict 1 and the point can be certified as e-locally-robus
5.2 RTK and Affinity GloRo Nets
We propose variations of GloRo Nets, RTK GloRo Nets and Affinity GloRo Nets, which naturally satisfy RTK and affinity robustness respectively on all non-rejected points. We first demonstrate how construct RTK GloRo Nets by instrumenting model, such that the instrumented model returns 1 unless / can be certified as RTK e-locally-robust, The construction for Affinity GloRo Nets is similar; is omitted here, but the details are included in Appendix B in the supplementary material.
As defined in Scction 3 let F be the predictions made by f. i.c., F(x) = argmax, (ff (x)),. and let F*)x) be the set of the top i predictions made by on x; and as above, let Kj. be the Lipschitz constant of fi-
For k K and F let fz)))((())) Ff (ar (f(()) +eK,s). Intuitively, (x) is the -
margin by which class j, which in the top l: classes, exceeds every class not in the top k classes, after accounting for the maximum change in logit values within a radius of determined by the Lipschitz constant. We observe that if m² (z: > then the logit for class j. (z), cannot be surpassed within the e-ball around x by an output not in the top outputs. f((x) for i (x))
Next, m k (x: = mmmn=mmiteaape (m/())) This represents the minimum margin by which any class in the top i classes exceeds every class not in the top & classes; thus if m² (z) > 0, then F is top-k robust at æ.
Finally, let mx) maxxs {m (z:) We observe that if m(x)> > O, then the model is RTK robust x. We would thus like to predict only when m(r) <0. To accomplish this we create an instrumented This instrumented model naturally satisfies RTK robustness, as
model, g. as given by Equation]] I
stated by Theorem
(x)x= 1 (x) = max maxx))(x))m))))) -m(x))
5

---

Theorem 1 Let be an RTK GloRo Net as defined by Equation not then F RTK e-locally-roie rroullsy- at z.
7
Then, the maximal output of g(x)
The proof of Theorem | as well as an analogous theorem stating correctness of our Affinity GloRo Net implementation. is given in Appendix in the supplementary material.
Implementation. In order to implement RTK or Affinity GloRo Nets, we must compute the Lipschitz constant of the instrumented network, f. Furthermore, this computation must be differentiable in order to incorporate certification into the learning routine. We approximate an upper bound of the global I Lipschitz constant of f by taking layer-wise product of the spectral norms of each layer's kernel matrix, using the power method. While this efficient, it may also provide loose bound leading the GloRo Net to reject more points than necessary. Nonetheless, we find this to be an effective method of certification, as the bound computation is incorporated into the training procedure, allowing the network to learn parameters for which the bound is reasonably tight [22].
For reproducibility and full transparency of our implementation, we have made our code publicly available on GitHub at https://gi git.gttthuu..... com wwt.cooo//laaa wwwmoooalleeeooeeeeeaeaaaaeeeeee
5.3 Other Certification Techniques
While many certification methods have been proposed and studied in the past, use the GloRo Net approach to certification for two key reasons. First, GloRo Nets have been shown to be among the top state-of-the-art methods for deterministic E2 certification, matching or outperforming the VRA of all other deterministic methods recently surveyed by Leino et al. [22]. Second, GloRo Nets provide an elegant way for incorporating our robustness objectives into a certifiable training procedure, as certified training can be reduced to simply performing overapproximate certification.
However, leveraging other types of techniques for certifying our proposed robustness properties remains an interesting possibility for future work to explore. Appendix D in the supplementary material provides discussion of how other certification techniques may be adapted to incorporate RTK and affinity robustness.
Evaluation
In this section, we motivate our proposed robustness relaxations via an empirical demonstration and argue that our proposed relaxations are likely to be relevant for extending certified defenses to complex prediction tasks with many classes, where standard robustness may be difficult or unrealistic to achieve. To this end, we first find that applying these relaxed robustness variants to suitable domains leads to certifiable models with lower rejection rates and higher certified accuracy (Section[6.1) We then explore the intriguing properties of model's 's prediction space that arise when the model is trained with the objective of RTK or affinity robustness on appropriate domains. In particular, we examine the predictions of RTK and Affinity GloRo Nets trained EuroSAT [I]] (Section[6.2) and CIFAR- 100 (Section(6.3) (.3), and find that (1) the classes that are "grouped" by the model typically follow a logical structure, even without supervision, and (2), affinity robustness can be used to capture small set of specific, challenging class distinctions that account for a relatively large fraction of the points satisfying RTK robustness but not standard robustness.
In addition, we provide further motivation for Affinity GloRo Nets by showing how they can be leveraged to efficiently certify previously-studics safety property for ACAS Xu [14], collision avoidance system for unmanned aircraft that has been primary motivation in many prior works that study certification of neural network safety properties [10
15 16 23). Specifically, we show that Affinity GloRo Nets can certify targeted safe regions [10] in a single forward pass of the network, while previous techniques based on formal methods require hours to certify this property, even smaller networks [10] These experiments are presented in Appendix Ejin the supplementary matcrial.
6.1 Improving Certified Performance through Relaxation
We begin our evaluation by measuring the extent to which certification performance can be improved when the objective relaxed. We focus particularly on the & norm, and deterministic certification and guarantees, opposed to the types of guarantees obtained via Randomized Smoothing (3]. To

---

dataset
guarantee
VRA/RTK VRA VRA/ /afiiiy VRA
rejection rate
clean accuracy
AT
standard (local robustness)
0.141
0,749 = 0.003
0.204 # 0.002
0.862
0.003
EuroSAT
RT3
0.141
0.908 = 0.002
0.073 = 0.002
0.987 + 0.002
Au
highwayeriver affinity
0.141
0.798 + 0.002
0.170 + 0.002
0.917 0.003
EuroSAT
highway-riveragrrculee aftty
0,141
0.819 = 0.003
0,151 = 0.003
0,930 + 0.003
CIFAR-100
standard
0.141
0.281 = 0.002
0.640 # 0.003
0.473 + 0.002
CIFAR-100
RTS
0,141
0.360 = 0.002
0.562 0.002
0.706 0.003
CIFAR-I00 100
superclass aflinity
0,141
0.323 = 0.002
0.599 + 0.002
0.520 + 0.002
Tuy-Imagean
standard
0,141
0.210
0.639
0.346 AM
Tiny Imagenet
RTS
0.277
0.002
0.447 0.006
0.537
0.002
ACAS Xu (App. Largeted affinity
0,010
0.749 = 0.001
0.195 + 0.001
0.858 + 0.002
Table I: Certification results under various notions of robustness. Note that VRA and clean accuracy numbers are given for the VR VRA/accuracy metric corresponding to the robustness guarantee the respec- tive model was trained for, thus their meaning is slightly slightly different for each guarantee (see Sec- tion 6.1 Metrics). Results are taken as the average over 10 runs; standard deviations are denoted by +.
this end, we compare against GloRo Nets [22], which have achieved state-of-the art performance for deterministic certification several common benchmark datasets.
Datasets. Our evaluation focuses on datasets for which our relaxed robustness variants are appropri- ate. Namely, we select datasets with large numbers of fine-grain classes, or classes with a large degree of feature-overlap: EuroSAT [TT] CIFAR-100 [17,, and
[19] The most widely-studied datasets for benchmarking deterministic robustness certification are CIFAR- 10 and MNIST, which do not fit these desiderata; however, Tiny-Imagenet has also been used for evaluating deterministic cer- tification [2 22]. making our results directly comparable to the previously-pbbiikee
state-of-the-art
Models. We trained three types of models in our evaluation: GloRo Nets (as a point of comparison to standard robustmess certification). RTK GloRo Nets, and Affinity GloRo Nets. More details on the affinity sets chosen for the Affinity GloRo Nets are given in Section (for EuroSAT) and Section 6.. (for (0FAR-100). The details of the architecture, training procedure, and hyperparameters are provided in Appendix Fin the supplementary material.
Metries. We measure the performance of RTK models using a metric we call R7K VRA, which is the natural analogous metric to top-k accuracy. For a given point, x, that is certifiably RTK robust, let k- be the the maximum 1: S K such that the model is top-k robust at æ (recall that an RTK robust point can be top-k robust for more than one k-k* corresponds to the loosest such guarantee). We define the RTK VRA of model, F, as the fraction of labeled points, (z. such that (1) the model RTK robust at x, and (2) y E Fkr. In other words, the correct label must be in a certifiably-obba set of top-k predictions for some 8: < K. Similarly, we define affinity VRA, with respect to collection of affinity sets, S, as the fraction of points for which the correct label is in a certifiably-robi set of top-k predictions that is contained in some affinity set in S.
We also provide clean accuracy metrics for each model, corresponding to the guarantee the model is trained for; e.g., top-k accuracy for RTK GloRo Nets. For Affinity GloRo Nets, we use what we call affinity accuracy, which counts a prediction as correct all labels scored above the ground truth share single affinity set with the ground truth.
Performance. Table [ shows the performance of GloRo Nets compared to RTK GloRo Nets and affinity GloRo Nets with respect to the appropriate VRA metric, as well as the rejection rate of each model, i.c., the fraction of points that cannot be certified. RTK GloRo Nets use the most relaxed objective, and accordingly, we see that they consistently outperform the standard GloRo Net, improving VRA performance by 6-16 percentage points. Additionally, RTK GloRo Nets reduce the rejection rate significantly, rejecting as few as half the number of points rejected by the standard GloRo Nets. We also observe that affinity GloRo Nets consistently improve performance compared to standard GloRo Nets. In particular,
affinity (see Section 6.2) and superclass affinity (see Section 6.33 increase VRA performance by 8 points and points respectively, despite the fact that these affinity guarantees are significantly more restrictive than the RTK guarantees.
7

---

fruccion cerijfeeeeeeae points with tops & gaaronte
BuroSAT
CIFAR-100
0.8
0.8
Figure 3: Robust prediction set sizes on EuroSAT (left) and CIFAR- 100 (right). The y-axis measures the fraction of certified test instances that were certifiable top-k robust, for each & on the x-axis. Note that the fractions do not sum to because some points can receive multiple guarantees.
Relaxed Guarantees & Learning Objectives. As demonstrated by the results in Table T RTK and affinity robustness significantly improve certifiability and VRA performance. Clearly, this improvement is in part due the relaxed certification and evaluation criteria entailed by RTK and affinity robustness. However, there is also evidence that the relaxed learning objective itself may better aid in learning robust boundaries in general. For example, CIFAR-100, 5% of points rejected by the GloRo Net are certified by the RTS GloRo Net with top-1 guarantee, suggesting that the RTS objective better facilitated obtaining strong robustness guarantee on these points.
Similarly, we find that the objective of affinity robustness, while technically stronger than RTK robustness, guides the model towards greater certifiability than would be explained by the fraction of instances for which the RTK GloRo Net naturally satisfies the affinity set groupings, highlighting the significance of incorporating affinity robustness into the training objective. For example, 100, 100, 22% of points certified by the RT5 GloRo Net receive a top-k guarantee that does not correspond to superclass. This would correspond to 16% higher rejection under superclass affinity robustness; meanwhile the rejection rate of the superclass Affinity GloRo Net is in fact only 6% higher than that of the RT5 GloRo Net.
CIFAR-
Top-k Prediction Set Sizes. While appropriate relaxations are useful in many contexts, it is generally preferable be able to obtain stricter guarantee -ie., a smaller robust output set. Figure shows the robust prediction set sizes obtained on certified (i.e., non-rejected) test points for both EuroSAT and CIFAR-100. Note that points may receive top-k guarantee for multiple values of k meaning that point may belong to robust sets of more than one size. For example, 56% of certified points EuroSAT and 24% CIFAR- 100 received guarantee for multiple values of k. We see that the majority of points get a tight guarantee, with about 80% of certified points receiving top-1 guarantee, and looser guarantees becoming progressively less common.
6.2 Relaxed Robustness Guarantees on EuroSAT
EuroSAT is relatively recent dataset based on land-use classification of Sentinel-22 satellite images M. Although EuroS AT contains only ten classes, we argue that is nonetheless suitable application for the types of relaxed robustness presented in this paper, primarily because of the lack of mutual exclusivity among classes. Specifically, the classification task proposed for EuroSAT contains the following classes to describe a 64 x 64 image patch: (I) annual crop. (2) forest, (3) herbaceous vegetation, (4) highway, (5) industrial buildings, (6) pasture, (7) permanent crop, (8) residential buildings (9) river, and (10) sea/lake. Each instance has exactly one label, however, in practice the labels are not necessarily non-overi con-overlapping. For example, highway images may depict road going through agricultural land, crossing river, near buildings. It may be reasonable, then, for classifier produce high logit values for two classes simultaneously. making local robustness potentially difficult to achieve.
Indeed, we find this to be the case; namely, many EuroSAT instances labeled "highway" cannot be certified for standard robustness, while large fraction of these rejected inputs can be certified for RT3 robustness. Specifically, we found that a standard GloRo Net trained on EuroSAT rejected 39% of highway instances from the test set (above average for instances overall). Meanwhile, an RT3 GloRo Net was able to certify 72% of these same instances. Upon examination, we found that many of the guarantees associated with the points rejected by the GloRo Net but certified by the RT3 GloRo Net appeal nicely to intuition. Figure 4a few of these intuitive examples; see that on image

---

highway, penmunent crop. anmull stop
highway, residentul buildings
highway, permanent crop, berbaccous vegetation
highway, annual crop
hishway, aummal coog, pasture
highway. residentull buildiing
anaual crop,
pasture, highway
diver
ground trad: highway
residential buildings
(b)
(C)
Figure 4: Samples EuroSAT instances labeled "highway" (a or "river" (b) that are rejected (i.e., cannot be certified) by standard GloRo Net, but certified by an RT3 GloRo Net. The classes included in the RT3 robustness guarantee are given beneath each image. (c) Two visually similar instances with ground truth label "river" (left) and "highway" (right).
patches with highway in field, the RT3 GloRo Net gives top-2 top-3 guarantees with highway alongside classes such as "annual crop." and on image patches with a highway near neighborhood, gives top-2 guarantees with highway grouped with "residential buildings."
Additionally, we find that many instances of rivers receive RTK guarantee including "highway" belonging to the corresponding robust prediction set. As illustrated by Figure [4c] this may not be unreasonable-Fiigreeeee shows visually similar EuroSAT instances with ground truth label "river" and "highway" respectively. demonstrating that the 64 x 64 patches may not always provide enough detail and context to easily distinguish these classes.
We see a similar trend for the "river" class, shown in Figure 4b
of the classes
The above intuition suggests that the difficulty in learning a certifiably-rode robust model on Eu may be largely due to frequent cases where specific sets of classes may not be sufficiently separable. That an adversary might have the ability to control which of set of plausible labels is chosen may be considered inconsequential, provided the adversary cannot cause arbitrary mistakes. This observation motivates the use of affinity robustness on EuroSAT. That is, we may wish to further restrict the sets of classes that may forgo c-separation (those that correspond to "arbitrary" mistakes), while the same time admitting the model to group specified set of classes, between which adversarial examples could be considered benign.
To this end, we suggest two plausible affinity sets for EuroSAT. The first, which we refer to as high- way+river affinity, captures the challenges faced by standard GloRo Nets that are illustrated by Figure namely, S consists of one affinity set, Se per class, c, consisting c, c, the class "highway," and the class affinity additionally allows the
"river:" The second, which refer classes "permanent crop" and "annual crop" to be grouped, as these classes are often visually similar. We find that these affinity sets allow improve the VRA EuroSAT compared to standard GloRo Net by and 7 percentage points, respectively (see Table T.. Moreover, the performance of the high- way-river+agrriultur Affinity GloRo Net closes half of the VRA gap between the standard GloRo Net and the more-relaxed RTK GloRo Net, suggesting that roughly half of the performance benefits obtained under RTK robustness can be recovered by accounting for few simple types of reasonable mistakes.
6.3 Relaxed Robustness Guarantees on CIFAR-100
CIFAR- 100 another natural application for which our relaxed robustness variants are suitable for several reasons, including that (1) it contains a large number of classes, (2) many of the classes are fine-grain, especially considering the small size of the input images, and (3) its 100 classes are further organized into 20 superclasses that each encompass 5 classes.

---

dolphin, whale oak tree, maple tree, willow tree, pine
bee, flatfish, sunflower, butterfly
palan tree, house
poppy, tulip, orchid. rose
boy, girl, baby bus, streetcar motoreycle
bicycle,
trout, woman, girl
Figure 5: Samples of CIFAR- 100 instances that are both correctly classified and certified as top-k robust for k> The classes included in the RT5 robustness guarantee are given beneath each image.
tulip, pepper, poppy
Tulip
shark,
shark,
spider, cuterpillar, butterfly
eaterpillar, busterfly
aquarium fish, tulip, poppy
squariim fish
Figure 6: Comparison robust prediction sets produced by an RTS GloRo Net (left) and a superclass Affinity GloRo Net (right). Samples taken from points which the RT5 GloRo Net did not match a single superclass, while the Affinity GloRo Net was able to successfully certify the point.
We find that when training for RT5 robustness using RT5 GloRo Net, 78% of certifiable points the RTS GloRo Net have corresponding robust prediction sets that are contained by some superclass set, That is, even without supervision, the robust prediction sets of the RTK GloRo net typically respect the superclass hierarchy. Moreover, even on instances for which the robust prediction set does not match superclass set, the robust prediction set is often nonetheless "reasonable," in that it is often clear upon inspection why the model may have chosen the particular set of predictions. Figure providees RT5--crtiffable points with their corresponding robust prediction sets, illustrating this point. More such examples can be found in Appendix Gijn the supplementary material.
samples of correctly-classffe
However, supposing would want to strictly enforce the model's robust prediction sets to be contained entirely in one superclass. Affinity GloRo Nets provide a means of doing this. We find that 34% of instances which the RT5 GloRo Net fails to match superclass can be certified by the superclass Affinity GloRo Net. Figure provides examples of such instances, showing that the additional supervision of Affinity GloRo Nets helps better ensure the robust prediction sets respect superclasses.
7 Conclusion
In this work, we introduce two novel safety properties for classifiers that relax local robustness in order provide more practical objective for certifiable defenses in complex prediction tasks where standard robustness may be difficult or unrealistic to achieve. The first property, RTK robustness, constitutes the first robustness notion extending top-k prediction tasks that can be certified without knowledge of the ground-truth label. The second, affinity robustness, is novel robustness notion tailored to certifiable defenses against targeted ad adversarial examples. We show how construct models that can be efficiently certified against each relaxed robustness property, and demonstrate that these properties well-suited to several significant classification problems, leading lower rejection rates and higher certified accuracies than can be obtained when certifying "standard" local robustness. We suggest that this work will be useful in striving towards performance parity between certifiable and non non-certii classification; and more generally, that broader, domain domain-apprope appropriate safety guarantees should be considered certifying model safety. Finally, we note that although robustness certification is typically helpful in making machine learning safe for high-stakes contexts, techniques drawn from evasion attacks may be used to protect privacy meaning robust models may thwart such avenues for anonymity.
Acknowledgments and Disclosure of Funding
The work described in this paper has been supported by the Software Engineering Institute under its FFRDC Contract No. FA8800215-D--0N with the U.S. Department Defense, and by the National Science Foundation under Grant No. CNS-1943016.
10

---

References
[1] Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Smooth loss functions for deep
top-k classification. In International Conference Learning Representations, 2018.
[2] Tom B. Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch. In NIPS Workshop on Machine Learning and Computer Security, 2017.
[3] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML), 2019.
[4] Francesco Croce and Matthias Hein. Provable robustness against all adversarial lp perturbations for In ICLR, 2020.
[5] Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of ReLU networks via maximization of linear regions. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
[6] Logan Engstrom, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and a translation suffice: Fooling cnns with simple transformations. In NIPS Workshop on Machine Learning and Computer Security, 2017.
[7] Ivan Evtimov, Kevin Eykholt, Earlence Fernandes, Tadayoshi Kohno, Bo Li, Atul Prakash, Amir Rahmati, and Dawn Song. Robust physical-wordd attacks on machine learning models. In Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
[8] Aymeric Fromherz, Klas Leino, Matt Fredrikson, Bryan Parno, and Corina Pásäreanu. Fast geometric projections for local robustness certification. In ICLR, 2021.
[9] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
[10] Divya Gopinath, Guy Katz, Corina S. Päsäreanu. and Clark Barrett. Deepsafe: A data-driven approach for assessing robustness of neural networks. In Automated Technology for Verification and Analysis, 2018
[11] Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Introducing curosat:
A novel dataset and deep learning benchmark for land use and land cover classification. IEEE International Geoscience and Remote Sensing Symposium, 2018
[12] Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In ICLR, 2020.
[13] Matt Jordan, Justin Lewis, and Alexandros G. Dimakis. Provable certificates for adversarial examples: Fitting ball in the union of polytopes. In NIPS, 2019.
[14] Kyle D. Julian, Jessica Lopez, Jeffrey S. Brush, Michael P. Owen, and Mykel J. Kochenderfer. Policy compression for aircraft collision avoidance systems. In IEEE/AIAA Digital Avionics Systems Conference ( (DASC), 2016.
[15] Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer-Aided Verification (CAV), 2017.
[16] Guy Katz, Derek A. Huang, Duligur Ibeling, Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah. Shantanu Thakoor, Haoze Wu, Aleksandar Zeljić, David L. Dill, Mykel Kochenderfer, and Clark Barrett. The marabou framework for verification and analysis of deep neural networks. In Computer Aided Verification. 2019.
[17] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[18] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. CoRR, 0tts/1607.0533. 2016.
[19] Y. Le and X. Yang. Tiny imagenet visual recognition challenge. 2015.
[20] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In Symposium Security and Privacy SSP),,
[21] Sungyoon Lee, Jaewook Lee, and Saerom Park. Lipschitz-cerrtfffbble training with a tight outer bound. In NIPS, 2020.
11

---

[22] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In ICML, 2021.
[23] Diego Manzanas Lopez, Taylor Johnson, Hoang-Dung Tran, Stanley Bak, Xin Chen, and Kerianne L. Hobbs. Verification of neural network compression of acas lookup tables with star set reachability. In AIAA Scitech 202/ Forum.
[24] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. In European Symposium Security and Privacy (EuroS&P), 2016.
[25] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. 2018.
[26] Shawn Shan, Emily Wenger, Jiayun Zhang, Huiying Li, Haitao Zheng, and Ben Y. Zhao. Fawkes: Protecting privacy against unauthorized deep learning models. In USENIX Security Symposium, 2020.
[27] Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K. Reiter. Accessorize to a crime: Real and stealthy attacks state-of-the ofr----rtttt face recognition. ACM SIGSAC Conference Computer and Communications Security (CCS), 2016.
[28] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[29] Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations (ICLR), 2019.
[30] Florian Tramèr and Dan Boneh. Adversarial training and robustness for multiple perturbations. In NIPS, 2019.
[31] Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In NIPS, 2018.
[32] Kai Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In International Conference on Learning Representations (ICLR), 2019.
[33] Huan Zhang, Tsui- Sei Weng. Pin-Yu Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In NIPS, 2018
12


Reviews:
[{"review_id": "tQqn14hSBKh", "reviewer": "Reviewer_N8vP", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe 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.\nSpecifically, 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.\nThe implementation still using approximated upper bound of the global Lipschitz constant which is similar to [22]. \n\nQuality:\n\nThe 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.\nAfter reading the paper I have some concerns about the experimental part:\n\n1) 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.\n2) It looks like the $\\epsilon$-ball is choose as $\\ell_2$ norm perturbation, does the proposed method can be generalized to $\\ell_\\infty$ perturbation?\n3) 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.\n\nSignificance:\n\nTo 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.\n\nDuring 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.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitations and potential negative societal impact were found during my review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "oAXfMq0jXJL", "reviewer": "Reviewer_4qXm", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Originality:\n  * 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). \nThe presented analysis on certification performance with RTK, affinity is also quite interesting.\n\n- Quality:\n  * 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).\n\n- Clarity:\n  * 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. \n  * It is not clear to me why the proposed approaches could improve clean accuracy over the standard guarantee. \n\n- Significance:\n  * 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2.25"}, "extra_text": {}}, {"review_id": "QFhQNYf6gv7", "reviewer": "Reviewer_miwT", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nPro:\n\nTo 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.  \n\nThe proposed algorithm to achieve the proposed top-k robustness seems very reasonable. Empirically the performance is better than the baselines. \n\nQuestions:\n\nMy 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. \n1. 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. \n2. 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\n3. The choice of robustness norm ball size (denoted \\epsilon in the paper) can be discussed.\n\nThere 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.\n\nIt 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. \n\nWriting: \n\nThe writing is generally very clear and easy to follow. There are a few locations where clarity could be improved. \n1. Section 4 needs more motivation. The jump from RTK to affinity robustness is somewhat abrupt.\n2. 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.”\n3. 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "Kj6EN3XLfdb", "reviewer": "Reviewer_TzLt", "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.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Writing\nThe 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). \n\n### Significance\nThis work would be useful to the progress of certifiable robustness to larger datasets, especially those that contain class similarities and hierarchies.\n\n### Problems\n1. 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?\n2. 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). \n\n\n### Questions\n1. 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.\n\n2. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "83FC50baDRN", "reviewer": "Reviewer_veMk", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nI do have some questions and concerns, and would like to hear back from the authors regarding the following.\n1) 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.\n2) 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.\n3) Figure 3 - please add a vertical line separating the images in (b) and the images in (c)\n4) 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?\n5) 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)