Optimising Neural Network Architectures for Provable Adversarial Robustness
Authors: Henry Gouk
Timothy M. Hospedales
Venue:  (2020)
Keywords: Provable adversarial robustness
Lipschitz neural networks
network architectures

Abstract: Existing Lipschitz-based provable defences to adversarial examples only cover the L2 threat model. We introduce the first bound that makes use of Lipschitz continuity to provide a more general guarantee for threat models based on any p-norm. Additionally, a new strategy is proposed for designing network architectures that exhibit superior provable adversarial robustness over conventional convolutional neural networks. Experiments are conducted to validate our theoretical contributions, show that the assumptions made during the design of our novel architecture hold in practice, and quantify the empirical robustness of several Lipschitz-based adversarial defence methods.

Under review as a conference paper at ICLR 2020
OPTIMISING NETWORK ARCHITECTURES FOR PROV- ABLE ADVERSARIAL ROBUSTNESS
A Anonymous authors Paper under double-blind review
ABSTRACT
Existing Lipschitz-based provable defences to adversarial examples only cover the & threat model. We introduce the first bound that makes use of Lipschitz contimuity to provide a more general guarantee for threat models based on any by norm. Additionally, a new strategy is proposed for designing network architectures that exhibit superior provable adversarial robustness over conventional convolutional neural networks. Experiments are conducted to validate our thcoretical contributions, show that the assumptions made during the design of our novel architecture hold in practice, and quantify the empirical robustness of several Lipschitz-basee adversarial defence methods.
INTRODUCTION
The robustness of deep neural networks to adversarial attack (Szegody al., 2014) is an increasingly topical issue as deep models are becoming more widely deployed in practice. This paper focuses on the problem of ensuring that once a deep network trained for image classification has been deployed, one can be confident that adversary has only limited ability to maliciously impact model predictions when they tamper with the system inputs. Such malicious inputs, so-called adversarial examples, appear to humans as normal images, but in reality they have undergone imperceptible modifications that cause a model to make incorrect prediction. In contrast to many empirically focused approaches to defending against adversarial interference Carlini & Wagner (2017) and AAhhalye et al. (2018) for more details), we look to the trends prevalent in cryptography research, where developing provable defences is the primary modus operandi. The analysis in this paper makes use of the Lipschitz properties of neural networks accomplish this.
We begin by extending existing theory addressing the relationship between Lipschitz continuity and provable adversarial robustness. Using insights from the resulting bounds, it shown how one can adjust network architectures in such way that Lipschitz-based regularisation methods are more effective. Experimental results show that, while having little difference in empirical adversarial robustness compared to existing Lipschitz-baser defences, approach improves the level of provable robustness significantly. We also provide evidence that indicates adversarial training has only small penalising elfect on the upper bound of the Lipschitz constant of a network currently used by most works.
RELATED WORK
There are several papers in the literature on deep learning that address adversarial robustness through the use of Lipschitz continuity, however they focus solely on perturbations with bounded Fuclidean norm. Tsuzuku al. (2018) present an efficient method for determining whether an example could have been tampered with at test time or, conversoly, certify that a prediction has not been influenced by an adversarial attack. They compare the prediction margin normalised by the Lipschitz constant of the network to the magnitude of the largest perturbation allowed by the threat model, allowing them to determinc whether the input could be an adversarial example. Farnia et al. (2018) show how the adversarial risk bounded in terms of the training loss by adapting the bound of Bartlett et al. (0117) to consider perturbations the margin, using similar technique to Tsuzuku et. al. (0088)
be

---

