Year: 2021

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 strictly local 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.

heading: 1 INTRODUCTION
text: There is a wide range of tasks that require models making multiple predictions based on a single input. For example, semantic segmentation requires assigning a label to each pixel in an image. When deploying such multi-output classifiers in practice, their robustness should be a key concern. After all – just like simple classifiers (Szegedy et al., 2014) – they can fall victim to adversarial attacks (Xie et al., 2017; Zügner & Gü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 a single perturbed input. While attacks on a single prediction may be easy, attacks on different predictions may be mutually exclusive. We have to explicitly account for this fact to obtain a proper collective robustness certificate that provides tight bounds.
There already exists a dedicated collective robustness certificate for multi-output classifiers (Schuchardt et al., 2021), but it is 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 predictions are in principle dependent on the entire input, each output may assign different importance to different components. For example, deep convolutional networks used for image segmentation can have very small effective receptive fields (Luo et al., 2016; Liu et al., 2018b), i.e. primarily use a 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 (Vaswani et al., 2017) 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 a few (not necessarily nearby) tokens (Shi et al., 2021).
While an adversarial attack on a single prediction of a softly local model is conceptually no different from that on a single-output classifier, attacking multiple predictions simultaneously can be much
more challenging. By definition, adversarial attacks have to be unnoticeable, meaning the adversary only has a limited budget for perturbing the input. When each output is focused on a different part of the input, the adversary has to decide on where to allocate their adversarial budget and may be unable to 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 on randomized smoothing (Liu et al., 2018a; Lécuyer et al., 2019; Cohen et al., 2019). Randomized smoothing is a versatile black-box certification method that has originally been proposed for single-output classifiers. Instead of directly analysing a model, it constructs a smoothed classifier that returns the most likely prediction of the model under random perturbations of its input. One can then use statistical methods to certify the robustness of this smoothed classifier. We discuss more details in Section 2. Randomized smoothing is typically used with i.i.d. 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., 2021). This results in a smoothed classifier that is 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 in a scheme we call localized randomized smoothing: Instead of using the same smoothing distribution for all outputs, we randomly smooth each output (or set of outputs) using a different non-i.i.d. distribution that matches its inherent soft locality. Using a 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 a 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-prediction 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 multi-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.

heading: 2 BACKGROUND AND RELATED WORK
text: Randomized smoothing. Randomized smoothing is a flexible certification technique that can be used for various data types, perturbation models and tasks. For simplicity, we focus on a
classification certificate for l2 perturbations (Cohen et al., 2019). Assume we have a continuous D-dimensional input space RD, a label set Y and a classifier g : RD → Y. We can use isotropic Gaussian noise with standard deviation σ ∈ R+ to construct the smoothed classifier f = argmaxy∈Y Prz∼N (x,σ) [g(z) = y] that returns the most likely prediction of base classifier g under the input distribution 1. Given an input x ∈ RD and the smoothed prediction y = f(x), we want to determine whether the prediction is robust to all l2 perturbations of magnitude , i.e. whether ∀x′ : ||x′−x||2 ≤ : f(x′) = y. Let q = Prz∼N (x,σ) [g(x) = y] be the probability of g predicting label y. The prediction of our smoothed classifier is robust if < σΦ−1(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 noise-level (here σ) is increased. But doing so could also lower the accuracy of the smoothed classifier or reduce q and thus weaken the certificate.
White-box certificates for multi-output classifiers. There are multiple recent methods for certifying the robustness of specific multi-output models (see, for example, (Tran et al., 2021; Zügner & Günnemann, 2019; Bojchevski & Günnemann, 2019; Zügner & Günnemann, 2020; Ko et al., 2019; Ryou et al., 2021; Shi et al., 2020; Bonaert et al., 2021)) 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 of Schuchardt et al. (2021). Like ours, it combines many per-prediction certificates into a collective certificate. But, unlike our novel localized smoothing approach, their certification procedure is only beneficial for strictly local models, i.e. models whose outputs operate on small subsets of the input. Furthermore, 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 Section D. Recently, Fischer et al. (2021) proposed a certificate for semantic segmentation. They consider a different notion of collective robustness: They are interested in determining whether all predictions are robust. In Section 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 no 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, 2021). Center smoothing bounds how much a vector-valued prediction changes w.r.t to a distance function under adversarial perturbations. With the l0 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 robustness, two recent certificates for non-i.i.d. Gaussian (Fischer et al., 2020) and uniform smoothing (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 collective 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 on the smoothing distribution itself and invalidate the certificate (see discussion by Wang et al. (2021)).

heading: 3 COLLECTIVE THREAT MODEL
text: 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 a multi-output classifier f : XDin → YDout , that maps from a Din-dimensional vector space to Dout labels from label set Y. We further assume that this classifier f is the result of randomly smoothing a base classifier g, as discussed in Section 2. To simplify our notation, we write fn to refer to the function x 7→ f(x)n that outputs the n-th label. Given this multi-output classifier f , an input x ∈ XDin and the resulting vector of predictions y = f(x), the objective of the adversary is to cause as many predictions from a set of targeted indices T ⊆ {1, . . . , Dout} to change. That is, their objective is minx′∈Bx ∑ n∈T I [fn(x
′) = yn], where Bx ⊆ XDin is the perturbation model. Importantly, note that the minimization operator is outside the sum, meaning the predictions have to
1In practice, all probabilities have to be estimated using Monte Carlo sampling (see discussion in Section C).
be attacked using a single input. As is common in robustness certification, we assume a norm-bound perturbation model. That is, given an input x ∈ XDin , the adversary is only allowed to use perturbed inputs from the set Bx = { x′ ∈ XDin | ||x′ − x||p ≤ } with p, ≥ 0.

heading: 4 A RECIPE FOR COLLECTIVE CERTIFICATES
text: Before discussing technical details, we provide a high-level overview of our method. In localized randomized smoothing, we assign each output gn of a base classifier g its own smoothing distribution Ψ(n) that matches our assumptions or knowledge about the base classifier’s soft locality, i.e. for each n ∈ {1, . . . , Dout} choose a Ψ(n) that induces more noise in input components that are less relevant for gn. For example, in Fig. 1, 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 x ∈ XDin and the corresponding smoothed prediction y = f(x), randomized smoothing makes it possible to compute per-prediction base certificates. That is, for each yn, one can compute a set H(n) ⊆ XDin of perturbed inputs that the prediction is robust to, i.e. ∀x′ ∈ Hn : fn(x
′) = yn. Our motivation for using non-i.i.d. distributions is that the H(n) will guarantee more robustness for input dimensions smoothed with more noise, i.e. quantify model locality.
The objective of our adversary is minx′∈Bx ∑ n∈T I [fn(x
′) = yn] with collective perturbation model Bx ⊆ XDin . That is, they want to change as many predictions from the targeted set T as possible. A trivial lower bound can be obtained by counting how many predictions are – according to the base certificates – provably robust to the collective threat model. This can be expressed as∑ n∈T minx′∈Bx I [ x′ ∈ H(n) ] . In the following, we refer to this as the naı̈ve collective certificate.
Thanks to our proposed localized smoothing scheme, we can use the following, tighter bound:
min x′∈Bx ∑ n∈T I [fn(x ′) = yn] ≥ min x′∈Bx ∑ n∈T I [ x′ ∈ H(n) ] , (1)
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.h.s. objective (recall Section 1). This makes our collective certificate stronger than the naı̈ve collective certificate, which allows each prediction to be attacked independently.
As stated in Section 1, the idea of combining base certificates into stronger collective certificates has already been explored by Schuchardt et al. (2021). 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 is 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 it allows us to compute the collective certificate from Eq. 1 using (mixed-integer) linear programming.

heading: 5 COMMON INTERFACE FOR BASE CERTIFICATES
text: A base certificate for a prediction yn = fn(x) is a set Hn ⊆ XDin of perturbed inputs that yn is provably robust to, i.e ∀x′ ∈ Hn : fn(x′) = yn. Note that base certificates do not have to be exact, but have to be sound, i.e. they do not have to specify all inputs to which the fn are robust but they must not contain any adversarial examples. As a common interface for base certificates, we propose that the sets Hn are parameterized by a weight vector w(n) ∈ RDin and a scalar η(n) that define a linear constraint on the element-wise distance between perturbed inputs and the clean input:
H(n) = { x′ ∈ XDin ∣∣∣∣∣ Din∑ d=1 w (n) d · |x ′ d − xd|κ < η(n) } . (2)
The weight vector encodes how robust yn is to perturbations of different components of the input. The scalar κ is important for collective robustness certification, because it encodes which collective perturbation model the base certificate is compatible with. For example, κ = 2 means that the base certificate can be used for certifying collective robustness to l2 perturbations.
In the following, we present two base certificates implementing our interface: One for l2 perturbations of continuous data and one for perturbations of binary data. In Section B, we further present a certificate for binary data that can distinguish between adding and deleting bits and a certificate for l1 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., 2020; Eiras et al., 2021) and merely reformulated to match our proposed interface, 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 generalization of Gaussian smoothing to anisotropic noise, a corollary of Theorem A.1 from (Fischer et al., 2020). In the following, diag(z) refers to a diagonal matrix with diagonal entries z and Φ−1 : [0, 1]→ R refers to the the standard normal inverse cumulative distribution function. Proposition 1. Given an output gn : RDin → Y, let fn(x) = argmaxy∈Y Prz∼N (x,Σ) [gn(z) = y] be the corresponding smoothed output with Σ = diag (σ)2 andσ ∈ RDin+ . Given an inputx ∈ RDin and smoothed prediction yn = fn(x), let q = Prz∼N (x,Σ) [gn(z) = yn]. Then, ∀x′ ∈ H(n) : fn(x ′) = yn with H(n) defined as in Eq. 2, wd = 1σd2 , η = ( Φ(−1)(q) )2 and κ = 2.
Bernoulli variance smoothing for perturbations of binary data For binary data, we use a smoothing distribution F(x,θ) with θ ∈ [0, 1]Din that independently flips the d’th bit with probability θd, i.e. for x, z ∈ {0, 1}Din and z ∼ F(x,θ) we have Pr[zd 6= xd] = θd. A corresponding certificate could be derived by generalizing (Lee et al., 2019), which considers a single shared θ ∈ [0, 1] with ∀d : θd = θ. However, the cost for computing this certificate would be exponential in the number of unique values in θ. We therefore propose a more efficient alternative. Instead of constructing a smoothed classifier that returns the most likely labels of the base classifier (as discussed in Section 2), we construct a smoothed classifier that returns the labels with the highest expected softmax scores (similar to CDF-smoothing (Kumar et al., 2020)). For this smoothed model, we can compute a 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 general-purpose technique that can be applied to arbitrary domains and smoothing distributions (see discussion in Section B.2). In the following, we assume the label set Y to consist of numerical labels {1, . . . , |Y|}, which simplifies our notation. Theorem 1. Given an output gn : {0, 1}Din → ∆|Y| mapping to scores from the |Y|-dimensional probability simplex, let fn(x) = argmaxy∈YEz∼F(x,θ) [gn(z)y] be the corresponding smoothed classifier with θ ∈ [0, 1]Din . Given an input x ∈ {0, 1}Din and smoothed prediction yn = fn(x), let µ = Ez∼F(x,θ) [gn(z)y] and σ2 = Varz∼F(x,θ) [gn(z)y]. Then, ∀x′ ∈ H(n) : fn(x′) = yn with H(n) defined as in Eq. 2, wd = ln ( (1−θd)2 θd + (θd) 2 1−θd ) , η = ln ( 1 + 1σ2 ( µ− 12 )2) and κ = 0.

