Existing Lipschitz-based provable defences to adversarial examples only cover the 2 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.
Summary:
This 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.
Further, this paper exceeds the recommended 8 page limit with ill-formatted references.
Overall
1) 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).
2) 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.
3) 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].
4) 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).
From 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.
5) 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?
6) 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]).
7) 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.
I would consider raising my score if the issues present in the theoretical results are addressed by the authors.
Minor:
- 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.
- Page 5, typo "This means the the"
References:
[1] Sorting out Lipschitz function approximation, Cem Anil, James Lucas, and Roger Grosse
[2] Limitations of the Lipschitz constant as a defense against adversarial examples, Todd Huster, Cho-Yu Jason Chiang, and Ritu Chadha
[3] Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks, Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J. Pappas
[4] Certified Adversarial Robustness via Randomized Smoothing, Jeremy M Cohen, Elan Rosenfeld, and J. Zico Kolter