Title: EXPECTED TIGHT BOUNDS FOR ROBUST DEEP NEURAL NETWORK TRAINING Anonymous

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. ( 2019) 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 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.

1. 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., 2016) 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 attacks. 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, Moosavi-Dezfooli 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 a wide range of DNNs across a large number of input samples. More recently, it was shown that such adversaries can also be as simple as Gaussian noise (Bibi et 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-driving 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., 2018; Wong & Kolter, 2018; Raghunathan et al., 2018; Alfadly et al., 2019) . 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 et al., 2017; Sankaranarayanan et al., 2016; Weng et al., 2018a) . 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 to minimize the exact (or upper bound) of the worst adversarial loss over all possible bounded energy (often measured in ∞ norm) perturbation around a given input.

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, Gowal 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. (2018) . In particular, they propagate the -∞ norm bounded input centered at x ∈ R n , i.e. [x -1 n , x + 1 n ], 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 a binary measure of robustness per sample, they propose to frame verification as a probability of 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., 2018b) 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 -∞ 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 are in expectation, under a distribution of network parameters, supersets to the true bounds of this block. Moreover, 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 CIFAR10 (Krizhevsky & Hinton, 2009) achieving state-of-art robustness-accuracy trade-off compared to IBP. In other words, we can consistently improve robustness by significant margins with minimal effect on test accuracy as compared to IBP.

2. RELATED WORK:

Training accurate and robust DNNs remains an elusive problem, since several works have demonstrated 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 maximizing the loss with respect to the input for a single iteration (Goodfellow et al., 2014) , one can easily 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 or relaxed verifiers.

Exact Verification. Verifiers of this type try to find the exact largest adversarial loss over all possible bounded energy (usually measured in ∞ 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; Lomuscio & Maganti, 2017; Tjeng & Tedrake, 2019) or Satisfiability Modulo Theory (SMT) solvers (Xiaowei Huang & Wu, 2017; Ehlers, 2017) . 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 networks of at most 3 hidden layers. The verification is fast for networks that are pretrained with a 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 al. (2018c) proposed ReluVal for network verification based on symbolic interval bounds, while Wang et al. (2018b) 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 a large number of recent works in a 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 an inherent barrier compared to exact verifiers.

For completeness, it is 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 a 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 a 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 as compared to layerwise IBP. The tighter bounds enable the use of simple standard training routines for robust training of large networks, resulting in state-of-art robustness-accuracy trade-off.

3. EXPECTED TIGHT INTERVAL BOUNDS:

We analyze the interval bounds of a DNN by proposing expected true and tight bounds for a two-layer network (Affine-ReLU-Affine). Then, we propose a mechanism to extend them for deeper networks. First, we detail the interval bounds of Gowal 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 1 ∈ R k×n and b 1 ∈ R k , it is easy to show that its output lower and upper interval bounds for an -∞ norm bounded input x ∈ [x -1 n , x + 1 n ] are:

l 1 = A 1 x + b 1 -|A 1 |1 n , u 1 = A 1 x + b 1 + |A 1 |1 n .

(1) Note that |.| is an elementwise absolute operator. In the presence of any non-decreasing elementwise nonlinearity (e.g. ReLU), the bounds can then be propagated by applying the nonlinearity to {l 1 , u 1 } directly. As such, the interval bounds can be propagated through the network one layer at a time, as proposed by Gowal 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 AFFINE-RELU-AFFINE BLOCK:

Here, we consider a block of layers of the form Affine-ReLU-Affine in the presence of ∞ perturbations at the input. The functional form of this network is:

g(x) = a 2 max (A 1 x + b 1 , 0) + b 2 ,

where max(.) is an elementwise operator. The affine mappings can be of any size, and throughout the paper, we take A 1 ∈ R k×n and without loss of generality the second affine map is a single vector a 2 ∈ R k . 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) 

L IBP = a 2 max (u 1 , 0 k ) + max (l 1 , 0 k ) 2 -|a 2 | max (u 1 , 0 k ) -max (l 1 , 0 k ) 2 + b 2 , U IBP = a 2 max (u 1 , 0 k ) + max (l 1 , 0 k ) 2 + |a 2 | max (u 1 , 0 k ) -max (l 1 , 0 k ) 2 + b 2 .

Note that max (l 1 , 0 k ) and max (u 1 , 0 k ) are the result of propagating [x -1 n , x + 1 n ] through the first affine map (A 1 , b 1 ) and then through the ReLU nonlinearity, as stated in (1).

Expected Tight Interval Bounds on g. 

Analysis.:

To derive L M and U M , we study the bounds of the following function first:

EQUATION

Note that g is very similar to the Affine-ReLU-Affine map captured by g with the ReLU replaced by a diagonal matrix M constructed as follows. If we denote u 1 = A 1 x + b 1 + |A 1 |1 n as the upper bound resulting from the propagation of the input bounds [x -1 n , x + 1 n ] through the first affine map (A 1 , b 1 ), then we have M = diag (1 {u 1 ≥ 0 k }) where 1 is an indicator function. In other words, M ii = 1 when the i th element of u 1 is non-negative and zero otherwise. Note that for a given u 1 , g(x) is an affine function with the following output interval bounds for x ∈ [x -1 n , x + 1 n ]:

