Efficient Certification for Probabilistic Robustness
Authors: Victor Rong
Alexandre Megretski
Luca Daniel
Tsui-Wei Weng
Venue: ICLR 2022 Submitted (2022)
Keywords: robustness
neural networks
deep learning

Abstract: Recent developments on the robustness of neural networks have primarily emphasized the notion of worst-case adversarial robustness in both verification and robust training. However, often looser constraints are needed and some margin of error is allowed. We instead consider the task of probabilistic robustness, which assumes the input follows a known probabilistic distribution and seeks to bound the probability of a given network failing against the input. We focus on developing an efficient robustness verification algorithm by extending a bound-propagation-based approach. Our proposed algorithm improves upon the robustness certificate of this algorithm by up to $8\times$ while with no additional computational cost. In addition, we perform a case study on incorporating the probabilistic robustness verification during training for the first time.

Under review as a conference paper at ICLR 2022
EFFICIENT CERTIFICATION FOR PROBABILISTIC RO- BUSTNESS
Anonymous authors Paper under double-blind review
A ABSTRACT
Recent developments on the robustness of neural networks have primarily emphasized the notion of worst-case adversarial robustness in both verif- cation and robust training. However, often looser constraints are needed and some margin of error is allowed. We instead consider the task of proba- bilistic robustness, which assumes the input follows a known probabilistic distribution and seeks to bound the probability of a given network failing against the input. We focus developing an efficient robustness verification algorithm by extending a nound-propagation.o algorithm improves upon the robust.nss certificate of this algorithm by up to 8x while with no additional computational cost. In addition, we perform case study on incorporating the probabilistic robust verification during training for the first time.
approach. Our proposed
1 INTRODUCTION
Neural networks have found great success in a wide variety of applications. For many of these applications, understanding when and how a neural network can fail is crucial. Szegedy et al. (2014) found that almost visually imperceptible perturbations of input images could drastically change the output of neural network. This realization set off large area of research, both in finding ways of attacking neural networks and developing defense and certification methods against said attacks. The most common setting which is considered is the morst-case robustness given an Ip norm. There have been a number of adversarial robustness certification methods which operate by finding provable 1p balls for which the output of the neural network is guaranteed to be constant. In other words, they find lower bounds on the minimum lp radius for which an adversarial attack exists. This is done by relaxing the network for bounded domain. Convex relaxations are typically used (Salman et al., 2019), although some works also consider quadratic program formulations (Raghmathan et al., 2018). Note that these are input-specific, they do not give guarantees about the entire input domain.
As opposed to the worst-case adversarial robustness, there is also great interest in the threat model where the primary concern is natural noise and corruption rather than a malicious adversary and thus the perturbations follow some probability distribution. Typical neural networks have been found to be vulnerable to common corruptions (Dodge & Karam, 2016; Geirhos al., 2018). We distinguish between these two notions of robustness as adversarial robustness and probabilistic robustness. We note that the terms such as corruption robustness, probability of violation, and adversarial density have also been used to refer to the general concept of probabilistic robustness. For the threat model of natural noise and corruption, there has not been as much work developed as for worst-case adversarial robustness. One of the very first probabilistic verification algorithms without imposing assumptions on the decision boundary is known as the PROVEN algorithm (Weng et al., 2019). In PROVEN, the authors derive probabilistic verification bounds based existing worst-case robustness verification such as Fast-Lin and CROWN (Weng et al., 2018; Zhang ct al., 2018).
Contributions. In this work, generalize the PROVEN algorithm proposed by Weng et al. (2019) to infinite support and greatly improve the tightness of the robustness certificate without additional computation cost. We name our algorithm I-PROVEN, as the proposed

---

