Localized Randomized Smoothing for Collective Robustness Certification
Authors: Jan Schuchardt
Tom Wollschläger
Aleksandar Bojchevski
Stephan Günnemann
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Robustness
Certification
Verification
Trustworthiness
Graph neural networks

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). Collective robustness certification is the task of provably bounding the number of robust predictions under this threat model. The only dedicated method that goes beyond certifying each output independently is limited to strictly local models, where each prediction is associated with a small receptive field. We propose a more general collective robustness certificate for all types of models. We further show that this approach is beneficial 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. Localized smoothing Pareto-dominates existing certificates on both image segmentation and node classification tasks, simultaneously offering higher accuracy and stronger certificates.

Published as a conference paper at ICLR 2023
LOCALIZED RANDOMIZED SMOOTHING FOR COLLECTIVE ROBUSTNESS CERTIFICATION
Jan Schuchardt'; Tom Wollschläger', Aleksandar Bojchevski", Stephan Günnemann {j. sishcchc rdt, t. wollsch aeger, s guennemann @t.mm de (bo jeejcheeskk eèci de 'Technical University of Munich
ECISPA Helmholtz Center for Information Security
ABSTRACT
Models for image segmentation, node classification and many other tasks map single input to multiple labels. By perturbing this single shared input (e.g. the image) adversary can manipulate several predictions (e.g. misclassify several pixels). Collective robustness certification is the task of provably bounding the number of robust predictions under this threat model. The only dedicated method that goes beyond certifying each output independently is limited to strictly local models, where each prediction associated with a small receptive field. We pro- pose more general collective robustness certificate for all types of models. We further show that this approach is beneficial 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 the image). The certificate is based on our novel localized randomized smooth- ing approach, where the random perturbation strength for different input regions is proportional to their importance for the outputs. Localized smoothing Pareto- dominates existing certificates on both image segmentation and node classification tasks, simultaneously offering higher accuracy and stronger certificates.
INTRODUCTION
There is a wide range of tasks that require models making multiple predictions based on a single input. For example, semantic segmentation requires assigning label to each pixel in an image. When deploying such multi-output classifiers in practice, their robustness should be key concern. After all just like simple classifiers (Szegedy et al., 2014) they can fall victim to adversarial attacks (Xie et al. 2017, Zügner& & Günnemann] 2019 Belinkov & Bisk 2018). Even without an adversary, random noise or measuring errors can cause predictions to unexpectedly change.
We propose a novel method providing provable guarantees on how many predictions can be changed by an adversary. As all outputs operate on the same input, they have to be attacked simultaneously by choosing single perturbed input, which can be more challenging for an adversary than attacking them independently. We must account for this to obtain proper collective robustness certificate.
The only dedicated collective certificate that goes beyond certifying each output indepen- dently (Schuchardt et al. 202T) is only beneficial for models call strictly local, where each output depends on a small, pre-defined subset of the input. Multi-output classifiers however, are often only softly local. While all their predictions are in principle dependent the entire input, each output may assign different importance to different subsets. For example, convolutional networks for image segmentation can have small effective receptive fields (Luo et al., 2016 Liu al. 2018), iec primarily use a small region of the image in labeling each pixel. Many models for node classi- fication are based on the homophily assumption that connected nodes are mostly of the same class. Thus, they primarily use features from neighboring nodes. Transformers, which can in principle at- tend to arbitrary parts of the input, may in practice learn "sparse" attention maps, with the prediction for each token being mostly determined by a few (not necessarily nearby) tokens (Shi et al. (02I).
"qqual contribution

---

Published as a conference paper at ICLR 2023
Grid cell (0,1)
g
muafority
Resterized image
Seamentation mask
Anisotropic Smoothing
Figure 1: Localized randomized smoothing applied to semantic segmentation. We assume that the most relevant information for labeling pixel is contained in other nearby pixels. We partition the input image into multiple grid cells. For each grid cell, we sample noisy images from a different anisotropic distribution that applies more noise far-away, less relevant cells. Segmenting all noisy images, cropping the result and computing the majority vote yields a local segmentation mask. These per-cell segmentation masks can then be combined into complete segmentation mask.
Softly local models pose budger allocation problem for an adversary that tries to simultaneously manipulate multiple predictions by crafting a single perturbed input. When each output primarily focused on a different part of the input, the attacker has to distribute their limited adversarial budget and may be unable to attack all predictions at once.
We propose localized randomized smoothing, novel method for the collective robustness certifi- cation of softly local models that exploits this budget allocation problem. It an extension of ran- domized smoothing (Lécuyer al., 2019 Li et al. 2019 Cohen al. 2019), versatile black-box certification method which is based on constructing a smoothed classifier that returns the expected prediction of a model under random perturbations of its input (more details in S 2}. Randomized smoothing is typically applied to single-output models with isotropic Gaussian noise. In localized smoothing however, we smooth each output (or set of outputs) of a multi-output classifier using dif- ferent distribution that is anisotropic. This is illustrated in Fig. I, where the predicted segmentation masks for each grid cell are smoothed using a different distribution. For instance, the distribution for segmenting the top-right cell applies less noise to the top-right cell. The smoothing distribution for segmenting the bottom-left cell applies significantly more noise to the top-right cell.
Given a specific output of a softly local model, using low noise level for the most relevant parts of the input lets us preserve high prediction quality. Less relevant parts can be smoothed with a higher noise level to guarantee more robustness. The resulting certificates (one per output) explicitly quantify how robust each prediction is to perturbations of which part of the input. This information about the smoothed model's 's locality can then be used to combine the per-prediction certificates into a stronger collective certificate that accounts for the adversary's budget allocation problem
Our core contributions
Localized randomized smoothing, a novel smoothing scheme for An efficient anisotropic randomized smoothing certificate for discrete data.
classifiers.
A collective certificate based on localized randomized smoothing.
2 BACKGROUND AND RELATED WORK
Randomized smoothing, Randomized smoothing is a certification technique that can be used for various threat models and tasks. For the sake of exposition, let us discuss certificate for l2 per- turbations (Chhen et al. 2019). Assume we have D-dimensional input space R.,, label set Y and classifier g R
Y. We can use isotropic Gaussian noise construct the smoothed classifier f = argmax, yey Pr Pra~N(z.a) [9(2) = y] that returns the most likely prediction of base classifier g under the input distribution Given an input E R and smoothed prediction y f(x).
can then easily determine whether is robust to all la perturbations of magnitude e, i.e. whether f(x') y. Let q Pr (g(z) y] be the probability of predicting
Var x æ
An implementation will be made available at httn:://ww.cs.ci.. www.sci.ttt.cc/dltcc.e
In practice, all probabilities have he estimated using Monte Carlo sampling (see discussion
2

---

Published as a conference paper at ICLR 2023
label y. The prediction is certifiably robust if (q) (Cohen et al. 2019). This result show- cases a trade-off inherent to randomized smoothing: Increasing the noise level (σ) may strengthen the certificate, but could also lower the accuracy of f or reduce q and thus weaken the certificate.
White-box certificates for multi-output classifiers. There are multiple recent methods for certify- ing the robustness of multi-output models by analyzing their specific architecture and weights (for example, see (Tran et al.] 2021; Zügner & Günnemann 2019; BBojcheskii & Günnemann, [209]] Zügner & Günnemann 2020; Ko et al., 2019 Ryou al., 2021 Shi et al. [0200] [Bonert et al.
2021j). They are however not designed to certify collective robustness, i.e. determine whether mul-
tiple outputs can be simultaneously attacked using a single perturbed input. They can only determine
independently for each prediction whether or not it can be attacked.
Black-box certificates for multi-output classifiers. Most directly related to our work is the afore- mentioned certificate of Scchchardt et al. (2021), which is only beneficial for strictly local models (i.e. models where each output has a small receptive field). In S smoothed models, their certificate is special case of ours. SegCertify (Fischer et al.) (02II) is a col- lective certificate for segmentation. This method certifies each output independently using isotropic smoothing (ignoring the budget allocation problem) and uses Holm correction (Holm 1979) to ob- tain tighter Monte Carlo estimates. It then counts the number of certifiably robust predictions and tests whether it equals the number of predictions. In SS H we demonstrate that our method can al- ways provide guarantees that are at least as strong. Another method that can in principle be used to certify collective robustness is center smoothing (Kumar & Goldstein 2021). It bounds the change of a vector-valued function w.r.t to a distance function. Using the to pseudo-norm, it can bound how many predictions can be simultaneously changed. More recently, Chenn al. (2022) proposed collective certificate for bagging classifiers. Different from our work, they consider poisoning (train- time) instead of evasion (test-time) attacks. Yatsura al. (2022) prove robustness for segmentation, but consider patch-basee instead of lp norm attacks and certify each prediction independently.
we show that, for randomly
Anisotropic randomized smoothing. While only designed for single-output classifiers, two recent certificates for anisotropic Gaussian and uniform smoothing (Fischer et al. [2200] (iias et al. 2022)
can be used as a component of our collective certification approach: They can serve as per-prediction
certificates, which we can then combine into stronger collective certificate (more details in
$ 3.2
3 PRELIMINARIES
3.1 COLLECTIVE THREAT MODEL.
We assume multi-output classifier f Di + Dour,, that maps Din th-ddmenniioal inputs to Dout labels from label set Y. We further assume that this classifier f is the result of randomly smooth- ing each output of a base classifier g. Given this multi-output classifier f. an input x E x and the corresponding predictions y = f(x), the objective of the adversary is to cause as many predictions from a set of targeted indices T C (1...., D } to change. That is, their objective is yn where I is the indicator function and B2 C D is the perturba-
min ER, Σmer [Jm(²') tion model. As is common in robustness certification, we assume a fp-norm perturbation model, iee Br. = (a' E x || - x l|l S e] with p,e 2 O. Importantly, note that the minimization operator is outside the sum, meaning the predictions have to be attacked using single input.
3.2 A RECIPE FOR COLLECTIVE CERTIFICATES
Before discussing localized randomized smoothing, we show how to combine arbitrary per- prediction certificates into collective certificate, procedure that underlies both our method and that Schuchardt et al. (2021) and Fischer et al. (202T). The first step is to apply an arbitrary certifi-
cation procedure to each prediction VI.... : VD... in order to obtain per- per-predintion base certificates.
Definition 3.1 (Base certificates). A base certificate for a prediction yn. = fx( is a set (m)) C X of perturbed inputs s.t. Vx' Hin), fn(²²) Vn-
Using these base certificates, one can derive two bounds on the adversary's objective:
min R' NET
Σ I[fa((') = yml min
Σ
H(m)]
> Σ min I x E m (1)
(1.1) 2 E3 TET
(1.2) neT r'EBz
3

---

Published as a conference paper at ICLR 2023
Eq. 1.1 follows from Theorem 3.1 (if a prediction is certifiably robust to x', then fn(x') Yn),
while Eq. 1.2 results from moving the min operator inside the summation.
the predictions and counts how many are certifiably robust to perturbation model r.. Each summand involves a separate minimization problem. Thus, the certificate neglects that the adversary has to choose single perturbed input to attack all outputs. SegCertify (Fischer et al. 2021) applies this to isotropic Gaussian smoothing.
Eq. 1.2 the naive collective certificate: It iterates
While Eq. 1.1 is seemingly tighter than the naïve collective certificate, it may lead to identical results. For example, let us consider the most common case where the base certificates guarantee robustness within an lp ball, i.c. [H]
(x" x= xiIp I r(²)) with certified radii r(*), Then,
the optimal solution both Eq. 1.1 and Eq. 1.2
to choose an arbitrary x' with || æll = c:
E1[ x [
Σ nET
Σ min 1 x EH1 x'EB.
mii C
The main contribution of (Schuchardt et al. (2021) is to notice that, by exploiting strict locality (i.e. the outputs having small receptive fields), can augment certificate Eq. 1.1 make it tighter than the naive collective certificate from FFq. 1.2 One must simply mask out all perturbations falling outside given receptive field when evaluating the corresponding base certificate:
Σ (2(((btn WET
(5(())
Oz' + (1-11i)) 26(")) @ "H")
min
Here, 2b(n) E 1) P.. encodes the receptive field of and C is the elementwise product. If two outputs fn and fm have disjoint receptive fields (i.e. 2b(m)" <b(m) 0), then the adversary has to split up their limited adversarial budget and may be unable to attack both once.
LOCALIZED RANDOMIZED SMOOTHING
The core idea behind localized smoothing that, rather than improving upon the naive collective certificate by using external knowledge about strict locality, we can use anisotropic randomized smoothing to obtain base certificates that directly encode soft locality. Here, we explain our approach in Nomain-inddeennan
manner before turning to specific distributions and data-types in
In localized randomized smoothing, we associate base classifier outputs 91: . .Do.. with distinct anisotropic smoothing distributions (1) ..... (Part) that depend on input æ. For example, they could be Gaussian distributions with mean æ and distinct covariance matrices like in where
we use different distribution for each grid cell. We use these distributions to construct the smoothed classifier f. where each output fu (ar) the result of randomly smoothing 9n. (Z) with (²(")
To certify robustness for a vector of predictions y f(x),, we follow the procedure discussed in $ 3.2. i.e. compute base certificates H ...,, (Dm)) and solve Eq. 1.1 We do not make any assumption about how the base certificates are computed. However, we require that they comply with a common interface, which will later allow us combine them via linear programming:
Definition 4.1 (Base certificate interface). A base certificate H() C Din is compliant with our base certificate interface for l norm perturbations if there is a E R."" and 17(*) e R, such that
Don
H (n)
x
(n) d
lara
xal < (n)"))
The weight w quantifies how sensitive yn. is to perturbations of input dimension d. It will be smaller where the anisotropic smoothing distribution applies more noise. The radius ry(*) quantifies the overall level of robustness. In 5 we present different distributions and corresponding certificates that comply with this interface. Inserting Eq. 2
into Eq. I.1 results in the collective certificate
Din Σ w
min 20' E3
(n)
xal < (m)
(3)
NET
Ld=1
4

---

Published as a conference paper at ICLR 2023
Eq. 3 showcases why locally smoothed models admit a collective certificate that is stronger than naively certifying each output independently (i.e. Eq. 1.2). Because we use different distributions for different outputs, any two outputs f(x) and fim) will have distinct certificate weights w))) and w(m). If they are sensitive in different parts of the imput, i.c. w(()² (m)) is small, then the adversary has to split up their limited adversarial budget and may be unable to attack both at once.
One particularly simple example is the case w (m) O, where attacking predictions ya and ym requires allocating udversarial budget to two entirely disjoint sets of input dimensions. S we show that, with appropriately parameterized smoothing distributions, we can obtain base certificates with (n)) v6("), with indicator vector z6(n) encoding the receptive field of output Hence,
the collective guarantees from (Schuchardt et al. 2021 are a special case of our certificate.
4.1 COMPUTING THE COLLECTIVE CERTIFICATE
While Eq. constitutes valid certificate, it is not immediately clear how evaluate it. However, we notice that the perturbation set 7 imposes linear constraints on the elementwise differences binary variables and that the base certificates
lr'2 zall, the values of the indicator functions inside the indicator functions are characterized by linear inequalities. We can thus reformulate Eq.
as mixed-integer linear program (MILP), which leads us to our main result (proof in D):
Theorem 4.2. Given locally smoothed model f. input æ (Di)), smoothed prediction y f(z)
and base certificates (H)), ..... Hou complying with interface Eq. 2 the number of simultaneously robust predictions ming' E1(f(('') = yyn is nowureb by
nET
min
Σ tm
(4)
BER Pin AE Pout NET
S.I. Vn b" w (m) 2 (1 - tt-nt))n m))) sum(b) S c..
(5)
The vector b models the allocation of adversarial budget (i.e. the elementwise differences ba = la'a P)) The vector serves the same role as the indicator functions from Eq. 3 i.e. it indicates which predictions are certifiably robust. Eq. 3 Jensures that b does not exceed the overall budget e (i.e. x' E BB))) and that i, can only be set to 0 b"d (n) 2 ry("), i.e. only when the base certificate cannot guarantee robustness for prediction yn- This problem can be solved using any MILP solver. Its optimal value provably bounds the number of simultancously robust predictions.
4.2 IMPROVING EFFICIENCY
Solving large MILPs is expensive. In $ E we show that partitioning the outputs into Nout subsets sharing the same smoothing distribution and the inputs into N₁, subsets sharing the same noise level (for example like in Fig. 1] where we partition the image into a 2 x grid), as well as quantizing the base certificate parameters rn(") into Nuin bins, reduces the number of variables and constraints from Di + Dout and Dout + to Ni, +Nout -Nbins and Nout . -Noins + +1, respectively. We can thus control the problem size independent of the data's 's dimensionality. We further derive a linear relaxation of the MILP that can be efficiently solved while preserving the soundness of the certificate.
4.3 ACCURACY-ROBUSTNIE TRADEOFF
When discussing Eq. 3) we only explained why our collective certificate for locally smoothed models better than a naive combination of localized smoothing base certificates. However, this does not necessarily mean that our certificate is also stronger than naïvely certifying an isotropically smoothed model. This is why we focus on soft locality. With isotropic smoothing, high certified robustness requires using large noise levels, which degrade the model's prediction quality. Localized smoothing, when applied to softly local models, can circumvent this issue. For each output, we can use low noise levels for the most important parts of the input to retain high prediction quality. Our LP-based collective certificate allows us to still provide strong collective robustness guarantees. We investigate this improved eccuracy-robustned trade-off in our experimental evaluation (see $ 7p.
5

---

Published as a conference paper at ICLR 2023
5 BASE CERTIFICATES
To apply our collective certificate in practice, we require smoothing distributions ()) and cor-
responding per-prediction base certificates that comply with the interface from Theorem 3.1 As
base certificates for la and 1 perturbations we can reformulate existing anisotropic Gaussian (is-
cher et al., 2020; Kumar& & Goldstein 202T) and uniform (Kumar Goldstein (02T)) smoothing
certificates for single-output models: For T [n)) = =Nxx, diag(s(*)) we have w [m]
1/(s/ (2))
and 17(*) = ( =0 ))² with Qn.y. = Pr =~ "n (g)(2) = v). For v(") = U (x, (()) we have
2a = 1
(m) and nn(n) = 2- (gm.y..) We prove the correctness of these reformulations in
$
For lo perturbations of binary data, we can use distribution F(æ, 0) that flips z4 with probability Oa E [0, 1]. i.e. Pr(zæ * za] = 0g for ~ F(æz, 0). Existing methods (e.g- (Lee et al. 2019)
can be used to derive per-prediction certificates for this distribution, but have exponential runtime in the number of unique values in 0. Thus, they are not suitable for localized smoothing, which uses different 0a for different parts of the input. We therefore propose novel, more efficient approach: fariance-constrainee certification, which smooths the base classifier's softmax scores instead of its predictions and then uses both their expected value and variance to certify robustness (proof in F.3):
Theorem 5.1 (Variance-constraaneed certification). Given function g X + A mapping from discrete set X to scores from the (1 - 1)-ddmeessoonal probability simplex, let f(x) Negmax,eevEzz..
[g(2)yl with smoothing distribution V, and probability mass function (=) Pre.v [== 1==22 z}. Given an input x E X and smoothed prediction y = (x),, let p = T. E. [g(z)y]
and Ç = Exn.a= (g(()) - w)² with v E R. Assuming S ss, then f(x') = yf
Σ ZEX
Taa Toe (z)
(2) <1+ 5- 2)
1
H 2 (
(m-1) 2
(6)
The l.h.s. of Eq.. 6) is the expected ratio between the probability mass functions of the smoothing distributions for the perturbed (Ta') and unperturbed (Ta) input | It is equal to 1 if both densities are the same, i.e. there is no adversarial perturbation, and greater than otherwise. The r.h.s. of Eq. 6 depends on the expected softmax score μt, a variable v S μ and the expected squared difference Ç between μ and v. For = μ the parameter Ç is the variance of the softmax score. A higher expected value and a lower variance allow us to certify robustness for larger adversarial perturbations.
Applying Theorem 5.1 with flipping distribution F(æ, 0) to each of the D softmax vectors of our model's s outputs yields Io-norm certificates for binary data that can be computed in linear time (see 8 F.31I. In (S F.3.2 we also apply it to the sparsity-aware smoothing distribution (Bojchevski cct al. 2020)) allowing us to differentiate between adversarial deletions and additions of bits. Theo- rem 5.1 can also be generalized to continuous distributions (see & F.3.3 But, for fair comparison with our baselines, we use the certificates of Eiras et al. (2022) as our base certificates for continuous data. In practice, the smoothed classifier and the base certificates cannot be evaluted exactly. One
has to use Monte Carlo sampling to provide guarantees that hold with high probability (see S G).
6 LIMITATIONS
A limitation of our approach is that it assumes soft locality. It can be applied to arbitrary models, but may not necessarily result in better certificates than isotropic smoothing (recall S 4.3) Also, choosing the smoothing distributions requires some 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. But choosing a distribution may be more challenging for other tasks. A limitation of (most) randomized smoothing methods that they use sampling to approximate the smoothed classifier. Because we use multiple distributions, we can only use a fraction of the samples per distri- bution. We can alleviate this problem by sharing smoothing distributions among outputs (see S F. Still, future work should try to improve the sample efficiency of randomized smoothing or develop deterministic base certificates (c.g. by generalizing (Levine & Feizi 2020) to anisotropic distribu- tions), which could then be incorporated into our linear programming framework.
"This term equivalent to the exponential of the Rényi-divergence exp (Da (Vzr [[])) with a 2.

---

Published as a conference paper at ICLR 2023
Avg. cert. radius
0.8
Localized LP
Certified accuracy
0.8
Localized LP
CenterSmooth SegCertily"
Localized Naive
0.6
0.6
SegCertify"
0.4
0.4
0.2
0.2
0.0
0.0
0.15
0.20
0.25
0.30
0.00
0.25
0.50
0.75
1.00
1.25
mIOU
Adversarial budget
Figure Comparison of isotropic smoothing with iso E (0..0....., 3.53 to our LP-based cer- tificate with (Amiu maxx) (oiso. o0), using modified, strictly local U-Net on Pascal-VOOe VOC. Localized smoothing offers the same mIOU as SegCertify' and stronger robustness certificates.
Figure Certified accuracy of U-Net on Pascal-VOC. We compare SegCertify" (Tiso 0.2) to localized smoothing ((Tmin: m (0.15, 1.0)). Combining the base certificates (dashed blue line) via our collective LP (solid blue line) outperforms the baseline.
7 EXPERIMENTAL EVALUATION
In this section, we compare our method all existing collective certificates for fn-norm perturba- tions: Center smoothing using isotropic Gaussian noise (Kumar & Goldstein 2021), SegCertify (Fis-)
cher et al. 2021) and the collective certificates of Schuucardt et al. (2021). To compare SegCertify to the other methods, we report the number of certifiably robust predictions and not just whether all predictions are robust. We write SegCertify" to highlight this. When considering models that are not strictly local (i.e. all outputs depend on all inputs) the certificates of [Schuchardt al. (2021) and Fischer et al. (202I) are identical, i.c., do not have to be evaluated separately. A more detailed description of the experimental setup, hardware and computational cost be found in inB C
Metrics. Evaluating randomized smoothing methods based on certificate strength alone is not suf- ficient. Different distributions lead to different tradeoffs between prediction quality and certifiable robustness (as discussed in $ 4.3) As metrics for prediction quality, we use accuracy and mean inter- The section over union (mIOU) The main metric for certificate strength is the certified accuracy E(t), i.e. the percentage of predictions that are correct and certifiably robust, given adversarial budget Following (Schuchardt al. 2021). we use the average certifiable radius (ACR) as an aggregate metric, i.c. >n En (E(en) E(En+1) with budgets E I 62. S eN and E = 0, E(EN) = 0.
Evaluation procedure. We assess the accuracy-robustnee accuracy mIOU and ACR for a wide range of smoothing distribution parameters. We then elimi- nate all points that are Pareto-dominated i.c. for which there exist diffent parameter values that yield higher accuracy mIOU and ACR. Finally, we assess to if localized smoothing dominates the base- lines, i.e. whether it can be parameterized to achieve strictly better accuracy-robustne tradeoffs.
tradeoff of each method by computing
7.1 IMAGE SEGMENTATION
Dataset and model. We evaluate our certificate for la perturbations on 100 images from the Pascal- VOC (Everingham et al., 2010) 2012 segmentation validation set. Training is performed on 10582 samples extracted from SBD, also known as "Pascal trainaug" (Hariharan et al. 2011). Additional experiments Cityscapes (Cordts et al. 2016) can be found in S A To increase batch sizes and thus allow a thorough investigation of different smoothing parameters, all images are downscaled to 50% of their original size, similar to (Fischer et al.) 2021). Our base model is a U-Net segmentation model (Ronneberger et al. (2015) with a ResNet-11 18 backbone. For isotropic randomized smoothing, use Gaussian noise N (0, diso) with different aiso E {0.01, 0.02, .., 0.5). To perform local- ized randomized smoothing, we choose parameters Tmin mmax E R4 and partition all images into regular grids (similar to Fig. l). To smooth outputs in grid cell (i.j), we sample noise for grid cell (k, 1) from (100 o' 1), with o' E [Amin; mmax] chosen proportional to the distance of (i,j) and
*I.e. add up confusion matrices the entire dataset, compute per-class IOUs and average over all classes.

---

Published as a conference paper at ICLR 2023
1.00
Avg. cert. radius
Localized LP
Avg. cert. radius
Localized LP
1.00
0.75
CenterSmooth SegCentify"
CenterSmooth
0.75
SegCertify"
0.50
MAK
0.50
0.25
*%
*x
0.25
x
xx
Rx
0.00
0.1
0.2
0.4
0.5
0.6
0.1
0.2
0.3
0.4
0.5
0.6
mIOU
mIOu
(a) 10240 samples per output pixel.
(b) 15 times as many samples for basclines.
Figure 4: Comparison of isotropic smoothing to our LP-based certificate with 3 x grid and U- Net on Pascal-VOC. U-Net is sufficiently local to benefit from localized smoothing (Fig. 4a), but not enough to offset the increased sample complexity (Fi.. 4b) for the probabilistic base certificates.
(k.)) (more details in S C.2 All training data is randomly perturbed using samples from the same smoothing distribution that is used for certification.
rccuracy-robustness tradeoff under strict locality. Our goal is verify that, if a model is suffi- ciently local, localized smoothing offers a better accuracy-robustned ing. As an extreme example, we construct a strictly local model from our U-Net segmentation model. This modified model partitions each image into a grid of size 2 x 2. It then iterates over cells (i,,)), sets all values outside (i, to 0 and applies the original model. Finally, it stitches all 4 segmentation masks into a single one. For such a strictly local model, we can apply localized smoothing with the same 2 x 2 grid and max - oo to recover the certificate of Schuchardt et al. (2021) (see ($ 1 Fig. 2 compares the resulting trade-off for min Tisn to that of both isotropic smoothing baselines using 153600 Monte Carlo samples. Localized smoothing yields the same mIOUs as SegCertify'. but up to 22.4 p.p. larger ACR. Both approaches Pareto-dominate center smoothing.
tradeoff than isotropic smooth-
eecuracy-robustess tradeoff under soft locality. Next, we want to verify our claim about the ex- istence of softly local models for which localized smoothing is beneficial. To this end, we randomly smooth the U-Net model itself, without using masking to enforce strict locality. We perform local- ized smoothing with grid size 3 5, various min E {0.01, 0.02. .... 0.5), max O
[0.02, 1.0] and 10240 samples per output pixel (i.e. 10240 15 = 153600 samples in total). Isotropic smoothing is also performed with 10240 samples per output pixel. Fig. 4a shows that localized smoothing Pareto- dominates SegCertify" for high-accuracy models with mIOu > 35.3%. Importantly the figure is not to be read like a line graph! Even if the vertical distance between two methods is small, one may significantly outperform the other. For example, Tiso = 0.1, with an mIOU of 46. 66.3%% and an ACR of 0.24 (highlighted with bold cross) is dominated by (amin: 0 m = (0.09, 0.2) (highlighted with large circle), which has larger ACR of 0.25 and a mIOU that is a whole 6.1 p.p. higher.
Benefit of linear programming. Fig. 3 demonstrates how the linear program derived ables this improved tradeoff. We compare SegCertify' with Diso 0.2 to localized smoothing with (amin; max) = (0.15, 1.0). Naïvely combining the base certificates (dashed line) is not sufficient for outperforming the baseline, as they cannot certify robustness beyond 0.45. However, solving the collective LP (solid blue line) extends the maximum certifiable radius to e 1.15.
4.1 en-
Sample efficiency. Using the same number of samples per output pixel for both localized and isotropic smoothing neglects that localized smoothing requires sampling from 15 different distri- butions, i.e. sampling 15 times as many images [ In Fig. 4b we allow the baselines to sample the same number of images. Now, localized smoothing is mostly dominated by SegCertify', except for high-accuracy models with mIOU E [52.4%, 57.8%...... or mIOU 60.8%. We conclude that U-Net is local enough to henefit from localized smoothing, but not enough to offset the practical problem of having to work with fewer Monte Carlo samples (see also discusion in ( 6) in the entire range of possible isotropic smoothing parameters. Note, however, that we can always recover the guarantees of SegCertify" by using
grid (see Hb.
"Note that they never evaluated their approach on image segmentation.
"This is however necessary for the previously discussed strictly local model.
8

---

Published as a conference paper at ICLR 2023
20
Localized
Localized LP SpanseSmooth
Avg. cert. radius
SparseSmooth
Avg. cert. radius
15
10
2
0.4
0.5
0.7
0.8
0.5
0.6
Accuracy
Accuracy
(a) Robustness to deletions, using S (z. 8)). (b) Robustness additions, using S (ar, 0.01, 0-).
Figure 5: Comparison of our LP-based collective certificate to Bojchevski et al. (2020), using APPNP on Citeseer. We consider both adversarial deletions (Fig. 5a and additions (Fig. 5b) of attribute bits. Locally smoothed models offer a better accuracy-robustress. tradeoff. especially for deletions. Transparent points signal that they are Pareto-dominated by points from the same method.
7.2 NODE CLASSIFICATION ON CITESEER
Dataset and model. Finally, we consider models that are designed with locality in mind: Graph neural networks. We take APPNP (Klicpera et al.) 2019), which aggregates per-node predictions from the entire graph based on personalized pagerank scores, and apply it to the Citeseer (Sen al., 2008) dataset. To certify its robustness, we perform randomized smoothing with sparsity- aware noise S (ar, 0+ ))). where 0+ and 0 control the probability of randomly adding deleting node attributes, respectively (more details in F3.22. As a baseline we apply the tight certificate SparseS- mooth of Bojchevski et al. (0000) to distributions S (ax, 0.01, ( with 8
0.15,.. ... 0.95).
The small addıtion probability 0.01 is meant to preserve the sparsity of the graph's 's attribute matrix and was used in most experiments in (Bojchevski et al. 2020). For localized smoothing, we partition the graph into clusters and define a minimum deletion probability 6 6min E (0.1,0.15,... ... 0.95}.
We then sample each cluster's 's attributes from S (x, 0.01, 0' with 0' E mimn 0.95] chosen based on cluster affinity. To compute the base certificates, we use the aariance-constranned certificate from & F.3.2] In all cases, we take 5 10 samples (i.e. 10 per cluster for localized smoothing). Further discussions, as well as experiments on different models and datasets can be found in
Accuracy-robustees tradeoff. Fig. 5 shows the accuracy and ACR pairs achieved by the naive isotropic smoothing certificate and the LP-based certificate for localized smoothing. Despite hav- ing fewer samples per prediction, our method outperforms the baseline, offering higher accuracy certifying larger ACRs, especially for attribute deletions. Notably, in some cases, our approach improves accuracy by over p.p. percentage points compared to isotropically smoothed mod- els. Similar to the observation made by [Bojcheyski et al. (2020) in their Section K, we also find improve accuracy some extent. We posit that localized smoothing can leverage this phenomenon as form of test-time regularization while preserving the crucial attributes of nearby nodes. In B.] we show that the stems from the smoothing scheme and is not solely due to using our novel conaurcee certificate.
that increasing the probability of attribute perturbations
8 CONCLUSION
We proposed a novel approach to achieve provable collective robustness in multi-output classi- fiers that extends beyond strict locality, utilizing our introduced localized randomized smoothing scheme. Our approach involves smoothing different outputs with anisotropic smoothing distribu- tions that match the model's soft locality. We demonstrated how per-output certificates obtained through localized smoothing can be combined into a strong collective robustness certificate using (mixed-integer) linear programming. Our experiments indicate that localized smoothing can achieve superior eccuracy-robustiee tradeoffs compared to isotropic smoothing methods. However, not all models match our distance-based locality assumption, particularly for image segmentation tasks. Node classification tasks more amenable to localized smoothing due to their inherent locality. Our results highlight the importance of locality in achieving collective robustness and emphasize the need for future research to develop effective local models for multi-output tasks.

---

Published as a conference paper at ICLR 2023
9 REPRODUCIBILITY STATEMENT
We prove all theoretic results that were not already derived in the main text in $ ensure reproducibility of the experimental results provide detailed descriptions of the evaluation process with the respective parameters in S C An implementation, including configuration files, will be made available
D
to
G
To
smoothing
10 ETHICS STATEMENT
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 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 avoid. We believe that it still necessary further research robustness of machine learning models as the positive effects can outweigh the negatíves, but it is necessary to discuss the ethical implications of the usage in any specific application area.
11 ACKNOWLEDGEMENTS
This research is funded by the Bavarian Ministry of Economic Affairs, Regional Development and Energy with funds from the Hightech Agenda Bayern. Further, it is supported by the German Re- search Foundation, grant GU 1409/4-1.
REFERENCES
T.W. Anderson. Confidence limits for the value of an arbitrary bounded random variable with a con- tinuous distribution function. In Bulletin The International and Statistical Institute, volume 43, pp. 249-2511 1969.
Yonatan Belinkov and Yonatan Bisk. Synthetic and natural noise both break neural machine trans- lation. In International Conference on Learning Representations, 2018.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In International Conference on Learning Representations, 2018.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Advances in Neural Information Processing Systems, volume 32, 2019.
Alcksandar Bojehevski. Johannes Klicpera, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, 2020.
Gregory Bonaert, Dimitar I. Dimitrov, Maximilian Baader, and Martin Vechev. Fast and precise cer- tification of transformers. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2021.
Carlo Bonferroni. Teoria statistica delle classi calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali Firenze, 8:3-62, 1936.
G. Bradski. The OpenCV Library. Dr. Dobb's Journal of Software Tools, 2000.
Alexander Buslaev, Vladimir I. Iglovikov, Eugene Khvedchenya, Alex Parinov, Mikhail Druzhinin, and Alexandr A. Kalinin. Albumentations: Fast and flexible image augmentations. Information, 11, 2020.
Liang-Chie Chich Chen, George Papandreou, Florian Schroff, and Hartwig Adam. Rethinking atrous convolution for semantic image segmentation, 2017.
10

---

Published as a conference paper at ICLR 2023
Ruoxin Chen, Zenan Li. Jie Li, Junchi Yan, and Chentao Wu. On collective robustness of bag- ging against data poisoning. In Proceedings of the 39th International Conference on Machine Learning. 2022.
C. Clopper and E. S. Pearson. The use of confidence fiducial limits illustrated in the case of the binomial. Biometrika, 36:4044415 1934.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Proceedings of the 36th International Conference on Machine Learning, 2019.
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Steven Diamond and Stephen Boyd. CVXPY: Python-emheddded modeling language for convex optimization. Journal of Machine Learning Research, 2016.
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic Minimax Character of the Sample Distribu- tion Function and the Classical Multinomial Estimator. The Annals of Mathematical Statistics, 27:642 669, 1956.
Francisco Eiras. Motasem Alfarra. Philip Torr, M. Pawan Kumar, Puneet K. Dokania, Bernard Ghanem, and Adel Bibi. ANCER: Anisotropic certification via sample-wise volume maximiza- tion. Transactions on Machine Learning Research, 2022.
Mark Everingham, Lue Gool, Christopher K. Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. Int. J. Comput. Vision, 88:303-338, June 2010.
Mare Fischer, Maximilian Baader, and Martin Vechev. Certified defense image transformations via randomized smoothing. In Advances in Neural Information Processing Systems, 2020.
Marc Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via random- ized smoothing. In International Conference on Machine Learning. 2021.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used uni- variate continuous distributions. Information Sciences, 249:124-1311 2013.
Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik. Se- mantic contours from inverse detectors. In 2011 International Conference on Computer Vision, 2011.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2):65-70, 1979.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on Scientific Computing, 20(1):359-33) 1998.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Ching- Thing-Yun Ko, Zhaoyang Lyu, Lily Weng, Luca Daniel, Ngai Wong, and Dahua Lin. POPQORN: Quantifying robustness of recurrent neural networks. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Aounon Kumar and Tom Goldstein. Center smoothing: Provable robustness for functions with metric-space outputs. In Advances in Neural Information Processing Systems, 2021.

---

Published as a conference paper at ICLR 2023
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. In Advances in Neural Information Processing Systems, 2020.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, pp. 656-672, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, 2019.
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In Advances in Neural Information P Processing Systems, 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, 2019.
Yongge Liu, Jianzhuang Yu, and Yahong Han. Understanding the effective receptive field in seman- tic image segmentation. Multimedia Tools and Applications, 77(17):22159-22 22171, 2018.
Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel. Understanding the effective receptive field in deep convolutional neural networks. Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
MOSEK ApS. MOSEK Optimizer API Python 9.2.66, 2019. URL hwwph:tttt/ooooo mosek. com/ 9. http999.pppthhoo.pp/. hindap/p//iiiii.iiieeeee html
Olaf Ronneherger, Philipp Fischer, and Thomas Brox U-net: Convolutional networks for biomed- ical image segmentation. In Medical Image Computing and Computer-Assisted Intervention MICCAI 2015, 2015.
Wonryong Ryou, Jiayu Chen, Mislav Balunovic, Gagandeep Singh, Andrei Dan, and Martin Vechev. Scalable polyhedral verification of recurrent neural networks. In Alexandra Silva and K. Rus- tan M. Leino (eds.), Computer Aided Verification, 2021.
Jan Schuchardt, Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference Learning Representations, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rate Collective classification in network data. Al Magazine, 29:93, 2008
Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James Tin- Yau Kwok. Sparsebert: Rethinking the importance analysis in self-attention. In Marina Meila and Tong Zhang (eds.). Proceedings the 38th International Conference Machine Learning, 2021.
the
Zhouxing Shi, Huan Zhang, Kai-Wei Chang, Minlie Huang, and Cho-Jui Hsieh. Robustness verifi- cation for transformers. In International Conference Learning Representations, 2020.
Christian Szegedy. Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
Hoang-Dung Tran, Neelanjana Pal, Patrick Musau, Diego Manzanas Lopez, Nathaniel Hamilton, Xiaodong Yang, Stanley Bak, and Taylor T. Johnson. Robustness verification of semantic seg- mentation neural networks using relaxed reachability. In Computer Aided Verification, 2021.
Cihang Xie. Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adversar- ial examples for semantic segmentation and object detection. International Conference on Computer Vision 2017.
12

---

Published as a conference paper at ICLR 2023
Pavel Yakubovskiy. Segmentation models pytorch. seqmentation modelsmdeels... pytorch, 2020.
https://github.c com qubvel
Maksym Yatsura, Kaspar Sakmann, N. Grace Hua, Matthias Hein, and Jan Hendrik Metzen. Certi- fied defences against adversarial patch attacks semantic segmentation. In Workshop on Trust- worthy and Socially Responsible Machine Learning, NeurIPS 2022, 2022.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certification with randomized smoothing: functional optimization based framework. In Advances Neural Information Processing Systems, 2020.
Daniel Zügner and Stephan Günnemann. Adversarial attacks graph neural networks via meta learning. International Conference on Learning Representations, 2019.
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph con- volutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Daniel Zügner and Stephan Günnnemann. Certifiable robustness of graph convolutional networks under structure perturbations. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2020.
13

---

Published as a conference paper at ICLR 2023
Image Segmentation on CityScapes
15
Additional Experiments on Node Classification
16
B.1
Comparison the Naive Variance-constraateed Isotropic Smoothing Certificate
16
B.2
Node Classification using Graph Convolutional Networks
16
Node classification Co
17
4
Lower Certifiblle Robustmess to Additions
18
B.5
Benefit of Linear Programming Certificates
19
Detailed Experimental Setup
21
Certificate Strength Metries
21
Semantic Segmentation
Node Classification
22
Hardware and runtime
23
D
Proof of Theorem 4.2
24
Improving Efficiency
25
E.1 Sharing Smoothing Distributions Among Outputs
................................
25
E.2 Quantizing Certificate Parameters
................................
25
Sharing Noise Levels Among Inputs
................................
26
Linear Relaxation
27
Base Certificates
28
Gaussian Smoothing for la Perturbations of Continuous Data
................................
28
Uniform Smoothing for | Perturbations Continuous Data
.
29
Variance-Constraing Certification
29
Monte Carlo Randomized Smoothing
38
Monte Carlo Base Certificates for Continuous Data
................................
38
2
Monte Carlo Variance-Constrraieed Certification
39
G.3 Monte Carlo Center Smoothing
40
Multiple Comparisons Problem
Comparison the Collective Certificate of Fischer et al. (2021)
42
Comparison to the Collective Certificate of Schuchardi et al. (2021)
43
The Collective Certificate
1.2 Proof of Subsumption
44
14

---

Published as a conference paper at ICLR 2023
1.0
Localized LP
1.0
Localized LP
Avg. 0ert. radius
0.8
X
ConterSmooth SegCortify
Avg. cert. radius
0.8
X
SegCertify*
CenterSmooth
0.6
0.4
0.2
0.2
0.0
0.0
0.0
0.6
0.0
0.1
0.2
0.3
0.8
mIOU
mIOU
(a) 153600 samples per output pixel.
(b)
153600
samples per output pixel for localized LP.
24
Figure 6: Comparison of our LP-based collective certificate for localized randomized smoothing
with a 3 x 5 grid to CenterSmooth and SegCertify", using DeepLabV3 on Cityscapes. Increasing the number of samples used for certifying each output from 6400 for the baselines) closes the gap between localized randomized smoothing and SegCertify. Still,
153600 153600 (same as
24
localized smoothing only offers stronger certificates for models with mIOU S 0.21 (compared to mIOU < 0.11 when using fewer samples).
A IMAGE SEGMENTATION ON CITYSCAPES
In the following, we apply our approach to DeepLaby3 (Chen et al. 2017) models trained on the Cityscapes (Cordts et al. 2016) training set. We evaluate the certificates on 50 images from the validation set. For localized smoothing. we partition the image into grid of shape 4 x To limit the number of LP variables despite the increased resolution, we quantize the base certificate parameters (7(") into 2048 bins (see E.2). Different from our experiments on Pascal-VOC and due to the increased computational cost of using higher-dimensional images, the locally smoothed models are not trained on the localized smoothing distribution with parameters (Amin: max)). Instead, we use model trained with isotropic Gaussian noise with standard deviation diso = Omin-
Fig. salss that, even when allowing 153600 samples per output pixel for both localized smooth- ing and the baselines (i.e. localized smoothing gets to sample 24 times as many images), most choices of (amin, max) do not offer higher accuracy and robustness than SegCertify' except those leading to a small mIOU below 0.21. Fig. 6b shows that reducing the number of samples per output pixel for localized smoothing to 6400 153600 further weakens the certificate. There, localized smoothing only offers stronger certificates for models with an mIOU below 0.11.
There are three possible explanations for why localized smoothing does not outperform SegCertify" The first one that we do not train on the same distribution that we use for certification, so our models are less accurate or less consistent in their predictions, which reduces mIOU certified robustness. The second one is that our simplisitic choice of localized smoothing based on grid cell distance (see [ C.2) does not match the actual locality structure of DeepLabv3. The last is that DeepLabv3, which uses dilated convolutions to increase the receptive field size in each layer, just inherently less local than the U-Net architecture used in our experiments on Pascal- VOC. Nevertheless, it should be noted that we can always parameterize localized smoothing to obtain the same results as SegCertify (see Appendix Hh.
15

---

Published as a conference paper at ICLR 2023
B ADDITIONAL EXPERIMENTS ON NODE CLASSIHICATION
In the following, we perform additional experiments on graph neural networks for node classifica- tion, including different model and additional dataset. Unless otherwise stated, details the experimental setup are identical to 7.2 In particular, we use sparsity- smoothing distribution (æ, 0.01, ). where probability of deleting bits 0- either constant across the entire graph (for the isotropic randomized smoothing baseline) or adjusted per output and cluster based on cluster affinity (for localized randomized smoothing).
20
20
Localized LP
Localized LP
Avg. cert. radius
15
SparseSmooth
Avg. cert. radius
15
x
Variance Cert.
10
x
x
0
0.4
0.5
0.6
0.7
0.8
0.4
0.5
0.6
0.7
0.8
Accuracy
Accuracy
(a) Using (Bojchevski al. 2020 for the naive (b) Using variance-constrained certification for the naive isotropic smoothing baseline.
isotropic smoothing baseline.
Figure 7: Analysis of our LP-based collective certificate using APPNP on Citeseer. We use the sparsity-aware smoothing with S (xx 0.01, 0 to certify robustness to deletions. In Fig. 7a we use the certificate of |Bojchevski et al. (2020) for baseline (identical to Fig. 5a In Fig. 7b we use constrre- certification (see [Theorem 5.1) baseline. In both cases, there are locally
smoothed models with a higher accuracy than any of the isotropically smoothed models and signifi- cantly larger average certifiable radii.
B.1 COMPARISON TO THE NAIVE VARIANCE-CONSTRAEE ISOTROPIC SMOOTHING CERTIFICATE
In Fig. of S 7.2 we observed that locally smoothed models surprisingly did not only achieve up to three times higher average certifiable radii, but simultaneously had higher accuracy than any of the isotropically smoothed models. One potential explanation is that we used variance-constraing certification (see Theorem 5.1) (i.c. smoothing the models' softmax scores instead of their predicted labels) for localized smoothing, but not for the isotropic smoothing baseline. This might result in two substantially different models. To investigate this, we repeat the experiment from Fig. 5a using variance-constrained certification for both localized smoothing and the isotropic smoothing baseline. Fig. 7 shows that, no matter which smoothing paradigm we use for our isotropic smoothing baseline, there c.a. 7 p.p. difference in accuracy between the most accurate isotropically smoothed model and the most accurate locally smoothed model.
Interestingly, even auriance-constrainee smoothing with isotropic noise (green crosses in Fig. 7b) is sufficient for outperforming the isotropic smoothing certificate of (Bojchevski et al. (2020) (orange stars in Fig. 7ap. This showcases that variance-constrained certification does not only present very efficient, but also very effective way of certifying robustness on discrete data (even when entirely ignoring the collective robustness aspect).
B.2 NODE CLASSIFICATION USING GRAPH CONVOLUTIONAL NETWORKS
So far, we have only used APPNP models as our base classifier. Now, we repeat our experiments using 6-layer Graph Convolutional Networks (GCN) (Kipf & Welling 2017). In each layer, GCNs first apply a linear layer to each node's ' latent vector and then average over each node's 's 1-hop neigh- borhood. Thus, 6-layer GCN classifies each node using attributes from all nodes in its 6-hop neighborhood, which covers most or all of the Citeseer graph. Aside from using GCN instead of APPNP the base model, we leave the experimental setup from 7.2 unchanged. Note that GCNs
16

---

Published as a conference paper at ICLR 2023
Localiaed SparseSmooth
Localized SparseSmooth
Avg. cert. radius
Avg. cert. radius
-]
3
2
6
0
0
0.40
0.45
0.50
0.35
0.60
0.65
0.70
0.75
0.40
0.45
0.50
0.55
0.60
0.65
0.70
0.75
0.80
Accuracy
Accuracy
(a) Robustness to deletions, using S (a, 0.01, 0-).
(b) Robustness to additions, using S (ax, 0.01,07).
Figure Comparison of our LP-based collective certificate for localized randomized smooth- ing to SparseSmooth, using a 6-layer GCN on Citeseer. We consider both adversarial deletions (Fig. 8a) and additions (Fig. 8b). Some locally smoothed models have a higher accuracy than any of the isotropically smoothed models. However, our certificate only dominates the best isotropi- cally smoothed models when considering robustness to deletions, not when considering robustness to additions. This can either be attributed to lower locality in deep GCNs variance-constrainee certification yielding weak base certificates for addition when #+ is small.
typically used with fewer layers. However, these shallow models are strictly local and it has already been established that the certificate SSchuchardt et al. (202T) which is subsumed by our certificate (see S 1.2) can provide very strong robustness guarantees for them. We therefore in- crease the number of layers to obtain model that is not strictly local.
Fig. shows the results for both robustness to deletions and robustness to additions. Similar to APPNP, some locally smoothed models have an up to 4 p.p. higher accuracy than the most accurate isotropically smoothed model. When considering robustness deletions, the locally smoothed mod- els Pareto-dominate all of the isotropically smoothed models, i.c. offer better accuracy-robustte tradcoffs. Some can guarantee average certifiable radii that are at least 50% larger than those of the baseline. When considering robustness to additions however, some of the isotropically smoothed models have a higher certifiably robustness.
We see two potential causes for our method's lower certifiable robustness to additions: The first po- tential cause that the GCN may less local than APPNP or that has a different form of locality that does not match our clustering- based localized smoothing distributions. This appears plausi- ble, as GCN averages uniformly over each neighborhood, whereas APPNP aggregates predictions based pagerank scores. APPNP may thus primarily attend to specific, densely connected nodes, making it more local than GCN. The second potential cause is that the variance-constraine certifi- cate
as base certificate may be less effective when certifying robustness to adversarial additions by using very small addition probablity like A+ = 0.01. Afterall, we have also seen in our experiments with APPNP [$ 7.2 that the gap in average certifiable radii between localized and isotropic smoothing was significantly smaller when considering additions. We investigate this second potential cause more detail in $ B.4
B.3 NODE CLASSIFICATION ON CORA-ML
Next, we repeat our experiments with APPNP on the Cora-ML (McCallum et al.) 2000 Bojchevski Günnemann 2018) node classification dataset, keeping all other parameters fixed. The results are shown in Fig. 9. Unlike on Citeseer, the locally smoothed models have a slightly reduced accuracy compared to the isotropically smoothed models. This can either attributed to one smoothing ap- proach having more desirable regularizing effect on the neural network, the fact that we smooth softmax scores instead of predicted labels when constructing the locally smoothed models. Never- theless, when considering adversarial deletions, localized smoothing makes it possible achieve average certifiable radii that are least 50% larger than any of the isotropically smoothed models' the cost of slightly reduced accuracy 8.6%. Or, for another point of the pareto front, in-
17

---

Published as a conference paper at ICLR 2023
Localized SparseSmooth
Avg. cert. radius
Avg. cert. radius
16
3
10
2
5
Localized SparseSmooth
0
0.4
0.5
0.6
0.7
0.9
0.0
0.2
0.6
Accuracy
Accuracy
(a) Robustness to deletions, using S (ax 0.01, 0-).
(b) Robustness to additions, using S (æx, 0.01, 0.
Figure 9: Comparison of our LP-based collective certificate for localized randomized smoothing to the SparseSmooth (Bojchevski et al., 2020), using APPNP on Cora-ML. We consider both ad- versarial deletions Fig. 9a) and additions (Fig. 9b). Some locally smoothed models that have higher accuracy than any of the isotropically smoothed models. However, our method is only able to dominate all isotropically smoothed models when considering robustness to deletions, not when considering robustness to additions. This can either be attributed to lower locality in deep GCNs or variance-constrained certification yielding weak base certificates for addition when # is small.
crease the certificate by 20% while reducing the accuracy by 2.8 percentage points. As before, the certificates for attribute additions are significantly weaker.
B.4 LOWER CERTIFIABLE ROBUSTNESS TO ADDITIONS
Localized
Localized
Avg. cert. radius
SparseSmooth
Avg. cert. radius
4
3
3
2
2
0.40
0.45
0.50
0.55
0.60
0.65
0.70
0.75
0.80
0.40
0.45
0.50
0.55
0.60
0.65
0.70
0.75
0.80
Accuracy
Accuracy
(a) Using (Bojehevski isotropic smoothing certificate.
2020 for the naive
Using variance-conssrained certification for the naive isotropic smoothing certificate.
Figure 10: Comparison of our LP-based collective certificate for localized randomized smoothing to SporseSmooth and to a naive combination of its base certificates, using GCN and adversarial additions Citeseer. Fig. Thalshows that the L.P-aaed certificate is outperformed by naïve isotropic smoothing. Fig. 10b shows that this is largely due to the variance-constrainee base certificates (green crosses) for adversarial additions being much weaker than the isotropic smoothing certificate of (Bojchevski et al. 2020) in Fig. 10al
While our certificates for adversarial deletions have compared favorably to the isotropic smoothing baseline in all previous experiments, our certificates for adversarial additions were comparatively weaker on Cora-ML and when using GCNs as base models. In the following, investigate to what extend this can be attributed to our use of variance-comstrained certification for our base certificates.
Fig. 10al shows both our linear programming collective certificate and the naïve isotropic smooth- ing certificate based on (Bojchevski et al. 2020) for GCNs on Citeseer under adversarial additions. In Fig. 10b plot not only the LP-based certificates, but also variance-constrained base cer- tificates (drawn as green crosses). Comparing both figures shows that our base certificate's 's average certifiable radii are at least 50% smaller than the largest ACR achieved by (Bojchevski et al. 2020
18

---

Published as a conference paper at ICLR 2023
in Fig. 10a While our linear program significantly improves upon them, it is not sufficient to over- come this significant gap. This result in stark contrast to our results for attribute deletions | B.1 where the constrae- base certificates alone were enough to significantly outperform the certificate of (Bojchevski et al. 2020).
Now that have established that the variance-constrannee base certificates appear significantly weaker for additions, we can analyze why. For this, recall that our base certificates are parameterized by weight vector w (see Definition 4.1), with smaller values corresponding higher robustness or two weight vectors w² u0 quantifying robustness to adversarial additions and deletions, respectively (see $ F.3.2.. Using our results from F.3.2 we can draw the weights w resulting from smoothing distribution S (æ, 0.01, 0 (-) as a function of t-. Fig. 1la shows that 0 has to be brought very close to order to guarantee high robustness deletions, effectively deleting almost all attributes in the graph. Alternatively, one can also increase the addition probability A+ to perhaps 10% or 20%. But this would utterly destroy the sparsity of the graph's 's attribute matrix. We can conclude that, while variance-consttrained certification can principle provide strong certificates for attribute deletions, might be worse choice than the method of Bojcchvski et al. (2020) for very sparse datasets that force the use of very low addition probabilities 8
32
3
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0-
8+
(a) Certificate weight = for (ar, (ar, 0.01, 0-) for (b) Certificate weight w for (ax, 0+, 0.6) for vary- varying 0
ing 6
Figure 11: Base certificate weight w+ of the suriance-constrainee sparsity-award smoothing certifi- cate for varying distribution parameters. Certifying high robustness to adversarial additions (i.e. ob- taining small weights) requires either setting high probability for random additions even higher probability for random deletions.
B.5 BENEFIT OF LINEAR PROGRAMMING CERTIFICATES
As we did for our experiments image segmentation (see Fig. we can inspect the certified accuracy curves specific smoothed models more detail to gain a better understanding of how the collective linear programming certificate enables larger average certifiable radii. We use the same experimental setup as in S 7.2 i.c. APPNP on Citeseer, and certify robustness to deletions. We compare the certifiably most robust isotropically smoothed model (0 0.8, ACR 5.67 to the locally smoothed model with 6 0. 0.75, A+ 0.95. For the locally smoothed models, compute both I.P-based collective certificate, as well as the naïve collective certificate.
Fig. 12 shows that naïvely combining the localized smoothing base certificates obtained via variance-constrainee certification (dashed blue line) is sufficient for outperforming the naïve isotropic smoothing certificate. This speaks its effectiveness deletions. Combining the base certificates via linear programming (solid blue line) significantly enlarges this gap. leading to even larger maximum and average certifiable radii.
certificate against adversarial
19

---

Published as a conference paper at ICLR 2023
Certified accuracy
Localized LP
0.8
Localized Naive
0.6
SparseSmooth
0.4
0.0
10
40
Number of adversarial deletions
Figure 12: Certified accuracy of APPNP on Citeseer. We compare the naive isotropic smoothing certificate of the most robust baseline model (0 0.8) to localized smoothing (0 (0min 0.75). Even naively combining the aariance-constraing outperforming the SparseSmooth certificate for 15 deletions or less. Combining the base certificates via our LP (solid blue line) further extends the certifiable radius and significantly increases the certified accuracy for perturbations with 5 or more deletions.
base certificates (dashed blue line) is sufficient for
20

---

Published as a conference paper at ICLR 2023
C DETAILED EXPERIMENTAL SETUP
In the following, we first explain the metrics we use for measuring the strength of certificates, and how they can be applied the different types of randomized smoothing certificates used in our experiments. We then discuss the specific parameters and hyperparameters for our semantic seg- mentation and node classification experiments. We conclude by specifying the used hardware and comparing the computational cost of Monte Carlo sampling to that of solving the collective linear program.
C.I CERTIFICATE STRENGTH METRICS
We use two metrics for measuring certificate strength: For specific adversarial budgets c, we com- pute the certified accuracy E(e) (i.e. the percentage of correct and certifiably robust predictions). As an aggregate metric, we compute the average certifiable radius, i.e. the lower Riemann integral of E(e) evaluated at EN with 61 0 and E(ex) O. For our experiments on image segmen- tation, we use 81 equidistant points in [0, 4]. For our experiments on node classification, where we certify robustness a discrete number of perturbations, we use e, n. i.c natural numbers. In all experiments, we perform Monte Carlo randomized smoothing (see [ Gj. Therefore, we may have abstain from making predictions. Abstentions are counted as non-robust and incorrect. In the case of center smoothing, either all or no predictions abstain (this is inherent to the method. In our experiments, center smoothing never abstained).
C.1.1 COMPUTING CERTIFIED ACCURACY
The three different types of collective certificate considered in experiments each require a different procedure for computing the certified accuracy. In the following, let (d (I...., } (a(()) = } be the indices of correct predictions, given an input æ.
Naïve collective certificate. The naïve collective certificate certifies each prediction independently. Let (n) be the set of perturbed inputs Yn is certifiably robust to (see Definition 3.1). Let IB be collective perturbation model. Then
{d e (l,..., Dont B, C [H is the set of all certifiably robust predictions. The certified accuracy be computed Dout
[LA2]
Center smoothing Center smoothing used for collective robustness certification does not determine which predictions are robust, but only the number of robust predictions. We therefore have to make the worst-case assumption that the correct predictions the first to be changed by the adversary. Let be the number of certifiably robust predictions. The certified accuracy can then be computed as ma (Dan
Collective certificate. Let ((T) be the optimal value of our collective certificate for the set of targeted nodes T. Then the certified accuracy can be computed via ((T) with T Z.
Dout
C.2 SEMANTIC SEGMENTATION
Here, we provide all parameters of our experiments on image segmentation.
Models. As base models for the semantic segmentation tasks, we use U-Net (Ronneberger al. 2015) and DeepLabv3 (Chen et al.] (017) segmentation heads with ResNet-18 (He al. 2016 backbone, as implemented by the Pytorch Segmentation Models library (version 0.13) Yakubovskiy 2020). We use the library's 's default parameters. In particular, the inputs 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. For the DeepLabv3 segmentation head, we use all de- fault parameters from Chen al. (2017) and output stride of 16. To avoid dimension mismatches in the segmentation head, all input images are zero- proo-ppdeed to a height and width that is the next multiple of 32.
Data and preprocessing. We evaluate our certificates on the Pascal- VOC 2012 and Cityscapes seg- mentation validation set. We do not the test set, because evaluating metrics like the certified
21

---

Published as a conference paper at ICLR 2023
accuracy requires access to the ground-truth labels. For training the U-Net models on Pascal, use the 10582 Pascal segmentation masks extracted from the SBD dataset (Hariharan et al. 2011) (referred to "Pascal trainaug" or "Pascal augmented training set" in other papers). SBD uses different data split than the official Pascal-VOC 2012 segmentation dataset. We avoid data leakage by removing all training images that appear in the validation set. For training the DeepL.abv3 model on Cityscapes, we use the default training 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 larger range of different smoothing distributions. The segmentation masks are downscaled using nearest-neighhor interpo- lation, 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 512 epochs, using Dice loss and Adam(lr = 0.001, 31 0.9, 32 0.999, 10-8, weight.
= 0). We use a batch size of 128 for Pascal-VOC and a batch size of 32 for Cityscapes. 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: With 50% probability, each image is randomly scaled by factor from [1, 2.0] using the ShiftscaleRRtate augmentation implemented by the Albumentations library (version 0.5.2) (Buslaev et al.) 2020). The images are than cropped to a fixed size of 160 x 256 (for Pascal- VOC) or 384 x 384 (for Cityscapes). Where necessary, the images are padded with zeros. Padded parts of the segmentation mask are ignored by the loss function. After these operations, each input is randomly perturbed using Gaussian noise. For isotropic smoothing, we use a fixed standard deviation diso E {0. 0.0........ 0.53, i.e. we train 51 different models on different isotropic smoothing distributions. For localized smoothing with grid shape H x W and parameters (amin mmax) we perform localized smoothing with a single sample per image. Since this generates W as many perturbed images, perform gradient accumulation, processing H-W of each batch at a time. All samples are clipped to [0, 1] to retain valid RGB-values
Certification. For Pascal-VOC, we evaluate all certificates on the first 100 images from the val- idation set that after downscaling - have a resolution of 166 x 250. For Cityscapes, we use every tenth image from the validation set. For all certificates, smoothing (see discussion in [ G). We use the significance parameter a to 0.01, i.e. all certifi- cates hold with probability 0.99. For the center smoothing baseline, we use the default parameters suggested by the authors (A = 0.05, B = 2, on = (²2). For the naive isotropic randomized smoothing baseline and for localized smoothing, we use Holm correction to account for the multiple comparisons problem, which yields strictly better results than Bonferroni correction (see S G.4). For our localized smoothing distribution, we partition the input image into a regular grid of size H x W (specified in the different paragraphs 7.I) and define minimum standard deviation diin and maximum standard deviation mmax- Let J be the set of all pixel coordinates in grid cell (k. l). To smooth outputs in grid cell (t,j). we use a smoothing distribution A (0, diag(o)) ()) with vk E H., E W],d d E (kk.)
use Monte Carlo randomized
a = min + (omax miin) max (li - 11,, 10 -1)
W
L.c we linearly interpolate between miin and mmax based on the loo distance of grid cells (i.j) and (K, All results are reported for the relaxed linear programming formulation of our collective cer- tificate (see E.4). The collective linear program solved using MOSEK (version 9.2.46) (MOSEK)
ApS. 2019) through the CVXPY interface (version 1.1.13)
C.3 NODE CLASSIFICATION
Here, we provide all parameters of our experiments on node classification.
Model We test two different models: 2-layer APPNP Kliccpra et al., 2019) and 6-layer GCN (Kipf & Welling 2017). For both models we use hidden size of 64 and dropout with a probability of 0.5. For the propagation step of APPNP we use 10 for the number of iterations and 0.15 as the teleport probability.
22

---

Published as a conference paper at ICLR 2023
Data and preprocessing. We evaluate our approach on the Cora-ML and Citeseer node classifi- cation datasets. We perform standard preprocessing, i.e., remove self-loops, make the graph undi- rected and select the largest connected component. We use the same data split as in (Schuchardt et al.
2021), i.e. 20 nodes per class for the train and validation set.
Training and data augmentation All models are trained with learning rate of 0.001 and weight decay of 0.001. The models we use for sparse smoothing are trained with the noise distribution that 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 Ofin and 0 miin.
Certification We evaluate our certificates on the validation nodes. For all certificates, use Monte Carlo randomized smoothing (see discussion in S G). We use 1000 samples for making smoothed predictions and 5 10 samples for certification. We use the significance parameter a to 0.01, i.c. all certificates hold with probability 0.99. For the naïve isotropic randomized smoothing baseline, we use Holm correction to account for the multiple comparisons problem, which yields strictly better results than Bonferroni correction (see [ G.4). For our localized smoothing certificates, we use Bonferroni correction. To parameterize the localized smoothing distribution, we first perform Metis clustering (Karypis & Kumar 1998) to partition the graph into 5 clusters. We create affinity ranking by counting the number of edges which are connecting cluster and j. Specifically, let be the set of clusters given by the Metis clustering. Then we count the number of edges between all cluster pairs and denote it by Ni.- j.j E C. If the number of edges of the pair (i.j) )) is higher than say that, due to the
the number for all other pairs () Vj C, i.e. Na.j > Ne. Vk E C, homophily assumption, cluster i is the most important one for cluster j. We create this ranking for all pairs and use classifying a node of cluster out of the discrete steps of the linear interpolation between mmin and max based on its previously defined ranking between the clusters. An example would be, given 11 clusters, m = 0.0, and 6max 1.0. If cluster j second most important cluster to i, then we would take the second value out of (0.0, 1. 1.03. All results are reported for the relaxed linear programming formulation of our collective certificate (see & F.4). For each cluster, we use 5 of the samples, which corresponds to 200 samples for prediction and 10a 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).
select the noise parameter 0' for smoothing the attributes of cluster while
C.4 HARDWARE AND RUNTIME
The experiments on POC with strictly local models Fig. 2p were performed using a Xeon E5- 26-2630 v4 CPU @ 2.20GHz, an NVIDA GTX 1080TI GPU and 128 GB of RAM. All other exper- iments were performed using an AMD EPYC 7543 CPU @ 2.80GHz, an NVIDA A100 GPU and 128 GB of RAM.
In all cases, the time needed for obtaining the Monte Carlo samples required by both localized and isotropic smoothing was much larger than the cost of solving the collective linear program.
For the strictly local model in Fig. 2, taking 153600 samples took 294s s on average. Aver- aged over all images and adversarial budgets, solving each LP only took 0.91s s.
For the standard U-Net model in Fig. 4 taking 153600 samples took 70.3 on average.
Each LP took 1.8s on average.
For the DeepLabv3 model in Fig. 6b. taking 153600 samples took 1204s on average. Each
LP took 2.788 s on average.
For the APPNP model in Fig. taking 5 10c samples took 1034 on average. Each LP
took 10.9 average.
For graphs, the reported time for solving a single instance of the collective linear program is much higher than for image segmentation, even though the graph datasets require fewer variables. That is because we used different, not as well vectorized formulation of the linear program in CVXPY.
In all cases, the time for calculating the isotropic smoothing certificates and base certificates from the Monte Carlo samples was too small to be measured accurately, since they can be implemented in few simple vector operations.
23

---

Published as a conference paper at ICLR 2023
D PROOF OF THEOREM 4.2
In the following, we prove Theorem 4.2 i.e. we derive the mixed-integer linear program that under- lies our collective certificate and prove that it provides valid bound on the number of simultane- ously robust predictions. The derivation bears some semblance to that of (Schuchardt et al. (021), in that both use standard techniques model indicator functions using binary variables and that both convert optimization in input space to optimization in adversarial budget space. Nevertheless, both methods differ in how they encode and evaluate base certificates, ultimately leading significantly different results (our method encodes each base certificate using only single linear constraint and does not perform any masking operations).
Theorem 4.2. Given locally smoothed model f. input æ E ((i))), smoothed prediction y f()) and base certificates (H) H Dout complying with interface Eq. 2 the number of simultancously robust predictions m E (f' yol is lower-bounded by
RET
beR Pin min
Σ4 hn
(8)
(.E Pout nET
s.t. Vn 6" w (n) 2 (1 - tn (m)) sum e".
Proof. We begin by inserting the definition of our perturbation model Bg and the base certificates (()) into Eq. 1.1
min Σ [T = ynl 2 min e/EB
Στ
o E [H())
(10)
2 E
NET
NET
Din
Din
min
Σ
-1a'a zal < (n) w Σ
(nt)
s.t. Σ
Ial
S e..
a' x'EXPm
WET
d=1
(11)
Evidently, input a' only affects the elementwise distances | x. Rather than optimizing a', we can 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 E R.P. Din (or b E {0, 1] Diu for binary data). Replacing sums with inner products, we can restate Eq. 1l as
s.t. sum(b) S e.. w (n) < ma)
min BER Pm NET
(12)
In a final step, we replace the indicator functions Eq. 12 with a vector of boolean variables
{0, 1) Dout.
fn s.t. Vn bT w (m) 2 (1 - 4n (m), sum S e
min
(13)
BER Pt (0, Pout nET
(14)
The first constraint in Eq. 5 ensures that Ln = < b (n)) > (1()) Therefore, the optimiza-
tion problem in Eq. 13 and Eq. 5 is equivalent to Eq. 12 which by transitivity is lower bound on ming nET
Σ (x.
V.
24

---

Published as a conference paper at ICLR 2023
E IMPROVING EFFICIENCY
In this section, discuss different modifications to our collective certificate that improve its sam- ple efficiency and allow us fine-grained control over the size of the collective linear program. We further discuss linear relaxation of our collective linear program. All of the modifications preserve the soundness of our collective certificate, i.c. we still obtain provable bound on the number of predictions that can be simultaneously attacked by an adversary. To avoid constant case distinc- tions, we first present all results for real-valued data, i.e. X = IR, before mentioning any additional precautions that may be needed when working with binary data.
E. SHARING SMOOTHING DISTRIBUTIONS AMONG OUTPUTS
In principle, our proposed certificate allows a different smoothing distribution viSi) to be used per output 9n of our base model. In practice, where 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 increase the efficiency of our localized smoothing approach by partitioning our Dout outputs into Nout subsets that share the same smooth- ing distributions. 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,... (Naus; with
Nout K ULi
(1...., Dout
(15)
We then associate each set (() with smoothing distribution ! For each base model output gn with n E K()), we then use smoothing distribution ( to construct the smoothed output fn. e.g.
(x) argmax P [f 2) v] (note that for variance-constrained certificate
we smooth the softmax scores instead, see
E.2 QUANTIZING CERTIFICATE PARAMETERS
Recall that our base certificates from $ 5 are defined by a linear inequality: A prediction y, fa( is robust to perturbed input x' x if Σt= (n) | xal < 17("), for some p 2 0. The weight vectors w Rt only depend on the smoothing distributions. A side of effect of sharing the same distribution V among all outputs from set (K()), as discussed in the previous section, that the outputs also share the same weight vector w RDt, with Vn K( w(() (n) Thus, for all smoothed outputs Jn with E K(0) the smoothed prediction ya is robust if Ed, w. - xzll zz)" < (n)
Evidently, the base certificates for outputs from a set K() only differ their parameter ry (x)) Recall that in our collective linear program predictions are robust according to their base certificates (see) Theorem 4.2). If there are two outputs fn and fm with (n() = ()( 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 (+), we only need one indicator variable per unique r7'*). By quantizing the r7(*) within each subset (+) (for example
vector of variables f0. 1) Dout to indicate which
by defining equally sized bins between minnego 17(") and max ()()) ), 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 Drut to Nont Nhins-
To implement this idea, we define a matrix of thresholds E E TR. x Noin with Vi min (E..) S min (177() n E K(0)). We then define a function ; [l,..., ] x R R with
E(i, n) = max ((Ei, | ".....,,Niin A Ei, < m))
(16)
that quantizes base certificate parameter y from output subset (6) by mapping it to the next smallest threshold in E,:- We can then bound the collective robustness of the targeted dimensions T of our
25

---

Published as a conference paper at ICLR 2023
prediction vector y f(x) as follows:
min Σ
E
Tis (oknnTTKK)) (i.)/r)) = Ens
(17)
Nout j Noims)
s.t.
Vi,J w 2 (1- (1-Ti)))ss) sum(b) S
(18)
RpT, T {0, Nout Nuimo
(19)
Constraint Eq. 18 ensures that Ti, is only set to wf Fi. i.e. all predictions from subset K(() whose base certificate parameter v7()) is quantized to Es,y are no longer robust. When this the case, the objective function decreases by the number of these predictions. For Nout Dout Nuins = 1 and F,, = 17(*), we recover our general certificate from Theorem 4.2 Note that, if the quantization maps any parameter r7(") smaller number, the base certificate (H) becomes more
restrictive, i.e. yn is considered robust to a smaller set of perturbed inputs. Thus, Eq. 17 is lower bound on general certificate from Theorem 4.2
E.3 SHARING NOISR LEVELS AMONG INPUTS
Similar to how partitioning the output dimensions allows us to control the number of output variables partitioning the input dimensions and using the same noise level within each partition allows us to control the number of budget variables b.
Assume that we have partitioned our output dimensions into Nout subsets [K()) outputs in each subset sharing the same smoothing distribution V as explained in S E.1 Let us now define Ni, input subsets [[1]. I(N.) with
(Non)) with
UL =
Nin
(20)
Recall that a prediction = fa( with n E ((i) is robust to a perturbed input x' e P if Ed w()) | xal² (n)) and that the weight vectors w(() only depend on the smooth- ing distributions. Assume that we choose each smoothing distribution ( such that 4o E Ni.,. vd, J(M) w w i.c. all input dimensions within each set I[()) have the
same weight. This can be achieved by choosing (t) so that all dimensions in each input subset J are smoothed with the noise level (note that we can still use different smoothing distribution v! for each set of outputs (()). For example, one could use Gaussian distribution with covariance matrix Σ- diag (o)² with VI .L....,NuIh, Vd, d' ((0) oa od.
In this case, the evaluation of our base certificates can be simplified. Prediction y fn()) with n E (x)) is robust to a perturbed input x' E Din if
D
Σ
w
zal? < (n(o) 10'
(21)
d=1
Nin
(1)
Σ
lo'a - xell < <n)(m))
(22)
1=1
demu
with E N and Vi E Nou.. VI NI....,NN..... Vd E J(H) u/ w/- That is, we
can replace each weight vector (+) that has one weight w per input dimension with a smaller weight vector (+) featuring one weight uy (4)
per input subset (()
For our linear program, this means that we no longer need a budget vector E Din to model the elementwise distance |='s zzll in each dimension d. Instead, we can use a smaller budget vector E R.Y.. to model the overall distance within each input subset ("), ie. ((t) = =dego: |ar, - zz!". Combined with the quantization of certificate parameters from the previous section, optimization
26

---

Published as a conference paper at ICLR 2023
problem becomes
min
Σ
E
Tws K & (i.)(()) E
(23)
Nom. JE(I.....NG Noime)
s.t.
Vi,j : bbb""""""
Bis) sum(b) Se, TE {0, 13 Mous Noins
(24)
E RM
(25)
with u E N and Vi (1...., 4A Nin Din Nbins and Es, = - we recover our general certificate from Theorem 4.2
Nout).
(I...., Nu. AA E : u/ w For Nout Douts
When certifying robustness binary data, we impose different constraints on adversary can not flip more bits than are present within each subset, we use budget vector b E N with VI E fl...., N,...,,Nn)> : b I | instead continuous budget vector b E RR....
model that the
E.4 LINEAR RELAXATION
Combining the previous steps allows to reduce the number of problem variables and linear con- straints from Din + Dout and Dout + 1 to Nin + Nout Nims and Nout Nasss + 1, respectively. Still, finding an optimal solution the mixed-integer linear program may be too expensive. One can obtain lower bound on the optimal value and thus valid, albeit more pessimistic, robustness certificate by relaxing all discrete variables to be continuous.
When using the general certificate from Theorem 4.2, the binary vector t E 1) can be relaxed to E [0, 1| When using the certificate with quantized base certificate parameters from $ E.2 or E.3 the binary matrix T [0, 1| XNNim can be relaxed to T E [0, 1] 1] X.Niiee Conceptually, this means that predictions can be partially certified, i.c. tn E (0, 1) or Tú, E (0, 1). In particular, prediction be partially certified even if we know that is impossible to attack under the collective perturbation model Th = x E Dio || - ællp S {c). Just like Schuchardt et al. (2021) ), who encountered the same problem with their collective certificate, circumvent this by first computing a set IL C T of all targeted predictions that are guaranteed to always be robust under the collective perturbation model:
L
n
E
max Σ FEB
wi d=1
(n) 1o'a xxal" < <n)(n)
(26)
fn
(x) c < 17 171)) }
E
max
(27)
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. Be- cause we know that all predictions with indices in IL are robust, we do not have to include them in the collective optimization problem and instead compute
[L|
min EB
Σ nETYL
o E E
(28)
The r.h.s. optimization can be solved using the general collective certificate from Theorem 4.2 or any of the more efficient, modified certificates from previous sections.
When using the general collective certificate from Theorem 4.2 with binary data, the budget variables
b E
FO.1 Dia can be relaxed to E [0, 1] Pin, When using the modified collective certificate from E.3 the budget variables with E N can be relaxed to b RR-N.. The additional
constraint V/ E {l,..., N b < [_((0) can be kept in order to model that the adversary cannot flip (or partially flip) more bits than are present within each input subset (!))
27

---

Published as a conference paper at ICLR 2023
F BASE CERTIFICATES
In the following, we show why the base certificates discussed S and summarized in Table hold. In $ F.3.2 we further present base certificate (and corresponding collective certificate) that can distinguish between adversarial addition and deletion of bits in binary data.
F.1 GAUSSIAN SMOOTHING FOR 12 PERTURBATIONS OF CONTINUOUS DATA
Proposition E.1 Given output In
Y, let fa(x) argmaxyer PrzaN((,E) [9n(z) - y] be the corresponding smoothed output with Σ diag (o) and o E Rf Given an input E Di and smoothed prediction Yn = fn let q Piz~N(n,E) (2) yn]- Then, Val H(²) ff((z') Yn with H(m) defined as in Eq. wa o, n (q) and 2
Dro
Proof. Based on the definition of the base certificate interface, we need to show that, Va' H fa(x') Yn, with
Dm
x
E
R
Din
Σ d=
z'12 2 1
1 Ixa
(4)
(29)
Diras et al. (2022) have shown that under the same conditions as above, but with general covariance matrix Σ 4 Din prediction y/ is certifiably robust to perturbed input x' if
1 ( (g) - (g))
x - 1x=xx'2 (a x²)
(30)
where g' maxy', * diction under the smoothing distribution. Because the probabilities all possible predictions have obtain
E) [gn(2) vnl is the probability of the second most likely pre-
to sum up 1, have g' < q. Since Φ is monotonically increasing, lower bound on the r.h.s. EEq. 30 and thus a more pessimistic certificate by substituting for q' (deriving such "binary certificate" from "multiclass certificate" is common in randomized smoothing and was already discussed in (Cohen et al. 2019))
x
x
x²)
(g) Φ 1 (1-))) 9))
(31)
In our case, Σ is diagonal matrix diag )0)² with E Pim. Thus Eq. 31 is equivalent to
Din
1 r'a)
(na
o3 (at x'') < ( (q) - क -- (1-1)) 9))
(32)
0o
d=1
Finally, using the fact that + that we are certifiably robust if
(()
क --
9) 2Φ (g) and eliminating the square root shows
1
Ia
x'd ( (g))²
(33)
d=1
Table 1: Base certificates complying with interface Eq. with parameters (n(n) and 17(1). Here,
Dn = [x) is the prediction of fn (a:) = argmax In. With the lo certificate, In Bn(z), refers to the softmax score of class and C Varz~ Inn g...
9m. is the variance of yn. 's softmax score.
Norm
V (n)
gn.y
(m)
(n())
la
N' (x. diag (8)²)
(m) (2) =
( -1 (gm.wn ))*
4
U (x, A)
Pr Prawe(n) (n) Ign (z) v]
4 (gn.on)
A
lo
F F(x,00 0)
B (n) (9n(2)))
In
(1-0x)*
(0,)"
In (1 ) (gn.n 2)2))
28

---

Published as a conference paper at ICLR 2023
F.2 UNIFORM SMOOTHING FOR / PERTURBATIONS OF CONTINUOUS DATA
An alternative base certificate for 4 perturbations is again due to Biras et al. 2002)). Using uniform instead of Gaussian noise allows us to collective certify robustness to -orm- boundbound perturbations. In the following axx X) with a E RR, À E R. refers to a vector-valued random distribution in which the d-th element is uniformly distributed in [Td Ad; Fa + Aa)-
Proposition F.2. Given an output In Pi. + Y. let f(x) argmax PIz-EE((..)) [g(z) yl be the corresponding smoothed classifier with À E D Given an input E IR Ii and smoothed prediction y f()), let p ((z,)(( (g(z) y/. Then, Va' [H(()) fn(x') yn with H(m) defined as in Eq. Wa 1/ 7 = ① (q) and 1.
Proof. Based on the definition of H(),, we need to prove that Var E H: Jn(a")
yn with
Din
x' E
R Din
Σ
ad
x'dl 1 (g)
(34)
Xd
d=1
Eiras et al. (2022) have shown that under the same conditions as above, a prediction yn is certifiably robust perturbed input æ' if
D
1 (Ia n'd) < ④ (0) -0)--(-111 (1--(1-0))
(35)
Ad
where q' = Pu. Prz (z) v'nl is the probability of the second most likely predic-
tion under the smoothing distribution. As our previous proof for Gaussian smoothing, we can ob- tain more pessimistic certificate by substituting 1 1-g g for o/. Since (q) a- (119)) = 24 (g)
and Xa are non-negative, we know that our prediction is certifiably robust if
Dmn
|ed I'dl < + (p).
(36)
F.3 VARIANCE-CONSTRAIINE CERTIFICATION
In the following, we derive the general variance-constrained randomized smoothing certificate from Theorem 5. before discussing specific certificates for binary data in [ F.3.1 and S F3..2
Variance smoothing assumes that we make predictions by randomly smoothing base model's soft- max scores. That is, given base model g : X + d!yi mapping from an arbitrary discrete input space X to scores from the (l - 1-ddiensiioa probability simplex Arr we define the smoothed classifier (xx) argmax yy [=(=)y]- Here, V((x:) is an arbitrary distribution over X pa- rameterized by x. e.g a Normal distribution with mean æ. The smoothed classifier does not return the most likely prediction, but the prediction associated with the highest expected softmax score.
Given an input æ E X, smoothed prediction y =(x) and a perturbed input x' E X, we want to determine whether f(=') y. By definition of our smoothed classifier, we know that f(x') y 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.
Eg-((a)) [o(z)y) > 0.5 = f(x') =
(37)
Computing ( [g(z)y) (p) exactly is usually not tractable - especially if we later want to evaluate robustness to many x' from a whole perturbation model B C x. Therefore, we compute a lower bound on (xx) [o()),) 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 F with E IH and compute the minimum softmax score across all functions from F:
min EgwD(ar) [h(z)] > 0.5 f(x') y- hEF
(38)
29

---

Published as a conference paper at ICLR 2023
For our variance smoothing approach, we define FF to be the set of all functions that have larger or equal expected value and smaller or equal variance under V/ (z), compared to our base model g. Let μ (g~v(r) [z) be the expected softmax score of our base model g for label y. Let Ç Bz~v(a) (g(=), z be the expected squared distance of the softmax score from a scalar E R. (Choosing technical reasons related to Monte Carlo estimation | G.2). Then, we define
yields the variance of the softmax score. An arbitrary is only needed for
F h R (Z-((() [h(z)] 1 Bz) [(((z) u)² cc}
(39)
Clearly, by the definition of and Ç. we have By F. Note that we do not restrict functions from H to the domain [0. 1]. but allow arbitrary real vellev outputs.
By evaluating Eq. 37 with F defined as in Eq. 38 we can determine if our prediciton is robust. To compute the optimal value, we need the following two Lemmata:
Lemma F.3. Given discrete set % and the set II of all probability mass functions over X, any two probubility mass fanctions Ti, n2 filfill
(2(2) Σ
2 1. #EX (1
T2(2)
(40)
Proof. For a fixed probability mass function T1 Eq. 40 is lower-bounded by the minimal expected likelihood ratio that can be achieved by another (z) II:
Tz (2)2)
#(2) (2) T(2).
T2(2) REX (3)
min 2EX
(41)
The r.h.s. term can be expressed as the constrained optimization problem
7(=)
min Σ
(2)
(())
s.t.
Σ
#
(42)
ZEX
=EX
with the corresponding dual problem
#(2) (2)
max min
T(=)
-1 Σ 7(2) =EX
(43)
XER
SEX
The inner problem is convex in each #(2). Taking the gradient w.r.. to #t2)) for all & E X shows that it has its minimum at V2 E X 7(=) (=(=) Substituting into Eq. 43 results in
max Xm AER
(x)
+ -1
(44)
421(2)
2
=EX
TT (1(2)
max XER
12
(45)
2EX
2²
max
A
(46)
XER
4
-1.
(47)
Eq. 46 follows from the fact that nı (=) is a valid probability mass function. Due to duality, the optimal dual value 1 lower bound on the optimal value of our primal problem Eq. 40
Lemma E4, Given a probability distribution D over a IR and a scalar v E IR, let μ E [2] and
< = EgnD (z-v) --}² Then & 2 (μ-- - D)²
30

---

Published as a conference paper at ICLR 2023
Proof. Using the definitions of μ and as well some simple algebra, show:
= (p v)²
(48)
E END
(2 - w)²
2 1²² -pp + v²
(49)
BNND
[x² 22v + v²1 2 x² - 22 + 1²
(50)
ByDD
322 2zv v² 2 x2² 2 v2
(51)
ENDD
[2²] 2/10 + 2 2 11² 2 + U²
(52)
EnnD [20] 2 11²
(53)
is well known for the variance that DEg~D [(= - n) = EEND [x-]] - 1²2. Because the variance is
always non-negative, the above inequality hölds.
Using the previously described approach and lemmata, robustness certificate:
show the soundness of the following
Theorem 5.1 (Variance-constrained certification). a function X A mapping from
discrete set X to scores from the (J -)-dimensional probability simplex, let f(x)
vrgmaxyev y [g(=))] with smoothing distribution Vx and probability mass function (2))
Preww. [ z|. Given an input æ X and smoothed prediction y f(x), , let p IE Ww (g(2)y] and Ex-Va (9(2)) -\)
with E R. Assuming v S μ. then fxx' = y
Σ ZEX
Tel Tu
Txx (2) <1+ C (u - v)2
1
(1-2)
u 1
(54)
Proof. Following our discussion above, we know that f(x') = y if Exns(a') [g(2)y] >> 0.5 with defined as in Fq.. 39 We can compute (tight) lower bound minger E. 2 2 (we) by following the functional optimization approach for randomized smoothing proposed by Zhhang et al. (2020). That is, we solve a dual problem in which we optimize the value h(zz) for each X. By the definition of the set IF,, our optimization problem is
min (z)(((r)) [h(z]] hx
(55)
s.t. (z)((a) [h[=)] p. Ez (1(z)) w)² Sc.
(56)
The corresponding dual problem with dual variables a, 2 is
max min E (a)) [h(2)] a. a,920 h:
(57)
+a (μ-E (z) [h(=)]) + 3 (Bz~ [h(()) 1) -c).
We first move move all terms that don't 't involve h out of the inner optimization problem:
max ap - 3C + min Eg))(()) [h(=]] alEz~v()) [h(2)] + 3E.~v(a) a,820
[b(z)) - n)² (58)
AX
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 op BC + min a,300
((())mr(()) -E( ah(z)==(2)) (h(2) v)² Tx (z)
(59)
A:X
(recall that Th and म.. 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 ap BC+ + Σ 0,0
min h(2)== (z) ah(=) (z) + (h(z) v)² n. (z).
(60)
h())ER
xEX
31

---

Published as a conference paper at ICLR 2023
Because 3 O, each inner optimization problem is convex in hzz). We can thus find the optimal h" (z) by setting the derivative to zero:
d
h TT (Mt)
"² (z) -
(61)
dh(z)
Tex (2) aTT (z) + 2B (h(z) 1)) (z) =
(62)
h²' (z)
Tw (z)
a
+v.
(63)
2 (z)
2/3
Substituting into Dq. and simplifying leaves us with the dual problem
a²
1
Tw (z)
max ap - 3C a,320
(64)
43
23
43
Tar (2)
In the following, let us use p EzEx [a((=)²
==(=) as a shorthand for the expected likelihood ratio. The problem is concave in a. We can thus find the optimum a by setting the derivative to zero, which gives a* 2,3(u v) + 1. Because 3 2 0 and our theorem assumes that S fr, the value at is
a feasible solution to the dual problem. Substituting into Eq. 64] and simplifying results in
a2
a
max 3C #20
43
+
2
a v +
V-
43
(65)
max B ((1 (11- 0²) $20
p)
(66)
43
Lemma F.3 shows that the expected likelihood ratio is always greater than or equal to 1. Lemma F.4 shows that (p - w/)² x² < O. Therefore Eq. 66 is concave in 3. The optimal value of 3 can again
be found by setting the derivative to zero:
p ((1 v/2 02)-
B
(67)
Recall that our theorem assumes o² 2 (14 2)² and thus 3rr is real valued. Substituting Eq. 67 into Eq. 66) shows that the maximum of our dual problem is
p) ((p 1ou-170 1)2
(68)
By duality, this is a lower bound on our primal problem minner Ezww(r)) [h(2]]. We know that our
prediction is certifiably robust, i.e. f(x)) y. if minger ( [m(2)] > 0.5. So, in particular, our prediction robust if
# V (1 p) ((p w)² 02)
0.5
(69)
1
1
(70)
0² - (n- - v1=
(z)
1
1 2
<
11
(71)
(z)
02 02 (n u)²
2
The last equivalence is the result of inserting the definition of the expected likelihood ratio p.
Theoreme 5.1 iin 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, this can be done efficiently, as the two following base certificates for binary data demonstrate.
F.3.1 BERNOULLI SMOOTHING FOR PERTURBATIONS OF BINARY DATA
We begin by proving the base certificate presented in S 5 Recall that
smoothing distribution F(x, 0) with 0 E [0, 1m that independently flips the d'th bit with probability A,, f.e. for xc, E (0, 1) D.n and F(x, 0) we have Pr(za * 2:2 Oa-
32

---

Published as a conference paper at ICLR 2023
Corollary E.5. Given output 9n. 10.1) + Am mapping to scores from the ((') 1)-
dimensional probability simplex, let [n( argmax 2 [gn(z)y) be the corresponding
smoothed classifier with 0 E [0,1]Dm Given an inpul æ E [0,1) and smoothed prediction
Yn [n(x), let μ F(g=F(a.0) I (2)y and ( Varz==((a,0)) (gn(2) Then, Var' [HH(())
fa(xx) yn with H()) defined as Eq. wi In (1-8a)² 2 (0x)² and p = O.
84 0a in (1 (1+ (
Proof. Based on our definition of the base certificates interface (see Definition 4.1 that Va E IH:: fn(x')
we must show
= Un with
Din
0a)² (1)
(1
(0a)²
1
H o' E 10 Pm
In
+
-1 xall < in [1 s
0.
1- 04
2
d=1
(72)
Because all bits are flipped independently, our probability mass function (x) Pre factorizes:
[
Din
Te (z) =
II d=1
Tza (za)
(73)
with
(d
if F Ftd else
Txa (za)
(74)
(1
Oa
Thus, our expected likelihood ratio can be written as
Tax (z)²
Σ
T
II
Σ
Tea (za)²
(75)
Ta (2)
Tze (zd)
Tz (zz)
(0.1)
(E d=1
(0.1)
For each dimension d, we can distinguish two cases: both the perturbed and unperturbed input are the same in dimension d, i.e. x'a = Fd, then Tx (2)
(z) = and thus
TZy (za)2
Σ
Tz (x)( 0₂ + (1 02) = 1.
(76)
(2a)
(0.1)
If the perturbed and unperturbed input differ in dimension d, then
Tal (2a)2
(1 (1-0a) 0x)²
(0a)²
(77)
(2a)
0a 1- Os
(0.1)
Therefore, the expected likelihood ratio is
1
Din II
Tat (za)2
Din
(1 0a)
(0a)
II
(78)
Tue (2d)
0g
1
0s
(0,1)
Due to Theorem 5.1 (and using v = i when computing the variance), we know that our prediction
is robust, I.c. (xx = Un. if
Σ
Te (z)²
1 +
1
(79)
Ta (2)
2
ZE (0.1) Pmn
Di
0z)
(0a)
1 1/6
1 2
1
11---
-
(80)
0g
1 0s
2
dml
Din
(1 (1-08)) 0a)2
(0a)
(
1 2)
In
1o xzl < In
(1+]
11 2
(81)
0₂
1-
0₂
Because Fa and 2', are binary, the last inequality is equivalent to
Dm
(1
0a)
(0z)²
(1+
1 1 | 2 )
1) 2)
In
+ 1 0g
Ja'a xal < In
(82)
0.
33

---

Published as a conference paper at ICLR 2023
F.3.2 SPARSITY-AWARE SMOOTHING FOR PERTURBATIONS OF BINARY DATA
Sparsity-awand aware randomized smoothing (Bojchevski et al. 2020) is an alternative smoothing ap- proach for binary data. It uses different probabilities for randomly deleting (1 - 0) and adding (0 + 1) bits to preserve data sparsity. For a random variable z distributed according to the sparsity-aware distribution S(æ, 0+, 0-) with æ {0, 1J Pin and addition and deletion probabil-
ities E [0, Im, we have:
Pr(za = 0] = (1 0ī) 1-ma (07 )0 Pr[za = (0 1-ea (1-02) an
The Bernoulli smoothing distribution we discussed in the previous section is special case of sparsity-aware smoothing with 0+ 0- The runtime of the robustness certificate derived by Bojchevski et al. (2020) increases exponentially with the number of unique values # and A which makes unsuitable for localized smoothing. Variance-constrainee smoothing, on the other hand, allows us to efficiently compute a certificate in closed form.
Corollary F6. Given an oulpul 9n Din + Api mapping to scores from the (1 - 1)- dimensional probability simplex, let fx(x) = y
[9n (z)gl be the corre- sponding smoothed classifier with 0t, 0 E 10 Given an input E {0, PiP and smoothed prediction yn fn(x),, let p E Ez- 0-) 1 (z) and Ç Varz=S(m.00 R-) (z Then, Vx' Hi: fn yn for
Dmn
H x' E 1
d
I = 0 +
x'al + +ra [ = 1 + x'y <n].
(83)
d=1
(0y)
(1-0z)² 0
7i = In (1-01)²
0, + (0))²
where - E Pin, 7d
and =
1-0
1-0
(1+ (1- 1 22)
Proof. Just like with the Bernoulli distribution we discussed in the previous section, all bits are flipped independently, meaning our probability mass function (z)))) = Prew((a) [ = 2] factor- izes:
Din II
T (2)
Tza (zJ) d=1
(84)
with
(
if za + Fdd
Tzy (za)
(85)
0a
else
As before, our expected likelihood ratio can be written
Tax (z)²
Dmn
(2d)2
Din
Tay (2d)2
Σ
II
(86)
Ta zE(0,1) Pmn d=1 (2d)
Tz, (2d)
ZE (0.1) Pm
d=1
(0,1)
We can now distinguish three cases. If both the perturbed and unperturbed input are the same in dimension d, i.c. x'1 Dd. then
x,t (=)
1 and thus
[xy(E]
Tay (za)
Σ
Teg(Ea) 1.
(87)
Tae (zd)
(0,10
(0,
If 4/4 = and xd O, i.c.aaa a bit was added, then
Tzy(2)2
Ti (za)²
T. (0)
(1
(0
(1 - 0
(88)
Tze (2)
To(2a)
(0)
8
0
(0.1)
34

---

Published as a conference paper at ICLR 2023
If 2/2 = 0 and zd 1, i... bit was deleted, then
Tzt (2)2
Ta(zd)? =o(0)²
+ mo(1)² (1 11-6% )²
(07)²
+
(89)
(z)
#oE(0.1) (1(2)) TT T1 0
0
(0E()
Therefore, the expected likelihood ratio is
Din
Tal (za)²
(90)
Tud Taa (za)
d=1
[0,11
2 (07)
(1 (1-07)²
1/2=0
(1 (1--2)²
(07)
2
|
(91)
0g
07
0g
0g
d=1
Din
exp (7t)
fo (ou
exp (7ā) (foum
(92)
In the last equation, we have simply used the shorthands 7 and 7/ defined Corollary F.6 Due to Theorem 5.1 (and using
when computing the variance), we know that our prediction is
robust, i.c. fn('') = yn. if
1 (1 10 2
-1-2) 1
Σ
< 1 + 5
(93)
(z)
(0,1)) Pm
Din
(1d (1tt ([0=0000
exp (vz) Her=
{ | )
1
exp
<1+ +
(94)
d=1
Din
/
1 2 2
Yd I [ 0 a'd 72 I[r 1 a'll
< In
1 [
(95)
Use for collective certification. It should be noted that this certificate does not comply with our interface for base certificates (see Definition 4.1), meaning we can not directly use to certify robustness
norm-bound perturbations using our collective linear program from The- forem 4.2] 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 B
No specifying the number of bits the adversary is allowed to add or delete. We can now follow the procedure outlined in $ 3.2 to combine the per- prepicddittonn base certificates into collective cer- tificate 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 certifiably robust according to their base certificates:
{a'' E 1 Eb= [ra- - 0 + x'yll Set Ed=1
Din [rra = 1 + s'yll S < with et,
min xE' EB
E1(f(('') = ynl
min EB
Ei T m
(96)
BET
Inserting the linear inequalities characterizing our perturbation model and base certificates results in:
Dmn Σ
min #' e'E(0.1)
Σ
II I[r = 0 n'd + 7/
I[xa # x'dl < mp(m)
(97)
Pin
nET
Ld=1
s.t.
[aa 0 4 x'dll S
Σ
Fa 1 + 2'21 5
(98)
d=1
d=1
35

---

Published as a conference paper at ICLR 2023
Instead of optimizing over the perturbed input z', can define two vectors bt, b- E {0. 1 Pin that indicate in which dimension bits were added or deleted. Using these new variables, Eq. 97 can be rewritten as
Σ Σi((
T+ bt + (x-)² b < mn
min by b E(0.1) Pu
(99)
nET
s.t. sum S <et,
sum b sc,
(100)
b 0,
Σ d=a==
by = 0.
(101)
d
The last two constraints ensure that bits only be deleted where Id and bits only be added
where vi = O. Finally, we can use the procedure for replacing the indicator functions with indicator
variables that we discussed in D restate the above problem the mixed-integer problem
min b+ b+,,-E(0,1) BE (0,1)
Σ Im
(102)
RET
s.t. (7**) b+ + (7-)) b 2 (1 - (n))(())
(103)
cb+] set, sum b b0) cc
(104)
=0
Σ by =.
(105)
d=
d
The first constraint ensures that in can only be set to 0 if the l.h.s. is greater or equal Yh i.e. only when the base certificate can longer guarantee robustness. The efficiency of the certificate can be improved by applying any of the techniques discussed in S E
F.3.3 GAUSSIAN SMOOTHING FOR PERTURBATIONS OF CONTINUOUS DATA
Even though we specifically proposed variance-constrainge certification as means of efficiently certifying anisotropically smoothed classifiers for discrete data, it can be generalized to continuous distributions by replacing sums with integrals and mass functions with density functions (the proof is analogous that Anpppeddix F.3)
In the following, we assume Gaussian smoothing, i.e. (ax) ~ N(x Σ) with E E RDDDD with density function Tr. In this case, the expected ratio between Tw' and Tz is the exponential of the squared Mahalanobis distance (see Table 2 of (Gil et al. 2013) with 2), i.c.
I Tix (2) JRD (2)
(2) dz = exp ((x' x)) E 'x'' x²)
This leads us to the following corollary of Theorem 5.1
Corollary F.7 Given a function h IR A A mapping to scores froresfrom the (1 - 1)-dimensional probability simplex, let f(x) = argmax, yey Bz [h(2)g] with covariance matrix E E RRDDD Given an input x X and smoothed prediction = f(x), let μ Ez~N(mx)) [h(z),] and C = (h(z), EznN(a,))
v)² with E RR Assuming S μs then sxx' -ybl yf
(x' +)= 'x'' x)) < In 1 <- (u u)²
(1+
1
1
1 2
(106)
As with Theorem 5.1. The r.h.s. of Eq. 106 depends the expected softmax score μ, variable S y and the expected squared difference C between j and и. For v μ the parameter Ç is the variance of the softmax score. A higher expected value and a lower variance allow us to certify robustness for larger adversarial perturbations.
For comparison, ANCER (Eiras al. 2022 guarantees robustness for the smoothed prediction yn = argmax,ex Pr [g(x)) y if
(xd'
x)
(x' xx) x =-
(107)
36

---

where Py. is the probability of predicting class Yns i... 9y.. Prz ((n,)) [9(2) Unl- Here, g: IR. W directly outputs class lahel instead of softmax score. We see that both the variance- constrained certificate and ANCER yield the same certified ellipsoid, scaled by different factor. We also that both Published as a conference paper at ICLR 2023
This factor is the certifiable radius v), i.c. the r.h.s. term Eq. and certificates have the same computational complexity they both involve calculation of the squared Mahalanobis distance and constant number of operations for evaluation of the certifiable radius.
In the following, we briefly assess under which conditions which certificate yields a larger certifiable radius 7). For this evaluation, we assume that g(æ) argmax, ((x)) i.e. 9 predicts the class with the highest softmax score. We then vary the prediction probability Qy., and the expected softmax score u within [0.5, 1.0]. For each μu, we calculate the largest possible variance (using the Bhatia-Davis inequality Ç < (1 μ4) μ)), which will give the weakest possible variance-consttrained certificate
(see Eq. (106)p.
Fig. shows the difference in certifiable radius n, with the dashed line indicating parameters for which both certificates are identical. We have omitted all combinations of qy. and that are not possible, namely > 9y. + [1 9p.). We see that ANCER is stronger when Qv. is large, i.. almost all samples from the smoothing distribution are correctly classified, but not necessarily with high confidence. The pariance-constraie
certificate is stronger when qy. is smaller and is larger, misclassified but the correctly classified ones have high confidence. Note
Le. some samples however, that this is the worst case for the variance-constrained certificate. For C + O, much larger radii can be certified (see Fig. 14 and Eq. (106)..
0.25
Que
0.125
-3
0
0.5
0.75
0.50
0.75
Figure 13: Worst-case difference in certifi- able radius 7) between ANCER (Eiras et al.) 2022) and the variance--oonstrained certificate for anisotropic Gaussian smoothing. The dashed line indicates combinations of prediction probability Gy, and expected softmax score for which both certificates are equally strong.
Figure 14: Certifiable radius n of the variance- constrained randomized smoothing certificate for anisotropic Gaussian smoothing the expected value and the variance of the softmax score. the variance is small, large radii can be certified even if the expected softmax score small.
function of
37

---

Published as a conference paper at ICLR 2023
G MONTE CARLO RANDOMIZED SMOOTHING
To make predictions and certify robustness, randomized smoothing requires computing certain prop- erties of the distribution of a base model's output, given an input smoothing distribution. For example, the certificate of Cohen et al. (2019) assumes that the smoothed model f predicts the most likely label output by base model 9. given a smoothing distribution (N0, σ 1): f(x) = argmaxyer Prz-N(0,r-1) [g(x + 2) yl. To certify the robustness of a smoothed prediction y fa)) for specific input we have to compute the probability q PIz-N((0,-11) [g(x + z) yl to then calculate the maximum certifiable radius o with standard-normal inverse CDF d-1 For complicated models like deep neural networks, computing such properties in closed form is usually not tractable. Instead, they have be estimated using Monte Carlo sampling. The result predictions and certificates that only hold with a certain probability.
Randomized smoothing with Monte Carlo sampling usually consists of three distinct steps:
1. First, small number of samples N1 from the smoothing distribution are used generate a candidate prediction ÿ. e.g. the most frequently predicted class.
2. Then, second round of N2 samples is taken and statistical test is used to determine whether the candidate prediction is likely to be the actual prediction of smoothed classifier f(x) with certain probability (1 a1). If this is not the case, one has to abstain from making a prediction (or generate a new candidate prediction).
f. i.e whether
3. To certify the robustness of prediction ý. final round of N3 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 PI [g( + =) y to compute the certificate oΦ- (2), whose strength is monotonically increasing in q. To ensure that the certificate holds with high probability (1 - a2). we have to com- pute probabilistic lower bound q S q. Instead of performing two separate round of sampling, one can also re-use the same samples for the abstention test and certification. One particularly simple abstention mechanism is to just compute the Monte Carlo randomized smoothing certificate to de- termine whether Vx E {x> : f(x') = ÿ with high probability, i.e. whether the prediction is robust to input x' that is the result of "perturbing" clean input æ with zero adversarial budget.
In the following, we discuss how we perform Monte Carlo randomized smoothing for our base certificates, as well as the baselines we use for our experimental evaluation. In [S G.4] we discuss how we account for the multiple comparisons problem, i.c. the fact that we are not just trying to probabilistically certify a single prediction, but multiple predictions at once.
G.1 MONTE CARLO BASE CERTIFICATES FOR CONTINUOUS DATA
For our base certificates for continuous data, we follow the approach we already discussed in the previous paragraphs (recall that the certificate of Cohen et al. (2019) is a special case of our cer- tificate with Gaussian noise for la perturbations). We are given an input space X Pin, label space Y. base model (or in the case of multi-output classifiers base model output) D - Y and smoothing distribution (xx) (either multivariate Gaussian multivariate uniform). To gen- erate a candidate prediction, we apply the base classifier to N₁ samples from the smoothing distribution in order to obtain predictions (y.,)..., (()))) and compute the majority prediction ý argmaxyey {n (()) = ú}. Recall that for Gaussian and uniform noise, our certificate guar- antees Va' E [H: f(æ)= = ÿ for
D
}
H
x'' Pmu
Σ
xal < <" ) wa Ir's
(g) (depending on the distribution), q PTz~N((0.r11 11) Ig(x x) ز) and standard-normal inverse CDF -- To obtain a probabilistic cer- tificate that holds with high probability 1 - a, we need a probabilistic lower bound on 77. Both 7 are monotonically increasing in q, i.e. we can bound them by finding lower bound g on g. For this,
with 77 ( (a)) 2
7
38

---

Published as a conference paper at ICLR 2023
take N2 more samples from the smoothing distribution and compute Clopper- Peers-n lower
fidence bound (Clopper& & Pearson 1934) on For abstentions, we use the aforementioned simple
mechanism: We test whether H. Given the definition of HI, this is equivalent testing whether
< (g)
(0) q
0.5 < q.
If q S 0.5, we abstain.
G.2 MONTE CARLO CARIANCE-CONSTERE
CERTIFICATION
For variance-constrainee certification, we smooth a model's 's softmax scores. That is, we are given an input space X label space W, base model (or in the case of multi-output classifiers base model output) X b Á with (J - 1) --ddiensiiona probability simplex A and smoothing distribution (x) (Bernoullli or sparsity-
noise, in the case of binary data). To generate a apply the base classifier N1 samples from the smoothing distribution
candidate prediction, in order to obtain vectors (s(1),.. ..... s(Mi)) with E A compute the average softmax scores N; Σm=1 s and select the label with the highest score ò = arg max, Sy.
Recall that our certificate guarantees robustness if the optimal value the following optimization problem is greater than 0.5:
min Bz-((m)) [h(z)] AXx
(108)
s.t. (x) [h(=)] M4 Eg)((1)) (h(z) -v) sc
(109)
(0(2)) - w) and a fixed scalar v E 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 minimization problem, this can be achieved by loosening its constraints, i.c. computing a probabilistic lower bound on and a probabilistic upper bound on
with y = Ex- [0(2)g). C Ex)(()))
Like in CDF-smoothing (Kumar et al. 2020). we bound the parameters using DDF-based non- parametric confidence intervals. Let F(s) Prz-v(m) [g(2) I s) be the CDF of g (Z) with
7 (ar). Define M thresholds
O71 . TM-1 S TM S with Vm. Tm [0. 1]-
We then take N2 samples (1),, ..... (N2) from the smoothing distribution compute the empirical CDF F(s) >N>; (g((())g S s]. We can then use the Dvoretzky-Kenn -eeffrr Wolfowitz inequality Dvoretzky et al. 1956) to compute an upper bound F and lower bound F on the CDF of 9g:
F(s) max (F(s) v.0) < F(s) I min (F(s) + v, F(s),
(110)
2/2/a with V = V N: which holds with high probability (1 (1)... a.. Using these bounds on the CDF, we can bound / [()) [o(=);] as follows (Anderson 1969h:
# TM F(T + (mm+1 Tm F(Fm).
(111)
[0(x)) - -1)² can be bounded a similar fashion. The parameter Ç = Ez)((())
Define
Eo,...,&m R4 with:
Eo max ((x)))))
xE(U,T]]
EM max
((15 - ((1-- (15)))2)
(112)
xE[T>r]]
Sm = max
((1s - (()=))
Vm (1...., M-1 1),
+1]
39

---

Published as a conference paper at ICLR 2023
Le. compute the maximum squared distance to y within each bin [Tm Tm+1] Then:
M
Ç ((F(T) + tMM (1 F(TM)))
+
Sm (F(Tm+11 F(Tm))
(113)
m=
M-
= MM
Σ
(5m-1 Em) FTmm)
(114)
M-1
2 EM +
Σ
(5m-1 - Sm) (sgn (5m-1 - Em) F( + +11 sgn (Em-1 5mm) F( (115)
m=1
with probability (1-a). a). the first inequality, we bound the expected squared distance from by assuming that the probability mass in each bin [Tm, Tm+11 is concentrated at the farthest point from v. The equality is result of reordering the telescope sum. In the second inequality, we upper-bound the CDF where it is multiplied with non-negative value and lower-bound it where it is multiplied with a negative value.
With the probabilistic bounds y and we can now in principle evaluate our robustness certificate, i.e. check whether
Tax (2)²
(2) <1
h- (- 4 2
(116)
#EX
where the the probability mass functions of smoothing distributions ((x)) and (ax).. But one crucial detail of Theorem 5.1 underllying the certificate was that it only holds for v S μ. To use the method with Monte Carlo sampling, one has ensure that v S p by first computing y and then choosing some smaller v.
In our experiments, we use an alternative method that allows us to use arbitrary v: From our proof of hhorrm 5. know that the dual problem of Eq. 108 is
2
Tax (z)2
max ap 3C a,320
au 0v +
(117)
43
23
43
ZEX
Instead of trying to find an optimal (which causes problems in subsequent derivations if v I p)) we can simply choose a = 1. By duality, the result is still lower bound on the primal problem, i.e. the certificate remains valid. The dual problem becomes
Tz (z)
- B20
(118)
48
43
Te (z)
ZEX
The problem is concave in 3 (because the expected likelihood ratio is 2 1). Finding the optimal 3, comparing the result to 0.5 and solving for the expected likelihood ratio, shows that prediction is robust if
Ter (z)
(119)
ZEX
For our abstention mechanism, like in the previous section, we compute the certificate H and then test whether æ E H. In the case of Bernoulli smoothing and sparsity-aware smoothing), this corre- sponds to testing whether
1 (--))
1 << In
1 5
(120)
1
p
(121)
G.3 MONTE CARLO CENTER SMOOTHING
While we can not use center smoothing base certificate, we benchmark our method against it during our experimental evaluation. The generation of candidate predictions, the abstention mech- anism and the certificate are explained in (Kumar & Goldstein 2021). The authors allow multiple options for generating candidate predictions. We use the "B minimum enclosing ball" with 3 that is based pair-wise distance calculations.
40

---

Published as a conference paper at ICLR 2023
G.4 MULTIPLE COMPARISONS PROBLEM
The first step of our collective certificate is to compute one base certificate for each of the Dout predictions of the multi-output classifier. With Monte Carlo randomized smoothing, we want all of these probabilistic certificates to simultaneously hold with a high probability (1 o). But as the number of certificates increases, so does the probability of least one of them being invalid. To account for this multiple comparisons problem, we use Bonferroni (Bonterroni 1936 correction, i.e. compute each Monte Carlo certificate such that it holds with probability (1 ))
For base certificates that only depend on In Prz=ein) [=) = Un., i.e. the probability of the base classifier predicting a particular label yn 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 Pl....,
.......PPN. PN- Starting at i 1, the i'th hypothesis is rejected if p; N41-;' until one reaches such that p. 2 N+1-1'
Fischer et al. )021) 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 perturba- tions. 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.c. certifying the number of robust predictions. As in & G.I. the goal is to obtain lower bound 2, on Qn. Przww(()) [9m(2) 5n] for each of the Don classifier outputs. Assume we take N2 samples (1) ,..., ,...,,((, (..,)((N)) (Na) from the smoothing distribution. Let V, = Σ (z(()) = dn.] and let (1...., Dout + bijection that orders the 2 descending order, i.e. Vz(1) 2 (x(2)) ... Vz (D(uuu)) Instead of using Clopper-Pearson confidence intervals to obtain tight lower bounds the yo. Pischer al. (2021) define a threshold 7 [0.5, 1) and use Binomial tests to determine for which n the bound S qu holds with sigh-rrobability. Let BinP (Vn, N2, r) be the p-value of the one-sided binomial test, which is monotonically decreasing in Pn. Following the Holm correction scheme, the authors test whether
Dout } be
BinP (MR(R): N2, S.T)
(122)
Dout -1-k
for I = -...., Dout until reaching a K- for which the null-hypothesis can no longer be rejected, Le. the p-value is g.e.q- Do They then know that with probability 1 a, the bound 5 S qn holds for all {T(k) k {l...., k*}; For these outputs, they use the lower bound 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 different threshold Tn per output Ia. i.e. test whether
BinP (UZ(K)) N2, S, Tx(K)) < Dont + k
a
(123)
for k I..... Dout. In particular, we can use
Ta sup s.t. BinP (vn, N2, Dout + +1 x (n))
(124)
i.e. choose the largest threshold such that the null hypothesis can still be rejected. Eq. 124 is the lower Clopper-Pearson confidence bound with significance Dem+1-7--(m) This means that, instead of performing hypothesis tests, we can obtain probabilistic lower bounds 2, S On by computing Clopper-Peanee Pearssn confidence bounds with significance parameters Dont .........
a 4 The g, can then be
used to compute the base certificates. Due to the definition of the Ta, all of the null hypotheses are rejected, i.e. obtain valid probabilistic lower bounds on all gn- We thus use the abstention mechanism from S G.I. iee. only abstain if g,, $ 0.5.
41

---

Published as a conference paper at ICLR 2023
H COMPARISON TO THE COLLECTIVE CERTIFICATE OF FISCHER ET AL. (2021)
Our collective certificate based localized smoothing is designed to bound the number of simul- taneously robust predictions. Fischer et al. (2021) designed SegCertify to determine whether all predictions are simultancously robust. As discussed in 3.2] their work based on the naive collec- tive certification approach applied to isotropic Gaussian smoothing: They first certify each output independently. then count the number of certifiably robust predictions for a specific adversarial bud- get and then test whether the number of certifiably robust predictions equals the overall number of predictions. To obtain better guarantees practical scenarios, they further propose to
use Holm correction address the multiple comparisons problem (see G.4).
Abstain higher rate to avoid "bad componets", i.e. predictions 1/, that have low consistency In = Prz~N(a,o) [g(2) = y] and thus very small certifiable radii.
more technical summary of their method can be found in S G.4
In the following, we discuss why our certificate can always offer guarantees that are at least as strong as SegCertify, both for our notion of collective robustness (number of robust predictions) and their notion of collective robustness (robustness of all predictions). In short, isotropic smooth- ing is a special case of localized smoothing and Holm correction can also be used for our base certificates. Before proceedings, please read the discussion Monte Carlo base certificates and Clopper-Pearsee confidence intervals in & G. and the multiple comparisons problem in S G.4
A direct consequence of the results in S G.4 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 Poopper-Pearson--- basdd method only abstains if one cannot guarantee that On >> 0.5 with high probability, while their method abstains if one cannot guarantee that 4. predictions, the Clopper-Pearson -aased certificate will be at least as strong as the one obtained using single threshold T, as computes the tightest bound for which the null hypothesis can still be rejected (see Eq. 124
with r 2 0.5 (or specific other predictions abstain). For all non-abstaining
Consequently, when certifying notion of collective robustness, i.e. determining the number of robust predictions given adversarial budget e, a naive collective robustness certificate (i.e. count- ing the number of predictions whose robustness are guaranteed by the base certificates) based on Slopper-Pearson bounds will also be stronger than the method of Fischer et al. 2021). It should however be noted that their method could potentially be used with other methods of family-wise enror rate correction, although they state that "these methods do not scale to realistic segmentation problems" and do not discuss any further details.
Conversely, when certifying their notion of collective robustness, i.e. determining whether all non- abstaining predictions are robust given adversarial budget e, the certificate based on Clopper-Pearsee confidence bounds is also at least strong as that of Fischer al. 2021) To certify their notion of robustness, they iterate over all predictions and determine whether all non-abstaining predictions certifiably robust, given Naturally, as the Coopper-Pearson-arre any prediction that is robust according to (Fischer et al.] 2021) is also robust acccording to the Clopper-Penn Coopper-Pearson-aeee 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 9,, S instead of gn < 0.5 as our criterion.
certificates are stronger,
Finally, it should be noted that our proposed collective certificate based on linear programming is at least strong as the naïve collective certificate (see [Bq. 1.1 1.1] and [Eq. 1.2 in 3.2). 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 will also result in certificate that least
as strong as that of Fischer et al. (202T) in their setting.
42

---

Published as a conference paper at ICLR 2023
1 COMPARISON TO THE COLLECTIVE CERTIFICATE OF SCHUCHARDT ET AL. (2021)
In the following, we first present the collective certificate for binary graph-structured data proposed We then show that, when using sparsity-aware smoothing distributions (Bojchevski et al. 2020) the family of smoothing distributions used both in our work
by Schuchardt et al. (2021) (see $ I.1
and that Schuchardd 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 1.2
1.1 THE COLLECTIVE CERTIFICATE
Their certificate assumes the input space to be G {0, W x {0, 1]NNN -the set of undirected attributed graphs with N nodes and D attributes per node. The model is assumed to be a multi- output classifier f G YN that assigns label from label set Y 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 of perturbed graphs S G. The perturbation model B is characterized by four scalar parameters x: "x."xx rAA A No. specifying the number of bits the adversary is allowed to 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. formal definition of the perturbation model can found in Section B of (Schuchardt et al. 2021).
add + 1) and delete +
in the attribute and adjacency matrix, respectively.
The goal of their work is to certify collective robustness for a set of targeted nodes T S (1....,,M N), i.c. compute lower bound on
min IIff.(G') =3n]- RET
(125)
Their approach to obtaining this lower-bound shares the same high-level idea ours (see 3.2 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- ii.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 fa 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 sp(n)) and an indicator matrix (a) that fulfill
N
ΣΣ m 1=1
H Innl [Xm.d X
+
( [ Am, # Ar,l =0
(126)
fa fn. (X' (X', A').
for any perturbed graph g' (X', Eq. 126 22ceexseees that the prediction of output fn remains
unchanged if all inputs in its receptive field remain unchanged. Conversely, it expresses that per- turbations outside the receptive field can be ignored. Unlike in our work, [Schuchardt et al. (2021)
describe their base certificates sets in adversarial budget space. That is, some certification proce- dure is applied to each output fn to obtain a set
(n)
C
[x)]
(127)
K (x)) then prediction yn robust any perturbed input with exactly ox attribute additions, ex attribute deletions, c edge additions and c 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 by combining them using the receptive field indicators from Eq. 126 one obtain a collective certificate that is better than the naive collective certificate (i.e. counting how many predictions certifiably robust the collective threat model). The resulting collective certificate
with [k] = ko. If (et CX AAl
43

---

Published as a conference paper at ICLR 2023
is
min b+ b
Σ
bx
(ubin))* bx
Ens W Bis
Eis V. (m)
Brs
E K(N)
nET
(128)
N ΣΣ
S.t.
bm
X
Σ bm S x
ΣΣ B S
B S T
(129)
b b E No B*,B" E N
(130)
The variables defined in Eq.. 130 model how the adversary allocates their adversarial budget, i.e. how many attributes are perturbed per node and which edges are modified. [Eq. 129 ensures that this allocation in compliant with the collective threat model. Finally, in Eq. 128 the indicator vector and
matrix {6(*) 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 al. (202I) 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 budgets K(*) from its complement ((() in adversarial budget space (the "Pareto front" discussed in Section of (Schuchardt et al. 2021
From the above explanation, the main drawbacks of this collective certificate compared to our lo- calized randomized smoothing approach and corresponding collective certificate should be clear. Firstly, if the classifier f is not strictly local, i.e. the receptive field indicators sp and V only have non-zero entries, then all base certificates are evaluated using the entire collective adversarial bud- get. It thus degenerates to the naive collective certificate. Secondly, even if the model is strictly local, each of the outputs may assign varying levels of importance to different parts of its receptive field. Their method 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.
1.2 PROOF OF SUBSUMPTION
In the following, we show that any robustness certificate obtained by using the collective certificate 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 the receptive field is equivalent to masking out any pertur- bations outside the receptive field.
First, we derive the certificate of Schuchardt et al. 2021 for predictions obtained via sparsity- aware smoothing. [Schuchardt et al. (2021) require base certificates that guarantee robustness when
Iat cx et ca] E K(a), where the c indicate the number of added and deleted attribute and adjacency bits. That is, the certificates must only depend the number of perturbations, not 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 PA E [0, 1]. Given attribute matrix X E {0, ND they then sample
random attribute matrices Zx that are distributed according to sparsity-aware smoothing distribu- tion S [X,1 p 1. px)
(see S F.3.2 i.e.
Pr[(Zx] m.d = 0] = (1- 1 px) 1-Xmmm (px) XXma Pr[ [ m.d
m = = (px) (xx) 1-Xmd (1 - px) Xm..
Given input adjacency matrix A, random adjacency matrices Za are sampled from the distribution (A,1 1- PAA PAA) Applying Corollary F.6 (to the flattened and concatenated attribute and ad- jacency matrices) shows that smoothed prediction yn fn(X,, A) is robust to the perturbed graph
44

---

Published as a conference paper at ICLR 2023
(X', ,') if
D
I [[ = + Xmma] +7x I [[Xm,t = 1 + X
7
m=
d=1
N
(131)
A 1 [[ii = ANJ. +27 + =1 Av,1]
< <1)(0)
(px) 2
(1-px)*
X = In (L-Px) )a
(xx)
with
** = In
+
+ 1-PX
A
1-Px
PX
PX
In
(Pa)² 1-p
+ (1-PA)²) P
VA = In (1-PA)
+
(px)²
and ry = In (1 (1+ o(n)2 (u(m)
2 2
PA
1-PÄ
where (a()) is the mcan and (²)) is the variance of the base classifier's 's output distribution, given the input smoothing distribution. Since the indicator functions for each perturbation type in Eq. 131 share the same weights. Eq. c3n be rewritten as
X + + + + AACA (m)
(132)
where cx, Cx. ct. CA are the overall number of added and deleted attribute and adjacency bits, re-
spectively. Eq. 132 matches the notion of base certificates defined by |Schuchardt et al. (2021). i.e.
corresponds to set ((a) in adversarial budget space for which provably know that prediction Vn.
is certifiably robust if
cx
T A A E K(n). When we insert the base certificate Eq. 132
into objective function
Eq. 128 the collective certificate of Schuccardd et al. (2211 becomes equiv-
alent to
7x (1stri)² T bx + 7xx (15()0)² T bx
Σ
min b+ B+
B
NET
+y Σ
1.
+
Σ YA
!
(1) Big S m7)m0)
(133)
i
1.
N n
N
N
s.t.
Σ m=1
bt S
bm TX
Σ
Σ
BBs
STA
(134)
m=1
1=1 1=
b+, EN B BT
(135)
Next, we show that obtaining base certificates through localized randomized smoothing with ap- propriately chosen parameters and using these base certificates within proposed collective cer- tificate (see Theorem 4.2) will result in the same optimization problem. Instead of using the same smoothing distribution for all outputs, we different distribution parameters for each one, For the
'tth output, we sample random attributes matrices from distribution S
X
+ (m)
O (n) with
O x x (n)
[0, 1j Note that, in order to avoid having to index flattened vectors, we over- load the definition of sparsity-aware smoothing to allow for matrix-valued parameters. For example,
(m)
the value θ X indicates the probability of flipping the value of input attribute Xn,d from
(r))
(n)
and the value 0x indicates the probability of flipping the value of input attribute Xn,d from 1 to
O. We choose the following values for these parameters:
+ m.d
(n)
(n)
Px
(n)
0.5,
(136)
+ (n) (()) Px (m)
1
-0..
(137)
m.d
where 25(m) is the receptive field indicator vector defined in Eq. 126 and p pk. px E [0, are
the same flip probabilities used for the certificate of Schuchardt et al. (2021). Due to this
parameterization, attribute bits inside the receptive field are randomized using the same distribu- tion as in the certificate of [Schuchardt et al. (202T). while attribute bits outside
either
45

---

Published as a conference paper at ICLR 2023
0 with equal probability. Similarly, sample random adjacency matrices from distribution [0, 1j and
S [, O (n) 0 (m)) with
(m)
O (n)
A
Aij = w b. P + (1 (1(()
(n)
1. 0.5,
(138)
θ (n)
Au. = ((() 1. PA + (1 (1()) 0.5,
(139)
1.j
where (p(()) is the receptive field indicator matrix defined in Eg. 126, Note that, since we only alter
the distribution of bits outside the receptive field, the smoothed prediction yn = (n A) will be the same as the one obtained via the smoothing distribution used by (Schuchardt et al. (2021).
Applying Corollary F.6 (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
D
Σ
X m [[Xm,d = + Xmma] + +Tx [[ = 1 + Xmmd
m=
d=1
N
(140)
Asss [Air =0 Ab, +TAiS 1 [ 1 11
(T)
Because we only changed the distribution outside the receptive field, the scalar ry("), which depends on the output distribution's mean and variance μ and a will the same as the one obtained via the smoothing scheme used by |Schuchardt et al. (202 1 et al. Due to toroolllyyy F6land the definition of our smoothing distribution parameters in Eqs. (136) to (139). the scalars dx 'x TAis' TAi.j have the following values:
X m,d" = vilrn) 7 + (1 (1- v/((a)
(1 0.5)
0.5²
2- In
(141)
0.5
1- 0.5
(1 0.5)
0.5²
X m,d
7xx +
vo((a)
2 2-10 In
0.5
1- 0.5
(142)
(1 0.5)
0.5
TAi = 1/10) ? (1 (1- v (10)
2n
(143)
0.5
1- 0.5
TAi,j 1/ A + (1 vp (n)
(1 - 0.5)
0.5²
2 In
+
(144)
0.5
1 0.5
where the 7 are the same weights as those of the base certificate Iq.. 131 of Schuccarddt et al.
2021). Inserting the above values of 7 into the base certificate Fq.. 140 and using the fact that
(1-0.5)²
-
0.52
In(1) = results in
0.6
Σ
Σ
(1)) 7x I [[Xm, = 0 + Xmna] + tpffm)
7x I I[Xm,d = 1 X'mal
1=1
N N
(145)
- A = - Ah,
w (n) i.j 7A -
= 11 Ah.ll
.A
While our collective certificate derived in 4 only considers one perturbation type, we have al- ready discussed how to certify robustness to perturbation models with multiple perturbation types in S F..22 We use 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 dis- cussed in E.3 i.e. use single budget variable per node instead of using one per node and attribute.
46

---

Published as a conference paper at ICLR 2023
Modelling our collective problem in this way, using Eq. 145 the first two sums using inner products results the optimization problem
base certificates and rewriting
(15(r1) T
bx +7x (15()0)² T
mi b B
Σ RET
7x
bx
B
+² A
Σ
(m)
+
Σ
A
(n) (.
Br S 37(0m)
(146)
1.
N
N
N
N
s.t.
Σ m==1
bt S
+ X
T
Σ
3 STA
(147)
m==1
j=1
bt,b E B B E
(148)
This optimization problem is identical to that of Schuchardt et al. (202 from Eqs. (133)
(335)
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 single linear constraint. Schuchardt et al. (202T) 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 model's striet locality equivalent completely randomizing (here: flipping bits with probability 50%) parts of the input. While Schuchardt et al. (202)) only derived their certificate for binary data, it can also be applied to strictly local models for continuous data. Considering our certificates for Gaussian (Proposition F.I) and uniform (Proposition F.2) smoothing, where the base certificate weights are and x. respectively, is possible to perform the same masking operation as Schuchaardd et al. 1202)) by using -> oo and X 0C.
Finally, it should be noted that the certificate by [Schuchardt al. (202)) allows for additional con- straints, e.g. the adversarial budget per node or the number of nodes controlled by the adversary. As all of them can modelled using linear constraints on the budget variables (see Section their paper), they can be just easily integrated into our mixed-integer linear programming certificate.
47


Reviews:
[{"review_id": "nnhqdbaqvV", "reviewer": "Reviewer_7Fc5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a framework, Localized Smoothing, to solve the problem of collective certification. The proposed method does not rely on any assumption for the validity, but it is formulated to be able to exploit any homophily/soft locality property in the multiple labeling task. The paper's main idea is to use region-specific smoothing distribution that puts more noise on less relevant pixels and less on relevant pixels. The paper also provides experimental evidence showing the algorithm's superior performance on image segmentation and node classification tasks.", "summary_of_the_review": "The proposed method, Localized Smoothing, provides a general framework for collective robustness certification. The theorems proved in the paper show the theoretical benefit of using the proposed method over the existing state-of-the-art, which is also reflected in the experiments. Moreover, the Variance-constrained certification approach defined in the paper could be of independent interest. In general, I think the ideas in the paper, as well as the final algorithm, would be of interest to the ML community.", "strength_and_weaknesses": "Strengths\n- The proposed method extends the idea of using a strict locality condition to produce certificates to exploiting soft locality to produce a general certification method. \n- The authors propose a general framework to efficiently combine local certificates as long as they satisfy the correct interface.\n- The Variance-constrained certification approach provides a scalable way to do anisotropic $\\ell_0$ certification, which could be independent interest.\n- The experiments provided in the paper are detailed and give a comprehensive view of the benefits of the proposed algorithm.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "lu1lY_IfWk", "reviewer": "Reviewer_gYEN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes localized randomized smoothing to improve collective certificate.\nIt formulates the problem as a solution to a linear program after smoothing different parts of a given input image differently.\nExperiments were carried on two standard segmentation benchmarks and one node classification dataset showing the effectiveness of the proposed approach.", "summary_of_the_review": "This work has several merits of this work including the motivation, theoretical analysis, and supporting experiments. However, there are few concerns that I hope to be addressed in the discussion period. This includes the claim about the second contribution (efficient anisotropic certification), limited experimental analysis, and the writing of this paper.", "strength_and_weaknesses": "Strengths:\n\n- The problem that this paper studies is important.\n\n- The experiments presented in this work provide improvements over previous approaches supporting the main claims.\n\nWeaknesses:\n\n- The scale of the experiments in this work is rather small. Certifying only 50 images from Pascal and CityScapes might be not enough to draw conclusions on. I would suggest extending the results on larger amount of samples. Also, some fine-grained experimental analysis on instances containing different number of categories could also be insightful.\n\n- The second contribution of this work claims an efficient anisotropic randomized smoothing certificate. However, this problem was previously explored in the literature, as dictated in the related work, by Eiras et.al. Efficiency analysis between different approaches would strengthen this contribution. Further and since the experiments are done on few number of samples, how does the proposed method compare to ANCER from Eiras et.al when combined with other baselines?\n\n- The writing of the paper along with the presented notation need improvements in some parts of this work. For example, small paragraphs discussing both Theorem 4.2 and 5.1 would ease the reading of this work.\nFurther, in theorem 4.2, the prediction is referred to as $y_n$ while in the third paragraph of section 4 it is $\\mathbf y$.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hf7YLKa3LoU", "reviewer": "Reviewer_jKFf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel certification mechanism for certification in the multiple-output setting (e.g., image segmentation) based on randomized smoothing (RS), referred to as a collective certificate.\nRS typically is used to create a robust-by-construction classifier in the (single-output) classification setting, by evaluating a base model multiple times and reporting the majority output.\n\nThe key idea of this work is to utilize perturbation distributions for RS that match the locality patterns of the model outputs (e.g., use anisotropic distributions that capture locality). Prior works have either ignored this locality aspect or only treated strict locality imposed by the receptive field of convolutions.\nThis, in turn, requires determining the appropriate anisotropic smoothing distirbutions for all local regions, which the authors propose to solve a mixed-interger linear program (MILP). To avoid the high cost of the MILP, discretizations, and simplfications (larger regions) as well as a relation to linear programming are considered.\n\nThe approach is thoroughly evaluated on image segmentation and node classification. The results are good if the locallity assumptions truly hold (and deteriored as expected if not).", "summary_of_the_review": "This is a well-written paper proposing a new smoothing approach for multi-output settings.\nMy main concern is how inference would be handled soundly.", "strength_and_weaknesses": "**Strengths**:\n- The paper is well-written and easy to follow. Arguments in the main paper are thorughly backed-up by derivation and explanation in the appendix.\n- Algorithmically interesting approach for a relevant problem.\n- Mathematical justifications are thorough and appear to be correct seem correct.\n\n**Weaknesses**:\n- Some aspects of inference are unclear (see below).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%