EQUATION

To compare L M and U M to L true and U true , respectively, and since having access to L true and U true is not feasible, we make the following mild key assumption. Assumption 1. (Key Assumption). Consider an ∞ bounded uniform random variable x, x ∈ [x -1 n , x + 1 n ] where A 1 and a 2 have elements that are i.i.d. Gaussian of zero mean and σ A1 and σ a2 standard deviations, then there exists a sufficiently large m, such that:

E A1,a2 [L true ] ≥ L approx = E A1,a2,x [g(x)] -m Var A1,a2,x [g(x)], E A1,a2 [U true ] ≤ U approx = E A1,a2,x [g(x)] + m Var A1,a2,x [g(x)].

Under Assumption 1 and to show that L M and U M are true bounds in expectation, it is sufficient to show that L approx ≥ E A1,a2 [L M ] and similarly for U M . However, since it is generally difficult to compute the right hand sides of Assumption 1, they can be well approximated by Lyapunov Central Limit Theorem. More formally, follows the two propositions. Proposition 1. For a ∈ R n ∼ N (0, σ 2 a I) and a uniform random vector x ∼ U[x -1 n , x + 1 n ] where both a and x are independent, we have that Lyapunov Central Limit Theorem holds such that

1 s n n i=1 (x i a i -E[a i xi ]) → d N (0, 1), where s 2 n = Var n i=1 (x i a i -E[a i xi ])

where → d indicates convergence in distribution.

Proposition 2. For a random matrix A 1 with i.i.d. Gaussian elements of zero mean and σ A1 standard deviation and a uniform random vector Figure 1b shows that a similar behaviour is present even under varying network depth.

x ∼ U [x -1 n , x + 1 n ] we have that Covariance(Ax) = ( 1 3 2 σ 2 A1 n + σ 2 A1 trace(xx ))I.

Following Propositions 1 and 2, we have that for a sufficiently large input n:

EQUATION

)

where the output of the first affine layer

EQUATION

Theorem 1 states that the interval bounds for function g are simply looser bounds to the function of interest g in expectation under a plausible distribution of A 1 and a 2 . Now, we investigate the tightness of these bounds as compared to the IBP bounds

[L IBP , U IBP ]. Theorem 2. (Tighter Bounds in Expectation) Consider an ∞ bounded uniform random variable input x ∈ [x -1 n , x + 1 n ]

to a block of layers in the form of Affine-ReLU-Affine (parameterized by A 1 , b 1 , a 2 and b 2 for the first and second affine layers respectively) and a 2 ∼ N (0, σ a2 I). Under the assumption that 1

√ 2π x j 1 k A 1 (:, j) + 1 2n 1 k b 1 ≥ A 1 (:, j) 2 -1 √ 2π A 1 (:, j) 1 ∀j, we have: E a2 [(U IBP -L IBP ) -(U M -L M )] ≥ 0.

Theorem 2 states that under some assumptions on A 1 and under a plausible distribution for a 2 , our proposed interval width can be much smaller than the IBP interval width, i.e. 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 (A 1 , b 1 ) satisfy it, and the following proposition gives an example that does so in expectation.

Proposition 3. For a random matrix A 1 ∈ R k×n with i.i.d elements A 1 (i, j) ∼ N (0, 1), then

E A1 A 1 (:, j) 2 - 1 √ 2π A 1 (:, j) 1 = √ 2 Γ k+1 2 Γ k 2 -k 2 π ≈ √ k 1 - 2 π √ k .

Proposition 3 implies that as the number of hidden nodes k 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 1 ∼ N (0 k , I). In other words, for Gaussian zero-mean weights (A 1 , b 1 ) 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 1 and a 2 . Generally speaking, our proposed bounds [L M , U M ] computed using Equation 3 can be very loose and much worse compared to IBP if the network weights A 1 , a 2 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 2 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, CIFAR10, CIFAR100). with and without 2 regularization See appendix for details. 

3.3. EXTENDING OUR EXPECTED TIGHT BOUNDS TO DEEPER NETWORKS:

To extend our proposed bounds to networks deeper than a two-layer block, we simply apply our bound procedure described in Section 3.2, recursively for every block. In particular, consider an L-layer neural network defined as

f (x) = A L ReLU(A L-1 ReLU(• • • A 2 ReLU(A 1 x))) and an - ∞ norm bounded input centered at x, i.e. x ∈ [x -1 n , x + 1 n ].

Without loss of generality, we assume f is bias-free for ease of notation. Then, the output lower and upper bounds of f are

L M = G L-1 x -|G L-1 |1 n and U M = G L-1 x + |G L-1 |1 n , respectively.

Here, G L-1 is a linear map that can be obtained recursively as follows:

G i = A i+1 M i G i-1 (with G 0 = A 1 ) and M i = diag (1 {(G i-1 x + |G i-1 |1 n ) ≥ 0}) (6) Note that G i-1 x + |G i-1

