Towards certifying $\ell_\infty$ robustness using Neural networks with $\ell_\infty$-dist Neurons
Authors: Bohang Zhang
Zhou Lu
Tianle Cai
Di He
Liwei Wang
Venue:  (2021)

Abstract: It is well-known that standard neural networks, even with a high classification accuracy, are vulnerable to small $\ell_\infty$ perturbations. Many attempts have been tried to learn a network that can resist such adversarial attacks. However, most previous works either can only provide empirical verification of the defense to a particular attack method or can only develop a theoretical guarantee of the model robustness in limited scenarios. In this paper, we develop a theoretically principled neural network that inherently resists $\ell_\infty$ perturbations. In particular, we design a novel neuron that uses $\ell_\infty$ distance as its basic operation, which we call $\ell_\infty$-dist neuron. We show that the $\ell_\infty$-dist neuron is naturally a 1-Lipschitz function with respect to the $\ell_\infty$ norm, and the neural networks constructed with $\ell_\infty$-dist neuron ($\ell_{\infty}$-dist Nets) enjoy the same property. This directly provides a theoretical guarantee of the certified robustness based on the margin of the prediction outputs. We further prove that the $\ell_{\infty}$-dist Nets have enough expressiveness power to approximate any 1-Lipschitz function, and can generalize well as the robust test error can be upper-bounded by the performance of a large margin classifier on the training data. Preliminary experiments show that even without the help of adversarial training, the learned networks with high classification accuracy are already provably robust.

Under review as a conference paper at ICLR 2021
TOWARDS CERTIFYING lo ROBUSTNESS USING NEU- RAL NETWORKS WITH Loo -DIST NEURONS
Anonymous authors Paper under double-blind review
ABSTRACT
It is well-known that standard neural networks, even with a high classification accuracy, are vulnerable to small fx perturbations. Many attempts have been tried to learn a network that can resist such adversarial attacks. However, most previous works either can only provide empirical verification of the defense to a particular attack method, or can only develop a theoretical guarantee of the model robustmess in limited scenarios. In this paper, develop theoretically principled neural network that inherently resists Eoo perturbations. In particular, we design a novel neuron that uses for distance as its basic operation, which call -ost neuron. We show that the -dist neuron is naturally a I-Lipschitz function with respect the fo norm, and the neural networks constructed with -d--ist neuron (foo-dist Nets) enjoy the same property. This directly provides a theoretical guarantee of the certified robustness based on the margin of the prediction outputs. We further prove that the dist Nets have enough expressiveness power to approximate any I-Lipschitz function, and can generalize well as the robust test error can be upper-bounded by the performance of large margin classifier on the training data. Preliminary experiments show that even without the help of adversarial training, the learned networks with high classification accuracy already provably robust.
INTRODUCTION
Modern neural networks are usually sensitive to small, adversarially chosen perturbations to the inputs (Szegedy et al., 2013 Biggio et al. 2013). Given image æ that is correctly classified by a neural network, malicious attacker may find a small adversarial perturbation ò such that the perturbed image + 5. though visually indistinguishable from the original image, is assigned to wrong class with high confidence by the network. Such vulnerability creates security concerns in many real-world applications.
Developing a model that can resist small Eo perturbations has been extensively studied the lit- erature. Adversarial training methods (Szegedy et al. 2013 Madry et al.) 2017 Goodfellow et al. 2013 Huang et al., 2015] Athalye et al. 2018 Ding et al. 2020) first learn on-the-fly adversarial examples of the inputs, and then update model parameters using these perturbed samples together with the original labels. Such approaches are restricted to a particular (class of) attack method and cannot be formally guaranteed whether the resulting model is robust against other attacks. Another line of algorithms trains robust models by maximizing the certified radius provided by robust certi- fication methods. (Weng et al. (2018); Wong & Kolter (2018)); Zhang et al. (2018): Mirman et al. 2018); Wang et al. (2018); Gowal et al. (2018) Zhang et al. (2019)) develop their methods based on linear or convex relaxations fully connected ReLU networks. However, the certification methods are usually computationally expensive and can only handle ReL.U activations. Cohen et al. (2019); Salman et al. (2019); Zhai et al. (2020) show that a certified guarantee on small & perturbations can be casily computed for general Gaussian smoothed classifiers. But recent works suggest that such methods are hard to extend to the le pertturrration scenario.
In this work, we overcome the challenge mentioned above by introducing new type of neural network that naturally resists local adversarial attacks and can be easily certified under the &go per- turbation. In particular, neuron design that uses a non-linear activation after a linear transformation, the - neuron is purely based on computing the lo distance between the inputs and the parameters. It is straightfor-
propose novel neuron called -ist neuron. Unlike the standard

---

