Sound Randomized Smoothing in Floating-Point Arithmetic
Authors: Vaclav Voracek
Matthias Hein
Venue: ICLR 2023 poster (2023)
Keywords: Randomized smoothing
floating-point arithmetic
adversarial robustness
formal methods

Abstract: Randomized smoothing is sound when using infinite precision. However, we show that randomized smoothing is no longer sound for limited floating-point precision. We present a simple example where randomized smoothing certifies a radius of $1.26$ around a point, even though there is an adversarial example in the distance $0.8$ and show how this can be abused to give false certificates for CIFAR10. We discuss the implicit assumptions of randomized smoothing and show that they do not apply to generic image classification models whose smoothed versions are commonly  certified.  In order to overcome this problem, we propose a sound approach to randomized smoothing when using floating-point precision with essentially  equal speed for quantized input. It yields sound certificates or image classifiers which for the ones tested so far are very similar to the unsound practice of randomized smoothing.  Our only assumption is that we have  access to a fair coin.

Published as a conference paper at ICLR 2023
SOUND RANDOMIZED SMOOTHING IN FLOATING- POINT ARITHMETIC
Václav Voráček, Matthias Hein Tübingen Al Center, University of Tübingen
ABSTRACT
Randomized smoothing is sound when using infinite precision. However, we show that randomized smoothing is no longer sound for limited floating point precision. We present a simple example where randomized smoothing certifies radius of .626 around point, even though there an adversarial example in the distance 0.8 and show how this can be abused to give false certificates for CIFAR10 10. We discuss the implicit assumptions of randomized smoothing and show that they do not apply to generic image classification models whose smoothed versions are commonly certified. In order to overcome this problem, we propose a sound approach to randomized smoothing when using floating- point precision with essentially equal speed for quantized input. It yields sound certificates for image classifiers which for the ones tested far are very similar the unsound practice of randomized smoothing. Our only assumption is that we have access to a fair coin.
INTRODUCTION
Shortly after the advent of deep learning, was observed in Szegedy et al. (2014) that there exist adversarial examples, i.e., small imperceptible modifications of the input which change the decision of the classifier. This property is of major concern in application areas where safety and security critical such medical diagnosis or in autonomous driving. To overcome this issue, lot of
different defenses have appeared over the years, but new attacks were proposed and could break
these defenses, see, e.g., (Athalye et al.] [ Croce and Hein [0200] Tramer et al., [2200] Carlini et al.) 2019). The only empirical (i.e., without guarantees) method which seems to work is adversarial training (Goodfellow et al.) 20155 Madry et al. (2018) but also there, a lot of defenses turned out to be substantially weaker than originally thought (Croce and Hein 2020).
Hence, there has been focus on certified robustness. Here, the aim produce certificates assuring no adversarial example exists in small neighborhood of the original image. For the neighborhood, typically called threat model, one often uses fp- balls centered at the original image. However, there also exist other choices, such Wasserstein balls (Wong et al. 2019 Levine and Feizi 2020) or balls induced by perceptual metrics (Laidlaw et al.] 2021 Voráčck and Hein 2022). The common certification techniques include (1) Bounding the Lipschitz constant of the network,
Hein and
Andriushchenko (2017); Li et al.) (2019):(Te) Trockman and Kolter (0 Leino et al. (002T) [Singla la et al. (2022) for the &g threat model and Zhang al. (2022) for fxc. (2) Overapproximating the threat model by its convex relaxation (admittedly, bounding Lipschitz constant can also be interpreted this way), possibly combined with mixed-integer linear programs SMT; see, e.g., Katz al. (2017): Gowal
et al. (2018); Wong et al. (2018); Balunovic and Vechev (2020). (3) Randomized smoothing (Lecuyer al. 2019 Cohen al. 20199; Salman 2019). which hitherto the only method scaling to
ImageNet. Note that the concept of randomized smoothing may also be interpreted as special case
of (1), see (almann et al. 2019))
All of these certificates expect that calculations can be done with unlimited precision and do not take into account how finite precision arithmetic affects the certificates. For Lipschitz networks (1), the round-off error is of the order of the lowest significant bits of mantissa, which we can estimate to be in the orders of 10 for single-precision precision floating-poin numbers. Thus, we should assume that the adversary can also inject lao -prruuraation bounded by 1 in every layer. However, since the networks have small Lipschitz constants by construction, those errors will not be significantly magnified. Although cannot universally quantify the numerical emror of Lipschitz networks,

---

Published as a conference paper at ICLR 2023
they will likely be very small and in particular, can be efficiently traced during the forward pass so that the certificates can be made sound. For the verification methods from category (2), previous works have shown that numerical errors may lead to false certificates for methods based on SMT or mixed-integer linear programming (Jia and Rinard 2021 Zombori et al. 2021). However, is possible (and often done in practice) to adapt the verification procedure to be sound w.r.t. floating- point inaccuracies (Singh et al., 2019); thus, the problem is not fundamental, and these verification techniques can be made sound. For randomized smoothing certificates (3), Jin et al. (2022) perform floating poatingg-pointt attacks on certifiably robust networks and indicate the existence of false certificates; see Appendix F for discussion. The recent work of Lin et al. (202T) focuses on randomized smoothing when using only integer arithmetic in neural networks for embedded devices, so they will, by definition, not have problems with floating-point errors. On the other hand, it does not cover some modern architectures, such as transformers. Furthermore, the way the certificates are computed is derived from the continuous normal distribution; thus, the certificates are approximate, see Appendix G Another direction is so-called derandomized smoothing methods that remind randomized smoothing but are deterministic. See, e.g., Levine and Feizi (2021)
In this paper, we make the following contribution
1. We perform novel analysis of numerical errors in randomized smoothing approaches when using floating-point arithmetic and identify qualitatively new problems.
2. Building on the observations, we present a simple approach for developing classifiers whose smoothed version will provide fundamentally wrong certificates for chosen points and discuss how this could be exploited in practice.
3. We propose a sound randomized smoothing procedure for Koating-poine arithmetic with negligible computational overhead for image classification compared the unsound practice.
While we could not find substantial differences of our sound certificates compared the unsound practice for our tested classifiers, a lack of a counterexample is not a proof of the correctness. The past has shown that such gaps will be exploited by malicious actors in the future. It be expected that certificates of adversarial robustness are required for classifiers used in safety-criticll systems (see European AI act European Commission 202T and thus will be controlled by regulatory bodies. malicious company could use then the problems of randomized smoothing in floating- point arithmetic to provide fake certificates on a known/lcaked test set. Since our sound randomized smoothing procedure for Hoating-poin arithmetic comes at essentially no additional cost for quantized input e.g., images, we believe that using our sound procedure should always be used for such domains.
Manuscript organization: We start with the definition of randomized smoothing Section 2 then we continue with the introduction of floating-poin arithmetic following the IEEE standard 754 (iee) 2008) in Section 3 In Section we exploit the properties of floating-poine arithmetic and present a simple classifier producing wrong certificates, and we follow with the identification of the implicit assumptions of randomized smoothing. In Section we conclude the main result by proposing a method of sound randomized smoothing in floating-pont -ponnt arithmetic and provide an experimental comparison of the old unsound and the new sound certificates.
2 RANDOMIZED SMOOTHING
Throughout the paper, consider for clarity the problem of binary classification, but every phe- nomenon we discuss can be casily transferred to the multiclass setting. We note that the proposed algorithmic fix, see Appendix K well as the experiments in A are done for the multiclass setting.
We first introduce randomized smoothing and define certificates with respect to a norm ball.
Definition 2.1. A classifier F: 2 + {0, 1} is said to be certifiably robust at point x e IRd with radius r, w.r.t. norm |.| if the correct label at x is {0, 1}. and |x x'1 S = F(x') y.
One way to get such a certificate is randomized smoothing (Lecuyer et al. 2019 Cohen et al. 2019 Salman et al. 2019) which we introduce following. We are given base classifier 12
0,
Cooe available at http://www..aaaaa//....c///////a
zed Smoothi
2

---