|1 n is the output upper bound through a linear layer parameterized by G i-1 for input x as in (1). With this blockwise propagation, the output interval bounds of f are now estimated by the output intervals of f (x) = G L-1 x.

4. EXPERIMENTS:

True Bounds in Expectation. Here, we validate Theorem 1 with several controlled experiments. For a network g

(x) = A 2 max (A 1 x + b 1 , 0) + b 2 that has true bounds [L true , U true ] for x ∈ [x -1 n , x + 1 n ],

we empirically show that our proposed bounds [L M , U M ], under the mild assumptions of Theorem 1, indeed are true, i.e. they are a super set to [L true , U true ] in expectation. We also verify this as a function of the network input dimension n (as predicted by Theorem 1).

We start by constructing a network g where the biases b 1 ∈ R k and b 2 ∈ R are initialized following the default Pytorch initialization (Paszke et al., 2017) . As for the elements of the weight matrices A 1 ∈ R k×n and A 2 ∈ R 1×k , they are sampled from N (0, 1/ √ n) and N (0, 1/ √ k), respectively. We estimate L true and U true by taking the minimum and maximum of 10 6 + 2 n Monte-Carlo evaluations of g. For a given x ∼ N (0 n , I) and with = 0.1, we uniformly sample 10 6 examples from the interval [x -1 n , x + 1 n ]. We also sample all 2 n corners of the hyper cube [x -1 n , x + 1 n ] n . To show that the proposed interval [L M , U M ] is a super set of [L true , U true ] (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

Γ = |[L M , U M ] ∩ [L true , U true ]|/|[L true , U true ]|. Note that Γ = 1 if and only if [L M , U M ] is a super set of [L true , U true ].

For a given n, we conduct this experiment 10 3 times with varying A 1 , A 2 , b 1 , b 2 and x and report the average Γ. Then, we run this for a varying number of input size n and a varying number of hidden nodes k, as reported in Figure 1a . As predicted by Theorem 1, Figure 1a 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 k = 1000, require no more than n = 15 input dimensions for the proposed intervals to be a super set of the true intervals. In practice, n is much larger than that, e.g. n ≈ 3 × 10 3 in CIFAR10.

In Figure 1b , we empirically show that the above behavior also holds for deeper networks. We propagate the bounds blockwise as discussed in Section 3.3 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 k = n. These results indeed suggest that the proposed bounds are true bounds and are more likely so with larger input dimensions. Here, n = 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 et al., 2019) . In particular, we validate Theorem 2 by comparing the interval length of our proposed bounds, W M = U M -L M , with that of IBP, W IBP = U IBP -L IBP , 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 the average width difference and ratio over 10 3 runs in a similar setup to 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 = 0.1. Similar improvement occurs with increasing n, as in Figures 2c and 2d .

We also compare the tightness of our bounds to those of IBP with increasing depth for both fullyconnected networks (refer to Figures 3a and 3b ) and convolutional networks (refer to Figures 3c and 3d ). For all fully-connected networks, we take n = k = 500. Our proposed bounds get consistently tighter as the network depth increases over all choices of . In particular, the proposed bounds can be more than 10 6 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 i using the easy-to-compute 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. (2019) , 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, we use the MIP formulation by Tjeng & Tedrake (2019). We then report Γ over varying testing . Table 1 demonstrates that indeed even on real networks beyond two layers and without the Gaussian weight Figure 5 : Better Test Accuracy and Robustness on MNIST. We compare the PGD robustness 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 train, but we eliminated all models with test accuracy lower than 97.5%. Our results demonstrate an impressive trade-off between accuracy and robustness and, in some cases (medium and large models), we excel in both.

Figure 6 : Better Test Accuracy and Robustness on CIFAR10. We compare the PGD robustness and test accuracy of three models (small, medium, and large) robustly trained on the CIFAR10 dataset using our bounds and those robustly trained with IBP. We eliminated all models with test accuracy lower than 40.0%. PGD robustness is averaged over multiple test (refer to appendix).

distributed assumption, our bounds are still a super set to the true bounds computed with an MIP formulation. Moreover, Table 1 also 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 et al., 2019) 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 is used), and those trained robustly with IBP (Gowal et al., 2019) . Given the wellknown 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 to the one proposed in (Gowal et al., 2019) . In particular, we use L = (f θ (x), y true ) + κ (z, y true ), where , f θ (x), y true , and κ are the cross-entropy loss, output logits, true class label, and regularization hyperparameter respectively. z 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 κ = 0. Due to the tightness of our bounds, in contrast to IBP, we follow a standard training procedure that avoids the need to vary κ or train during training.

