Expected Tight Bounds for Robust Deep Neural Network Training
Authors: Salman Alsubaihi
Adel Bibi
Modar Alfadly
Abdullah Hamdi
Bernard Ghanem
Venue:  (2020)
Keywords: network robustness
network verification
interval bound propagation

Abstract: Training Deep Neural Networks (DNNs) that are robust to norm bounded adversarial attacks remains an elusive problem. While verification based methods are generally too expensive to robustly train large networks, it was demonstrated by Gowal et. al. that bounded input intervals can be inexpensively propagated from layer to layer through deep networks. This interval bound propagation (IBP) approach led to high robustness and was the first to be employed on large networks. However, due to the very loose nature of the IBP bounds, particularly for large/deep networks, the required training procedure is complex and involved. In this paper, we closely examine the bounds of a block of layers composed of an affine layer, followed by a ReLU, followed by another affine layer. To this end, we propose \emph{expected} bounds (true bounds in expectation), which are provably tighter than IBP bounds in expectation. We then extend this result to deeper networks through blockwise propagation and show that we can achieve orders of magnitudes tighter bounds compared to IBP. Using these tight bounds, we demonstrate that a simple standard training procedure can achieve impressive robustness-accuracy trade-off across several architectures on both MNIST and CIFAR10.

Under review as a conference paper at ICLR 2020
EXPECTED TIGHT BOUNDS FOR ROBUST DEEP NEURAL NETWORK TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Training Deep Neural Networks (DNNs) that are robust to norm bounded adver- sarial attacks remains an elusive problem. While verification based methods are generally too expensive to robustly train large networks, it was demonstrated by Gowal al. (211)) that bounded input intervals can be inexpensively propagated from layer to layer through deep networks. This interval bound propagation (IBP) approach led to high robustness and was the first to be employed on large networks. However, due to the very loose nature of the IBP bounds, particularly for large/deep networks, the required training procedure is complex and involved. In this paper, we closely examine the bounds of a block of layers composed of an affine layer, followed by ReLU, followed by another affine layer. To this end, propose expected bounds (true bounds in expectation), which are provably tighter than IBP bounds in expectation. We then extend this result to deeper networks through blockwise propagation and show that we can achieve orders of magnitudes tighter bounds compared to IBP. Using these tight bounds, we demonstrate that simple standard training procedure can achieve impressive abusstess-acccuracy trade-off across several architectures on both MNIST and CIFAR10.
INTRODUCTION
Deep neural networks (DNNs) have demonstrated impressive performance in many fields of research with applications ranging from image classification (Krizhevsky et al.] 2012 He et al. (016)) and semantic segmentation (Long et al., 2015) to speech recognition (Hinton et al. 2012), just to name a few. Despite this success, DNNs are still susceptible to small imperceptible perturbations, which can lead to drastic performance degradation, especially in visual classification tasks. Such perturbations are best known and commonly referred to as adversarial atfacks. Early work showed that simple algorithms (e.g. maximizing the classification loss with respect to the input using a single optimization iteration (Goodfellow et al., 2014)) can easily construct such adversaries. Since then, a research surge has emerged to develop simple routines to construct adversarial examples consistently. For instance, Moosavii-Dezooo et al. (2016) proposed a simple algorithm, called DeepFool, which finds the smallest perturbation that fools a linearized version of the network. Interestingly, the work of Moosavi-Dezfooli et al. (2017) demonstrated that such adversaries can be both network and input agnostic, i.e. universal deterministic samples that fool wide range of DNNs across large number of input samples. More recently, it was shown that such adversaries can also be as simple as Gaussian noise (Bibi al., 2018). Knowing that DNNs are easily susceptible to simple attacks can hinder the public confidence in them, especially for real-world deployment, e.g. in self- delf-drivin cars and devices for the visually impaired.
Such a performance nuisance has prompted several active research directions, in particular, work towards network defense and verification. Network defense aims to train networks that are robust against adversarial attacks through means of robust training or procedures at inference time that dampen the effectiveness of the attack (Madry et al. 20188] Wong & Kolter 2018 Raghunathan et al. 2018: Alfadly et al., 2 On the other hand, verification aims to certify/verify for a given DNN that there exists no small perturbation of a given input that can change its output prediction (Katz al. 2017 Sankaranarayanan et al.. 2016 Weng al. (018a). However, there are also works at the intersection of both often referred to as robustness verification methods, which use verification methods to train robust networks. Such algorithms often try minimize the exact (or upper bound) of the worst adversarial loss over all possible bounded energy (often measured in Eo norm) perturbation around a given input.

---

Under review as a conference paper at ICLR 2020
Although verification methods prove to be effective in training robust networks (Wong & Kolter 2018), they are computationally expensive, thus limiting their applicability to only small, at best medium, sized networks. However. Gowaal et al. (2019) recently demonstrated that robustly training large networks is possible by leveraging the cheap-to-compute but very loose interval-based verifier, known as interval domain from Mirman et al. (018). In particular, they propagate the e-fxe norm bounded input centered at x E IR" f.e. XX - n. x cn through every layer in the network at a time. This interval bound propagation (IBP) is inexpensive and simple; however, it results in very loose output interval bounds, which in turn necessitates a complex and involved training procedure.
Closer to our work, there has been several prior arts that propose to perform verification differently. In particular, |Webb et al.] (2018) presents a statistical approach to assessing robustness of neural networks. As opposed to verification methods, which in many cases can be hard to scale, that provide probability of
binary measure of robustness per sample, they propose to frame verification violation instead. That is to say, they investigate the probability of failure over a violation rather than confirming that this probability is exactly zero. Moreover, (Weng et al.) (018b) propose CLEVER which estimates a lower bound to the minimum perturbation rather that finding the lower bounds exactly. In both works, the verification is tackled by, and closely related to our direction of work, probabilistically estimating the bounds.
In this paper, we are interested in improving the tightness of output interval bounds (referred to as bounds from now on). We do so by closely examining the bounds for a block of layers composed of an affine layer, followed by a ReLU nonlinearity, followed by another affine layer under coloc bounded input. In fact, we propose new expected bounds for this block of layers, which we prove to be not only supersets to the true bounds of this block in expectation but also very tight to the true bounds. Lastly, we show how to extend such a result to deeper networks through blockwise bound propagation leading to several orders of magnitude tighter bounds as compared to IBP.
Contributions. Our contributions are three-fold. (i) We propose new bounds for the block of layers composed of an affine layer, followed by a ReLU, followed by another affine layer. We prove that these bounds in expectation, under a distribution of network parameters, supersets to the true bounds of this block. Morcover, we prove that these bounds are much tighter, in expectation (will be formalized later) than the IBP bounds (Gowal et al. 2019) generated by propagating the input bounds through every layer in the block. Our bounds get even tighter as the number of hidden nodes in the first affine layer increases. (ii) We show a practical and efficient approach to propagate our bounds (for the block of layers) through blocks (not through individual layers) of a deep network, thus resulting in magnitudes tighter output bounds compared to IBP. (iii) We conduct experiments on synthetic networks and on real networks, to verify the theory, as well as the factors of improvement over IBP. Due to the tightness of our proposed expected bounds, we show that with a simple standard training procedure, large/deep networks can be robustly trained on both MNIST (LeCun) 1998) and CIFAR 10 (Krizhevsky & Hinton] 2009) achieving state-of-art robustness-accuree compared to IBP. In other words, we can consistently improve robustness by significant margins with minimal effect on test accuracy as compared to IBP.
trade-off
2 RELATED WORK
Training accurate and robust DNNs remains an elusive problem, since several works have demon- strated that small imperceptible perturbations (adversarial attacks) to the DNN input can drastically affect their performance. Early works showed that with a very simple algorithm, as simple as max- imizing the loss with respect to the input for a single iteration (Goodfellow et al., 2014). one can casily construct such adversaries. This has strengthened the line of work towards network verification for both evaluating network robustness and for robust network training. In general, verification approaches can be coarsely categorized as exact relaxed verifiers.
Exact Verification. Verifiers of this type try to find the exact largest adversarial loss over all possible bounded energy (usually measured in fo norm) perturbations around a given input. They are often tailored for piecewise linear networks, e.g. networks with ReLU and LeakyReLU nonlinearities.
They typically require mixed integer solvers (Cheng et al. 2017; 2017: Lomuscio & Maganti 2017 Tjeng
Tedrake 2019) or Satisfiability Modulo Theory (SMT) solvers (Xiaowei Huang Wu, 2017
Ehlers 2017). p. The main advantage of these approaches is that they can reason about exact adversarial
robustness; however, they generally are computationally intractable for verification purposes let alone
any sort of robust network training. The largest network used for verification with such verifiers was with the work of Tjeng& & Tedrake (2019), which employed a mixed integer solver applied to
2

---

BLOCK Under review as a conference paper at ICLR 2020
networks of at most 3 hidden layers. The verification is fast for networks that are pretrained with relaxed verifier but gets much slower on normally trained similar sized networks.
Relaxed Verification. Verifiers of this type aim to find an upper bound on the worst adversarial loss across a range of bounded inputs. For instance, a general framework called CROWN was proposed by Huan Zhang & Daniel (2018) to certify robustness by bounding the activation with linear and quadratic functions, thus, enabling the study of generic, not necessarily piecewise linear, activation functions, By utilizing the structure in ReLU based networks, the work of Weng et al. (2018a) proposed two fast algorithms based on linear approximation on the ReLU units. Moreover, Wang et (201 (c) proposed Relu Val for network verification based on symbolic interval bounds, while Wang et al. (20T8b) proposed Neurify with much tighter bounds. Several other works utilized the dual view of the verification problem (Wong & Kolter 2018 Wong et al., 2018). More recently,
Salman et al. (2019) unified large number of recent works in single convex relaxation framework and revealed several relationships between them. In particular, it was shown that convex relaxation methods that fit this framework suffer from inherent barrier compared to exact verifiers.
important to note that there are also hybrid methods that combine both exact and relaxed verifiers and have shown to be effective (Rudy Bunel| 2018). Although relaxed verifiers are much more computationally friendly than exact verifiers, they are still too expensive for robust training of large/deep networks (with more than 5 hidden layers). However, very loose relaxed verifiers can possibly still be exploited for this purpose. For instance, Wang et al. (2018a) leveraged symbolic interval analysis to verifiably train large networks. More recently, the work of Gowal et al. (2019) proposed to use an inexpensive but very loose interval bound propagation (IBP) certificate to train (for the first time) large robust networks with state-of-the-art robustness performance. This was at the expense of complex and involved training routine resulting from the loose nature of the bounds. To remedy these training difficulties, we instead propose expected bounds, not for each layer individually, but for block of layers jointly. Such bounds are slightly more expensive to compute but are much tighter in expectation. We then propagate these bounds through every block in a deeper network to attain much tighter bounds overall compared to layerwise IBP. The tighter bounds enable the use of simple standard training routines for robust training of large networks, resulting in statc-of-art art robustness accuraacy trade-off.
For completeness,
3 EXPECTED TIGHT INTERVAL BOUNDS
We analyze the interval bounds of DNN by proposing expected true and tight bounds for a two-layer network Afffine-Rel.--Affine Then, we propose a mechanism to extend them for deeper networks. First, we detail the interval bounds Gooal et al. 2019 to put our bounds in context.
3.1 INTERVAL BOUNDS FOR A SINGLE AFFINE LAYER
For a single affine layer parameterized by A E R*x and bj E k it is easy to show that its output lower and upper interval bounds for an e- norm bounded input x [x el,, x + eln)] are:
1 = A,x + b - | u1 A b + c|A1
(1)
Note that |.| an elementwise absolute operator. In the presence of any non-decreasing elementwise nonlincarity (e.g. ReLU), the bounds can then be propagated by applying the nonlinearity to {l1 } directly. As such, the interval bounds can be propagated through the network one layer at a time, as proposed by Gooal et al. (2019). While this interval bound propagation (IBP) mechanism is a very simple and inexpensive approach to compute bounds, these bounds can be extremely loose for deep networks, requiring a complex and involved robust network training procedure.
3.2 PROPOSED INTERVAL BOUNDS FOR AN CEINNE-RELUAAAE
Here, consider block of layers of the form Affine-Red ReLU-Affine in the presence of foo pertur- bations at the input. The functional form of this network is: gxx) = a. max (A₁x+ + b 0) + b2. where max(.) is an clementwise operator. The affine mappings can be of any size, and throughout the paper, we take A₁ E R and without loss of generality the second affine map is single vector a2 E R Note that g also includes convolutional layers, since they are also affine mappings.
Layerwise Interval Bound Propagation (IBP) on g. Here, we apply the layerwise propagation strategy of Gowal et al. 2019) detailed in Section 3.1 on function g() with & É [x el,, x cl,)
3