Published as a conference paper at ICLR 2023
Its smoothed version is f(x) 1. E), and the resulting hard classifier is F(x) [f(z) > 0.5], where the Iverson bracket [statement] evaluates to if and only the statement inside holds true. Using the Leyman-Pearson lemma the following result has been shown:
Theorem 2.2 ((Cohen et al. 2019)). Let F be deterministic random classifier and let क- be the inverse Gaussian CDF. If
(F- CC)) PA.
for some PA (3) 1}. then F(x+ () C for all 5 Rdd with |081| < <a t (PA).
We call in the following r(z)= = क (-(((=)))) the certified Ez-radius of F æ.
We note we require that the output of the base classifier F to be independent of previous inputs and outputs. is easy to construct an violating this assumption and producing false certificates, e.g., take F that returns 0 in the first 10 calls and 1 afterwards. For the majority of classifiers, it is intractable evaluate fx) exactly; therefore, random sampling is used to estimate and thus only a probabilistic certificate is possible where the probability that the certificate holds can be made arbitrarily close one if one uses more samples weakens the certificate. Following the literature, we use 100 000 samples estimate f(x) and then lower bound this by p for certifying class (resp. upper bound it for class 0) so that the failure probability, that when p > f(x) (resp. p < f())), is at most 0.001. The value of p can be computed using tail bounds or classical Clopper-Pearson confidence intervals for the binomial distribution. The actual certification procedure is described in Algorithm However, to keep the example below in Listing as simple possible, we computed p using simple Hoeffding bound which we derive in Appendix Although it produces a weaker certificate, it is still sufficient for the demonstration.
COMPUTER REPRESENTATION
FLOATING-POINT NUMBERS
In this section we briefly introduce the floating-poil representation and arithmetic according to standard IEEE-754 (iee 2008). A detailed version with examples and treatment of other precisions can be found in Appendix C where present examples in a toy, 8-bit, arithmetic. Here, introduce only single-precision floating-point numbers.
Single-precision floating-poii point numbers represented in memory sequences of bits 31 ....... .332 The first bit is a sign bit, the next 8 bits determine the exponent, and the last 23 numbers determine the mansissa. The conversion normalized form is as follows:
(1
32
(-1)at 2(E 2.2 2)-17
34 29-1
We will write the floating-point operations in circles; e.g., @, instead of +, distinguish them from the mathematical ones which do not suffer from rounding errors.
The addition (or analogically subtraction) of floating-point numbers is performed in three steps. First, the number with the lower exponent is transformed to the higher exponent; then the addition performed (we assume with infinite precision), and then the result is rounded fit into the floating-pont representation. An example is provided in C.2 in Appendix
Thus, it happens that e y x for any x and some y z. Consequently, there will exist some w such that there is no for which @ v = This is the main observation that we will built and is treated in detail Appendix Cin Example C.3
3.1 CONNECTION TO RANDOMIZED SMOOTHINNG
We have identified some unpleasant properties of floating- ppotin arithmetic that we will exploit in sequel to provide false certificates. In particular, We will try to determine a given number could be smoothed version of specific number not. The following observations will help
In Reiser and Knuth (975). it is shown that the identity ((x @ y) e ey @ yoy= x o holds apart from single y for any æ. It is further shown that the identity (((2r (z:
o (x o v) ey
3

---

Published as a conference paper at ICLR 2023
holds always true. On the other hand, there is no evidence that the equality (r y) y x should hold. Indeed, consider z to have a lower exponent than y. Then during the addition, a @ y, the low bits of the mantissa of z are lost. Similarly, if y has different exponent than y, then a loss of significance may occur during the second rounding. Finally, consider the case where I a @ y, then the identity (I y) y holds.
Our idea is to make the classifier determine if the observed value x could be a smoothed version of a. This can be done precisely, but we only approximate this using the previous observation. The reason is that it is sufficient for the demonstration, and the resulting function (introduced in Equation (T) in the next section) will be simple, suggesting that the phenomenon may occur in standard networks.
3.2 FLOATING-POINT ISSUES IN THE CONTEXT OF DIFFERENTIAL PRIVACY
Randomized smoothing has been motivated by differential privacy (I (ecuyer et al. 2019). In differen- tial privacy it has been shown in the seminal work of MMronov (2012) that the lowest bits of mantissa can serve as a side channel which yields a substantial discrepancy between the theoretical propertics of algorithms of differential privacy, and the properties of their naive implementations, see Mironov (201)); Jin et al. (2021): Bichsel et al. (2021). Consequently, revisions of the standard differential privacy mechanisms accounting for the floating-pois pointt errors have appeared, see, e.g., Casacubertal ct al. Canoone et al. (020), and included in the framework OpenDP (Gaboardi et al. (2020).
In our construction, utilize of the rounding errors of floating-point addition. On a high level, this is similar to what |Mironoy] (2012) exploit. However, their procedure considers Laplacian noise and the example also exploits the Laplace distribution samplers' properties.
4 CONSTRUCTION OF CLASSIFIERS WITH FALSE CERTIFICATES
We present an example of a function F: R {0, 1} which is prone to giving incorrect certificates via randomized smoothing; the whole "experimental setup" captured Listing [ The example is based on the observation that we are able to determine if a floating point number could be result of moating-point addition @ n where whose behavior we analyzed in Subsection 3.1
known and n is arbitrary. We construct function Fa
Fa ((==))((==))=])))
We take Fa the base classifier and consider the smoothed classifier fa it induces with 0.5. It holds that (a) therefore if we have enough samples, we may obtain very large certified radius. Specially, in the example considered in Listing with 100 000 samples, we can certify a b2-radius of 1.26 around point = 210/255, however 0 = F. (0) Fa (a) = 1, and the point 0 is nowhere near the boundary of the certified ball. the example in | we use a simple Hoeffding bound jnstead of the standard bounds of Clopper-Pearson The Clopper-Pearson bounds certify robust radius 1.9.
import nampy as np from scipy.stats import norm
sigma 0.5; num_samples 100000; alpha 0.001
lambda x: (x 210/255) 210/255 x noise np. random. randn
ssigma
pl = {(+nciss) sum ///nn_samplees
# 0.46 # 1.0
p2 (2200/55+tnise)) .um.s))sssmmm)))) () sampplssssssesssseea__aeee
10 p--(-np. hopp.oogaaal (og / /uw_asammeee//mmmaaama *+0
11 = sigma * norm. ppt. (p)
# 1.26
Listing 1: example of incorrect randomized smoothing certificate
This construction does not rely on the fact that Fa + s) = for NO 02) with very high probability, it only serves as a striking example. Similarly, we get 0 = (0) 4 F, (200/255) despite every point 0, 1/255..... 255/255 would be class according to the certificate.
4

---