Specifically, we train three network models (small, medium, large) provided by Gowal et al. (2019) on both MNIST and CIFAR10. See appendix for more details. Following the same setup in (Gowal et al., 2019) , we train all models with train ∈ {0.1, 0.2, 0.3, 0.4} and train ∈ {2/255, 8/255, 16/255, 0.1} on MNIST and CIFAR10, 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 a 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 test ∈ {0.1, 0.2, 0.3, 0.4} for MNIST and for all test ∈ {2/255, 8/255, 16/255, 0.1} for CIFAR10. 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. We report the performance results on MNIST and CIFAR10 for the small, medium, and large architectures in Figure 5 . For all trained architectures, we only report the results for those that achieve at least a test accuracy of 97.5% and 40% on MNIST and CIFAR10, respectively; otherwise, it is an indication of failure in training. Interestingly, our training scheme can be used to train all architectures for all train . This is unlike IBP, which for example was only able to successfully train the large architecture with train = 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 a Affine-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 our 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.

Proposition 1. For a ∈ R n ∼ N (0, σ 2 a I) and a uniform random vector x ∼ U[x -1 n , x + 1 n ] where both a and x are independent, we have that Lyapunov Central Limit Theorem holds such that

1 s n n i=1 (x i a i -E[a i xi ]) → d N (0, 1), where s 2 n = Var n i=1 (x i a i -E[a i xi ])

where → d indicates convergence in distribution.

Proof. The Lyapunov condition

∃δ > 0, 1 s 2+δ n n i=1 E xi a i -E[a i xi ] 2+δ → 0, as n → ∞ (7)

is sufficient for Lyanunov Central Limit Theorem to hold. Note that

EQUATION

Since for δ = 2, we have that

E[|a i xi | 2+δ ] = ∞ -∞ xi+ xi- a 2 i x2 i 1 2 1 √ 2πσ a exp - a 2 i 2σ 2 a da i dx i = 3σ 4 a 2 xi+ xi- x4 i dx i = 3σ 4 a 10 (x i + ) 5 -(x i -) 5 .

Thereafter, Lyanunov Central Limit Theorem with δ = 2 is satisfied since

lim n→∞ 1 s 4 n n i=1 E xi a i -E[a i xi ] 2+δ = lim n→∞ 1 s 4 n n i=1 E xi a i 4 = lim n→∞ 3 n i=1 (x i + ) 5 -(x i -) 5 10 n 2 3 + n i=1 x 2 i 2 ≤ lim n→∞ 3n (x max + ) 5 -(x min -) 5 10 n 2 3 + n i=1 x 2 i 2 = 0

Proposition 2. For a random matrix A 1 with i.i.d. Gaussian elements of zero mean and σ A1 standard deviation and a uniform random vector

x ∼ U [x -1 n , x + 1 n ] we have that Covariance (Ax) = 2 σ 2 A 1 n 3 + σ 2 A1 trace xx I.

Proof. The former follows from the fact that

Covariance (A 1 x + b 1 ) = Covariance (A 1 x) = E A 1 xx A 1 -E [A 1 x] (E [A 1 x]) = E A 1 xx A 1 = E A1 A 1 E xx A 1 = E A1 A 1 Diag 2 3 + xx A 1 = 2 3 E A1 A 1 A 1 + E A 1 xx A 1 = 2 3 E A1 A 1 A 1 + σ 2 A1 trace xx I = 2 σ 2 A1 n 3 + σ 2 A1 trace xx I

The last equality follows since:

E A 1 xx A 1 i,j = E a i xx a j = trace xx E a j a i = 0 if i = j σ 2 A1 trace xx if i = j

Theorem 1. (True Bounds in Expectation) Let Assumption 1 hold. We have that for large input dimension n,

E A1,a2 [L M ] ≤ E A1,a2 [L true ] , E A1,a2 [U true ] ≤ E A1,a2 [U M ] .

Proof.

L approx ≈ E a2,ỹ a 2 max (ỹ, 0) + b 2 -m Var a2,ỹ a 2 max (ỹ, 0) + b 2 x = b 2 -m E a2 Var ỹ a 2 max (ỹ, 0) + b 2 |a 2 + Var a2 E ỹ a 2 max (ỹ, 0) + b 2 |a 2 = b 2 -m E a2 (a 2 a 2 ) E ỹ max 2 (ỹ, 0) -(E ỹ [max (ỹ, 0)]) 2 + Var a2 E ỹ a 2 max (ỹ, 0) + b 2 |a 2 1 2 = b 2 -m k i=1 σ 2 a2 E ỹ max 2 (ỹ, 0) i - k i=1 σ 2 a2 (E ỹ [max (ỹ, 0)]) 2 i + k i=1 σ 2 a2 (E ỹ [max (ỹ, 0)]) 2 i 1 2 = b 2 -mσ a2 k i=1 (E ỹ [max 2 (ỹ, 0)]) i y = b 2 -mσ a2 b 2i 1 + σ 2 ỹ Φ b i 1 σ ỹ + b i 1 σ ỹ φ b i 1 σ ỹ Ψ .

Note that x follows by total expectation and total variance on the two terms, respectively. Lastly, y 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 ỹ ∼ N b 1 ,