Under review as a conference paper at ICLR 2021
ward to see that such neuron is 1-Lipschitz with respect the f norm and the neural networks constructed with &g -dist neuron -dist Nets) enjoy the same property. Based on such prop- erty, we can obtain the certified robustness for any & -iit Nets using the margin of the prediction outputs.
Theoretically, investigate the expressive power of foe -ist Nets and its adversarially robust gener- alization ability. We first prove a Lipschitz--nivversll approximation theorem for - Net using a structured approach, which shows that -ditt Nets can approximate any I-Lipschitz function with respect to loo norm. We then give upper bounds of robust test error based on the Rademacher com- plexity, which shows that the robust test error would be small if the -dist Net learns a large margin classifier on the training data. Both results demonstrate the excellent capability and generalization ability of the dist Net function class.
The fo -dist Nets have nice theoretical guarantees, but empirically, training an fo--dist Net is not easy. For example, the gradient of the parameters in the fe norm is sparse, which makes the opti- mization inefficient. We show how to initialize the model parameters, apply proper normalization, and overcome the sparse gradient problem via smoothed approximated gradients. Preliminary ex- periments on MNIST and Fashion-MNIST show that even without using adversarial training, the learned networks are already provably robust.
Our contributions are summarized follows:
We propose novel neural network using loo -ist neurons, called dist Nets. Theoretically,
In Section 3, we show that &o -ist Nets are I-Lipschitz with respect to the &oo norm in nature, which directly guarantees the certified robustness of any dist Net (with respect to the foo norm).
In Section 4.1, we prove that dist Nets have good expressive power as it can approximate any I-Lipschitz function with respect to the &oo norm.
In Section 4.2, we prove that dist Nets have good generalization ability as the robust test error can be upper-bounded by the performance of large margin classifier the training data.
We provide several implementation strategies which are shown to practically helpful for model training (in Section 5).
RELATED WORKS
There are two major lines of works seeking to get robust neural networks:
Robust Training Approaches. Previous works showed that the conventional neural networks learned using standard training approaches (e.g., maximum likelihood method) are sensitive small adversarial perturbations, and significant efforts have been put developing training approaches for learning robust models. Adversarial training is the most successful method against adversarial at- tacks. By adding adversarial examples to the training set the fly, adversarial training methods (Szegedy et al. 20133] Goodffllow et al.) 2015) Huang et al. [0155] Zhang et al.) [2019a] Wong et al.] 2020) can significantly improve the robustness of the conventional neural networks. However, all the methods above are evaluated according to the empirical robust accuracy against pre-defined adver- sarial attack algorithms, such as projected gradient decent. It cannot be formally guaranteed whether the resulting model is also robust against other attacks.
Certified Robustness. Many recent works focus certifying the robustness of learned neural networks under any attack. Approaches based on bounding the certified radius layer by layer using some convex relaxation methods have been proposed for certifying the robustness of neural networks (Wong & Kolter 2018b) Gowal et al. 2018 Mirman et al. 2018 Dvijotham et al.) 20188] Raghu- nathan al.] 2018. Zhang et al. 2020). However, such approaches are usually computationally expensive and have difficulties in scaling to deep models.
More recently, researchers found a approach called randomized smoothing that can provide certified robustness guarantee for general models. Leeuyer et al. (2018); Li et al. (2018); Cohen eet al. (2019): Salman al. (2019): Zhai et al. (2020) showed that if Gaussian random noise is
2

---

