Localized Randomized Smoothing for Collective Robustness Certification
Authors: Jan Schuchardt
Tom Wollschläger
Aleksandar Bojchevski
Stephan Günnemann
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial robustness
Robustness certification
Robust machine learning
Randomized smoothing
Verification

Abstract: Models for image segmentation, node classification and many other tasks map a single input to multiple labels. By perturbing this single shared input (e.g. the image) an adversary can manipulate several predictions (e.g. misclassify several pixels). A recent collective robustness certificate provides strong guarantees on the number of predictions that are simultaneously robust. This method is however limited to strictily models, where each prediction is associated with a small receptive field. We propose a more general collective certificate for the larger class of softly local models, where each output is dependent on the entire input but assigns different levels of importance to different input regions (e.g. based on their proximity in the image). The certificate is based on our novel localized randomized smoothing approach, where the random perturbation strength for different input regions is proportional to their importance for the outputs. The resulting locally smoothed model yields strong collective guarantees while maintaining high prediction quality on both image segmentation and node classification tasks.

Under review as a conference paper at ICLR 2022
LOCALIZED RANDOMIZED SMOOTHING FOR COLLECTIVE ROBUSTNESS CERTIFICATION
Anonymous authors Paper under double-blind review
ABSTRACT
Models for image segmentation, node classification and many other tasks map single input to multiple labels. By perturbing this single shared input (e.g. the image) adversary can manipulate several predictions (e.g. misclassify several pixels). A recent collective robustness certificate provides strong guarantees on the number of predictions that are simultancously robust. This method is however limited to strictly local models, where each prediction is associated with a small receptive field. We propose more general collective certificate for the larger class of softly local models, where each output is dependent on the entire input but as- signs different levels of importance to different input regions (c.g. based on their proximity in the image). The certificate is based on novel localized random- ized smoothing approach, where the random perturbation strength for different input regions is proportional to their importance for the outputs. The resulting lo- cally smoothed model yields strong collective guarantees while maintaining high prediction quality on both image segmentation and node classification tasks.
INTRODUCTION
There is a wide range of tasks that require models making multiple predictions based on a single in- put. For example, semantic segmentation requires assigning a label each pixel in an image. When deploying such multi-outpun classifiers in practice, their robustness should be key concern. After all 111-jun just like simple classifiers (Szegedy et al. 2014) they can fall victim to adversarial attacks (Xie et al. 2017; Zügnnr & Günnemann 2019 Belinkov & Bisk 2018). Even without an adversary, random noise or measuring errors could cause one or multiple predictions to unexpectedly change.
In the following, we derive a method that provides provable guarantees on how many predictions can be changed by an adversary. Since all outputs operate on the same input, they also have to be attacked simultaneously by choosing single perturbed input. While attacks on single prediction may be easy, attacks on different predictions may be mutually exclusive. We have to explicitly account for this fact to obtain proper collective robustness certificate that provides tight bounds.
There already exists a dedicated collective robustness certificate for multi-output classifiers (Schuchardt et al. 202T), but it only benefical for models we call strictly local, where each output depends only on a small, well-defined subset of the input. One example are graph neural networks that classify each node in a graph based only on its neighborhood. Multi-output classifiers used in practice, however, are often only softly local. While - unlike strictly local models all of their pre- the entire input, each output may assign different importance
dictions are in principle dependent to different components. For example, deep convolutional networks used for image segmentation can have very small effective receptive fields (Luo et al. 2016; Liu al., 2018b). i.e. primarily use small region of the input in labeling each pixel. Many models used in node classification are based on the homophily assumption that connected nodes are mostly of the same class. Thus, they primarily use features from neighboring nodes to classify each node. Even if an architecture is not inherently softly local, a model may learn a softly local mapping through training. For example, a transformer Vasswani et al. (017) can in principle attend to any part of an input sequence. However, in practice the learned attention maps may be "sparse", with the prediction for each token being determined primarily by few (not necessarily nearby) tokens (Shi al. 202T).
While an adversarial attack on a single prediction of a softly local model conceptually no different from that single-output classifier, attacking multiple predictions simultaneously can be much

---