2 σ 2 A 1 n 3 + σ 2 A1 trace xx I and that σ 2 ỹ = 2 σ 2 A 1 n 3 + σ 2 A1 trace xx . L approx -E A1,a2 [L M ] ≈ b 2 -mσ a2 Ψ -E A1,a2 a 2 M (A 1 x + b 1 ) + b 2 -|a 2 MA 1 |1 = E A1,a2 |a 2 MA 1 |1 -mσ a2 Ψ = E A1   n j=1 E a2 |a 2 MA 1 (:, j)| A 1   -mσ a2 Ψ x = 2 π E A1   n j=1 Var a2 a 2 MA 1 (:, j))   -mσ a2 Ψ = σ a2 2 π E A1   n j=1 A 1 (:, j) MA 1 (:, j)   -mσ a2 Ψ = σ a2 2 π E A1   n j=1 k i=1 A 1 (i, j) 2 1 u i 1 ≥ 0   -mσ a2 Ψ = σ a2 2 π E |S|   E A1   n j=1 k i∈S A 1 (i, j) 2   | |S|   -mσ a2 Ψ

Note that x 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 u i 1 ≥ 0 for all i ∈ S. Since u 1 is random, then

|S| is also random. Therefore, one can reparametrize the sum and thus we have

σ a2 2 π E |S|   E A1   n j=1 k i∈S A 1 (i, j) 2   | |S|   = 2 σ A1 σ a2 n √ π E |S|   Γ |S|+1 2 Γ |S| 2   ≈ 2 σ A1 σ a2 n √ π E |S| |S| 2 ≥ 2 σ A1 σ a2 n √ π k 2

The approximation follows from stirlings formula Γ( x+1 /2) /Γ( x /2) ≈ x /2 for large x where the last

inequality follows since E |S| ≤ k]. L approx -E A1,a2 [L M ] ≥ 2 σ A1 σ a2 n √ π k 2 x -mσ a2 k i=1 b 2i 1 + σ 2 ỹ Φ b i 1 σ ỹ + b i 1 σ ỹ φ b i 1 σ ỹ y Note that x is O(n) while y is O( √ n).

Thus, for sufficiently large input dimension n we have that L approx ≥ E A1,a2 [L M ] and since by construction E A1,a2 [L true ] ≥ L approx which completes the proof. Note that a symmetric argument can be applied to show that

E A1,a2 [U M ] ≥ E A1,a2 [U true ].

Theorem 2. (Tighter Bounds in Expectation) Consider an ∞ bounded uniform random variable input x, i.e. x ∈ [x -1 n , x + 1 n ], to a block of layers in the form of Affine-ReLU-Affine (parameterized by A 1 , b 1 , a 2 and b 2 for the first and second affine layers respectively) and a 2 ∼ N (0, σ a2 I).

Under the assumption that:

1 √ 2π x j 1 k A 1 (:, j) + 1 2n 1 k b 1 ≥ A 1 (:, j) 2 -1 √ 2π A 1 (:, j) 1 ∀j, we have: E a2 [(U IBP -L IBP ) -(U M -L M )] ≥ 0. Proof. Note that [(U IBP -L IBP ) -(U M -L M )] = |a 2 ||A 1 |1 n + 1 2 |a 2 ||u 1 | - 1 2 |a 2 ||l 1 | -2 | a 2 diag (1 {u 1 ≥ 0}) A 1 | 1 n

Consider the coordinate splitting functions S ++ (.), S +-(.), S --(.) and S -+ (.) such that for

x ∈ R n S ++ (x) = x 1 u i 1 ≥ 0, l i 1 ≥ 0 where 1 u i 1 ≥ 0, l i 1 ≥

0 is a vector of all zeros and 1 in the locations where both u i 1 , l i 1 ≥ 0. However, since u 1 ≥ l 1 , then S -+ (.) = 0. Therefore it is clear that for any vector x and an interval [l 1 , u 1 ], we have that

EQUATION

since the sets {i;

u i 1 ≥ 0, l i 1 ≥ 0}, {i; u i 1 ≥ 0, l i 1 ≤ 0} and {i; u i 1 ≤ 0, l i 1 ≤

0} are disjoints and their union {i = 1, i = 2, . . . , i = k}. We will denote the difference in the interval lengths as W IBP -W M for ease of notation. Thus, we have the following:

W IBP -W M = S ++ |a 2 | |A 1 |1 n + S +-|a 2 | |A 1 |1 n + S --|a 2 | |A 1 |1 n + 1 2 S ++ |a 2 | |u 1 | + 1 2 S +-|a 2 | |u 1 | + 1 2 S --|a 2 | |u 1 | - 1 2 S ++ |a 2 | |l 1 | - 1 2 S +-|a 2 | |l 1 | - 1 2 S --|a 2 | |l 1 | -2 S ++ a 2 + S +-a 2 + S --a 2 diag (1 {u 1 ≥ 0}) 1 n = 2 S ++ |a 2 | |A 1 |1 n + S +-|a 2 | (A 1 x + b 1 ) + S +-|a 2 | A 1 1 n -2 S ++ a 2 + S +-a 2 A 1 1 n = 2 S ++ |a 2 | |A 1 |1 n x + S +-|a 2 | u 1 y -2 S ++ a 2 + S +-a 2 A 1 1 n z .