Under review as a conference paper at ICLR 2021
added to the input layer, certified guarantee small & perturbations be computed for Gaus- sian smoothed classifiers. However, Yang et al. (2020): Blum et al. (2020); Kumar et al. (2020) showed that randomized smoothing cannot achieve nontrivial certified accuracy against more than
Ω (min (1, d//-112))) radius for lp perturbations, where d is the input dimension, therefore it can- not provide meaningful results for & perturbations due to the curse of dimensionality.
Another line of more conservative certification approaches sought to bound the global Lipschitz constant of the neural network (Gouk et al. 2018) Tsuzuku et al.) 2018:) Anil et al. 2019 Cisse et al.) 2017). However, the bounds are not tight (Cohen et al. 2019). and the final robustness performances are not as good as other certification methods.
Lo DIST NETWORK AND ITS ROBUSTNESS GUARANTEE
3.1 PRELIMINARIES
Throughout this paper, we will use bold letters to denote vectors and otherwise scalars. Consider standard classification task with an underlying data distribution D over pairs of examples æ E X and corresponding labels y E ) (1, 2, M). Usually D is unknown and we can only access training set T {(x) M1), ... (I,, } in which (æt, y1) is i.i.d. drawn from D. i = ...,...., n, Let f E F be the classifier of interest that maps any X to V. We call x' = x + an adversarial example of x to classifier f if f can correctly classify æ but assigns a different label to x'. In real practice, the most commonly used setting is to consider the attack under c-bounded &oo norm constraint, i.e., 5 satisfies || I e, which is also called fo perturbations.
Our goal is to learn model from T that resist attacks at (x, y) with high probability over (æc, v) ~ 'D for any small foo perturbations. It relates to compute the radius of the largest foo ball centered æ: in which f does not change its prediction. This radius is called the robust radius, which is defined as (Zhai et al. 2020; Zhang et al. 2019a):
inf f(a f(())
|
x xlloo when f(x) =
R(f; x. y)
(I)
when f(x) +
Unfortunately, computing the robust radius ( of classifier induced by standard deep neural network is very difficult. For example, Weng et al. (2018) showed that computing the lp robust radius of deep neural network is NP-hard for some specific p. Researchers then seek to derive a tight lower bound of R(f; x.f; y) for general f. This lower bound is called certified radius and denote it CR(f; xz, y). The certified radius satisfies 0 S CR(S: S R(J; (i y) for any f. f. y.
3.2 NETWORKS WITH foo -DIS NEURONS
In this subsection, we propose the lo- Neuron that is inherently Lipschitz with respect to foc norm. Using these neurons as building blocks, we then show how to obtain an foe Lipschitz neural networks dubbed Eo dist Net.
Denote as the imput vector to neuron. A standard neuron processes the input by first projecting z to a scalar value using a linear transformation, and then applying an non-linear activation function on it, i.e., aw + b). w and b are parameters, and function can be the sigmoid or ReLU activation. Unlike the previous design paradigm, we introduce a new type of neuron using foo distance as the basic operation, which we call f neuron:
u(z,0) 0) = || w|/so +b,
(2)
where 0 = (w, b} the parameter set. From the above equation, we can see that the foo- neuron is non-linear as it caleulates the loo distance between input and parameter w with bias term b. As a result, there is no need to further apply non-linear activation function.
Without loss of generality, we study the properties of multi-layer perceptron (MLP) networks that are constructed using dist neurons. All theoretical results can be easily extended to other neural network architectures, such convolutional neural nets. We E dhap to denote the input vector of an MLP network. A (MLP) network using lo neurons can be formally defined as follows.
3

---

Under review as a conference paper at ICLR 2021
Definition 3.1. (Lee-dist Net) Denote MLP network which takes x! Rdupp input. Assume there are L hidden layers and the I-th hidden layer contains di hidden units. We call is an MLP network constructed by dist neurons, if the k-th unit in the 1-th hidden layer Ty computed by
(1+1)
(1+1)_ = ((((")))(kk))))) = ||x(0) wilk 1l + bll.) <..o<<< 2b
(1) (1) (1) where x0() (a] 22
de
is the input vector to the 1-th hidden layer.
For simplicity, we will call an MLP network constructed by lo neurons as lo Net. For classification tasks, the dimensionality of the output of g matches the number of categories, i.e., M. We write g(x) = (g) (2))92((;)) (2()),...... ... gas (a:) and define the predictor f(x:) = arg max max Di (ar). Note that g can be used as the output logits the same as in any other networks, so we can apply any standard loss function on the lox dist Net, such the cross-entropy loss or hinge loss.
We will further show that the loc -ist neuron and the neural networks constructed using it have nice theoretical properties to control the robustness of the model. For completeness, we first introduce the definition of Lipschitz functions as below.
Definition 3.2. (Lipschitz Function) A function g(z): R R is called X-Lipschitz with respect to Ep norm || l1p. if for any 21, 22, the following holds:
( - g(z))llp S A||=1 x2l1p
It is straightforward to that the -ist neuron is I-Lipschitz with respect to foo norm.
3.3 LIPSCHITZ AND ROBUSTNESS FACTS ABOUT &00 DIST NETS
In this subsection, we introduce two straightforward but important facts about & -ist Nets. We first show that l dist Nets still I-Lipschitz with respect to fxo norm, and then derive the certified robustness of the model based on this property.
Fact 3.1. Any -ist Net g(-) is 1-Lipschitz with respect to to norm, for any æ1, 22 E RRd Rduper, we have (1g()1) g(x22) S ||= Ø2lloo.
Proof. It's easy to check that every operation u(x()), ((LR) is 1-Lipschitz, and therefore the map- ping from one layer the next (1) a((+1) is 1-Lipschitz. Then have for any æı, 22 Rdiaput, (g(x))) g( S || - 222loo--
Since g is I-Lipschitz with respect to &o norm, if the perturbation of the output can be bounded and the label of the perturbed data a' will not change as long as arg max gi(=)) arg max 9: (2=), which directly bounds the certified radius.
is rather small, the change
Fact 3.2. Given model f(x) = arg [| (x(x)) defined as above, and x is correctly classified as y. We define margin(æ;;) g) the difference between the largest and second-larges/ elements of g(æ),, then for any x' satisfying || x' a'11oo S margin (r:; g)/2, we have that f(x) = f(x') and:
CR() margin(x;
Proof. Since g(x) is I-Lipschitz, each element of g(x) can move at most margin(w:g) changes to s', therefore the largest element will remain the same.
when x
2
Using this bound, we can certify the robustness an dist Net of any size under foo norm with little computational cost (only forward pass). In contrast, existing certified methods suffer from either poor scalability (methods based on convex relaxation) or curse of dimensionality (randomized smoothing), and lack efficiency as well.
4

---

Under review as a conference paper at ICLR 2021
4 EXPRESSIVE POWER AND ROBUST GENERALIZATION OF Lo -DIST NET
The expressive power a model family and its generalization are two central topics in machine learning. In the previous section, show that dist Net is I-Lipschitz with respect to loo norm. Then it's natural to ask whether the designed neural network can approximate any I-Lipschitz function (with respect bo norm) and whether we can give theoretical guarantees on the robust test eгror of a learned model.
In this section, we give affirmative answers both questions. We will first prove Lipschitz- universal approximation theorem for -dittt Net using a structured approach, then give upper bounds of robust test error based on the Rademacher complexity of the model family. Without loss of any generality, we consider binary classification problems and assume the output dimension I. All the omitted proofs in this section can be found the appendix.
4.1 PPSCHITZ-UNIVERRSS APPROXIMATION OF DDIST NET
In this subsection, show that -dit Nets with bounded width approximate any 1-Lipschitz function (with respect to &or norm), formalized in the following theorem:
Theorem 1. For any I-Lipschitz, function g(x)) (with respect to Eo norm) on bounded domain KK E Raluaus and any 0, there exists an dist Net g(x) with width no more than dinput + 2, such that for all x E K, we have
(19(x) f( Sc
(4)
To prove Theorem I we need the following key lemma:
Lemma 4.1. For any L-pissciitz function f(x (with respect to too norm) on a bounded domain KK E Rt, and any >> 0, there exists finite number of functions fi(x) such that for all x E K
max fz(()) S [(x)= S max fe(x)) +e, i
where each f((x)) has the following form
fx))) min w wi
31,
22
w0z (4)
(1( x.n. + bj.
Lemma "decomposes" any target 1 I-Lipschitz function into simple "base functions", which will serve as building blocks in proving the main theorem. Lu et al.] (2017) first proved such universal approximation theorem for width-bounded ReLU networks by constructing special network that approximates the target function by "sum of cubes". For -dstt Net, such an approach cannot be directly applied as the summation will break the Lipschitz property. We employ novel "max of pyramids" construction to overcome the issue. The key idea is to approximate the target function from below using the maximum of many "pyramid- likee" basic 1-Lipschitz functions.
Theorem D implies that an -istist Net can approximate any 1-Lipschitz function with respect to lo norm on a compact set, using only finite width which is barely larger than the input dimension. Combining with the fact that an fo -dist Net is 1- L-Liscchitz, we conclude that loo- -diit Nets is good class of model to approximate I-Lipschitz functions.
4.2 BOUNDING ROBUST TEST ERROR OF lo DIST NET
Good robust generalization ability, i.c. small empirical (margin) error implies small robust test error, as important as strong expressive power. In this subsection, we give upper bound for the robust test error of t.z- -iit Net.
Consider the following classification problem: let (xx, y) be an instance-label couple where x E K
and y (1, -1) I) and denote D the distribution of (æ. y). For function g(x) : Rddape -> R,
use sign (x)) as the classifier. The r-robust test error 7, of a classifier g is defined as
Ep
sup
Ing(=")<0
Sr
We upper bound 7r by the margin error on training data and the size of network:
5

---

Under review as a conference paper at ICLR 2021
Theorem 2. Let I denote the set of all g represented by lx--dist Net with width and depth L, for every > with probability at least 1 - 2e-28 262 the random drawing of samples, for all r > 0 and g E F we have that
Lwe 8vn
log log2(3)
7r S inf 6E(0,1)
n v.o(0))54r
+
+
(5)
n2.
vn
large training margin
network size
Theorem provides a theoretical guarantee on the adversarial robust test error: when a large margin classifier is found on training data, and the size of the lo -dit Net is not too large, then with high probability the model can generalize well in terms of adversarial robustness.
We prove the theorem in two steps. One step is to provide margin bound to control the gap between standard training error and standard test error. In this step, we use Rademacher complexity R(F) of a hypothesis set F, where the test error B, with as margin defined as: 3, EE [[w(a)sr) The other step is to bound the gap between test emrrr and robust test error. The two steps are provided in the following two lemmas.
Lemma 4.2. Let F be hypothesis class, then for any >> O.
P 3g F.EFBBA
inf (ool(=)))8r> + Rr (F) +
48
(log (3)
1.
+ vra
S
2c. -212
6E(0.1)
Lemma 4.3. The r-robust test error is no larger than the test error Br, i.e. S By.
5 TRAINING foo NET
Motivated by the theoretical analysis in the previous sections, we would like find large margin solution on the training data. Therefore we use the standard hinge loss as the objective function:
L(g. 7)
max 0,
max g(xi),; - g(z.)y. V.Fu.
(6)
where / controls the desired margin and should slightly larger than twice of the desired robust- ness level according to Eqn. It can be easily seen that L(g. T) is a continuous function of the network parameters and is differentiable almost everywhere. Therefore any gradient based opti- mization method can be used to train an -ist Net.
However, the optimization is not easy. We find that directly using SGD or Adam optimizer fails to train the network well. In fact, the gradient of the foo norm (i.e., || w|l with respect to w is very sparse, which makes the optimization inefficient. In this section, we list few important optimization tricks which we find effective in practice.
Normalization and parameter initialization Batch Normalization (Toffe & Szegedy 2015), which shifts and scales feature values in each layer, is shown be one of the most important com- ponents in training deep neural networks. However, in dos-tist Net, if we directly apply batch normalization, the Lipschitz constant of the network will change due the scaling operation, and the robustness of the trained model cannot be guaranteed. To leverage the advantages of BatchNorm, we only apply the shift operation that shifts the output of each layer using the mean over the current batch during training. Similar to BatchNorm, we use the running mean during inference. Note that inference, the running mean serves as an additional bias term in -ist neuron, which does not affect the Lipschitz constant. Finally, we do not use affine transformation which is typically used in BatchNorm.
We apply the shift operation in all intermediate layers after calculating the foct norm, but not the final layer. As a result, we remove the bias term in the loc neuron in all intermediate layers. The bias in the last layer is initialized to zero. As for the weight initialization, weights and inputs should have the same scale due to the for distance operation. Therefore we initialize all weights from standard Gaussian distribution since the inputs normalized have unit variance.

---

Under review as a conference paper at ICLR 2021
Smoothed approximated gradients. We find that training -do from scratch is usually in- efficient, and the model can easily be stuck in some bad local minima. To obtain a well-optimized model, relax the & distance by Lp distance for each neuron, to get an approximate and non- sparse gradient of the parameters (Chen et al., 2020). During training, we set p to be a small value in the beginning, and linearly increase it in each iteration reach large value. When the training finishes, we freeze the model parameter and set p to oo as our final model.
6
EXPERIMENT
6.1 EXPERIMENTAL SETTING
Model details and training configurations. We train the -dist Net on two benchmark datasets: MNIST and Beshion-MNISS For both tasks, we use 4-layer los -ist Net. Each hidden layer has 4096 neurons. Normalization is applied between each intermediate layer. The batch size is set to 512. Random-crop data augmentation and image standardization are used during training. We train the network using Adam optimizer with hyper-parameters 31 = 0.9 and B3 = 0.99. The training procedure is as follows: First, we relax the -ditt Net to -p-dist Net with p = and train the model parameters for 30 epochs. Then gradually increase from 6 to 100 in the next 170 epochs. Finally, we fix = 100 and train the last 50 epochs. The learning rate the first and second parts is set to be 0.015 and is divided by 5.0 in the final 50 epochs. We use hinge loss with parameter 0.9. For the Aushion-MNIS" dataset, we use exactly the same model and the same hyper-parameter" as MNIST, except for the hinge loss parameter 0.4. Adjusting models and hyper-parameters may further improve the results.
Evaluation. Following Wong & Kolter (2018)); Gowal et al. 20 Madry et al. (2017): Zhang al. (2019b), we test the robustness of foe dist Net under 2. radius 0.3 MNIST and 0.1 on FaSiion-MNiST.. We use two evaluation metrics to measure the robustness of the model. We first evaluate the robust test accuracy under the Projected Gradient Descent (PGD) attack (Madry al. 2017]. Following standard practice, we set the number of steps of the PGD attack to be 20 and set the step size to be 0.01. We also calculate the certified radius for each sample using Eq, 3 and check the percentage of test samples that can be certified to be robust within the chosen radius.
Table I: Comparison of different methods on MNIST under foo radius 0.3.
Method
w/o Adv Train
Scalable
Standard Ace
Robust Acc
Certified Acc
Natural
99.3
R (
R (
IBP
X
X
98.34
93.88
91.95
CROWN-IBP
X
X
98.18
93.95
92.98
GroupSort
X
As 97.0
ss 32.0
2.0
l -dist Net
V
98.61
93.78
91.59
Table 2: Comparison of different methods on Fashion-MNIST under foo radius 0.1.
Method
w/o Adv Train
Scalable
Standard Acc
Robust Acc
Certified Acc
Natural
94.0
CAP
X
78.27
68.37
65.47
IBP
X
76.51
-ist Net
87.46
75.44
73.23
Baselines. In Table T and 2 compare -ist Net with several basclines, i.c., standard training
on standard neural network (abbreviated as Natural in the table). CAP (Wong & Kolter 2018b).
IBP (Gowal al. 2018). CROWN-IBP ęZhang al. 2019h), GroupSort Network (Anil et al. 2019). Randomized Smoothing (Cohen et al. 2019 Salman et al.] 2019 Zhai et al. 2020) is another strong baseline when considering the robustness with respect la perturbation. However, as discussed in the related work section, it cannot achieve nontrivial certified accuracy against more than Ω (min (1, d 1/2) radius for for perturbation where d is the input dimension, which implies randomized smoothing cannot obtain good certification under for norm. We report the performances

---

Under review as a conference paper at ICLR 2021
MNIST
Fashion MNIST
Input image
2
Neuron parameter
0.2
certified radius
(b)
Figure 1: (a) We sample some neurons from the first layer and list the parameters w together with some input data on MNIST and MNNIS. can be seen that on both tasks, the parameters (first row) look very similar to the data (second row) in some categories. This shows that the neuron captures the shape information, which meaningful feature and useful for classification. (b) The radius-ccertified accuracy) curve of our trained model on MNIST dataset.
(picked from the original papers) together with other properties of these methods, e.g., whether these methods use adversarial training (abbreviated as Adv Train in the table); are these methods scalable to large neural networks.
6.2 EXPERIMENTAL RESULTS
We list the performances of dis-dist Net in Table and 2 In these tables, use "Standard Acc", "Robust Acc" and "Certified Acc" as abbreviations of standard (clean) test accuracy, robust test accuracy under PGD attack and certified robust test accuracy. All the numbers are reported in percentage.
From [ find that -ist Net achieve comparative better robustness than other baselines while maintaining high standard accuracy. Specifically, on MNIST, among the methods that do need adversarial training can be scaled to large networks, loo -dst Net has the best robustness and achieves more than 93% robust test accuracy and more than 91% certified test ac- curacy. These performances are also comparative with those methods that train the model using adversarial training and calculate the certified radius with huge computational cost (Wong & Kolter, 2018b, Gowal et al., 2018 Zhang et al. 1b).. We also plot the radius-(certified accuracy) curve on MNIST in Figure [(b) Results on Fashion-MNIST are similar.
To understand how the -ditt Net extracts information from the data, we sample some neurons in the first layer and record its parameter We then visualize together with some input data both tasks. Interestingly, in Figure ((a) we can see that the parameters w (first row) "look similar" to the input data (second row). This phenomenon is because
use foo distance in the network to obtain effective signals for classification. Then the neurons seek to find typical patterns that can differentiate category others in terms of Eoo distance, e.g., the shape of the objects, which is quite different from the feature extractor in standard neural networks.
CONCLUSION
In this paper, we design a novel neuron that uses foo distance as its basic operation. We show that the dist neuron is naturally 1-Lipschitz function with respect to the foo norm and the neural networks constructed with dist neuron -dit Nets) enjoy the same property. This directly provides a theoretical guarantee of the certified robustness based on the margin of the prediction outputs. We further formally analyze the expressiveness power and the robust generalization ability of the network. Preliminary experiments show promising results on MNIST and Fashion-MNISTT datasets. As future work, will conduct experiments of the dist Net more datasets (CI- FARI0 and ImageNet) and extend it to modern networks, such as deep convolutional networks with residual connections.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In Inter- national Conference on Machine Learning, pp. 291-301, 2019.
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. CoRR, abs/1802.004223 2018.
Peter L. Bartlett, Nick Harvey. Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pscudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1 2019.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šmdić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Joint European conference machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify Lo robustness for high-dimensional images. arXiv preprint 1rXiv:2002.03517. 2020.
Hanting Chen, Yunhe Wang, Chunjing Xu, Boxin Shi, Chao Xu, Qi Tian, and Chang Xu. Addernet: Do we really need multiplications in deep learning? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1468-1477, 2020.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Gavin Weiguang Ding. Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. Mma training: Direct input space margin maximization through adversarial training. In International Conference Learning Representations, 2020.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers. arXiv preprint arXiv: 102.665, 2018.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arXiv preprint 1eXiv:8804.. 804.04368, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 18/0. 2018.
Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvári. Learning with a strong adver- sary. arXiv preprint arXiv:1511.0333 2015.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Vladimir Koltchinskii, Dmitry Panchenko, et al. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. arXiv preprint arXiv:2002.032399 2020.

---

Under review as a conference paper at ICLR 2021
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. arXiv preprint arXiv: 2018.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. CoRR, abs/I 809.031 13, 2018.
Zhou Lu, Hongming Pu, Feicheng Wang. Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6231663-66000 -2399. Curran Associates, Inc., 2017.
Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with lipschitz functions. Journal of Machine Learning Research, 5(Jun):669-69))) 2004.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1oXXi::7006.6660 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3578-3586, 2018.
Aditi Raghumathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 11292-11303, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. CORR, abs/1312.6199, 2013.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. posschitz-marghi training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in neural information processing systems, pp. 6541-6550, 2018.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint arXiv: 101:://11..0000 0ee//1811000200 1.02225, 2018.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song. Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5276-5285, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th In- ternational Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research. pp. 5286-5295 Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018a. PMLR.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286552869999 PMLR, 2018b.
Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.0322 033994, 2020.
Greg Yang. Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. arXiv preprint arXhv:2002.08118. 2020.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. arXiv preprint arXiv:2001.023: 2020.
10

---

Under review as a conference paper at ICLR 2021
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7472-7482, Long Beach, California, USA, 09-15 Jun 2019a. PMLR.
Huan Zhang, Tsui Wei Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards sta- ble and efficient training of verifiably robust neural networks. arXiv preprint urXiv:1906.063 2019b.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2020.
A APPENDIX
A.I PROOF OF LEMMA
Proof. Without loss of generality we may assume K E [0, 1]". Consider the set S consisting of all points (N, where Nj are integers, we can write $ n K (w ..... wmm) since it's finite set. (1) E S K, we define the corresponding fa( as follows
fa min w(") wi 11. w/" .... w((h In 3 + f(w!!))
Obviously Vaz E K have that f(x) 2 f((),, thus max, f((x) S f(x) holds as direct conse- quence.
On the other hand, Yo E there exists its 'neighbour' (i E S such that ||æ - w00) 1100 S 5, therefore by using the Lipschitz properties of both f(x) and f, (z), we have that
f(x) < (1) = (1
S fx) te
2
Since max; fi(x)) 2 (z)), we conclude our proof.
A.2 PROOF OF THROREM
Proof. By lemma 4.1 there exists finite number of functions fi( (i 1,... m) such that Vi E K
max f((x) & g(x)= S max f((z) +
(9)
where each f((x)) has the form
f((x) = min ( (1( -1, x2 ..... w((() 2n (1)
(10)
The high-level idea of the iroof very simple: among width dinput + 2. we allocate dinput neurons each layer to keep the information of æ. one to calculate each f((x)) one after another and the last neuron calculating the maximum of fı(x:) accumulated.
To simplify the proof, we would first introduce three general basic maps which can be realized at a single unit, then illustrate how represent max, fx by combing these basic maps.
Let's s assume for now that any input to any unit in the whole network has its & norm upper bounded by large constant C, will come back later determine this value and prove its validity.
11

---

Under review as a conference paper at ICLR 2021
Proposition A.1. Vj, k, p and constant w, c, the following base functions realizable the kth unit the lth hidden layer:
the projection map:
u(ax"), ((.h))) = =z] +c
(11)
2, the negation map:
u(x1), g(.,)) 2 +
(12)
the maximum map:
(kal",g(kk)) max{a, (1) + w. x1() uxx((,)) 0l1,)))))))))))))))))))))) max(-rr + w. au +e
(13)
Proof. 1, the projection map: Setting u(x()) (()-))) as follows
u )(lk)) = [1(=)) ..... 2/ + 2C, ...,,.,,. 20)) 2C +
(14)
the negation map: Setting ul u'x g(t.K) as follows
" g(l))) = [1(x1]) ...... ......J I.. 10) - 20" - 20 +
(15)
3, the maximum map: Setting u(x! o((,A)) as follows
u(x("),(0k))) (ll.k)) ||(=1" ..... ...,. (1)
20, ... 17 + 2C, 20 )1 2C +c
(16)
"(x ,(l.))) = -1(x0]) .... 1y + w + (0) + 2C,
(1)
20 +
(17)
With three basic maps in hand, we are prepared construct our network. Using proposition A. the first hidden layer realizes u(ar, (11.k) 3kk for k 1,... dinput- The rest units can be arbitrary, we set both to be F1-
By proposition A.1 throughout the whole network, k = 1,..., n. Notice that fe(œ) can be rewritten as
set u(x(9), g(.k) zy for all I and
f(()) = max (a1 w1 (5)
max (w] 11; max m... ( J.....}} (1))
(18)
Using the maximum map recurrently while keeping other units unchanged with the projection map, we can utilize the unit u(x((), g(hdmpaatt)) to realize one fi( at time. Again by the use of maximum map, the last unit u(x!!) (ll.uomtt2)) will recurrently calculate (initializing with max (z))
max fe(x) mm) max(.., (fxx(((())))...
(19)
using only finite depth, say L. then the network outputs g(x:) = u(x((L) ((L.)) = u(x(h-1),
g( = max, fa(x) as desired. We are only left with deciding a valid value for C. Because K is bounded and ((x)) ) continuous, there exists constants C, C2 such that Vo E K, ||]||> < C₁ and [ğ(x)) S C2, it's easy to verify that C = 201 + C2 is valid.
A.3 PROOF OF LEMMA
First we give quick revisit Rademacher complexity and its properties.
12

---

Under review as a conference paper at ICLR 2021
Rademacher Complexity Given sample X,, ( Fnl IK", and real-valued function class on IK, the Rademacher complexity of is defined as
n
R2 (I) = Ex,,
Egg
sup fEF
Σ
n2
where o, are drawn from the Rademacher distribution independently, i.e. P(e, = 1) P(o;
- 1) = It's worth noting that Vr, RIF R., (I @ r) where F + (f E).
It's well known (using Massart's Lemma) that Rademacher complexity can be bounded by VC dimension:
Ra, (F) S 2VCdim(B) log (Cdim(F)
en
(20)
Proof. Denote the hypothesis set with IF and its Rademacher complexity on training data with (F), we can upper bound the generalization enror when large margin solution is found on training data:
Lemma A.1. (Theorem 11 in Koltchinskii et al.
2002 For all L 0.
P 3g E F:: 8o >
inf 6E(0,1]
ng(e)so + 5
48 (F) +
log logg
+
S
2e 22
To further generalize lemma A.I to 3, with r we use the fact that Rademacher complexity remain unchanged if the same constant is added to all functions in IF. Lemma 4.2 is direct consequence by replacing m by m r the end of the proof of theorem 11 Koltchinski et al. (2002), where it plugs my into theorem 2 in Koltchinskü et al. (002))
A.4 PROOF OF LEMMA
Proof. yg(æ:) > implies inf
[a'- Sr Ug(a'')
because g(x) is 1-LLipchitzz therefore
Ep [[
Ex
inf
S EED
sup
|| ||ll
and
3, < % which concludes the proof.
A.5 PROOF OF THEOREM
Proof. There generalization bounds like (uxbburg & Bousquet 2004), which involves only the Lipschitz property. Unfortunately, those bounds, the dependence on sample size of or- der n Fiput which suffers from the curse of dimensionality. To derive a more meaningful bound, we take the network size into consideration well.
We can bound the VC dimension of -dctt Net by reducing given fic- Net network to a fully- connected ReLU network. We first introduce the VC bound for fully-connected neural networks with ReLU activation borrowed from Bartlett et al. (2019):
Lemma A.2. (Theorem 6 in Bartlett al. (2019) Consider a fully-connected ReLU network archi- tecture with input dimension d, width w 2 and depth (number of hidden layers) L,, then its VC dimension satisfies:
VCdim(()) Ô(L2w²)
(21)
The following lemma shows how to calculate lo distance using a fully-connected ReLU network architecture.
13

---

Under review as a conference paper at ICLR 2021
Lemma A.3. Ve R there exists fullly-connected ReLU network h with width ((d) and depth Oloog d) such that h(z)= = || w
Proof. The proof is by construction. Rewrite | w|/s as
max - W1: W1 21, Zd
wa: Wi zal
which is maximum of 2d items. Notice that max y) Re Re (eLU(y) ReLU y),, we can use 3d neurons the first hidden layer so that the input to the second hidden layer are max(#; Wi, w; ri in all d items. Repeating this procedure which cuts the number of items within maximum by half, within Ollog d) hidden layers this network finally outputs || - w 0c as desired.
The VC bound of foo Net is formalized by the following lemma:
Lemma A... Consider an dosd Net architecture F with imput dimension d, width d and depth (number of hidden layers) L, then its VC dimension satisfies:
VCdim((F) = O(L²u²))
(22)
Proof. By lemma A.3 each neuron in the -dst Net can be replaced by a fully-connected ReLU subnetwork with width O(w) and depth (log w). Therefore fully-connected ReLU network architecture G' with width O(w²) and depth O(L log w) can realize any function represented by the dist Net when parameters vary. Remember that VC dimension monotone under the ordering of set inclusion, we conclude that such &oo dist Net architecture F has VC dimension no more than that G which equals ([= by lemma A.2
Finally, Theorem 2 is direct consequence by combing Lemmas
A.4
14


Reviews:
[{"review_id": "lLRXhjVkmi6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors consider the task of adversarial/robust learning with respect to neural networks. The problem is a well-motivated one: suppose there is a neural network that on input a training set T={(x_i,y_i)} does a good classification job, but an adversary comes along and modifies some parts of T, then it is very possible that the neural network will classify almost incorrectly and hence isn't robust. In this paper they consider this setting and ask if we can naturally make neural networks robust. \n\nIn this direction, the authors propose a major change: in the conventional neural networks, one has sigmoid function which on input x, outputs sigma( w^T x ) (let's ignore bias for the time being) and the authors observe this functions is neither Lipschitz nor is it robust to noise. Instead, the author propost an ell_inf neuron which is just || w - x ||_inf. In this direction, they consider a neural network that is built out of ell_inf neurons. Simply by definition, it isn't too hard to see that this function is Lipschitz with respect to the ell_inf norm. The authors go on to show that every function can be represented using this new ell_inf NNs with sufficiently many neurons and sufficiently large depth. Furthermore, they go on to perform certain simulations for MNIST data. \nIn my opinion here are the pros and cons of the paper:\n\n1) Pros: I think the problem is very well motivated and has been extremely well-studied. I am not an expert in this area, but i find their ell_inf neuron pretty interesting as well. Their simulations also seem very intriguing that such neurons seem to work after all (which is slightly surprising to me based on what I say next)\n\n2) Cons: In my opinion, the authors do not make a sincere effort to compare both the models. A simple example where the new model is *extremely* inefficient is simply to compute the inner product function. It is easy to do it in the standard neural model (albeit its not robust), but in the new model, even the non-robust setting, I don't think the inner product can be computed easily. SO it seems to me that their \"fix for robustness\"might lack the decades of research that has been done in understanding and proving results about the standard sigmoid function. This is an important aspect which is missing in their work. \n\nOverall, I think the idea is nice, but I'd tend towards rejection since their fix could be nice if they can show that everything computable in the standard NN model can be computed in their new ell_inf NN model (with approximately the same complexity), but this seems to be missing in its current form.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GrAy4kPakQo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:**\n\nThe contribution of the paper is threefold: First, it proposes a novel variation of AdderNet (Chen et al. 2020) that ensures the network is always 1-Lipschitz with respect to $\\ell_{\\infty}$ norm. The architecture allows one to generate robustness certificates with respect to $\\ell_{\\infty}$ norm with only a single forward pass, which is computationally cheap compared to many of the previous methods. Second, it analyzes the expressive power and robust generalization of the architecture. Finally, it proposes two training techniques (bias batchnorm and p-norm schedule) that overcome the optimization problem inherent with training $\\ell_{\\infty}$ Net and analyzes its empirical performance with respect to the previous methods.\n\n\n**Strength:**\n- The approach is easy to implement while performing reasonably well.\n- Similar to (Anil et al. 2019), the approach is very efficient requiring only a single forward pass for certification, and it performs substantially better on MNIST in comparison with (Anil et al. 2019). \n- The expressiveness of the architecture is analyzed, though the proof is simple, it is nice to settle the issue within the paper.\n- I like that they are studying  $\\ell_{\\infty}$ robustness since it has been shown to be a more important problem compared to $\\ell_{2}$ robustness (Goodfellow et al. 2018). This is in contrast with the recent popular randomized smoothing approach, which tends to focus more on $\\ell_{2}$ robustness.\n\n\n**Weakness:**\n- The experiments do not include results for the convolutional variant of the model nor results for CIFAR-10. It is odd that the convolutional variant of the model is not included since the original AdderNet was developed specifically for convolution. Even though (Anil et al. 2019) did not include results for CIFAR-10, all the other related papers (Wong et al. 2018, Sven 2018, Zhang 2019)  included results for CIFAR-10. I don’t think performance on these experiments is a deal-breaker, but it is important to include these results so that future researchers can build upon your work and put your work in the context of existing literature.\n\n**Recommendation**\n\nOverall, I like the paper and recommend acceptance. I would further raise the score if the experimental concern above is addressed.\n\nI find enforcing the 1-Lipschitz property through architecture to be a very promising direction for efficient robustness certification, and the work proposes an interesting and reasonably effective method for enforcing the 1-Lipschitz property with respect to $\\ell_{\\infty}$ norm. My main concern is that the experiments are not comprehensive enough. It is okay if it does not significantly outperform the previous methods, but it would be easier for the community to build upon your work if experiments are more comprehensive.\n\n\n**Miscellaneous:**\n- Since the approach is so similar to AdderNet, I recommend giving more credit to it. I wouldn’t have realized the similarities between them unless I dug into the citation.\n- In Table 1 and 2, why are IBP, CROWN-IBP, and GroupSort considered as not scalable in the comparison? IBP & CROWN-IBP only cost ~2 times for certification compared to normal inference. Groupsort network requires only a single forward pass to calculate the certified radius. \n- The generalization bound looks nice but I find that it slightly distracts from the main point of the paper. I am not too keen on the generalization bound that depends on Rademacher complexity in general since it does not consider the model learnable through gradient descent (not that it is an easy thing to do). This comment is more for future references, and I am okay with the way the paper is laid out right now.\n\n\n[1] Chen, Hanting, et al. \"AdderNet: Do we really need multiplications in deep learning?.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020.\n\n[2] Goodfellow, Ian. “Defense against the Dark Arts: An overview of adversarial example security research and future research directions.” https://www.iangoodfellow.com/, 2018, https://www.iangoodfellow.com/slides/2018-05-24-DLS.pdf. Accessed 2020.\n\n[3] Anil, Cem, James Lucas, and Roger Grosse. \"Sorting out lipschitz function approximation.\" International Conference on Machine Learning. 2019.\n\n[4]Wong, Eric, and Zico Kolter. \"Provable defenses against adversarial examples via the convex outer adversarial polytope.\" International Conference on Machine Learning. PMLR, 2018.\n\n[5]Gowal, Sven, et al. \"On the effectiveness of interval bound propagation for training verifiably robust models.\" arXiv preprint arXiv:1810.12715 (2018).\n\n[6]Zhang, Huan, et al. \"Towards Stable and Efficient Training of Verifiably Robust Neural Networks.\" International Conference on Learning Representations. 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EO0vjFJzjVq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new kind neural network based on a new kind of activation function, the L_\\infty-Dist neuron, which they then demonstrate how to train, and show is both experimentally and certifiably robust.  Furthermore, they provide a theoretical result demonstrating that the network can approximate any desired function.\n\nIn terms of novelty, this paper has a lot of promise.  In particular:\n* This approach to producing robust networks appears promising and fundamentally different from other approaches which either certify preexisting networks or smoothing approaches built on top of preexisting architectures.\n* The theoretical result that their network can approximate lipschitz continuous functions is a helpful addition when considering an entirely new architecture.\n* The training approach for a network without multiplications seems like a novel contribution in its own right. \n\nHowever, the experimental section is lacking which diminishes my score.  Specifically, my main issue is that the utility of the method is dependent on its advantage over prior robust training and certification algorithms, and here it is only shown to perform similarly to prior approaches on the easy datasets of MNIST and FashionMNIST.  To properly evaluate the method, more difficult datasets need to be demonstrated, in particular - CIFAR10.   On Fashion-MNIST, no comparison is made to IBP in standard accuracy and while it outperforms CAP, cap is known to underperform other methods on other datasets.\n\n=======================================================================\nUpdate:\n\nI thank the authors for providing additional data, however the additional data is insufficient for me to recommend acceptance.   While the approach is certainly novel, it appears to performs worse in the relevant metrics than other methods while working on less standard networks.  As the networks are so far from standard, it is necessary to see how they (and the method) behave on commonly accepted datasets.\n\nFurthermore, AnonReviewer4 pointed out the similarities to AdderNet which I had overlooked.   Given these similarities I expect a more thorough methodological and experimental comparison to the original AdderNet.", "extra_scores": {}, "extra_text": {}}, {"review_id": "49etAdFtzAd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discussed a technique to obtain a neural network with verifiable\nrobustness guarantee. The approach is based on a redesign of neural network\nbuilding blocks. Instead of using matrix multiplication, the authors propose\nto use the L_\\infty norm operator, which is itself non-linear and Lipschitz.\nThe authors successfully train L_\\infy network with several training tricks on\nMNIST and Fashion-MNIST, and the verified accuracy is close to the\nstate-of-the-art results.\n\nStrength:\n\n1. The idea of using L_\\infty operations as basic building blocks of a neural\nnetwork is simple. It provides verifiable robustness in a new way, and can be\nuseful for future works on improving verifiable robustness.\n\n2. The authors prove that a Linf-dist net is an universal function\napproximator for bounded 1-Lipschitz functions.\n\n3. The authors discuss a few training tricks to train L_\\infty net, such as\nusing an increasing p norm (from a small value to infinity) during training.\n\n4. The paper is overall well written, well motivated and organized well.\n\nWeakness:\n\n1. Only very limited empirical evaluation is done on two small datasets.\nEspecially, it is claimed that the proposed approach is \"scalable\", yet only\nresults on small datasets are shown. Actually, in my opinion IBP is also\nscalable; CROWN-IBP has recently been scaled up to ImageNet as well (according\nto information on their github [1]).\n\n2. It is unclear if L_\\infty net can be extended to convolutional neurons to\nwork on larger datasets such as CIFAR. I think it should be possible to use\nconvolutional neurons with weight sharing here, so if the authors can include\nconvolutional L_\\infty net results that will be a big plus.\n\n3. The approach cannot outperform existing baselines (IBP and CROWN-IBP) on\nMNIST and Fashion-MNIST. But I am okay with it. If the authors can show L_\\infy\nnet on more challenging dataset such as CIFAR-10, it might be able to\noutperform previous baselines.\n\nOther points:\n\n1. In table 2 why there is no standard acc and robust acc for IBP? And why not\ninclude CROWN-IBP results as in Table 1 (it should be quite easy to change\nMNIST to Fashion-MNIST in training). \n\n2. In section 3.1 an inaccurate reference is given for the NP-completeness of\nrobustness verification. The correct paper to cite is Katz et al. [2], which\ngives the proof in section I. The currently cited paper discussed complexity of\napproximate verification algorithm which is a different setting.\n\n3. Is it possible to generalize the L_\\infty network to other general p norms\nsuch as the L2 norm? A recent work on L2 norm verifiable training is [3].\n\n\nDespite that the evaluation of the proposed algorithm is relatively weak, I\nappreciate this approach and I am overall positive with this paper. I hope the\nauthors can provide more evaluation results as mentioned above during the\ndiscussion period to make this paper stronger. I will consider increasing my\nrating based on the author's response.\n\n\n[1] Xu, Kaidi, et al. \"Provable, Scalable and Automatic Perturbation Analysis on General Computational Graphs.\" NeurIPS 2020. https://arxiv.org/pdf/2002.12920\n\n[2] Katz, Guy, et al. \"Reluplex: An efficient SMT solver for verifying deep neural networks.\" International Conference on Computer Aided Verification. Springer, Cham, 2017.\n\n[3] Singla, Sahil, and Soheil Feizi. \"Second-Order Provable Defenses against Adversarial Attacks.\" ICML 2020. arXiv:2006.00731 (2020).\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a theoretically principled neural network that inherently resists ℓ∞ perturbations without the help of adversarial training. Although the authors insist to focus on the novel design with comprehensive theoretical supports, the reviewers still concern the insufficient empirical evaluations despite the novel idea and theoretical analysis.
Decision: Reject