Under review as a conference paper at ICLR 2022
algorithm is significantly improved version of PROVEN algorithm. The I-PROVEN algorithm can achieve significant improvements (2x-8x tighter) on the tightness of prob- abilistic robustness certificate for both MNIST and CIFAR-10 models without additional computation cost, and it also enables the certification of probability distributions with infinite support. Based an existing training pipeline with probabilistic robustness verification bounds, and we find mixed results for the training. We examine potential causes and implications.
proposed algorithm, we conduct case study augmenting
BACKGROUND AND RELATED WORKS
Notation. In order to describe related work in depth, we will lay out some notation. We define K-layer feed-forward ReLU neural network with no inputs and ng outputs f: 1R + R"* as
f(x) - (x) (x) = (f + b6+1)
(z) w
In other words, (x) denotes the vector of pre-activation values in the 7th layer. Generally, we work in the setting of image classifiers where a class is classified over a class if fe(z) fx() > To simplify notation, we assume that the neural networks f which we are working with have already had this margin function applied to it for some given e, i. In other words, we assume ng for convenience and we are interested in when f(x) 0.
2.1 ADVERSARIAL ROBUSTNESS VERIFICATION
Adversarial robustness verification asks, given a neural network f and a region R(e) in the input space, does there exist an x E R(e) such that f(x) I 0? To solve this problem, we can formulate it as an equivalent optimization problem: min f(x). If no such & such that f(x) < O exists, or equivalently, if the minimum f(x) is positive, then I is robust for region R((). Tf we can prove that is robust. on regions R(e) for all S then the robusiness certificate is g. The robustness certificate is a lower bound for the true minimum distortion et
The regions R(e) of general interest are Lp balls By( e) for given image or input zo-- This arises from the interpretation that an adversary is perturbing xy by at most e under a given Lp norm. Note that certification only informs robustness about a single image. As far as we know, it infeasible certify an entire dataset other than processing it image by image.
Convex relaxation for provable verification. These methods find a convex relaxation of a neural network in order to find provable certifications for its adversarial robustness. We will discuss these methods in detail as our method builds on them certain ways. There are number of works following these methods (Weng et al., 2018; Singh et al., 2018; Zhang et al., 2018; Singh et al., 2019b), and a general framework for them is described (Salman et al., 2019). We will use the setup used in CROWN (Zhang et al., 2018). In these methods, inequalities on pre-activation neurons are recursively computed
16) A +b6) < (6) < 1 x +b) ())
for each layer j. Note that these are element-wise bounds, (6) and u0) are scalar vectors, and AL") ((6) A() bb) are linear transformations of inputs x. These linear bounds are obtained by relaxing the non-linear activation functions to linear lower and upper bounds given that the inputs to the activation functions are within some interval found from the incqualities applied to earlier layers, (()), 200), (8)) i < j. These inequalities are propagated backwards through the network until the original input is reached. Under the typical 4, ball threat model, Hölder's inequality can give scalar bounds on these layers and the process can contimue to the final outputs. (Singh et al,, 2019a; Tjandraatmadja et al., 2020) have made progress on improving these bounds beyond the convex relaxation gap pointed out by Salman et al. (2019) by considering the activation functions multiple neurons jointly.
2

---