---

Under review as a conference paper at ICLR 2020
to obtain bounds
LLBP, UIBP] We use these bounds for comparison in what follows.
max (n1 0&) + max (11, 0k)
-|ag] max (u1, 02) max (11, 0s)
LIBP- = a²
+ b2.
2 max (u1, 0₂) + max (1,, 0x) + |
2
max (u, 0&)) mmx (11, 0₂)
UIPP = a2
+ b2.
2
2
Note that max (1,, 0g. and max (u,, 0₂) are the result of propagating [x - el,, cln) through the first affine map (A1; b1) and then through the ReL.U nonlinearity, as stated in 1
Expected Tight Interval Bounds on Our goal is to propose new interval bounds for g. block, which are tighter than the IBP bounds [LIP.. UIBP], since we believe that tighter bounds for a two-layer block, when propagated/extende
to deeper networks, can be tighter than applying IBP layerwise. Denoting the true output interval bounds of g as [Luee Utee] the following inequality holds Luue S g(x) < Unee vX E [x c1,, x + cln]. Deriving these true (and tight) bounds for in closed form either hard or results in bounds that are generally very difficult to compute, deeming them impractical for applications such as robust network training. Instead, we propose new closed form expressions for the interval bounds denoted [L, UM]. which we prove to be true bounds and tighter than [LIBP, UIP in expectation under a distribution of the network parameters A and a2- As such, make two main theoretical findings. (i) We prove that LM and UM true bounds in expectation, i.e. EA,, [Lm] < E EA, ,22 [Imee] and EA, ag [UM] 2 EA,,av .az [Umee] hold for sufficiently large input dimension (ii) We prove that [L, U UM] can be arbitrarily tighter than
the loose bounds [LBP, UBBP] in expectation, as the number hidden nodes increases.
Analysis. To derive LM and UM, study the bounds of the following function first:
g(x) 2 M (A₁* b1) + b2 a. MA + a, Mb; + b22
(2)
Note that ğ very similar to the Affine Sefine-ReL--- ReLU-Affine map captured by g with the ReLU replaced by a diagonal matrix M constructed as follows. If we denote = A + b1 + e as the upper bound resulting from the propagation of the input bounds [x e1n,,
e1n, through the first affine map (A,, b1). then we have M = diag (1 {nj 2 0x)) where is an indicator function. In other words, Mg = when the 7th element of u, is non-negative and zero otherwise. Note that for a given un (x) is an affine function with the following output interval bounds for x E [x eln, x + eln]:
LM, UM a. MA, x + a. Mb; + b2 F c/a |
(3)
To compare LM and UM to Lune and Utue- respectively, and since having access to Luue and Uuve not feasible, we make the following mild key assumption.
Assumption 1. (Key Assumption). Consider an Eo bounded uniform random variable x, x E [x c1,, x + =1,] where Ai and ag have elements that are i.i.d. Gaussian of zero mean and a and aa standard deviations, then there exists a sufficiently large m, such that:
EA, 82 [Lrue] 2 Lapprox E [x(x) my Var Yara,: [9(3)],
E EA [Umel] < U approx = EAJ [x(x]] + / Var [x(x)]
Under Assumption I and to show that LM and UM are true bounds in expectation, it is sufficient to show that Lapprox EA,,ay ay [LM] and similarly for UM. However, since it generally difficult to compute the right hand sides Assumption they can be well approximated by IyyLyan Lyapunov Central Limit Theorem. More formally, follows the two propositions.
Proposition 1. For E RD N0000 and a uniform random vector & ~ U[x e eln, x + el,,) where both and & independent, have that Lyapunov Central Limit Theorem holds such that
(i:a; - E(a,ū.)) -a NO 1), where 2 = Var Σ n
(a:a: - Ela,ū.))
Sn
where _d indicates convergence in distribution.
Proposition 2. For random matrix A1 with i...d. Gaussian elements of zero mean and A standard deviation and uniform random vector x U [x- cl,, X + c1,)] we have that Covariance (Ax) (g (22o2 22 22 trace(xx (xx T)...
4

---

Under review as a conference paper at ICLR 2020
fully connected aetwork
hilly-conneee untwork
0.98
0.99
- 0.96
100
= 0.98
500
0.94
0.97
10
H 20
0.96
2
8 10
Impur size: I
number of layers
(a)
(b)
Figure I: True Bounds in Expectation. As shown in Figure 1a our proposed interval bounds [LM, Um]), as
predicted by Theorem get closer to being true super to the true interval bounds [Lmme Umee] estimated by
Monte-Cate Sampling as the input dimension n increases regardless of the number of hidden nodes. Figure 16 shows that a similar behaviour is present even under varying network depth.
Following Propositions
T
and we have that for a sufficiently large input n::
Lupproxs U Uapprox Rs Emg.y [a]] max (8, 0) + b2] F my Varag. [a] max (5,0) + b2],
where the output of the first affine layer Ai + by is approximated by Lyapunov Central Limit Theorem as ÿ ~ N(i,, (3e² 22 + d trace(xx III.
Theorem 1. (True Bounds in Expectation) Let Assumption Thold. For large input dimension n, EA [LM] & EA, [L
and EA,, U S AA (UM)-
(5)
Theorem ! states that the interval bounds for function I are simply looser bounds to the function of interest g in expectation under a plausible distribution of A₁ and ag. Now, we investigate the tightness of these bounds as compared to the IBP bounds [LBP,, UIBP].
Theorem 2. (Tighter Bounds in Expectation) Consider an to bounded uniform random variable block of layers in the form of Ceine-RRLU--ffiee (parameterized by A1, b a2 and b2 for the first and second affine layers respectively) and a ~ NO, oaz I). Under
input x E [x- clu,x x
clu)
the assumption that 22 x 1 A (::j)) + 2n b 2 c <(IA1((,)))=
<25 A1(:))))1) Vj. we
have: Eag [[UIBP LIBP) (UM LM)]
Theorem 2 states that under some assumptions on A and under a plausible distribution for a2, our proposed interval width can be much smaller than the IBP interval width, Le. our proposed intervals are much tighter than the IBP intervals in expectation. Next, we show that the inequality assumption in Theorem 2 is very mild. In fact, a wide range of (A1, b1) satisfy it, and the following proposition gives an example that does so in expectation.
Proposition 3. For random matrix A₁ E Rxxx with i.d.d elements Az ~N 1), then
1 2
T ( /2
[ k
2 2J Vk ( (1-v
1 (1
2
EA, |IAi (1.))2
A1 (1(6)))))))
Proposition 3 limpliss that as the number of hidden nodes increases, the expectation of the right hand side of the inequality assumption in Theorem 2 grows more negative, while the left hand side of the inequality is zero in expectation when b ~ N (Ox. I). In other words, for Gaussian zero-mean weights (A1, b1) and with a large enough number of hidden nodes k the assumption is satisfied. All proofs and detailed analyses are provided in the appendix.
Comment on the Assumptions on A and a2. Generally speaking, our proposed bounds LM, U computed using Equation can be very loose and much worse compared to IBP the network weights A1,a, a2 do not follow the Gaussian assumption. We leave for the appendix an example to such failure. However, while the Gaussian i.i.d. assumption can be strong for general networks trained on real data, it is not far from being reasonable due to commonly accepted training procedures. This is since it is common to regularize network weights while training deep neural networks with an Eg regularizer encouraging the weights to follow a zero mean Gaussian distribution not to mention that networks in many cases are initialized in such manner. We dwell on this further in the appendix where we show the histogram of the weights of networks trained on real data (MNIST, CIFAR1O, 10, CIFAR 100). with and without f regularization See appendix for details.
5

---