heading: 6 COMPUTING THE COLLECTIVE ROBUSTNESS CERTIFICATE
text: With our common interface for base certificates in place, we can discuss how to compute the collective robustness certificate minx′∈Bx ∑ n∈T I [ x′ ∈ H(n) ] from Eq. 1. The result bounds the number of predictions yn with n ∈ {1, . . . , Dout} that can be simultaneously attacked by the adversary. In the following, we assume that the base certificates were obtained by using a smoothing distribution that is compatible with our lp collective perturbation model (i.e. κ = p), for example by using Gaussian noise for p = 2 or Bernoulli noise for p = 0. Inserting the definition of our base certificate interface from Eq. 2 and rewriting our perturbation model Bx = { x′ ∈ XDin | ||x′ − x||p ≤ } as{
x′ ∈ XDin | ∑Din d=1 |x′d − xd|p ≤ p } , our objective from Eq. 1 can be expressed as
min x′∈XDin ∑ n∈T I [ Din∑ d=1 w (n) d · |x ′ d − xd|p < η(n) ] s.t. Din∑ d=1 |x′d − xd|p ≤ p. (3)
We can see that the perturbed inputx′ only affects the element-wise distances |x′d−xd|p. Rather than optimizing x′, we can instead directly optimize these distances, i.e. determine how much adversarial budget is allocated to each input dimension. For this, we define a vector of variables b ∈ RDin+ (or b ∈ {0, 1}Din for binary data). Replacing sums with inner products, we can restate Eq. 3 as
min b∈RDin+ ∑ n∈T I [ bTw(n) < η(n) ] s.t. sum{b} ≤ p. (4)
In a final step, we replace the indicator functions in Eq. 4 with a vector of boolean variables t ∈ {0, 1}Dout . Define the constants η(n) = p ·min ( 0,mind w (n) d ) . Then,
min b∈RDin+ ,t∈{0,1}Dout ∑ n∈T tn s.t. ∀n : bTw(n) ≥ tnη(n) + (1− tn)η(n), sum{b} ≤ p. (5)
is equivalent to Eq. 4. The first constraint guarantees that tn can only be set to 0 if the l.h.s. is greater or equal η(n), i.e. only when the base certificate can no longer guarantee robustness. The term involving η(n) ensures that for tn = 1 the problem is always feasible2. Eq. 5 can be solved using any mixed-integer linear programming solver.
While the resulting MILP bears some semblance to that of Schuchardt et al. (2021), it is conceptually different. When evaluating their base certificates, they mask out parts of the budget vector b 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 5, our problem only involves a single linear constraint per prediction, making it much smaller and more efficient to solve. Interestingly, when using randomized smoothing base certificates for binary data, our certificate subsumes theirs, i.e. can provide the same robustness guarantees (see Section D.2).
Improving efficiency. Still, the efficiency of our certificate in Eq. 5. 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 Nin subsets sharing the same noise level (for example like in Fig. 1), as well as quantizing the base certificate parameters η(n) into Nbin bins reduces the number of variables and constraints from Din + Dout and Dout + 1 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 a linear relaxation of the mixed-integer problem, which can be more efficiently solved while preserving the soundness of the certificate.

heading: 7 LIMITATIONS
text: The main limitation of our approach is that it assumes softly local models. While it can be applied to arbitrary multi-output classifiers, it 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 of the samples for each output. As discussed in Section A.1, 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 a single smoothing distribution. Still, future work should try to improve the sample efficiency of randomized smoothing (for example by developing more methods for de-randomized smoothing (Levine & Feizi, 2020)).Any such advance could then be incorporated into our localized smoothing framework.