Published as a conference paper at ICLR 2023
4.1 CONSEQUENCES FOR IMAGE CLASSIFIERS
We stress that the simple construction generalizes to images. For the remainder of the section, we consider (0, 1/255,.. 255/255) (d be vectorized image with e.g., d 3 3-322 3072 for CIFAR dataset. Indeed, we could employ a function
(x,( 1(,, e o x;],
which takes vectorized version of an image certify that any image with intensity 210/255 at position is class 1 with robust radius 1.26, while any image with intensity 0 at position would be classified as 0; a clear contradiction. We take one step further. Consider a function with parameter é R
input. Using such function in Listing I would
G (x) = min! 0 @ a x,]
(3) v 1; thus, certifying "arbitrarily" high radius (to be specific, with
holds that E Ga(a+ E 100 000 samples it is 3.8115 in l norm), and Ez-N(o.1)) Ga (a' + 5) < 0.5 for the vast majority of inputs a + d'. We tried the following experiment: For every image a in the CIFARIO test set, we created an image a' by increasing the image intensity of a by 1/255 at 512 random positions. Then it holds that IE. (Dc-N((,1)Ga(( + s 0.2 for every CIFAR image a with high probability, even though
||a (a=a'll2 < 0.09.
Following this line of examples, let us introduce the base classifier:
Hx(x)= m8X A (z maX A min [(2;
(4)
where A is a set of images. Therefore, when A is the set of CIFARIO I0 test set images, then we can certify the robustness of the smoothed version of HA at every point of the CIFARIO test set for large radii, even though it is vulnerable even to small random perturbations. We remark that HA can be implemented with a standard network architecture using only linear layers and ReLU non- non-lincasisies. To conclude the examples, we state the findings in the upcoming proposition. Since we introduced the machinery only for binary classification, we treat CIFARIO as binary classification dataset. For time reasons, we (as it is common in the context of randomized smoothing) only consider 1000 test images for the upcoming proposition; the first 500 images from the test set of both classes.
Proposition 4.1. There is a classifier with certified robust accuracy 100% on the first 1000 CIFARIO
test set images X c [0, 255 ...., 1 (where we define class 0 to include classes 0, 1, 2,3, 4 of CIFARIO and class contains the other classes) with l--rrobust radius of and failure probability 0.001 using randomized smoothing certificates, while for every point é X there is an adversarial example x' with | x') 2
The proof can be found in Appendix D The past has shown that loopholes can and will be exploited in the future by malicious actors trying to trick certification agencies e.g. see the diesel scandal where car manufacturers detected the test in a lab to fake significantly better pollution values. As the European AI act requires a certain level of adversarial robustness in safety-critical applications, certification agency are likely to evaluate certified robustness in the future. In order to illustrate the problem, we just sketch how the fake certificates of Proposition 4.1 could be exploited. In fact let M be the classifier described in the proof of Proposition 4.1 and let m(()) E.--
c) be the smoothed version of M. One can see that roughly m(x) = 1 if x & N(X), where N(X) denotes a small neighborhood of the test set X. Given neural network for image classification simple way to trick the certification agency. would be a new classifier where one uses the neural network whenever < m(x) s 1 ō_ e.g. 8 0.1, and otherwise the classifier M of Proposition 4.1 This classifier would inherit the strong fake robustness guarantees on the test set from M but behave like a normal classifier on any other input. We emphasize that this problem is resolved by our fix to randomized smoothing in floating point representation of Section S which has negligible computational overhead for image classification.
4.2 IMPLICIT ASSUMPTIONS OF RANDOMIZED SMOOTHING
The obvious questions after this negative result are: i) what is the key underlying problem point arithmetic? ii) what are the implicit assumptions in randomized smoothing?. and iii) how can fix the problem?
in floating-
5

---

Published as a conference paper at ICLR 2023
The first assumption of randomized smoothing is that samples from normal distribution are indeed i..d. samples. This is not true for floating- point precision due to the rounding: Thus, the resulting distribution from which we observe samples is uncontrolled, and for certification, we should not rely on it. However, violation of this assumption is not the cause of the wrong certificate in Listing |
The intuition behind randomized smoothing is that the distributions D1 (Nx,, and D2 N(= + e, I2) have significant overlap for small values of e. As a consequence, the smoothed classifier f(x) Bg-N((,,0 F(x+ +) evaluated at z also carries information about its value at points near æ. However, the following observation will prove this wrong in floating- -pont arithmetic.
Roughly speaking, the supports of two high dimensional normal distributions appear to be almost disjoint, although in one dimension the overlap may be substantial. To support this claim, We performed the following experiment; given point E {0, 1/255, ... 255/255) and a 0, find point e {0. 1/255,.. ... 255/255) such that |a - bj & 2/255 which minimizes the probability that for an E1 ~ (O, o²) there exists a number E2 such that a E1 b @ Eg. For example, if 2 5/255 and a= 1, then the minimized probability is less than 0.99, and for the majority of a 0 5/255 it is even smaller. In order see that the distributions are almost disjoint, consider CIFAR dataset, a 3-3022 which has at least half of its channels with intensities greater than 4/255. According to the previous observation, we can find an image a' such that ||a la-a',, d'I x0 = 2/255 and that the probability that smoothed at any (non black) position could be a smoothed version of a' is at most 0.99 (this can be exploited by function Fa, from Equation ( Therefore, the probability that a smoothed version of the first image could also be smoothed version of the second image is at most 0. 30792 x 2 x 10-7 (this can be exploited by function G. from Equation (3). Thus, when we follow the standard practise and use 10 samples to estimate f(a) from base classifier F, the chances that at least one of the samples belongs to the distribution from which we sample to estimate f(a') is most in the orders 10-2, Consequently, without any assumptions on the base classifier F,, f(a) carries almost no information about (a').
image, say from
4.3 POTENTIAL REVISIONS OF RANDOMIZED SMOOTHING
The described experiment exploits the floating-point rounding. The errors are in the order of the least significant bits, which are in the order of 10-8 for single-precision and 10-1 for half-precision. Since these numerical errors are not controlled, we should assume that the model is adversarially attacked during smoothing, where the attacker's 's budget is the possible rounding error, denoted as B; therefore, the smoothing (for certifying class 1) should be performed as:
f(x) IE minezes F(x+
To mitigate this problem, during estimating f(z), we should certify F(x+e). Although the attacker's budget B is very small for single accuracy and possibly noticeable for the half accuracy, it is not clear how it should be certified, since in randomized smoothing, there are assumptions on F.
Consider F to be a thresholded classifier F(z)= [f(=) > 0.5], where f is a neural network, then we could certify that f is constant in B-neigghouuhooo of the smoothed image. For generie models, this can be done by either bounding the Lipschitz. constant of f (w.r.t. an -like norm), or by propagating convex relaxation (c.g.. IBP) through the network. For smoothing, there are usually used deep models. E.g.. Salman et al. (2019) used ResNetl 10 and ResNet50 for certifying CIFARIO and ImageNet respectively. The bound on the global Lipschitz constant of deep network by bounding the operator norms of each layer is thus very weak (N< 1000 130 depending on the model) and cannot certify F(x + even under such a weak threat model as the rounding errors in B.
A possible defense against this problem would be to round the input on a significantly larger scale than B before evaluating F. Let the rounding be performed by a mapping g, then we would in fact smooth a classifier F o g. If we consider B to be in the orders of 10-8 and we would round it to orders 1 then the probability that x E will be close to the boundary of rounding, i.e., J E 8 g(x s $2) + g(x e) would be on the order of 10-6, 6, which is then the probability that the attack within the threat model B could indeed change the input of F at a single position. Consequently, the probability that there is no Eg E B which would change the result of rounding is very roughly s (1- 100) 3072 a 0.997 for CIFAR and æ (1 - 10 150328 a 0.86 for ImageNet. This means that for approximatelly 86% of the smoothed ImageNet images we can guarantee that

---

Published as a conference paper at ICLR 2023
F( F(x+ and for the others, could e.g.. min F( 0. This replacement of by F during smoothing seem to solve the problem for CIFAR and partially also for ImageNet for single precision. For half precision, the problem will persist.
However, even this adjustment solved the problem with numerical errors satisfactorily during the unlikely to control
addition of noise images, the certificate will still not be sound because the normal distribution sampler's s performance. The normal distribution samplers implementations used standard software libraries (e.g., Ziggurat algorithm; Box-Muller transform) transform i.i.d. uniform distribution samples to i.i.d. normal distribution samples. While this is true in theory for unlimited precision: here, we perform floating-poit poiii operations. Therefore, the sampling is subject to floating-pone point enrors and we don't observe the actual rounded samples from normal distribution.
While we do not present any example exploiting the subtle errors of the normal distribution samplers, relying on them only keeps possible loophole in the procedure. As our goal is to propose sound randomized smoothing procedure in floating-pon arithmetic, our work would be incomplete if we addressed only some potential causes of floating-point errors and not the others, even though think they are harder to exploit. particular, we note that Mironov (2012) exploited the (standard) floating- point implementation of the Laplace distribution sampler in order to attack the guarantees of differential privacy.
SOUND RANDOMIZED SMOOTHING FOR FLOATING-POINT ARITHMETIC
In this section, we will derive sound randomized smoothing certification procedure for floating-poit arithmetic. Our only assumption is the access to i.idd samples of fair coin toss, which is equivalent to having access to samples from the uniform distribution on integers 0, ...... , for some n. Thus, assume to have access to uniform samples from numbers representable by Long datatype, that is when n = 64. We further consider classification tasks where the input is quantized as it is true for images. Throughout the section, consider the input space be {0, 1...., 255} d in order have clear notation. The generalization to other forms of quantized inputs is generic, but the generalization to real-valued inputs is bit more involved; move the discussion Appendix B The resulting algorithm is captured in Appendix K in Algorithm
5.1 CERTIFICATION OF QUANTIZED INPUT
As discussed in the previous section, it is appealing to quantize the smoothed images before feeding them into the network. Thus, we prepend a mapping 9& Rd - [-k, 1..... 255}. for some positive integer & which rounds the input to the nearest integer from its range before the function to be smoothed F; therefore, the smoothed classifier (with base classifier F gk) is defined as:
f(x) (o- F(g((x+))),
which we further equivalently rewrite as
f(x) (x-.)( F(t).
This treatment crucial for the method. Instead of adding noise to the input, which subject to rounding errors, we sample the noised input directly.
5.2 DISCRETIZED NORMAL DISTRIBUTION
It remains to show how to obtain i.i.d. samples from the discretized normal distribution
N (x. o²) (x)+)))))))))) ~ (0,
We note that the discretized normal distribution is different from the discrete Gaussian distribution used in the context of differential privacy (Canonne al. 2020).
As discussed in the two final paragraphs of Subsection 4.3 it is not enough to round samples from normal distribution since we cannot guarantee the correetness of the normal sampler. The key observation that we do not even need to obtain samples from A/ o²) anymore. The resulting distribution from which want sample now is discrete. Concretely, we have
7

---

Published as a conference paper at ICLR 2023
Table 1: Time comparison of certification times per image of the standard randomized smoothing and the proposed sound procedure with and without reusing noise. Details in Appendix A.I For CIFARIO we used 100 000 random samples and for ImageNet 10 000.
dataset
standard proposed w/ reusing
proposed w/o reusing
CIFARIO (ResNet- 10)
9.82
9.87s
31.70s
ImageNet (ResNet-50)
8.65 s
8.67
129
-oo
ktt
1
u
20 du
if a = -k.
Van0²
(a-u)
sar
2n
du
if -k < < k + 255, Z
PaN [t= a]
V2n02
JK+255 3 V2nm
du
a k 255.
otherwise
Additionally, the following well-known property of normal distribution holds for the discretized normal distribution as well.
Proposition 5.1. Let k be a positive integer and x e {0, 1..., 255), then it holds that Nb(2,0") max(-k, min 255, + x}}, t' -ND N5-2555 (0,
Thus, it is enough to have sampler from Nb 20-25550,,0)))5 (0,
The value of is chosen such that the vast majority of samples from N (x, o²) falls into the interval (-k, + 255]. The choice of does not affect the correctness of the certificates, but may affect the accuracy. In the experiments we chose = Games= for inputs from [0, 1jd, so it corresponds to 255 in the notation of this section.
5.2.1 DISCRETIZED NORMAL DISTRIBUTION SAMPLER
Let us denote the quantile function (inverse edf) of (b 0²) as TD then D transforms i..d. samples from the uniform distribution on the interval [0, 1) 1) to i.i.d. samples from fromW/
distribution N (0, d²). To sample from N D (0, o²), we first approximate the samples from 40 1) by samples from the discrete uniform distribution on (0,...,2" 21) which will interpret uniform 2=11== =: U(0, 1). Then we only need to compute the 2k+ 255 probabilities with high enough accuracy that we can claim the correctness of 47 (u) for u {0, 20 .....
distribution on {0,
2" 2"-1 }.
This is ensured by using symbolic mathematical libraries allowing computations in arbitrary precision.
Since the distribution N3 (0, o²) is supported on 2k 256 events, there will be 2k + 255 points æ e {0, 2 ..... 2"11) such that 27, 25 (x zn Now, consider the mapping between samples from (0, 1) and U(0, 1) which rounds down sample from the continuous real interval [o. 1) to the closest point u from the set {0, 1 2--1), }. Then holds for the probability $ (u) (v) < 255+2k not the actual i.i.d. sample is thus most 212-n at position. Therefore, the probability that all the smoothed images, considering ImageNet sized images with shape 3 x 224 x 224, out of 100 000 smoothed samples are indeed the correct i.i.d. samples from discrete normal distribution is least 1 1 24-n > 0.999996 for n 64.
2nd < 212-n for a choice k = 7.5 x 255. The probability that a produced sample is
Therefore, the probability of receiving a sample that might not be the actual i.i.d sample is negligible. Still, we can check if we receive such a potentially flawed sample a and in that case, we would set F(x) when certifying class (resp. F(x) when certifying 0) for that particular sample.
5.2.2 SAMPLING SPEED DISCRETIZED NORMAL DISTRIBUTION
The sampling is slightly more expensive since we need to threshold the observed uniform samples; however, this is only implementation issue. On the other hand, it is sufficient to sample i..d. noise for just one image 100 000 times and reuse it for all the other images. The certificates will be valid, only the case of failure for different images will not be independent, but it is not required in the
8

---

Published as a conference paper at ICLR 2023
Table 2: Certified radii for a model I' smoothed with NN o21) on CIFARIO test set. Evaluated on 500 images from the test set highlighting the differences. The model is ResNet-1100 taken from (Salman et al. 2019), more details in Appendix
Sound smoothing of F ge via Algorithm
2 for k
certified radius
0.1
0.25
0.5
0.75
1
1.25
1.5
2.0
0.12
0.878
0.848
0.778
0.000
0.000
0.000
0.000
0.000
0.000
0 0.25
0.836
0.808
0.746
0.600
0.466
0.000
0.000
0.000
0.000
0.5
0.708
0.672
0.618
0.502
0.410
0.338
0.248
0.174
0.000
0 1
0.512
0.492
0.448
0.380
0.316
0.278
0.230
0.182
0.112
Standard smoothing of FF via Algorithm
!
certified radius
0.25
0.5
0.75
1.25
1.5
2.0
0 0.12
0.880
0.848
0.778
0.000
0.000
0.000
0.000
0.000
0.000
0.25
0.836
0.808
0.746
0.602
0.468
0.000
0.000
0.000
0.000
0.5
0.706
0.672
0.618
0.502
0.408
0.338
0.248
0.174
0.000
1
0.516
0.492
0.448
0.378
0.316
0.278
0.230
0.182
0.110
literature. As we sample just once for the whole data set, the time spent for sampling is negligible, see Table I]
We discuss the timing in detail in Appendix [A.]
Finally, we wrap up the observations in the following corollary:
Corollary 5.2. Let F Idd - {0, be a deterministic or a random function and gk. Bd +
Ik 1k+1
k-2
maps imput to the closest point of its range, breaking ties arbitrarily. Then the
155 255 ..... 255,
following two functions identical:
=(())=E
F(ox(z+)))
f(z) = -EL)-(E-.E)))) F(t).
Therefore, to certify f1 with base classifier F using randomized smoothing, we can estimate the value of f and use for the certification. Furthermore we can get i.i.d. sumplesfrom t~ (N, with arbitrarily high precision using exact arithmetic; thus, the certificate is sound.
Remark 5.3. The empirical performance of the sound and unsound versions of randomized smoothing are essentially equivalent practice; see Table and also Appendix A for the evidence. However, no longer incorrectly certifies the example from Listing [ where it only certifies radius 0.6, and the points are distant 0.82 from each other. Similarly, the smoothed classifier of M from Proposition 4.] does not contain the universal adversarial perturbations in the certified balls around the points. See Appendix for more details.
To summarize: we showed how to replace sampling from the normal distribution, where one cannot trace the numerical errors, by sampling from the uniform distribution on integers, where we can bound the failure probability in order to obtain high probability estimates of the output of smoothed classifier with prepended rounding mapping. See Algorithms [ for the comparison of the standard and the proposed certification procedure. We also provide an empirical comparison of the methods in Table and in Appendix A
CONCLUSION
In the paper, we described multiple simple ways how construct models that will be certifiably robust for points of our choice using the standard randomized smoothing certification procedure, although there will be adversarial examples in their close neighborhood.
Most importantly, we provided a sound way to do randomized smoothing in floating point representa- tion which comes at negligible cost in image classification.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The authors thank the anonymous reviewers for their comments, which helped improve the quality of the manuscript. The authors acknowledge support from the DFG Cluster of Excellence "Machine Learning New Perspectives for Science", EXC 2064/1, project number 390727645 and the Carl Zeiss Foundation in the project "Certification and Foundations of Safe Machine Learning Systems in Healthcare". The authors are thankful for the support of Open Philanthropy.
REFERENCES
IEEE standard floating point arithmetic. IEEE Std 754-2008, Aug 2008 doi: 10.1109/EEESTTD.2000 4610935.
A. Athalye. N. Carlini, and D. Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In ICML, 2018.
Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap, In ICLR, 2020.
Benjamin Bichsel, Samuel Steffen, Ilija Bogunovic, and Martin Vechev. Dp-sniper: Black-box discovery of diffcrential privacy violations using classifiers. In 202/ IEEE Symposium on Security and Privacy (SP), pages 391-409, IEEE, 2021.
Clément L. Canonne, Gautam Kamath, and Thomas Steinke, The discrete gaussian for differential privacy, 2020. preprint, arXiv:2004000110.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wicland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv:190.007755, 2019.
Sílvia Casacuberta, Michael Shoemate, Salil Vadhan, and Connor Wagaman. Widespread underestimation of sensitivity differentially private libraries and how fix it, 2022. preprint, arXiv:2207.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In NewrIPS, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In ICML, 2020.
European Commission. Regulation for laying down harmonised rules on Al. European Commission. 2021. URL htttps://eur- 1ex. www.xeuuopp.auu. www.errpp.a...ee.aaloooo.aaatta. /EN/ EXI/PDF SCc//DF/2uriiCEEE. 2uri=CELEX
52021PC0206sErom-BD
Marco Gaboardi, Michael Hay, and Salil Vadhan. A programming framework for opendp. Manuscript, May. 2020.
L J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In JCLR, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmect Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv:1810.12711 12715, 2018.
M. Hein and M. Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. In NeurlPS, 2017.
Kai Jia and Martin Rinard. Exploiting verified neural networks floating point numerical error. International Static Analysis Symposium, 2021.
Jiankai Jin, Fleanor McMurtry, Benjamin Rubinstein, and Olga Ohrimenko, Are we there yet? timing and floating-point attacks on differential privacy systems. arXiv preprint arXiv:21 2021.
Jiankai Jin, Olga Ohrimenko, and Benjamin IP Rubinstein. Getting a-round guarantees: Floating point attacks certified robustness. arXiv preprint arXiv:2205. 2022.
Guy Katz, Clark Barrett, David I. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In CAV, 2017.
10

---

Published as a conference paper at ICLR 2023
Cassidy Laidlaw, Sahil Singla, and Soheil Feizi. Perceptual adversarial robustness: Defense against threat models. ICLR, 2021.
Mathias Lecuyer. Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. IEEE Symposium on Security and Privacy (SP), 2019.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks, In ICML, 2021.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks. In A/STATS, 2020.
Alexander J Levine and Sobeil Feizi. Improved, deterministic smoothing for L certified robustness. In ICML,, 2021.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jöm--Henrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. NeurIPS, 2019.
Haowen Lin, Jian Lou, Li Xiong, and Cyrus Shahabi. Integer-arithmeticconly certified rohustness for quantized neural networks. In ICCV, 2021.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Valdu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security, pages 650-661, 2012. 2012
John F. Reiser and Donald E. Knuth. Evading the drift in floating-pois addition. Information Processing Letters, 3(3):84-87, 1975.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. NeurlPS, 2019.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. In POPI, 2019.
Sahil Singla, Surbhi Singla, and Sohcil Feizi. Improved deterministic ly robustness CIFAR-10 and CIFAR-100. In ICLR, 2022.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In NeurIPS, 2020.
Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In ICLR, 2021.
Václav Voráček and Matthias Hein. Provably adversarially robust nearest prototype classifiers. In JCML, 2022.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In NewrIPS, 2018.
Eric Wong, Frank Schmidt, and Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. In ICML, 2019.
Andrew C. Yao. Theory and application of trapdoor functions. In Symposium on Foundations of Computer Science, 1982.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of l-infinity distance nets. In ICLR, 2022.
Dániel Zombori, Balázs Bánhelyi, Tibor Csendes, István Megyeri, and Márk Jelasity. Fooling complete neural network verifier. In ICLR, 2021.
11

---

Published as a conference paper at ICLR 2023
A EXPERIMENTS
To run the experiments, we used the publicly available codebase of Salman et al. (2019) which is distributed under MIT licence. Our modifications will be publicly available under MIT licence. The experiments were run on a single Tesla V100 GPU. The models we evaluated were chosen arbitrarily from the models Salman et (2019) provide in their repository. Their identifications are:
pretrained models/cifar 10/innetue cifar from imagened/GDDsscps/PGD) Satpsceppp/GG__IOtpppsspppp 10eepps multinoise/22 multitrain/eps O4/cciaa httpslssoocccccccoittiiile
pretranedd_moddll/iiitteee
///eeeeee (//esnett | pth.
(/resnett O/oosse__c/chhccooinnttt hrgp://eeSe222ciaiiioeeeeeeeeeer pth.ttt
where a {0.12, 0.25, 0.50, 1.00) for tables and respectively. In Table 2 100 000 samples are
used, whereas for Tables 3 we used only 10 000 samples evaluate the smoothed classifier.
For Imagenet experiments, we used models:
pretrained_ Sttp://wwwwp.p.e..eee//////////e http://ppp....eeeeeeeee/ooiieeep hatpss/eeeeeoiiiiseoccepepopppoo pttckkpppott...ttttt
where (0.25, 0.50, 1.00} for tables and 6 respectively. Again, we used 10 000 samples evaluate the smoothed classifier.
A.1 SPEED
The speed essentially equal for both of the methods, described in Algorithm [ respectively because compute the noise beforehand and then image, where n is the number of samples used to evaluate a smoothed classifier. The time needed to generate the noise is in the order of minutes; thus, negligible compared to the time needed to run the experiments.
the same set of noises for every
To be more precise; time per image for 100 000 samples used to evaluate the classifier is 9.82 0.05s. If we precompute the noise batches (batch size 1000, thus we have 100 batches) and save them files. Then with every image and every batch we load the corresponding noise, the time is then 10.47 + 0.03s per image. The advantage of this approach that the change of the codebase is minimal. In our case, we changed two lines of code of Salman et al. (2019) and added one class. The disadvantage is that we lot of unnecessary work by loading the same batch of noises multiple times. Finally, if compute batch of noises and evaluate the classifier for every test-set point with this noise before sampling a new batch, we get to average time 9.87s If we compute noises for every image separately, the per image time is 31.70 0.15. The denotes standard deviation of time per image. Thus, is not applicable for the second to last last case. The reported times are from experimental setup 2 with 0.12, A (ResNetl 10). For these experiments, to the one in Algorithm] 2 It takes minutes to compute the breaking points with SymPy library using exact arithmetic evaluated with sufficient precision (on single core). Here, we assumed that torch. randi nt. produces i.i.d. samples.
the experiment
GPU Tesla V100. For CIFAR1O, The (standard)
used (vectorized) procedure analogical
For ImageNet, used the model from Table with 0.5, k (ResNet50). We used batch size 100, 10 000 smoothed versions to evaluate the per-image times follow: The time of the standard method 8.65 0.07s, the time of the reloading reuse 12.36 0.07s. The time when sample noise and evaluate every image on that noise is 8.67s. New noises for every image yields 129 + 1.29s. The time to compute breaking points about minutes (again, single core).
12

---

Published as a conference paper at ICLR 2023
Table 3: Certified radii for a model F smoothed with (0, I² on CIFARIO test set. Evaluated on 500 images from the test set highlighting the differences. The model is ResNet-110 taken from (Salman et al. 2019p. See Appendix A for the details.
Sound smoothing of F ge via Algorithm 2 for k
certified radius
0.1
0.25
0.5
0.75
1.25
1.5
2.0
0.12
0.714
0.678
0.630
0.000
0.000
0.000
0.000
0.000
0.000
0 0.25
0.660
0.636
0.590
0.526
0.444
0.000
0.000
0.000
0.000
0.50
0.554
0.538
0,500
0.442
0.386
0.340
0.284
0.204
0.000
0 1
0.440
0.428
0.402
0.368
0.332
0.292
0.248
0.202
0.160
Standard smoothing of F via Algorithm
!
certified radius
0.1
0.25
0.5
0.75
1.25
1.5
2.0
0.12
0.712
0.678
0.630
0.000
0.000
0.000
0,000
0,000
0.000
0.25
0.664
0.638
0.592
0.522
0.444
0.000
0.000
0.000
0.000
0.50
0.556
0.540
0,500
0.440
0.386
0.338
0.284
0.194
0.000
1
0.440
0,428
0.402
0.366
0.330
0.290
0.248
0.204
0.164
Table 4: Certified radii for a model /' smoothed with (O, 02 on CIFARIO test set. Evaluated on 500 images from the test set highlighting the differences. The model is ResNet-110 taken from (Salman et al. 2019). See Appendix A for the details.
Sound smoothing of F ge via Algorithm
2 for k
certified radius
0.1
0.25
0.5
0.75
1
1,25
1.5
2.0
0.12
0.560
0.544
0.522
0.000
0.000
0.000
0.000
0.000
0.000
0.25
0.534
0.514
0.492
0.450
0.408
0.000
0.000
0.000
0.000
0.50
0.466
0.458
0.440
0.414
0.378
0.342
0.306
0.258
0.000
a
0.370
0.364
0.342
0.320
0.298
0.276
0.252
0.226
0.166
Standard smoothing of FF via Algorithm
certified radius
0.25
0.5
0.75
1.25
1.5
2.0
0.12
0.558
0.544
0.522
0.000
0.000
0.000
0.000
0.000
0.000
0.25
0.534
0.514
0.492
0.450
0.410
0.000
0.000
0.000
0.000
0.50
0.464
0.458
0.440
0.414
0.380
0.340
0.308
0.264
0.000
1
0.372
0.364
0.344
0.318
0.298
0.274
0.250
0.222
0.168
13

---

Published as a conference paper at ICLR 2023
Table 5: Certified radii for model I' smoothed with (V on Imagenet test set. Evaluated on 1000 images from the test set highlighting the differences. The modelis ResNet--0 taken from (Salman
al 2019). See Appendix A for the details.
Sound smoothing of Po gh via Algorithm 2 for
12
certified radius
0.1
0.25
0.5
0.75
1.25
1.5
2.0
0 0.25
0.661
0.636
0.614
0.559
0.498
0.000
0.000
0.000
0.000
0.50
0.597
0.586
0.549
0.509
0.460
0.428
0.383
0.330
0.000
0 1
0.447
0.438
0.424
0.390
0.365
0.344
0.319
0.299
0.238
Standard smoothing of F via Algorithm
!
certified radius
0.25
0.5
0.75
1.25
1.5
2.0
0 0.25
0.660
0.635
0.614
0.559
0.497
0.000
0.000
0.000
0.000
0.50
0.598
0.584
0.548
0.507
0.459
0.429
0.385
0.323
0.000
1
0.447
0.439
0.424
0.390
0.365
0.344
0.320
0.297
0.240
Table 6: Certified radii for model F smoothed with (N0, o2 on Imagenet test set. Evaluated on 1000 images from the test set highlighting the differences. The model is ResNet-50 taken from Salman et al. 2019). See Appendix A for the details.
Sound smoothing of o gu via Algorithm
2 for k= 12
certified radius
0.1
0.25
0.5
0.75
1
1.25
1.5
2.0
0.25
0.672
0.642
0.592
0.505
0.393
0.000
0.000
0.000
0.000
0.50
0.580
0.566
0.534
0.484
0.425
0.378
0.331
0.268
0.000
0 1
0.448
0.439
0.416
0.379
0.348
0.327
0.299
0.266
0.210
Standard smoothing of F via Algorithml
!
certified radius
0.25
0.5
0.75
1.25
1.5
2.0
0 0.25
0.672
0.641
0.593
0.503
0.389
0.000
0.000
0.000
0.000
0.50
0.581
0,564
0.534
0.486
0.423
0.377
0.337
0.270
0.000
0.449
0.440
0.418
0.380
0.349
0.324
0.299
0.268
0.211
14

---

Published as a conference paper at ICLR 2023
B PROOF OF PROPOSITION5.1
Let us inspect the probability of observing some a E {-k + 1....,k 254). In that case
(x-w)²
PI-N%(r,02) [t a| fa-D.s
du. For the other distribution it holds that t' 20d
V2no"
2, du and the change of the variable - concludes the proof of this case. The other two cases are analogical.
and P. Po-N)( ||t a =1 Sa-x-0.5
V250²
C PLOATING-POINT NUMBERS
In this appendix, introduce the floating-point representations and arithmetic according standard IEEE-754 (iee) 2008). For the sake of clarity, in this section, we use 8-bit floating-poin number representation instead of the usual 16, 32, 64 bits, respectively for half, single, and double precision. This appendix is self-contained and repeats the contains also (in a more detailed way) the content presented in the main paper.
Floating-point numbers are represented in memory using three different sequences of bits. The split 1/3/4 for the 8-bit example, 1/5/10 for half- salf-precision, 1/8/23 for standard single precision, and 1/11/52 for double precision. The modern GPUs use most often seggeccccciioon floating point numbers. We will represent the binary numbers as binary strings of 8 numbers and start with an example translating binary floating-poin point representation to the standard decimal one.
Example C.1. Consider the binary number 1110 1010. The first bit is the sign bit. The number is negative iff the bit is set to 1. In our example, the bit is 1; thus, the number is negative. The next 3 bits (110) determine the exponent. It is the integer value of this encoding minus 3, thus, in our example, the exponent is 6 6-3 3 = 3. The subtraction of 3 enables that The last sequence is called mantissa and encodes the number after the decimal point. There is also an implicit (not written) before it. This is so-called normalized form. Thus, the encoded value of the mantissa is 1. 1.1010 in binary representation, which 1 00.55 0- 0.25 1- 0.125 0- 0.00625 1.625 in base 10. The represented number thus 11625 2 13 in base 10.
represent exponents -3, -2....,
C.1 SUBNORMAL NUMBERS, NANS AND INFS
We note that the introduced foating-poiin representation is not able represent 0 and the smallest representable positive number is 0000 0000 which is 0.125 in base 10. To represent even smaller numbers, there are so-called subnormal numbers. That is, whenever the exponent consists only of zeros, there is no implicit 1 in the mantissa, but the exponent is higher by one. That is, the exponents represented by bits 000 and 001 both correspond -2. If our 8 bit toy arithmetic also used subnormal numbers, then 0000 0000 would be O and 000 0001 would be (0- 1 + 0- 0.5 + 0 0-.25 + 0 0.125 + + 0.0625)- 2-2 0.015625. We note that there is positive and a negative zero (and also inf).
Similarly, floating-pote point numbers whose exponents consist only of ones are special. If additionally the mantissa is zeros, then it represents inf and if the mantissa contains non-zero bit, then represents not-a-number (NaN) and the set bits correspond to error messages.
C.2 OPERATIONS WITH FLOATING-POINT NUMBERS
To distinguish the mathematical operations (infinite precision) from the computer arithmetic ones, we will use @, θ instead of +, - to represent Hoating-poine operations. When writing, e-g. @ 7 12, mean that the floating-pon point representation of 5 added to the boating-point representation of 7 results in a floating-pott point 12. We also note that a @ -b = a e
The addition (or analogically subtraction) of two floating-poit -aaiin numbers is performed in three steps. First, the number with the lower exponent is transformed to the higher exponent; then the addition is performed (we assume with infinite precision), and then the result is rounded to fit into the floating- point representation. The standard allows for several rounding schemes, but the common one is to round to the closest number breaking the ties by rounding the number with mantissa ending with 0.
15

---

Published as a conference paper at ICLR 2023
For the sake of completeness, also mention the multiplication of floating point numbers. The mul- tiplication is done a way that exponents are added; the mantissas are multiplied and consequently normalized. We will not use (nontrivial) doating-poin multiplication in constructions.
Let us show an example of the Hoating-poinn addition.
Example C.2. Consider the addition of binary numbers, 1110 1010, and 0101 0011. The first one we already decoded as 1.11010 2 and the other one is 1.0011 22; both in base
1110 1010 e 0101 0011 - 11.1010 2 1.0011 2 -1.1011 2 0.10011 x 2",
-1.000001 x 2 1..000 2 1110 0000.
In base 10, we would have 13 4.75 -8 due to the loss of the least significant bits. This happened even though the exponents were different by the smallest possible Snfference.Considee further 6.5 @ 4.75 = 11; Here, the loss of precision appeared even with equal exponents.
Unsurprisingly, also holds that 6.5 @ 4.5 11. Therefore, the addition to 6.5 is not injective and, as consequence, is not surjective. Connecting this randomized smoothing, know that there numbers which cannot be smoothed from 6.5 as the following example shows.
Example C.3. When observing 2.125, could not arise as 6.5 @ for any a. Indeed, 6.5 -4.5 2, while 6.5 -4.25 2.25. The representations are: 6.5 ~ 0101 1010, 2.125 0100 0001, -4.25 1101 0001 and -4.5 ~ 1101 0010. Here -4.25 is the smallest number bigger than -4.5. Note again that the exponents of 6.5 and 2.25 differ only by the smallest possible difference.
Another consequence is that floating-point addition is not associative. That is, the following identity does not always hold (a @ b)
(b@c).
Example C.4. Consider the numbers a 2.375 0100 0011, b= 3.75 0100 1110, and 3.25 ~ 0100 1010. Then a @ = 0101 1000 and (a @ b) @ = 9 0110 0010. On the other hand, e 0101 1100 and (b c) 9.5 0110 0011; thus, the triple a, b, serves counterexample for associativity of e.
D PROOF OF PROPOSITION
Proposition D.1. There is classifier with certified robust accuracy 100% on the first 1000 CIFARIO test set images c [0, ........ 3077 (where we define class 0 to include classes 0, 2,3, 4 of CIFARIO and class 1 contains the other classes) with fz-robust radius of 3 and failure probability 0.001 using randomized smoothing certificates, while for every point X there an adversarial example a' with x x' 2'1211.
Proof. We take X, S X to be the set of all images from X with class 0 and X1 X Xg. Then we construct hard classifier
M(x)= =11
127 if Hx, (+) or (x) 0 and æ 255
otherwise,
where we use HA from 4 Experimentally, we conclude that for the smoothed classifier of M with
a= = 1, randomized smoothing certifies robust radius 3 in &g norm for every point x of the test set. At 240 -I
the same time, the perturbation p (a 255 255 .... ) IR3072 where is 1 when looking for
adversarial perturbation of class 0 and otherwise are universal adversarial perturbations. holds
for x e X that M (x) is correct; (x) ()= .7 (x p). and also |p|, S
E CERTIFICATION OF REAL- VALUED INPUTS OR DIFFERENT QUANTIZATIONS
Here we shall discuss the adaptation of the method to real-valued inputs, and also to other quantization levels.
16

---

Published as a conference paper at ICLR 2023
E. GENERALIZATION TO OTHER QUANTIZATION LEVELS
We described the method assuming 256 quantization levels and later we rounded the input to exact the same levels. This choice was arbitrary. The motivation was that the more fine-grained the levels are, the more similar the less changes will the rounding introduce. However, when choosing the quantization level after rounding, one should have in mind that the efficiency of the method relies on Proposition 5.1 It is easy to see that in general, we need to compute approximately lcm Pout) integrals to be able to perform sampling, when qin- Gout are the respective inverse distances between neighbouring quantization levels of input, and after rounding. E.g., If we decided round the input on scale 1/256 instead of 1 1/255, we would need to compute 256 times more integrals than when the quantization with the current rounding.
E.2 GENERALIZATION TO VALUED INPUTS
Here we propose two potential generalizations of the method real-valued inputs. The first produces maximal (in the sense of NP lemma) certificates at the cost of slow execution. The other brings no slow down, but the certificates will not be maximal.
As discussed in the previous subsection, Proposition 5.1 is crucial for the efficiency. However, with the real-valued inputs. it cannot be taken advantage of, because the inputs will (in general) be arbitrarily distant from O. Thus, we would need to compute the samples from N (z, (2, La independently for every input. While it is not fundamental problem and we, in principle, can do so, it will become slow for high-dimensional images. To soften this problem, we can decide to have small number of quantization levels (e.g.. 2) so we would need to compute just a single integral per input dimension. Using 2 quantization levels was already considered in Levine and Feizi 202T and it yields the state-of-the ooett--rt-t-tt & robustness.
Another possible solution is to round the input before the certification. Let R6 be the input point, we chose a quantization grid and its closest element to x is x'. Then if we certify robust radius around x', it implies that the robust radius centered at x: is at least r |x: x'|l. For instance, considering CIFAR 10 dimension d 3072 and the distance between quantization points is 1/1000,
then || - 12 s (3072 * 1/2000²) 1/2 s 0.055. At the same time, we know that the certified radius at x' would be at-most r + - æ'|1 Thus, the error is controlled and not significant. We can use more fine- gea-irainnd quantization to make this error even smaller.
Finally, we note that the main focus of this paper is on quantized input as used in image classification. We expect that there are more sophisticated solutions this problem e.g., by combining both proposed variants with rejection sampling. We leave this to future work.
F GETTING A-ROUND GUARANTEES: FLOATING-POINT ATTACKS ON CERTIFIED ROBUSTNESS
In this appendix we discuss the floating-point attacks on randomized smoothing certificates of Di et al. (2022). We could not reproduce the result which could be due to the following problems:
The certificates of randomized smoothing are w.r.t. the smoothed classifier which is impossible evaluate and approximate it by random sampling. Thus, if we certify robust radius r at point x for classifier f, then if some v1, |x [x-xx] | <= r should be considered as an adversarial example (with high probability), we should also ensure that f(x,) = f()) with high probability. That is, from the certification procedure we know fxx) with high probability, but to know f(x1 with high probability, one has determine confidence intervals e.g. using Clopper-Pearson or Hoeffding's inequality. However, in the paper, on bottom of page 13, there written: Given an instance x, the smoothed classifier g runs the base classifier f on M noise corrupted instances of x, and returns the top class kA that has been predicted by f. This suggests that only majority vote is performed; but to claim that one has found with high probability an adversarial samples not only the majority vote has be wrong but there needs significant gap between wrong and correct
17

---

Published as a conference paper at ICLR 2023
class. Otherwise the result might just be bad luck due to random sampling and not indicate the existence of an adversarial sample.
During the attack, they iteratively "refine" the adversarial perturbation. Thus, they evaluate the smoothed classifier multiple times. Since the outputs probabilistic, when tries enough candidates, one should in principle (incorrectly) find a "high probability" adversarial example just because will be "lucky" with the randomness. This seems be taken into account in their method.
If their method is indeed a successful attack on randomized smoothing in floating point arithmetic, then this just emphasizes the need for fix, which is exactly what we propose in this paper and overcomes the possibility of such an attack.
G NEURAL NETWORKS
CERTIFIED ROBUSTNESS FOR QUANTIZED
Here we describe why the technique of Lin et al. (2021) for sampling from the discrete normal distribution and the consequent certification is not sufficient for our purposes.
The definition of the discrete normal distribution from Lin et al. (2021) (coinciding with the one
in Canonne et al. (2020)) is as follows:
(a-m)² 20
I (H. al Ze
where Z is appropriate normalization constant and the distribution is supported the set of integers. For the certification, similarly to the standard smoothing, first, the lower bound on the probability of the correct class for the smoothed classifier is estimated. Then, the robust radius is computed as ob N1 (p). where 2y is the inverse CDF of discrete Gaussian. This can be seen at the very bottom of the second column on page Lin et al. (202T). Note. in Algorithm 1 Lf et al.] (2021) there is written only 4- which according to the neighbouring discussions (and according to Thm 3.2 there) corresponds to N, This certified radius is clearly not exact, because the possible certified radii can only be multiples of the quantization levels because the smoothing distribution is discrete. For a I, the possible robust radii are 0, 1, ..... while the actual robust radius may clearly be non-integral which makes sense even when considering quantized inputs; e.g., consider the perturbation (1, 1,0,0 0, .... which has distance /2. Therefore, the smoothing as described in Lin et al. (2021) is restricted to certify only integer radii which is a significant restriction.
not able to verify the correctness of the method proposed in Lin et al. 202 In the proof of Theorem 3.1, there is: "Notice that that p., = P[X E SA). where S - [2: (2 x, s 1 W (P(,)) ))" Where ph is the lower bounded probability of the target class. However, since the smoothing distribution is discrete, the function T is piecewise constant, therefore there probabilities P1 P2 with 25 (P1)= 4 (p2), thus they will both generate the same set SA. but using the stated fact in the proof, would yield p1 [ SA] = P2. which absurd. Since the (incorrect) fact (v P[X e SA), where SA (2: (= (=-,, 8) s a [10| &N (r²,)) )))i is given without a proof, we cannot rely on the correctness of the method. Even assuming the correctness of the method, the produced certificates cannot be, as discussed above, exact and are only lower-bounds on the actual robust radius certifiable by randomized smoothing.
However,
())))))
H DISCUSSION ON PRESENTED MALICIOUS EXAMPLES
To reproduce the malicious examples from Section 4 it is important to carry every computation in the same precision. We tested it for both, single and couble-precision, it likely holds also for the half-precision. If some calculations are done in single, and some in double precision, then the claimed results will probably not hold. Specially, some calculation is performed
the single precision (e.g., transforming images from (0, 1, 1...,. 255) to {0, 1/255...... 1)), casting it to double precision afterwards not sufficient because the low mantissa bits are already lost. Although the codes are very simple, enclose some of the snippets in the supplementary materials. Proposition 5.T is verified
18

---

Published as a conference paper at ICLR 2023
by C++ program. We believe that for the demonstration it is sufficient to only 100 noises per sample. With 100 000 samples, it is sufficient to observe 99 900 successes to claim robust radius with probability 99.9%, and 50 500 successes to claim with probability 99.9% that the result is class However, the runtime about one day on a 64 core machine.
I HOEFFDING'S S BOUND
Proposition L11 (Hoeffding's s inequality). Let XI... Xn be random variables with 12 E and X2 s 1. Then it holds that
X:] =
TP
Σ F=
Xz)
-u22
se-2in
n
for any t 2 0.
We rewrite the incquality as
(
P
1 n p
S 21'n
Now the Ihs stands for the probability that when we subtract from the average, will still be bigger than the mean. This is the failure case of randomized smoothing that we want to allow only with probability 0.001. Thus, we want to compute how much do we subtract from the average.
2P a
2tn n In(a)
82 In(a)
-2n
In(
1
-2n
PSEUDO RANDOM NUMBERS
Here discuss the issues regarding the random number generators. In reality, don't have true random number generators, we only have pseudo-random number generators. In order to estimate with probabilistic guarantees, we need the actual random numbers. Otherwise, the probabilistic statement does not make sense (apart from trivial cases). Thus, reasonable alternative is to require that no statistical test would distinguish in polynomial time between the generated pseudo-random numbers and the actual random numbers with non-negligibly better probability than chance. This property is guaranteed by so-called cryptographically secure random number generators Yao 1982).
the quantity f(x) (E.-A((,
K ALGORITTS
Here we compare actual algorithms of the standard randomised smoothing in Algorithm T and of the proposed method in Algorithm The differences in the methods of the same
highlighted by colors. The algorithms assume input to be in {0, 1/255, 1). We emphasize that our method simple extension (differences highlighted) of the standard randomized smoothing, where the two additional procedures in Algorithm 2 can be evaluated just once before the certification; thus, they do slow down the method, neither decreases the accuracy.
19

---

Published as a conference paper at ICLR 2023
Algorithm Randomized smoothing certification of Cohen al. 2019
I: procedure SAMPLEUNDERNOISS((, N1,0))
2: counts [0,0]
3: for 1, do
4:
6 < N(0,0²1)
5:
x' x
6:
if f=') 0.5 then counts[[]] + counts[]] 1
7:
8:
else
9:
counts[0] + counts[0]+
10:
return counts
11:
procedure CERTIFY(F, O,E, no, a.
12:
counts0 + SLMMPELUNDERNOSSS((....... (o,
13:
ča top index in count
14:
countss <- SSAMPPLAUUDAANNNNORRR........
15:
РΛ LOWFERCNFFBONND( (CA (:)
16:
if p then
return prediction è and radius aΦ-1(p)
18:
else
return ABSTAIN
20

---

Published as a conference paper at ICLR 2023
Algorithm 2 Sound randomized smoothing certification of a
1: procedure PRECOMPUTE ARRAY OF BREAKING POINTS(K. o²) D This function is evaluated
only once
2: arr [0. [
Array of 255 (k 1) 1 zeros
3: for -255k 255, 255k + 254 do
4: arr[255k 255 i] - [261 - (2+0.5)/255
de
V2
5: arr[2-255) 255 (As 1)] + 264
6:
return arr
7: procedure (0,0000 This function is evaluated only on the first call with given arguments
and the result is memorized. The relevant arguments
8: arr + Precomputed array of breaking points for N (0, x²)
9: E [0.
Array of d zeros
10:
for i < 1,d do
U(0, 264-1
12:
for j + -255(k 1), 255 do
13:
if' d'arrjj+ 255k] = then
14:
return Fail Failure
15:
else if arr[j k] then
16:
j/255
17:
Break
18:
return
procedure SAMPLBUUNDERNOOSFRR,.....
20:
counts [0,0]
21:
for 1,
22:
5- "'-
23:
+ then
24:
x' + maxa(-k.
+e)
25:
if f(x') > 0.5 then
26:
counts[1] count s [1]
27:
else
count s[0] count [(0]+
29:
return counts
30:
procedure CERTIFY(S a,,,, Ro, a, k) k)
counts0 SAMPLEUUNDERNOISS(S........ n,, ĆA top index in count
32:
counts SAMPLEUNDERNNOSH((.,,
34:
+ LOWEECONFBOUND(Coor
35:
if p then
36:
return prediction è and radius o
37:
else
38:
return ABSTAIN
21


Reviews:
[{"review_id": "YeZvhRoATW", "reviewer": "Reviewer_9zy2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper identifies a new floating point arithmetic-based problem with the randomized smoothing-based certification framework. The authors show that a point can have an erroneously big certificate while being vulnerable to attacks. The paper proposes two rounding-based alternatives to standard randomized smoothing to address the floating point error problems. The authors also show that the run time of the proposed methods, as well as the performance, is comparable to standard randomized smoothing.\n\n", "summary_of_the_review": "The paper points out an important problem that has gone unnoticed till now. The paper provides some good insights to solve this problem, but it is not fully clear how widespread it is in real-world networks. Finally, although it is an important problem that needs to be solved, I feel this might not be the right venue for this paper.", "strength_and_weaknesses": "Strengths\n- The paper closely analyzes the failure case for randomized smoothing certification under floating point errors. Provides a theoretical example where an image classifier might give false certificates because of numerical errors.\n- The proposed solution of using a discrete normal distribution is quite simple and elegant. The paper also provides an efficient way to sample from the distribution making the approach practical.\n\nWeakness\n- Although not stated explicitly, the general belief is the safety guarantees of different data points are independent of one another. The single sampling framework needs to give a union bound over all points to ensure there are not too many failure cases.\n- The paper does not show the vulnerability of real-world networks to floating point errors. Although the theory indicates that the networks might be vulnerable in the worst-case scenario, it is unclear how often these scenarios happen in real life.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Tn1WMJ2L6QP", "reviewer": "Reviewer_YCXh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper shows that randomized smoothing in floating point arithmetic is susceptible to adversarial attacks.", "summary_of_the_review": "I haven't seen many papers showing that floating point operations can be used to attack neural nets.", "strength_and_weaknesses": "* Strength\n\nThe paper shows that randomized smoothing in floating point arithmetic, which has not been an obvious attack angle.\n\n* Weakness \n\nThe proposed solution requires i.i.d. random numbers, which in practice we don't have. How would the paper modify the proposed solution if we know the random numbers are coming from a pseudo random generator?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OSMa0TxAY-", "reviewer": "Reviewer_rQaT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper explains that randomized smoothing is no longer sound in floating-point arithmetic. The paper then proposes a more solid approach to randomized smoothing when using floating-point precision that yields sound certificates for image classifiers. Since adversarial attacks are of critical importance for security-related applications, certified robustness is an important topic. These certificates need to hold in finite precision. ", "summary_of_the_review": "The paper presents an interesting issue with current robustness certificates and proposes a new approach to randomized smoothing when using floating-point precision.", "strength_and_weaknesses": "The paper identifies qualitatively new issues with randomized smoothing approach when using floating-point arithmetic. One expects potentially more issues when the numbers that appear in a classifier are large as this when floating point makes large absolute error in representing numbers. Since randomized rounding is used as a model for understanding the accumulation of errors in floating-point arithmetic when analyzing algorithms, I suspect that the issues that the paper is raising are quite minor in practice. \n\nThe sound randomized smoothing procedure in floating-point arithmetic results in negligible computational overheads in the image classification example, when compared to unsound certificates. \n\nA weakness of the paper is that the differences between the unsound practice and sound certificates are very small in the image classification example. Therefore, the manuscript has not demonstrated that caring about floating point arithmetic will make significant difference in practice.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NTur45yk_pR", "reviewer": "Reviewer_88Dn", "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 discusses how implementations of Randomized Smoothing (RS), an algorithm for certified robustness, can become unsound due to floating point arithmetic.\nRS performs multiple model evaluations under noise to determine a robust output. The finite precision of IEEE-754 floating point numbers causes the addition of noise not to work as mathematically expected. This leads to an overestimation of the robustness properties and unsound certificates. This is also showcased in a toy example.\nLastly, a solution based on discretized noise is proposed and evaluated.", "summary_of_the_review": "The paper showcases an important issue of the popular randomized smoothing algorithm.\nIt is well-written and also proposed a simple yet effective solution.\nThus my recommendation is acceptance. ", "strength_and_weaknesses": "**Strengths**:\n- The presented problem is significant and relevant as many papers in the robustness space rely on randomized smoothing.\n- The proposed solution seems to work well.\n- The paper is well-written and easy to follow.\n- The idea of reusing the same noise took me by surprise, but it does seem sound.\n\n\n**Weaknesses**:\n- No example on a real dataset/classifier.\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: poster