Note that we used the property of the coordinate splitting functions defined in Eq 9 along with the definitions of The previous The penultimate equality follows since S ++ (.) and S +-(.) corresponds to the indices that are selected by l 1 and u 1 . The penultimate equality follows since S ++ and S +- corresponds to the indices that are selected by diag (1 {u 1 ≥ 0}).

Now by taking the expectation over a 2 , we have for x :

2 E S ++ |a 2 ||A 1 | 1 n = 2 k i=1 E |a i 2 | |A 1 (i, :)|1 u i 1 ≥ 0, l i 1 ≥ 0 1 n = 2 σ a2 2 π k i=1 |A 1 (i, :)|1 l i 1 ≥ 0 1 n = 2 σ a2 2 π n j=1 k i=1 |A 1 (i, j)|1 l i 1 ≥ 0

The second equality follows from the mean of the folded Gaussian. and the fact that u 1 ≥ l 1 .

For y , we have:

E S +-|a 2 | u 1 = σ a2 2 π k i=1 u i 1 1 u i 1 ≥ 0, l i 1 ≤ 0

Lastly, for z , we have:

2 E S ++ a 2 + S +-a 2 A 1 1 n = 2 E k i=1 A 1 (i, :)a i 2 1 u i 1 ≥ 0 1 n Using Holder's inequality, i.e. E[|x|] ≤ E[x 2 ], per coordinate of the vector k i=1 A 1 (i, :)a i 2 1 u i 1 ≥ 0

and by binomial expansion, we have at the j th coordinate

2 E k i=1 A 1 (i, j)a i 2 1 u i 1 ≥ 0 2 = 2 k i=1 (A 1 (i, j)) 2 E a i 2 2 1 u i 1 ≥ 0 + 2 i=1 z<i A 1 (i, j)A 1 (z, j)E a i 2 a z 2 1 u i 1 ≥ 0 1 {u z 1 ≥ 0} 1 2 = 2 k i=1 (A 1 (i, j)) 2 E a i 2 2 1 u i 1 ≥ 0 = 2 σ a2 k i=1 (A(i, j)) 2 1 {u i ≥ 0}

The second equality follows from by the independence of a i 2 and that they have zero mean. Therefore it follows from z that:

2 E S ++ A 2 + S +-A 2 A 1 1 n ≤ 2 σ a2 n j=1 k i=1 (A 1 (i, j)) 2 1 {u i ≥ 0}

Lastly, putting things together, i.e. E [x + yz ] we have that

EQUATION

Note that to show that the previous inequality is non-negative, it is sufficient to show that the previous inequality is non-negative for the non-intersecting sets {i : l i 1 ≥ 0} and {i : u i 1 ≥ 0, l i 1 ≤ 0}. Thus the right hand side can be written as the sum of two sets.

For the set {i : l i 1 ≥ 0}, the RHS of inequality 10 reduces to

EQUATION

)

For the set {i : u i 1 ≥ 0, l i 1 ≤ 0} and using the definition of u 1 , the RHS of inequality 10 reduces to

EQUATION

Note that given the assumption in the Theorem where

1 √ 2π x j 1 k A 1 (:, j) + 1 2n 1 k b ≥ 0 ≥ A 1 (:, j) 2 -1 √ 2π

A 1 (:, j) 1 ∀j, then if both Eq 11 and Eq 12 are non-negative completing the proof.

Lemma 1. For x ∈ R k ∼ N (0, I), where k ≥ 5 we have that E 3 √ 2π x 1 -2 x 2 ≥ 0.

Proof. Note that by the mean of a folded Gaussian, we gave that

E [ x 1 ] = k i E [|x i |] = k 2 π . Moreover, note that E [ x 2 ] = E   k i x 2 i   = E [ √ y] = 1 2 k 2 -1 Γ( k 2 ) ∞ 0 x k exp - x 2 2 dx = 2 k-1 2 Γ k+1 2 2 k 2 -1 Γ( k 2 ) = √ 2 Γ k+1 2 Γ( k 2 ) ∼ √ k.

Note that y is Chi-Square random variable and that

f √ y (x) = 2xf y (x 2 ) = x k-1 2 k 2 -1 Γ( k 2 ) exp -x 2 2

where the third inequality follows by integrating by parts recursively. Lastly, the last approximation follows by stirling's approximation for large k.

Proposition 3. For a random matrix A 1 ∈ R k×n with i.i.d elements such A 1 (i, j) ∼ N (0, 1), then

E A1 A 1 (:, j) 2 - 1 √ 2π A 1 (:, j) 1 = √ 2 Γ k+1 2 Γ k 2 -k 2 π ≈ √ k 1 - 2 π √ k .