Under review as a conference paper at ICLR 2022
2.2 PROBABILISTIC ROBUSTNESS
For probabilistic robustness, we are considering a known probability distribution D R + [o, which the inputs we denote, in an abuse of notation, as (x, c). In other words, (x, c) is the distribution generated by sampling points evenly from the hyperrectangle [x] 6, 21 + x [x2 22
sampled from. We will focus additive iid uniform noise which
o) x ..... x [an - En e|-
Then the problem of probabilistic robustness verification is to verify that
PreND [f(x) > 2 21-Q
(1)
for some given failure probability Q.
We can define the robustness certificate similarly to how it was done for adversarial robustness. Weng et al. (2019) and Anderson & Sojoudi (2020) particularly consider the maximum e parameterizing D) for which the above holds and we also provide such results. This is found by binary searching over 6, as empirically we find that the robustness monotonic in e for the distributions we consider, but we note that there are no theoretical guarantees for this.
Sampling methods. Sampling gives well-established statistical guarantees which can be applied to the problem of probabilistic robustness. By using the neural network essentially as a black-box- Chernoff bounds can estimate the probability of the neural network giving the incorrect classification given distribution. This has the advantage of making no assumptions on the model or the distribution, but requires a large number of samples to achieve a high degree of accuracy and there is an inherent uncertainty present in the application of such algorithm. Baluta et al. (2021) notes for example, that proving that the probability is between - 10 0.1 0.5 10-#] with a confidence of 0.9 would require 5.5 10th samples. To overcome this, they propose a framework which reduces the nunber of samples necessary, although this is dependent on the true probability. Anderson & Sojoudi (2020) also provide method that can find upper bounds on the probability that a model is incorrect with small number of samples. Webb et al. (2018) uses clever sampling method that leverages the layered structure of common architectures. They require upwards of 10" samples but are able obtain precise estimations. Though they are unable to provide theoretical guarantees, they show that empirically, their estimations agree with naive Monte Carlo estimates with as many as 1000 samples.
2.3 TRAINING ADVERSARIALLY-ROBUS MODELS
Training methods for improving adversarial robustness have generally taken two paths. The first augments the data with adversarial attacks in order to strengthen model's resistance to such attacks (Madry et al., 2017). The second approach adds loss regularization terms that help the model learn robust fcatures of the data. Xiao et al. (2018) identifics weight sparsity and RcLU stability as important factors in a model's adversarial robustness and builds training framework which incorporates these. Other works use certification methods as regularization lerms in order to improve the certifiable robust of a model. Interval bound propagation (IBP) has found great success in this despite being a relatively loose certification method (Gowal et al., 2019). In particular, the efficiency of IBP has made it amenable to training. A number of other works have made progress in closing this efficiency gap (Zhang et al., 2019; Xu et al., 2020; Shi et al., 2021; Boopathy et al., 2021).
OUR MAIN RESULTS
In scction 3.1, we illustrate the idea of deriving tighter probabilistic robustness certificate and provide the details of our I-PROVEN algorithm. We remark on alternative setups in section 3.2. In section 3.3 we conduct a case study on including our proposed probabilistic verification bounds into standard training. All experimental results reported in section 4.
3

---

Under review as a conference paper at ICLR 2022
3.1 I-PROVEN: IMPROVING THE TIGHTNESS OF PROVEN ALGORITHM
In this subsection, we will show how we could build on top of the state-of-tho-art PROVEN algorithm (Weng et al., 2019) to derive lighter probabilistic robustness certificate in I- PROVEN. Using convex relaxation methods, one can find linear bounds with respect to the input such that,
k x + (K)
< f(x) < 1 x+ 6 Va E supp
(2)
PROVEN argues that by applying probabilistic bounds
Pr (K) [4 x + (K) 2 2 anD
(3)
we can conclude that f(x) 0 with probability at least q. Notably, probabilistic inequalities are only considered in the final layer. Thus, they are able to give a probabilistic robustness certification.
To extend this method, we must look into how these linear bounds AL. bz. Ay, by were obtained. This is done recursively: every layer's pre-activation neurons are bounded by linear bounds with respect to the input. Then, scalar bounds are obtained using Hölder's inequality on the linear bounds and the support of the input. These scalar bounds define intervals in the domain of each activation function for the next layer. This allows linear bounds to be calculated over the activation function and for the next layer to continue propagating linear bounds.
The key observation that these linear bounds in previous layers can also apply with some probability rather than strictly and that the failure probabilities accumulate linearly. Assume that we have some q' for which
2nD ( (1)
12
Then a simple union bound gives that the probability of f(x) 2 at least 1 1- 9 is simple scenario which can be extended to involve all layers of the network.
d. This
Theorem 1. In the convex-relaratio framework, for each scalor inequality i (1 S A + br or Au by), denote qs as the probability that this inequality violated with respect to the probability distribulion D which a is sampled from. Then the probability of the fonal output of the convez- relezatelazation algorithm holding for given D is 2- E.
Proof. The convex-relaxation framework operates by making series of inequalities which ultimately lead to the output layer. We can label these L1, Lz,,... Im- When we apply probabilistic bounds, these inequalitics may not be guaranteed. We will denote E, to be the event that Lj is correct. Even though there is the chance of failure, we will operate assuming that all inequalities were correct. If they are indeed all correct for some v, then we can conclude that /(x)= 2 ((K) for this particular x as expected. Then it suffices to find a lower bound on the probability of the intersection of the E5 's. We have
Pr [(()) 2 pK0]] z>D
Pr IND
n
Eg
Pr aDD
U
2
EP
Σ
Pr E3 RND
=1
Σ
9) (5)
as desired.
Now we will take advantage of this theorem. Assign every scalar inequality i (either A +b 2 I or A +b' S u) a failure probability qi which sum to Q altogether. We can invert the probabilistic inequalities to find scalars I and such that these hold with given failure probability qe In particular, say that functions 72 (a, b) and yu (a, b) are such that
(a b) < Pr lax + b>00000 0] v (a, IND
for any a, b. We want to choose I such that Pr(A + t < 4 S qs. Thus, it suffices to solve for I such that 7r (AL, be - = 1 li.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 I-PROVEN for Boo (I)
1: procedure PRINEQ(Z, e, Ar, by, Au, bu, 9)
2: Istrict + ALæ + by c|| A
3: Ustrictt + AUT + by + e|1A0|11
4: lprob + Aræ + br. e v 2 In _ |r.111
5: Uprob Avx + by + E v 1n 1
g ||Ar
6: return max(Istrict (prob). min (ustritt Mprob)
7: end procodure
8: procedure IPROVEN(1, Q)
9:
- Q/ x number of neurons)
10:
((1) (1)) + PRINEQ(I, W1.b,, W1,b1.9)
11:
for i in [2, KJ do
A 09 .48 by - GETLINEABBOUND(((1 (((") ( .b 4 6: (i:))
12:
(0, (() PRINEQ(I,,,A 1/,
13:
14:
end for
15: return ((m)
16: end procedure
For the uniform distribution Bx, such functions y and TO can be derived from Hoeffding's Incquality as seen in Corollary 3.2 of (Weng et al., 2019). Inverting them, we obtain
A by - e 2 22
||A2|12. qi
(6)
Performing the forward and backward bound propagation methods ultimately yields final scalar lower bound ((m), By theorem 1, we have that
Pr( [(n]] 1 Σ % =1
We choose a simple scheme in assigning the failure probabilities. We select some subset of layers and assign all inequalities pertaining these layers equal qi All other g/s are to 0. So
Q
if i
4i 2x number of neurons within layers S
a. 0 indicates using the strict bounds and only possible when D has bounded support, as with (xoar,)) e). In this case, the Hölder inequality for the Loo norm is used. Note that the original PROVEN algorithm is equivalent to only selecting the last layer.
We found that more complex assignment strategies such optimizing over a with sum equal to did not lend themselves to any significant improvements compared to this simple method, especially given their additional run-time cost. However, there few factors to keep in mind when choosing the subset of layers S. In the case uniform bounded noise, the non-zero qi are small, it is possible for the strict incqualities, which find
latrict AL + by A|IAbllı, Matrict = Aux by + cllAull
(8)
to give tighter intervals than the probabilistic inequalities.
The different weight norms also create some discrepancy in the effectiveness of the probabilistic bounds. In particular, although the matrices A in the above equations are not directly the network weights, we found that I-PROVEN performed worse models with sparse weights. To take these into account, we return the tightest intervals using either the strict or probabilistic bounds, alt hlthh do not update the q's to incorporate choice.
5

---

Under review as a conference paper at ICLR 2022
3.2 OTHER DISTRIBUTIONS AND CERTIFIERS
I-PROVEN can support distributions with infinite support. The only requirement which I-PROVEN has on the distribution D that we must have lower and upper bounds on Pry=n au + b> 0j for a, b E R. This may include distributions with infinile support. For example, for additive fid Gaussian noise with standard deviation 6, we can obtain
1 1= Ar + by - erf ((1 - 22.4 |ALll2
(9)
from basic facts about Gaussian distributions. Similar formulas can be found for Gaussian mixtures when such a distribution is known and relevant. Note that qi must be non-zero for all inequalities when dealing with distributions with infinite support, as strict alternatives no longer exist.
I-PROVEN can be used with any linear-relaxation--asse certifier with no addi- tional computational cost. As I-PROVEN only requires changing the evaluation of the scalar bounds, it has additional time complexity cost to whatever method it is being used with. It can be incorporated in any such linear-relxxation method. For a network with K layers and n neurons at cach layer, the entire method when used with CROWN is O(n" (Zhang et al., 2018), an additional factor of compared to a pass of the network.
3.3 PROBABILISTIC VERIFICATION BASED TRAINING
Our training method is simply a substitution of PROVEN into CROWN-IBP (Zhang al., 2019). It requires two forward passes. The first computes strict bounds on cach pre-activation neuron using IBP. The second performs linear bound propagations to compute linear bounds on the output. Then probabilistic bounds are applied to obtain the final scalar lower and upper bounds which are used in the loss function described in CROWN-IBP's original paper. Note that this effectively means that only the original PROVEN is applied in this training method.
EXPERIMENTS
4.1 IMPLEMENTATION DETAILS
We performed experiments on the MNIST and CIFAR-10 datasets (LeCun et al., 2010; Krizhevsky, 2009). For our verification experiments, used pretrained models provided in (Weng et al., 2018) and (Zhang et al., 2018) and the images from each dataset were scaled so that their values were in [-0.5, 0.5). For training experiments, we used the architectures described in (Gowal ct al., 2019) and the images in the dataset were scaled to be in [0, 1]. Our MNIST models were trained for 100 epochs with a batch size of 100 and with warm-up period for the first 5 epochs and a ramp-up period for the next 45. We followed the 3 and k schedule used in (Zhang al., 2019) for the PROVEN-IBP loss and we increase our from 0 to 4 x 10-1 during the ramp-up up period. We evaluate the validation set using e = 3 x 10- All code was written in Python with the use of the PyTorch library (Paszke et al., 2019) and training was conducted on NVIDIA Tesla V100 GPU.
4.2 VERIFICATION RESULTS
We compare the original PROVEN bounds with our improved PROVEN on various MNIST and CIFAR-10 classifier in table 1. The classifier are k-layer MI.Ps with neurons in each layer, denoted as k x [n). In I-PROVEN, & are all non-zero and equal across all layers. It achieves much better performance than the original PROVEN (Weng et al., 2019) with 600% increase for 99.99% probabilistic robustness. Note that Q = 0 is simply the adversarial robustness certificate.
I-PROVEN's improvement over PROVEN can be observed from intermediate layers' bounds. In table 2, the average interval gap of the neurons in layer is tabulated. The model in particular a 4-layer MNIST MLP (layer 0 indicates the input, which is why the interval length is simply 2c). PROVEN and I-PROVEN are each evaluated on 10 images for various

---

Under review as a conference paper at ICLR 2022
Table 1: I-PROVEN versus original PROVEN for probabilistic robustness certificate on MNIST and CIFAR-10 models. I-PROVEN achieve significant improvements (1.6x-8.5x)
on the tightness of probabilistic robustness certificate without additional computation cost.
Q
0
0.0001
0.01
0.05
0.25
0.5
MNIST
PROVEN
0.0247
0.0325
0.0333
0.0337
0.0342
0.0345
2 x [1024]
I-PROVEN
0.0247
0.0864
0.1013
0.1087
0.1181
0.1229
% improvement
0
166
204
223
245
256
MNIST [1024]
PROVEN 0.0194
0.0223
0.0226
0.0227
0.0228
0.0229
I-PROVEN
0.0194
0.0640
0.0745
0.0797
0.0860
0.0893
% improvement
187
230
251
277
289
MNIST [1024]
PROVEN 0.0079
0.0083
0.0084
0.0084
0.0084
0.0084
I-PROVEN
0.0079
0.0299
0.0347
0.0370
0.0398
0.0413
% improvement
259
315
342
374
391
CIFAR-10 5 [2048]
PROVEN
0.0017
0.0018
0.0018
0.0018
0.0018
0.0018
I-PROVEN
0.0017
0.0123
0.0141
0.0150
0.0161
0.0166
% improvement
574
673
720
776
804
CIFAR-10 7 x [1024]
PROVEN
0.0018
0.0018
0.0018
0.0018
0.0018
0.0018
I-PROVEN
0.0018
0.0128
0.0147
0.0157
0.0168
0.0174
% improvement
606
716
764
826
857
Improved on Layer Class (Unitorm Noise
Improved
Leyer
Usooroppcc Gaussian Noise)
IMMOVEN WINVIN
0.1.
Ont rallvx
0.00
0.13
stadded
0.05
0.05
0.04
0.02
0.7
0.
6.1
0.6
0.8
0.0
02
CA
0.6
ca
Total to lare probabiltt O
Total ta protacditt
Figure 1: I-PROVEN verification results for small 3-layer MNIST model considering the uniform distribution Bod (x, c) and isotropic Gaussian distribution N(x, c), respectively. Error bars are based on 3x stdev.
Q. The scalar intervals I, u which give bounds on each neuron in both methods are averaged within each layer. The smaller the interval size (that is, the tighter the interval), the better. I-PROVEN's intervals are noticeably tighter from the first layer onwards as it invests portion of the total failure probability Q tighten these earlier inequalities. This does mean PROVEN's final inequalities are sharper than I-PROVEN's, which we can notice by observing the ratio of interval widths between Layer and Layer 4. For 6 = 0.001, = 0.1 for example, PROVEN goes from 0.045 to 0.564, 12.5x increase, while I-PROVEN goes from 0.09 to 0.203, a 22.5x increase. However, the improvements I-PROVEN makes in the carlier layers means it still ends up with tighter final bounds than PROVEN.
Note that we can our method is also able to handle additive Gaussian noise with only small changes to probabilistic inequalities. Notably, we do not need to truncate the Gaussian distribution as (Weng et al., 2019) did. We plot our results for both additive uniform noise and additive Gaussian noise in fig. 1.

---

Under review as a conference paper at ICLR 2022
Table Average interval lengths per layer
Layer 0
Layer
Layer 2
Layer 3
Layer 4
PROVEN
0.002
0.049
0.043
0.045
0.564
c = 0.001, Q 0.01
IPROVEN
0.002
0.011
0.009
0.009
0.203
PROVEN 0.010
0.247
0.324
0.522
7.478
< 0.005, Q 0.01
I-PROVEN
0.010
0.054
0.052
0.055
1.146
PROVEN 0.002
0.049
0.043
0.045
0.588
0.001, Q 0.0001
I-ROVEN
0.002
0.013
0.011
0.011
0.237
4.3 COMPARISON TO OTHER METHODS
In the carlier scction, compared I-PROVEN to PROVEN in terms of their robustness certificates. Now, we will show comparisons to IBP and a simple Monte Carlo approach based on (Anderson & Sojoudi, 2020). IBP does not generally perform well for arbitrary networks, 80 we use IBP-trained models in our experiment. In particular, we trained three CIFAR-10 CNN models A, B, and C. Model A was trained with standard loss, Model B was trained with an IBP loss term with ramping up to 2.2/255, and Model C was trained with an IBP loss term with e ramping up to 8.8 255. We use two different e, 2/255 and 8/255, for each model and cortifier. Q is fixed at 1%. We apply these certifiers on 1000 images from the validation datasot.
For the Monte Carlo approach, we take Tin 1/uu// samples from the uniform (x c) distri- bution where u == 0.0001 and T = 100, rounding 921 samples per image x. Then if every sample is correctly classified,
conclude that at least 1/T 99% of the distribution is correctly classified with false positive rate less than u. This Monte Carlo approach has a higher false negative rate than other sampling approaches, but we chose this one beecause it requires the lowest number of samples as far as we are aware.
Table 3: IBP, PROVEN, I-PROVEN, and the Monte Carlo method on a CIFAR-10 classifier. The entries indicate the portion of images which each certifier is unable to certify as robust (lower is better). Standard (error) denotes the portion of images which is classified incorrectly without any perturbations.
IBP
PROVEN I-PROVEN
Monte Carlo
Standard
Model A
1,000
0.996
0.808
0.429
0.409
6 2/255
Model B
0.715
0.643
0.598
0.511
0.483
Model C
0.621
0.604
0.613
0.576
0.552
Model A 1.000
1.000
1.000
0.491
0.409
c 8/255
Model B
0.993
0.978
0.952
0.588
0.483
Model 0.806
0.797
0.801
0.634
0.552
As the results in table 3 show, I-PROVEN performs better than IBP across all models, but this gap diminishes greatly in the two IBP-trained models, particularly for Model C. Similarly, we see the gap between PROVEN and I-PROVEN close and PROVEN even outperforms I-PROVEN in Model C. We see similar phenomena in the next sect ion, section 4.4, and provide an explanation.
Unsurprisingly, the Monte Carlo approach obtains better results than any of the relaxation- based approaches. Furthermore, in terms of timing, PROVEN/LPPROVIE IIPPROVE took 128-131s for all 1000 images per model, while the Monte Carlo approach consistently took around 4s. Evaluating the standard error and IBP error took under a second. However, the exact details on timing do depend somewhat the situation. In this experiment, I-PROVEN could not be batched at all as the memory used was too expensive, while Monte Carlo methods easily be batched.
8

---

Under review as a conference paper at ICLR 2022
4.4 A CASE STUDY ON TRAINING WITH I-PROVEN
We examine I-PROVEN's verification compared with IBP's models trained with IBP and PROVEN-IBP, respectively, on the small CNN from (Gowal et al., 2019) and the verification algorithms are considering (x, 0.3). Note that IBP is considering the model's adversarial robustness while I-PROVEN is considering the probabilistic robustness for Q = 1 x 10-2 (oquivalently, for 99% of the ball). We found that I-PROVEN docs not obtain significantly better results than IBP in cither case, mirroring our results on the table We conjecture that this is due to the weight sparsity induced by IBP's involvernent in the training for both pure IBP training and PROVEN-IBP, and that this sparsily is also present in the linear bounds for I-PROVEN. Weight sparsity is beneficial for adversarial robustness, particularly for the lo norm (Xiao et al., 2018). However, as far we are aware, there is no reason to expect weight sparsity to help a model's probabilistic robustness and as noted in section 3.1, I-PROVEN's probabílistic inequalities prefer more evenly distributed matrices.
models in
This weight sparsity also explains why PROVEN out perforrms I-PROVEN in Model C of table 3. When the model weights are sparse, the striet inequality is lighter than the probabilistic inequalities for very small qi and so I-PROVEN does not perform as well as usual by distributing Q evenly among the inequalities.
To test our hypothesis, we compared the last layer's linear lower bounds Ag between CNN trained in a standard manner, and a CNN trained with an IBP loss as in (Gowal et al,, 2019). We show this for an image from the validation set in fig. These A 'ss came from I-PROVEN applied with c 0.3, Q = 1 x 10-2 and the failure probabilities in the last two layers non-zero and equal. Each 28 x 28 grid corresponds to a logit in the output. The grid for 3 is all 0 as this is specifically considering the margin function between each class with the true class, 3. The absolute values of the matrix are scaled to fit in [0, 1]. Evidently, the values from the IBP model are far more sparse. Further examples are included in the appendix.
Figure 2: Ar from a CNN trained in a standard manner (top row), and CNN trained with IBP respectively (bottom roow).
CONCLUSION
In this paper, we present I-PROVEN, an algorithm that can efficiently verify the prob- abilistic robustness of a neural network. We show strong improvements compared to the prior method used against this problem: we remove the assumptions of bounded support and significantly improve the tightness of robustness certificate without any additional cost. Fur- thermore, we present a training framework for probabilistic robustness and demonstrate its shortcomings. By taking a closcr look at these results, we make steps towards understanding the relation between adversarial certified defense methods and our own.
REFERENCES
Brendon G Anderson and Somayeh Sojoudi. Certifying neural network robustness to random input noise from samples. Xiv preprint 2xXiu:2010.07592 2020. 3, 8
9

---

Under review as a conference paper at ICLR 2022
Teodora Baluta, Zheng Leong Chua, Kuldeep S Meel, and Prateck Saxena. Scalable quantitative verification for deep neural networks. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), pp. 312 323. IEEE, 2021. 3
Akhilan Boopathy, Bsui-Wei Weng, Sijia Liu, Pin-Ye Yu Chen, Gaoyuan Zhang, and Luca Daniel. Fast training of provably robust neural networks by singleprop. arXiv preprint arXiv:2102. 01208, 2021.
Samuel Dodge and Lina Karam. Understanding how image quality affects deep neural works. In 2016 eighth international conference on qualily of mullimediaa experience (QoMEX), pp. 1-6. IEEE, 2016. 1
Robert Geirhos, Carlos R Medina Temme, Jonas Rauber, Heiko Schütt, Matthias Bethge, and Felix A Wichmann. Generalisation in humans and deep neural networks. arxiv preprint Xix: 1atp:18888077000 08750, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. ICCV, 2019. 3, 6,
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. 6
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist. handwritten digit database. ATT Labs |Online/. Available: http://aannn....n../mm com/erdb /e/////dd/mmmim/eeeeeeee /misst, 2, 2010. 6
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial allacks. arXiv preprint XXx::170600066 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gre- gory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alch6-Buc, E. Fox, and R. Garnett (cds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL http::/ neurips ptt.rpp..cpppper//// 2015-pytorch-an-ie an- waw-imperatiee-steeeeeeeeee style- wtwll--ighh-eerorreeeeee tet---rrfommnneedeeee leam pdf.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang, Semidefinite relaxations for certifying robustness to adversarial examples. Xiv preprinl Xrx:::1811. 1.1.1111.011000 1001057, 2018
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. arXio preprint 19XX:0:1002.08222, 2019. 1,
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast certified robust training via better initialization and shorter warmup. arXie preprint arXiv:2103. 17268, 2021. 3
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T Vechev. Fast. and effective robustness certification. NeurIPS, 14):6, 2018. 2
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin Vechev. Beyond the single neuron convex barrier for neural network certification. Advances in Neural Information Processing Systems, 32:15 32:15098-1 -11099 2019a. 2
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, (POPI.):1-38) 30, 2019b. 2
10

---

Under review as a conference paper at ICLR 2022
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. ICLR, 2014. 1
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. arXic preprinl ar arxiv:2006. 14076, 2020.
Stefan Webb, Tom Rainforth, Yee Whye Tch, and M Pawan Kumar. A statistical approach to assessing neural network robustness. arXw preprint arXi::1811.07200, 2018.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 1, 2,
PMLR, 2018.
Lily Weng, Pin- Yu Chen, Lam Nguyen, Mark Squillante, Akhilan Boopathy, Ivan Oseledets, and Luca Daniel. Proven: Verifying robustness of neural networks with a probabilistic approach. In International Conference on Machine Learning, pp. 6727-6736. PMLR, 2019.
1, 3, 4, 6,
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint Xr:::18099 03008, 2018. 3,
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances Neurol Information Processing Systems, 33, 2020. 3
Huan Zhang, Tsui-Wel Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. arXiv preprint or 1811::111.0000 2018. 1, 6
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint orXiv:19066 06316, 2019. 3,
11


Reviews:
[{"review_id": "npolf_819oW", "reviewer": "Reviewer_sAmC", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths: An interesting problem, and improves over a previous method.\n\nWeaknesses: Overall, I found the empirical results unconvincing because they compared only to a single existing method (which was essentially a worse version of the current method). A simple baseline would be to use a stronger verification method (e.g. https://arxiv.org/pdf/2010.11645.pdf) with Q=0, which might actually outperform the proposed method even allowing for larger Q. There are also methods for related problems that should be able to handle relatively small Q (perhaps smaller than those considered in the current paper), such as this paper: https://arxiv.org/abs/2008.10581. It is difficult to contextualize the results without comparisons or at least discussions of these methods.", "summary_of_the_paper": "The paper considers the problem of probabilistic certification of robustness, that is, showing that the probability that a random point in some hyperrectangle changes the classification. It improves an existing method, PROVEN, to produce a new method I-PROVEN that it shows achieves better empirical results.", "summary_of_the_review": "Overall, the experiments are too narrow to support the main claims, so I recommend against accepting the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fxaM1-jjE0", "reviewer": "Reviewer_o2Ha", "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": "I think the pros of this paper are its clear exposition, goals, and methodology. In particular, the problem of adversarial examples is a serious one and continuing to work on expanding adversarial robustness guarantees to larger models is a avenue of research that can have clear impact. Further the goals and method of the paper are clearly explained. Finally, the proposed algorithm does have some key empirical advantages over the PROVEN algorithm, often gaining significantly better certified radii. \n\nThe cons of this paper lie in questions of its practicality compared not just to the PROVEN algorithm but to sampling based methods. For both PROVEN and I-PROVEN I find the use of convex relaxation a questionable choice due to several limitations. Firstly, these relaxations are known to introduce non-trivial over-approximations in the output. This is, of course, acceptable when performing rigorous safety verification, but given that the guarantees desired in this work are only statistical/probabilistic performing such relaxations (especially on large models on CIFAR) might introduce unnecessary over-approximation which leads to vastly conservative estimates in safety radius. I would be greatly surprised if this method was able to produce better radius than statistical methods given that they do not introduce such over approximations. Thus, there is an unexplored trade-off in a few directions that I think limits the impact of this paper. In particular, my questions are (1) how much more costly is this method (in terms of computational complexity and time) than the standard PROVEN algorithm? Just above subsection 3.3 they note its complexity relative to CROWN and I suspect that this complexity comparison will hold compared to PROVEN (that it is only a linear factor slower); however, it would be good to get an idea of how much slower this is in practice for their large CIFAR networks. (2) How much tighter are the statistical bounds? I expect them to be a great deal tighter, but also much more expensive to compute. It would be interesting to see what the trade off is here. Clearly I-PROVEN should theoretically fall in between PROVEN and sampling methods in terms of its tightness and its computational time, yet the authors do not explore this. \n\nMoreover, I think the extension to infinite support noise distributions is a rather weak extension. Clearly, PROVEN can also truncate a Gaussian and make the same erf function argument that is used here without any issue, so I do not see this as an extension unique to the proposed methodology. Of course, for statistical methods, infinite support is just fine, and so are poorly defined densities (i.e. distributions which can only be efficiently sampled from) which is something this method cannot support and this should be noted as a limitation. \n\nFinally, I think it would be interesting to compare the training method proposed here to randomized smoothing of classifiers and the MACER algorithm for training of robust randomized smoothing classifiers. \n\n\n\n", "summary_of_the_paper": "In this paper, the authors consider a notion of statistical/probabilistic robustness which does not require a model to be robust to all inputs in a specified set, only a certain, high-probability subset of these inputs. The authors rely on a bound propagation methodology to compute the the probability that a given input property is violated. In particular, the authors expand a known methodology (PROVEN) for computing probabilistic robustness and show that in many cases their methodology is better than that of PROVEN. ", "summary_of_the_review": "I think this is a good paper and is heading in the right direction, but needs a bit more work to realize its potential impact. In particular, I believe it needs a bit more discussion and evaluation in order to fully understand where this method falls in relation to previously proposed methods. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cL-jwwsnCDM", "reviewer": "Reviewer_5NRz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper seems to be an incremental improvement over PROVEN algorithm proposed by Weng et al.\nWhile I like the general approach of combining several linear relaxations with union bound, and thus improving the\nresults, I also have some concerns, which I list below.\n\n1) I am not sure that the threat model considered in this work is that relevant.\nI think authors should explain what would be some setting in which adversary is performing these probabilistic local perturbations.\nRight now, it seems to me that the setting is quite artificial, and there does not seem to be that much interest in the literature\nin solving this problem, except the work of Weng et al. Could authors motivate their problem setting better?\n\n2) In the background, authors mention some methods based on Chernoff bound, and argue that these methods need high number of samples to achieve a high degree of accuracy. Why are these methods, e.g. the one proposed by Baluta et al., not compared to in the experimental evaluation? Without this, I think it is not actually clear whether these methods do not scale.\n\n3) Could authors discuss limitations of their approach? Right now it seems that, as all of the convex relaxation based approaches, this approach does not scale to large networks, while e.g. Chernoff bound based approach is essentially independent of the architecture.\n\n4) Could authors discuss relationship between the proposed method and randomized smoothing [1, 2]? Could randomized smoothing be applied to the threat model of probabilistic robustness that authors consider in this work? Fundamental limitation of approaches based on convex relaxations is that they do not scale to large networks, and randomized smoothing has worked well for achieving provable (deterministic) local adversarial robustness even on large networks and datasets, so it would be interesting to know whether it can work in this setting as well. Especially given the fact that guarantees are already probabilistic, randomized smoothing might be better tool to solve this problem than convex relaxation based approaches.\n\nTypos:\n\n- \"Note that we can our method\"\n\n[1] Lecuyer, Mathias, et al. \"Certified robustness to adversarial examples with differential privacy.\" 2019 IEEE Symposium on Security and Privacy (SP). IEEE, 2019.\n\n[2] Cohen, Jeremy, Elan Rosenfeld, and Zico Kolter. \"Certified adversarial robustness via randomized smoothing.\" International Conference on Machine Learning. PMLR, 2019.\n", "summary_of_the_paper": "This work considers problem of local robustness where each input is perturbed according to some probability distribution (e.g. uniform distribution over the L-infinity ball). Proposed approach is based on extending an approach proposed by prior work which uses linear bounds to compute bounds on the output of the network. The key contribution is computing the probabilistic bounds for inner layers, and not only the final one as was done in prior work. Authors show that their approach improves over prior work on MNIST and CIFAR-10 datasets.\n", "summary_of_the_review": "I find this paper marginally below the acceptance bar because the problem setting is not that well motivated, and the approach itself is incremental over the prior work PROVEN.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MvL0fWkpPmr", "reviewer": "Reviewer_JweR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main result, Theorem 1, seems rather trivial. While it is good to highlight that one can consider a union over all layers, the contribution may not be significant enough for ICLR.\n\n***updates after author response***\n\nI am still feeling that, while the observation of union bound is cute, the overall technical contribution is below the bar (the union bound is the only new analysis). However I do encourage authors to further explore the power of the bound, likely among other things, to get a stronger algorithm.", "summary_of_the_paper": "see below", "summary_of_the_review": "see above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method to improve PROVEN, which gives a certification for probabilistic robustness. However, reviewers think the paper is below the acceptance bar due to unclear motivation and insufficient experiments. In particular, a clear use case of probabilistic robustness certification is crucial for the paper.
Decision: Reject