Under review as a conference paper at ICLR 2020
Input deze
300
Ingui deee 500
mimber hilden zodes k- 500
rumber of Modden modes k
War WW:
10'
EUT
Wor Wi:
10
-01
+1
ol
10
+01
2.
0.5
F711
5000
5000
10003
5000
10200
5003
(a)
(b)
(c)
(d)
Figure 2: Tighter than IBP with Varying Input Size and Hidden Nodes. We show a bound tightness comparison between our proposed interval bounds and those of IBP by comparing the difference and ratio of their interval lengths with varying k. n, and c for a two-layer network. The proposed bounds are significantly tighter than IBP, as predicted by Theorem 2
To Inpret vloe 100
Impest skar
900
Expert
12x50
laper dlze 12:52
10
War
War
121
922
103
T
Numbet
Number
Nonther
Number
(c)
(d)
Figure 3: Tighter than IBP in Deeper Networks. We show hound tightness comparison between proposed interval bounds and those of IBP by varying the number of layers for several choices of c. The proposed bounds are significantly tighter than IBP.
3.3 EXTENDING OUR EXPECTED TIGHT BOUNDS TO DEEPER NETWORKS
and an To extend our proposed bounds networks deeper than two-layer block, we simply apply bound procedure described in Section 3.2 recursively for every block. In particular, consider an AgReLU(A1x))
L-layer neural network defined as f(x) Ae
lo norm bounded input centered at x, i.e. x E [x el, x + e1,). Without loss of generality, we assume f is bias-free for ease of notation. Then, the output lower and upper bounds of are LM = G - <| eGGr,_1 and UM = Gr, e/Gr.-/ In, respectively. Here, G is linear map that can be obtained recursively as follows:
G. - (with Go A1) and M, = diag (1 ((G,,)x+ (G--I 2 0}) (6)
Note that - i|G.-1|1,, is the output upper bound through linear layer parameterized by G for input as in (IT. With this blockwise propagation, the output interval bounds of f are now estimated by the output intervals of f(x) = GL-1X.
EXPERIMENTS
True Bounds in Expectation. Here, validate Theorem I with several controlled experiments. For a network (xx = A₂ max (A,* + b1, 0) + b2 that has true bounds [Luger Unue] for & E [x c1,1,, x + cl,), we empirically show that assumptions of Theorem [] indeed are true, i.e. they are a super set to [Luee U Utue]] in expectation. We also verify this function of the network input dimension (as predicted by Theorem D
cl,,
proposed bounds [L,, UM), under the mild
We start by constructing a network y where the biases b E R& and by E R. are initialized following the default Pytorch initialization (Paszke et al. (017). As for the elements of the weight matrices IR. I they are sampled from (0, 1//n) and (O 1/VK), respectively. We
A *x and A2 E estimate Line and U Une by taking the minimum and maximum of 10 + 2" Monte-Carlo evaluations 0.1, we uniformly sample 10 examples from the interval [x (x-c1,, c1,, x cl,]]. We also sample all 2n corners of the hyper cube [x [x x cl,l"" To show that the proposed interval [LM, Um] is a super set of [Luue Urrel (i.e. they are true bounds), we evaluate the length of the intersection of the two intervals over the length of the true interval defined as I =I[LM Um] [Luve, / [Luuee Unue]l. Note that = if and only if [L, UM] super set of [Lmeey m- For given n, conduct this experiment 10 times with varying Ai,
of g. For given x ~ (O,,,, I) and with
A2. by, b2 and x and report the average r. Then, we run this for a varying number of input size and varying number of hidden nodes k; reported in Figure Ta As predicted by Theorem [

---

Under review as a conference paper at ICLR 2020
Table 1: True and Tight Bounds on Real Networks. Table shows that our bounds are super set to true bounds computed with an exact MIP solver. Moreover, they are much tighter than bounds estimated by IBP.
Tai
Tax
Wine
WM
Wine/ WM
Small
MNIST
0.01
1
1.0
1.0
Small
0.01
644.322
17.391
0.02
1.0
1.0
1.0
0.02
1381.980
15.270
0.03
0.97 + 0.088
0.635
1.0
0.03
2255.397
14.555
4043
12
40.
-1.83
14
1.34
2.43
00.35
4035
3.55
0.06
0.35
-3.89
-35
3.0
0.5
0.4
1.35
0,5
2.5
1,4
45
14
4.0
155
Figure 4: Qualitative Results. We plot visualizations of the output polytope of a 20- 100-100010--1000 100-1000100 network through Monte-Carlo evaluations of the network with uniform random input with varying We also plot our proposed bounds LM, UM] in red. Each row is for a given with different randomized weights for the network. As for the IBP bounds [Lap, Uwe], they were omitted they were significantly larger. For example, for the first figure with 0.05, IBP bounds are 43.7, 32.9) for the x-axis and -7.88, 37.0) for the y-axis.
Figure Ta demonstrates that as n increases, the proposed interval will be more likely to be a super set of the true interval, regardless of the number of hidden nodes k. Note that networks that are as wide as h: = 1000, require no more than n input dimensions for the proposed intervals be a super set of the true intervals. In practice, n is much larger than that, e.g. n Re 3 x 10s in CIFAR10.
In Figure Ib we empirically show that the above behavior also holds for deeper networks. We propagate the bounds blockwise as discussed in Section [33 and conduct similar experiments on fully-connected networks. We construct networks with varying depth, where each layer has the same number of nodes equal to the input dimension = n. These results indeed suggest that the proposed bounds true bounds and more likely so with larger input dimensions. Here, 20 performs better than n = 10 across different network depths.
Tighter Bounds in Expectation, Here, we experimentally affirm that our bounds can be much tighter than IBP bounds (Gowal al., 2019). particular, we validate Theorem by comparing the interval length of our proposed bounds, WM UM LM. with that of IBP, W WIBP UIPP LIBP, on networks with functional form g. We compute both the difference and ratio of widths for varying values of k. n, and Figure 2 reports reguotsrrppors the average width difference and ratio over 10 runs in similar setup the previous section. Figures 2a and 2b show that the proposed bounds indeed get tighter than IBP, as k increases across all values (as predicted by Theorem 2 Note that we show tightness results for {0.01, 0.1} in Figure 2b as the performance of
0.5, 1.0) was very similar to e = 0.1. Similar improvement occurs with increasing n. as in Figures 2c and 2d
We also compare the tightness of our bounds those of IBP with increasing depth for both fully- connected networks (refer to Figures Ba and 3b) and convolutional networks (refer to Figures and 3d For all fulne-con networks, we take = k = 500. Our proposed bounds get consistently tighter as the network depth increases over all choices of e. In particular, the proposed bounds can be more than 10 times tighter than IBP for a 10 layer DNN. A similar observation can also be made for convolutional networks, where it is expensive to compute our bounds using the procedure in Section 3.3 so instead, we obtain matrices M, using the aasytto-coppute IBP upper bounds. Despite this relaxation, we still obtain very tight expected bounds. Note that this slightly modified approach reduces exactly to our bounds for two-layer networks.
True and Tight Bounds on Real Networks. Moreover, we also train small network, the architecture is similar to Gowal et al. (001)). on the MNIST dataset ~ 99%. To show that our bounds are also true on real networks, and since the input dimension is too large for Monte-Carlo sampling, the MIP formulation by Tjeng & Tedrake 2019). We then report I over varying testing e. Table demonstrates that indeed even real networks beyond two layers and without the Gaussian weight
7

---

Under review as a conference paper at ICLR 2020
MNIST Small
MNIST
MNIST Large
0.9
Nominal
8 0.7
[6rw 0.11
0.6
IBP
[Cmm - 0.2]
0.5
TBP
[6unn 0.3]
0.4
[Gmn 0.1]
PGD
0.3
Ours
[Eun 0.2]
0.2
Ours [Cran 0.3]
0.1
[Eran 0.41
0.98
0.99
1.00
0.98
0.99
1.00
0.98 0.99
1.00
Test Accuracy
Figure Better Test Accuracy and Robustness on MNIST. We compare the PGD rohustness and test. accuracy of three models (small, medium, and large) robustly trained on the MNIST dataset using our bounds and those robustly trained with IBP. We have trained both methods using four different Cuain, but we eliminated all models with test accuracy lower than 97.5%. Our results demonstrate impressive trade-off between accuracy and robustness and, in some cases (medium and large models), excel in both.
CIFAR1O-SMD
CIFAR10 Medium
CIFAR10 Large
0.45
0.40
Nominal
0.35
18P [ran - 2/255]
0.30
ISP
Ifea 8/2551
0.25
Ours
[toa 2/2551
0.20
[eaa 8/255]
Ours
[raas 16/255]
0.10
Freas 0.1]
0.05
0.00
0.4
0.5
0.8
0.5
0.6
0.7
Test Accuracy
Figure 6: Better Test Accuracy and Robustness CIFAR10. We compare the PGD robustness and test accuracy of three models (small, medium, and large) robustly trained on the CIFARIO dataset using bounds and those robustly trained with IBP. We eliminated all models with accuracy lower than 40.0%. PGD robustness averaged over multiple ene (refer to appendix).
distributed assumption, our bounds are still a super set to the true bounds computed with an MIP formulation. Moreover, Table demonstrates that our bounds are much tighter than IBP bounds. Note that the reported results are averaged over 100 random MNIST images.
Qualitative Results. Following previous work (Wong & Kolter 2018 Gowal al.) 2019), visualize examples of the proposed bounds in Figure 4 and compare them to the true ones for several choices of e E f0.05, 0.1, 0.25) and random five-layer fully fully-conneeted network with architecture n- 1-1100-00-110-1000
We also show the results the Monte-Care sampling for an input size 20. More qualitative visualizations for different values of n are in the appendix.
Training Robust Networks. Here, we conduct experiments showing that our expected bounds can be used to robustly train DNNs. We compare our method against models trained nominally (i.e. only the nominal training loss used), and those trained robustly with IBP (Gowal al. 2019). Given the well- known robustness-accuracy trade off, robust models are often less accurate. Therefore, we compare all methods using an accuracy vs. robustness scatter plot. Following prior work, we use Projected Gradient Descent (PGD) (Madry et al. 2018) to measure robustness. We use a loss function similar the one proposed in (Gowal al. 2019). P..1.. In particular, we use L = ((]o(x), (x)e) where f, fo(x), Yime. and x are the eross-yntropy loss, output logits, true class label, and regularization hyperparameter respectively. represents the "adversarial" logits that combine the lower bound of the true label and the upper bound of all other labels, as in (Gowal et al. 2019). Nominal training occurs when K O. Due to the tightness of our bounds, in contrast to IBP. we follow standard training procedure that avoids the need to vary K or Etrain during training.
xl(z, Yine).
Specifically, we train three network models (small, medium, large) provided by Gowal et al. (2019) on both MNIST and CIFARIO. See appendix for more details. Following the same setup in (Gowal et 2019) we train all models with Grain E (0.1. 0.2, 2,,0 0.3, 0.4] and Grain E (2/255, 8 8/255. 16/255, 0.1 on MNIST and CIFAR1O, respectively. In all experiments, and for stronger baselines and fair comparison between IBP training and our bounds employed in training, we grid search over (0.1, 0.001, 0.0001) learning rates and employ a temperature over the logits with grid of {1, 1/5} as in (Hinton et al.] 2015) and report the best performing models for both. Then, we compute PGD robustness for every train of every model for all tre {0.1, 0.2, 0.3, 0.4) for MNIST and for all ftest E {2/255, 8/ 8/255, 16/ 6/255, 0.1 for CIFAR 10. To compare training methods, we compute the average PGD robustness over all éea and the test accuracy, and report them in 2D scatter plot. We
8

---

Under review as a conference paper at ICLR 2020
report the performance results MNIST and CIFARIO for the small, medium, and large architectures in Figure []] For trained architectures, we only report the results for those that achieve at least test accuracy of 97.5% and 40% on MNIST and CIFARIO, respectively; otherwise, it is an indication of failure training. Interestingly, our training scheme can be used to train all architectures for all frain- This is unlike IBP, which for example was only able to successfully train the large architecture with furann 0.1 on MNIST. Moreover, models trained with our bounds always achieve better PGD) robustness than the nominally trained networks on all architectures while preserving similar if not higher accuracy (on large networks). Models trained with IBP achieve high robustness but their test accuracy is drastically affected. Several other experiments are left for the appendix.
5 CONCLUSION
In this work, we proposed new interval bounds that are tight, relatively cheap to compute, and true in expectation. We analytically showed that for Affine-Rel- ReLU-Affine block with large input and hidden layer sizes, our bounds are true in expectation and can be several orders of magnitude tighter than the bounds obtained with IBP. We conduct extensive experiments verifying theory, even for deep networks. As a result, we are able to train large models, with simple standard training routines while achieving excellent trade-off between accuracy and robustness.
REFERENCES
Modar Alfadly, Adel Bibi, and Bernard Ghanem. Analytical moment regularizer for gaussian robust networks. arXiv: /904. 1005, 2019.
Adel Bibi, Modar Alfadly, and Bernard Ghanem. Analytic expressions for probabilistic moments of pl-dnn with gaussian input. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR18), 2018
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Aulomuted Technology for Verification and Analysis, 2017.
Rüdiger Ehlers. Formal verification of piece-wise wise linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, 2017.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adversarial examples. arXiv: 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. International Conference on Computer Vision (ICCV), 2019.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine. 2012.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. NIPS Deep Learning and Representation Learning Workshop, 2015.
Pin-Yu Yu Chen Cho-Jui Hsich Huan Zhang, Tsui-Wei Weng and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. Advances in Neural Information Processing Systems (NeuriPs), 2018
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, 2009.

---

Under review as a conference paper at ICLR 2020
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances Neural Information Processing Systems (NeurIPs), 2012.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. #xXiv//76.0073/// 2017.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015,
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICLR), 2018.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning (ICML), 2018.
Seyed-Mohsen Moosavi-Dezfoolli Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
Seyed-Mohser Moosavi-Dezfooll, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vetooo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. Advances in Neural Information Processing Systems workshop, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. International Conference on Learning Representations (ICLR), 2018
Philip H.S. Torr Pushmeet Kohli-M. Pawan Kumar Rudy Bunel, Ilker Turkaslan. A unified view of piecewise linear neural network verification. Advances in Neural Information Processing Systems (NeurlPs), 2018
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robust verification of neural networks. Advances in Neural Information Processing Systems (NeurIPs), 2019.
Swami Sankaranarayanan, Azadeh Alavi, Carlos D Castillo, and Rama Chellappa. Triplet probabilistic embedding for face verification and clustering. In IEEE International Conference on Biometrics Theory, Applications and Systems (BTAS), 2016.
Kai Xiao Tjeng, Vincent and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. International Conference on Learning Representations, (ICLR), 2019.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv: 1.02625, 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems (NeurIPs), 2018b.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang. and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In 27th {USENIX) Security Symposium ({USENIX) Security 18), 2018c.
Stefan Webb, Tom Rainforth, Yee Whye Teh, and M Pawan Kumar. A statistical approach to assessing neural network robustness. International Conference on Learning Representations (ICLR), 2018.
Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and I Luca Daniel. Towards fast computation of certified robustness for relu networks. International Conference Machine Learning (ICMI.), 2018a.
10