Under review as a conference paper at ICLR 2022
Grid cell (i.f)
Rasterized image
Segmestattin mask
Localtzed smoothing
Figure 1: Localized randomized smoothing applied to semantic segmentation. We assume that the most relevant information for labeling pixel contained in other nearby pixels. We partition the input image into multiple grid cells. For each grid cell, we sample noisy images from a localized smoothing distribution that applies more noise to far-away, less relevant grid cells. Segmenting all noisy images using base model g. cropping the result and computing the majority vote (i.e. the most common label for each pixel) yields a local segmentation mask. These per-cell segmentation masks can then be combined into complete segmentation mask.
more challenging. By definition, adversarial attacks have to be unnoticeable, meaning the adversary only has limited budget for perturbing the input. When each output is focused a different part of the input, the adversary has to decide on where to allocate their adversarial budget and may be unable attack all outputs at once. Our collective robustness certificate explicitly accounts for this budget allocation problem faced by the adversary and can thus provide stronger robustness guarantees.
Our certificate is based randomized smoothing (Liu al., 2018a Lécuyer al. 2019 Cohen
itt al., 2019). Randomized smoothing is versatile black-box certification method that has originally been proposed for single-output classifiers. Instead of directly analysing a model, it constructs smoothed classifier that returns the most likely prediction of the model under random perturbations of its input. One can then use statistical methods certify the robustness of this smoothed classifier. We discuss more details in [Section 2] Randomized smoothing is typically used with i.id. noise: Each part of the input (e.g. each pixel) independently undergoes random perturbations sampled from the same noise distribution. One can however also use non-i.i.d. noise (Eiras et al. (002I). This results in a smoothed classifier that certifiably more robust to parts of the input that are smoothed with higher noise levels (e.g. larger standard deviation).
We apply randomized smoothing to softly-local multi-output classifiers a scheme we call local- ized randomized smoothing: Instead of using the same smoothing distribution for all outputs, randomly smooth each output (or set of outputs) using a different non-i.i.d. distribution that matches its inherent soft locality. Using low noise level for the most relevant parts of the input allows us to retain a high prediction quality (e.g. accuracy). Less relevant parts of the input can be smoothed with higher noise level. The resulting certificates (one per output) explicitly quantify how robust each prediction is to perturbations of which section of the input they are certificates of soft locality.
After certifying each prediction independently using localized randomized smoothing, we construct a (mixed-integer) linear program that combines these per- predicedittion base certificates into a collective certificate that provably bounds the number of simultaneously attackable predictions. This linear program explicitly accounts for soft locality and the budget allocation problem it causes for the adversary. This allows us to prove much stronger guarantees of collective robustness than simply certifying each prediction independently. Our core contributions are:
Localized randomized smoothing, a novel smoothing scheme for aulti-output classifiers.
A variance smoothing method for efficiently certifying smoothed models on discrete data.
A collective certificate that leverages our identified common interface for base certificates.
2 BACKGROUND AND RELATED WORK
Randomized smoothing, Randomized smoothing is a flexible certification technique that can be used for various data types, perturbation models and tasks. For simplicity, focus
2

---

Under review as a conference paper at ICLR 2022
classification certificate for l2 perturbations (Cohen et al. 2019). Assume have continu- ous D-dimensional input space RR,, a label set Y and a classifer g : RD - Y. We can use isotropic Gaussian noise with standard deviation a E R. to construct the smoothed classifier = argmaxyey yEY Prz~N(zz.o) [=(=) = y] that returns the most likely prediction of base classifier g under the input distribution | Given an input E R and the smoothed prediction y fxx) we want to determine whether the prediction robust to all 12 perturbations of magnitude e, i.e. whether Vw' || - æ æ212 S f<=' = y. Let Prz-N(aa,o) [9())) = y] be the probability of y predicting
label y. The prediction of our smoothed classifier is robust if < σ (q) (Cohen et al. 2019
This result showcases a trade-off we alluded to in the previous section: The certificate can become stronger if the novse-level (here σ) is increased. But doing so could also lower the accuracy of the smoothed classifier or reduce and thus weaken the certificate.
White-box certificates for multi-output classifiers. There are multiple recent methods for certify- ing the robustness of specific multi-output models (see, for example, (Tran et al., [02T Zügner &
Günnemann 2019 Bojchevski & Günneeannn 2019 Zügner& & Günnemann [0200] Ko al. 2019
Ryou et al. [021] Shi et al. [020] [oonacrt et al. (022)) by analyzing their specific architecture and weights. They are however not designed to certify collective robustness. They can only determine
independently for each prediction whether or not it can be adversarially attacked.
Collective robustness certificates. Most directly related to our work is the certificate Schuchardt et al. (202T). Like ours, it combines many per-prediction certificates into collective certificate. But, unlike our novel localized smoothing approach, their certification procedure only beneficial for strictly local models, i.e. models whose outputs operate on small subsets of the input. Further- more, their certificate assumes binary data, while our certificate defines a common interface for various data types and perturbation models. A more detailed comparison can be found in Seeciion D Recently, Fischer et al. (202T) proposed a certificate for semantic segmentation. They consider a dif- ferent notion of collective robustness: They are interested in determining whether all predictions are robust, In [Secttonn C.4 we discuss their method in detail and show that, when used for certifying our notion of collective robustness (i.e. the number of robust predictions), their method is better than certifying each output independently using the certificate of Cohen et al. (2019). Furthermore, our certificate can be used to provide equally strong guarantees for their notion of collective robustness by checking whether the number of certified predictions equals the overall number of predictions. Another method that can be used for certifying collective robustness is center smoothing (Kumar & Goldstein (021). Center smoothing bounds how much vector-valued prediction changes w.r.t to a distance function under adversarial perturbations. With the to pseudo-norm as the distance function, center smoothing bounds how many predictions of a classifier can be simultaneously changed.
Randomized smoothing with non-i.i.d. noise. While not designed for certifying collective ro- bustness, two recent certificates for non-ii.d. Gaussian (Fischer et al. 2020) and uniform smooth- ing (Eiras et al.) 2021) can be used as a component of our collective certification approach: They can serve as per- prediction base certificates, which can then be combined into our stronger collec- tive certificate (more details in /Section 4). Note that we do not use the procedure for optimizing the smoothing distribution proposed by Eiras et al.] (2021) as this would enable adversarial attacks the smoothing distribution itself and invalidate the certificate (see discussion by Wang et al. (2021)
COLLECTIVE THREAT MODEL
Before certifying robustness, we have to define a threat model, which specifies the type of model that is attacked, the objective of the adversary and which perturbations they are allowed to use. We assume that we have multi-output classifier ʃ D + Dontt that maps from a -in-dimmnsionnl vector space to Dout labels from label set Y. We further assume that this classifier f is the result of randomly smoothing base classifier g. as discussed in /Section 2 To simplify notation, write fn to refer to the function x + f(x),, yn that outputs the n-th label. Given this multi- classifier f, an input x E Dn and the resulting vector of predictions y = (ax), the objective of the adversary is to cause as many predictions from a set of targeted indices T C {1...., Dea) to change. That is, their objective is m Enen [ (x') Vnl, where B_, Di. is the perturbation model. Importantly, note that the minimization operator is outside the sum, meaning the predictions have to
In practice, all prohabilities have to he estimated using Monte Carlo sampling (see discussion in Section C
3

---

Under review as a conference paper at ICLR 2022
be attacked using a single imput. As is common in robustness certification, assume norm-bound perturbation model. That is. given an input æ E X Piu, the adversary is only allowed to use perturbed ||| =اا S {c with p, 2 0.
inputs from the set 2=, {x' x Piu
4 A RECIPE FOR COLLECTIVE CERTIFICATES
Before discussing technical details, we provide a high-level overview of our method, In localized randomized smoothing, we assign each output In of base classifier y its own smoothing distribution (n(n) that matches assumptions or knowledge about the base classifier's ss soft locality, i.e. for each {I...., Dout) } choose a (n) that induces more noise in input components that are less relevant for In- For example, in Fig. I we assume that far-away regions of the image are less relevant and thus perturb pixels in the bottom left with more noise when classifying pixels in the top-right corner. The chosen smoothing distributions can then be used to construct the smoothed classifier f-
Given an input smoothing makes it possible to compute per- per-prediction base certificates. That is, for each yo. one can compute set H(n) C % of perturbed inputs that the prediction robust to, i.e. Va' E HI,," : (a()) = Yn- Our motivation for using non-i.i.d. distributions is that the HH() will guarantee more robustness for input dimensions smoothed with more noise, i.e. quantify model locality.
D and the corresponding smoothed prediction y f(x), randomized
The objective of our adversary is min Ener [ff = ynl with collective perturbation model B3 S Pis, That is, they want to change as many predictions from the targeted set as according to the base certificates provably robust to the collective threat model. This can be expressed as ΣnET ming/es, x E [.(""). In the following, we refer to this as the naive collective certificate.
possible. A trivial lower bound can be obtained by counting how many predictions
Thanks to our proposed localized smoothing scheme, we can use the following, tighter bound:
ET(a(=')) yn) min EB
Στ E (H]
min JE E
WET
NET
which preserves the fact that the adversary has to choose a single perturbed input. Because we use different non-i.i.d. smoothing distributions for different outputs, we provably know that each fn has varying levels of robustness for different parts of the input and that these robustness levels differ among outputs. Thus, in the r.h.s. problem the adversary has to allocate their limited budget across various input dimensions and may be unable to attack all predictions at once, just like when attacking the classifier in the l.b.s. objective (recall [Section Tp. This makes our collective certificate stronger than the naïve collective certificate, which allows each prediction to be attacked independently.
As stated in Section [ the idea of combining base certificates into stronger collective certificates has already been explored by (Schuchardt et al. (202T). But instead of using localized smoothing to capture the (soft) locality of a model, their approach leverages the fact that perturbations outside an output's receptive field can be ignored. For softly local models, which have receptive fields covering the entire input, their certificate is no better than the naïve certificate. Another novel insight underlying our approach that various non-i.i.d. randomized smoothing certificates share a common interface, which makes our method applicable to diverse data types and perturbation models. In the next section, we formalize this common interface. We then discuss how allows us to compute the collective certificate from Eq.. Jusing (mixed-integer) linear programming.
5 COMMON INTERFACE FOR BASE CERTIFICATES
base certificate for a prediction y/- = (xx) is a set H,, S x.... of perturbed inputs that yo is provably robust to, ie Vx' E HH, fn(x') Vn. Note that base certificates do not have to be exact, but have to be sound, i.c. they do not have to specify all inputs to which the fn are robust but they must not contain any adversarial examples. As common interface for base certificates, that the sets H,, are parameterized by a weight vector (") E Dim and a scalar ry'") that define linear constraint on the element-wise distance between perturbed inputs and the clean input:
propose
Din
(n)
x E Dm
10'a - =xal" < 17 w
(n)
(2)
4

---

Under review as a conference paper at ICLR 2022
The weight vector encodes how robust yn is to perturbations of different components of the input. The scalar x is important for collective robustness certification, because encodes which collective perturbation model the base certificate is compatible with. For example, certificate can be used for certifying collective robustness to l2 perturbations.
means that the base
In the following, we present two base certificates implementing our interface: One for l2 perturba- tions of continuous data and one for perturbations of binary data. In (nectii B] we further present a certificate for binary data that can distinguish between adding and deleting bits and certificate for Ii perturbations of continuous data. All base certificates guarantee more robustness for parts of the input smoothed with a higher noise level. The certificates for continuous data are based on known results (Fischer et al.] [2000] Eiras et al.] (22T) and merely reformulated to match our proposed in- terface, so that they can be used as part of our collective certification procedure. The certificates for discrete data however are original and based on the novel concept of variance smoothing.
Gaussian smoothing for l2 perturbations of continuous data The first base certificate is a gen- eralization of Gaussian smoothing to anisotropic noise, corollary of Theorem A.I from (Fischer) p.20p. In the following, diag(z) refers to a diagonal matrix with diagonal entries z and 0., + R refers to the the standard normal inverse cumulative distribution function.
al. (et
Proposition Given an output 9n : Pin + Y. let f (x) = argmax yEV Piz~N(x,E) (2)=
be the corresponding smoothed output with Σ diag )or² and a E &R.... Given an imput E PR. and smoothed prediction Yn S (x), ) let q = Prz~A((xE)) (gn(2) = ynl. Then, Ve' E H(m))
(x'') 1), with H() defined as in Eq. 2 wa- 0. 1) (0()))aa) and k 2.
Bernoulli variance smoothing for perturbations of binary data For binary data, use smooth- ing distribution F(x, 0) with 0 E [0. Pim that independently flips the d' d'th bit with probability Od, ic. for x, {0, P) and z F(x, 0) we have Pr[za # za] = 02. A corresponding certificate could be derived by generalizing (Lee et al. 2019), which considers a single shared @ E [0, 1] with vd fu- 0. However, the cost for computing this certificate would be exponential in the number of unique values in O, We therefore propose a more efficient alternative. Instead of constructing smoothed classifier that returns the most likely labels of the base classifier (as discussed in [Scc- tion 2). we construct smoothed classifier that returns the labels with the highest expected softmax scores (similar to CDF-smoothing (Kumar et al.] (0200). For this smoothed model, we can com- pute robustness certificate in constant time. The certificate requires determining both the expected value and variance of softmax scores. We therefore call this method variance smoothing. While we use it for binary data, it is a ceneral-purpose technique that can be applied to arbitrary domains and smoothing distributions (see discussion in Secciinn B.2). In the following, we assume the label set Y to consist of numerical labels {1, ..,..., [)) which simplifies our notation.
Theorem 1. Given an output 9n. : (0, Pm + d mapping to scores from the |YJdimensioonll (9n(z))) be the corresponding smoothed
probability simplex, let fnx = argmax ye
classifier with E [0, P Given an input x E {0.1) Piu and smoothed prediction you = =fn(x))
let μ = (g-J((m 0) 19n (z) yy and o² = Var Ign (z)ll. Then, Vx' E (H(")) fn(('') = yn
with (*) defined as in Eq. 2 wa In (1-0,))
(0,)²
In (1 2/ (p 1)²) and K = O.
1-0x
6 COMPUTING THE COLLECTIVE ROBUSTNESS CERTIFICATE
With our common interface for base certificates in place, we can discuss how to compute the collec- tive robustness certificate min RR2 Ener [x' E [[]()] from Eq. The result bounds the number
of predictions yn with n E (1,.... Dout) } that can be simultaneously attacked by the adversary. In
the following, we assume that the base certificates were obtained by using smoothing distribution
that is compatible with our I, collective perturbation model (i.e. x = for example by using Gaus-
sian noise for p 2 or Bernoulli noise for p O. Inserting the definition of our base certificate
interface from Eq. 2 and rewriting our perturbation model B { x'' E x ||æ" - x lpp S $) as
ax E Di
Din 1==1 L'' xa.. P < EP our objective from Eq. can be expressed
Din
Dmn
min Σ Pin
Σ
w
10ra
rall < (n)
s.t.
x/j - xz P <
ce. e.
(3)
TET
1d=1
d=1
5

---

Under review as a conference paper at ICLR 2022
We that the perturbed input x' only affects the element-wise distances lz/-zzll Rather than optimizing x', we can instead directly optimize these distances, i.c. determine how much adversarial budget is allocated to each input dimension. For this, we define a vector variables b E R. (or
b E {0, Pi for binary data). Replacing sums with inner products, we can restate Eq. 3 as
min BER," Pin
Ei(o
w < mn
s.t. sum(b} S e².
(4)
NET
In a final step, we replace the indicator functions in Eq. 4 with vector of boolean variables t E {0, Dout, Define the constants v(()) =e. .min (0. mina (mi) Then,
min
(m) 2 tn + +(1 (n) sum S (5) Etn tn s.t. Vn: 6" (n)
e..
bER Pio (0, Pour RET
is equivalent to Eg. 4] The first constraint guarantees that in can only be set to 0 if the l.h.s. is greater or equal n7 i.e. only when the base certificate can no longer guarantee robustness. The term involving (n()) ensures that for 4 = 1 the problem is always feasible Eq. can be solved using any mixed-integer linear programming solver.
While the resulting MILP bears some semblance to that of Schuccaaddd et al. (2021). it is conceptually different. When evaluating their base certificates, they mask out parts of the budget vector based on a model's strict locality, while we weigh the budget vector based on the soft locality guaranteed by the base certificates. In addition, thanks to the interface specified in Section [ our problem only involves single linear constraint per prediction, making it much smaller and more efficient solve. Interestingly, when using randomized smoothing base certificates for binary data, our certificate subsumes theirs, i.e. can provide the same robustness guarantees (see D.2).
Improving efficiency. Still, the efficiency of our certificate in Eq. 3) certificate can be further improved. In |Section A we show that partitioning the outputs into Nout subsets sharing the same smoothing distribution and the the inputs into Ni subsets sharing the same noise level (for example like in Fig. 1). well as quantizing the base certificate parameters r7(") into Nbin bins reduces the number of variables and constraints from Din + Dont and Dout. to Nin + Nout Nbins and Nout Nbins + 1, respectively, We can thus control the problem size independent of the data's dimensionality. We further derive linear relaxation of the mixed-integer problem, which can be more efficiently solved while preserving the soundness of the certificate.
LIMITATIONS
The main limitation of our approach is that it assumes softly local models. While it can be applied to arbitrary multi-output classifiers, may not necessarily result in better certificates than randomized smoothing with i.i.d. distributions. Furthermore, choosing the smoothing distributions requires some a-priori knowledge or assumptions about which parts of the input are how relevant to making a prediction. Our experiments show that natural assumptions like homophily can be sufficient for choosing effective smoothing distributions. But doing so in other tasks may be more challenging.
A limitation of (most) randomized smoothing certificates is that they use sampling to approximate the smoothed classifier. Because we use different smoothing distributions for different outputs, we can only use a fraction the samples for each output. As discussed in [Section A. we can alleviate this problem by sharing smoothing distributions among multiple outputs. Our experiments show that despite this issue, our method outperforms certificates that use single smoothing distribution. Still, future work should try to improve the sample efficiency of randomized smoothing (for example by developing more methods for de- de-randomized smoothing (Levine Feizi (0200).Any such advance could then be incorporated into localized smoothing framework.
8 EXPERIMENTAL EVALUATION
Our experimental evaluation has three objectives 1.) Verifying our main claim that localized random- ized smoothing offers a better trade-off between accuracy and certifiable robustness than smoothing
2 Because (m) is the smallest value bt (n) can take on, i.e. min beR.i. Pia b (w (n) s.t. sum(b) S e..

---

Under review as a conference paper at ICLR 2022
with i..d. distributions. 2.) Determining to what extend the linear program underlying the proposed collective certificate strengthens our robustness guarantees. 3.) Assessing the efficacy of our novel variance smoothing certificate for binary data. Any of the used datasets and classifiers only serve as a means of comparing certificates. We thus use well-known and well-established architectures instead of overly focusing on maximizing prediction accuracy by using the latest SOTA models.
We use two metrics to quantify certificate strength: Certified accuracy (i.e. the percentage of correct and certifiably robust predictions) and certified ratio (i.e. the percentage of certifiably robust pre- dictions, regardless of correctness [ As single-number metrics, we report the AUC of the certified accuracy/ratio functions w.r.t. adversarial budget (not be confused with certifying some AUC metric). For localized smoothing, we evaluate both the naive collective certificate, i.c. certifying predictions independently (see SSccion 4), and the proposed I. L.--based certificate (using the linearly relaxed version from Appendix AA44). We compare our method to two baselines using i.i.d. random- ized smoothing: The naïve collective certificate and center smoothing (Kumar & Goldstein 2021). For softly local models, the certificate Sfhhchaahr al. (202I) is equivalent to the naive baseline. When used to certify the number of robust predictions, the segmentation certificate of Fischer et al. 2021 is at most as strong the naive baseline (see [Section C.4). Thus, our method is compared to all existing collective certificates listed in Section [2] In all experiments, we use Monte Carlo randomized smoothing. More details the experimental setup can be found in Seection E
8.1 SEMANTIC SEGMENTATION
Dataset and model. We evaluate our certifi- cate for continuous data and l2 perturbations on the PaScal-VOC 2012 segmentation valida- tion set. Training is performed on 10582 pairs
1.0
Certified accuracy
LP localized
0.8
of training samples extracted from SBL* (Har-
0.6
Naive
iharan et al.] (011)) To increase batch sizes and thus allow a more thorough investigation of different smoothing parameters, all images are downscaled to 50% of their original size. Our base model is U-Net segmentation model with a ResNet-18 backbone. To obtain accu- rate and robust smoothed classifiers, base mod- els should be trained on the smoothing distribu- tion. We thus train 51 different instances of our base model, augmenting the training data with a different train E {0, 0001..... ...5). At test time, when evaluating baseline i.i.d. certificate with smoothing distribution (10 r),, we load the model trained with Trrain a. To perform localized randomized smoothing, we choose pa- rameters mmin max E R_ and partition all im- ages into regular grids of size 4 x 6 (similar to example Fig. 1p. To classify pixels in grid cell (i,j), we sample noise for grid cell (k,1) using (O o') ). with o' E [ominn mmax] chosen proportional to the distance of (i.j) and (k, (more de- tails in (Section E.2.I). As the base model, we load the one trained with Terain amin- Using the same distribution at train and test time for the i.i.d. baselines but not for localized smoothing is meant to skew the results in the baseline's 's favor. But, in Section E.2.3 we also repeat our experiments using the same base model for i.i.d. and localized smoothing.
localized
0.4
Naive i.i.d.
0.2
0.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget e
Figure 2: Certified ratios of U-Net models un- der varying We compare the naive i.i.d. base- line (a = 0.4) to localized smoothing (amin = 0.25, maax 1.5). Combining the base certifi- cates via linear programming (solid orange line) instead of evaluating them independently (dotted orange line) outperforms the baseline.
Evaluation. The main goal of our experiments on segmentation is to verify that localized smoothing can offer a better trade-off between accuracy and certifiable robustness. That is, for all or most o, there are mmin, mmax such that the locally smoothed model has higher accuracy and certifiable collective robustness than i.i.d. smoothing baselines using (0,, Ø). Because 0,, m o max E R,, we can not evaluate all possible combinations. We therefore use the following scheme: We focus on the case E [0, 0.5). which covers all distributions used in (Kumar & Goldstein 2021 and
In the case of image segmentation, we compute these metrics per image and then average over the dataset. "Asso known "Pascal trainaug"
7

---

Under review as a conference paper at ICLR 2022
(Fischer al. 2021). First, we evaluate our two baselines for five {0.1,0.2, 0.4, 0.5). This results in baseline models with diverse levels of accuracy and robustness (c.g. the accuracy of the naive baseline shrinks from 87.7% to 64.9% and the AUC of its certified accuracy grows from 0.17 to 0.644). We then test whether, for each of the o, we can find miin max such that the locally smoothed models attains higher accuracy and is certifiably more robust. Finally, verify that {0.1, 0.2, 0.3, 0.4, J.5) were not just a particularly poor choice of baseline parameters, we fix the chosen min, max We then perform a fine-grained search over a E [0, 0.5] with resolution 0.01 to find a baseline model that has at least the same accuracy and certifiable robustness (as measured by certificate AUC) as any of the fixed locally smoothed models. If this is not possible, this provides strong evidence that the proposed smoothing scheme and certificate indeed offer better trade-off.
Fig. shows one example. For a = 0.4, the naive i.i.d. baseline has an accuracy of 72.5%. With min = 0.25, max = 1.5, the proposed localized smoothing certificate yields both higher accu- racy of 76.4% and higher certified accuracy for all c. can certify robustness for c up to 1.825, compared to 1.45 of the baseline and the AUC of its certified accuracy curve is 43.1% larger. Fig. also highlights the usefulness of the linear program we derived in Section 5] Evaluating the local- ized smoothing base certificates independently, i.e. computing the naive collective certificate (dotted orange line), is not sufficient for outperforming the baseline. But combining them via the proposed linear program drastically increases the certified accuracy
The results for all other combinations of smoothing distribution parameters, both baselines and both metrics of certificate strength can be found in /Section E.2.3] of our evaluation procedure, in which we optimize the localized smoothing parameters. Safe for one exception (with 0.2, center smoothing has a lower accuracy, but slightly larger certified ratio), the locally smoothed models have the same or higher accuracy, but provide stronger robustness guarantees. The difference is particularly large for o E {0.3, 0.4, 0.53. where the accuracy of models smoothed with i.i.d. noise drops off, while our localized smoothing distribution preserves the most relevant parts of the image to allow for high accuracy. [Table 5] summarizes the second part of our evaluation scheme, in which we perform fine-grained search over [0, 0.5). We find that there is no a such that either of the i.i.d. baselines can outperform any of the chosen locally smoothed models w.r.t. AUC of their certified accuracy certified ratio curves. This is ample evidence for our claim that localized smoothing offers a better trade-off than i.i.d. smoothing. Also, the collective LPs caused little computational overhead (avg. 0.68 s per LP, more details in Section E.2.3).
and
the first part
8.2 NODE CLASSIFICATION
Dataset and model. We evaluate our certificate for binary data on the Cora-ML. node classification dataset. We use two different base-models: Approximate Personalized Propagation of Neural Pre- dictions (APPNP) (Klicpera et al. 2019) and 6-layer Graph Convolutional network (GCN) (Kipf & Welling 2017). Both models have a receptive field that covers most or all of the graph, meaning they are softly local. For details on model and training parameters, see Section E.3.1
As center smoothing has only been derived for Gaussian smoothing, we only compare to the naive baseline. For both. the baseline and our localized smoothing certificate, we use sparsity- ran- domized smoothing (Bojchevski et al. 2020) i.e. flip 1-bits and 0-bits with different probabilities (0- and 0+, respectively), which allows us to certify different levels of robustness to deletions and additions of bits. With localized randomized smoothing, we use the variance smoothing base certifi- cate derived in [Section B.2.2 We choose the distribution parameters for localized smoothing based on an assumption of homophily, i.e. nearby nodes are most relevant for classifying a node. We par- tition the graph into 5 clusters and define parameters 6 and @tt When classifying a node in cluster i, we randomly smooth attributes in cluster j with t o.j that are based on linearly interpo- lating in 10min= maax and [mmin> maxx] based on the affinity of the clusters (details in Section E.
Evaluation. We first evaluate the new variance-based certificate and compare it to the certificate derived by [Bojchevsii et al. (2020). For this, we use only one cluster, meaning we use the same smoothing distribution for both. Fig. in Section E.3 shows that the variance certificate is weaker than the baseline for additions, but better for deletions. It appears sufficiently effective to be used as a base certificate and integrated into stronger, collective certificate.
The parameter space of our smoothing distributions is large. For the localized approach we have four continuous parameters, as have to specify both the minimal and maximal noise values.
8

---

Under review as a conference paper at ICLR 2022
1.0
1.0
Certified accuracy
LP localized
Certified accuracy
LP localized
0.8
0.8
Naive localized Naive i.d.
Naive localized
0.6
0.6
Naive i.d.
0.4
0.4
0.2
0.2
0.0
0.0
20 30
50
0
10
30
40
Number of adversarial additions
Number of adversarial deletions
Figure 3: Certified accuracy for an APPNP model under varying number of attribute additions (left)
and deletions (right). We compare localized smoothing (0 = 0.05, 0 = 0.65, 0 0.08, max 0.95) to two separately optimized naïve i.i.d. smoothing baselines: addition (8 0.04, O = 0.61) and deletion (#+ 0.04. f- = 0.68). Combining the localized smoothing base certificates via linear programming (solid orange line) instead of evaluating them independently (dotted line) allows us to outperform the baselines for most adversarial budgets.
Therefore, it is difficult to show that our approach achieves a better accuracy-robustnes trade-off over the whole noise space. However, we can investigate the accuracy-robustees trade-off within some areas of this space. For the localized approach we choose a few fixed combinations of the noise parameters Ammia and 0 To show our claim, we then optimise the baselines with parameters in an interval around our 8 and 6 6 This is smaller space, as the baselines only have two parameters. We select the baseline whose certified accuracy curve has the largest AUC. We perform the search for the best baseline for the addition and deletion scenario independently, i.e., the best baseline model for addition and deletion does not have to be the same.
In Fig. 3,
the certified accuracy of APPNP model for varying number of attribute ad- ditions and deletions (left and right respectively). To find the best distribution parameters for the baselines, we evaluated combinations of 6 E (0.04, 0.055, 0.07) and 0 [0.1..... 0.827J. using 11 equally spaced values for the interval. For adversarial additions, the best baseline yields a certi- fied accuracy curve with AUC of 4.51 compared to 5.65. The best baseline for deletions has an AUC of 7.76 compared to our 16.26. Our method outperforms these optimized baselines for most adversarial budgets, while maintaining the same clean accuracy (i.e. certified accuracy e 0). Experiments with different noise parameters and classifiers can be found in Section E.3] In general, we find that we significantly outperform the baseline when certifying robustness deletions, but often have weaker certificates for additions (which may be inherent to the variance smoothing base certificates). Due the large continuous parameter space, we cannot claim that localized smoothing outperforms the naïve baseline everywhere. However, our results show that, for the tested parameter regions, localized smoothing can provide a significantly better accuracy-robustnes. trade-off.
We found that using the collective LP instead of naïvely combining the base certificates can result in much stronger certificates: The AUC of the certified accuracy curve (averaged over all experiments) increased by 38.8% and 33.6% for addition and deletion, respectively. The collective LPs caused little computational overhead (avg. 10.9 s per LP, more details in SScctio E.3.3).
CONCLUSION
In this work, we have proposed the first collective robustness certificate for softly local multi-output classifiers.
based on localized randomized smoothing, i.e. randomly smoothing different outputs using different non-i.i.d. smoothing distributions matching the model's locality. We have shown how per-output certificates based on localized smoothing can be computed and that they share a common interface. This interface allows them to be combined into strong collective bustness certificate. Experiments on image segmentation and node classification tasks demonstrate that localized smoothing offer better bobustness-accuraae trade-off than existing randomized smoothing techniques. Our results show that locality is linked to robustness, which suggests the research direction of building more effective local models to robustly solve multi-output tasks.

---

Under review as a conference paper at ICLR 2022
10 REPRODUCIBILITY STATEMENT
We prove all theoretic results that were not already derived in the main text in Appendices to To ensure reproducibility of the experimental results we provide detailed descriptions of the evaluation process with the respective parameters in Section E.2 E.2 [Sccion E.3 Code will be made available reviewers via an anonymous link posted on OpenReview, suggested by the guidelines.
11 ETHICS STATEMENT
In this paper, we propose a method to increase the robustness machine learning models against adversarial perturbations and to certify their robustness. We see this an important step towards general usage of models in practice, as many existing methods are brittle to crafted attacks. Through the proposed method, we hope to contribute to the safe usage of machine learning. However, robust models also have to be seen with caution. As they are harder to fool, harmful purposes like mass surveillance are harder to avoid. We believe that it is still necessary to further research robustness of machine learning models as the positive effects can outweigh the negatíves, but it is necessary to discuss the ethical implications of the usage in any specific application area.
REFERENCES
T.W. Anderson. Confidence limits for the value of an arbitrary bounded random variable with a con- tinuous distribution function. In Bulletin The International and Statistical Institute, volume 43, pp. 251, 1969.
Yonatan Belinkov and Yonatan Bisk. Synthetic and natural noise both break neural machine translation. In International Conference on Learning Representations, 2018. URL https:
7/ //ppeneevie.nnet.. http://eeeeetooooaaaaa-aeoaaaee
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In
Advances in Neural Information Processing Systems, volume 32, pp. 8319-8330, 2019.
Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference Machine Learning, pp. 1003-1013. PMLR, 2020.
Gregory Bonaert, Dimitar Dimitrov, Maximilian Baader, and Martin Vechev. Fast and precise certification of transformers. In Proceedings of the 42nd ACM SIGPLAN International Confer- ence on Programming Language Design and Implementattion, PLDI 2021, pp. 466 481, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383912. 10.114553453433334444000 URL
doi: 11 1 44445334444333 3454056
Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del Istituto Superiore di Scienze Economiche Commericiali di Firenze, 8:3-62 1936.
G. Bradski. The OpenCV Library. Dr. Dobb's Journal of Software Tools, 2000.
Alexander Buslaev, Vladimir I. Iglovikov, Eugene Khvedchenya, Alex Parinov, Mikhail Druzhinin, and Alexandr Kalinin. Albumentations: Fast and flexible image augmentations. Information, 11(2), 2020. ISSN 2078-2489, 2078 200-2449//1/2/223
doi: 10.3390/infol 1020125. htLhttss: //tt:::::/wwww/ www. mápi. com/
C. J. Clopper and E. S. Pearson. The use confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-413 1934. ISSN 00063444. URL http:://wwt jstor.
3rg/stable/233155
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 13200 PMLR, 09-15 Jun 2019. URL /ttta::://ppcceeeeeeeee https/////oceeeigss.i.e .mlr.
preas/v97/cohen cohen 9c. htm]
10

---

Under review as a conference paper at ICLR 2022
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
A. Dvoretzky, Kiefer, and Wolfowitz. Asymptotic Minimax Character of the Sample Distri- bution Function and of the Classical Multinomial Estimator. The Annals of Mathematical Statis- tics, 27(3):642 - 669, 1956. doi: 10.2144/0mm111777221774 URL https: : //o::///ooooooo org/10. 1214/aoms11177338
Francisco Eiras, Motasem Alfarra, M. Pawan Kumar, Philip H. S. Torr, Puneet K. Dokania, Bernard Ghanem, and Adel Bibi. Ancer: Anisotropic certification via sample-wise volume maximization. 2021.
Mare Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transformations via randomized smoothing. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and Lin
(eds.), Advances in Neural Information Processing Systems, volume 33, pp. 8404-8417. Cur- ran Associates, Inc., 2020. [eL//tttpp://rrreeednee nwurgis..euri..... wttp:/ppps.cppppp/2//22
f 41le/55b3aabbbbbeeeeeeeeaa 300 Fa2er//5577soaaaaaaaaaaaoaarrrar
Mare Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via ran- domized smoothing. International Conference on Machine Learning, pp. 3340-3351. PMLR, 2021.
Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik. Se- mantic contours from inverse detectors. In 2011 International Conference on Computer Vision, pp. 991-998, 2011. doi: 10. 109/1CC// 11122011.666 1.6126333.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016.
doi: 10.1 10.1109/CPPR.2116990
Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2):65-70, 1979. ISSN 03036898, 14679469. URL http: www. jstor org
stable/4615733
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning ir- regular graphs. SIAM Journal on Scientific Computing, 20(1):359 392. 1998. doi: 10.1137/
$1064827595287997,, 1ttppp/pp.///00...c./..11111111.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 20/7, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank, 2019.
Ching-You Yun Ko, Zhaoyang Lyu, Lily Weng, Luca Daniel, Ngai Wong, and Dahua Lin. POPQORN: Quantifying robustness of recurrent neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2019. URL https: httpps::/proceeinnggg wtw.:iiggss.r....ssss...... www.sp.essvvvvv wwt.ss///9//oo/ htm
PMLR, 09-15 Jun
mlr
Aounon Kumar and Tom Goldstein. Center smoothing: Provable robustness for functions with metric-space outputs. 2021.
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via ran- domized smoothing. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5165 5177. Curran Asso- ciates, Inc., 2020. U.L.hecpps///prooeeeesss.....a 47aa5dfcc44dddddd 9d43 h2ta::ceeccccco00144444111000000 http://ppoooaaaa...........or/rr

---

Under review as a conference paper at ICLR 2022
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy, SP 2019, San Francisco. CA, USA. May 19- 2019, pp. 656-672. IEEE, 2019. doi: 10.1109/SP.2019.00444
http:sttt:///ttt /doi. org / /00. 1109/55 201 9.099.000 9.0044
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S. Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. 2019.
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 6465 6475. Curran Asso- ciates, Inc., 2020. URL httpss://pproceeedngggggog//// meu... inserrpps ips. httpp.ccpppppeeeeee ccc/paper/2220/51eee. pdf
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh. Towards robust neural networks via random self-ensemble. In Computer Vision ECCV 2018, pp. 381-397. Springer International Publishing, 2018a. doi: 10. 10.1007/978-3- 0111//78883-0000122-22-2-0
Yongge Liu, Jianzhuang Yu, and Yahong Han. Understanding the effective receptive field in seman- tic image segmentation. Multimedia Tools and Applications, 77(17):2119-22217,, jan 2018b. doi: 10. 10.1007//11022-01--577
Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel. Understanding the effective receptive field in deep convolutional neural networks. Proceedings of the 30th International Conference Red Hook, NY, USA, 2016.
on Neural Information Processing Systems, NIPS' 16, pp. Curran Associates Inc. ISBN 9781510838819.
MOSEK ApS. MOSEK Optimizer API for Python 9.2.46, 2019. URL com/ 9.
html
Olaf Ronneberger. Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomed- ical image segmentation. In Medical Image Computing and Computer-Assine Asssisttd Intervention .ICCAI 2015, pp. 234 241. Springer International Publishing, 2015. ISBN 978-3-319-245444.
Wonryong Ryou, Jiayu Chen, Mislav Balunovic, Gagandeep Singh, Andrei Dan, and Martin Vechev. Scalable polyhedral verification of recurrent neural networks. In Alexandra Silva and K. Rus- tan M. Leino (eds.), Computer Aided Verification, pp. 225-248, Cham, 2021. Springer Interna- tional Publishing. ISBN 978-3-030-81685.
Jan Schuchardt. Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations, 2021. URL
net. forum?
Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James Tin-Yau Kwok. Sparsebert: Rethinking the importance analysis in self-attention. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learn ing Research, pp. 9547-9557. PMLR, 2021. URL httphttt:///rrcceiinne http:/oooeeednn........r......s. html
Zhouxing Shi, Huan Zhang, Kai-Wei Chang, Minlie Huang, and Cho-Jui Hsich. Robustness veri- fication for transformers. In International Conference on Learning Representations, 2020. URL
htttps://openreviier net www.:/nee/oooumfooooto
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL http: http///axivv... org/ abs /tlos/1112..m 6199
Hoang- Dung Tran, Neelanjana Pal, Patrick Musau, Diego Manzanas Lopez, Nathaniel Hamilton, Xiaodong Yang, Stanley Bak, and Taylor T. Johnson. Robustness verification of semantic segmen- tation neural networks using relaxed reachability. In Computer Aided Verification, pp. 263-286, Cham, 2021. ISBN 978-3-030- -1655-8.
12

---

Under review as a conference paper at ICLR 2022
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Proceedings of the 31st Inter- national Conference Neural Information Processing Systems, NIPS' 17, pp. 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 578151086996..
Lei Wang, Runtian Zhai, Di He, Liwei Wang. and Jian. Pretrain-to-finetune adversarial training via sample-wise randomized smoothing, 2021. URL httpstts: /ttp:////ppeeeeeeeeeeemoe net. ffr/ffrrmmm id Ti--Taaa2myP
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adversar- ial examples for semantic segmentation and object detection. In International Conference on Computer Vision. IEEE, 2017.
Pavel Yakubovskiy. Segmentation models pytorch. https://gittub.commmmm
secmentation, lttpr/atttooomdellseeeemmmm pytooch,, 2020.
Dinghuai Zhang. Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box cer- tification with randomized smoothing: A functional optimization based framework. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2316 2326. Curran Asso- ciates, Inc., 2020. URL htttp::/ www.iinerippp... wttppppppep//////eeeeeeeee 1896a3bf
pdff
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations, 2019. URL https://
openreview. net nett//oorumm.dd331xxx22
Daniel Zügner and Stephan Günnemann. Certifiable robustmess and robust training for graph con- volutional networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2019.
Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1656-1665, 2020.
A IMPROVING EFFICIENCY
In this section, we discuss different modifications to our collective certificate that improve its sam- ple efficiency and allow us fine-grained control over the size of the collective linear program. We further discuss linear relaxation of our collective linear program. All of the modifications preserve the soundness of our collective certificate, i.c. we still obtain provable bound on the number of predictions that can be simultancously attacked by adversary. To avoid constant case distinc- tions, we first present all results for real-valued data, i.e. = IR, before mentioning any additional precautions that may be needed when working with binary data.
A. SHIARING SMOOTHING DISTRIBUTIONS AMONG OUTPUTS
In principle, our proposed certificate allows a different smoothing distribution (m)) be used per output 9n of our base model. In practice, where we have to estimate properties of the smoothed classifier using Monte Carlo methods, this problematic: Samples cannot be re-used, each of the many outputs requires its own round of sampling. We can increase the efficiency of our localized smoothing approach by partitioning our Dout outputs into Nout subsets that share the same smooth- ing distribution. When making smoothed predictions computing base certificates, reuse the same samples for all outputs within each subsets.
then
More formally, we partition our Dout output dimensions into sets (()).., K (Nout) with
Nout
K (i)
f1..... Dout
(6)
13

---

by defining equally sized bins between gin 17(") and max, ry(*) we can ensure that Under review as a conference paper at ICLR 2022
We then associate each set K() with smoothing distribution Tr(() For each base model output In. with n E (6)() we then use smoothing distribution v)(() to construct the smoothed output fn. e-g- Ja (a) = argmax, weY Pr g(1)) [f + + = y] (note that we use different smoothing paradigm
for binary data, see Section 5
A.2 QUANTIZING CERTIFICATE PARAMETERS
Recall that our base certificates from Section are defined by a linear inequality: A prediction
In (a) is robust to a perturbed input x' E X if Σd= waa
(x) | xall < mf("), for some p 2 0. The weight vectors w()) IR Din only depend on the smoothing distributions. A side of effect of sharing the same smoothing gp(i) among all outputs from set K(),, as discussed in the previous section, is that the outputs also share the same weight vector w(() E RD with
An E K(()) m((( = (n(") Thus, for all smoothed outputs Sn with n E K(0, the smoothed prediction yn, robust if E wa la'a =al" 17(
Evidently, the base certificates for outputs from set K only differ in their parameter m)(*) Recall that in our collective linear program we use a vector of variables E {0, 1 Dout to indicate which predictions are robust according their base certificates (see SectSon 6). If there are two outputs fn and fm with 17")) n7(m), then fn and fm have the same base certificate and their robustness can be modelled by the same indicator variable. Conversely, for each set of outputs K(), we only need one indicator variable per unique nf("). By quantizing the 77(*) within each subset (K()) (for example
there is always a fixed number Nains of indicator variables per subset. This way, we can reduce the number of indicator variables from Dout to Nout Nhins-
To implement this idea, we define matrix of thresholds E E IR.-Nour Niin with Vi min {E,,) s min (17)()) n E ()))). We then define function & Nou.t!,,ot.! R + R with
E(i,n) max (fE,, j (1...., A Ea, < <n))
that quantizes base certificate parameter r) from output subset K()) by mapping it to the next smallest threshold in E... For feasibility, like in Section 6 we need to compute the constant
())) = minDeR
br w/ s.t. sum(b} S e² to ensure feasibility of the problem. Note that, be-
cause all outputs from subset (6) share the same weight vector ( we only have to compute this constant once per subset. We can bound the collective robustness the targeted dimensions T of our vector of predictions f(x) follows:
min Σ
Σ
Ths KNETNK (i.)(m)) Ess
(8)
(E(.....Noon Naine
s.t. Vi,j 6t (
Te (6) (1-Tr,)Eua sum(b} S E
(9)
BERP", TE 10 Nout Noiia
(10)
Constraint Eq. 9 ensures that Túj is only set if 6² w)()) Eij. i.e. all predictions from subset K()) whose base certificate parameter r/(") is quantized Er, are no longer robust. When this is the case, the objective function decreases by the number of these predictions. For Nout Douts Nhins 1 and En, = n,("), we recover our general certificate from Section 6 Note that, the quantization maps any parameter (7(*) to a smaller number, the set H()) becomes more restrictive, i.e. Yn considered robust to a smaller set of perturbed inputs. Thus, Eq. is lower bound on our general certificate from Section 6
A.3 SHARING NOISE LEVELS AMONG INPUTS
Similar to how partitioning the output dimensions allows us to control the number of output variables partitioning the input dimensions and using the same noise level within each partition allows us to control the number variables b that model the allocation adversarial budget.
Assume that we have partitioned our output dimensions into Nout subsets K(), (Nont with outputs in each subset sharing the same smoothing distribution (0) explained in Section A.1
14

---

Under review as a conference paper at ICLR 2022
Let us now define Nu input subsets J(D) ,...., ,...,, ((iin) with
J6] {1, (l,..., Dont..
(11)
Recall that a prediction yn = fa(x) with n E k() is robust to a perturbed imput x' E P if Ed=1 wd (i) |x'' =xll" ry(*) and that the weight vectors w(() only depend on the smooth- ing distributions. Assume that we choose each smoothing distribution vp(()) such that 4/
(I....,Nua), Vd, E J w = w i.e. all input dimensions within each set J(() have the same weight. This can be achieved by choosing ()(() so that all dimensions in each input subset J' are smoothed with the noise level (note that we can still use different ()(*), i.e. different noise levels for smoothing different sets of outputs). For example, one could use Gaussian distribution with covariance matrix Σ diag (o)² with V/ E Ni, Vd, d' J : oa ad'
In this case, the evaluation of our base certificates can be simplified. Prediction yo. - (a( is robust perturbed input x' D if
Σ d=1
(8) W
1x's
Id < 17 (n)
(12)
Na
(1)
Σ dEja
la'a - xal2
<n)(m))
(13)
with E &N and Vi E Nouth,,,oot), VI (in,.., E J : u w/. That is, we can replace each weight vector wi)) that has one weight ( per input dimension d with smaller
weight vector (1) with one weight ui (6) per input subset [().
For our linear program, this means that no longer need a budget vector b E P.P model the element-wise distance (=ra = in each dimension d. Instead, we can a smaller budget vector E I model the overall distance within each input subset J(t,, i.e. Edejo nn |a's zal". Combined with the quantization of certificate parameters from the previous section, our optimization problem becomes
min
Σ
Σ Tes f {NETNKolG (1.1(() Fii)
(14)
LE(I...,Nou s.t.
Vi,j (1) 2 T (0) + -1- En,) sum(b] S se,
(15)
b BERNO, TE [0,1]Noout Nout NNiine
(16)
with u E No. and Vi (I,...,, No VI (I....,,,,I Ni. Vd E J: : w/ w For Nout = ("),,, we recover our general certificate from Section
=
Douts
Ni = Din Nbins = and =
When certifying robustness for binary data, we impose different constraints on b. To model that the adversary can not flip more bits than are present within each subset, with VI (1...., N bi & [ instead of continuous budget vector b E TR-N
budget vector b E Na"".
A.4 LINEAR RELAXATION
Combining the previous steps allows us to reduce the number of problem variables and linear con- straints from Di + Daut and Dout + to Nin + Nout Nbins and Nout Nbins + 1, respectively. Still, finding optimal solution to the mixed-intege linear program may be too expensive. One can obtain a lower bound on the optimal value and thus a valid, albeit more pessimistic, robustness certificate by relaxing all to be continuous.
When using the general certificate from Section 6. the binary vector t E {0, 1 can be re- laxed to t E [0, Puut When using the certificate with quantized base certificate parameters from Section A.2 or Section A.3 the binary matrix T e [0, Non x Nuius can be relaxed to e [0, oou Ximim Conceptually, this means that predictions can be partially certified, i.e. i, (0,
15

---

Under review as a conference paper at ICLR 2022
or Ti E (0. 1). In particular, prediction can be partially certified even if we know that is impos- sible to attack under the collective perturbation model Ex { E Pi || =xI1p S Se}. Just like Schuchardt et al. (022), who encountered the same problem with their collective certificate, circumvent this issue by first computing L [ T of all targeted predictions in that guaranteed to always be robust:
We (n)) 1ro's sall) < <ndu)
L TET
max vEBu
(17)
d=1
n max (max { ( c², 20 < <n/m)
(18)
The equality follows from the fact that the most effective way of attacking a prediction is to allocate all adversarial budget to the least robust dimension, i.c. the dimension with the largest weight unless all weights are negative. Because we know that all predictions with indices L are robust, do not have to include them in the collective optimization problem and can instead compute
[L]
+
min 2 EB
Σ NETV.
1 E E
(19)
The r.h.s. optimization can be solved using the general collective certificate from Section 6 or any of the more efficient, modified certificates from previous sections.
When using the general collective certificate from Section 6 with binary data, the budget variables b E Pi
be relaxed to b E [0, Pi When using the modified collective certificate from Section A.3 the budget variables with b E No can be relaxed to b R: The additional s |
constraint 1/ E ......,,in).
can be kept in order model that the adversary cannot flip (or partially flip) more bits than are present within each input subset J())
B BASE CERTIFICATES
In the following, show why the base certificates presented in Section 5 hold and present altemna tives for other collective perturbation models.
B. GAUSSIAN SMOOTHING FOR l2 PERTURBATIONS CONTINUOUS DATA
Proposition 1. Given output 9n IRPi. Y. let fn(x) = argmax Piz~N(e, [gn (z) y) be the corresponding smoothed output with E = diag )o)² and a E ERQ... Given an imput x E TR Din and smoothed prediction Yn = (x), let q = Prz~N(m,E)) [g)(2) = ynl. Then, Vxe E H()))) fx(')) Yn. with (n) defined as in Eq. 2
o 1 = (T(-1)(a)) and k = 2.
2
Proof. Based on the definition of the base certificate interface, we need to show that, Val H fa(x') yn with
D
x
E
K
Dmn
| - 1 ( (q))2
(20)
Eiras et al. 12021) have shown that under the same conditions as above, but with a general covariance matrix Σ E R4 Pm Di prediction yn is certifiably robust to perturbed input æ' if
1 ④ (g) - (q')).
(x tu-xx)E' 1x x')
(21)
where g' maX #y. Prz~N(m E) (x) = v/l is the probability the second most likely pre- diction under the smoothing distribution. Because the probabilities of all possible predictions have to sum up to 1, we have g' < q. Since t is monotonically increasing, we can obtain a lower bound the r.h.s. of Fq. 21 and thus more pessimistic certificate by substituting q
16

---

Under review as a conference paper at ICLR 2022
for q' (deriving such "binary certificate" from a "multiclass certificate" is common in randomized smoothing and was already discussed in (Cohen et al. 2019))
- x')
-
(a) 2 21 q))
(22)
In our case, is diagonal matrix diag (o)² with o IR Pio. Thus Eq. 22 is equivalent
Din
1
a rtd) { (aa -z'))
2 ( (4) ② (1--))) -))
(23)
Finally, using the fact that + -0((1) - that we are certifiably robust if
- 1-1 - 1) 2Φ 24) and eliminating the square root shows
(4)
Fd z'd?² ① (g))
(24)
02 d=1 d
B.1.1 UNIFORM SMOOTHING FOR 4 PERTURBATIONS OF CONTINUOUS DATA
An alternative base certificate for I perturbations is again due to Eiras et al. (021)) Using uniform
instead of Gaussian noise later allows us to collective certify robustness to I --norm----- bound perturba- tions. In the following (ax, X) with E TR_ X E R._ refers to vector-valued random distribution in which the d-th element is uniformly distributed [ad- - da za + Ad].
Proposition Given an output 9n. ... -> Y, let (ax) argmax yEY Prz=e((0.)) (g(z) = v] be the corresponding smoothed classifier with À E Pin.. Given input E Pi and smoothed prediction y f(x), let p (()) (g(z) v). Then, Va HH()) fn(x') Yn with H()
defined as in Eq. wa- 1/>a. 7 4 (g) and
Proof. Based on the definition of ("),, we need to prove that Va E H: fn(x')
yn with
Din
x' E I Din
Σ
d'dl x 10
(25)
d=1
Eiras et al. (2021) have shown that under the same conditions as above, a prediction yn is certifiably robust perturbed input x' if
D Σ Ad
(xa - (xa-2'))
< (b (g) - 1 (-1 9))
(26)
where g' maxy s.y. P [9, vol is the probability of the second most likely predic-
tion under the smoothing distribution. As our previous proof for Gaussian smoothing, we can ob- tain more pessimistic certificate by substituting 1 1-g for o'. Since (q) -0-(11110) 9) 2 1ab--(g)) (g)
and all da are non-ne non-negative, we know that our prediction is certifiably robust if
Σ d=1
Ix I'dl x (p).
(27)
B.2 VARIANCE SMOOTHING
We propose variance smoothing base certificate for binary data. Variance smoothing certifies predictions based on the mean and variance of the softmax score associated with a predicted label. It is in principle applicable arbitrary data types. We focus discrete data, but all results can
17

---

Under review as a conference paper at ICLR 2022
be generalized from discrete to continuous data by replacing any sum probability mass fune- tions with integrals over probability density functions. We first derive a general form of variance smoothing before discussing certificates for binary data in Section B.2.1 and [Section B.2.2]
Variance smoothing assumes that we make predictions by randomly smoothing a base model's soft- max scores. That is, given base model g : X -> |r] mapping from an arbitrary discrete input space X to scores from the \ dimmensiooall probability simplex AIii we define the smoothed classifier f(x: argmaxyer?Pxx.uu by æz e.g a Normal distribution with mean a.. The smoothed classifier does not return the most likely prediction, but the prediction associated with the highest expected softmax score.
[g(=))) Here, (zz) is an arbitrary distribution over X parameterized
Given an input æ E X. smoothed prediction y = f(x) and a perturbed input x' E Xx we want to By definition of our smoothed classifier, we know that f(xx) if y is the label with the highest expected softmax score. In particular, we know that [(x=' = y if y softmax score is larger than all other softmax scores combined, i.c.
determine whether (x²)
Egw((ar) [9(x)y] > 0.5 = f(x') =
(28)
Computing (gr) [g(2), y] exactly is usually not tractable especially if we later want to evaluate robustness many x' from whole perturbation model B C X. Therefore, we compute lower bound on (x=))(()) [g)))]] [ If even this lower bound is larger than 0.5, we know that prediction certainly robust. For this, we define a set of functions HH with By IH and compute the minimum softmax score across all functions from Hi:
min Ez~(((a) [h(=)] 0.5 f(x') = y. REB
For our variance smoothing approach, we define H. be the set of all functions that have larger or equal expected value and smaller or equal variance, compared to our base model g applied to unperturbed input œ. Let μ (z)((=) [g(2)g] be the expected softmax score of our base model
g for label y. Let d² = Ez-a(a) [o(2), - =v)² be the expected squared distance of the softmax yields the variance of the softmax score. An arbitrary v is only needed for technical reasons related to Monte Carlo estimation [Section C.2 Then, we define
score from scalar R. (Choosing
H = { h X R (g-w(a) [h(z)] 2 P A ( [1b(2) -> s
(30)
Clearly, by the definition of 1s and o², we have By E H.. Note that we do not restrict functions from HI to the domain [0, 1]. but allow arbitrary real-valued outputs.
By evaluating [q. 28 with HI defined as in Eq. 29 we can determine if our prediciton is robust. To compute the optimal value, we need the following two Lemmata:
Lemma 1. Given a discrete set X. and the set II of all probability mass functions over X, any two probability mass functions 1,, T2 II fulfill
T2(2)
Σ #EX
12 (2)2) 2 1. (2)2
(31)
Proof. For a fixed probability mass function Ii. Eq. 31 is lower-bounded by the minimal expected likelihood ratio that can be achieved by another ((2) II:
T2
#(2)
T2(2)
min FETI
7(z).
(32)
क (=)
REX
SEX
The r.h.s. term can be expressed as the constrained optimization problem
#(=)
min
s.t.
Σ [+) =
(33)
=EX
with the corresponding dual problem
7(2) (1)2)
max min XER R
Σ
7(2)
+
-1 Σ #(2)
(34)
SEX
ZEX
18

---

Under review as a conference paper at ICLR 2022
The inner problem is convex in each #22). Taking the gradient w.r.t. to #(2) for all X shows that it has its minimum at Va X (2)) A=)(=) Substituting into Eq. results in
Ao (2)
A -1
(35)
AER
(2)(2)
SEX
x1(2)
max
12
(36)
XER
#EX
A2
max AER
- X
(37)
4
1.
(38)
Eq. 37 follows from the fact that TT (2) is a valid probability mass function. Due to duality, the
optimal dual value 1 is lower bound on the optimal value of our primal problem Fq. 31
L
Lemma 2. Given probability distribution D over R and scalar E R. let μ ENND and
{ = L=EEDD (z-1)² Then & 2 22=
Proof. Using the definitions of μ and as well as some simple algebra, can show:
2 (1 v)²
(39)
ExND
(z - w)²
2 1² 2pv + v2
(40)
B 222 22v + v²1
2 1²2 2p + v²
(41)
B [22 2zv v
2 p² 2p v2
(42)
REDD
[22] 2 + 2² 2 , 2 + u²
(43)
ExnD [2-] 2 μي²
(44)
is well known for the variance that ED [(2 - n EEDD [3?] - 1.2. Because the variance
always non-negative, the above inequality holds.
show the soundness of the following Using the previously described approach and lemmata, robustness certificate:
Theorem 3. Given a model g X - Aai mapping from discrete set X to scores from the dimeenssiol probability simplex, let f(x) = argmax [g(z)g] be the corre- sponding smoothed classifier with smoothing distribution (x(x)) and probability mass function Ta (2) Przww(()) [ z). Given an input X and smoothed prediction y f(x). let
a Ex-((a) [9(2)y) and o² Ezw((a) ((o()), - u)²] with u R. 1f S ps we know that f(x'= yf
Tee (2)2
<1 σ2 (n w)² H (M-2) 1-2))
(n-1)
(45)
ZEX (z)
Proof. Following our discussion above, know that f(x') y Eg.. [9(2)y] > 0.5 with H
defined as in Section 5) We can compute (tight) lower bound on minker E (x)((()))) by following the functional optimization approach for randomized smoothing proposed by Zhang et (2020). That is, we solve a dual problem in which we optimize the value h(z) for each E X. By the
definition of the set HI, our optimization problem is
min E [A(2)] h:*-R
s.t. EZwe(z) [h(x)] 2 ,4 Ez)(()) (h(z) ~v² 5
19

---

Under review as a conference paper at ICLR 2022
The corresponding dual problem with dual variables a, B 2 0 is
max min ( [1(z)]
(46)
+o (1i (x))
[b(=)] 3 (x)))())
(M(z) w) - -02)
We first move move terms that don't involve out of the inner optimization problem:
max of 20p-BB²= + min (xx)(()) [b(=) al (M(=)) (B a,820
[1((2) w}² (47)
IxX-R
Writing out the expectation terms and combining them into one sum (or in the case of continuous one integral), our dual problem becomes
max Cep - 30² + min 0,920
((z) N:X -.
Σ #EX
BB - -V)² (=)))
(48)
(recall that To' and Twx refer the probability mass functions of the smoothing distributions). The inner optimization problem can be solved by finding the optimal h(z) in each point x:
ap 30² + Σ min (z)))==()) ah(z)== + 3 (h(z) v)² (z)
(49)
a,920
h(z)ER
Because 3 2 O, each inner optimization problem is convex in l(2). We can thus find the optimal h" (z) by setting the derivative to zero:
d
dh(z) (( (z) - (a(())=x(22) + + - v)² Tez (2) 1
(50)
- Tar (z) ar (2) + 2,3 (1(2) - v) (z) 1 0
(51)
(z)
(²)2))) 2 (z)
+ 2 +
(52)
Substituting into Eq. 48 and simplifying leaves us with the dual problem
a²
Tx (2)
max aj 30 0,320
ou +
(53)
43
23
43
#EX Ta (2)
In the following, us use p p= Σzex (=) (x) as a shorthand for the expected likelihood ratio. The
problem is concave in a. We can thus find the optimum a by setting the derivative to zero, which
gives a* 2B v) 1. Because 3 and ou theorem assumes that I μ4, a" is feasible solution to the dual problem. Substituting into Eq. 53 and simplifying results in
a2
max O' μ - 30 820
+
(54)
4,3
23
4.
max 3 ((n w)² 820
o²
43 (1 p).
(55)
Lemma I shows that the expected likelihood ratio is always greater than or equal to 1. Lemma 2
shows that (p 10--)) 2/)2 0² < 0. Therefore Eq. 55 is concave in 3. The optimal value of 3 can again
be found by setting the derivative to zero:
1-p p
8"
(56)
V ((1 u)2 σ2)
Recall that our theorem assumes o² 2 (μ 2)² and thus 8r is real valued. Substituting into Eq. 56 shows that the maximum of our dual problem is
(1 p) ((n u)2 02).
(57)
20

---

Under review as a conference paper at ICLR 2022
By duality, this is lower bound on primal problem mingen (z)w(ar) [h(2)]. We know that our
prediction is certifiably robust, i.e. f(x) y, if minsen Rew)(()) [h[ 2)] > 0.5. So, in particular, our prediction robust if
p v (1 p) ((u v)² - -02) > 0.5
(58)
1
2
x+
=
(59)
x² (1 - w)²
2
Tax (z)2
1
<1 -² v)
/
(60)
2
#EX
The last equivalence the result of inserting the definition of the expected likelihood ratio p.
With Theorem 3 in place, we can certify robustness for arbitrary smoothing distributions, assuming working with discrete data and the
compute the expected likelihood ratio. When smoothing distributions factorize (but are not necessarily i.i.d), this can be done efficiently, as the two following base certificates for binary data demonstrate.
B.2.1 BERNOULLI VARIANCE SMOOTHING FOR PERTURBATIONS OF BINARY DATA
We begin by proving the base certificate presented Section 5 Recall that we we use smoothing distribution F(x, 0) with 0 E [0, Pin that independently flips the d'th bit with probability 0.- Le. for x, 2 E {0, 1] Pin and z ~ F(x, 0) we have Pr[za * xa] = 0g.
Theorem 1. Given an output In : {0, 1) Pmn - App mapping to scores from the [Y-ddmmesioonal probability simplex, let fx) ye EE (=) be the corresponding smoothed
classifier with E [0,,) Given an input æ E {0, 1] and smoothed prediction yn = =fn(x),
let μ = (gnF(1,0) (z)g and o² Var VargxF((a.0) [9n (z)gl Then, Voe E [H(()) :In(x') = Un
with (H) defined as in Eq. 2 wa- = Inn (1-0,)² (0n)²
I-02 In (1 11++((1 (1= ))² and K = O.
Proof. Based definition of the base certificate interface from Section Va' E Hi: : fn(x') = Un with
we must show that
H o Ph Piu
Σ In
Dmn
02)
(0a)
1 0² 13//2 xzl < In (1+
1
0a
0₂
(61)
Because all bits are flipped independently, our probability mass function (z) = Prin((a))
[
=
factorizes:
Dim
Ta (2) =
II d=
nu, (zd)
(62)
with
O0
if za & xd else
Tza (2a) =
(63)
11 Oa
Thus, expected likelihood ratio be written
Ta (z)
Din
(zd)
D
Tay (za)²
(64)
Tae #E Piu d=1 Tza (za)
Tza (zz)
(0.1) Pmn
d=1
For each dimension d, we can distinguish two cases: both the perturbed and unperturbed input are T=4 (z)
the same in dimension d, i.e. x'4 Fdd then Nzz
1 and thus
Tz (2a)
Σ
Tz; (2x) = Oa + (1 04) = 1.
(65)
Tzg (2d)
E (0.1)
(0.1)
21

---

Under review as a conference paper at ICLR 2022
If the perturbed and unperturbed input differ in dimension d, then
Ta's (zd)²
(1 - -Aa)² (1-
(0a)
Σ
+ 1 0d
(66)
Tue (2d)
da
(0.1)
Therefore, the expected likelihood ratio is
Din II
Txt (za)
Din
(1 11-0k 0a)²
(0a)²
12/ 1aga
Σ
II
+
(67)
Txa
(za)
0a
0s
d=1 (0..)
d=1
Due to Theorem 3 (and using l when computing the variance), we know that our prediction is
robust, l.e. [n'(') = Un. if
Tex (z)2
1
1 + σ²
1
(68)
Tu Tn (z)
(0,1)) Pio
1 zal
(1 - 0n)
(0a) 2
1
1
+
x1+
+
(69)
0a
1- Od
x²
2
d=1
Din
(1 0z)²
(0a)²
2
+
In'a val <hn
1
11 2
1
(70)
P
0d
Because Idd and x'a are binary, the last inequality is equivalent to
(1 11-0% 0z)²
(0a)²
1
2 2)
+
100/ xz < In
[
1
2
(71)
0
1-81)
B.2.2 SPARSITY-AWARE VARIANCE SMOOTHING FOR PERTURBATIONS OF BINARY DATA
awwre randomized smoothing (Bojchevski et al. 2020) is an alternative smoothing ap- proach for binary data. It uses different probabilities for randomly deleting (1 - 0) and adding (0 + 1) bits to preserve data sparsity. For a random variable z distributed according to the sparsity aaware aware distribution S(x, 0+, .-) with æ {0, 1),1)Pm Pin and addition and deletion probabil-
ities 0+ 10 E [0, Pi we have:
Pr[za = 0] (1 (1- - 1-maa (07)
Pr(za 1] (0t) 1--1 (1 (1-07) 07) 32
The Bernoulli smoothing distribution we discussed in the previous section is special case of sparsity-aware smoothing with 0+ = 0- The runtime of the robustness certificate derived by Bojchevski et al. (2020) increases exponentially with the number of unique values in A+ and A-, which makes it unsuitable for localized smoothing. Variance smoothing, on the other hand, allows us to efficiently compute a certificate in closed form.
Theorem 2. Given an output 9n : .R.. Pin Amr mapping to scores from the dildimnnni prob- .0-) [gn(2)), be the corresponding smoothed classifier with 0+ O =[0,1]Pu, Given an input x Pm and smoothed prediction On = fn(x), let = EznS(n, . [g)(2)y] and x² = Varr=SSte00. o [gn(z)y). Then,
ability simplex, let fn(
dw'' E HI: fa(x') forrr
D Σ 1=1
H = x' E {0.
Vd 1[20 = a x'd + + [ = 1 + x'd] <n {m)
(72)
(07)²
(1-07)²)
( 7a = In (1-02)²
05 + (0))²
where , E Pi,,, gt =
1-0t +
and =
0f
07
In [ 1 σ- (n- ))²
22

---

Under review as a conference paper at ICLR 2022
Proof. Just like with the Bernoulli distribution discussed in the previous section, all bits flipped independently, meaning our probability mass function Tee Tz (re) 22 = 2] factor- izes:
Din
Tn (2)
Toy (2d)
(73)
d=1
with
0d
if zd + Itd
Txy (za)
(74)
1
Oa
else
As before, our expected likelihood ratio can be written as
(z)²
Te (2d) Il
Tet (2d)
(75)
(2d)
Tzz (2d)
(0,1) Pin
=E(0,)) Pin d=1
d=1 (0.1)
We can now distinguish three cases. dimension d, i.e. x'a Fd, then *, (z)
If both the perturbed and unperturbed input are the same in
and thus
xxy(=)
Ta (za)²
Σ 1dE(0,1)
(rg(2d) = 1.
(76)
Taa (2d)
#2E(0,1)
If 2' = and Zd i.e. a bit was added, then
(2)
(za) (0)2
(1)2
(07)
(1 0₂)
E
+
(77)
Tay (z)
To(Za) (0) x1(
1 - 0
0
(0.1)
10
If 2 0 and Fdd i.e. bit deleted, then
Ted (2)
To(2d)2 (0) mo(1)
0t)² (1-0))²
(1 (1-
(07)²
(78)
Tz,(2) (0E(
T1 (2()
(0)
T (1)
0
1 0
:2E(0,13
Therefore, the expected likelihood ratio is
Dmn II
Trl (zd)2
(79)
Tx (2d)
d=1 (0.1)
1/ 1
[[
Din
(07)
(1 07)
(1 (1-03) )
(ot)²
+
+
(80)
1 0+
0
0
1 0J
Din
exp (xt (x 1 exp (1z) 1/ (12)(1b 1
(81)
In the last equation, we have simple used the shorthands 7i and V as defined in Theorem 2 Due
to Theorem 3) (and using v = a when computing the variance), we know that our prediction is robust, i.e. (xx) Un. if
Tha (z)²
+ G2
(82)
(2)
2
(0 Pm
D II d=1
exp (1t) [aa=0+tu'll
exp (7/ 1 |
1
2
< +
<
(83)
g²
2
D
1 2
[ = 0 + x'2l vo
I[xa = 1 2'al < in
|+ g²
#
(84)
2
23

---

Under review as a conference paper at ICLR 2022
It should be noted that this certificate does not comply with our interface for base certificates Seec- [i meaning we can not directly use it to certify robustness to norm- norm-bound perturbations using our collective linear program from PromSSection 6 We can however use it certify collective robustness to the more refined threat model used in (Schuchardr et al. 2021): Let the set of admissible perturbed in-
[za 1 + z'all S E with puts be B_ x' E P Elm [ = 0 + r'Ill S et Edm
e".c" No specifying the number of bits the adversary is allowed to add or delete. We can now follow the procedure outlined in [Section 6) to combine the per- per-prediction base certificates into collective certificate for our new collective perturbation model. As discussed in, we can bound the number of predictions that are robust simultaneous attacks by minimizing the number of predic- tions that are certifiably robust according to their base certificates:
ET(n((a'> = ynl 2 min Et(s'e [a'emm]] x C'EBa
min 2' EB
(85)
NET
nET
Inserting the linear inequalities characterizing our perturbation model and base certificates results in:
Din Σ
min wr (0,1)
Σ 1
V - [ = + x'2l + + 1[xa = # x'sl < (m)
(86)
Pin
nET
1d=1
s.t.
Σ
|=a=
r'dll S
Σ l=a= = z'2ll SE.
(87)
Instead of optimizing over the perturbed input æ', we can define two vectors b+ b- E f0. 1) D.. that indicate in which dimension bits were added or deleted. Using these new variables, Eq. 86 can be rewritten as
E1(( 6+ + (r-)² < mn)
min 10.1)) Piu
(88)
NET
s.t. sum sct,
ss,
(89)
b
0,
b
(90)
d=
d|
The last two constraints ensure that bits can only be deleted where za = and bits can only be added where za O. Finally, we use the procedure for replacing the indicator functions with
indicator variables that we discussed in Section 6). Let 17(") be the minimum values the weighted sums in the objective function can take on.
n (n)
min bt b _
(r+) b+ + (xr)
(91)
s.t. sum s sct,
sum 5b
(92)
b
b==0.
(93)
4
d=r,=0
The above problem can be solved by finding all negative entries of y and T and then summing up the min (sum (1 æ} bt) (or min (sum {x) br), respectively) smallest ones. Using these r7(*)
and binary indicator variables t {0, Dour, we can restate the above problem as the mixed-integer problem
min (0,,1 (0,,1) Pout Paut
Σ tm
(94)
NET
s.t. (r+)² b+ + (r (7-)²²
)²6 b 2 tn7 (n) + (1 - tx (m)
(95)
sum (b+ } Ett, sum SE
(96)
Σ =
(97)
4|===1
d|mx=0
The first constraint ensures that t, can only be set to 0 if the Lh.ss is greater equal na. i.e. only when the base certificate can no longer guarantee robustness. The efficiency of the certificate can be improved by applying any of the techniques discussed in Section A
24

---

Under review as a conference paper at ICLR 2022
C MONTE CARLO RANDOMIZED SMOOTHING
To make predictions and certify robustness, randomized smoothing requires computing certain prop- erties of the distribution of a base model's output, given an input smoothing distribution. For example, the certificate of Cohen et al. (019) assumes that the smoothed model f predicts the most likely label output by base model g. given a smoothing distribution (NO, a 1): f(x) = argmaxyev (00.N((0.-11 (g(2 2) - yl- To certify the robustness of a smoothed prediction y f() for specific input x, we have compute the probability y = Pr [g(a: =) y) to then calculate the maximum certifiable radius o with standard-norma inverse CDF $ 11 For complicated models like deep neural networks, computing such properties in closed form is usually not tractable. Instead, they have be estimated using Monte Carlo sampling. The result are predictions and certificates that only hold with a certain probability.
Randomized smoothing with Monte Carlo sampling usually consists of three distinct steps. First, a small number of samples N1 from the smoothing distribution are used to generate candidate prediction ÿ. e-g. the most frequently predicted class. Then, a second round of N₂ samples taken and a statistical test is used to determine whether the candidate prediction is likely to be the actual prediction of smoothed classifier f. i.e. whether ú = f(x) with a certain probability (1 a.). If this is not the case, one has to abstain from making prediction (or generate a new candidate prediction). To certify the robustness of prediction 9. a final round of N₃ samples is taken to estimate all quantities needed for the certificate. In the case of (Cohen et al. (201)), we need to estimate the probability Pr [9(x ( + z) = ú] to compute the certificate oΦ- (4). whose strength is monotonically increasing in q. To ensure that the certificate holds with high probability (1 -1-6 a22), we have compute probabilistic lower bound q S q. If one wants to certify robustness for all predictions, as we do in our experiments, one can also use the same samples for the abstention test and the certificates. One particularly simple abstention mechanism is to just compute the Monte Carlo randomized smoothing certificate to determine whether Va' E {œ)} [(x') = y with high probability, i.e. whether the prediction is robust to input x' that is the result of "perturbing" clean input æ with zero adversarial budget.
In the following, we discuss how we perform Monte Carlo randomized smoothing for our base certificates, as well as the baselines we use for our experimental evaluation. In Section C.4, we discuss how we account for the multiple comparisons problem, i.e. the fact that we are not just trying to probabilistically certify a single prediction, but multiple predictions at once.
C.I MONTE CARLO BASE CERTIFICATES FOR CONTINUOUS DATA
For our base certificates for continuous data, we follow the approach we already discussed in the previous paragraphs (recall that the certificate of Cohen et al. (2019) is a special case of our cer- tificate with Gaussian noise for la perturbations). We are given an input space Din,, label space Y, base model (or in the case of multi-output classifiers base model output) g D -> Y and smoothing distribution (x)) (either multivariate Gaussian or multivariate uniform). To gen- erate a candidate prediction, we apply the base classifier to N, samples from the smoothing distribution in order to obtain predictions
".......(M). and compute the majority prediction i = argmaxyev {n (n)) = .}. Recall that for Gaussian and uniform noise, our certificate guar-
antees Va' e H:: f(z)= = 9 with
D Σ
H = x' E Dm
wa In'a xal
with 77 (Φ- (g))
= (g) (depending on the distribution),
PIz~~N(0.011) [g(æ z) = o] and standard-normal inverse CDF Φ-1 To obtain a probabilistic cer- tificate that holds with high probability 1 - a, we need a probabilistic lower bound on 77. Both 17 are monotonically increasing in q. i.c. can bound them by finding lower bound take N₂ more samples from the smoothing distribution and compute a Clopper-Peanee Pearson lower con- fidence bound (Clopper & Pearson 1934) on g. For abstentions, we use the aforementioned simple
q. For this,
25

---

Under review as a conference paper at ICLR 2022
mechanism: We test whether H.. Given the definition of HI, this is equivalent testing whether
Φ (
(0)
0.5
If q S 0.5, we abstain.
C.2 MONTE CARLO VARIANCE SMOOTHING
In variance smoothing, we smooth a model's softmax scores. That is, we are given an input space D label space Y, base model (or in the case of multi-output classifiers base model output) g: P + A |yl with dimmennni probability simplex Arr and smoothing distribution (x) (Bernoullii or sparsity-awarr noise, in case of binary data). To generate a candidate prediction, we apply the base classifier to Ni samples from the smoothing distribution in order to obtain vectors (s(1) (e"),...,,ssN... with Amp compute the average softmax scores the label with the highest score ÿ = arg max, Sy.
Ni Σ and select
Recall that our certificate guarantees robustness if the optimal value the following optimization problem is greater than 0.5:
min Ez-V(-)) [h(z)] A-
(98)
s.t. E2)((() [1(=)] 2 (m~ [h(z) -v² -h( S
(99)
(a(z); - u) and a fixed scalar v E To obtain probabilistic certificate, have compute a probabilistic lower bound the optimal value of the optimization problem. Because it is minimization problem, this can be achieved by loosening its constraints, i.e. computing a probabilistic lower bound on and a probabilistic upper bound ō on o².
with μ = -g>((()) [g(2)g). o² = Eg>((a)
Like in CDF-smoothing (Kumar et al. 2020p, we bound the parameters using CDF-based nonpara- metric confidence intervals. Let F()) Przw)(() [Ø()) S s] be the CDF of the distribution of gy
under the smoothing distribution 인 (zx). Define M thresholds < 0ri < ..... TM-1 S TM S with Vm Tm E [0, 1J. We then take N2 samples ('))...... (N2) from the smoothing distribution
to compute the empirical CDF (s) N I [g(((())) I s]. We can then use the Dvoretzky-
Keifer Wolfowitz inequality Dvoretzkyy et al. 1956) to compute an upper bound F and a lower bound F on the CDF of ggi
F()) = max (f(s)- s F(8) S min (f())+ + v.
F()),
(100)
with V = 1n2/a N: which holds with high probability (1 a1) Using these bounds on the CDF, we
can bound μ V()) [0(=)g] as follows (Anderson 1969):
M-1
# #2 TM F(T) +
(Tm+1 Tm) F(Tm).
(101)
m=1
The parameter o² (x) (0(2) w}a
can be bounded in similar fashion. Define
Eu...., EM E R4 with:
Eo max (1)))
kE(U,T]]
EM max
- ((15- (1=)))2)
((15
(102)
xE[Tx]]]
Sm = max
((ss - (()=))?)
Vm (1...., - 1),
+1]
26

---

Under review as a conference paper at ICLR 2022
Le. compute the maximum squared distance to v within each bin [Tme Fm+1]. Then:
M
a² S (TF((T) + (1 F(TM))
Em (F(Tm+1 (T(m))
(103)
= fM +
(5m-1 - Em) F((m)
(104)
m=1
M-1
SM +
Σ
sgn (5m-1 - Sm) F(Tm) + +(1))++1111111111 sgn (5m-1 -mm) F(Tm)
(105)
m=1
with probability (1 a). In the first inequality, we bound the expected squared distance from v by assuming that the probability mass in each bin [Tm. Tm+11 is concentrated the farthest point from p. The equality is result of reordering the telescope sum. In the second inequality, we upper-bound the CDF where it is multiplied with non-negative value and lower-bound it where is multiplied with negative value.
With the probabilistic bounds and o² we can now in principle evaluate our robustness certifi- cate, i.e. check whether
T Tx
< c
(106)
σ² (1+ v)
2
#EX
where the и are the probability mass functions of smoothing distributions (xx) and (xx'.. But one crucial detail Theorem 3lnnderyying the certificate was that only holds for v S μ,, i.e. only when this condition is fulfilled can compute the certificate in closed form by solving the corresponding dual problem. To use the method with Monte Carlo sampling, one has to ensure that v S 4 by first computing μl and then choosing
smaller v.
In our experiments, we use an alternative method that allows us to use arbitrary vs From our proof of Theorem 3ive know that the dual problem of Eq. 98 is
a²
1
Mer (2)
ay
30
+
(107)
0,920
43
23
48
Tu (z)
Instead of trying to find an optimal a (which causes problems in subsequent derivations v L μ)), we can simply choose = 1. By duality, the result is still lower bound on the primal problem, ie. the certificate remains valid. The dual problem becomes
Ta (z)2
max - 30 #20
(108)
43
43
TTe (z)
ZEX
The problem is concave in (because the expected likelihood ratio is 2 1). Finding the optimal 8, comparing the result to 0.5 and solving for the expected likelihood ratio, shows that prediction is robust if
Tan (z)2 Σ #EX
2
σ² 1
(109)
(2)
2
For our abstention mechanism, like in the previous section, we compute the certificate HH and then test whether æ E H. In the case of Bernoulli smoothing and sparsity-aware smoothing). this corre- sponds to testing whether
# --2) ))
<< In
1+
(110)
1>
(111)
C.3 MONTE CARLO CENTER SMOOTHING
While not center smoothing base certificate, benchmark our method against it during our experimental evaluation. The generation of candidate predictions, the abstention mech- anism and the certificate are explained in (Kumar & Goldstein 2021). The authors allow multiple
27

---

Under review as a conference paper at ICLR 2022
options for generating candidate predictions. We use the "3 minimum enclosing ball" with / that is based on pair- pair-wise distance calculations.
C.4 MULTIPLE COMPARISONS PROBLEM
The first step of our collective certificate is to compute one base certificate for each of the Dout predictions of the multi-output classifier. With Monte Carlo randomized smoothing, we want all of these probabilistic certificates simultaneously hold with high probability (1 a). But as the number of certificates increases, so does the probability of at least one of them being invalid. To account for this maltiple comparisons problem, use Bonferroni (Bonferroni 1936) correction, i.c. compute each Monte Carlo certificate such that it holds with probability (1 )
For base certificates that only depend on Gn Prg--p(n) [gn(2) = 9n). i.e. the probability of the base classifier predicting a particular label Un under the smoothing distribution, one can also use the strictly better Holm correction (Holm 1979). This includes our Gaussian and uniform smoothing certificates for continuous data. Holm correction is a procedure than can be used to correct for the multiple comparisons problem when performing multiple arbitrary hypothesis tests. Given N hypotheses, their p-values are ordered in ascending order pI,-...PM. PN. Starting at i 1, the i'th hypothesis is rejected if p. < N+ii3. until one reaches an such that p. 2 N
Fischer et al. 2021) proposed use Holm correction as part of their procedure for certifying that all (non-abstaiming) predictions of an image segmentation model are robust to adversarial perturbations. In the following, we first summarize their approach and then discuss how Holm correction can be used for certifying our notion of collective robustness, i.e. certifying the number of robust predic- tions. As in /ecciion C.T the goal is to obtain a lower bound U, on In Pr pnoppi
(2) = [n) for
each of the Dom classifier outputs. Assume take N2 samples (1) distribution. Let V2 = Σ (z)) = Un] and let : {I...., Dout + bijection that orders the Vn in descending order, i.c. V=(1) 2 Px(2) -.. 2 (T(D Instead of using Clopper-Pearsee Pearson confidence intervals to obtain tight lower bounds on the On. Fischer et al. (2021) define a threshold E [0.5, 1) and use Binomial tests to determine for which n the bound I In holds with high-probability.. Let BinP (Un, N2, S, be the p-value of the one-sided binomial test, which is monotonically decreasing in Un. Following the Holm correction scheme, the authors test whether
(Na) from the smoothing
Dout } be
BinP (Mx(K): N2, S,T) Dont +1-k
(112)
for k 1. l..... Dout until reaching k- for which the null-hypothesis can no longer be rejected, iec the p-value is g.e.q. D They then know that with probability 1 - a, the bound T S 4n holds for all E {<(k) E (l,...,
.....,,' k*) }. For these outputs, they use the lower bound to compute robustness certificates. They abstain with all other outputs.
This approach is sensible when one is concerned with the least robust prediction from set of predictions. But our collective certificate benefits from having tight robustness guarantees for each of the individual predictions. Holm correction can be used with arbitrary hypothesis tests. For instance, we can use a different threshold Tn per output Ja. i.e. test whether
BinP (V*()), N2, S, Tpp(k)) < Dout + 1
(113)
for l: = 1,.... Dout- In particular, we can use
Fn sup s.t. BinP (Vn, N2. S.t Dout + +1- π (n)
a
(114)
t
i.e. choose the largest threshold such that the null hypothesis can still be rejected. Eq. 114 is the
a lower Stopper-Pearson confidence bound with significance +1a++1-7 [[n]- This means that, instead
of performing hypothesis tests, we can obtain probabilistic lower bounds 9 < Qn by computing a
4 Clopper- Pooper-PParson confidence bounds with significance parameters Dant ....: T The g,, can then be
used to compute the hase certificates. Due to the definition of the Tu, all of the null hypotheses are rejected, i.e. we obtain valid probabilistic lower bounds on all In- We thus use the abstention mechanism from Section C.I i.c. only abstain if q,- < 0.5.
A direct consequence of the results above is that using Clopper- Clopper-Pearson Pearson confidence intervals and Holm correction will yield stronger per-prediction robustness guarantees and lower abstention rates
28

---

Under review as a conference paper at ICLR 2022
than the method of Fischer et al. (2021). The Hopper-Pearsonn-ere method only abstains if one cannot guarantee that In > 0.5 with high probability, while their method abstains if one cannot guarantee that dr 2 with 7 2 0.5 (or specific other predictions abstain). For all non-abstaining predictions, the single threshold т, as it computes the tightest bound for which the null hypothesis can still be rejected (see [g. 114). Consequently, a naive collective robustness certificate (i.e. counting the number of predictions whose robustness are guaranteed by the base certificates) based on Clopper- Pearson bounds will also be stronger. It should however be noted that this is only relevant for our notion of collective robustness, not for the one considered by Fischer al. (202T). should also be noted that their method could potentially be used with other methods of family-wise error rate correction, although they state that "these methods do not scale to realistic segmentation problems" and do not discuss any further details.
certificate will be at least as strong as that obtained using
Our above discussion shows that, for our notion of collective robustness, the naïve collective cer- tificate using Clopper-Pearson confidence bounds and Holm correction is at least strong that of Fischer et al. (20TT) (or alternatively: the certificate Fischer et al. (202T) is a naive collective certificate with Holm correction, but with weaker per-preeeeee per-prediction certificates). Conversely, the certifi- cate based on Clopper-Pearson confidence bounds at least as strong as that Fischer et al. (2021) when certifying their notion of collective robustness, i.e. determining whether all non-abstaining predictions are robust, given adversarial budget e. To certify this notion of robustness, they simply iterate over all predictions and determine whether all non-abstaining predictions are certifiably ro- bust, given Naturally, as the Clopper-Pearye Pww.-earrsonaaaee based certificates are stronger, any prediction that robust according to (Fischer et al. 202T) is also robust acccording the Clopper-Pearson Sooper-Pearson-basee based certificates. The only difference is that, for r > 0.5, their method will have more abstaining predic- tions. But, due the direct correspondence of (lopper-Pearsee tests, we can modify our abstention mechanism to obtain exactly the same set of abstaining pre- dictions: We simply have to use I, S T instead of qn. S 0.5 as our abstention criterion. Finally, should be noted that the proposed collective certificate tificate (see Seccton 4). Thus, letting the set of targeted predictions T be the set of all non-abstaining predictions and checking whether the collective certificate guarantees robustness for all of T will also result in certificate that is at least as strong that of Fischer et al. (202T) in their setting.
confidence bounds and Binomial
least as strong as the naïve collective cer-
In our experiments (see Section 8). we use Holm correction for our naive collective certificate and the weaker Bonferroni correction for base certificates. This is only meant to slightly skew the results in favor of our baselines. Holm correction can in principle also be used when computing the base certificates, in order improve our proposed collective cert.
29

---

Under review as a conference paper at ICLR 2022
D COMPARISON TO THE COLLECTIVE CERTIFICATE OF SCHUCHARDT ET AL.
In the following, we first present the collective certificate for binary graph-structured data proposed
by bySSchuchardt et al. (202 1) (see Section D.1 We then show that, when using sparsity-aware smooth- ing distributions (Bojchevski et al. (0200 the family of smoothing distributions used both in our
work and that of [Schuchardt et al. 2021) our certificate subsumes their certificate. That is, our
collective robustness certificate based on localized randomized smoothing can provide the same
robustness guarantees (see Section D.2).
D.1 THE COLLECTIVE CERTIFICATE
Their certificate assumes the input space to be G = {0, 1] x {0, 1] - -the set of undirected attributed graphs with N nodes and D attributes per node. The model is assumed be multi- output classifier f G - Y that assigns label from label set Y to each of the nodes. Given an input graph G (X,, A) and a corresponding prediction y = f(G). they want certify collective robustness to a set of perturbed graphs IB C G. The perturbation model B is characterized by four scalar parameters rx: '' rtt r Ng. specifying the number of bits the adversary is allowed to add (0 + 1) and delete (1 + Ó) in the attribute and adjacency matrix, respectively. It can also be extended to feature additional constraints (e.g. per-node budgets). We discuss how these can be integrated after showing main result. A formal definition of the perturbation model can be found in Section B of (Schuchardt et al. 2021).
NN. The goal of their work is to certify collective robustness for set of targeted nodes T S (L.....,NK ie. compute a lower bound on
min Σ [[[fa(G'= = ynl PET
(115)
GLEB
Their approach to obtaining this lower- shares the same high-level idea as ours: Combining per- prrppddiitionn base certificates and leveraging some notion of locality. But while our method uses localized randomized smoothing, i.e. smoothing different outputs with different non-i.i.d. smoothing distributions, to obtaín base certificates that encode locality, their method uses a-priori knowledge about the strict locality of the classifier f. A model is strictly local if each of its outputs fn only operates on a well-defined subset of the input data, To encode this strict locality, Schuchardt et al. (2021) associate each output fn with an indicator vector sbin) and an indicator matrix V m) that fulfill
N ΣΣ Σ winl [Xm, X
D ((n) [m d # Av,l =0
(116)
m=1
fa(X A) fn (X' A').
for any perturbed graph = g²= (X', Eq. 116 expresses that the prediction of output fn remains
unchanged all inputs in its receptive field remain unchanged. Conversely, it expresses that per- turbations outside the receptive field can be ignored. Unlike in our work, [Schuchardt al. (2021) describe their base certificates as sets in adversarial budget space. That is, some certification proce- dure is applied each output fn obtain set
K
(117)
A E k(n), then prediction Yn is robust to any perturbed input with exactly Cx attribute additions, C attribute deletions, o edge additions and сa edge deletions. A more detailed explanation can be found in Section 3 of (Schuchardt et al. 2021]. Note that the base certificates only depend on the number of perturbations, not their loca- tion the input. Only combining them using the receptive field indicators from Eq. 116 makes it possible to obtain a collective certificate that is better than a naive combination of the base certifi- cates (i.e. counting how many predictions are certifiably robust to the collective threat model). The
with [k] = kJ. If |o
x
30

---

Under review as a conference paper at ICLR 2022
resulting collective certificate is
7
min bt bt.b B
Σ
bx
(1bin1) " bx
Eis wh
BiA
Bid
Eis w
Big
E K(m)
EET
(118)
N
N
N
N N
S.L.
m
S xx)
bm S
xix
B S
S
Bij S S
(119)
m=1
m=1
j=1
b E Nº
B E N N
(120)
The variables defined in Eq. 120 model how the adversary allocates their adversarial budget, i.e. how many attributes are perturbed per node and which edges are modified. [Eq. 1T9 ensures that this
allocation in compliant with the collective threat model. Finally, in Eq. 118]the indicator vector and
matrix vb(() and (T(m) are used to mask out any allocated perturbation budget that falls outside the receptive field of fn. before evaluating its base certificate.
To solve the optimization problem. SShuuchard et al. (2021) replace each of the indicator functions with binary variables and include additional constraints ensure that they have value 1 i.f.f. the indicator function would have value 1. To do so, they define one linear constraint per point separating
the set of certifiable budgets K(*) from its complement (x) in adversarial budget space (the "pareto
front" discussed in Section 3 of (Schuchardt et al. 202T))
From the above explanation, the main drawbacks of this collective certificate compared to our lo- calized randomized smoothing approach and corresponding collective certificate should be clear. Firstly, the classifier f is not strictly local, i.e. the receptive field indicators up and v only have non-zero entries, then all base certificates get. It thus degenerates to the naïve collective certificate. Secondly, even if the model is strictly local, each of the output may assign varying levels of importance to different parts of its receptive field. Their method is incapable of capturing this additional soft locality. Finally, their means of evaluating the base certificates may involve evaluating a large number of linear constraints. Our method, on the other hand, only requires a single constraint per prediction. Our collective certificate can thus be more efficiently computed.
evaluated using the entire collective adversarial bud-
D.2 PROOF OF SUBSUMPTION
In the following, we show that any robustness certificate obtained by using the collective certificate Schuchardt al. (202T) with sparsity-aware randomized smoothing base certificates can also be obtained by using our proposed collective certificate with an appropriately parameterized localized smoothing distribution. The fundamental idea is that, for randomly smoothed models, completely randomizing all input dimensions outside a receptive field is equivalent to masking out any pertur- bations outside the receptive field.
First, we derive the certificate of Schuchardt et al. 2021 for predictions obtained via sparsity- aware smoothing. [Schuchardt et al. (2021) require base certificates that guarantee robustness when
[et c t ca] IK(",, where the c indicate the number of added and deleted attribute and adjacency bits. That is, the certificates must only depend on the number of perturbations, not on their location. To achieve this, all entries of the attribute matrix and all entries of the adjacency matrix, respectively, must share the same distribution. For the attribute matrix, they define sealar distribution parameters . E [0, 1]. Given attribute matrix X E {0, Nx they then sample random attribute matrices Zx that are distributed according to sparsity- smoothing distribu- tion S (x.1 px 1 px) (see Section B.2.2 i.c.
Pr((Zx) m,d = 0] = (1-x)) 1- 1-maat
(px) Xmnat
(r( m.d = = (px) 1-Xmad 1- (1 (1-18 Px)) Xmmd
Given input adjacency matrix A, random adjacency matrices Za are sampled from the distribution (A,1 1 P 1- -P)) Applying Theorem (to the flattened and concatenated attribute and adja- cency matrices) shows that smoothed prediction yo fa(X, A) is robust the perturhed graph
31

---

Under review as a conference paper at ICLR 2022
(X' if
N D
X 1 [[m.d = 0 + X.m +7x 1 [(m,d = 1 # X X'md)
M=1 1=1
N N
(121)
Σ
Σ
tt
[Ais = + Acol +2ā +2x-I[Ai, I[Ais =1 Acol
< 17
(px)
(1-px)
) and r7(x) = In (1 (1+ دايي= (n(m) 2) ))))
(1 (1-px)² In
(xx)
with
X
In
7x
+
A
1-Px
Px
Px
1-Px
(pā)² I-PÄ
)² + (1 (1-pā)²
(I-PA)*
(pt)²
In
V In
+
PA
PA
I-P7
where (.(()) is the mean and (()) is the variance of the hase classifier's output distribution, given the input smoothing distribution. Since the indicator functions for each perturbation type in Eq. 121 share the same weights, Eq. can be rewritten as
Xx* +Xx + 7
(122)
where cx. cy. C. are the overall number of added and deleted attribute and adjacency bits, respectively. Eq. 122 matches the notion of base certificates defined by (Schuchardt et al.) (2021), i.e it corresponds to a set K(n) in adversarial budget space for which we provably know that pre-
diction yn is certifiably robust if [ Cx A ca. K(n), When this base certificate is used,
i.c. we insert the base certificate Eq. into objective function Eq. 118 the collective certificate of Schuchardt et al. (202T) becomes equivalent
min B+
Σ nET
Xx (15l1))²
ox + Tx (1slnr)²
bx
b+.b
B
(n)
B + Σ
Ta
(1) Bis S (m)
(123)
i
1.
N
N bm
N
N
N
N
s.t.
b+ m
<
x X
TTX
B
B SUSTA
(124)
m=1
m=1
/=1==1
b+ EN B B*,B-ENN**
(125)
Next, we show that obtaining base certificates through localized randomized smoothing with ap- propriately chosen parameters and using these base certificates within our proposed collective cer- tificate (see (Section 6) will result in the same optimization problem. Instead of using the same smoothing distribution for all outputs, we use different distribution parameters for each one, For the
'tth output, we sample random attributes matrices from distribution S
[x,e) O x
(m) (n) with
[0. 1| Note that, in order to avoid having to index flattened vectors, we over- load the definition of sparsity-aware smoothing to allow for matrix-valued parameters. For example,
o (n) (n)
(n)
the value +* n,d indicates the probability of flipping the value of input attribute X,,dd from
(n)
and the value O xnnd indicates the probability of flipping the value of input attribute Xn.d from 1 to
0. We choose the following values for these parameters:
++ m.d = (f())
(n)
Px
(n)
0.5,
(126)
θx (m)
= (n)
Px +
(n) 0.5,
(127)
m.d
m
where 26(m) is the receptive field indicator vector defined in Eq. 116 and p p px E [0, are
the same flip probabilities used for the certificate of Schuchardt et al. (2221). Due to this
parameterization, attribute bits inside the receptive field are randomized using the same distribu- tion as in the certificate of [Shhuchrrdt et al. (202T). while attribute bits outside
either
32

---

Under review as a conference paper at ICLR 2022
O with equal probability. Similarly, sample random adjacency matrices from distribution [0, 1jNxD and
S [, 1 (n) 1 (n)) with A
(m) O (n)
θ (n)
P + (1 (p()) Aij = w
0.5,
(128)
b
(n) Au.j = (()) fJ PA + 1. 0.5,
(129)
where (p(() is the receptive field indicator matrix defined in Eq. 116, Note that, since we only alter
the distribution of bits outside the receptive field, the smoothed prediction yn = (x, A)) will be the same as the one obtained via the smoothing distribution used by (Schuchardt et al. (2021).
Applying Theorem (to the flattened and concatenated attribute and adjacency matrices) shows that smoothed prediction y/. = fn (X, A) is robust to the perturbed graph (X', A') if
N
D
Σ
Σ
x
[[Xm, = + mmm + xx T [[Xmmd = 1 # Xmma] mm,
m= d=1
N
(130)
Aiis
[Ais 0 Ab,1 +TAiS I [ 1 1
Because we only changed the distribution outside the receptive field, the scalar ry(*), which depends on the output distribution's mean and variance μ and a will be the same as the one obtained via the
smoothing scheme used by |Schuchardt et al.] (021) 1 et al. Due to Theorem 2 and the definition of
our smoothing distribution parameters in Eqs. 126 to 129). the scalars Tx m, Xmm,d' TAig' TAi.j have the following values:
(1 0.5)
0.52
X m,d = vi(())
> + (1- v.laa)
2- In
(131)
0.5
1
0.5
(1 0.5)
0.52
x m,dd
7x +
volaa)
2 In
0.5
1- 0.5
(132)
TAi = 1/ 7 (1 (1-
(1 0.5)
0.5
v
22
(133)
0.5
1- 0.5
TAi !/
- + (1 v
(n)
2 In
(1 - 0.5)
+
0.5²
(134)
0.5
1 0.5
where the 7 are the same weights as those of the base certificate Eq. 121 of Schuchardt et al.
2021.
Inserting the above values of 7 into the base certificate [iq. 130 and using the fact that
0.5)
0.52
In(1) = results in
0.6
0.5
N
Σ
Σ
(n)) 7x
1 [[Xm, = = + Xmm.a] + (pfm))
7x I[Xm, = + Xmmal
1=1
N
N
(135)
A = 0 A/,
+ V (n) i.j
7A 7.-1(A15
= 1 Ah,yl
==
While our collective certificate derived in Section 6 only considers one perturbation type, we have already discussed how to certify robustness to perturbation models where there are multiple pertur- bation types in Section B.2.2 We use different budget variable per input dimension and perturba- tion type. Furthermore, the attribute bits of each node share the same noise level. Therefore, we can the method discussed in Section A.3] i.e. a single budget variable per node instead of using
33

---

Under review as a conference paper at ICLR 2022
per node and attribute. Modelling collective problem in this way, using Eq. 135 our base certificates and rewriting the first two sums using inner products results in the optimization problem
(15(r))
I bx + +7x
(15(N))
min b
7x
bx
B
NET
+
+
Σ 1.
Va
(1) (.j
Big I n/(0))
(136)
2.3
N
N
N
N
s.t.
b+
Σ bm S r
B 1
S
(137)
b+,b E N
B B
B
N
N
(138)
This optimization problem is identical to that of Schuchardt et al. The only difference is in how these problems would be mapped to a mixed-intege linear program. We would directly model the indicator functions in the objective using a single linear constraint. Schuchardt et al. (202T) would use multiple linear constraints, each corresponding to one point in the adversarial budget space.
202T from Eqs. 123 to
To summarize: For randomly smoothed models, masking out perturbations using a-priori knowl- edge about model's strict locality is equivalent to completely randomizing (here: flipping bits with probability 50%) parts of the input. While Schuchardt et al. (202I) only derived their certificate for binary data, it is conceivable that their approach could be applied to strictly local models for tinuous data. Considering our certificates for Gaussian (Proposition Тp and (Proposition 2) uniform smoothing, where the base certificate weights _ and +. respectively, it should again be possible to perform the same masking operation as Schuchardt et al. (2021) by using -> oo and À + co.
Finally, it should be noted that the certificate by |Schuchardt et al. 2021 allows for additional con- straints, e.g. on the adversarial budget per node or the number of nodes controlled by the adversary. As all of them can be modelled using linear constraints on the budget variables (see Section of their paper), they can be just as easily integrated into our mixed-integer linear programming certificate.
E EXPERIMENTAL SETUP AND ADDITIONAL EXPERIMENTS
In the following, we first explain the metrics we use for measuring the strength of certificates, and how they can be applied the different types of randomized smoothing certificates used in our experiments. We then discuss the experimental setup, as well hyperparameters and additional ex- perimental results for our semantic segmentation (Section E.2 and node classification (ecction 8.2) experiments.
F. METRICS
We use two metrics for measuring certificate strength: Certified accuracy (i.e. the percentage of correct and certifiably robust predictions) and certified ratio (i.e. the percentage of certifiably robust predictions, regardless correctness). We use Monte Carlo randomized smoothing (see SseeeSetioon C Therefore, may have abstain from making predictions. Abstentions and incorrect. In the case of center smoothing, either all or none predictions abstain (this is inherent the method. In our experiments, center smoothing never abstained). In the following, let Jn. be the indices of correct predictions, given an input x.
counted non-robust.
{d E f1...., Dout
Naive collective certificate. The naive collective certificate certifies each prediction independently. Like with base certificates, let (m)) be the set of perturbed inputs yn is robust Let B2 be the collective perturbation model. Then LL {d {l...., Dont } B, C H[(") } is the set of all
J_d_ and the certified accuracy certifiably robust predictions. The certified ratio can be computed as D
LLZ as D
Center smoothing Center smoothing does not determine which predictions are robust, but only how many are. Let & be the number of certifiably robust predictions. The certified ratio be easily
34

---

Under review as a conference paper at ICLR 2022
k For the certified accuracy, we have make the worst-case assumption that the computed Dout"
non-robust predictions are correct predictions, i.e compute max(0.k- [Z]]
Dout
Collective certificate. Let ((T) be the optimal value of our collective certificate and set of targeted nodes T. Then both the certified ratio and certified accuracy can be computed via QTT) with {I...., } and T = 2, respectively.
Dous
=
E.2 SEMANTIC SEGMENTATION
We first list all parameters and details of our training and certification procedures, before discussing additional experimental results in Section E.2.3
E.2. EXPERIMENTAL SETUP AND HYPERPARAMETERS
Model. As the base model for the semantic segmentation task, we use a U-Net model (Ronneberger al. 2015) with a ResNet-18 (He et al. 2016) backbone, implemented by the Pytorch Segmen- tation Models library (version 0.13) (Yakubovskiy 2020). We use the library's 's default parameters. In particular, the imputs to the U-Net segmentation head are the features of the ResNet model after the first convolutional layer and after each ResNet block (i.e. after every fourth of the subsequent layers). The U-Net segmentation head uses (starting with the original resolution) 16, 32, 64, 128 and 256 convolutional filters for processing the features at the different scales. To avoid dimension mismatches in the segmentation head, all input images are zero-padded to a height and width that is the next multiple of 32,
Data and preprocessing. We evaluate our certificates on the Pascal- 2012 segmentation vali- dation set. We do not use the test set, because evaluating metrics like the certified accuracy requires access to the ground-truth labels. For training, we use the 10582 Pascal segmentation masks ex- tracted from the SBD dataset (Hariharan et al. (01T) (referred to as "Pascal trainaug" "Pascal augmented training set" in other papers). SED uses a different data split than the official Pascal- VOC 2012 segmentation dataset. We avoid data leakage by removing all training images that appear in the validation set. We downscale both the training and the validation images and ground-truth masks to 50% of their original height and width, that we can use larger batch sizes and thus use our compute time to more thoroughly evaluate a larger range of different smoothing distribu- tions. The segmentation masks are downscaled using neighbr interpolation, the images are downscaled using the INTER AREA operation implemented in OpenCV (Bradski 2000).
Training and data augmentation. We initialize our model weights using the weights provided by the Pytorch Segmentation Models library, which were obtained by pre-training on ImageNet. We train our models for 256 epochs, using Dice loss with batch size 64 and Adam(lr = 0.001, 31 = 0.9, B2 = 0.999. 10-8, weight _decay = O. Every 8 epochs, we compute the mean IOU on the validation set. After training, we use the model that achieved the highest validation mean IOU. We apply the following train-time augmentations: Each image is randomly shifted by up to 10% of its height and width, scaled by a factor from [0.5, 2.0] and rotated between -10 and 10 degrees using the ShiftScaleRRtate augmentation implemented by the Albumentations library (version 0.5.2) (Buslaev et af.) 2020). The images are than cropped to a fixed size of 128x x 160. Where necessary, the images are padded with zeros. Padded parts of the segmentation mask are ignored during training. After these operations, each input is randomly perturbed using a Gaussian distribution with a fixed standard deviation E {0, 0.00.......... 0.5).. All samples are clipped [0, 1] retain valid RGB- images.
Certification. We evaluate all certificates on the first 50 images from the validation set that after downscaling- - have a resolution of 166 x 250. For our experiments, we use Monte Carlo randomized smoothing (see discussion in /Section C). We use 12288 samples for making smoothed predictions and 153600 samples for certification. We use the significance parameter to 0.01, i.e. all certifi- cates hold with probability 0.99. For the center smoothing baseline, we use the default parameters suggested by the authors (A = 0.05, 3 2, ai 02). For the naive collective certificate baseline, we use Holm correction to account for the multiple comparisons problem, which yields strictly bet- ter results than Bonferroni correction. For localized smoothing certificates, we use Bonferroni correction. For our localized smoothing distribution, we partition the input image into a regular grid of size 4 6 and define minimum standard deviation miin and maximum standard deviation maxx-
35

---

Under review as a conference paper at ICLR 2022
Let ((AA)) be the set of all pixel coordinates in grid cell (A. To smooth outputs in grid cell (i,j),
use smoothing distribution (O0, (o) with, Wk {l..... ..... 4), {l..... 6), d E J(k.))
max (1i 1b jl)
do
min + (mmax Omin)
(139)
6
L.e. we linearly interpolate between mmin and max based on the 1 distance of grid cells (i. and (k. All results are reported for the relaxed linear programming formulation of our collective certificate (see Ssccionn A.4). For each grid cell, we use 24 4-6 to 512 samples for prediction and 6400 samples for certification. The collective linear program is solved using MOSEK (version 9.2.46) (MOSEK ApS 2019) through the CVXPY interface (version 1.1.13) (Diamond & Boyd 2016).
- ف of the samples, which corresponds
E.2.2 HARDWARE
All experiments on image segmentation were performed using a Xeon E5-2630 v4 CPU @ 2.20GHz, an NVIDA GTX 1080TI GPU and 128 GB of RAM.
E.2.3 COMPLETE EXPERIMENTAL EVALUATION
As explained in Section 8.1 the objective of our experiments on semantic segmentation is to verify our claim that localized smoothing allows for better securacy-robustnes trade-off than random- ized smoothing with i.i.d. distributions, i.c. it allows us to retain a higher prediction quality and simultaneously provide stronger collective robustness guarantees.
The first step of our evaluation procedure is to evaluate the naive and the center smoothing baselines for Gaussian standard deviations of localized smoothing parameters mmin, Jout that result in equal or higher accuracy and stronger certificates, as measured by certified accuracy and certified ratio. Figs. 5 to g show the certified accuracy and certified ratio curve for all 10 pairs of baseline and locally smoothed models (5 per baseline). The AUC of the certified ratio and certified ratio curves for all smoothed models are summarized in Tables and Safe for center smoothing with o = 0.2, which has a slightly higher certified ratio but lower accuracy, we can outperform all baselines.
0.2, 0.3, 0.4, 0.5} and for each find combination
The second step is to fix the found localized smoothing parameters and perform tne-grained search over a [o, 1]. This is to ensure that our previous results were not caused by a particularly poor choice of baseline parameters. Table 5) summarizes the results. It shows that there is no in our search space for which the baselines outperform the locally smoothed model w.r.t. our metrics of certificate strength.
Figure Fig. 4/demonstrates why there is no a that outperforms our baselines, using the certified ratio of the naive collective certificate baseline as example. The certificate strength, measured by the certified ratio's ' AUC, increases with a. But the model's 's accuracy decreases with a. Therefore, strengthening the certificate requires sacrificing some accuracy. But the locally smoothed models were already as accurate or more accurate than the baselines, which makes it impossible for the base- lines simultaneously attain higher accuracy and stronger certificates. To summarize: Localized smoothing appears to indeed offer a better trade-off between certified accuracy and robustness.
we mentioned that we compare base classifiers with different trained weights. For i.i.d. smoothing with a,, we loaded models trained with Trrain = a. For localized smoothing, we loaded models trained with Trrai min- To show that this not the reason why we outperform the baselines, we compare the same i.i.d. and localized smoothing distributions as before, but use Tusin = mmin for all models. The results are summarized Appendix E.2.3 and Table 4 Overall, there is only single instance in which the baselines are better than the localized smoothing cer- tificate in any of our metrics: For a = 0.3, the naïve baseline attains an accuracy of 79.5% that 0.4 p.p. higher than that of the locally smoothed model. The AUC of its certified accuracy and cer- tified ratio curves 0.492 and 0.5615, respectively - are however much smaller than the 0.5869 and 0.6579 guaranteed by localized smoothing. So, even with this different choice of weights, localized smoothing appears to guarantee a better trade-off between accuracy and provable robustness.
In Section 8.1,
While it resulted in significantly stronger certificates, the proposed collective certificate added very little additional computational cost, compared to the naive collective certificate. The naive collec- tive certificate requires taking Monte Carlo samples and then performing small number of vector
36

---

Under review as a conference paper at ICLR 2022
operations to compute the per-prediction Gaussian smoothing certificates. The proposed collective certificates requires taking Monte Carlo samples and computing the same type of per-prediction certificate, but then solves linear program top. The sampling dominated the runtime, with an average 460 s per image (both for the baseline and the proposed certificate, as we used the same num- ber of samples for both). Averaged over all experiments and images, computing the per-prediction certificates took s for the baseline and 0.15s for the proposed certificate (the increased cost for the baseline due the more complicated Holm correction with Bonferroni correction both are equally fast). Averaged over all images and tested adversarial budgets, solving each collective linear program only took 0.68 s, i.e. much less than the Monte Carlo sampling that is necessary for both the baseline and our method.
Certified ratio AUC
1.0
0.6
0.8
Accuracy
0.4
0.6
0.4
0.2
0.2
0.0
0.1
0.3
0.4
0.5
0.2
0.4
0
(a) Cortificate strength
(b) Accuracy
Figure 4: Trade-off off between accuracy and certifiably robustness at the example of the naive collec- tive certificate and certified ratio AUC. Increasing the standard deviation strengthens the certifi- cate, but decreases the accuracy.
37

---

Under review as a conference paper at ICLR 2022
Naive collective certificate
Localized smoothing
AUC of
AUC of Cert. Ratio
AUC of
AUC of Cert. Ratio
Acc.
Cert. Acc.
mmin
c max
Acc.
Cert. Acc.
0.1
87.7%
0.1555
0.1702
0.055
0.28
87.7%
0.1807
0.193
0.2
83.8%
0.3127
0.3515
0.16
0.35
83.9%
0.3627
0.3925
0.3
79.1%
0.4899
0.548
0.25
0.7
79.1%
0.5869
0.6579
0.4
72.5%
0.5426
0.6067
0.25
1.5
76.4%
0.7764
0.8999
0.5
64.9%
0.5684
0.6444
0.3
1.5
74.8%
0.7143
0.8091
Table 1; Comparison of the naïve collective certificate baseline and localized smoothing for E {0.1, 0.2, 0.3, 0.4, 0.5} and different min and mmax. In all cases, the localized smoothing certificate retains an equal or higher accuracy and simultaneously provides stronger robustness guarantees.
Center smoothing
Localized smoothing
AUC
AUC of Cert. Ratio
AUC of Cert. Acc.
AUC of Cert. Ratio
Acc.
Cert. Acc.
min
max
Acc.
0.1
88.3%
0.1673
0.194
0.08
0.15
88.4%
0.1889
0.2004
0.2
84.7%
0.281
0.3464
0.12
0.4
84.8%
0.3151
0.3427
0.3
80.3%
0.3192
0.4339
0.2
0.6
80.5%
0.4935
0.5533
0.4
75%
0.2316
0.3720
0.25
1.5
76.4%
0.7764
0.8999
0.5
68.3%
0.1498
0.2914
0.25
1.5
76.4%
0.7764
0.8999
Table 2:
Comparison of the center smoothing baseline and localized smoothing for (0.1, 0.2, 0.4, 0.5} and different min and maxx- Safe for 0.2, where the baseline has slightly higher certified ratio AUC but lower accuracy, localized smoothing retains an equal or higher accuracy and simultaneously provides stronger robustness guarantees.
Naïve collective certificate
Localized smoothing
AUC of
AUC of Cert. Ratio
AUC of
AUC of Cert. Ratio
Acc.
Cert. Acc.
min
0 max
Acc.
Cert. Acc.
0.1
86.9%
0.1519
0.1686
0.055
0.28
87. 87.7%
0.1807
0.193
0.2
83.8%
0.3184
0.357
0.16
0.35
83.9%
0.3627
0.3925
0.3
79.5%
0.492
0.5615
0.25
0.7
79.1%
0.5869
0.6579
0.4
73.5%
0.6094
0.711
0.25
1.5
76.4%
0.7764
0.8999
0.5
72.5%
0.7001
0.7981
0.3
1.5
74.8%
0.7143
0.8091
Table Comparison of the naïve collective certificate baseline and localized smoothing for E 0.2, 0.3, 0.4, 0.5) and different miin and 0max- Unlike in Table we also load the model trained with mmin for the baselines. Safe for 0.3, where the baseline has a higher accu- racy but much weaker certificates, localized smoothing again offers higher accuracy and stronger certificates.
Center smoothing AUC of
Localized smoothing
AUC of Cert. Ratio
AUC of
AUC of Cert. Ratio
Acc.
Cert. Acc.
Omin
T maxx
Acc.
Cert. Acc.
0.1
88.3%
0.1624
0.19
0.08
0.15
88.4%
0.1889
0.2004
0.2
83.9%
0.268
0.3392
0.12
0.4
84.8%
0.3151
0.3427
0.3
80%
0.3721
0.5009
0.2
0.6
80.5%
0.4935
0.5533
0.4
74.9%
0.3494
0.5397
0.25
1.5
76.4%
0.7764
0.8999
0.5
62.9%
0.1656
0.4212
0.25
1.5
76.4%
0.7764
0.8999
Table 4: Comparison of the center smoothing baseline and localized smoothing for E
(0.1, 0.2, 0.3, 0.4, 0.5} and different 7min and dmax- Unlike in Table 2] we also load the model trained with amin for the baselines. In all cases, the locally smoothed model has higher accuracy and stronger certificates.
38

---

Under review as a conference paper at ICLR 2022
Localized smoothing
Baselines
Best
Best
AUC of Cert. Ace.
AUC of Cert. Ratio
0 amin
o Tmax
Acc.
Baseline
AUC
AUC of Cert. Ratio
Cert. Acc
0.055
0.28
87.7%
0.1807
0.193
0.1555
0.1702
0.16
0.35
83.9%
0.3627
0.3925
Naïve Collective
0.296
0.3293
0.25
0.7
79.1%
0.5869
0.6579
0.4899
0.548
0.25
1.5
76.4%
0.7764
0.8999
Certificate
0.5753
0.6465
0.3
1.5
74.8%
0.7143
0.8091
0.5753
0.6465
0.08
0.15
88.4%
0.1889
0.2004
0.1488
0.1704
0.12
0.4
84.8%
0.3151
0.3427
Center
0.2715
0.3286
0.2
0.6
80.5%
0.4935
0.5533
Smoothing
0.3306
0.4255
0.25
1.5
76.4%
0.7764
0.8999
0.3538
0.5029
Table 5: Optimizing baseline standard deviation a. For the same (amin mmax) as in Tables | and 2 perform grid search for [0, 0.5) that yield certified accuracy certified ratio curves with higher AUC, and an accuracy that at least equals the locally smoothed models. Such a a could not be found. Localized smoothing appears offer better accuracy-robustec trade-off.
39

---

Under review as a conference paper at ICLR 2022
1.0
1.0
LP
LP
Cortified ratio
0.8
localized Naive localized
Certified ratio
0.8
localized
0.6
0.6
Naive
localized
Naïve i.i.d.
Naive i.i.d.
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(a)
0.1, Mmin
0.055, max
0.28
0.2, min 0.16, mmas
0.35
1.0
1.0
I.P
I.P localized
Certified ratio
0.8
localized
Certified ratio
0.8
0.6
Naive localized
0.6
Naive localized
0.4
Naive i.i.d.
0.4
Naive i.i.d.
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(c) 0.3, minn 0.25, Fmax 0.7
(d) 0.4, amin 0.25, mmax
1.5
1.0
LP
Certified ratio
localized
Naïve localized
0.4
Naïve i.idd.
0.2
0.0
0.5
1.0
1.5
2.0
Adversarial budget
(c) a 0.5, Omin
0.3, Fmax 1.5
Figure 5: Certified ratios of U-Net models under varying adversarial budgets We compare the naïve i..dd smoothing baseline (with standard deviation σ) to localized smoothing (with param- min: max such that the locally smoothed model has higher equal accuracy). Com- bining the localized smoothing base certificates using the proposed linear program (solid orange line) instead of evaluating them independently (dotted orange line) yields stronger guarantees. For E f0.3, 0.4, 0.5}. the localized smoothing certificate outperforms the baseline for all c.
40

---

Under review as a conference paper at ICLR 2022
1.0
1.0
Certified accuracy
Certified accuracy
LP
LP
0.8
localized Naive localized
0.8
localized
0.6
0.6
Naive
localized
0.4
Naïve i.i.d.
Naive i.i.d.
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(a)
0.1, mmin
0.055, max
0.28
0.2, min 0.16, mmas
0.35
1.0
1.0
Certified accuracy
Certified accuracy
I.P
I.P localized
0.8
localized
0.8
0.6
Naive localized
Naive localized
0.4
Naive i.i.d.
0.4
Naive i.i.d.
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(c) 0.3, mann
0.25, Fmax 0.7
(d) 0.4, amin 0.25, mmax
1.5
1.0
Certified accuracy
LP
localized
Naïve localized
0.4
Naïve i.idd.
0.2
0.0
0.5
1.0
1.5
2.0
Adversarial budget
(c) a 0.5, Omin
0.3, Fmax
1.5
Figure 6: Certified accuracies of U-Net models under varying adversarial budgets We compare the naive collective certificate baseline (with standard deviation σ) to localized smoothing (with parameters min: max such that the locally smoothed model has higher equal accuracy). Com- bining the localized smoothing base certificates using the proposed linear program (solid orange line) instead of evaluating them independently (dotted orange line) yields stronger guarantees. For E f0.3, 0.4, 0.5}. the localized smoothing certificate outperforms the baseline for all c.
41

---

Under review as a conference paper at ICLR 2022
1.0
1.0
LP
LP
Certified ratio
0.8
localized
Certified ratio
0.8
localized
0.6
Naäve localized
Naive localized
0.4
Center
0.4
Center
smoothing
smoothing
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(a) R
0.1, Omin
0.08, mmax
0.15
(b)
0,2, mmin 0.12, maxx
0.4
1.0
1.0
LP localized
Certified ratio
0.8
localized
Certified ratio
0.8
0.6
Naive localized
0.6
Naive
localized
0.4
Center
0.4
Center
smoothing
smoothing
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(c) 0 0.3, Omin 0.2, Fmax = 0.6
(d) 0 0.4, miin 0.25, Omax = 1.5
LP
Certified ratio
localized
0.6
Naive localized
0.4
Center
smoothing
0.2
0.5
1.5 Adversarial budget e
(c) = 0.5, Omin 0.25, Fmax = 1.5
Figure 7: Certified ratios of U-Net models under varying adversarial budgets e. We compare the center smoothing baseline (with standard deviation a) to localized smoothing (with parameters Omin; mmax such that the locally smoothed model has a higher or equal accuracy). For 0, center smoothing has higher certified ratios, i.e. it abstains a lower rate. For 0.2, the center smoothing certified accuracy curve has higher AUC than both the naïve combination localized smoothing certificates (dotted line) and the proposed collective certificate (solid line). But for other a localized smoothing outperforms center smoothing. The gap widens with increasing a.
42

---

Under review as a conference paper at ICLR 2022
1.0
1.0
Certified accuracy
Certified accuracy
LP
LP localized
0.8
localized
0.8
0.6
Naive localized
0.6
Naive localized
0.4
Center smoothing
Center
smoothing
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
(a)
0.1, miin
0.08, max
0.15
(b)
0.2, min
0.12, 0 max
0.4
1.0
1.0
Certified accuracy
Certified accuracy
I.P
LP localized
0.8
localized
0.8
0.6
Naive localized
Naive
localized
0.4
Center smoothing
0.4
Center
smoothing
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
Adversarial budget
0.3, Jmin
0.2, Fmax
0.6
(d) 0.4, amin 0.25, mmax
1.5
1.0
Certified accuracy
LP
localized
Naive localized
0.4
Center
smoothing
0.2
0.0
0.0
0.5
1.0
1.5
2.0
Adversarial budget
(e) a 0.5, amin 0.25, Tmax 1.5
Figure 8: Certified accuracies of U-Net models under varying adversarial budgets We compare the center smoothing baseline (with standard deviation σ) to localized smoothing (with parameters miin max such that the locally smoothed model has higher or equal accuracy). Combining the localized smoothing base certificates using the proposed linear program (solid orange line) instead of evaluating them independently (dotted orange line) yields stronger guarantees. The gap between center smoothing and localized smoothing widens with increasing
43

---

Under review as a conference paper at ICLR 2022
E.3 NODE CLASSIFICATION
We first discuss the experimental setup and the necessary parameters for our training and certification procedure before we show additional experimental results in Section E.3.3
E.3.1 EXPERIMENTAL SETUP AND HYPERPARAMETERS
Metric In the node classification setting we are generally only concerned with certified accuracy. To calculate this accuracy, we only consider nodes that are correctly classified, where the method does not abstain, and is certifiably robust for the given perturbation.
Model We test two different models: 2-layer APPNP (Klicpera et al. 2019) and 6-layer GCN (Kipf & Welling 2017). For both models we use hidden size 64 and dropout with a probability 0.5. Furthermore, for the propagation step of APPNP we use 10 for the number of interactions and 0.15 as value for a.
Data and preprocessing. We evaluate our approach on the Cora-ML node classification dataset. We perform standard preprocessing, i.e., remove self-loops, make the graph undirected and select the largest connected component. For the localized smoothing approach we perform Metis clustering (Karypis & Kumar 1998) to partition the graph into clusters. We create an affinity ranking by counting the number of edges which are connecting cluster i and This ranking is used to select the noise parameter for smoothing the attributes of cluster j while classifying node cluster i.
Training and data augmentation All models trained with learning rate of 0.001 and weight decay of 0.001. The models we use for sparse smoothing are trained with the noise distribution that is also reported for certification. The localized smoothing models are trained the their minimal noise level, i.c., not with localized noise but with only 0f and 0 0min.
Certification In the node classification setting the noise parameter space is large. Instead of only one noise parameter as used in the image segmentation scenario, we can vary flip probabilities for addition and deletion. Apart from that we need lower and upper values for each of those. Therefore, we just selected the minimum parameters and focused on optimising the baseline around these noise levels as described in [Section 8.2 The specific noise parameters and baseline search space regions can be seen in the captions of the respective figures. The collective linear program is solved us- ing MOSEK (version 9.2.46) (MOSEK ApS] 2019) through the CVXPY interface (version 1.1.13) (Dimmond & Boyd 2016).
E.3.2 HARDWARE
All experiments on image segmentation were performed using an AMD EPYC 7543 CPU @ 2.80GHz, an NVIDA A100 GPU and 32 GB of RAM.
E.3.3 ADDITIONAL EXPERIMENTAL EVALUATION
In Fig. we can see a comparison of our localized smoothing approach to sparse smoothing for a GCN model with 6-layers. Here, the smoothing distribution is the same the one used in Fig. 3 of Section 8.2 In Fig. 10 we can see a comparison for an APPNP model but with smaller minimal noise levels.
We can see that in all experiments for deletion, the localized smoothing approach outperforms the baselines. In the deletion setting we increase the certified accuracy curve's AUC from an average 12.28 to 18.93 (i.e. by 54%). In the addition scenario the AUC, averaged over all experiments, decreases from 6.85 to 6.08 (i.e. by 11.25%). This is mainly due the results of the experiment that can be seen in Fig. 10 In the baseline evaluation process both noise parameters for sparse smoothing are significantly larger than our min-values. This shows that our values may be too small in this scenario.
Fig. compares the variance certificate to the sparse smoothing certificate of (Bojchevski et al. (222)) That is, we use only one cluster and the same noise levels and models for our approach and the baseline, i.e., 8+ 0.01 and A = 0.6. We observe that for both models the variance certificate yields better results for deletion. However, in the addition setting, it is outperformed by the baseline. If we look at Theorem we can see that we multiply the adversarial budget for addition with y+
44

---

Under review as a conference paper at ICLR 2022
1.0
1.0
Certified accuracy
LP localized
Certified accuracy
LP localized
0.8
0.8
Naive localized
Naive localized
0.6
Naive t.d.
0.6
Naive i..d
0.4
0.4
0.2
0.2
0.0
0.0
20
50
20 30
40
Number of adversarial additions
Number of adversarial deletions
Figure 9: Certified accuracy for varying number of attribute additions (left) and deletions (right)
for the GCN model. We compare localized smoothing (0 min = 0.075, 0min = 0.6, 0 0.15,
mmax 0.95) with sparse smoothing with (0+ 0.085, # 0.609) for addition and deletion.
This configuration yields the largest certified accuracy curve AUC of 10.41 for addition and 14.78
for deletion compared to all combinations 0+ E {0.007, 0.0085, 0.01) and 0- E [0.1. 0.827]
In the deletion scenario we outperform the baseline with an AUC of 21.76 (15.76 non-collective). For addition the sparse smoothing performs slightly better than our certificate with AUC of 9.19 (6.39 collecteec.. However, the our approach performs significantly better in small perturbation regions and also in clean accuracy (0 perturbation).
and the one for deletion with y As yt has 4 in the denominator the small noise level for addition results in larger values for y For these parameters we have y+ = 2.795 and Y = 0.491 which shows why the certificate is less robust to adversarial additions. This is consistent with the other experiments where our results are on par worse than the baseline for additions but we outperform for deletions.
The Monte Carlo sampling dominated the runtime. Averaged over all experiments, it took 1034 s (both for the baseline and the proposed certificate, as we used the same number samples for both). Averaged over all experiments, the per-prediction certificates took 0.11 s for the baseline and 0.66 s for the proposed certificate (note that the baseline uses the sparsity-award aware smoothing cer- tificate of Bojccheskii et al. (2020). while the proposed collective certificate uses our novel variance smoothing certificate (seef l'heorem 2). which requires estimating both the mean and variance of soft- max scores). Averaged over all tested adversarial budgets, solving each collective linear program only took 10.9 s, i.c. less than the Monte Carlo sampling that is necessary for both the baseline and our method. The reason that the linear programs for graphs required more time than those for image, even though they involve fewer constraints and variables, is that a different, not as well-vectorized implementation was used.
45

---

Under review as a conference paper at ICLR 2022
1.0
1.0
Certified accuracy
LP localized
Certified accuracy
LP localized
0.8
0.8
Naive localized
Naive localized
0.6
Naive i.d.
0.6
Naive i.d.
0.4
0.4
0.2
0.2
0.0
0.0
0
10
20
30
40
50
0
10
20
30
40
50
Number of adversarial additions
Number of adversarial deletions
Figure 10: Certified accuracy for varying number of attribute additions (left) and deletions (right) for the APPNP model. We compare localized smoothing (0+ 0.0075, 9 0.65, 0 0.08,
8 mmxx = 0.95) with sparse smoothing with (0+ = 0.0085, A- = 0.827) for addition and (0+
0.007, 0 0.555) for deletion. These configurations yield the largest certified accuracy curve AUC 5.62 for addition and 14.29 for deletion compared to all combinations 0+ E {0.007, 0.0085, 0.01} and 0 [0.1.... 0.827]. In the deletion scenario we outperform the baseline with an AUC of 18.76 (14.86 non-collective). However, the sparse smoothing performs better for addition than our certificate which only yields a AUC of 3.39 (2.54 non-collective). We observe that the optimal parameters for addition are both significantly larger than our minimal ones.
1.0
1.0
Certified accuracy
Var: cert., del.
Certified accuracy
0.8
0.8
Sparse, del.
0.6
Van: cert., add, Sparse, add.
0.6
Var. cert., del. Spurse, del.
0.4
Var. cert., add. Sparse, add.
0.2
0.2
0.0
0.0
0
10
20
30
40
0
10
20
30
40
Number of adversarial perturbations
Number of adversarial perturbations
Figure 11: Comparison of the variance certificate with sparse smoothing. this approach we only used one cluster, i.e., use the same noise levels. Left on the right for a 6-layer GCN. The models are trained with the same noise parameters 0+ 0.01 and 0 0.6. We observe that in for both models the variance certificate yields better results for deletion. However, in the addition setting, it is outperformed by the baseline.
the results for an APPNP model and
46


Reviews:
[{"review_id": "lMy28o_NWxR", "reviewer": "Reviewer_y7cf", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Strengths: The studied problem is important and the paper is easy to follow (before evaluation) in general. The proposed method is somewhat novel. \n\nWeaknesses: The key difference between the proposed method and the existing works is unclear. The paper lacks comparison with the existing method. Evaluation is insufficient and some metrics are not reasonable.  \n\n\n\nThe main idea is motivated by several existing works and the key difference between the proposed method and these existing works are unclear for me. \nFor instance, what’s the key difference between the proposed theoretical results (e.g., Prop 1&2) and those in Eiras et al.? Is it possible for Fischer et al. to be adapted to the considered setting? \n \n\nNo comparison with center smoothing or/and Fischer et al., if possible. \n\nFigures are confused for me. For instance, what is the difference between the “dotted line” and “Naive” in Figure 2? Similar to all the other figures. \n\nWhy using certified ratio? I do not think it meaningful to certify pixels/nodes that are wrongly classified.\n\nThe image segmentation is only evaluated on Pascal voc2012. I suggest the authors to evaluate on more datasets, e.g., Cityscape, which is used in Fischer et al. \nThe authors use AUC to report the \n\nIt is not standard to use AUC to show image segmentation results.  A commonly used metric is mIoU (mean intersection over union). \n\nUNet is an outdated model for semantic segmentation model. I suggest the authors to evaluate on more recent models such as deeplab v3, danet, hrnet, etc.  \n\nWhat’s the computational overhead to find the optimal $\\sigma_{\\min}$ and $\\sigma_{\\max}$? \n\nWhile computation is an issue for localized RS, the way to partition an image into grid cells and certifying grid cells independently already looses semantic relationship between pixels in different cells and thus violates the purpose of semantic segmentation.  \n\n", "summary_of_the_paper": "The authors consider tasks mapping a single input to multiple outputs and study robustness certificate against input perturbations. To achieve the goal, the authors propose a collective certificate where each output is dependent on the entire input but assigns different levels of importance to different input regions, and then derived the collective certificate based on localized randomized smoothing. The proposed collective certificate is evaluated on both image segmentation and node classification tasks. \n", "summary_of_the_review": "Collective robustness certificate is an important research problem. The proposed method is novel to some extent, but its key difference with the existing work is not unclear for me, and so as the performance comparison. My another major concern is on evaluation. For instance, the image segmentations results are not reported using reasonable metrics and the models and datasets are rather outdated on my end. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ifiC7ibyt9d", "reviewer": "Reviewer_ruKP", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths\n- The collective certification strategy in the paper can be used with most of the existing literature on randomized smoothing, which allows it to be quite versatile and adapt to new developments in the field. The MILP relaxation and the distribution sharing ideas in the paper also highlight some critical limitations/ future research directions for randomized smoothing.\n- The variance smoothing idea in the paper is quite exciting and a natural next step for getting better certificates. \n- The empirical results in Table 5 that compare the best achievable baseline performance with the performance of the proposed methods provide compelling evidence for the efficacy of the suggested approach.\n\nWeaknesses\n- No training counterpart is suggested for the proposed local smoothing strategy. The current results use a model trained with $\\sigma_\\min$ as the base model. It seems a bit counterintuitive to have essentially different prediction strategies during training and testing. Some of the local smoothing ideas should be reflected in training to make the objectives better aligned. ", "summary_of_the_paper": "The paper makes three contributions in particular:\n- A local version of randomized smoothing for multi-output classifiers. The authors suggest using a customized smoothing distribution for certifying each output of the multi-output classifier. The custom distributions allow them to produce tighter guarantees for each output.\n- A new analysis method of variance smoothing for discrete data uses the average softmax value instead of the majority vote as the prediction rule. The authors use the first and second-order statistics (mean and variance) to provide robustness guarantees in this method.\n- A collective certification strategy for multi-output classifiers using a common interface ($\\ell_p$ norm ellipsoids) for base certificates for every output. The authors describe a common way of stating the base certified regions for every output. Then the multi-output certification problem can be expressed as a mixed-integer linear program to find a point inside the perturbation model that lies outside the base certified regions for the maximum number of outputs.", "summary_of_the_review": "In summary, the paper explores a very relevant problem in certification against adversarial examples. The main ideas of the paper are pretty novel and would help future research. The paper does a great job of presenting the ideas and discussing some of the potential limitations. However, it would be better if the authors briefly discussed the mismatch between the training objectives and the test time prediction model. Taking all of this into account, I would recommend the paper be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZZj5cnLMe7l", "reviewer": "Reviewer_z9Ri", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "**Strengths**\n\nI very much appreciate the extensive experiments in tuning in the baseline with several sigma to guarantee (1) best robust accuracy of baseline when compared to localized randomized smoothing (2) when comparing certified ratios, the accuracies are comparable. The paper's proposed methodology is very well written and the formulation is beautifully simple and intuitive.\n\n\n**General Questions**\n\n1. Why is Equation 1 not an equality? Is not the set H for every pixel output is exactly tight? Or is the assumption here that H can be an over-approximation to the true certified region? \n\n2. In the case where H is given by the localized smoothing using Propositions 1 or 2, will this result in an exact equality for (1)?\n\n3. Can the authors comment of the compleixty for solving (5) with the proposed splits in the inputs? How does the method compare against the Naive approach. I believe it should be much more expensive as it requires the computation of the lower bound to the probability of success and then followed by solving the high dimensional linear program.\n\n4. There are no comparisons against Fischer et al on certifying semantic segmentation.\n\n5. It is not clear to how does the Naive classifier in Fgiure 2 work. Is it simply to perform RS certification for every pixel independently and counting the number of certifiable functions with a shared sigma over all inputs? If so, it is not clear to me why does the dashed line perform worse than this Naive approach?\n\n6. It is also not clear to me why does solving the linear program reformulation work better than direct RS with anisotropic certificates (dashed line vs solid orange). Since the linear program lower bounds the original objective should not it be providing a pessimistic certified accuracy compared to the dash orange? That is to say, it tends to produce more adversaries that flip predictions under the lower bound but does not necessarily flip prediction of the original binary objective?\n\n7. This is related to (6). What is the key motivation/intuition behind believing that solving (3) is better than directly certifying the anisotropic certificates. This link is very much un clear to me.\n\n8. One of the key weaknesses that I see so far is the small certification experiments. For example, on the segmentation task, the certified accuracy is reported only on 50 images of the validation dataset. Perhaps a different dataset experiments (Cityscapes) following Fischer et al would make the submission stronger.\n\n9. It is not clear to me if showing state-of-the-art certification results is not the objective of the paper, what is the key objective/insight of this reformulation? Showing that localized RS has a better trade-off between accuracy and robustness is not sufficiently novel for several reasons. (1) The per pixel sigma certification was derived in prior art which the paper faithfully state. (2) The proposed method of nonshared sigma over all method (without linear relaxation) is expected to be better intuitively as it overparameterizes the smoothing distribution holding the global shared sigma RS as a special case. So, I do not follow: what are the key *new* insights that I am missing here (please correct me if I am wrong here). (3) The certification time is not reported which is expected to be much larger.\n\n10. I generally enjoyed reading the variance smoothing part (section B.2 in the appendix). The authors' are to be commended on it. Can the authors comment on how much of improved radius can the incorporation of the variance bring compared to classical RS certification. Does it actually tighten the radius for other certificates beyond gaussian? If so, this should be highlighted more in the paper as I believe this is significant. If not, then why doing variance smoothing and not directly with the expectation fixed and lower bounding over functions with a fixed expected prediction with Bernoulli distribution? So in short, why variance smoothing? \n\n\n\n**Minor comments**\n1. Page 3, line 9: \"be the probability of g y\" >> \"of predicting y under g\".\n2. Caption of Figure 2. Sigma_min is given two values, I believe the second should be Sigma_max.\n3. Page 8, line 11: sigma_min assigned twice.\n3. Page 8, line 16: \"Figure Fig. 2\".\n4. Proposition 4 in page 17. The radius shown by Eiras et al is without inverse CDF. It is only the difference in predictions between the top and runner up class.\n5. Figure 1. I generally advise to have 4x6 grid in the figure aligning with the text. This is particularly the case as when Figure 1 was referenced in the experiments, it was after describing the 4x6 splits of the input.", "summary_of_the_paper": "**Summary**\n\nThe paper proposes a localized smoothing approach for certifying structured output models. The threat model of interest in this setting is the bounded input perturbation that results in the highest number of prediction flips per pixel. The paper proposes to utilize the idea that when certifying pixel predictions at location (i,j), one can smooth the input pixels (k,l) far away from (i,j) by larger noise magnitude (standard deviation) resulting in a higher certified radii as they perhaps may not play a significant role in predicting the label of (i,j). The paper formulates the problem of finding worst cases adversaries that result in misprediction to the task of finding adversaries outside the certified region with anisotropic smoothing over the input. The paper then lower bounds the binary objective with a box constraints and solve the problem using linear  programs. Experiments are conducted on image segmentation tasks along with node classification.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "41FGRK_xqW", "reviewer": "Reviewer_Fv4q", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper has many merits:\n- The motivation behind this work is clearly stated.\n- The use of anisotropic smoothing is intuitive.\n- The tasks on which the experiments are conducted are in line with the motivation.\n\nHowever, there several concerns in this work that need to be addressed:\n- While the major part of this work is dedicated to the theoretical analysis, it is not clear to me which parts belong to the contributions of this work and which parts are restatements from other work. For example:\n1. In terms of the theoretical results in this work in sections 4, 5, and 6: what is exactly new (considered as a contribution)? For example, Proposition 1 and 4 are just a special case of the results of Eiras et.al. for when the covariance matrix is diagonal. In fact, with the formulation setup presented in section 2, a generalization of proposition 1 can be found in Appendix A of [1]. \n\n2. In terms of the analysis in sections 4 and 6, what is exactly new? For example, the bound derived in Equation (1) and the analysis in (3-6) are very similar to the results in Schuchardt et. al.\n\n- In terms of experiments:\n1. it is mentioned that \"showcasing state-of-the-art accuracy on datasets is not part of our objective\". Why? If the proposed collective anisotropic certificate is preferable, then it is necessary to show that it improves the best baselines.\n\n2. What is the importance of certified ratio metric? Why not reporting wither certified accuracy or certified AUC in the case of segmentation. While two models could have similar certified ratios, their accuracy could significantly differ.\n\n3. Since the analysis of this work follows the work of Schuchardt et. al., a direct comparison on the strictly local setup should be presented.\n\n4. The experiments conducted include a single benchmark per task. The experiments should include multiple datasets to check whether the assumptions related to the use of anisotropic smoothing hold or not (e.g. homophily). \n\n- The writing of the paper could be significantly improved. There are several parts were the text refer to tables/figures in the appendix without mentioning the appendix. Also, please consider moving more experiments from the appendix to the main work. Moreover, in the caption of Figure 1, $\\sigma_{\\text{min}}$  is mentioned twice, is that a typo? It is also repeated in page 8 in the second paragraph.\n\n\n\n[1]: Certified Defense to Image Transformations via Randomized Smoothing, NeurIPS 2020.", "summary_of_the_paper": "This paper leverages the recent anisotropic certificates for randomized smoothing for certifying multi-output classifiers. In particular, it leverages anisotropic Gaussian  and Bernoulli smoothing for better collective robustness. Experimental evaluation was conducted on semantic segmentation and node classification to demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "While the main motivation of this work is clear, there are several parts of this work that need to be revised. In particular, it should be clearly stated which parts of the theoretical results in this work are new. Also, the experimental part of this work can be significantly improved by including stronger baselines and more datasets. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a framework for improving robustness certificates obtained by randomly smoothed classifiers in settings with multiple outputs (segmentation or node classification), by combining local robustness certificates obtained for individual classifiers. They validate their results empirically and demonstrate gains from their approach.

The reviewers were mostly in agreement that the authors make a novel and interesting contribution. However, there were a lot of technical concerns raised by reviewers that, while addressed during the discussion phase, would require a substantial revision of the paper to address adequately. Overall, I feel the paper is borderline but recommend rejection and encourage the authors to incorporate feedback from the reviewers and submit to a future venue.
Decision: Reject