Proof. The proof follows immediately from Lemma 1.

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 DM , u DM ] for random n -100 -100 -100 -100 -2 networks initialized with N (0, 1/ √ n) similar to Wong & Kolter (2018) . We show our bounds compared to the polytobe estimated from MonteCarlo sampling on results for n ∈ {2, 10, 20} and ∈ {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. -152.7639 192.4156 -188.4030 148.2482 = 0.25, Figure Number = 2 -196.8923 195.4355 -163.2691 177.3766 = 0.25, Figure Number = 3 -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: 

E FAILURE EXAMPLE FOR OUR BOUNDS:

In this section, we show a faliure example to when the network weights do not follow Gaussian Assumption 1, our bounds can be far too loose even compared to IBP. Consider a two layer neural network where A 1 = 1000 I n×n , b 1 = -999 1 n , a 2 = -10 1 n and b 2 = 0 for the interval [-1 n , 1 n ]. Then, we have that

l, u = b 1 ∓ |A 1 |1 n = 1 n ∓ 1000 -999 = -1999 1 n , 1 n .

Since u ≥ 0, then M = I n×n . Thereafter our estimated bounds as given by Equation 3 are given as:

L M , U M = a 2 b 1 ∓ |a 2 A 1 |1 n = 9990n ∓ 10000 1 n 1 n = -10n, 19990n.

As for IBP bounds, they are given as follows:

L IBP , U IBP = a 2 max(u, 0 n ) + max(l, 0) 2 ∓ |a 2 | max(u, 0 n ) -max(l, 0) 2 = - 10 2 1 n 1 n ∓ 10 2 1 n 1 n = -10n, 0.

Under this construction of weights to the network, different of the i.i.d Gaussian assumption, it is 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 are not far from the Gaussian assumption by empirically investigating the histogram of the network weights.

F HISTOGRAM OF WEIGHTS OF TRAINED NETWORKS:

To quantify how reasonable is the assumption of Gaussian i.i.d weights in trained networks, we train medium CNN (discussed in previous section) and show the histogram of the weights of the first 6 layers. The network is trained with and without 2 regularization on three datasets namely MNIST, CIFAR10 and CIFAR100. 

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 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 on showing that our bounds are 'supersets' to some approximate bounds L approx and U approx . The approximate bounds are indeed related to the unknown true bounds through Assumption 1. Note that Assumption 1 states that there exists some m where the Assumption inequality holds. As we pointed out to R1, the larger the constant m, the larger n has to be for Theorem 1 to hold. Please refer to the last inequality in the proof of Theorem 1.

• 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 test . Please note that the robustness results over each individual test 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.

• 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?

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

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 R1, 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 to R1 in regards to the histogram results of the appendix to R2 for completion. "For the MNIST experiments, even without 2 regularization, the weights seem to follow a bell shaped. With 2 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 CIFAR10 and CIFAR100. We want to emphasize that while this is not a proof that the Gaussian assumption holds in practice, we 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.

• 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 ... 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 elaborated 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 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 ...

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 1:

We thank R1 for the time spent in reviewing our paper. Follows our response to R1's concerns.

• 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 ...

As correctly pointed out by R1, Gowal et al do not make such an assumption. They provide loose 'true' bounds for deep architectures as a function of network parameters by simply computing worst case bound per layer. As suggested by R1, we have conducted an experiment where we trained Medium CNN with identical structure to previous experiments on MNIST, CIFAR10 and on CIFAR100 with and without 2 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 2 regularization, the weights seem to follow a bell shaped. With 2 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 CIFAR10 and CIFAR100. We want to emphasize that while this is not a proof that the Gaussian assumption holds in practice, we 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 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 ... 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 n and k) of the variance of L M and U M 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 be 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 a technical issue to do so?

• Comment on the metric PGD Robustness and not PGD accuracy.