---

Under review as a conference paper at ICLR 2020
Tsui-We Wei Weng, Huan Zhang. Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. International Conference Learning Representations (ICLR), 2018b.
Eric Wong and J Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. International Conference on Machine Learning (ICML), 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems (NeurlPs), 2018.
Sen Wang Xiaowei Huang, Marta Kwiatkowska and Min Wu. Safety verification of deep neural networks. International Conference on Computer Aided Verification, 2017.

---

Under review as a conference paper at ICLR 2020
Proposition 1. For R" ~ NN0, oo and a uniform random vector & ~ U(x cln,, x cIn) where both a and are independent, we huve that Lyapunov Central Limit Theorem holds such that
Sp. - (3,a,- - -[a,ū,)) a NN(,,)),, where s = Var - (5,0; - Ela,E.1)
-
where tat indicates convergence in distribution.
Proof. The Lyapunov condition
38 > 0,
E
[.a
- E[a,ū;]| 2+0
+
0,
n -
(7)
2+5 2=1
is sufficient for Lyanunov Central Limit Theorem to hold. Note that
2
n
nE2
n
Var (āça.)
o
x
0
+
(8)
Since for = 2, we have that
E [ (20]
Bitt
2-2
1
1
exp (- a
(- 20
da,dō;
2c
V2TTa
xi-e
30 4
tite
30d
Add.;
[[x; + t) - (s; - c)
2c
10c
sc-
Thereafter, Lyanunov Central Limit Theorem with d = 2 is satisfied since
i.a. E|a,ū;] 2+07
T []]
lim
lim n $
70000
3 3
(xt + +c)² - (x:; - 6)
lim
10c (33
nc²
+ x2? )²
3n ((Imax +e) (mmin =))
lim
n=000
10c
nne2 + Em x²²)
2
3
Proposition 2. For random matrix A with i.i.d. Gaussian elements of zero mean and a. standard deviation and a uniform random vector X ~ 2 [x cl,, x + eln] we have that Covariance (AX)
2032 + +o2 trace (xx)) (sxxT)) I.
Proof. The former follows from the fact that Covariance (A, + b,) Covariance (A18)
E
A XX
A
E |
X
(E
(A) T = E EAA ATI
EAI A E
A
EA
A
Diag
xx A
2
EA, [A,A]] + E [A AT]
2002, n
EA, [AIA]] + +o², trace (xx II
3 A trace (xx I
The last equality follows since:
if i if i=
I A1xx T = E | xx T a,] = trace (xx TE [aya?] TI) =
03 trace (xx
12

---

Under review as a conference paper at ICLR 2020
Theorem 1. (True Bounds in Expectation) Let Assumption 7 hold. We have that for large input dimension n,
aA LM] S Ba [iuee, Ba [Umee I EA [UM].
Proof.
Luppexx Engs [ag max (ý, 0) b2] my Varaz. [ag max (ý, bz]
@ bo - my Bag Varyy (a) max (ý, 0) + by [a2]] Varag (Fg [a] max (ý. 0) + (bg
3
lo
Rag
(ag
22)
By mmax² (ý, 0)] (Es [max (y, 01))*}
Varna (Eg [a] max (8, 0) + b2 (y(aa)))
k mmax (ý, 0)]),
b2
Σ a (Ey [max (5. 0));
+ Σ o (Ey [max (ÿ, 0))?
a2
b9
10
(By [max² (5, 0)),
1=1
2
b2 m0aa
(b + o ④ (bf 2 ooy) + (b) o o (bf 0
Note that @ follows by total expectation and total variance the terms, respectively. Lastly, follows from the closed form expression derived in Bibi et al. (2018) where & and ø are the normal cumulative and probability Gaussian density functions, respectively. Note that
@
E0 +
+ trace (xxT)) and that oî (200,, 0 trace (xx (xxx))
M b
Lyprrox
aa [Mm]
by mo v
EA, [ M (Aix b1) b2 cla MA
EA a2 [ela] MA 1] moa, V
=EAA,
En J MAI
m0 Vp
① EA
Vara, (aMMA, (..M(::.)) (:.1))
Mō a;
12 FA V
60
((..))MAA (:.5)
-m V
π
1 RA
<0ag V -
(1( 20
m0 W
12 E|s V
E0ag
EA1
Σ iES
A و2,
1||
m0 V
π
Note that @ follows from the mean of a folded Gaussian. The last equality follows by taking the total expectation where S is the set of indices where of > 0 for all i S. Since u is random, then
13

---

Under review as a conference paper at ICLR 2020
|S] is also random.
Therefore, reparametrize the sum and thus have
k
200 A T
r
+1
60
RAI
j)
[
Byst
71
SES
r
[S]
2c0 A 02 n1
S|
B|sl
V
2
2c0 A. Ja n
le 2
π
The approximation follows from stirlings formula r(*1 (a)l///))) 2 v*/2 for large where the last inequality follows since E
VIsI < k].
2e0 A J
Luppexx EAL,02 [Lm] 2
v π 2
md
b + o3) o 4 (bj 2 ogy)
(bj By o 20r))
Note that @ is (n) while @ is O(vn)) Thus, for sufficiently large input dimension we have that
Lupproxx 2 EA, [M] and since by construction EA,,,v [Luue]] 2 Luppoox which completes the proof.
Note that a symmetric argument can be applied to show that EA .2 MM] 2 EA, a2 [ un D
14

---

Under review as a conference paper at ICLR 2020
Theorem 2. (Tighter Bounds in Expectation) Consider lee bounded uniform random variable
inpul X, i.e. & E fxx- el,; X + tlnp to block of layers in the form of Sfjme-ReLUU-Afime (parame- terized by A1, bi, a2 and b2 for the first and second affine layers respectively) and a2 ~ (O, oag I.
Under the assumption that V22 x (1:5)) + 2n 1 2 e (1AA
V2n (1(:))1 Vj.
we have: Eaz 1(UIIP L(BP) - (UM LM)) 2 0.
Proof. Note that
[UIP Lmp) - (UM - LM)] e e|a2 |||||
1n
+
0/
||||]
2 a/2
[h]
2
26 a2 diag (1 [u 2
T
0)) A
1
Consider the coordinate splitting functions (++) 5 (.), (.) and S - such that for E IR"
S++(x) {u} 0.1 0} where 1 {u] 0, 2 0} is vector of all zeros and in the
locations where both ni. 1 2 0. However, since u1 2 11 then (-) O. Therefore it is clear
that for any vector x and an interval [4, un], we have that
x S (x) S S (x)+ (x),
since the sets fi: 2 0.1 2 0}. ui 2 0.1 S 0} and {i: S 0, 1 I 0} are disjoints and their union {i = 1, 2...., = kj. We will denote the difference in the interval lengths as
Winp WM for ease of notation. Thus, we have the following:
1) |A 1,, + + (Ia) |A [1, + + (la) l) |Ai + 1 St (Ia)) Jui
WIBP - = (Ia)
+/2
St (la) [n| 2 S (|a) l) |un| 2 st ((aT]) [h||
1
1 St (aa5 [h|]
2
2
1 S- (la) () |h| 2c (s+ (a)) + +S+ (a.) + 5- (a. diag (1 (u, 2 03) la
2
= 2 (|aT)) | 1n + + (aa) I) (Aix + b1) + + (aa. l) Al
28 (s++ (a)) + S (a))) A 1,
= - ((a l) |1 + + (lag) 1) in 2e (o++(a)) + 5 (a A 1n
Note that used the property of the coordinate splitting functions defined in Eg 9 along with the definitions of The previous The penultimate equality follows since + and 5 corresponds to the indices that are selected by I and u1. The penultimate equality follows since S and S corresponds to the indices that are selected by diag (1 {u, 2 0}).
Now by taking the expectation over a2, we have for ①
2cE [s+ (lag ||A))) 1, 2e
>
E
a
L
(i.:)
{ut 0.1 0] 1.
i=1
2
220 V
(1, |
[1 2 0} 1n
π
2 2e0 V
A { 2 20}
j=
The second equality follows from the mean of the folded Gaussian. and the fact that u1 2 1
15

---

Under review as a conference paper at ICLR 2020
For @ have:
E Bis (1a5 1) ui = 0n2
n 2
1=1
Lastly, for @ we have:
2elE (s++ (at) + (az) A
1, 2el3
Σ A (i, (1 2 1n
20)
Using
Holder's inequality, i.e. B[|=||
B per coordinate of the vector
k
Ai (i,)))a (1 fut 0})] and by binomial expansion, have at the jDh coordinate
A A (i. {ut 03
2c,
E
k
2e
Σ
(Ai ( E (ab))
I {ui 2 0) +2 +2 2
A (i( [abba] 1 {ui 2 0} I [uf 2 01)
i= s<i
26
Σ (i.j))))
[ab))] {ut 2 0} = 260az
Σ (A(i.))) {u, 2 0)
The second equality follows from by the independence of a and that they have mean. Therefore follows from @ that:
2cE
(s
(AT) + (A.) A1
1n I 2E0 32
Σ (ii().)) 1 2 0}
Lastly, putting things together, i.c. E
+ @
we have that
2
n
2
[IBB WMl
20
V
(1.
(1i 2 0) + oaz
(uf 0,1 s
π
#=1
n
260
(i,j) {ut 2 0)
(10)
Note that to show that the previous inequality is non-negative, is sufficient to show that the previous
inequality is non-negative for the -oneintersecting sets {i 1 0} and {i ui the right hand side can be written as the sum of two sets.
0. < 0). Thus
For the set (i 1 > 0}. the RHS of inequality 10 reduces to
2 2 V
(2 - -
2e0 #=1
(11)
For the set (i: un 2 0, 1 < 0) and using the definition of un the RHS of inequality 10 reduces
16

---

Under review as a conference paper at ICLR 2020
2
00
A (1,5)x +b, + Σ A (1.33)))
260
A (1()))l
17
A1 I + (A(()))))
2E0 Σ (t:5)l)
Jai
2 au V π 11
([b+c|A((..))) 200 |A1
(12)
Note that given the assumption in the Theorem where /2x x,,1,
11 2
(I)A2(;,))la= -a (11:((()))) Vj. then if both Eq 11 and Eq
12 are non-negative complet-
ing the proof.
Lemma 1. For RR ~
N (0, I), where k 2 5 we have that E
/er ||x|| 2||x||2 20.
Proof. Note that by the mean of folded Gaussian, we gave that E [[x]]]] Moreover, note that
= Σ EE [|x:|]
//
k EV
( x22 dr
2 2²
E [||||] =
Σ x?
x² exp
k)
2
2
(+t)) 2
22
Vk.
I(
Note that is Chi-Square random variable and that [(((1)) = (xf 23 -r()
where the third inequality follows by integrating by parts recursively, Lastly, the last approximation follows by stirling's 's approximation for large k.
Proposition 3. For a random matrix A E RR. Rxn with i.idd elements such Ai(i,) ~ N(0, 1), then
EA. (1,0l2 - 1 2 (A(0))) = v2 r (+1
k
V
1
Vk
r
Proof. The proof follows immediately from Lemma
17

---

Under review as a conference paper at ICLR 2020
A
MORE QUALITATIVE RESULTS OF THE NEW BOUNDS
We conduct several more experiments to showcase the tightness of our proposed bounds to the true bounds and compared them against propagating the bounds layerwise [l. upm for random 100 100 100 networks initialized with (0, 1/ /n) similar to Wong & Kolter (2018) We show our bounds compared to the polytobe estimated from MonteCarlo sampling results for n E (2, 10, 20 and e (0.05, 0.1, 0.25). The layer wise bound propagation is shown in the tables as the bounds were too loose to be presented visually.
71
100
2
1.34
0.2
0.02
0.28
1.345
bounds
0.208
0.03
0.27
11335
0.26
1..2
0.707
0.25
-0.24
0.6
0.14
-0.66
0.55
0.1
1.9
0.66
0.67
0.68
0.15
0.2
0.85
3.9
0.82
0.88
0.8
2.05
1.2
4.35
-1.9
1.5
1.3
12
-1.2
+.2
1.4
1.15
1.4
1.45
14
111
115
1.2
.0.6
-0.5
-34
-22
0.9
0.05
1.2
Figure 7: Each represents 5 different randomly initialized networks for given with 2. Note that the proposed bounds are far from being true this as predicted by Theorem for small n.
Figure Number
UDM
0.05, Figure Number 1
-10.1261
19.0773
-18.1500
13.3573
< 0.05, Figure Number = 2
-12,2529
14.3428
-14.4295
12.3479
c 0.05, Figure Number = 3
-12.6594
14.1837
-12.5873
12.2612
é 0.05, Figure Number = 4
-17.7825
16.4048
-15.3843
15.1688
6 0.05, Figure Number = 5
-12.5260
11.1149
-8,9242
12,7539
0.1, Figure Number
-27,4598
23.6603
-17.9481
23.4817
0.1, Figure Number 2
-23.2877
34.0542
-28.1535
21.8703
0.1, Figure Number 3
-35.2950
36.4901
-31.7465
36.0421
0.1, Figure Number 4
-31.7154
29.3062
-3033000
35.7105
0.1, Figure Number 5
-25,0870
39.4373
-2455087
32.5493
C 0.25, Figure Number =
-54,0557
56,2884
-52,5686
73.9621
é 0.25, Figure Number = -59,2115
82.8742
-75.7999
65.6898
E 0.25, Figure Number = 3 -50.1142
56,2330
-72.4221
54.4631
C 0.25, Figure Number = -52.6030
83,3950
-92,8100
69.1407
C 0.25, Figure Number = -89.1335
43.4685
-74.4519
91.5137
Table 2: Shows the interval bounds obtained by propagating e (0.05, 0.1, 0.25) with 2 and denoted as H "bM for the first output function of the 2-dimensional output network (shown along the x-axis in the previous figure) while 1/MM and uf is for the other function (shown along the y-axis the previous figure).
18

---

Under review as a conference paper at ICLR 2020
10
0:34
1.4
polylap
142
1.04
14
106
0.92
1.30
0.20
0.83
0.9
0.5
0.55
0.38
0.1
0.15
1.5
1.35
-155
-1.6
-1.0
0.13
3.4
3.5
3.6
0.6
0.65
1.5
1.65
17
3.3
3.25
3.2
0.1
0.05
-.0
-1.2
-0
-0.
6
-0.2
-12
0
0..4
2.4
-1.
-1
0.5
-0.6
2.5
Figure 8: Each row represents different randomly initialized networks for given with 10. Note how the bounds are more likely now to enclose the true output region for all given compared previous case where 2.
Figure Number
MDM
2
é 0.05, Figure Number =
-16.9716
24.9259
-21.2584
20.6358
< 0.05, Figure Number
-42.6267
48.1786
-38.6958
37.7851
0.05, Figure Number -41.4147
36.4056
-42.0363
36.6605
0.05, Figure Number
-32.1013
25.1485
-37.7864
33.3652
0.05, Figure Numher -45.4368
32.9774
-44.946
38.6805
0.1, Figure Number
-48.1221
86.6800
-5430559
71.2724
0.1, Figure Number 2
-51.2668
46.1237
-38,8889
33.6512
< 0.1, Figure Number = 3
-51.3915
52.4437
-52.7149
49. 49.1031
6 0.1, Figure Number = 4
-71.7738
54.4836
-91.0335
37.0950
6 0.1, Figure Number 5
-48.1744
33.2927
40.9540
47.2282
C 0.25, Figure Number
-152.7639
192.4156
1188.4030
148.24 2482
0.25, Figure Number
-196.8923
195.4355
-163.2691
177.3766
25, Figure Numher -141.6800
207.5414
-207.9396
190.2823
0.25, Figure Number 4
-200.7513
156.2560
-227.6427
182.0180
0.25, Figure Number 5
-153.3898
164.8314
-147.8662
137.4380
Table 3: Shows the interval bounds obtained by propagating E (0.05, 0.1, 0.25) with n 10 and denoted lb "bm for the first output function of the 2-dimensional output network (shown along the x-axis in the previous figure) while 1/M and up for the other function (shown along the y-axis in the previous figure).
19

---

Under review as a conference paper at ICLR 2020
20
-155
125
-128
1.44
-0.45
Smazated poytopo
0.05
-1.6
-.3
142
1332
14
-1.65
1:15
0.35
3.95
-18
0.15
0.2
1:55
1.4
1.3
.0.6
6.5
-0.4
6.2
0.3
0.4
1.7
1.655
-1.6
3.6
1.8
-0.4
-3.3
40.2
1.8
1.8
1.6
1.6
-0.2
1.4
1.4
-0.4
Figure 9: Each row represents different randomly initialized networks for given with 20. The bounds almost always enclose the polytope computed from Monte-Carlo compared to n 2, 10.
Figure Number
MDM
12
2
< 0.05, Figure Number 1
43.66899
32.8572
-47,7556
36.9842
é 0.05, Figure Number 2
-53.2447
47.1651
-46,5306
53.1638
é 0.05, Figure Number 3
-59.1694
42.6647
-43.4659
57.2781
6 0.05, Figure Number
-39.8479
42,4197
-2,1966
39.7649
6 0.05, Figure Number
-5.3150
42,8637
44.5742
43.8117
1, Figure Numher
-3355004
81.9034
-97.5203
98.8713
0.1, Figure Number 2
-64.8464
76.8083
-84.9233
83.9505
0.1, Figure Number 3
-70.5862
92.6652
-88,6098
71.8915
0.1, Figure Number 4
-78.0557
151.4360
10060073
123.3686
ε 0.1, Figure Number 5
-91.8368
97.3438
103.2845
76.6581
é 0.25, Figure Number
-188.7623
256.2275
-211.3972
255.5101
c 0.25, Figure Number
2219.5622
274.5287
-217.7622
349.4256
0.25, Figure Number -214.7457
160.7498
-186.5554
184.1767
0.25, Figure Number
-188.7623
256.2275
-211.3972
255.5101
0.25, Figure Numher
-276.9137
177.7929
-202.2031
245.8731
Table 4: Shows the interval bounds obtained by propagating (0.05, 0.1, 0.25) with 20 and denoted as l upm for the first output function of the 2-dimensional output network (shown along the x-axis in the previous figure) while 22 and u is for the other function (shown along the y-axis in the previous figure).
20

---

Under review as a conference paper at ICLR 2020
B
EXPERIMENTAL SETUP FOR TRAINING DNNS
small
medium
large
CONV 16 x x4x4+2
CONV 32 x 3 x 3+1 1
CONV 64 x 3 x 3 1
CONV 32 x 4x44+1
CONV 32 x 4 4 4
CONV 64 x 3 x
1
FC 100
CONV 64 x 3 x
CONV 128 x 3
CONV 64 x 4
CONV 128 x x
512
CONV 128 x
512
200
Table 5: Architectures for the three models trained on MNIST and CIFARIO. "CONV p w x h+ correspond to p 2D convolutional filters with size (w x h) and strides of While "FC d" a fully connected layer with d outputs. Note that the last fully connected layer is omitted.
21

---

Under review as a conference paper at ICLR 2020
C PGD ROBUSTNESS ON SPECIFIC INPUT BOUNDS ON MNIST
MNIST Small Icee = 0.1
MNIST Medium Liee - 0.11
MNIST -aarge (Crue 0.1]
1.00
0.95
Noninal
Babushes couusees
0.90
IBP [teer 0.11
Ireu 0.2]
0.85
IBP
[tear 0.3]
0.80
Burs [fewr 0.1]
0.75
[tear
0.70
Ours [ree 0:3]
0.65
Ours [tear 0.4]
0.60
0.98
0.99
1.00
0.96
0.99
1.00
0.98
0.99
1.00
Test
Figure 10: Compares PGD (ftest = 0.1) and test accuracy our models against IBP on MNIST.
MNIST Small [swe = 0.2)
MNIST Medium [tee 0.2]
MNIST Large [Swe 0.2)
0.8
PGD Rabustress
IBP [tem 0.1]
IBP
[Cme - 0.2]
[em
0.4
Ours [6mm 0.1]
Ours [Rrm 0.2]
0.2
[6mo
0.0
Ours [Cra 0.4]
Test Accuracy
Figure 11: Compares PGD (Erest 0.2) and test accuracy of our models against IBP on MNIST.
0.8
[sw 0.3)
[twe
MNIST Large [swe
Nominal
PGD Robustress
I0P [trm 0.1]
0.5
[[on
0.4
IBP
[ema 0.3]
0.3
Ours [Ram 0.1]
Ours
0.2
Ours [Eran 0.3]
Frras 0.4]
0.0
0.98
0.99
1.00
0.98
0.99 Test Accuracy
1.00
0.98
0.99
1.00
Figure 12: Compares PGD (feest 0.3) and test accuracy our models against IBP on MNIST.
MNIST Small lewe = 0.4]
MNIST Medium [twe:: = -0.4]
MNIST Large (cre 0.4]
0.14
Robustress
0.12
TBP Trear 0.11
0.10
I0P
[tear 0.2]
TBP
[fear
Ours [tewr 0:1]
[rar
Ours [Bear 0.3]
Ours [rear D.4]
0.99
0.98
0.98
Accuraty
Figure 13: Compares PGD (Etest 0.4) and test accuracy of our models against IBP on MNIST.
22

---

Under review as a conference paper at ICLR 2020
D PGD ROBUSTNESS ON SPECIFIC INPUT BOUNDS ON CIFARIO
CIFAR10
Small [iue = 2/255]
CIFAR10 Medium [Com = 2/555]
CIFAR10 Large [Cue 2/255]
0.9
0.8
Nominal
Rebusness
0.7
IBP [Coe 2/255]
8/255]
Ours [eear 2/255]
[eae B/255]
Ours [Grar 16/255]
Triee 0.1]
0.4
0.5
0.6
0.5
0.6
0.7
0.4
0.5
0.7
0.8
Test Accuracy
Figure 14: Compares PGD (Erest 2/255) and test accuracy of our models against IBP CIFARIO.
CIFAR10
8/255]
CIFARIO Medium
CIFAR10
0.5
Noninal
Rabustress
IEP
[fonn
0.3
T6P
[fum
6/2551
[tew 2/255]
0.2
Ours [fan B/255]
0.1
[fma 16/255)
Durs [frn C.3]
0.0
0.4
0.5
0.6
0.7
0.8
0.4
0.5
0.6
0.7
0.8
0.4
0.5
0.6
0.7
0.8
Test Accuracy
Figure 15: Compares PGD (Erest 8/255) and accuracy of our models against IBP on CIFARIO.
CIFAR10 Small Isee 16/255]
CIFAR10 Medium [Ceat = 16/255]
CIFAR10 Large [Cuu 16/255)
0.5
Nominal
PGD Robusress
IBP [Cre 2/255]
8/255)
Ours [eeer 2/255)
[ere 8/255]
Ours [Gaer 16/255]
0.1
Te 0.1]
0.0
0.4
0.5
0.6
0.8
0.5
0.6
0.7
0.1
0.5
0.7
0.8
Test Accuracy
Figure 16: Compares PGD (Etest 16/255) and test accuracy of our models against IBP on CIFARIO 10.
CIFAR10
CIFAR10 Medium
CIFARIO
0.35
Noninal
RSD Rabushess
IBP
2/255]
0.25
IBP
[fme 8/255]
0.20
2/25]
Ours
[fie 8/255]
0.10
[fme 16/555
Ours [fiee 0.11
0.00
0.4
0.5
0.6
0.7
0.4
0.5
0.6
0.7
0.4
0.5
0.8
0.7
Test Accurocy
Figure 17: Compares PGD (Erest 0.1) and test accuracy of our models against IBP CIFARI0.
23

---

Under review as a conference paper at ICLR 2020
E FAILURE EXAMPLE FOR OUR BOUNDS
In this section, we show faliure example to when the network weights do not follow Gaussian Assumption I bounds can be far too loose even compared to IBP. Consider layer neural network where A 1000 Laxss b1 = -99 1,, ag = -10 1, and b2 = for the interval [-Ins InJ. Then, we have that
1 b 1
+ 1000 999 - I,, In-
Since 2 0, then M = Ixx- Thereafter our estimated bounds as given by Equation 3 are given as:
LM, UM a bi F c/a, A,
9990n F 10000 e1,,1, 10m, 19990n.
As for IBP bounds, they are given follows:
max(u, u, 0,,) + max(1.0)
max(u, (,, 0,,) max 0)
LIBP, UIPP = a2
F |a
2
2
10
10 1,
1,1,, F
-00n
2
Under this construction of weights the network, different of the i.i.d Gaussian assumption, it clear that our bounds can be orders of magnitude looser to IBP. In the following section, we demonstrate that networks trained on real data do have weights that not far from the Gaussian assumption by empirically investigating the histogram of the network weights.
24

---

Under review as a conference paper at ICLR 2020
F HISTOGRAM OF WEIGHTS OF TRAINED NETWORKS
To quantify how reasonable the assumption of Gaussian i.id weights in trained networks, we train medium CNN (discussed in previous section) and show the histogram of the weights of the first layers. The network trained with and without E regularization on three datasets namely MNIST, CIFARIO and CIFARIOU
F.1 HISTOGRAM OF WEIGHTS ON MNIST
Histogram of convl
Histogram conv2
Histogram conv3
0.04
0.03
0.03
0.03
0.02
0.02
0.02
0.01
0.01
0.01
0.00
0.00
0.00
-0.4
-0.2
0.0
0.2
04
-0.2
0.0
0.2
-0.4
-0.2
0.0
0.2
Histogram of fc1
Histogram of fc2
Histogram of fc3
0.04
0.04
0.06
0.03
0.03
0.04
0.02
0.02
0.02
0.01
0.00
0.00
0.00
-0.2
0.0
02
-0.1
0.0
0.1
0.2
-0.1
0.0
0.1
0.2
Figure 18: Histogram of weights of medium CNN trained on MNIST without & regularization.
Histogram convl
Histogram conv2
Histogram conv3
0.100
0.075
0.2
0.050
0.1
0.1
0.025
0.000
0.0
0.0
-0.4
-0.2
0.0
0.2
0.4
-0.1
0.1
-0.2
-0.1
Histogram of fc1
Histogram of fc2
Histogram of fc3
0.4
0.4
0.4
0.3
0.3
0.2
0.1
0.1
0.0
0.0
0.0
-0.1
0.0
0.1
Figure 19: Histogram of weights of medium CNN trained on MNIST with & regularization.
25

---

Under review as a conference paper at ICLR 2020
F.2
HISTOGRAM OF WEIGHTS ON CIFAR10
Histogram of convl
Histogram conv2
Histogram conv3
0.04
0.06
0.04
0.04
0.02
0.02
0.01
0.00
0.00
0.00
-0.4
-0.2
0.0
0.2
0.4
-0.4
-0.2
0.0
0.2
0.4
-0.4
-0.2
0.0
0.2
Histogram of fc1
Histogram of fc2
Histogram of fc3
0.06
0.04
0.04
0.02
0.00
0.00
0.00
-0.2
0.0
0.2
-0.2
0.0
0.2
-0.5
0.0
Figure 20: Histogram of weights of medium CNN trained on CIFARIO without & regularization.
Histogram convl
Histogram conv2
Histogram conv3
0.4
0.2
0.2
0.1
0.1
0.00
0.0
0.0
0.0
0.0
-0.2
Histogram of fc1
Histogram of fc2
Histogram of fc3
0.4
0.6
0.4
0.4
0.3
0.
0.2
0.1
0.0
0.0
-0.2
0.0
0.0
02
-0.50
-0.25
Figure 21: Histogram of weights of medium CNN trained CIFAR10 with &a regularization.
26

---

Under review as a conference paper at ICLR 2020
F.3
HISTOGRAM OF WEIGHTS ON CIFAR100
Histogram of convl
Histogram conv2
Histogram conv3
0.06
0.04
0.02
0.02
0.02
0.00
0.00
0.00
-0.25
0.00
0.25
0.50
-0.50
-0.25
0.00
0.25
-0.4
-0.2
0.0
0.2
Histogram of fc1
Histogram of fc2
Histogram of fc3
0.08
0.06
0.03
0.04
0.02
0.04
0.02
0.02
0.01
0.00
0.00
0.00
-0.4
-0.2
0.0
0.2
-0.4
-0.2
0.0
02
0.4
-1.5
-1.0
-0.5
0.0
Figure 22: Histogram of weights of medium CNN trained on CIFARI00 without &2 regularization.
Histogram convl
Histogram conv2
Histogram conv3
0.4
0.4
0.04
0.3
0.2
0.2
0.02
0.1
0.00
0.0
0.4
-0.2
0.2
-0.4
-0.2
0.0
02
0.4
0.2
Histogram of fc1
Histogram of fc2
Histogram of fc3
0.3
0.4
0.2
0.1
0.0
0.0
0.0
-1.0
Figure 23: Histogram of weights of medium CNN trained on CIFAR100 with & regularization.
27

---

Under review as a conference paper at ICLR 2020
G REBUTTAL
G.1 REVIEWER 2
We thank R2 for their very thorough review of our paper. Regarding the disclaimer, we want to clarify to other reviewers too that we have indeed tried to address all R2's previous concerns in this submission. We have conducted some extra experiments from the previous submission; we have also done some serious changes to the structure and presentation of the paper as previously suggested by R2. In what follows we try addressing R2's s current concerns.
The logical argument explaining the "why" these are valid is harder to understand and could be clarified. My understanding so far ...
The overall description of R2 to the logical argument is correct. The proof is based showing that our bounds are 'supersets' to some approximate bounds Lppeox and U appreex. The approximate bounds are indeed related to the unknown true bounds through Assumption 1. Note that Assumption I states that there exists some m where the Assumption inequality holds. As we pointed out to RI, the larger the constant the larger n. has to be for Theorem to hold. Please refer to the last inequality in the proof of Theorem
The caption of Figure 1 is misleading. It says that it shows that the proposed...
True. This was a mistake of phrasing on our part. We have addressed this in the revised version.
The reporting of Figure 5 and 6 is weird because according to the text, each datapoint seems to be the average robustness of ...
We have addressed this in the revised version. The reported models had only their robustness averaged over multiple frest Please note that the robustness results over each individual érest were left for the appendix. The best models from the grid search over the hyperparameters are reported for both our bound training and IBP training for fair comparison.
appreciate the effort of the author to include experiments involving a MIP solver returning the true bounds. This is very helpful in building confidence that the bounds generated are correct. How is the real network trained? Is this based on robustly trained network or is just standard training? Is 99% the nominal accuracy?
Yes, 99% is the nominal accuracy of the trained models. The network was trained normally without any special regularization.
In general, I think that the paper would be better if there was more discussion of the failure modes of the method. There are easy identify failure cases where the proposed bound is incorrect or loose. My opinion is that the paper would be stronger if it acknowledged them
We agree with R2. We have addressed this in the revised version. In particular, we reflected this in the paragraph just before section 3.3. We have added in the appendix the example of the failure case pointed out by R2. Moreover, as suggested by RI, we have investigated, at least empirically, the histogram of the weights of a normally trained network on 3 real dataset in appendix F. In what follows, we re-state our response R1 in regards to the histogram results of the appendix R2 for completion. "For the MNIST experiments, even without f2 regularization, the weights seem to follow bell shaped. With E2 regularization, the histogram tend to be much pointy. Of course, the regularization parameter used in training interpolates between the two histograms. the larger the regularization the more 'pointy' the histogram will tend to be. A similar observation can be noted for CIFARIO 10 and CIFAR100. We want to emphasize that while this is not a proof that the Gaussian assumption holds in practice, believe that at least the distribution of the weights does not seem to be far from Gaussian and thereafter sheds light on why perhaps such an assumption may not be utterly unreasonable on real networks."
The assumption about gaussian weights in A1 and a2 seems strong but is at least partially motivated at the end of 3.2 (although not all networks are
R2 is correct. The i.i.d assumption over all elements of the weights matrix A breaks in the presence of topelitz/circulant structure convolutional layers have. This, unfortunately, is as far as the current theory can go. We find though that this have little impact on practically upon training the networks.
28

---

Under review as a conference paper at ICLR 2020
think that the paper would benefit from having some discussion of other methods that can derive "bounds" which may not actually be bounds. The works by Stefan Webb (A Statistical
Indeed, the two referenced works are related to our direction since both aim at either probabilistically carrying out the verification or by estimating the lower bound of the minimum perturbation. We claborated on this in the revised version and added a paragraph in the introduction.
While reviewing the paper, I also spotted some strong similarities between the methods pro- posed (particularly subsection 3.3) and the Fastlin method. The computation mechanism of Fastlin (propagate recursively from the end through the linear layers and through diagonal matrices that replace the ReLU activation function) is exactly the same as the proposed one (Fastlin goes through the...
The description of R1 for the intuition of the construction of the diagonal matrix M is correct. Indeed, there are similarities between both our work and Fastlin. However, we do not believe that the works are limited. Both works still provide an excellent trade-off between efficiency and computational complexity, even when over estimating the intermediate upper bounds for the intermediate M, the approximation for the superset bounds are still effective.
Minor comments, typos and references. We have addressed the issues in the revised version. We have also tried to address other issues and writing style highlighted by R2.
G.2 REVIEWER
We thank RI for the time spent in reviewing our paper. Follows our response to Rl's concerns.
Some assumptions seem pretty unrealistic to me. For instance, the fact that the neural net- work should have Gaussian i.i.d weights: it is thus
As correctly pointed out by R1, Gowal et al do not make such an assumption. They provide loose 'true' bounds for deep architectures as function of network parameters by simply computing worst case bound per layer. As suggested by RI, we have conducted an experiment where we trained Medium CNN with identical structure to previous experiments on MNIST, CIFARIO and on CIFARIO0 with and without f regularization. We then plot the histogram of the weights of the 6 layers in the network (3 convolutional and 3 fully connected). We report the results in Section E of the appendix in the revised version. For the MNIST experiments, even without l regularization, the weights seem to follow bell shaped. With Eg regularization, the histogram tend to be much pointy. Of course, the regularization parameter used in training interpolates between the two histograms, the larger the regularization the more 'pointy' the histogram will tend to be. A similar observation can be noted for CIFARIO and CIFARI00. We want to emphasize that while this is not a proof that the Gaussian assumption holds in practice, believe that at least the distribution of the weights does not seem to be far from Gaussian and thereafter sheds light on why perhaps such an assumption may not be utterly unreasonable on real networks.
A major difference with (Gowal al) that: here, the bounds are in expectation whereas the bound in (Gowal et al) are deterministic. In this paper, there are some approximation assumptions ...
This is true. Unfortunately, as far as the analysis goes, we do not yet have concentration results. One direction of interest is to study the asymptotic behaviour (in terms of and k) of the variance of Lm and UM over the distribution of network parameters. So far we have some little progress in that direction as the analysis becomes untraceable.
Most of the proofs are long and complicated, and several equations of 7-8 lines could be summarized with up to 2-3 lines maximum. I had a hard time to understand the proof of Theorem 1, which is simply some algebra. This could improved.
The equations were, for most part purposely, left to span multiple lines as we wanted to elaborate on each step of the analysis.
I'm curious of the imagenet performance: couldn't this technique be easily applied to AlexNet, which is nowadays simple to manipulate? Is there technical issue to do so?
29

---

Under review as a conference paper at ICLR 2020
While we were interested for the most part in the analysis, we do believe that the paper can benefit from the ImageNet experiments vastly. They were left out for time/computation capacity related reasons. We will try to address this within our capacity.
Is the assumption really an assumption? given a,a² and b, there always exists m such that a>=b-m and a <== like m>=max(la-blla"->) Am I wrong? I think do not understand this assumption...
Yes, Assumption is trivial. The key element to note from Assumption 1 is that there is some m (that could be very large) where this inequality holds. Now, the question is how does this constant m affect the analysis? Larger m results into requiring a larger input dimension n for Theorem to hold. To see this, refer to the last equation of the proof of Theorem 1. Note that the second term of the right hand side of the inequality is a function of m. This shows that the larger the constant m for the Assumption to hold, the larger the input dimension for the inequality to be positive and thereafter for Theorem to hold.
How simple is it to extend those theoretical results for NNs to the case of CNNs?
The results hold for generic linear operators and ag. For convolutional layers, the kernel can indeed be represented with a structured topelitz/cireulant matrix fitting into our analysis. However, we find a trick avoid the inefficient construction of such massive matrices. Note that to compute our bounds, one only needs to compute Eq (3) efficiently where A is convolutional kernel. For A x, this can be computed by simply performing convolution the input center x without constructing A (which is a forward pass through the layer). The tricky part comes upon computing the term |ag M | As one need to compute a MA1 first where M is a diagonal matrix without constructing A₁. The way we go about this is by simply taking a backward pass through the layer that computes a, MA for some input center then compute the gradients as a function of resulting in having access to a. MAj and thereafter computing a MA 1,, becomes efficient. Note that this has been employed in the experiments as the networks used did have convolutional layers.
function of x. That is we perform forward pass for some input center x and
G.3 REVIEWER 3
We thank R3 for their time reviewing the paper. Follows our response.
However, these results shown in Figs and 7 appear be somewhat inconsistent with those reported in the paper of IBP [Gowal et al., 2018)].
We would like raise to the attention of R3 that the metric used here is PGD robustness and not PGD accuracy. While they are to some extent related, the PGD robustness is the percentage of the testing samples where the network prediction was not altered under PGD attacks from the prediction of the network on the original samples regardless if the prediction is correct. Since the pretrained models of IBP were not made available, we trained models with IBP by running the code provided by the authors on their github page (with the same exact setup). Moreover, for fair comparison and stronger baselines, all IBP trained models were trained over different learning schedules. The best models with the highest securacy-robustned pair trade-off for IBP are reported.
I am not sure if it really makes sense to discuss which method is better in such ranges of failed defense.
We believe that so long the model accuracy on the noise free-samples is still preserved (captured on the x-axis of Figures 5 and 6) with an increase in robustness, this is good evidence for improvement. For instance, for CIFARIO on the small architecture (Figure 6), our models have improved the average robustness over all Exst (captured by y-axis) while preserving similar accuracy to the nominal model. This is unlike IBP, where despite that the robustness improved 30% the accuracy dropped by 20% compared to the nominal model.
Sources for differences to Gowal et. al.
Indeed, as correctly pointed by R3, the reported robustness is averaged over all tested e. However, note that report the robustness results for individual twe in the supplementary material (Figures 10-17). The range of feea for MNIST is identical to that of Gowal et. al.; however, the range for festt is indeed larger for CIFAR10 experiments.
30

---

Under review as a conference paper at ICLR 2020
Comment on the metric PGD Robustness and not PGD accuracy.
The focus our work to show an efficient approach to estimate the output bounds of a network. Since the bounds are only 'true' in expectation they can not be used for certification in the absence of concentration results to our bounds. To that extent, verified accuracy (aceuracy by running exact solvers) and its lower and upper bound estimates, certified accuracy and PGD accuracy respectively. do not make much sense in our framework. Therefore, we limit our experiments showcasing that such simple estimates of the bounds can be utilized to efficiently regularize networks to improve their robustness.
31


Reviews:
[{"review_id": "HyxiCSC6Kr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes some expected bounds in order to improve the robustness-accuracy trade-off on standard CNNs. The bounds numerically improve (Gowal et al), thus this method works numerically well.\n\nMy main concern is about the fact that several assumptions seem relatively constraining or are not quantitatively justified. Furthermore, I'm wondering if such bounds could be applied to Neural Tangent Kernel works. This could be useful and it would seem to correspond better to the setting of this work.\n\nPros:\n- The performances are quite good.\n- In expectation for random NNs, the proposed bounds are tighter.\n- The beginning of Section 4 conducts an interesting numerical study that tries to validate those bounds.\n\nCons:\n- Some assumptions seem pretty unrealistic to me. For instance, the fact that the neural network should have Gaussian i.i.d weights: it is thus surprising that this technique works in real-life settings. As far as I understood, this assumption is not done in (Gowal et al). Did the authors check that their CNNs had Gaussian weights? I'm not convinced by the paragraph at the end of section 3.2, yet a simple histogram to validate this claim would convince me.\n- A major difference with (Gowal et al) is that: here, the bounds are in expectation whereas the bound in (Gowal et al) are deterministic. In this paper, there are some approximation assumptions (e.g., large input, large number of hidden layers) without non-asymptotic arguments. For instance, I was sort of expecting some concentration inequalities that would allow to quantify how large should be the input dimension $n$ or the width $k$.\n- Most of the proofs are long and complicated, and several equations of 7-8 lines could be summarized with up to 2-3 lines maximum. I had a hard time to understand the proof of Theorem 1, which is simply some algebra. This could be improved.\n- I'm curious of the imagenet performance: couldn't this technique be easily applied to AlexNet, which is nowadays simple to manipulate? Is there a technical issue to do so?\n- Is the assumption 1 really an assumption? given a,a' and b,b' there always exists m such that a>=b-m and a'<=b'+m, like m>=max(|a-b|,|a'-b'|). Am I wrong? I think I do not understand this assumption...\n- How simple is it to extend those theoretical results for NNs to the case of CNNs?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlSowJ15B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Disclaimer: I have already reviewed this paper for another conference. I re-read it to assess the modifications made by the authors but I am aware of the comments that they received in the previous round of reviews. I'm also re-raising some concerns that I made in a previous review that the authors didn't address.\n\nSummary\nInterval Bound Propagation (IBP) is a fast method to propagate bounds through the activation of a Neural Network. It is however quite loose. The authors of this paper propose a different way of propagating the bounds, which is not a rigorous bound computation method, but for which they show that, with some strong assumptions on the distribution of the weights, the expectation of the generated results are valid bounds that are tighter than the ones generated by IBP.\n\nThe paper explains clearly the \"how\" of how these bounds are achieved. Equation 3 and the paragraph before it are good. (Essentially, as long as a ReLU is not in a \"blocking\" state where all its input are negative, treat it as an identity, and do a forward pass of the center of the input region). \nThe logical argument explaining the \"why\" these are valid is harder to understand and could be clarified. My understanding so far is:\n- All the analysis is dependent on all weights being drawn from iid gaussian of zero mean.\n- In addition to that, there is an assumption (Assumption 1) between the relation of bounds of network with random weight and some quantity (L_approx, U_approx) with random uniform inputs x. \nThe proof is done that the expectation of the bound proposed is \"correct\" with regards to (L_approx, U_approx) but then, the relation to the true bounds is given by the Assumption?\nSo the relation to the true bounds is only given by the Assumption?\n\nRegarding the experiments:\n* The caption of Figure 1 is misleading. It says that it shows that the proposed bounds are a super set of the interval bounds, while they are actually not (ratio is strictly smaller than 1). You can argue that they are close, but now that they are a superset when they aren't!\n* The reporting of Figure 5 and 6 is weird because according to the text, each datapoint seems to be the average robustness of networks trained with different hyperparameters, so it's hard to interpret.\n* I appreciate the effort of the author to include experiments involving a MIP solver returning the true bounds. This is very helpful in building confidence that the bounds generated are correct. How is the real network trained? Is this based on a robustly trained network or is it just standard training? Is 99% the nominal accuracy?\n\nIn general, I think that the paper would be better if there was more discussion of the failure modes of the method. There are easy to identify failure cases where the proposed bound is incorrect or loose. My opinion is that the paper would be stronger if it acknowledged them but then made the points that the bounds proposed are still good most of the time (which their experiment show) and useful (for example for training where the exact correctness of the bounds may not be the most important), rather than ignoring them and pretending that the bounds are perfect.\n[From previous review]\nSimple example of a network where the results would be quite loose, while IBP is tight:\nTwo layer NN, x = 0 \\in R^n, eps = 1, W1 = 1000 * Identity, b1 = -999 * 1_n, a2 = -10 1_{1,n} , b2 = 0\nu1 would be all positive, so the matrix M would simply be the identity.\nL_M = a2^T M b1 - eps | a2^T M A1| vec(1) = (-10)*(-999)*n - 10 * (1000) * n = -19990 * n\nU_M = a2^T M b1 + eps | a2^T M A1| vec(1) = (-10)*(-999)*n + 10 * (1000) * n = n\nThe actual bound (which also correspond in that case to what would be computed by IBP) is\nL_gt = -10*n\nu_gt = 0\n\nComments:\n* \"We prove to be true bounds in expectation\" -> This is a bad formulation that should be rephrased. The expectation of the proposed bound is correct with regards to the expectation of the true bounds, but \"True in expectation\" is a bad formulation that doesn't reflect what is happening. Maybe True in expectation would mean that E_{A_1, a_2}(indicator(L_true > L_M)) -> 1 as n grows\n\n* The assumption about gaussian weights in A1 and a2 seems strong but is at least partially motivated at the end of 3.2 (although not all networks are trained with l2 regularizer) What about the iid assumption? In case of a CNN for example, the weights are shared, so definetely won't fit this framework?\n\n* I think that the paper would benefit from having some discussion of other methods that can derive \"bounds\" which may not actually be bounds. The works by Stefan Webb (A Statistical Approach to Assessing Neural Network Robustness, ICLR 2019) or Tsui Wei Weng (Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach, ICLR 2018) being others of the top of my head . While this paper clearly propose to do things very differently, I think the discussion would have been very valuable.\n\n* While reviewing the paper, I also spotted some strong similarities between the methods proposed (particularly subsection 3.3) and the Fastlin method. The computation mechanism of Fastlin (propagate recursively  from the end through the linear layers and through diagonal matrices that replace the ReLU activation function) is exactly the same as the proposed one (Fastlin goes through the notational burden of handling the bias). The only difference is in the way the coefficients of the diagonal matrix are computed. (here, it's 0 if the Relu is blocking, and 1 otherwise. Fastlin has 0 if blocking, 1 if passing but a coefficient in between (u/u-l) if the reLU is ambiguous).\nIf that connection is correct, then the benefits of the proposed methods are limited: neither Fastlin nor IBP dominate each other, and the computational costs for Fastlin is higher, due to having to propagate the full linear maps here noted G from the end to the input to obtain the bounds, as the authors seem to have also realised (\"it is expensive to compute our bounds using the procedure in Section 3.3, so instead, we obtain matrices Mi using the easy-to-compute IBP upper bounds.\")\n\nOpinion:\nI am bothered by the framing of the results that the authors employ, as their theoretical results are, to the best of my understanding, dependent on strong assumptions. Some of the experimental results are also over-exaggerated (caption saying that things are superset while the experimental results show something different), and the relation and contextualization with regards to existing literature is lacking ( both against other works with similar aims but different methods, and with works with similar method but a slightly different aim)\n\nTypos:\nPage 7, \"are are much\"\nPage 8,\"When kappa=0\", no need for uppercase\nThe references should ideally be cleaned and put in a consistent format. In the text of the paper, Some citation have first name + last name of one author, some have two out of all the authors, some have the et al. format.... It's all over the place. \nIn the References section, some authors list are shuffled (at least the \"Scaling provable adversarial\" paper), some are missing the conference where paper where cited and just cite the arxiv version", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xvtsu2Fr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I understand that the proposed bound is derived based on a few assumptions, which do not necessarily hold true in real cases, and thus it is only an approximate bound, meaning that the bound is not theoretically guaranteed to be a ‘superset’ of the true bound. In fact, in both Fig.1 (dealing with ideal conditions) and Table 1 (dealing with a real task (MNIST)), \\Gamma, which is an indicator that should be 1 if the proposed bound is the superset, is not always 1. \n\nTherefore, it is fair to say that the practical value of the proposed approach depends on its performance on real tasks. This is supposed to be judged mainly from Fig.6 (MNIST) and Fig.7 (CIFAR-10). My first impression is that it is hard to see the expected accuracy-robustness trade-offs from them and the results appear rather random. That said, there are several cases for which the proposed method show better accuracy and robustness than IBP, as is claimed in the paper. \n\nHowever, these results shown in Figs 6 and 7 appear to be somewhat inconsistent with those reported in the paper of IBP [Gowal et al., 2018)]. They are summarized in Table 4 of [Gowal et al., 2018)], where IBP achieves PCD accuracy 97.9, 96.1, 93.9, and 89.7% on MNIST for \\epsilon_{test}=0.1, 0.2, 0.3, and 0.4, respectively, and achieves 55 and 35% on CIFAR-10 for \\epsilon_{test}=2/225 and 8/225, respectively. On the other hand, in Figs 6 and 7 of this paper, the PCD accuracies of IBP and the proposed method distribute in the range of 30-70% for MNIST (Fig.6) and 5-20% for CIFAR-10 (Fig.7). Considering that the accuracy under no attack is greater than 98% on MNIST and 50% on CIFAR-10, we should consider that the defense practically fails in these ranges. I am not sure if it really makes sense to discuss which method is better in such ranges of failed defense.\n\nThis difference from [Gowal et al., 2018)] seems to come from i) the employment of the average PGD robustness over all \\epsilon_{test}’s for Figs. 6 and 7, as in the statement: ”To compare training methods, we compute the average PGD robustness over all εtest and the test accuracy, and report them in a 2D scatter plot“; and ii) the range of \\epsilon_{test} is wider than [Gowal et al., 2018)]. I think that the evaluation in [Gowal et al., 2018)] is conducted in the range that the defense is regarded to be successful, and thus is more appropriate. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new technique for training networks to be robust to adversarial perturbations. They do this by computing bounds on the impact of the worst case adversarial attack, but that only hold under strong assumptions on the distribution of the network weights. While these bounds are not rigorous, the authors show that they can produce networks that improve the robustness-accuracy tradeoff on image classification tasks.

While the idea proposed by the authors is interesting, the reviewers had several concerns about this paper:
1) The assumptions required for the bounds to hold are unrealistic and unlikely to hold in practice, especially for convolutional neural networks.
2) The comparisons are not presented in a fair manner that allow the reader to interpret the difference between the nature of certificates computed by the authors and those computed in prior work.
3) The empirical gains are not substantial if one normalizes for the non-rigorous nature of the certificates computed (given that they only hold under hard-to-justify assumptions).

The rebuttal phase clarified some issues in the paper, but the fundamental flaws with the approach remain unaddressed. Thus, I recommend rejection and suggest that the authors revisit the assumptions and develop more convincing arguments and/or experiments justifying them for practical deep learning scenarios.
Decision: Reject