heading: 8 EXPERIMENTAL EVALUATION
text: Our experimental evaluation has three objectives 1.) Verifying our main claim that localized randomized smoothing offers a better trade-off between accuracy and certifiable robustness than smoothing
2Because η(n) is the smallest value bTw(n) can take on, i.e. min b∈RDin+ bTw (n) d s.t. sum{b} ≤ p.
with i.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 predictions, regardless of correctness)3. As single-number metrics, we report the AUC of the certified accuracy/ratio functions w.r.t. adversarial budget (not to be confused with certifying some AUC metric). For localized smoothing, we evaluate both the naı̈ve collective certificate, i.e. certifying predictions independently (see Section 4), and the proposed LP-based certificate (using the linearly relaxed version from Appendix A.4). We compare our method to two baselines using i.i.d. randomized smoothing: The naı̈ve collective certificate and center smoothing (Kumar & Goldstein, 2021). For softly local models, the certificate of Schuchardt et al. (2021) is equivalent to the naı̈ve baseline. When used to certify the number of robust predictions, the segmentation certificate of Fischer et al. (2021) is at most as strong as the naı̈ve 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 on the experimental setup can be found in Section E.
8.1 SEMANTIC SEGMENTATION
Dataset and model. We evaluate our certificate for continuous data and l2 perturbations on the Pascal-VOC 2012 segmentation validation set. Training is performed on 10582 pairs of training samples extracted from SBD4 (Hariharan et al., 2011), 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 a U-Net segmentation model with a ResNet-18 backbone. To obtain accurate and robust smoothed classifiers, base models should be trained on the smoothing distribution. We thus train 51 different instances of our base model, augmenting the training data with a different σtrain ∈ {0, 0.01, . . . , 0.5}. At test time, when evaluating a baseline i.i.d. certificate with smoothing distribution N (0, σ), we load the model trained with σtrain = σ. To perform localized randomized smoothing, we choose parameters σmin, σmax ∈ R+ and partition all images into regular grids of size 4 × 6 (similar to
example Fig. 1). To classify pixels in grid cell (i, j), we sample noise for grid cell (k, l) using N (0, σ′), with σ′ ∈ [σmin, σmax] chosen proportional to the distance of (i, j) and (k, l) (more details in Section E.2.1). As the base model, we load the one trained with σtrain = σmin. 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 favor. But, in Section E.2.3, we also repeat our experiments using the same base model for i.i.d. and localized smoothing.
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 σ, there are σmin, σmax such that the locally smoothed model has higher accuracy and certifiable collective robustness than i.i.d. smoothing baselines using N (0, σ). Because σ, σmin, σmax ∈ R+, we can not evaluate all possible combinations. We therefore use the following scheme: We focus on the case σ ∈ [0, 0.5], which covers all distributions used in (Kumar & Goldstein, 2021) and
3In the case of image segmentation, we compute these metrics per image and then average over the dataset. 4Also known as ”Pascal trainaug”
(Fischer et al., 2021). First, we evaluate our two baselines for five σ ∈ {0.1, 0.2, 0.3, 0.4, 0.5}. This results in baseline models with diverse levels of accuracy and robustness (e.g. the accuracy of the naı̈ve 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 σ, we can find σmin, σmax such that the locally smoothed models attains higher accuracy and is certifiably more robust. Finally, to verify that {0.1, 0.2, 0.3, 0.4, 0.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 σ ∈ [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 a better trade-off.
Fig. 2 shows one example. For σ = 0.4, the naı̈ve i.i.d. baseline has an accuracy of 72.5%. With σmin = 0.25, σmax = 1.5, the proposed localized smoothing certificate yields both a higher accuracy of 76.4% and a higher certified accuracy for all . It can certify robustness for up to 1.825, compared to 1.45 of the baseline and the AUC of its certified accuracy curve is 43.1% larger. Fig. 2 also highlights the usefulness of the linear program we derived in Section 5: Evaluating the localized smoothing base certificates independently, i.e. computing the naı̈ve 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. Tables 1 and 2 summarize the first part 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 σ ∈ {0.3, 0.4, 0.5}, 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 a fine-grained search over [0, 0.5]. We find that there is no σ 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 or 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).

heading: 8.2 NODE CLASSIFICATION
text: 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 Predictions (APPNP) (Klicpera et al., 2019) and a 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 naı̈ve baseline. For both, the baseline and our localized smoothing certificate, we use sparsity-aware randomized smoothing (Bojchevski et al., 2020) , i.e. flip 1-bits and 0-bits with different probabilities (θ− and θ+, 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 certificate 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 partition the graph into 5 clusters and define parameters θ±min and θ ± max. When classifying a node in cluster i, we randomly smooth attributes in cluster j with θ+ij , θ − ij that are based on linearly interpolating in [θ−min, θ − max] and [θ − min, θ − max] based on the affinity of the clusters (details in Section E.3.1).
Evaluation. We first evaluate the new variance-based certificate and compare it to the certificate derived by Bojchevski et al. (2020). For this, we use only one cluster, meaning we use the same smoothing distribution for both. Fig. 11 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 a stronger, collective certificate.
The parameter space of our smoothing distributions is large. For the localized approach we have four continuous parameters, as we have to specify both the minimal and maximal noise values.
Therefore, it is difficult to show that our approach achieves a better accuracy-robustness trade-off over the whole noise space. However, we can investigate the accuracy-robustness trade-off within some areas of this space. For the localized approach we choose a few fixed combinations of the noise parameters θ±min and θ±max. To show our claim, we then optimise the baselines with parameters in an interval around our θ+min and θ − min. This is a 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, we see the certified accuracy of an APPNP model for a varying number of attribute additions and deletions (left and right respectively). To find the best distribution parameters for the baselines, we evaluated combinations of θ+ ∈ {0.04, 0.055, 0.07} and θ− ∈ [0.1, . . . , 0.827], using 11 equally spaced values for the interval. For adversarial additions, the best baseline yields a certified accuracy curve with an AUC of 4.51 compared to our 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 at = 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 to deletions, but often have weaker certificates for additions (which may be inherent to the variance smoothing base certificates). Due to 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-robustness 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 Section E.3.3).

heading: 9 CONCLUSION
text: In this work, we have proposed the first collective robustness certificate for softly local multi-output classifiers. It is 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 a strong collective robustness certificate. Experiments on image segmentation and node classification tasks demonstrate that localized smoothing can offer a better robustness-accuracy 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.

heading: 10 REPRODUCIBILITY STATEMENT
text: We prove all theoretic results that were not already derived in the main text in Appendices A to C. To ensure reproducibility of the experimental results we provide detailed descriptions of the evaluation process with the respective parameters in Section E.2 and Section E.3. Code will be made available to reviewers via an anonymous link posted on OpenReview, as suggested by the guidelines.

heading: 11 ETHICS STATEMENT
text: In this paper, we propose a method to increase the robustness of machine learning models against adversarial perturbations and to certify their robustness. We see this as 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 negatives, but it is necessary to discuss the ethical implications of the usage in any specific application area.

heading: A.1 SHARING SMOOTHING DISTRIBUTIONS AMONG OUTPUTS
text: In principle, our proposed certificate allows a different smoothing distribution Ψ(n) to be used per output gn of our base model. In practice, where we have to estimate properties of the smoothed classifier using Monte Carlo methods, this is 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 smoothing distribution. When making smoothed predictions or computing base certificates, we can then reuse the same samples for all outputs within each subsets.
More formally, we partition our Dout output dimensions into sets K(1), . . . ,K(Nout) with⋃̇Nout i=1 K(i) = {1, . . . , Dout}. (6)
We then associate each set K(i) with a smoothing distribution Ψ(i). For each base model output gn with n ∈ K(i), we then use smoothing distribution Ψ(i) to construct the smoothed output fn, e.g. fn(x) = argmaxy∈Y Prz∼Ψ(i) [f(x+ z) = y] (note that we use a different smoothing paradigm for binary data, see Section 5).

heading: A.2 QUANTIZING CERTIFICATE PARAMETERS
text: Recall that our base certificates from Section 5 are defined by a linear inequality: A prediction yn = fn(x) is robust to a perturbed input x′ ∈ XDin if ∑D d=1 w (n) d · |x′d − xd| p < η(n), for some p ≥ 0. The weight vectors w(n) ∈ RDin only depend on the smoothing distributions. A side of effect of sharing the same smoothing Ψ(i) among all outputs from a set K(i), as discussed in the previous section, is that the outputs also share the same weight vector w(i) ∈ RDin with ∀n ∈ K(i) : w(i) = w(n). Thus, for all smoothed outputs fn with n ∈ K(i), the smoothed prediction yn is robust if ∑D d=1 w (i) d · |x′d − xd| p < η(n).
Evidently, the base certificates for outputs from a set K(i) only differ in their parameter η(n). Recall that in our collective linear program we use a vector of variables t ∈ {0, 1}Dout to indicate which predictions are robust according to their base certificates (see Section 6). If there are two outputs fn and fm with η(n) = η(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(i), we only need one indicator variable per unique η(n). By quantizing the η(n) within each subset K(i) (for example by defining equally sized bins between minn∈K(i) η(n) and maxn∈K(i) η(n) ), we can ensure that there is always a fixed number Nbins of indicator variables per subset. This way, we can reduce the number of indicator variables from Dout to Nout ·Nbins. To implement this idea, we define matrix of thresholds E ∈ RNout×Nbins with ∀i : min {Ei,:} ≤ minn∈K(i) ({ η(n) | n ∈ K(i) }) . We then define a function ξ : {1, . . . , Nout} × R→ R with
ξ(i, η) = max ({Ei,j | j ∈ {1, . . . , Nbins ∧ Ei,j < η}) (7) that quantizes base certificate parameter η from output subset K(i) by mapping it to the next smallest threshold in Ei,:. For feasibility, like in Section 6 we need to compute the constant η(i) = min
b∈RDin+ bTw (i) d s.t. sum{b} ≤ p to ensure feasibility of the problem. Note that, be-
cause all outputs from a subset K(i) share the same weight vector w(i), we only have to compute this constant once per subset. We can bound the collective robustness of the targeted dimensions T of our vector of predictions y = f(x) as follows:
min ∑
i∈{1,...,Nout} ∑ j∈{1,...,Nbins} Ti,j ∣∣∣{n ∈ T ∩K(i) ∣∣∣ξ (i, η(n)) = Ei,j }∣∣∣ (8) s.t. ∀i, j : bTw(i) ≥ Ti,jη(i) + (1− Ti,j)Ei,j , sum{b} ≤ p (9)
b ∈ RDin+ , T ∈ {0, 1}Nout×Nbins . (10) Constraint Eq. 9 ensures that Ti,j is only set to 0 if bTw(i) ≥ Ei,j , i.e. all predictions from subset K(i) whose base certificate parameter η(n) is quantized to Ei,j are no longer robust. When this is the case, the objective function decreases by the number of these predictions. For Nout = Dout, Nbins = 1 and En,1 = η(n), we recover our general certificate from Section 6. Note that, if the quantization maps any parameter η(n) to a smaller number, the set H(n) becomes more restrictive, i.e. yn is considered robust to a smaller set of perturbed inputs. Thus, Eq. 8 is a lower bound on our general certificate from Section 6.

heading: A.3 SHARING NOISE LEVELS AMONG INPUTS
text: Similar to how partitioning the output dimensions allows us to control the number of output variables t, partitioning the input dimensions and using the same noise level within each partition allows us to control the number of variables b that model the allocation of adversarial budget.
Assume that we have partitioned our output dimensions into Nout subsets K(1), . . . ,K(Nout , with outputs in each subset sharing the same smoothing distribution Ψ(i), as explained in Section A.1.
Let us now define Nin input subsets J(1), . . . , J(Nin) with⋃̇Nout i=1 J(i) = {1, . . . , Dout}. (11) Recall that a prediction yn = fn(x) with n ∈ K(i) is robust to a perturbed input x′ ∈ XDin if ∑D d=1 w (i) d · |x′d − xd| p < η(n) and that the weight vectors w(i) only depend on the smoothing distributions. Assume that we choose each smoothing distribution Ψ(i) such that ∀l ∈ {1, . . . , Nin},∀d, d′ ∈ J(l) : w(i)d = w (i) d′ , i.e. all input dimensions within each set J(l) have the same weight. This can be achieved by choosing Ψ(i) so that all dimensions in each input subset Jl are smoothed with the noise level (note that we can still use different Ψ(i), i.e. different noise levels for smoothing different sets of outputs). For example, one could use a Gaussian distribution with covariance matrix Σ = diag (σ)2 with ∀l ∈ {1, . . . , Nin},∀d, d′ ∈ J(l) : σd = σd′ . In this case, the evaluation of our base certificates can be simplified. Prediction yn = fn(x) is robust to a perturbed input x′ ∈ XDin if
D∑ d=1 w (i) d · |x ′ d − xd| p < η(n) (12)
= Nin∑ l=1 u(i) · ∑ d∈J(l) |x′d − xd| p  < η(n), (13) with u ∈ RNin and ∀i ∈ {1, . . . , Nout},∀l ∈ {1, . . . , Nin},∀d ∈ J : uil = wid. That is, we can replace each weight vector w(i) that has one weight w(i)d per input dimension d with a smaller weight vector u(i) with one weight u(i)l per input subset J(l).
For our linear program, this means that we no longer need a budget vector b ∈ RDin+ to model the element-wise distance |x′d − xd|
p in each dimension d. Instead, we can use a smaller budget vector b ∈ RNin+ to model the overall distance within each input subset J(l), i.e. ∑ d∈J(l) |x′d − xd|
p. Combined with the quantization of certificate parameters from the previous section, our optimization problem becomes
min ∑
i∈{1,...,Nout} ∑ j∈{1,...,Nbins} Ti,j ∣∣∣{n ∈ T ∩K(i) ∣∣∣ξ (i, η(n)) = Ei,j }∣∣∣ (14) s.t. ∀i, j : bTu(i) ≥ Ti,jη(i) + (1− Ti,j)Ei,j , sum{b} ≤ p, (15)
b ∈ RNin+ , T ∈ {0, 1}Nout×Nbins . (16)
with u ∈ RNin and ∀i ∈ {1, . . . , Nout},∀l ∈ {1, . . . , Nin},∀d ∈ J : ωil = wid. For Nout = Dout, Nin = Din, Nbins = 1 and En,1 = η(n), we recover our general certificate from Section 6.
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, we use a budget vector b ∈ NNin0 with ∀l ∈ {1, . . . , Nin} : bl ≤ ∣∣J(l)∣∣, instead of a continuous budget vector b ∈ RNin+ .

heading: A.4 LINEAR RELAXATION
text: Combining the previous steps allows us to reduce the number of problem variables and linear constraints from Din + Dout and Dout + 1 to Nin + Nout · Nbins and Nout · Nbins + 1, respectively. Still, finding an optimal solution to the mixed-integer 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 ∈ {0, 1}Dout can be relaxed to t ∈ [0, 1]Dout . When using the certificate with quantized base certificate parameters from Section A.2 or Section A.3, the binary matrix T ∈ [0, 1]Nout×Nbins can be relaxed to T ∈ [0, 1]Nout×Nbins . Conceptually, this means that predictions can be partially certified, i.e. tn ∈ (0, 1)
or Ti,j ∈ (0, 1). In particular, a prediction can be partially certified even if we know that is impossible to attack under the collective perturbation model Bx = { x′ ∈ XDin | ||x′ − x||p ≤ } . Just like Schuchardt et al. (2021), who encountered the same problem with their collective certificate, we circumvent this issue by first computing a set L ⊆ T of all targeted predictions in T that are guaranteed to always be robust:
L = { n ∈ T ∣∣∣∣∣ ( max x∈Bx D∑ d=1 w (n) d · |x ′ d − xd| p ) < η(n) } (17)
= { n ∈ T ∣∣∣max(max{w(n)} · p, 0) < η(n)} . (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.e. the dimension with the largest weight – unless all weights are negative. Because we know that all predictions with indices in L are robust, we do not have to include them in the collective optimization problem and can instead compute
|L|+ min x′∈Bx ∑ n∈T\L I [ x′ ∈ H(n) ] . (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 ∈ {0, 1}Din can be relaxed to b ∈ [0, 1]Din . When using the modified collective certificate from Section A.3, the budget variables with b ∈ NNin0 can be relaxed to b ∈ R Nin + . The additional
constraint ∀l ∈ {1, . . . , Nin} : bl ≤ ∣∣J(l)∣∣ can be kept in order to model that the adversary cannot flip (or partially flip) more bits than are present within each input subset J(l).

heading: B BASE CERTIFICATES
text: In the following, we show why the base certificates presented in Section 5 hold and present alternatives for other collective perturbation models.
B.1 GAUSSIAN SMOOTHING FOR l2 PERTURBATIONS OF CONTINUOUS DATA
Proposition 1. Given an output gn : RDin → Y, let fn(x) = argmaxy∈Y Prz∼N (x,Σ) [gn(z) = y] be the corresponding smoothed output with Σ = diag (σ)2 andσ ∈ RDin+ . Given an inputx ∈ RDin and smoothed prediction yn = fn(x), let q = Prz∼N (x,Σ) [gn(z) = yn]. Then, ∀x′ ∈ H(n) : fn(x ′) = yn with H(n) defined as in Eq. 2, wd = 1σd2 , η = ( Φ(−1)(q) )2 and κ = 2.
Proof. Based on the definition of the base certificate interface, we need to show that, ∀x′ ∈ H : fn(x ′) = yn with
H = { x′ ∈ RDin ∣∣∣∣∣ Din∑ d=1 1 σ2d · |xd − x′d|2 < ( Φ−1(q) )2} . (20)
Eiras et al. (2021) have shown that under the same conditions as above, but with a general covariance matrix Σ ∈ RDin×Din+ , a prediction yn is certifiably robust to a perturbed input x′ if√
(x− x′)Σ−1(x− x′) < 1 2
( Φ−1(q)− Φ−1(q′) ) , (21)
where q′ = maxy′n 6=yn Prz∼N (x,Σ) [gn(z) = y ′ n] is the probability of the second most likely prediction under the smoothing distribution. Because the probabilities of all possible predictions have to sum up to 1, we have q′ ≤ 1 − q. Since Φ−1 is monotonically increasing, we can obtain a lower bound on the r.h.s. of Eq. 21 and thus a more pessimistic certificate by substituting 1 − q
for q′ (deriving such a ”binary certificate” from a ”multiclass certificate” is common in randomized smoothing and was already discussed in (Cohen et al., 2019)):√
(x− x′)Σ−1(x− x′) < 1 2
( Φ−1(q)− Φ−1(1− q) ) , (22)
In our case, Σ is a diagonal matrix diag (σ)2 with σ ∈ RDin+ . Thus Eq. 22 is equivalent to√√√√Din∑ d=1 (xd − x′d) 1 σ2d (xd − x′d) < 1 2 ( Φ−1(q)− Φ−1(1− q) ) . (23)
Finally, using the fact that Φ−1(q)−Φ−1(1− q) = 2Φ−1(q) and eliminating the square root shows that we are certifiably robust if
Din∑ d=1 1 σ2d · |xd − x′d|2 < ( Φ−1(q) )2 . (24)
B.1.1 UNIFORM SMOOTHING FOR l1 PERTURBATIONS OF CONTINUOUS DATA
An alternative base certificate for l1 perturbations is again due to Eiras et al. (2021). Using uniform instead of Gaussian noise later allows us to collective certify robustness to l1-norm-bound perturbations. In the following U(x,λ) with x ∈ RD, λ ∈ RD+ refers to a vector-valued random distribution in which the d-th element is uniformly distributed in [xd − λd, xd + λd]. Proposition 2. Given an output gn : RDin → Y, let f(x) = argmaxy∈Y Prz∼U(x,λ) [g(z) = y] be the corresponding smoothed classifier with λ ∈ RDin+ . Given an input x ∈ RDin and smoothed prediction y = f(x), let p = Prz∼U(x,λ) [g(z) = y]. Then, ∀x′ ∈ H(n) : fn(x′) = yn with H(n) defined as in Eq. 2, wd = 1/λd, η = Φ−1(q) and κ = 1.
Proof. Based on the definition of H(n), we need to prove that ∀x′ ∈ H : fn(x′) = yn with
H = { x′ ∈ RDin |
Din∑ d=1 1 λd · |xd − x′d| < Φ−1(q)
} , (25)
Eiras et al. (2021) have shown that under the same conditions as above, a prediction yn is certifiably robust to a perturbed input x′ if
Din∑ d=1 | 1 λd · (xd − x′d) | < 1 2 ( Φ−1(q)− Φ−1(1− q) ) , (26)
where q′ = maxy′n 6=yn Prz∼U(x,λ) [gn(z) = y ′ n] is the probability of the second most likely prediction under the smoothing distribution. As in our previous proof for Gaussian smoothing, we can obtain a more pessimistic certificate by substituting 1−q for q′. Since Φ−1(q)−Φ−1(1−q) = 2Φ−1(q) and all λd are non-negative, we know that our prediction is certifiably robust if
Din∑ d=1 1 λd · |xd − x′d| < Φ−1(p). (27)
B.2 VARIANCE SMOOTHING
We propose variance smoothing as a 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 to arbitrary data types. We focus on discrete data, but all results can
be generalized from discrete to continuous data by replacing any sum over probability mass functions with integrals over probability density functions. We first derive a general form of variance smoothing before discussing our 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 softmax scores. That is, given base model g : X→ ∆|Y| mapping from an arbitrary discrete input space X to scores from the |Y|-dimensional probability simplex ∆|Y|, we define the smoothed classifier f(x) = argmaxy∈YEz∼Ψ(x) [g(z)y]. Here, Ψ(x) is an arbitrary distribution over X parameterized by x, e.g a Normal distribution with mean x. The smoothed classifier does not return the most likely prediction, but the prediction associated with the highest expected softmax score.
Given an input x ∈ X, smoothed prediction y = f(x) and a perturbed input x′ ∈ X, we want to determine whether f(x′) = y. By definition of our smoothed classifier, we know that f(x′) = y if y is the label with the highest expected softmax score. In particular, we know that f(x′) = y if y’s softmax score is larger than all other softmax scores combined, i.e.
Ez∼Ψ(x′) [g(z)y] > 0.5 =⇒ f(x′) = y. (28)
Computing Ez∼Ψ(x′) [g(z)y] exactly is usually not tractable – especially if we later want to evaluate robustness to many x′ from a whole perturbation model B ⊆ X. Therefore, we compute a lower bound on Ez∼Ψ(x′) [g(z)y]. If even this lower bound is larger than 0.5, we know that prediction y is certainly robust. For this, we define a set of functions H with gy ∈ H and compute the minimum softmax score across all functions from H:
min h∈H
Ez∼Ψ(x′) [h(z)] > 0.5 =⇒ f(x′) = y. (29)
For our variance smoothing approach, we define H to be the set of all functions that have a larger or equal expected value and a smaller or equal variance, compared to our base model g applied to unperturbed input x. Let µ = Ez∼Ψ(x) [g(z)y] be the expected softmax score of our base model g for label y. Let σ2 = Ez∼Ψ(x) [ (g(z)y − ν)2 ] be the expected squared distance of the softmax
score from a scalar ν ∈ R. (Choosing ν = µ yields the variance of the softmax score. An arbitrary ν is only needed for technical reasons related to Monte Carlo estimation Section C.2). Then, we define
H = { h : X→ R ∣∣∣ Ez∼Ψ(x) [h(z)] ≥ µ ∧ Ez∼Ψ(x) [(h(z)− ν)2] ≤ σ2} (30) Clearly, by the definition of µ and σ2, we have gy ∈ H. Note that we do not restrict functions from H to the domain [0, 1], but allow arbitrary real-valued outputs.
By evaluating Eq. 28 with H 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 Π of all probability mass functions over X, any two probability mass functions π1, π2 ∈ Π fulfill∑
z∈X
π2(z) π1(z) π2(z) ≥ 1. (31)
Proof. For a fixed probability mass function π1, Eq. 31 is lower-bounded by the minimal expected likelihood ratio that can be achieved by another π̃(z) ∈ Π:∑
z∈X
π2(z) π1(z) π2(z) ≥ min π̃∈Π ∑ z∈X π̃(z) π1(z) π̃(z). (32)
The r.h.s. term can be expressed as the constrained optimization problem
min π̃ ∑ z∈X π̃(z) π1(z) π̃(z) s.t. ∑ z∈X π̃(z) = 1 (33)
with the corresponding dual problem
max λ∈R min π̃ ∑ z∈X π̃(z) π1(z) π̃(z) + λ
( −1 +
∑ z∈X π̃(z)
) . (34)
The inner problem is convex in each π̃(z). Taking the gradient w.r.t. to π̃(z) for all z ∈ X shows that it has its minimum at ∀z ∈ X : π̃(z) = −λπ1(z)2 . Substituting into Eq. 34 results in
max λ∈R ∑ z∈X λ2π1(z) 2 4π1(z) + λ
( −1−
∑ z∈X λπ1(z) 2
) (35)
= max λ∈R −λ2 ∑ z∈X π1(z) 4 − λ (36)
= max λ∈R −λ
2
4 − λ (37)
= 1. (38)
Eq. 37 follows from the fact that π1(z) is a valid probability mass function. Due to duality, the optimal dual value 1 is a lower bound on the optimal value of our primal problem Eq. 31.
Lemma 2. Given a probability distribution D over a R and a scalar ν ∈ R, let µ = Ez∼D and ξ = Ez∼D [ (z − ν)2 ] . Then ξ ≥ (µ− ν)2
Proof. Using the definitions of µ and ξ, as well as some simple algebra, we can show:
ξ ≥ (µ− ν)2 (39) ⇐⇒ Ez∼D [ (z − ν)2 ] ≥ µ2 − 2µν + ν2 (40)
⇐⇒ Ez∼D [ z2 − 2zν + ν2 ] ≥ µ2 − 2µν + ν2 (41)
⇐⇒ Ez∼D [ z2 − 2zν + ν2 ] ≥ µ2 − 2µν + ν2 (42)
⇐⇒ Ez∼D [ z2 ] − 2µν + ν2 ≥ µ2 − 2µν + ν2 (43)
⇐⇒ Ez∼D [ z2 ] ≥ µ2 (44)
It is well known for the variance that Ez∼D [ (z − µ)2 ] = Ez∼D [ z2 ] − µ2. Because the variance is always non-negative, the above inequality holds.
Using the previously described approach and lemmata, we can show the soundness of the following robustness certificate:
Theorem 3. Given a model g : X → ∆|Y| mapping from discrete set X to scores from the |Y|-dimensional probability simplex, let f(x) = argmaxy∈YEz∼Ψ(x) [g(z)y] be the corresponding smoothed classifier with smoothing distribution Ψ(x) and probability mass function πx(z) = Prz̃∼Ψ(x) [z̃ = z]. Given an input x ∈ X and smoothed prediction y = f(x), let µ = Ez∼Ψ(x) [g(z)y] and σ2 = Ez∼Ψ(x) [ (g(z)y − ν)2 ] with ν ∈ R. If ν ≤ µ, we know that f(x′) = y if ∑ z∈X πx′(z) 2 πx(z) < 1 + 1 σ2 − (µ− ν)2 ( µ− 1 2 ) . (45)
Proof. Following our discussion above, we know that f(x′) = y if Ez∼Ψ(x′) [g(z)y] > 0.5 with H defined as in Section 5. We can compute a (tight) lower bound on minh∈H Ez∼Ψ(x′) by following the functional optimization approach for randomized smoothing proposed by Zhang et al. (2020). That is, we solve a dual problem in which we optimize the value h(z) for each z ∈ X. By the definition of the set H, our optimization problem is
min h:X→R Ez∼Ψ(x′) [h(z)] s.t. Ez∼Ψ(x) [h(z)] ≥ µ, Ez∼Ψ(x) [ (h(z)− ν)2 ] ≤ σ2.
The corresponding dual problem with dual variables α, β ≥ 0 is
max α,β≥0 min h:X→R Ez∼Ψ(x′) [h(z)]
+α ( µ− Ez∼Ψ(x) [h(z)] ) + β ( Ez∼Ψ(x) [ (h(z)− ν)2 ] − σ2 ) .
(46)
We first move move all terms that don’t involve h out of the inner optimization problem:
= max α,β≥0 αµ−βσ2 + min h:X→R
Ez∼Ψ(x′) [h(z)]−αEz∼Ψ(x) [h(z)]+βEz∼Ψ(x) [ (h(z)− ν)2 ] (47)
Writing out the expectation terms and combining them into one sum (or – in the case of continuous X – one integral), our dual problem becomes
= max α,β≥0 αµ− βσ2 + min h:X→R ∑ z∈X h(z)πx′(z)− αh(z)πx(z) + β (h(z)− ν)2 πx(z) (48)
(recall that πx′ and πx′ refer to the probability mass functions of the smoothing distributions). The inner optimization problem can be solved by finding the optimal h(z) in each point z:
= max α,β≥0 αµ− βσ2 + ∑ z∈X min h(z)∈R h(z)πx′(z)− αh(z)πx(z) + β (h(z)− ν)2 πx(z) (49)
Because β ≥ 0, each inner optimization problem is convex in h(z). We can thus find the optimal h∗(z) by setting the derivative to zero:
d
dh(z) h(z)πx′(z)− αh(z)πx(z) + β (h(z)− ν)2 πx(z) ! = 0 (50)
⇐⇒ πx′(z)− απx(z) + 2β (h(z)− ν)πx(z) ! = 0 (51)
=⇒ h∗(z) = − πx ′(z)
2βπx(z) +
α
2β + ν. (52)
Substituting into Eq. 48 and simplifying leaves us with the dual problem
max α,β≥0
αµ− βσ2 − α 2
4β +
α 2β − αν + ν − 1 4β ∑ z∈X πx′(z) 2 πx(z) (53)
In the following, let us use ρ = ∑ z∈X πx′ (z) 2 πx(z) as a shorthand for the expected likelihood ratio. The problem is concave in α. We can thus find the optimum α∗ by setting the derivative to zero, which gives us α∗ = 2β(µ− ν) + 1. Because β ≥ 0 and ou theorem assumes that ν ≤ µ, α∗ is a feasible solution to the dual problem. Substituting into Eq. 53 and simplifying results in
max β≥0
α∗µ− βσ2 − α ∗2 4β + α∗ 2β − α∗ν + ν − 1 4β ρ (54)
= max β≥0
β ( (µ− ν)2 − σ2 ) + µ+ 1
4β (1− ρ) . (55)
Lemma 1 shows that the expected likelihood ratio ρ is always greater than or equal to 1. Lemma 2 shows that (µ− ν)2 − σ2 ≤ 0. Therefore Eq. 55 is concave in β. The optimal value of β can again be found by setting the derivative to zero:
β∗ =
√ 1− ρ
4 ((µ− ν)2 − σ2) . (56)
Recall that our theorem assumes σ2 ≥ (µ− ν)2 and thus β∗ is real valued. Substituting into Eq. 56 shows that the maximum of our dual problem is
µ+ √ (1− p) ((µ− ν)2 − σ2). (57)
By duality, this is a lower bound on our primal problem minh∈H Ez∼Ψ(x′) [h(z)]. We know that our prediction is certifiably robust, i.e. f(x) = y, if minh∈H Ez∼Ψ(x′) [h(z)] > 0.5. So, in particular, our prediction is robust if
µ+ √ (1− ρ) ((µ− ν)2 − σ2) > 0.5 (58)
⇐⇒ ρ < 1 + 1 σ2 − (µ− ν)2
( µ− 1
2
)2 (59)
⇐⇒ ∑ z∈X πx′(z) 2 πx(z) < 1 +
1
σ2 − (µ− ν)2
( µ− 1
2
)2 (60)
The last equivalence is the result of inserting the definition of the expected likelihood ratio ρ.
With Theorem 3 in place, we can certify robustness for arbitrary smoothing distributions, assuming we can compute the expected likelihood ratio. When we are working with discrete data and the 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.

heading: B.2.1 BERNOULLI VARIANCE SMOOTHING FOR PERTURBATIONS OF BINARY DATA
text: We begin by proving the base certificate presented in Section 5. Recall that we we use a smoothing distribution F(x,θ) with θ ∈ [0, 1]Din that independently flips the d’th bit with probability θd, i.e. for x, z ∈ {0, 1}Din and z ∼ F(x,θ) we have Pr[zd 6= xd] = θd. Theorem 1. Given an output gn : {0, 1}Din → ∆|Y| mapping to scores from the |Y|-dimensional probability simplex, let fn(x) = argmaxy∈YEz∼F(x,θ) [gn(z)y] be the corresponding smoothed classifier with θ ∈ [0, 1]Din . Given an input x ∈ {0, 1}Din and smoothed prediction yn = fn(x), let µ = Ez∼F(x,θ) [gn(z)y] and σ2 = Varz∼F(x,θ) [gn(z)y]. Then, ∀x′ ∈ H(n) : fn(x′) = yn with H(n) defined as in Eq. 2, wd = ln ( (1−θd)2 θd + (θd) 2 1−θd ) , η = ln ( 1 + 1σ2 ( µ− 12 )2) and κ = 0.
Proof. Based on our definition of the base certificate interface from Section 5, we must show that ∀x′ ∈ H : fn(x′) = yn with
H = { x′ ∈ {0, 1}Din ∣∣∣∣∣ Din∑ d=1 ln ( (1− θd)2 θd + (θd) 2 1− θd ) · |x′d − xd|0 < ln ( 1 + 1 σ2 ( µ− 1 2 )2)} , (61) Because all bits are flipped independently, our probability mass function πx(z) = Prz̃∼Ψ(x) [z̃ = z] factorizes:
πx(z) = Din∏ d=1 πxd(zd) (62)
with
πxd(zd) = { θd if zd 6= xd 1− θd else . (63)
Thus, our expected likelihood ratio can be written as
∑ z∈{0,1}Din πx′(z) 2 πx(z) = ∑ z∈{0,1}Din Din∏ d=1 πx′d(zd) 2 πxd(zd) = Din∏ d=1 ∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) . (64)
For each dimension d, we can distinguish two cases: If both the perturbed and unperturbed input are the same in dimension d, i.e. x′d = xd, then πx′ d (z)
πxd (z) = 1 and thus
∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) = ∑ zd∈{0,1} πx′d(zd) = θd + (1− θd) = 1. (65)
If the perturbed and unperturbed input differ in dimension d, then∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) = (1− θd)2 θd + (θd) 2 1− θd . (66)
Therefore, the expected likelihood ratio is
Din∏ d=1 ∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) = Din∏ d=1
( (1− θd)2
θd +
(θd) 2
1− θd
)|x′d−xd| . (67)
Due to Theorem 3 (and using ν = µ when computing the variance), we know that our prediction is robust, i.e. fn(x′) = yn, if ∑
z∈{0,1}Din
πx′(z) 2
πx(z) < 1 +
1
σ2
( µ− 1
2
)2 (68)
⇐⇒ Din∏ d=1
( (1− θd)2
θd +
(θd) 2
1− θd
)|x′d−xd| < 1 + 1
σ2
( µ− 1
2
)2 (69)
⇐⇒ Din∑ d=1 ln
( (1− θd)2
θd +
(θd) 2
1− θd
) |x′d − xd| < ln ( 1 + 1
σ2
( µ− 1
2
)2) . (70)
Because xd and x′d are binary, the last inequality is equivalent to
Din∑ d=1 ln
( (1− θd)2
θd +
(θd) 2
1− θd
) |x′d − xd|0 < ln ( 1 + 1
σ2
( µ− 1
2
)2) . (71)

heading: B.2.2 SPARSITY-AWARE VARIANCE SMOOTHING FOR PERTURBATIONS OF BINARY DATA
text: Sparsity-aware randomized smoothing (Bojchevski et al., 2020) is an alternative smoothing approach 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-aware distribution S(x,θ+,θ−) with x ∈ {0, 1}Din and addition and deletion probabilities θ+,θ− ∈ [0, 1]Din , we have:
Pr[zd = 0] = ( 1− θ+d )1−xd · (θ−d )xd , Pr[zd = 1] = ( θ+d )1−xd · (1− θ−d )xd .
The Bernoulli smoothing distribution we discussed in the previous section is a special case of sparsity-aware smoothing with θ+ = θ−. The runtime of the robustness certificate derived by Bojchevski et al. (2020) increases exponentially with the number of unique values in θ+ and θ−, 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 gn : RDin → ∆|Y| mapping to scores from the |Y|-dimensional probability simplex, let fn(x) = argmaxy∈YEz∼S(x,θ+,θ−) [gn(z)y] be the corresponding smoothed classifier with θ+,θ− ∈ [0, 1]Din . Given an input x ∈ {0, 1}Din and smoothed prediction yn = fn(x), let µ = Ez∼S(x,θ+,θ−) [gn(z)y] and σ2 = Varz∼S(x,θ+,θ−) [gn(z)y]. Then, ∀x′ ∈ H : fn(x′) = y for
H = { x′ ∈ {0, 1}Din |
Din∑ d=1 γ+d · I [xd = 0 6= x ′ d] + γ − d · I [xd = 1 6= x ′ d] < η
} , (72)
where γ+,γ− ∈ RDin , γ+d = ln ( (θ−d ) 2
1−θ+d +
(1−θ−d ) 2
θ+d
) , γ−d = ln ( (1−θ+d ) 2
θ−d +
(θ+d ) 2 1−θ−d .
) and η =
ln ( 1 + 1σ2 ( µ− 12 )2) .
Proof. Just like with the Bernoulli distribution we discussed in the previous section, all bits are flipped independently, meaning our probability mass function πx(z) = Prz̃∼Ψ(x) [z̃ = z] factorizes:
πx(z) = Din∏ d=1 πxd(zd) (73)
with
πxd(zd) = { θd if zd 6= xd 1− θd else . (74)
As before, our expected likelihood ratio can be written as∑ z∈{0,1}Din πx′(z) 2 πx(z) = ∑ z∈{0,1}Din Din∏ d=1 πx′d(zd) 2 πxd(zd) = Din∏ d=1 ∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) . (75)
We can now distinguish three cases. If both the perturbed and unperturbed input are the same in dimension d, i.e. x′d = xd, then πx′ d (z)
πxd (z) = 1 and thus
∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) = ∑ zd∈{0,1} πx′d(zd) = 1. (76)
If x′d = 1 and xd = 0, i.e. a bit was added, then∑ zd∈{0,1} πx′d(z) 2 πxd(z) = ∑ zd∈{0,1} π1(zd) 2 π0(zd) = π1(0) 2 π0(0) + π1(1) 2 π0(1) = ( θ−d )2 1− θ+d + ( 1− θ−d )2 θ+d
(77)
If x′d = 0 and xd = 1, i.e. a bit was deleted, then∑ zd∈{0,1} πx′d(z) 2 πxd(z) = ∑ zd∈{0,1} π0(zd) 2 π1(zd) = π0(0) 2 π1(0) + π0(1) 2 π1(1) = ( 1− θ+d )2 θ−d + ( θ+d )2 1− θ−d . (78)
Therefore, the expected likelihood ratio is
Din∏ d=1 ∑ zd∈{0,1} πx′d(zd) 2 πxd(zd) (79)
= Din∏ d=1
( ( θ−d )2
1− θ+d +
( 1− θ−d )2 θ+d )I[xd=06=x′d|](( 1− θ+d )2 θ−d + ( θ+d )2 1− θ−d )I[xd=16=x′d|] (80)
= Din∏ d=1 exp ( γ+d )I[xd=06=x′d|] · exp (γ−d )I[xd=16=x′d|] . (81)
In the last equation, we have simple used the shorthands γ+d and γ − d , as defined in Theorem 2 Due to Theorem 3 (and using ν = µ when computing the variance), we know that our prediction is robust, i.e. fn(x′) = yn, if ∑
z∈{0,1}Din
πx′(z) 2
πx(z) < 1 +
1
σ2
( µ− 1
2
)2 (82)
⇐⇒ Din∏ d=1 exp ( γ+d )I[xd=06=x′d|] · exp (γ−d )I[xd=16=x′d|] < 1 + 1σ2 ( µ− 1 2 )2 (83)
⇐⇒ Din∑ d=1 γ+d · I [xd = 0 6= x ′ d|] · γ−d · I [xd = 1 6= x ′ d|] < ln
( 1 + 1
σ2
( µ− 1
2
)2) . (84)
It should be noted that this certificate does not comply with our interface for base certificates Section 5, meaning we can not directly use it to certify robustness to norm-bound perturbations using our collective linear program from Section 6. We can however use it to certify collective robustness to the more refined threat model used in (Schuchardt et al., 2021): Let the set of admissible perturbed inputs be Bx = { x′ ∈ {0, 1}Din | ∑Din d=1 [xd = 0 6= x′d|] ≤ + ∧ ∑Din d=1 [xd = 1 6= x′d|] ≤ − } with
+, y ∈ N0 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-prediction base certificates into a collective certificate for our new collective perturbation model. As discussed in, we can bound the number of predictions that are robust to simultaneous attacks by minimizing the number of predictions that are certifiably robust according to their base certificates:
min x′∈Bx ∑ n∈T I [fn(x ′) = yn] ≥ min x′∈Bx ∑ n∈T I [ x′ ∈ H(n) ] . (85)
Inserting the linear inequalities characterizing our perturbation model and base certificates results in:
min x′∈{0,1}Din ∑ n∈T I [ Din∑ d=1 γ+d · I [xd = 0 6= x ′ d] + γ − d · I [xd = 1 6= x ′ d] < η (n) ] (86)
s.t. Din∑ d=1 [xd = 0 6= x′d|] ≤ +, Din∑ d=1 [xd = 1 6= x′d|] ≤ −. (87)
Instead of optimizing over the perturbed input x′, we can define two vectors b+, b− ∈ {0, 1}Din that indicate in which dimension bits were added or deleted. Using these new variables, Eq. 86 can be rewritten as
min b+,b−∈{0,1}Din ∑ n∈T I [( γ+ )T b+ + ( γ− )T b− < η(n) ] (88)
s.t. sum{b+} ≤ +, sum{b−} ≤ −, (89)∑ d|xd=1 b+d = 0, ∑ d|xd=0 b−d = 0. (90)
The last two constraints ensure that bits can only be deleted where xd = 1 and bits can only be added where xd = 0. Finally, we can use the procedure for replacing the indicator functions with indicator variables that we discussed in Section 6). Let η(n) be the minimum values the weighted sums in the objective function can take on:
η(n) = min b+,b−∈{0,1}Din
( γ+ )T b+ + ( γ− )T b− (91)
s.t. sum{b+} ≤ +, sum{b−} ≤ −, (92)∑ d|xd=1 b+d = 0, ∑ d|xd=0 b−d = 0. (93)
The above problem can be solved by finding all negative entries of γ+ and γ− and then summing up the min ( sum {1− x} , b+d ) (or min ( sum {x} , b−d ) , respectively) smallest ones. Using these η(n) and binary indicator variables t ∈ {0, 1}Dout , we can restate the above problem as the mixed-integer problem
min b+,b−∈{0,1}Din ,t∈{0,1}Dout ∑ n∈T tn (94)
s.t. ( γ+ )T b+ + ( γ− )T b− ≥ tnη(n) + (1− tn)η(n), (95)
sum{b+} ≤ +, sum{b−} ≤ −, (96)∑ d|xd=1 b+d = 0, ∑ d|xd=0 b−d = 0. (97)
The first constraint ensures that tn can only be set to 0 if the l.h.s. is greater or equal ηn, 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.

heading: C MONTE CARLO RANDOMIZED SMOOTHING
text: To make predictions and certify robustness, randomized smoothing requires computing certain properties of the distribution of a base model’s output, given an input smoothing distribution. For example, the certificate of Cohen et al. (2019) assumes that the smoothed model f predicts the most likely label output by base model g, given a smoothing distribution N (0, σ · 1): f(x) = argmaxy∈Y Prz∼N (0,σ·1) [g(x+ z) = y]. To certify the robustness of a smoothed prediction y = f(x) for a specific input x, we have to compute the probability q = Prz∼N (0,σ·1) [g(x+ z) = y] to then calculate the maximum certifiable radius σΦ−1(q) with standard-normal inverse CDF Φ−1. For complicated models like deep neural networks, computing such properties in closed form is usually not tractable. Instead, they have to 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 a candidate prediction ŷ, e.g. the most frequently predicted class. Then, a second round of N2 samples is 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 ŷ = f(x) with a certain probability (1 - α1). If this is not the case, one has to abstain from making a prediction (or generate a new candidate prediction). To certify the robustness of prediction ŷ, a final round ofN3 samples is taken to estimate all quantities needed for the certificate. In the case of (Cohen et al., 2019), we need to estimate the probability q = Prz∼N (0,σ·1) [g(x+ z) = ŷ] to compute the certificate σΦ−1(q), whose strength is monotonically increasing in q. To ensure that the certificate holds with high probability (1 - α2), we have to compute a probabilistic lower bound q ≤ 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 ∀x′ ∈ {x} : f(x′) = ŷ with high probability, i.e. whether the prediction is robust to input x′ that is the result of ”perturbing” clean input x 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.

heading: C.1 MONTE CARLO BASE CERTIFICATES FOR CONTINUOUS DATA
text: 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 certificate with Gaussian noise for l2 perturbations). We are given an input space XDin , label space Y, base model (or – in the case of multi-output classifiers – base model output) g : XDin → Y and smoothing distribution Ψ(x) (either multivariate Gaussian or multivariate uniform). To generate a candidate prediction, we apply the base classifier to N1 samples from the smoothing distribution in order to obtain predictions ( y(1), . . . , y(N1) ) and compute the majority prediction
ŷ = argmaxy∈Y { n | y(n) = ŷ } . Recall that for Gaussian and uniform noise, our certificate guarantees ∀x′ ∈ H : f(x) = ŷ with
H = { x′ ∈ XDin ∣∣∣∣∣ Din∑ d=1 wd · |x′d − xd|p < η }
with η = ( Φ−1(q) )2 or η = Φ−1(q) (depending on the distribution), q = Prz∼N (0,σ·1) [g(x+ z) = ŷ] and standard-normal inverse CDF Φ−1. To obtain a probabilistic certificate that holds with high probability 1−α, we need a probabilistic lower bound on η. Both η are monotonically increasing in q, i.e. we can bound them by finding a lower bound q on q. For this, we take N2 more samples from the smoothing distribution and compute a Clopper-Pearson lower confidence bound (Clopper & Pearson, 1934) on q. For abstentions, we use the aforementioned simple
mechanism: We test whether x ∈ H. Given the definition of H, this is equivalent to testing whether
0 < Φ−1(q)
⇐⇒ Φ(0) < q ⇐⇒ 0.5 < q.
If q ≤ 0.5, we abstain.

heading: C.2 MONTE CARLO VARIANCE SMOOTHING
text: In variance smoothing, we smooth a model’s softmax scores. That is, we are given an input space XDin , label space Y, base model (or – in the case of multi-output classifiers – base model output) g : XDin → ∆|Y| with |Y|-dimensional probability simplex ∆|Y| and smoothing distribution Ψ(x) (Bernoullli or sparsity-aware noise, in the case of binary data). To generate a candidate prediction, we apply the base classifier toN1 samples from the smoothing distribution in order to obtain vectors( s(1), . . . , s(N1) ) with s ∈ ∆|Y|, compute the average softmax scores s = 1N1 ∑N n=1 s and select the label with the highest score ŷ = arg maxy sy .
Recall that our certificate guarantees robustness if the optimal value of the following optimization problem is greater than 0.5:
min h:X→R Ez∼Ψ(x′) [h(z)] (98) s.t. Ez∼Ψ(x) [h(z)] ≥ µ, Ez∼Ψ(x) [ (h(z)− ν)2 ] ≤ σ2, (99)
with µ = Ez∼Ψ(x) [g(z)ŷ], σ2 = Ez∼Ψ(x) [ (g(z)ŷ − ν)2 ] and a fixed scalar ν ∈ R. To obtain a
probabilistic certificate, we have to compute a probabilistic lower bound on the optimal value of the optimization problem. Because it is a minimization problem, this can be achieved by loosening its constraints, i.e. computing a probabilistic lower bound µ on µ and a probabilistic upper bound σ2
on σ2.
Like in CDF-smoothing (Kumar et al., 2020), we bound the parameters using CDF-based nonparametric confidence intervals. Let F (s) = Prz∼Ψ(x) [g(z)ŷ ≤ s] be the CDF of the distribution of gŷ under the smoothing distribution Ψ(x). Define M thresholds ≤ 0τ1 ≤ τ2 . . . , τM−1 ≤ τM ≤ 1 with ∀m : τm ∈ [0, 1]. We then take N2 samples x(1), . . . ,x(N2) from the smoothing distribution to compute the empirical CDF F̃ (s) = ∑N2 n=1 I [ g(z(n))ŷ ≤ s ] . We can then use the DvoretzkyKeifer-Wolfowitz inequality (Dvoretzky et al., 1956) to compute an upper bound F̂ and a lower bound F on the CDF of gŷ:
F (s) = max ( F̃ (s)− υ, 0 ) ≤ F (s) ≤ min ( F̃ (s) + υ, 1 ) = F (s), (100)
with υ = √
ln 2/α 2·N2 , which holds with high probability (1− α). Using these bounds on the CDF, we
can bound µ = Ez∼Ψ(x) [g(z)ŷ] as follows (Anderson, 1969):
µ ≥ τM − τ1F (τ1) + M−1∑ m=1 (τm+1 − τm)F (τm). (101)
The parameter σ2 = Ez∼Ψ(x) [ (g(z)ŷ − ν)2 ] can be bounded in a similar fashion. Define
ξ0, . . . , ξM ∈ R+ with:
ξ0 = max κ∈[0,τ1]
( (κ− ν)2 ) ξM = max
κ∈[τM ,1]
( (κ− ν)2 ) ξm = max
κ∈[τm,τm+1]
( (κ− ν)2 ) ∀m ∈ {1, . . . ,M − 1},
(102)
i.e. compute the maximum squared distance to ν within each bin [τm, τm+1]. Then:
σ2 ≤ ξ0F (τ1) + ξM (1− F (τM )) + M−1∑ m=1 ξm (F (τm+1 − F (τm)) (103)
= ξM + M−1∑ m=1 (ξm−1 − ξm)F (τm) (104)
≤ ξM + M−1∑ m=1 sgn (ξm−1 − ξm)F (τm) + (1− sgn (ξm−1 − ξm))F (τm) (105)
with probability (1− α). In the first inequality, we bound the expected squared distance from ν by assuming that the probability mass in each bin [τm, τm+1] is concentrated at the farthest point from ν. The equality is a result of reordering the telescope sum. In the second inequality, we upper-bound the CDF where it is multiplied with a non-negative value and lower-bound it where it is multiplied with a negative value.
With the probabilistic bounds µ and σ2 we can now – in principle – evaluate our robustness certificate, i.e. check whether ∑
z∈X
πx′(z) 2
πx(z) < 1 +
1 σ2 − ( µ− ν )2 (µ− 12 )2 . (106)
where the π are the probability mass functions of smoothing distributions Ψ(x) and Ψ(x′). But one crucial detail of Theorem 3 underlying the certificate was that it only holds for ν ≤ µ, i.e. only when this condition is fulfilled can we 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 ν ≤ µ by first computing µ and then choosing some smaller ν.
In our experiments, we use an alternative method that allows us to use arbitrary ν: From our proof of Theorem 3we know that the dual problem of Eq. 98 is
max α,β≥0
αµ− βσ2 − α 2
4β +
α 2β − αν + ν − 1 4β ∑ z∈X πx′(z) 2 πx(z) , (107)
Instead of trying to find an optimal α (which causes problems in subsequent derivations if ν µ), we can simply choose α = 1. By duality, the result is still a lower bound on the primal problem, i.e. the certificate remains valid. The dual problem becomes
max β≥0 µ− βσ2 + 1 4β − 1 4β ∑ z∈X πx′(z) 2 πx(z) . (108)
The problem is concave in β (because the expected likelihood ratio is ≥ 1). Finding the optimal β, comparing the result to 0.5 and solving for the expected likelihood ratio, shows that a prediction is robust if ∑
z∈X
πx′(z) 2
πx(z) < 1 +
1
σ2
( µ− 1
2
)2 . (109)
For our abstention mechanism, like in the previous section, we compute the certificate H and then test whether x ∈ H. In the case of Bernoulli smoothing and sparsity-aware smoothing), this corresponds to testing whether
1 < ln ( 1 + 1
σ2
( µ− 1
2
)) (110)
⇐⇒ µ > 1 2 . (111)

heading: C.3 MONTE CARLO CENTER SMOOTHING
text: While we can not use center smoothing as a base certificate, we benchmark our method against it during our experimental evaluation. The generation of candidate predictions, the abstention mechanism and the certificate are explained in (Kumar & Goldstein, 2021). The authors allow multiple
options for generating candidate predictions. We use the ”β minimum enclosing ball” with β = 2 that is based on pair-wise distance calculations.

heading: C.4 MULTIPLE COMPARISONS PROBLEM
text: 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 to simultaneously hold with a high probability (1 − α). But as the number of certificates increases, so does the probability of at least one of them being invalid. To account for this multiple comparisons problem, we use Bonferroni (Bonferroni, 1936) correction, i.e. compute each Monte Carlo certificate such that it holds with probability (1− αn ). For base certificates that only depend on qn = Prz∼Ψ(n) [gn(z) = ŷn], i.e. the probability of the base classifier predicting a particular label ŷn 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 p1, . . . , pN . Starting at i = 1, the i’th hypothesis is rejected if pi < αN+1−i , until one reaches an i such that pi ≥ α N+1−i .
Fischer et al. (2021) proposed to use Holm correction as part of their procedure for certifying that all (non-abstaining) 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 predictions. As in Section C.1, the goal is to obtain a lower bound q
n on qn = Prz∼Ψ(n) [gn(z) = ŷn] for
each of theDout classifier outputs. Assume we takeN2 samples z(1), . . . ,z(N2) from the smoothing distribution. Let νn = ∑N2 i=1 I [ gn(z (i)) = ŷn ]
and let π : {1, . . . , Dout} → {1, . . . , Dout} be a bijection that orders the νn in descending order, i.e. νπ(1) ≥ νπ(2) · · · ≥ νπ(Dout). Instead of using Clopper-Pearson confidence intervals to obtain tight lower bounds on the qn, Fischer et al. (2021) define a threshold τ ∈ [0.5, 1) and use Binomial tests to determine for which n the bound τ ≤ qn holds with high-probability. Let BinP (νn, N2,≤, τ) be the p-value of the one-sided binomial test, which is monotonically decreasing in νn. Following the Holm correction scheme, the authors test whether
BinP ( νπ(k), N2,≤, τ ) <
α
Dout + 1− k (112)
for k = 1, . . . , Dout until reaching a k∗ for which the null-hypothesis can no longer be rejected, i.e. the p-value is g.e.q. αDout+1−k∗ . They then know that with probability 1− α, the bound τ ≤ qn holds for all n ∈ {π(k) | k ∈ {1, . . . , 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 a 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 τn per output gn, i.e. test whether
BinP ( νπ(k), N2,≤, τpi(k) ) <
α
Dout + 1− k (113)
for k = 1, . . . , Dout. In particular, we can use
τn = sup t
s.t. BinP (νn, N2,≤, t) < α
Dout + 1− π−1(n) , (114)
i.e. choose the largest threshold such that the null hypothesis can still be rejected. Eq. 114 is the lower Clopper-Pearson confidence bound with significance αDout+1−π−1(n) . This means that, instead of performing hypothesis tests, we can obtain probabilistic lower bounds q
n ≤ qn by computing
Clopper-Pearson confidence bounds with significance parameters αDout , . . . , α 1 . The qn can then be used to compute the base certificates. Due to the definition of the τn, all of the null hypotheses are rejected, i.e. we obtain valid probabilistic lower bounds on all qn. We can thus use the abstention mechanism from Section C.1, i.e. only abstain if q
n ≤ 0.5.
A direct consequence of the results above is that using Clopper-Pearson confidence intervals and Holm correction will yield stronger per-prediction robustness guarantees and lower abstention rates
than the method of Fischer et al. (2021). The Clopper-Pearson-based method only abstains if one cannot guarantee that qn > 0.5 with high probability, while their method abstains if one cannot guarantee that qn ≥ τ with τ ≥ 0.5 (or specific other predictions abstain). For all non-abstaining predictions, the Clopper-Pearson-based certificate will be at least as strong as that obtained using a single threshold τ , as it computes the tightest bound for which the null hypothesis can still be rejected (see Eq. 114). Consequently, a naı̈ve collective robustness certificate (i.e. counting the number of predictions whose robustness are guaranteed by the base certificates) based on ClopperPearson 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 et al. (2021). It 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.
Our above discussion shows that, for our notion of collective robustness, the naı̈ve collective certificate using Clopper-Pearson confidence bounds and Holm correction is at least as strong as that of Fischer et al. (2021) (or alternatively: the certificate of Fischer et al. (2021) is a naı̈ve collective certificate with Holm correction, but with weaker per-prediction certificates). Conversely, the certificate based on Clopper-Pearson confidence bounds is at least as strong as that of Fischer et al. (2021) when certifying their notion of collective robustness, i.e. determining whether all non-abstaining predictions are robust, given adversarial budget . To certify this notion of robustness, they simply iterate over all predictions and determine whether all non-abstaining predictions are certifiably robust, given . Naturally, as the Clopper-Pearson-based certificates are stronger, any prediction that is robust according to (Fischer et al., 2021) is also robust acccording to the Clopper-Pearson-based certificates. The only difference is that, for τ > 0.5, their method will have more abstaining predictions. But, due to the direct correspondence of Clopper-Pearson confidence bounds and Binomial tests, we can modify our abstention mechanism to obtain exactly the same set of abstaining predictions: We simply have to use q
n ≤ τ instead of qn ≤ 0.5 as our abstention criterion. Finally, it
should be noted that the proposed collective certificate is at least as strong as the naı̈ve collective certificate (see Section 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 a certificate that is at least as strong as that of Fischer et al. (2021) in their setting.
In our experiments (see Section 8), we use Holm correction for our naı̈ve collective certificate and the weaker Bonferroni correction for our 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 to improve our proposed collective cert.

heading: D COMPARISON TO THE COLLECTIVE CERTIFICATE OF SCHUCHARDT ET AL.
text: In the following, we first present the collective certificate for binary graph-structured data proposed by Schuchardt et al. (2021) (see Section D.1. We then show that, when using sparsity-aware smoothing distributions (Bojchevski et al., 2020) – 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).

heading: D.1 THE COLLECTIVE CERTIFICATE
text: Their certificate assumes the input space to beG = {0, 1}N×D×{0, 1}N×N – the set of undirected attributed graphs with N nodes and D attributes per node. The model is assumed to be a multioutput classifier f : G → YN that assigns a 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 to certify collective robustness to a set of perturbed graphs B ⊆ G. The perturbation model B is characterized by four scalar parameters r+X , r − X , r + A, r + A ∈ N0, specifying the number of bits the adversary is allowed to add (0 → 1) and delete (1 → 0) 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 our main result. A formal definition of the perturbation model can be found in Section B of (Schuchardt et al., 2021).
The goal of their work is to certify collective robustness for a set of targeted nodes T ⊆ {1, . . . , N}, i.e. compute a lower bound on
min G′∈B ∑ n∈T I [fn(G ′) = yn] . (115)
Their approach to obtaining this lower-bound shares the same high-level idea as ours: Combining per-prediction 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 obtain 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 ψ(n) and an indicator matrix Ψ(n) that fulfill
N∑ m=1 D∑ d=1 ψ(n)m I [ Xm,d 6= X ′i,j ] + N∑ i=1 N∑ j=1 Ψ(n)m I [ Am,d 6= A′i,j ] = 0
=⇒ fn(X,A) = fn(X ′,A′).
(116)
for any perturbed graph G′ = (X ′,A′). Eq. 116 expresses that the prediction of output fn remains unchanged if all inputs in its receptive field remain unchanged. Conversely, it expresses that perturbations outside the receptive field can be ignored. Unlike in our work, Schuchardt et al. (2021) describe their base certificates as sets in adversarial budget space. That is, some certification procedure is applied to each output fn to obtain a set
K(n) ⊆ [r+X ]× [r − X ]× [r + A]× [r − X ] (117)
with [k] = {0, . . . , k}. If [ c+X c − X c + A c − A ]T ∈ K(n), then prediction yn is robust to any perturbed input with exactly c+X attribute additions, c − X attribute deletions, c + A edge additions and c−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 location in 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 naı̈ve combination of the base certificates (i.e. counting how many predictions are certifiably robust to the collective threat model). The
resulting collective certificate is
min b+,b+,B+,B− ∑ n∈T I [[( ψ(n) )T b+X ( ψ(n) )T b−X ∑ i,j Ψ (n) i,j B + i,j ∑ i,j Ψ (n) i,j B − i,j ]T ∈ K(n) ] (118)
s.t. N∑ m=1 b+m ≤ r+X , N∑ m=1 b−m ≤ r−X , N∑ i=1 N∑ j=1 B+i,j ≤ r + A, N∑ i=1 N∑ j=1 B−i,j ≤ r − A, (119)
b+, b− ∈ NN0 B+,B− ∈ NN×N0 . (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. 119 ensures that this allocation in compliant with the collective threat model. Finally, in Eq. 118 the indicator vector and matrix ψ(n) and Ψ(n) 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, Schuchardt et al. (2021) replace each of the indicator functions with binary variables and include additional constraints to 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 budgetsK(n) from its complementK(n) in adversarial budget space (the ”pareto front” discussed in Section 3 of (Schuchardt et al., 2021)).
From the above explanation, the main drawbacks of this collective certificate compared to our localized randomized smoothing approach and corresponding collective certificate should be clear. Firstly, if the classifier f is not strictly local, i.e. the receptive field indicators ψ and Ψ only have non-zero entries, then all base certificates are evaluated using the entire collective adversarial budget. 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.

heading: D.2 PROOF OF SUBSUMPTION
text: In the following, we show that any robustness certificate obtained by using the collective certificate of Schuchardt et al. (2021) 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 perturbations outside the receptive field.
First, we derive the certificate of Schuchardt et al. (2021) for predictions obtained via sparsityaware smoothing. Schuchardt et al. (2021) require base certificates that guarantee robustness when[ c+X c − X c + A c − A ]T ∈ K(n), 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 scalar distribution parameters p+X , p − A ∈ [0, 1]. Given attribute matrix X ∈ {0, 1}N×D, they then sample random attribute matrices ZX that are distributed according to sparsity-aware smoothing distribution S ( X,1 · p+X ,1 · p − X ) (see Section B.2.2), i.e.
Pr[(ZX)m,d = 0] = ( 1− p+X )1−Xm,d · (p−X)Xm,d , Pr[(ZX)m,d = 1] = ( p+X )1−Xm,d · (1− p−X)Xm,d .
Given input adjacency matrix A, random adjacency matrices ZA are sampled from the distribution S ( A,1 · p+A,1 · p − A ) . Applying Theorem 2 (to the flattened and concatenated attribute and adjacency matrices) shows that smoothed prediction yn = fn(X,A) is robust to the perturbed graph
(X ′,A′) if N∑ m=1 D∑ d=1 γ+X · I [ Xm,d = 0 6= X ′m,d ] + γ−X · I [ Xm,d = 1 6= X ′m,d ] +
N∑ i=1 N∑ i=1 γ+A · I [ Ai,j = 0 6= A′i,j ] + γ−A · I [ Ai,j = 1 6= A′i,j ] < η(n)
(121)
with γ+X = ln ( (p−X) 2
1−p+X +
(1−p−X) 2
p+X
) , γ−X = ln ( (1−p+X) 2
p−X +
(p+X) 2 1−p−X .
) , γ+A =
ln
( (p−A) 2
1−p+A +
(1−p−A) 2
p+A
) , γ−A = ln ( (1−p+A) 2
p−A +
(p+A) 2 1−p−A .
) and η(n) = ln ( 1 + 1
σ(n)2 ( µ(n) − 12 )2) ,
where µ(n) is the mean and σ(n) is the variance of the base 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. 121 can be rewritten as
γ+Xc + X + γ − Xc − X + γ + Ac + A + γ − Ac − A ≤ η (n), (122)
where c+X , c − X , c + A, c − A 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 prediction yn is certifiably robust if [ c+X c − X c + A c − A
]T ∈ K(n). When this base certificate is used, i.e. we insert the base certificate Eq. 122 into objective function Eq. 118, the collective certificate of Schuchardt et al. (2021) becomes equivalent to
min b+,b+,B+,B− ∑ n∈T I [ γ+X ( ψ(n) )T b+X + γ − X ( ψ(n) )T b−X
+γ+A ∑ i,j Ψ (n) i,j B + i,j + ∑ i,j γ−AΨ (n) i,j B − i,j ≤ η (n)
] (123)
s.t. N∑ m=1 b+m ≤ r+X , N∑ m=1 b−m ≤ r−X , N∑ i=1 N∑ j=1 B+i,j ≤ r+A, N∑ i=1 N∑ j=1 B−i,j ≤ r−A, (124)
b+, b− ∈ NN0 B+,B− ∈ NN×N0 . (125)
Next, we show that obtaining base certificates through localized randomized smoothing with appropriately chosen parameters and using these base certificates within our proposed collective certificate (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 n’th output, we sample random attributes matrices from distribution S ( X,Θ+X (n) ,Θ−X (n) ) with
Θ+X (n) ,Θ−X (n) ∈ [0, 1]N×D. Note that, in order to avoid having to index flattened vectors, we overload the definition of sparsity-aware smoothing to allow for matrix-valued parameters. For example, the value Θ+X (n) n,d indicates the probability of flipping the value of input attribute Xn,d from 0 to 1 and the value Θ−X (n)
n,d indicates the probability of flipping the value of input attribute Xn,d from 1 to 0. We choose the following values for these parameters:
Θ+X (n) m,d = ψ (n) m · p+X + ( 1− ψ(n)m ) · 0.5, (126)
Θ−X (n) m,d = ψ (n) m · p−X + ( 1− ψ(n)m ) · 0.5, (127)
where ψ(n) is the receptive field indicator vector defined in Eq. 116 and p+X , ·p − X ∈ [0, 1] are the same flip probabilities we used for the certificate of Schuchardt et al. (2021). Due to this parameterization, attribute bits inside the receptive field are randomized using the same distribution as in the certificate of Schuchardt et al. (2021), while attribute bits outside are set to either
0 or 1 with equal probability. Similarly, we sample random adjacency matrices from distribution S ( A,Θ+A (n) ,Θ−A (n) ) with Θ+A (n) ,Θ−A (n) ∈ [0, 1]N×D and
Θ+A (n) i,j = Ψ (n) i,j · p + A + ( 1−Ψ(n)i,j ) · 0.5, (128)
Θ−A (n) u,j = Ψ (n) i,j · p − A + ( 1−Ψ(n)i,j ) · 0.5, (129)
where Ψ(n) 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 = fn(X,A) will be the same as the one obtained via the smoothing distribution used by Schuchardt et al. (2021). Applying Theorem 2 (to the flattened and concatenated attribute and adjacency matrices) shows that smoothed prediction yn = fn(X,A) is robust to the perturbed graph (X ′,A′) if
N∑ m=1 D∑ d=1 τ+Xm,d · I [ Xm,d = 0 6= X ′m,d ] + τ−Xm,d · I [ Xm,d = 1 6= X ′m,d ] +
N∑ i=1 N∑ j=1 τ+A i,j · I [ Ai,j = 0 6= A′i,j ] + τ−A i,j · I [ Ai,j = 1 6= A′i,j ] < η(n).
(130)
Because we only changed the distribution outside the receptive field, the scalar η(n), which depends on the output distribution’s mean and variance µ and σ will be the same as the one obtained via the smoothing scheme used by Schuchardt et al. (2021) et al. Due to Theorem 2 and the definition of our smoothing distribution parameters in Eqs. (126) to (129) , the scalars τ+Xm,d, τ − Xm,d, τ + A i,j , τ − A i,j have the following values:
τ+Xm,d = ψ (n) m · γ+X + ( 1− ψ(n)m ) · 2 · ln
( (1− 0.5)2
0.5 +
0.52
1− 0.5
) (131)
τ−Xm,d = ψ (n) m · γ−X + ( 1− ψ(n)m ) · 2 · ln
( (1− 0.5)2
0.5 +
0.52
1− 0.5
) (132)
τ−A i,j = Ψ (n) i,j · γ + A + ( 1−Ψ(n)i,j ) · 2 · ln
( (1− 0.5)2
0.5 +
0.52
1− 0.5
) (133)
τ−A i,j = Ψ (n) i,j · γ − A + ( 1−Ψ(n)i,j ) · 2 · ln
( (1− 0.5)2
0.5 +
0.52
1− 0.5
) , (134)
where the γ are the same weights as those of the base certificate Eq. 121 of Schuchardt et al. (2021). Inserting the above values of τ into the base certificate Eq. 130 and using the fact that ln (
(1−0.5)2 0.5 + 0.52 1−0.5
) = ln(1) = 0 results in
N∑ m=1 D∑ d=1 ψ(n)m · γ+X · I [ Xm,d = 0 6= X ′m,d ] + ψ(n)m · γ−X · I [ Xm,d = 1 6= X ′m,d ] +
N∑ i=1 N∑ j=1 Ψ (n) i,j · γ − A · I [ Ai,j = 0 6= A′i,j ] + Ψ (n) i,j · γ − A · I [ Ai,j = 1 6= A′i,j ] < η(n).
(135)
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 perturbation types in Section B.2.2: We use a different budget variable per input dimension and perturbation type. Furthermore, the attribute bits of each node share the same noise level. Therefore, we can use the method discussed in Section A.3, i.e. use a single budget variable per node instead of using
one per node and attribute. Modelling our collective problem in this way, using Eq. 135 as our base certificates and rewriting the first two sums using inner products results in the optimization problem
min b+,b+,B+,B− ∑ n∈T I [ γ+X ( ψ(n) )T b+X + γ − X ( ψ(n) )T b−X
+γ+A ∑ i,j Ψ (n) i,j B + i,j + ∑ i,j γ−AΨ (n) i,j B − i,j ≤ η (n)
] (136)
s.t. N∑ m=1 b+m ≤ r+X , N∑ m=1 b−m ≤ r−X , N∑ i=1 N∑ j=1 B+i,j ≤ r+A, N∑ i=1 N∑ j=1 B−i,j ≤ r−A, (137)
b+, b− ∈ NN0 B+,B− ∈ NN×N0 . (138)
This optimization problem is identical to that of Schuchardt et al. (2021) from Eqs. (123) to (125). The only difference is in how these problems would be mapped to a mixed-integer linear program. We would directly model the indicator functions in the objective using a single linear constraint. Schuchardt et al. (2021) would use multiple linear constraints, each corresponding to one point in the adversarial budget space.
To summarize: For randomly smoothed models, masking out perturbations using a-priori knowledge about a model’s strict locality is equivalent to completely randomizing (here: flipping bits with probability 50%) parts of the input. While Schuchardt et al. (2021) only derived their certificate for binary data, it is conceivable that their approach could be applied to strictly local models for continuous data. Considering our certificates for Gaussian (Proposition 1) and (Proposition 2) uniform smoothing, where the base certificate weights are 1σ2 and 1 λ , respectively, it should again be possible to perform the same masking operation as Schuchardt et al. (2021) by using σ →∞ and λ→∞. Finally, it should be noted that the certificate by Schuchardt et al. (2021) allows for additional constraints, 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 C of their paper), they can be just as easily integrated into our mixed-integer linear programming certificate.

heading: E EXPERIMENTAL SETUP AND ADDITIONAL EXPERIMENTS
text: In the following, we first explain the metrics we use for measuring the strength of certificates, and how they can be applied to the different types of randomized smoothing certificates used in our experiments. We then discuss the experimental setup, as well hyperparameters and additional experimental results for our semantic segmentation Section E.2 and node classification Section 8.2 experiments.

heading: E.1 METRICS
text: 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 of correctness). We use Monte Carlo randomized smoothing (see Section C. Therefore, we may have to abstain from making predictions. Abstentions are counted as non-robust and incorrect. In the case of center smoothing, either all or none predictions abstain (this is inherent to the method. In our experiments, center smoothing never abstained). In the following, let Z = {d ∈ {1, . . . , Dout} | yn = ŷn} be the indices of correct predictions, given an input x. Naı̈ve collective certificate. The naı̈ve collective certificate certifies each prediction independently. Like with our base certificates, let H(n) be the set of perturbed inputs yn is robust to. Let Bx be the collective perturbation model. Then L = { d ∈ {1, . . . , Dout} | Bx ⊆ H(n) } is the set of all certifiably robust predictions. The certified ratio can be computed as |L|Dout and the certified accuracy as |L∩Z|Dout .
Center smoothing Center smoothing does not determine which predictions are robust, but only how many are. Let k be the number of certifiably robust predictions. The certified ratio can be easily
computed as kDout . For the certified accuracy, we have to make the worst-case assumption that the non-robust predictions are correct predictions, i.e. compute max(0,k−(Dout−|Z|))Dout Collective certificate. Let l(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 l(T)Dout with T = {1, . . . , Dout} and T = Z, respectively.

heading: E.2 SEMANTIC SEGMENTATION
text: We first list all parameters and details of our training and certification procedures, before discussing additional experimental results in Section E.2.3.

heading: E.2.1 EXPERIMENTAL SETUP AND HYPERPARAMETERS
text: Model. As the base model for the semantic segmentation task, we use a U-Net model (Ronneberger et al., 2015) with a ResNet-18 (He et al., 2016) backbone, as implemented by the Pytorch Segmentation Models library (version 0.13) (Yakubovskiy, 2020). We use the library’s default parameters. In particular, the inputs 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-VOC 2012 segmentation validation 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 extracted from the SBD dataset (Hariharan et al., 2011) (referred to as ”Pascal trainaug” or ”Pascal augmented training set” in other papers). SBD uses a different data split than the official PascalVOC 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, so that we can use larger batch sizes and thus use our compute time to more thoroughly evaluate a larger range of different smoothing distributions. The segmentation masks are downscaled using nearest-neighbor 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, β1 = 0.9, β2 = 0.999, = 10
−8,weight decay = 0. 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 ShiftScaleRotate augmentation implemented by the Albumentations library (version 0.5.2) (Buslaev et al., 2020). The images are than cropped to a fixed size of 128×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 σ ∈ {0, 0.01, . . . , 0.5}. All samples are clipped to [0, 1] to retain valid RGBimages.
Certification. We evaluate all certificates on the first 50 images from the validation set that – after downscaling – have a resolution of 166×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 certificates hold with probability 0.99. For the center smoothing baseline, we use the default parameters suggested by the authors (∆ = 0.05, β = 2, α1 = α2). For the naı̈ve collective certificate baseline, we use Holm correction to account for the multiple comparisons problem, which yields strictly better results than Bonferroni correction. For our 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 σmin and maximum standard deviation σmax.
Let J(k,l) be the set of all pixel coordinates in grid cell (k, l). To smooth outputs in grid cell (i, j), we use a smoothing distribution N (0,diag(σ) with, ∀k ∈ {1, . . . , 4}, l ∈ {1, . . . , 6}, d ∈ J(k,l),
σd = σmin + (σmax − σmin) · max (|i− k|, |l − j|)
6 , (139)
i.e. we linearly interpolate between σmin and σmax based on the l∞ distance of grid cells (i, j) and (k, l). All results are reported for the relaxed linear programming formulation of our collective certificate (see Section A.4). For each grid cell, we use 124 = 1 4·6 of the samples, which corresponds 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).

heading: E.2.2 HARDWARE
text: 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.

heading: E.2.3 COMPLETE EXPERIMENTAL EVALUATION
text: As explained in Section 8.1, the objective of our experiments on semantic segmentation is to verify our claim that localized smoothing allows for a better accuracy-robustness trade-off than randomized smoothing with i.i.d. distributions, i.e. 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 naı̈ve and the center smoothing baselines for Gaussian standard deviations σ ∈ {0.1, 0.2, 0.3, 0.4, 0.5} and – for each σ – find a combination of localized smoothing parameters σmin, σout that result in equal or higher accuracy and stronger certificates, as measured by certified accuracy and certified ratio. Figs. 5 to 8 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 1 and 2. Safe for center smoothing with σ = 0.2, which has a slightly higher certified ratio but lower accuracy, we can outperform all baselines.
The second step is to fix the found localized smoothing parameters and perform a fine-grained search over σ ∈ [0, 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 σ that outperforms our baselines, using the certified ratio of the naı̈ve collective certificate baseline as an example. The certificate strength, as measured by the certified ratio’s AUC, increases with σ. But the model’s accuracy decreases with σ. 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 baselines to simultaneously attain a higher accuracy and stronger certificates. To summarize: Localized smoothing appears to indeed offer a better trade-off between certified accuracy and robustness.
In Section 8.1, we mentioned that we compare base classifiers with different trained weights. For i.i.d. smoothing with σ, we loaded models trained with σtrain = σ. For localized smoothing, we loaded models trained with σtrain = σmin. To show that this is not the reason why we outperform the baselines, we compare the same i.i.d. and localized smoothing distributions as before, but use σtrain = σmin for all models. The results are summarized in Appendix E.2.3 and Table 4. Overall, there is only a single instance in which the baselines are better than the localized smoothing certificate in any of our metrics: For σ = 0.3, the naı̈ve baseline attains an accuracy of 79.5% that is 0.4 p.p. higher than that of the locally smoothed model. The AUC of its certified accuracy and certified 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.
While it resulted in significantly stronger certificates, the proposed collective certificate added very little additional computational cost, compared to the naı̈ve collective certificate. The naı̈ve collective certificate requires taking Monte Carlo samples and then performing a small number of vector
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 a linear program on 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 number of samples for both). Averaged over all experiments and images, computing the per-prediction certificates took 15.85 s for the baseline and 0.15 s for the proposed certificate (the increased cost for the baseline is due to 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.

heading: E.3 NODE CLASSIFICATION
text: 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.

heading: E.3.1 EXPERIMENTAL SETUP AND HYPERPARAMETERS
text: 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 a hidden size of 64 and dropout with a probability of 0.5. Furthermore, for the propagation step of APPNP we use 10 for the number of interactions and 0.15 as value for α.
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 5 clusters. We create an affinity ranking by counting the number of edges which are connecting cluster i and j. This ranking is used to select the noise parameter for smoothing the attributes of cluster j while classifying a node of cluster i.
Training and data augmentation All models are trained with a 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 on the their minimal noise level, i.e., not with localized noise but with only θ+min and θ − min.
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 using MOSEK (version 9.2.46) (MOSEK ApS, 2019) through the CVXPY interface (version 1.1.13) (Diamond & Boyd, 2016).

heading: E.3.2 HARDWARE
text: All experiments on image segmentation were performed using an AMD EPYC 7543 CPU @ 2.80GHz, an NVIDA A100 GPU and 32 GB of RAM.

heading: E.3.3 ADDITIONAL EXPERIMENTAL EVALUATION
text: In Fig. 9, 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 as 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 to 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. 11 compares the variance certificate to the sparse smoothing certificate of Bojchevski et al. (2020). That is, we use only one cluster and the same noise levels and models for our approach and the baseline, i.e., θ+ = 0.01 and θ− = 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 2, we can see that we multiply the adversarial budget for addition with γ+
and the one for deletion with γ−. As γ+ has θ+ in the denominator the small noise level for addition results in larger values for γ+. For these parameters we have γ+ = 2.795 and γ− = 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 or worse than the baseline for additions but we outperform it 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 of 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-aware smoothing certificate of Bojchevski et al. (2020), while the proposed collective certificate uses our novel variance smoothing certificate (see Theorem 2), which requires estimating both the mean and variance of softmax scores). Averaged over all tested adversarial budgets, solving each collective linear program only took 10.9 s, i.e. 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.

Review summaries:
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.

The paper makes three contributions in particular: - 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. - 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. - 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.

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.  

**Summary**  The 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.