The focus of our work is 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 (accuracy 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 to showcasing that such simple estimates of the bounds can be utilized to efficiently regularize networks to improve their robustness.

:



Figures and Tables:

Figure 1: True Bounds in Expectation. As shown in Figure 1a, our proposed interval bounds [L M , U M ], as predicted by Theorem 1, get closer to being a true super set to the true interval bounds [Ltrue, Utrue] estimated by Monte-Carlo Sampling as the input dimension n increases regardless of the number of hidden nodes.Figure1bshows that a similar behaviour is present even under varying network depth.

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 for a two-layer network. The proposed bounds are significantly tighter than IBP, as predicted by Theorem 2.

Figure 4: Qualitative Results. We plot visualizations of the output polytope of a 20-100-100-100-100-2network through Monte-Carlo evaluations of the network with a 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 [LIBP, UIBP], they were omitted as 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[-47.8, 37.0]  for the y-axis.

, we visualize examples of the proposed bounds in Figure 4 and compare them to the true ones for several choices of ∈ {0.05, 0.1, 0.25} and a random five-layer fully-connected network with architecture n-100-100-100-100-2. We also show the results of the Monte-Carlo sampling for an input size n = 20. More qualitative visualizations for different values of n are in the appendix.

Figure 7: Each row represents 5 different randomly initialized networks for a given with n = 2.Note that the proposed bounds are far from being true this is as predicted by Theorem 1 for small n.

Figure 8: Each row represents 5 different randomly initialized networks for a given with n = 10. Note how the bounds are more likely now to enclose the true output region for all given compared to previous case where n = 2.

Shows the interval bounds obtained by propagating ∈ {0.05, 0.1, 0.25} with n = 10 and denoted as l 1 DM , u 1 DM for the first output function of the 2-dimensional output network (shown along the x-axis in the previous figure) while l 2 DM and u 2 DM is for the other function (shown along the y-axis in the previous figure).

Figure 9: Each row represents 5 different randomly initialized networks for a given with n = 20. The bounds almost always enclose the polytope computed from Monte-Carlo compared to n = 2, 10.

Figure 11: Compares PGD ( test = 0.2) and test accuracy of our models against IBP on MNIST.

Figure 12: Compares PGD ( test = 0.3) and test accuracy of our models against IBP on MNIST.

Figure 13: Compares PGD ( test = 0.4) and test accuracy of our models against IBP on MNIST.

Figure 15: Compares PGD ( test = 8 /255) and test accuracy of our models against IBP on CIFAR10.

Figure 16: Compares PGD ( test = 16 /255) and test accuracy of our models against IBP on CIFAR10.

Figure 17: Compares PGD ( test = 0.1) and test accuracy of our models against IBP on CIFAR10.

Figure 18: Histogram of weights of medium CNN trained on MNIST without 2 regularization.

Figure 19: Histogram of weights of medium CNN trained on MNIST with 2 regularization.

Figure 21: Histogram of weights of medium CNN trained on CIFAR10 with 2 regularization.

Figure 23: Histogram of weights of medium CNN trained on CIFAR100 with 2 regularization.

detailed in Section 3.1 on function g(x) with x ∈ [x -1 n , x + 1 n ] to obtain bounds [L IBP , U IBP ]. We use these bounds for comparison in what follows.

Table content: <table/>

Our goal is to propose new interval bounds for g, as a block, which are tighter than the IBP bounds [L IBP , U IBP ], since we believe that tighter bounds for a two-layer block, when propagated/extended to deeper networks, can be tighter than applying IBP layerwise. Denoting the true output interval bounds of g as [L true , U true ], the following inequality holdsL true ≤ g(x) ≤ U true ∀x ∈ [x -1 n , x + 1 n ].Deriving these true (and tight) bounds for g in closed form is 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 as [L M , U M ], which we prove to be true bounds and tighter than [L IBP , U IBP ] in expectation under a distribution of the network parameters A 1 and a 2 . As such, we make two main theoretical findings. (i) We prove that L M and U M are true bounds in expectation, i.e. E A1,a2 [L M ] ≤ E A1,a2 [L true ] and E A1,a2 [U M ] ≥ E A1,a2 [U true ] hold for a sufficiently large input dimension n. (ii) We prove that [L M , U M ] can be arbitrarily tighter than the loose bounds [L IBP , U IBP ] in expectation, as the number of hidden nodes k increases.

Table content: <table/>

True and Tight Bounds on Real Networks. Table shows that our bounds are a super set to true bounds computed with an exact MIP solver. Moreover, they are much tighter than bounds estimated by IBP.

Table content: <table><tr><td/><td/><td/><td>Γ</td><td>Γmin</td><td>Γmax</td><td/><td/><td/><td>WIBP -WM</td><td>W IBP/W M</td></tr><tr><td>Small</td><td>MNIST</td><td>0.01 0.02 0.03</td><td>1.0 ± 0 1.0 ± 0 0.97 ± 0.088</td><td>1.0 1.0 0.635</td><td>1.0 1.0 1.0</td><td>Small</td><td>MNIST</td><td>0.01 0.02 0.03</td><td>644.322 1381.980 2255.397</td><td>17.391 15.270 14.555</td></tr></table>

Peer review (iclr2020):
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. Summary Interval 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. The 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). The logical argument explaining the *why* these are valid is harder to understand and could be clarified. My understanding so far is: - All the analysis is dependent on all weights being drawn from iid gaussian of zero mean. - 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. The 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? So the relation to the true bounds is only given by the Assumption? Regarding the experiments: * 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! * 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. * 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? 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 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. [From previous review] Simple example of a network where the results would be quite loose, while IBP is tight: Two layer NN, x = 0 in R^n, eps = 1, W1 = 1000 * Identity, b1 = -999 * 1_n, a2 = -10 1_{1,n} , b2 = 0 u1 would be all positive, so the matrix M would simply be the identity. L_M = a2^T M b1 - eps | a2^T M A1| vec(1) = (-10)*(-999)*n - 10 * (1000) * n = -19990 * n U_M = a2^T M b1 + eps | a2^T M A1| vec(1) = (-10)*(-999)*n + 10 * (1000) * n = n The actual bound (which also correspond in that case to what would be computed by IBP) is L_gt = -10*n u_gt = 0 Comments: * *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 * 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? * 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. * 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). If 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.*) Opinion: I 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) Typos: Page 7, *are are much* Page 8,*When kappa=0*, no need for uppercase The 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. In 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