Under review as a conference paper at ICLR 2020
The analysis in this paper takes similar high-level strategy makingg use of margins and Lipschitz constants but we extend this theory to threat models based on arbitrary p-norms, and provide simpler proof than Tsuzuku et al. (2018). Huster et al. (2018) demonstrate that current methods for regularising Lipschitz constants of networks have deficiencies when used for improving adversaria robustness. Specifically, it is shown that existing approaches for regularising the Lipschitz constant may be too restrictive because the bound on the Lipschitz constant too loose, resulting in overrregularisation. In anticipation that future work can provide improved upper bounds on the Lipschitz constant of a network, we provide thcoretical and practical contributions that are compatible with arbitrary bounds.
Existing work that aims to provide theory-backed guarantees for adversarial robustness has resulted in several techniques able to certify whether a prediction for a particular example is immune to adversarial attack under threat model based on f--norm perturbation size. Weng et al. (0088) propose a method that can only be applied to networks composed of fully connected layers with rectified linear units activation functions, and no batch normalisation. Wong Kolter (2018) present an approach based on solving an optimisation problem. While the robustness estimates they give are considerably tighter than many other certification methods, they scale very poorly to networks with large input images or feature maps. In contrast. to these methods, our approach bounds the expected adversarial generalisation error, has virtually no test-time computational overhead, and can be applied to arbitrary feed-forward architectures, Bounding the expected generalisation error enables us to give guarantees about the level of robustness model will have once it has been deployed. Existing approaches provable robustness do not come with such guarantees, and can only provide certification for individual instances.
3 GENERALISATION UNDER ATTACK
Methods for estimating the generalisation performance of learned models typically assume examples, (H,, y), observed at both training and testing time are independently drawn from the same distribution, D. Such methods estimate or bound the expected risk,
R²( E( ((()))
(1)
of a classifier, f. with respect to some loss function, L. The standard technique for estimating the expected risk in deep learning is to use an empirical approximation measured on a set of held-out data. Literature of quantifying worst-case generalisation performance. This is typically accomplished by deriving bounds expressed in terms of the empirical risk measured on the training data, and a term related to some measure of complexity of the hypothesis class.
statistical learning theory often investigates the related problem
In the adversarial setting one must consider the expected risk when under the influence of an attacker that can add perturbations to feature vectors at test time,
R (5) EEEWNN
((f(E + +, ENA
max
(2)
which is known as the adversarial risk Maddy et al. 2018 In contrast to the expected risk, Rg,(() (f) cannot be reliably approximated from data when f is non-convex, as one must find the globally optimal setting of ē for each data point in the held-out set.
For a hypothesis, f, that produces vector of real-valued scores, cach associated with possible class, we define the margin function as
mf fg (z) - max (z),
where f((z) the ith component of the output of fā)) Typical loss functions for measuring the performance of a model via composition with the margin function include the zero-
one loss and the hinge. These compositions result in the classification error rate and the multi-class hinge loss variant proposed by Crammer & Singer (2001). respectively.
Proposition 1. If f is k-Tipschitz with respect to the p-norm and é R R+ is monotonically decreasing loss function, then
max {(f(E + E). S ((my(Z,y) - 22/9kt), a|
(4)
2

---

regularisation method is a principled approach to Under review as a conference paper at ICLR 2020
where 9 is defined such that || llg is the dual norm of || llp.
Proof. Note that one can define the margin function given in Equation 3 as my (T, y) = mf(f())) y), where is the identity function. The Lipschitz constant of my with respect to its first argument when using the p-norm is max; E 1)1l, (Shalev-Shwartz 2012 p. 133). The gradient of mi a vector with all elements set to zero, except for those corresponding to the largest and second largest components of Σ. These components of the gradient take the values of and -1, respectively. Plugging these values into the definition of vector p-norms, one arrives at Lipschitz constant. of 24/9. From the composition property of Lipschitz functions, we can say that my is (2%/4))-.ipschitz with respect to E. The Lipschitz property of my can be used to bound the worst-case change in the output the margin function for bounded change in the input, yielding
l( min my(ă + +,2))) S ((my(E, - k/t)
(5)
From the decreasing monotonicity of l, we have that
max
(m ē, y)) = l( min +) "lle
(6)
El[e|<<
which concludes the proof.
This proposition bounds the worst-case change in loss for a single image in terms of prediction confidence, Lipschitz constant of the network, and the maximum allowable attack strength.
The relationship given in Proposition 1 is more general form of the bound derived by Tsuzuku et al. (2018), who consider only the Euclidean norm. Gouk et al./ (2018) provide elficient techniques for computing upper bounds to the Lipschitz constant of Teed-forward networks with respect to the 1-, 2-, and oc-norms. Golowich et al. (2018) present a bound on the Rademacher complexity of deep networks that is primarily dependent on the same quantity that. Gouk et al. (2018) show to be upper bound on the x-norm Lipschitz constant. They do not make use Lipschitz properties to prove this, so tighter bounds on the Lipschitz constant will not. necessarily improve the bound on Rademacher complexity. These two pieces of related work, coupled with Proposition [ imply that empirical risk minimisation with Lipschitz-basse controlling adversarial risk.
Proposition D can be extended to provide non-trivial bound on the expected adversarial risk through the use of a held-out dataset and a simple application of McDiarmid's incquality, Although this is not a standard approach to take in learning theoret generalisation bounds, is a practical tool that can be used for quantifying worst-case ad adversarial robustness that of great utility to practitioners.
Proposition 2. If f is k-Lipschitz with respect to the p-norm, R + 10, B) is mono- tonically decreasing loss function, and { 8t) D) is independent of f (i.e., held-out data), the following holds with probability at least 1 6:
In(2/8)
(f)
Σ emmy(E.. (T) - 2 21/kkt
BV
2n
where q is defined such that || llg is the dual norm of ||- llp-
Proof. Constructing mean over loss terms applied to i..d. samples from D,
L - Σ ((m,(Z..v.) - 21/9kt),
-
(8)
results in a Doob martingale where each term is bounded by 1. This allows McDiarmid's incquality to bound the probability of the difference between the summation and its expected value exceeding some threshold,
-2n7
P(L-EIA - E[L]| > 7) < 2exp
(9)
B2
3

---

Under review as a conference paper at ICLR 2020
Setting 5 equal to the right-hand side of Inequality g and solving for y yields
In (2/6)
= BV
(10)
2n
Thus, we can say with confidence
1- 6 that
In (2/2/))
B[L S BV
(11)
2n
Applying Proposition 1 each term of the summation, L, concludes the proof.
Proposition expected risk.
2 extends the result of Proposition from the loss single instance the
In practice, this means that practitioner bound the worst-case adversarial performance of their model based on its (non-ad aoo--aversariil) validation-set performance and its Lipschitz constant, both of which can be measured efficiently. As we show later, this can lead to non-vacuous bounds on error rate, which in turn could allow user to deploy model with provable confidence about its performance under adversarial attack-without the hassle and computa cmmputational expense of instance-wis. certification at run-time [Weng et al. 2018 Wong & Kolter 2018
ARCHITECTURES FOR PROVABLE ROBUSTNESS
The analysis Section g motivates a high-level strategy for improving the adversarial robustness of neural networks: maximise the prediction margin while minimising the Lipschitz constant of the model. Several papers have proposed different methods for regularising the Lipschitz constant of network, with various motivations, including improving robustness to adversarial exmaples (Tsuzuku et al.) 2018 Cisse et al. 2017) and improving generalisation performance in the non-adversarial case Goou al. 2018).
We propose a strategy for modifying network architectures to make them more amenable to Lipschitz-based regularisers: splitting single multi-class classification network into collection of one-versus-all (OVA) classifiers that each produce real-valued score. Unlike the conventional OVA method, where each component classifier is trained in isolation, the werworks used in our approach are still trained jointly using softmax composed with the cross entropy loss function. The core assumption this approach predicated on is that each of the binary classifiers needs to solve simpler problem than the original multi-class classification task. Gouk et al. (2018) show that the Lipschitz constant is related to model capacity, the subnetwork associated with each class should be able to achieve high accuracy with a smaller Lipschitz constant than a conventional multi-class classification network. This makes such architecture more amenable to Lipschitz-based regularisation, and hence provable robustness via Proposition 2
Consider the vector-valued function,
f(ā) =
(12)
where C is the number of classes, and fa k;- ky-Lipschitz. We have from the Lipschitz property of each fi that
(1( 5(T + ")| S [|]]|ppppp- kello ||]])
(13)
||]|,, ka.,., kc]lm
(14)
from which we can deduce that the Lipschitz constant of the one-versus-all classifier is the lp norm of the vector of Lipschitz constants corresponding to each binary classifier. In the case of the co-norm, the largest Lipschitz constant associated with a single binary classifier dictates the Lipschitz constant of the entire OVA classifier.
4

---

Under review as a conference paper at ICLR 2020
4.1 LIPSCHITZ REGULARIZATION TRAINING
We investigate two approaches to controlling the Lipschitz constant of neural networks. The first approach is add the bound on the Lipschitz constant regularisation term to the objective function, resulting in
1 T Σ (((E))))))) + II Wil
(15)
where d is the number of layers the network and || Ilp is the operator norm induced by the vector p-norm. In the case where is two, the operator norm is the largest singular value of the matrix (i.c., the spectral norm). For = oc, is the maximum absolute row sum norm (Gou et al. 2018).
| = max Σ Wesl
(16)
The other regularisation technique we consider is the method proposed by [Tuzuku et al. (0018), which can be adapted to regularise the foo Lipschitz constant by using the norm in Equation 16. rather than the spectral norm.
5
EXPERIMENTS
This section presents the results of numerical experiments that demonstrate the tightness of the bounds presented in Section provides evidence that the architecture proposed in Section | is inherently casier to optimise for provable robustness than conventional network architectures, and evaluates the empirical robustness of Lipschitz- based defence methods. The models used in these experiments were implemented using Keras (Chollet) 2015). and the adversarial attacks were performed using the CleverHans toolkit (Papernot et al. 2016
5.1 TIGHTNESS OF THE BOUND
The bound given in Proposition model when under the influence of an adversary. In order to validate this bound empirically, we Irain linear support vector machines with different levels l2 regularisation on the MNIST dataset of hand-written digits. In the case of linear SVMs, the optimisation problem solved by iterative gradient- based attacks, such as the projected gradient descent method of Madry al. (2018), are convex and therefore be solved globally. This means the the empirical adversarial risk can be computed exactly. Plots indicating the tightness of the bound for linear SVMs given in Figures [ These were generated by training models on the first 50,000 instances of the training set, using the other 10,000 training instances as the held-out data required for computing the bound, and using the PGD attack when evaluating the network on the test data. These plots confirm that the bound proposed in Proposition con-vacuous and has the potential be useful in practice.
2 provides a way to estimate the worst-case performance of a
5.2 PROVABLE ROBUSTNESS
We first experiment on MNIST to determining whether our proposed OVA networks achieve better provable robustness than conventional convolutional neural networks. To control for the potentially confounding factor of model capacity, a series of networks with different widths are trained. We define the width of a conventional convolutional network as the number of feature maps produced by the first convolutional layer. For OVA networks, the width is the number of feature maps produced by the first layer in single binary classifier, multiplied by the number of binary classifiers. For both network types, the chosen architectures contain two convolutional layers, the second of which has twice the number of feature maps as the first. Each convolutional layer contains x 5 kernels, rectified linear unit activation functions, and is followed by 2 max pooling layer. After the convolutional layers two fully connected layers: one with 128 hidden units, and another with either 10 units (for conventional networks), or one unit (for OVA networks).
5

---

Under review as a conference paper at ICLR 2020
A
0:01
Advesaril Exoot Note
Advoarii Error Tade
00.5
0.5
Mdvesritll Ereor
01.0
0.4
Upper PGD Astack
0.2
1
2.5
1.6
[F]
Figure 1: Plots demonstrating the relationship between the provable upper bound adversarial risk, and the actual misclassification rate on the test set under adversarial attack. Linear SVM recognition on MNIST with & threat model and regularization strength A.
A-01
0.00
Adverssttdl Erot Rute
Advrescist Froe Butt
0.5
0.6
Adterssiit
0.4
Uppes PGD Attock
0.2
0.2
0.1
0.25
0.1
FF
Figure Plots demonstrating the relationship between the provable upper bound on adversarial risk, and the actual misclassification rate the test set under adversarial attack. Linear SVM recognition on MNIST with foo threat model and regularization strength A.
Figures 3 and f show how the number of feature maps in each layer of the networks impacts the provable adversarial robustness for the & and too norms under different threat models, respectively. The models in these plots are regularised using the Lipschitz penalty method proposed in Section 4 These figures show that: (1) Regularised OVA networks exhibit superior provable robust.ness compared to regularized conventional CNNs at comparable model sizes, (2) The magnitude of this margin becomes more pronounced as model size increases, (3) All methods have low error rate for unperturbed examples (left plots).
To investigate how well OVANets scale, additional experiments are run on the CIFAR-10 dataset, using VGG-style networks (Simonyan & Zisserman, 2014) as the base architecture. The bascline CNN uses the VGG11 architecture, and each subnetwork of the OVANet architecture is VGG11 network with half the number of feature maps in each layer. Table [ provides probabilistic (95% confidence) bounds on the worst-case ad adversarial error rale using Proposition
2 Table 2 shows the corresponding provable robustness results for SVHN see that: (1) Lipschitz penalty training improves the adversarial error rate for both vanilla VGG11 and VGG11-OVANG (performance improves with A); (2) VGG11-OVANet generally has superior provable robustness compared to vanilla. VGG11 for corresponding regularisation strength, espocially for strong attacks. (3) Mcanwhile, regularized OVANet achieves comparable results to regularized CNN in terms of clean data performance.
benchmark. From the results
5.3 EMPIRICAL ROBUSTNESS
OVA networks exhibit superior provable robustness compared to conventional networks, but it does not immediately follow from this that their empirical robustness will also be improved. We investigate this by using the PGD attack of Madry et al. (2018) to attack networks defended with Lipschitz Margin Training (LMT), the Lipschitz penalty regulariser (LP), and

---

Under review as a conference paper at ICLR 2020
[+ =
I| 5:025
IP S.5
OVANet (A = 0,000)
0.5
OVANet (A 001)
Advesaiall Baro Bale
CNN 8.00))
Adveasiial Henur Rate
3.5
CNN (A 001]
0.3
0.8
10a
107
10F 107
10f
107
Parumetes
Pursmnteess
Figure 3: Comparison of provable adversarial risk for conventional CNN versus OVANet trained with Lipschitz penalty regularization over range of model sizes. The & Lipschitz constant is used for regularisation and computing the bound. OVANet shows superior provable robustness, especially al larger model sizes.
F -0
F 5000
[F S00.
-10
0.065)
OVANet (A DO1:
Adverarial Excoe Hare
CNS (A-
Ashemmciial Bate
Ashorarrial Frrce Tha
CNN (A m.001)
08.
0.9
0.8
2.a
0.6
10
10
10
11
102
Parameters
Parameters
Parmeeters
Figure 4: Comparison of provable adversarial risk for conventional CNN versus OVANet trained with Lipschitz penalty regularization over a range of model sizes. The foo Lipschitz constant is used for regularisation and computing the bound. OVANet shows superior provable robustness, especially at larger model sizes.
no defence. For each method, the best performing architccture is chosen by measuring the empirical robustness of the validation set. The set architoctures considered are the same as those discussed Figures and 4 The results are given in Tables and 4 for the l and
Eo norms, respectively.
For the & norm, the OVA networks perform similarly to their conventional counterparts from an empirical standpoint, but with improved provable robustness. For the foo norm, we do not observe empirical benefit from using OVA networks over conventional network architectures. However, our adaptation Lipschitz-based regularisation to the foo sctting does improve empirical robustness noticeably over the undefended wwwwork-pattiulart// when using our novel penalty approach given in Equation
15 rather than LMT.
Table shows the upper bound on the Tipschitz constants of each model for which have reported empirical robustness measurements. From this table, we can see that both Lipschitz-based defences successfully limit the constant of each network- several orders of magnitude. Using an OVA network architecture, in most cases, results in another modest decrease in the Lipschitz constant when using Lipschitz regularisation method, and a substantial decrease when no regulariser is applied.
by
6 CONCLUSIONS
This paper presents a p-normmagnostic theoretical analysis of provable adversarial robustness via Lipschitz regularisation. A new architecture, the OVA network, is proposed, motivated by insights how Lipschitz constants can be bounded for different architecture design choices. It. is shown that OVA networks achieve similar empirical robustness conventional neural
7

---

Under review as a conference paper at ICLR 2020
Perturbation
Size (f2)
Model
A
Clean
1/255
2/ 2/255
3/255
4 255
0
14.50
100.00
100.00
100.00
100.00
0.0001
14.22
47.61
79.22
95.87
100.00
VGGII-CNN
0.0005
16.00
29.00
42.74
56.49
69.84
0.001
17.64
26.80
35.60
44.75
53.66
0
17.18
100.00
100.00
100.00
100.00
0.0001
15.58
44.54
73.49
93.11
99.99
VGG11-OVANel
0.0005
15.86
27.68
39.01
51.85
63.68
0.001
17.09
25.00
32.54
40.35
48.53
Table 1: Bounds on the error rate for VGG models trained on CIFAR-10 with the Lipschitz penalty regulariser. The bounds were computed with Proposition 2 at the 95% confidence level and the & threat model.
Perturbation Size (f2)
Model
A Clean
1/255
2/ 2/255
3/255
4/255
0
7.29
100.00
100.00
100.00
100.00
0.0001
7.15
13.16
21.86
33.59
47.10
VGG11-CNN
0.0005
8.46
11.38
14.84
19.33
24.49
0.001
9.41
11.76
14.95
17.76
21.48
0
7.69
100.00
100.00
100.00
100.00
0.0001
7.45
12.10
19.19
28.38
39.17
VGGII-OVANet
0.0005
8.25
10.64
13.02
16.11
19.82
0.001
9.02
10.92
12.86
15.05
17.81
Table 2: Bounds the rate for VGG models trained SVHN with the Lipschitz
penalty regulariser. The bounds were computed with Proposition 2 at the 95% confidence level and the & threat model.
networks when Lipschitz-based defences are used. However, as network size increases, OVA networks are able to achieve significantly better certifiable robustness. This is useful result for practitioners, who can use our LP regulariser and bound in order to train models with quantitatively certifiable degree of robustness against adversarial attack.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner, Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples. In International Conference on Machine Learning, pp. 274 283, July 2018
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normaaizze margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6240 6249, 2017.
Nicholas Carlini and David Wagner. Adversarial Examples Are Not Easily Detoctod: By- passing Ten Detection Methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Securily, ATSec '17, pp. 14, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-5200 doi: 10.1145/311 31144///128572.314000
François Chollet. Keras. https:/ githgi.thhoooc httphuub.coom/kka-tteeeaa /eeras-teaamaaa/ teaesteaaa///////////. 2015.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval Networks: Improving Robustness to Adversarial Examples. In International Conference Machine Learning, pp. 854-863, 863, July 2017.
8

---

Under review as a conference paper at ICLR 2020
Perturbation Size (42)
Model
Clean
0.5
1.0
1.5
2.0
CNN
0.80
2.87
14.90
49.64
74.73
CNN LMT
1.37
2.97
10.24
29.94
65.22
CNN + LP
1.72
3.51
10.94
29.66
61.80
OVANet
0.90
3.63
17.91
55.88
82.82
OVA Nel LMT
1.34
3.23
11.18
32.55
65.49
OVANet LP
1.90
3.44
11.42
30.51
58.50
Table 3: Error rates (lower is better) of models trained with different regularisers when attacked with the projected gradient descent method of Madry al. (2018). The &g threat model and regularisers are used. While our OVANet architecture does not improve empirical robustness, our L.P training does benefit both model architectures.
Perturbation Size (Loo)
Model
Clean
0.1
0.2
0.3
CNN
0.80
26.72
94.66
99.34
CNN + LMT
1.13
16.51
85.90
99.03
CNN + LP
1.52
14.40
79.34
98.94
OVANet
0.90
36.42
97.52
99.37
OVANet LMT
1.00
21.48
93.01
99.
OVANet LP
1.25
17.32
88.63
99.10
Table 4: Empirical error rates (lower is better) of models trained with different regularisers when attacked with the projected gradient descent method of Madry et al. (2018). The &oo threat model and regularisers used. While OAVNet architecture does not improve empirical robustness, our LP training does benefit. both model architecturos.
Tipschitz Constant.
Model
E
foo
CNN
361.0
148,886.8
CNN + LMT
23.2
711.7
CNN LP
11.3
261.2
OVANct
190.9
21,957.0
OVANet + LMT
22.7
741.3
OVANet LP
9.4
215.8
Table 5: Lipschitz constants for different architecture and regulariser combinations.

---

Under review as a conference paper at ICLR 2020
Koby Crammer and Yoram Singer. On the Algorithmic Implementation of Multiclass Kernel- based Vector Machines. Journal of Machine Learning Research, 2(Dec):265- 222-2 2001. ISSN ISSN 1533-7928.
Farzan Farnia, Jesse M. Zhang, and David Tse. Generalizable Adversarial Training via Spectral Normalization. arXiv:1811.07457 |es, stat/, November 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-Independent Sample Complexity of Neural Networks. In Conference On Learning Theory, pp. 297-299, July 2018.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of Neural Networks by Enforcing Lipschitz Continuity. University of Waikato Technical Report, 2018.
Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the Lipschitz constant as defense against adversarial examples. wwXiv:1807.09700 jes, stat/, July 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Atlacks. In International Conference on Learning Representations, February 2018.
Nicolas Papernot, Fartash Faghri, Nicholas Carlini, Ian Goodfellow, Reuben Feinman, Alexey Kurakin, Cihang Xie, Yash Sharma, Tom Brown, Aurko Roy, Alexander Matyasko, Vahid Behzadan, Karen Hambardzumyan, Zhishuai Zhang, Yi-Lin Juang, Zhi Li, Ryan Sheatsley, Abhibhav Garg, Jonathan Uesato, Willi Gierke, Yinpeng Dong, David Berthelot, Paul Hendricks, Jonas Rauber, Rujun Long, and Patrick McDaniel. Technical Report on the CleverHans v2.1.0 Adversarial Examples Library. arXic:1610.00760 [cs, stat/, October 2016.
Shai Shalev-Shwartz. Online Learning and Online Convex Optimization. Foundations and Trendss) in Machine Learning, 4(2):107-18) 194, March 2012. ISSN 1935-8237, 1935-8245. doi: 10. 10.1151/ 0201//200000018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint orXin:1409. 1556, 2014.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 111 /Cs/, 2014.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks. In Advances in Newral Information Processing Systems, 2018.
Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, 2018
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, 2018.
10


Reviews:
[{"review_id": "SyenrE9TYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "1. Contributions: \nA) Extension of robustness bound based on margin and Lipschitz constant of the network to arbitrary l_p norms. Significance: Low.\n\nB) High probability bound on adversarial robustness based on A) and McDiarmid's inequality. Significance: Low.\n\nC) Lipschitz constant bound for one-versus-all networks (OVAs). Significance: Low.\n\nD) Experimental evaluation. Significance: Low\n\n2.  Detailed comments:\nOriginality: Contribution A) is a simple extension of previously known bounds for the l_2 norm which is rather technical. As such It has questionable novelty and limited potential impact. The same goes for B) which is a simple application of a well-known concentration bound that holds for many statistical estimators based on averaging.\n\nAlso C) is a well-known alternative for multiclass classification (one-vs-all approach) and somehow defeats the purpose of representation reuse from intermediate layers of the network to perform classification.  In OVAs the prediction for each class depends on entirely independent values of hidden layers. As such it is not surprising that. a slightly tighter estimate of robustness can be obtained, as one does not have to worry about interactions between features from each independent sub-network.\n\nQuality: The paper is in general well written, but lacks any depth or clear important contribution. The propositions are rather technical and/or simple extensions. The proposal of OVA networks and the bound on the adversarial risk are two parallel ideas that could be explored and hopefully find a significant contribution.\n\nFor example, what could the authors say about local Lipschitz constant estimates? are they easy/difficult to compute? what new bounds could be derived in term of such constants? For OVA networks can there be some intermediate reuse of hidden layers and still get some improvement in certified robustness? perhaps only the final layers require a split to see the empirical improvement, in this way reducing the burden of training one network from scratch for each different class (ImageNet has 1000 classes so OVAs could be quite expensive to train).\n\nOr maybe for OVAs the complexity of each subnetwork can be substaintially less (e.g., less layers) to obtain the same accuracy/robustness?? It looks from the experiments that this is true but some theoretical insights about why it is the\ncase can yield a strong paper.\n\nClarity: The paper could see some improvements in notation and some erroneous claims:\n1. Authors claim that the robustness can not be assessed when f is non-convex. This is in general, false. There is a constrained maximization procedure. constrained maximization of convex functions is a hard problem.  Not to be\nconfused with certain instances of constrained minimization of convex functions that can be solved efficiently. The same in section 5.1. The true statement is that for SVM the problem becomes optimization of a linear function with some simple constraint.\n\n2. In section 3 it is not clear if the loss l depends on the label y or not. sometimes it appears as an argument, and sometimes it disappears. see for example equation (4).\n\n3. In proposition 2 the assumption is that l is monotonically decreasing and its range is [0, B). Does this mean that B is negative?? this makes the claims in this section seem weird. There is some problem here. Also McDiarmids does not require the Doob Martingale concept, which is not even defined or referenced.\n\nSignificance: I find the significance low as the work is incremental and has technical rather than theoretical statements, and lacks a clear contribution. I vote for rejecting this submission.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJgeTXH6KS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "Summary:\n\nThis paper presents interesting theoretical contributions towards measuring the robustness of Lipschitz constrained neural networks. The empirical results are fairly limited and lack explanation in places and appropriate comparisons to existing work. The paper is missing references to several key pieces of related work tackling similar problems. I identified (fixable) issues with the theoretical results in the paper and felt that overall the paper was rushed and difficult to read in places as a result.\n\nFurther, this paper exceeds the recommended 8 page limit with ill-formatted references.\n\n\nOverall\n\n1) Claim that threat models beyond l2 has not been explored before is false. See Anil et al. for networks implementing an L-infinity Lipschitz constraint [1] and Huster et al. [2] for a discussion of infinity norm constrained architectures (the latter is cited).\n\n2) In this work you claim through empirical evidence that adversarial training has only a small effect on the upper bound of the Lipschitz constant. This is contested by e.g. [3] which focused on measuring the Lipschitz constant of neural networks tightly and highlighted the impact of adversarial training.\n\n3) Ignoring issues discussed below, this paper presents an interesting theoretical result on providing stochastic robustness guarantees for Lipschitz constrained neural networks.  However, the paper does not discuss existing baselines which provide similar stochastic guarantees e.g. [4].\n\n\n4) There are several (fixable) issues present in the theoretical results. First, notation is inconsistent throughout with the loss function $l$ taking either one or two arguments in different places (e.g. Eqn. 2 vs. Proposition 1). In fact, in Proposition 1 the loss function on the left hand side of the inequality takes two arguments not one (one of which is vector valued).\n\nFrom the proof, it is clear that the authors mean to make the loss a function of the margin (which should be discussed clearly). Further, Proposition 2 presents the wrong terms in the sum (so that E[L] != adversarial risk). L should instead consider the sum over the maximum change in the margin for the dataset and use Proposition 1 after Eqn 11 as described. Further, this proof is a straight forward application of McDiarmid's inequality and does not need to define a Doob martingale (in fact, it is not clear that one is defined here as no filtration is presented). I also believe that the presented bound is computed incorrectly, as the maximum change in the sum value through modifying a single element would be B/n . I believe the stated result can be made rigorous and correct, however in its current form there are mistakes.\n\n5) I do not understand the proposed training strategy. It seems as though standard cross entropy training is used but with a modified Lipschitz constraint which allows the output of the vector-valued function to have different Lipschitz constants at each index. If this is the case, could you please elaborate on what you mean by the argument that subnetworks associated with each class can achieve higher accuracy?\n\n6) In section 4.1 you introduce the methods use to constrain the Lipschitz constant of the network. The first of which is a regularization scheme which provides no provable guarantees on the Lipschitz constant itself. Further, you describe spectral normalization as a regularization technique which is inaccurate --- it is typically implemented as a projection. Spectral normalization is also unable to tightly enforce the required Lipschitz constant (see e.g. [1]). Finally, I would like to ask how the authors compute the Lipschitz constants of the networks used throughout the experiments. Is the product of the linear layer p-norms computed after training? If so, this would give a loose upper bound (see [3]).\n\n7) I am also concerned by the range of perturbation size used to measure the theoretical robustness of the networks -- a maximum perturbation size on CIFAR-10 of 4/255 is used which is very small compared to e.g. [4] which searches up to a radius 1.5.\n\n\nI would consider raising my score if the issues present in the theoretical results are addressed by the authors.\n\nMinor:\n\n- In introduction: \"so-called adversarial examples, appear to humans as normal images\" may be considered to strict a definition. For example, images which look like random noise can force high classification confidence in classifiers and are often described as adversarial examples. Similarly, the thread model defined in equation (2) is presented as the general adversarial objective but is only a special case. One should be also be concerned with threat models violating a p-norm constaint.\n\n- Page 5, typo \"This means the the\"\n\nReferences:\n\n[1] Sorting out Lipschitz function approximation, Cem Anil, James Lucas, and Roger Grosse\n[2] Limitations of the Lipschitz constant as a defense against adversarial examples, Todd Huster, Cho-Yu Jason Chiang, and Ritu Chadha\n[3] Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks, Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J. Pappas\n[4] Certified Adversarial Robustness via Randomized Smoothing, Jeremy M Cohen, Elan Rosenfeld, and J. Zico Kolter", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkljE2Bntr", "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": "Summary:\nThe author show that lipschitz constants of the neural network can be used to bound adversarial robustness. They then propose an adjustment to the network architecture that, according to their assumption, would result in smaller lipschitz constant, which according to the theory would correlate with better robustness.\n\nComments:\n\"A practitioner can bound the worst-case adversarial performance of their model based on its (non-adversarial) validation-set performance and its Lipschitz constant, both of which can be measured efficiently.\"\n-> The Lipschitz constant can be measured efficiently only at the condition that you don't care about getting a tight one.\nThe method of Gouk et al. is a very loose overapproximation of the Lipschitz constant of the neural network (multiplication of lipschitz constant of each layer). \n\n- What happens if we want to obtain results for the 1-norm. Do all the arguments hold up, given that the dual norm is the infinity norm?\n\nNote: I did not assess the correctness of Proposition 2.\n\n\"Unlike the conventional OVA method, where each component classifier is trained in isolation, the networks used in our approach are still trained jointly using a softmax composed with the cross entropy loss function.\"\nHow is each network a one vs all if they are trained jointly? Is there an additional loss term on top of the joint softmax? Is it just that up until that point they are different networks?\n\n\"The core assumption this approach is predicated on is that each of the binary classifiers needs to solve a simpler problem than the original multi-class classification task.\" \n-> There is no validation of this assumption anywhere. This would improve the paper if there was some signs that the justification proposed by the authors have some experimental validation.\n\n\"the Lipschitz constant of the one-versus-all classifier is the `p norm of the vector of Lipschitz constants corresponding to each binary classifier\", end of page 4.\n-> A lipschitz constant, not THE lipschitz constant. This construction gives a valid lipschitz constant but it's entirely possible and very likely that there is a much tighter one.\n\n- Experiments in 5.1 are made on linear SVMs, which means that the lipschitz constant can be computed exactly but this doesn't really reflect how useful the bound will be on network with hidden layers, for which the lipschitz constant will have to be an approximation. This is a valid toy-example / sanity check but not a good validation of the method.\n\n- Experiments in 5.2 and 5.3 seem to indicate that the change in architecture proposed has at least some effect on the robustness to adversarial examples.\n\nNotation / typos:\n- In Proposition 1, on the left side of the inequality, l takes as argument a vector (f(x + eps)) and a coordinate, but on the right side and on the definition of l is a scalar function. Does that mean that the left side is the y-th coordinate? As in, what's in l is f_y?\n- Page 4, \"exmaples\"\n\nSome maybe interesting litterature that the paper might benefit from referencing/discussing:\nhttps://openreview.net/forum?id=HJguLo0cKQ, submitted to last years ICLR observed that ensemble of small models tended to be more robust than large models. I wonder if the reasoning in this paper might explain it at least partially.\n\n\nOpinion:\nAt the moment, the paper is quite confusing and hard to read, and it's not entirely clear what the crux of the paper, the new architecture is doing. It's also not validated where does the effect comes from.  I'm open to updating my opinion of the paper if these comments are addressed.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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 novel method to estimate the Lipschitz constant of a neural network, and use this estimate to derive architectures that will have improved adversarial robustness. While the paper contains interesting ideas, the reviewers felt it was not ready for publication due to the following factors:

1) The novelty and significance of the bound derived by the authors is unclear. In particular, the bound used is coarse and likely to be loose, and hence is not likely to be useful in general.

2) The bound on adversarial risk seems of limited significance, since in practice, this can be estimated accurately based on the adversarial risk measured on the test set.

3) The paper is poorly organized with several typos and is hard to read in its present form.

The reviewers were in consensus and the authors did not respond during the rebuttal phase.

Therefore, I recommend rejection. However, all the reviewers found interesting ideas in the paper. Hence, I encourage the authors to consider the reviewers' feedback and submit a revised version to a future venue.
Decision: Reject