Boosting the Certified Robustness of L-infinity Distance Nets
Authors: Bohang Zhang
Du Jiang
Di He
Liwei Wang
Venue: ICLR 2022 Poster (2022)
Keywords: Adversarial Robustness
Certified Defense
Lipschitz Network

Abstract: Recently, Zhang et al. (2021) developed a new neural network architecture based on $\ell_\infty$-distance functions, which naturally possesses certified $\ell_\infty$ robustness by its construction. Despite the novel design and theoretical foundation, so far the model only achieved comparable performance to conventional networks. In this paper, we make the following two contributions: $\mathrm{(i)}$ We demonstrate that $\ell_\infty$-distance nets enjoy a fundamental advantage in certified robustness over conventional networks (under typical certification approaches); $\mathrm{(ii)}$ With an improved training process we are able to significantly boost the certified accuracy of $\ell_\infty$-distance nets. Our training approach largely alleviates the optimization problem that arose in the previous training scheme, in particular, the unexpected large Lipschitz constant due to the use of a crucial trick called \textit{$\ell_p$-relaxation}. The core of our training approach is a novel objective function that combines scaled cross-entropy loss and clipped hinge loss with a decaying mixing coefficient. Experiments show that using the proposed training strategy, the certified accuracy of $\ell_\infty$-distance net can be dramatically improved from 33.30% to 40.06% on CIFAR-10 ($\epsilon=8/255$), meanwhile outperforming other approaches in this area by a large margin. Our results clearly demonstrate the effectiveness and potential of $\ell_\infty$-distance net for certified robustness. Codes are available at https://github.com/zbh2047/L_inf-dist-net-v2.

Published as a conference paper at ICLR 2022
BOOSTING THE CERTIFIED ROBUSTNESS OF L-INFINITY DISTANCE NETS
Bohang Zhang'
Du Jiang'
Di Hel!
Liwei Wang 1.3
"Key Laboratory of Machine Perception, MOE, School of Artificial Intelligence. Peking University *International Center for Machine Learning Research, Peking University
2 Microsoft Research
zhangbchang@pku edu.en 00000132270p0 edu, di di_he8pku. edu. wanglwecis pku. edu.en
ABSTRACT
Recently, Zhang et al. (2021) developed new neural network architecture based on l distance functions, which naturally possesses certified foe robustness by its construction. Despite the novel design and theoretical foundation, so far the model only achieved comparable performance to conventional networks. In this paper, we make the following two contributions: (i) We demonstrate that -distance nets enjoy fundamental advantage in certified robustness over conventional net- works (under typical certification approaches); (ii) With an improved training pro- are able to significantly boost the certified accuracy of l -distance nets. Our training approach largely alleviates the optimization problem that arose in the previous training scheme, in particular, the unexpected large Lipschitz constant due to the use of a crucial trick called fx-relaxation. The core of our training ap- proach is novel objective function that combines scaled cross-entropy loss and clipped hinge loss with a decaying mixing coefficient. Experiments show that us- ing the proposed training strategy, the certified accuracy of -dittace net can be dramatically improved from 33. 33.00% to 40.06% on CIFAR-10 (c = 8/255), mean- while outperforming other approaches in this area by large margin. Our results clearly demonstrate the effectiveness and potential of L distance net for certified robustness. Codes are available https///ithub.cco//bb/////./.1 -itt
INTRODUCTION
Modern neural networks, while achieving high accuracy various tasks, are found to be vulnerable to small, adversarially-chosee perturbations of the inputs (Szegedy et al., 2013; Biggio et al., 2013). Given image correctly classified by neural network, there often exists small adversarial per- turbation 8, such that the perturbed image x + ö looks indistinguishable to æ, but fools the network to predict incorrect class with high confidence. Such vulnerability creates security concerns in many real-world applications.
large body of works has been developed to obtain robust classifiers. One line of works proposed heuristic approaches that are empirically robust to particular attack methods, among which adver- sarial training is the most successful approach (Goodfellow al., 2014; Madry et al., 2017: Zhang et al., 2019a). However, a variety of these heuristics have been subsequently broken by stronger and adaptive attacks (Carlini & Wagner, 2017; Athalye et al., 2018: Uesato al., 2018; Tramer al., 2020; Croce & Hein, 2020), and there are no formal guarantees whether the resulting model is truly robust. This motivates another line of works that seeks certifiably robust classifiers whose prediction is guaranteed to remain the same under all allowed perturbations. Representatives of this field use convex relaxation (Wong & Kolter, 2018; Mirman et al., 2018; Gowal et al., 2018; Zhang et al., 2020b) or randomized smoothing (Cohen et al., 2019; Salman al., 2019a; Zhai et al., 2020; Yang et al., 2020a). However, these approaches typically suffer from high computational cost, yet still cannot achieve satisfactory results for commonly used lo -nom perturbation scenario.
Recently, Zhang et al. (2021) proposed a fundamentally different approach by designing a new net- work architecture called fox distance net, name coming from its construction that the basic neuron defined as the l-. -isstance function. Using the fact that any -de-tttancce net is inherently a 1- I Lipschitz mapping,
easily check whether the prediction is certifiably robust for given data

---

Published as a conference paper at ICLR 2022
point according to the output margin. The whole procedure only requires a forward pass without any additional computation. The authors further showed that the model family has strong expres- sive power, e.g., large enough -di-ttancc net approximate any I-Lipschitz function on bounded domain. Unfortunately, however, the empirical model performance did not well reflcct the theoretical advantages. As shown in Zhang al. (2021), it is necessary to multi-layer perception (MLP)' on top of an -distanncc net backbone to achieve better performance compared to the baseline methods. makes both the training and the certification procedure compli- cated. More importantly. it calls into question whether the foc -distance net is really better model configuration than conventional architectures in the regime of certified robustness.
conventional
In this paper, we give an affirmative answer by showing that lo distancee net itself suffices for good performance and can be well learned using an improved training strategy. We first mathematically prove that under mild assumptions of the dataset, there exists an fo -distance net with reasonable size by construction that achieves perfect certified robustness. This result indicates the strong expressive power of disttannc nets in robustness certification, and shows fundamental advantage over conventional networks under typical certification approaches (which do not possess such expressive power according to Mirman et al. (2021)). However, it seems contradict the previous empirical observations, suggesting that the model may fail to find an optimal solution and further motivating us revisit the optimization process designed in Zhang et al. (2021).
Due to the non-smoothness of the disttance function, Zhang et al. (2021) developed several train- ing tricks to overcome the optimization difficulty. A notable trick is called the fp-relaxation, in which ly dp-distance neurons are used during optimization to give a smooth approximation of -isttanne However, we find that the relaxation on neurons unexpectedly relaxes the Lipschitz constant of the network to an exponentially large value, making the objective function no longer maximize the robust accuracy and leading to sub-optimal solutions.
We develop a novel modification of the objective function to bypass the problem mentioned above. The objective function is a linear combination of a scaled cross-entropy term and modified clipped hinge term. The cross-entropy loss maximizes the output margin regardless of the model's is Lips- chitzness and makes optimization sufficient at the early training stage when p is small. The clipped hinge loss then focuses robustness for correctly classified samples at the late training phase when p approaches infinity. The switch from cross-entropy loss to clipped hinge loss is reflected in the mixing coefficient, which decays to zero p grows to infinity throughout the training procedure.
Despite its simplicity. our experimental results show significant performance gains on various datasets. In particular, an lx -distance net backbone on CIFAR-10 (c = 8/255). This goes far beyond the previous results, which achieved 33.30% cer- tified accuracy on CIFAR-10 using the same architecture (Zhang et al., 2021). Besides, it surpasses the relaxation-bart basedd certification approaches by at least 5 points (Shi et al., 2021; Lyu et al., 2021), establishing new state-of-the-an result.
achieve 40.06% certified robust accuracy
To summarize, both the theoretical finding and empirical results in this paper demonstrate the merit of -isttance net for certified robustness. Considering the simplicity of the architecture and train- ing strategy used in this paper, we believe there are still many potentials for future research of -distanee nets, and more generally, the class of Lipschitz architectures.
PRELIMINARY
In this section, we briefly introduce the disttate net and its training strategy. An -dittane net constructed using dds-tante neurons as the basic component. The lo -isttacee neuron u takes vector as the input and calculates the f -norm distance between æ and parameter w with bias term 6. The neuron can be written as
u( {w, (w)b)) || w|10c + b.
(1)
Based on the neuron definition, a fully-connected -istaacce net can then be constructed. Formally, an layer network g takes x (0) = x as the input, and the Ith layer (0 is calculated by
x (1) u( (w (1.) (('))) (-- (b.))) bl
(1) IE [L] [nv].
(2)
Without any confusion, in this paper, a conventional neural network model is referred to network composed of linear transformations with non-linear activations.
2

---

Published as a conference paper at ICLR 2022
Here ny is the number of neurons in the ith layer. For K-class classification problems, ne K. The network outputs ((x) .x(4) as logits and predicts the class arg max [K] (z()),
important property of -distanne net is its Lipschitz continuity, as stated below.
Definition 2.1. A mapping f(z) : R" + Rn called X-Lipschitz with respect to ly-norm ||- if for any 21, 22, the following holds:
ll f(2))llp S A|| =22lp-
(3)
The mapping of an fx distance layer is 1 1-Lipschitz with respect to lo norm. Thus by composition, any lox distance net g()) is 1-Lipschitz with respect to -orrm.
Proposition 2.2.
Lo distancee nets naturally possess certified robustness using the Lipschitz property. In detail, for any data point a with label y. denote the output margin of network g as
(4) If æ is correctly classified by g. then the prediction of perturbed input a + 8 will remain the same as æ if ||0]|cc < margin( v: g)/2. In other words, we can obtain the certified robustness for a given perturbation level c according to Ii(margin(z: y: g)2 > c), where I(.) is the indicator function. We call this margin-based certification. Given this certification approach, corresponding training approach can then be developed, where one simply learns large margin classifier using standard loss functions, e.g., hinge loss, without resorting to adversarial training. Therefore the whole training procedure is as efficient as training standard networks with no additional cost.
margin( yi [g(x))
max jFy
(m)x]
Zhang et al. (2021) further show that foe distance nets are Lipschitz-universal approximators. In detail, a large enough lx -distance net can approximate any 1-Lipschitz function with respect to lo -nom on a bounded domain arbitrarily well.
Training foo distance nets. One major challenge in training -distancc net is that the loo distance operation is highly non-smooth, and the gradients (i.e. Valxx-wi fofe-wwlee w|l.c and V Vwllx- Fwlxx-ue - are sparse. To mitigate the problem, Zhang et al. (2021) used lp-distance neurons instead of l -distance ones during training, resulting in approximate and non-sparse gradients. Typically p is set to small value (e.g.. 8) in the beginning and increases throughout training until it reaches a large number (e.g., 1000). The authors also designed several other tricks further address the optimization difficulty. However, even with the help of tricks, -de-ttanccce nets only perform competitively to previous works. The authors thus considered using hybrid model architecture, in which the -distance net serves as robust feature extractor, and an additional conventional multi-layer perceptron is used as the prediction head. This architecture achieves the best performance, but both the training and the certification approach become complicated again due to the presence of non-Lipschitz MLP layers.
EXPRESSIVE POWER OF Lo -DISTANCE NETS IN ROBUST CLASSIFICATION
In this section, we challenge the conclusion of previous work by proving that simple lo -distanee nets (without the top MIP) suffice for achieving perfect certified robustness classification. Recall that Zhang et al. (2021) already provides universal approximation theorem, showing the expressive power of -distance nets to represent Lipschitz functions. However, their result focuses on real- valued function approximation and is not directly helpful for certified robustness in classification. One may ask: Does a certifiably robust loc disttace net exist given a dataset? If so, how large does the network need to be? We will answer these questions and show that one can explicitly construct an 20 -istancee net that achieves perfect certified robustness as long as the dataset satisfies the following (weak) condition called r-separation (Yang et al., 2020b).
Definition 3.1. (r-separation) Consider labeled dataset D {(x;, y:)} where y; [K] is the label of x; We say D is r-separated with respect to fp-norm if for any pair of samples (ær, Wi), (4), My), as long as Y: * yj. one has ||a,- =x 2r.
Table The r-separation property of commonly used datasets, taken from Yang et al. (2020b).
Dataset
r
commonly used
MNIST 0.369
0.3
CI
0.106
8/255
3

---

Published as a conference paper at ICLR 2022
It is easy to see that r-separation is necessary condition for robustness under Lg nn-norm perturbation é = r. In fact, the condition holds for all commonly used datasets (e.g., MNIST, CIFAR-10). the value of in each dataset is much greater than the allowed perturbation level in Yang et al. (2020b) (see Table 1 above). The authors took a further step and showed there must exist classifier that achieves perfect robust accuracy if the condition holds. We now prove that even if we restrict the classifier to be the network funccion class represented by Exc-distance nets, the conclusion is still correct: simple two-layer -isttannc net with hidden size (n)) can already achieve perfect robustness for r-separated datasets.
is demonstrated
Let 'D be dataset with elements satisfying the r-separation condition with respect to bo--oom Then there exists a two-layer & disttanne net with hidden size n, such that when using margin-based certification, the certified & robust accuracy 100% on D under perturbation e r.
Theorem 3.2.
Proof sketch. Consider a two layer lo -distance net g defined in Equation (2). Let its parameters be assigned by
w Zt b. =0
for i [1a]
(2.5) = C. I(y: j) = -CC for i E [m].] E [K]
wi
where C == 4 max;e[s] || so is constant, and I(.) is the indicator function. For the above assign- ment, can be proved that the network outputs
[g(x)), = xj ve <e
min
|
- xz loa-
(5)
From Equation (5) the network can represent a nearest neighbor classifier, in that it outputs the negative of the nearest neighbor distance between input æ and the samples of each class. Therefore, given data æ z; in dataset DD the output margin of g(x) is at least 2r due to the r-separation condition. In other words, 9 achieves 100% certified robust accuracy on D.
Remark 3.3. The above result can be extended to multi-layer networks. In general, we can prove the existence of such networks with L layers and no more than (nn/ L + K + d) hidden neurons for each hidden layer where d is the input dimension. See Appendix A for details of the proof.
The significance of Theorem 3.2 can be reflected in the following two aspects. Firstly, our result explicitly shows the strong expressive power of f nets in robust classification, which complements the universal approximation theorem Zhang et al. (2021). Moreover, Theorem 3.2 gives upper bound of (1) on the required network size which is close to practical applications. much smaller than the size needed for function approximation (O(1/e4) under approximation error E, proved in Zhang et al. (2021)), which scales exponentially in the input dimension d.
Secondly, our result justifies that for well-designed architectures, using only the global Lipschitz property is sufficient for robustness certification. It contrasts to the prior view that suggests lever- aging the local Lipschitz constant is necessary (Huster et al., 2018), which typically needs sophisti- cated calculations (Wong al., 2018; Zhang et al., 2018; 2020b). More importantly, as compar- ison, Mirman et al. (2021) very recently proved that for any conventional network, the commonly- used interval bound propagation (IBP) (Mirman et al., 2018; Gowal et al., 2018) intrinsically cannot achieve perfect certified robustness on a simple r-separation dataset containing only three data points (under = r). In other words, -ds-tanaec nets certified using the global Lipschitz property have a fundamental advantage over conventional networks certified using interval bound propagation.
4 INVESTIGATING THE TRAINING OF foe -IISTANCE NETS
Since robust loo distance nets exist in principle, the remaining thing is understanding why the cur- rent training strategy cannot find robust solution. In this section, we first provide evidence that the training method in Zhang al. (2021) is indeed problematic and cannot achieve good certified robustness, then provide novel way to address the issue.
4.1 PROBLEMS OF THE CURRENT TRAINING STRATEGY
As shown in Scction 2, given any perturbation level e, the certified accuracy of data point æ can be calculated according to [maargin(x, yi g)/2 > é) for I-Lipschitz functions. Then the hinge loss becomes standard to learn robust loc -distance net:
Lringe gg, D: BEDDEDD [max (0 margin ((,,, 0}]
4

---

Published as a conference paper at ICLR 2022
p-3
p=22
D-100
P-1000
50
percenaaee 194)
300
cartiffee
25-
20
train
10000
2000
10
12
opoch
hinge Uhreshold (eld)
(a)
(b)
Figure 1: Experiments -distttac net training on CIFAR- dataset using the hinge loss function. Training details can be found in Section 5.1. (a) The percentage of training samples with output margin greater than throughout training. We use very long training epochs, and the final percentage is still below 2.5%. The dashed lines indicate different p values of E--distance neurons. (b) The certified accuracy training dataset and test dataset respectively, trained using different hinge threshold Training gets worse when 0 S 6c.
where 0 is the hinge threshold which should be larger than 2e. Hinge loss aims at making the output margin for any sample greater than 0, and Lnnge (g. D; 0) = if and only if the network achieves perfect certified robustness training dataset under perturbation
0/2.
Hinge loss fails to learn robust classifiers. We first start with some empirical observations. Con- sider plain for distance net trained on CIFAR-10 dataset using the same approach and hyper- parameters provided in Zhang et al. (2021). When the training finishes, we count the percentage of training samples whose margin greater than i.e., achieving zero loss. We expect the value be large if the optimization is successful. However, the result surprisingly reveals that only 1.62% of the training samples are classified correctly with a margin greater than 6. Even if we use much longer training epochs (e.g. 4000 epochs CIFAR-10), the percentage is still below 2.5% (see Figure I(a)). Thus we conclude that hinge loss fails to optimize well for most of the training samples.
Since the output margins of the vast majority of training samples are less than 0, the loss approxi- mately degenerates to a linear function without the maximum operation:
Lhinge (g. D; Ro Eningg (g. D; 0) = E m; MDED [0 margin x,, y:i
peD [margin (z,, 9) g)]
where 0 becomes irrelevant, and training becomes optimize the average margin over the dataset regardless of the allowed perturbation which is definitely problematic.
After checking the hyper-parameters used Zhang et al. (2021), we find that the hinge threshold is set to 80/255, which is much larger than the perturbation level e = 8/ 8/255. This partly explains the above degeneration phenomenon, but it still unclear why such a large value has be taken. We then conduct experiments to see the performance with different chosen hinge thresholds 0. The results are illustrated in Figure (b)) As one can see, a smaller hinge threshold not only reduces certified test accuracy but even makes training worse.
Why does this happen? We find that the reason for the loss degeneration stems from the 4p- relaxation used in training. While re-relaxtioon alleviates the sparse gradient problem, it destroys the Lipschitz property of the loo distancee neuron, as stated in Proposition 4.1:
Proposition 4.1. layer constructed using ly ey-distance neurons
Up(ax, {w. b}) = || - wllp -
(8)
is d Lipschitz with respect to lox-norm where d is the dimension of x. Thus by composition, layer dy-distance net is d Lipschitz with respect to foo-n
Zhang al. (2021) uses small p in the beginning and increases its value gradually during training. From Proposition 4.1, the Lipschitz constant of the smoothed network can be significantly large" at
FFor a 6-layer E, disdistnnce net (p- = 8) with hidden size 5120 used in Zhang et al. (2021), Proposition 4.1 approximately gives Lipschitz constant of 568. We also run experiments to validate such upper bound is relatively tight. See Appendix C. for more details.
5

---

Published as a conference paper at ICLR 2022
the early training stage. Note that the robustness certification II(margin(2, 9: 9) c) holds for 1-Lipschitz functions. When the Lipschitz constant is large, even if the margin of a data point passes the threshold, the data point can still lie near to classification boundary. This makes the training using hinge loss ineffective at the early stage and converge to a wrong solution far from the real optima. We argue that the early-stage training is important when p rises to large value, the optimization becomes intrinsically difficult to push the parameters back to the correct solution due to sparse gradients.
Such argument can be verified from Figure (()), in which we plot the percentage of training samples with margins greater than 9 throughout a long training process. After p starts rise, the margin decreases drastically, and the percentage sharply drops and never increases again during the whole lp-relaxation procedure. is also clear why the value of must be chosen to be much larger than 2c. For small f, the margin optimization becomes insufficient at early training stages when the I Lipschitz constant is exponentially large, leading to worse performance even on the training dataset.
4.2 OUR SOLUTION
In the previous section, one can see that the hinge loss and the fp-relaxation are incompatible. As the f,-relaxation essential to overcome the sparse gradient problem, we focus on developing better loss functions. We show in this section that a simple change of the objective function can address the above problem, leading to non-trivial improvements.
We approach the issue by investigating the commonly used cross-entropy loss. For conventional non-Lipschitz networks, cross-entropy loss aims at increasing the logit of the true class while de- creasing the other logits much as possible, therefore enlarges the output margin without a thresh- old constraint. This makes the optimization of output margin sufficient regradless of the Lipschitz constant, which largely alleviates the problem in Section 4.1 for training fp-distance nets with small Such findings thus motivate us to replace hinge loss with cross-entropy. However, on the other hand, cross-entropy loss only coarsely enlarges the margin, rather than exactly optimizing the sur- rogate of certified accuracy [(margin( g)g)/2 < e) that depends on When the model is almost I-Lipschitz (i.e. p approaches infinity), hinge loss can still be better than cross-entropy. In other words, cross-entropy loss and hinge loss are complementary.
Based on the above argument, we propose to simply combine cross-entropy loss and hinge loss to obtain the following objective function:
C(g, D)0)
E ((,,))) AlEE(s g(z:). vs) + (einge (z. (0).).))1)))
(9)
scaled cnoss-entropy Joss
olipped hingo loss
where (CE(z, y) = log(E, exp(2;)) Zy and Einng (z, u) = max | m Zi By + 1,0 We now
make detailed explanations about each term in Equation (9).
Scaled cross-entropy loss (CE(s g(:;), w:). Cross-entropy loss deals with the optimization issue when p is small. Here a slight difference is the introduced scaling s as is explained below. We know cross-entropy loss is invariant to the shift operation (adding a constant to each output logit) but not scaling (multiplying a constant). For conventional networks, the output logits are produced through the last linear layer, and the scaling factor can be implicitly learned in the parameters of the linear layer to match the cross-entropy loss. However, distance net is strictly 1-Lipschitz and does not have any scaling operation. We thus introduce a learnable scalar (temperature) that multiplies the network output g (x:)) before taking cross-entropy loss. We simply initialize it to be 1. Note that s does not influence the classification results and can be removed once the training finishes.
Clipped hinge loss min (g (g(x;)/ //0, y:), 1}. Clipped hinge loss is designed to achieve robust- ness when p approaches infinity. Unlike the standard hinge loss, the clipped version plateaus if the output margin is negative (i.e., misclassified). In other words, clipped hinge loss is equivalent to applying hinge loss only on correctly samples. The reason for applying such a clipping is folee-fold. (i) Scaled cross-ent cross-entropy loss already focuses on learning a model with high (clean) accuracy, thus there is no need to optimize on wrongly-classifiet samples duplicatively using hinge loss. Moreover, cross-entropy is better than hinge loss when used in classification, as the gradient of hinge loss makes optimization harder (ii) In the late training phase, the optimization becomes
The gradient of hinge loss w.r.t. output logits is sparse (only two non-zero elements) and does not make full use of the information provided by the logit.

---

Published as a conference paper at ICLR 2022
intrinsically difficult (p approaching infinity). As consequence, wrongly classified samples may have little chance to be robust. Clipped hinge loss thus ignores these samples and concentrates on easier ones to increase their potential to be robust after training. (iii) The clipped hinge loss is a bet- ter surrogate for 0-1 robust error T (margin (a: y: g)/2 S <). Compared with hinge loss, the clipped version is closer our goal and more likely achieve better certified accuracy. Finally, due the presence of cross-entropy loss, we will show in Section 5.3 that the hinge threshold 0 can be set to a much smaller value unlike Figure I(b), which thus avoids the loss degeneration problem.
The mixing coefficient X. The coefficient À in loss (9) plays a role in the trade-off between cross- entropy and hinge loss. Based on the above motivation, we use decaying that attenuates from A to zero throughout the process of l relrelxxtioon (Ao is a hyper- hyper-parameter). When p is small at the early training stage, we focus more on cross-entropy loss. After p grows large, vanishes, and a surrogate of 001 robust error is optimized.
We point out that objective functions similar to (9) also appeared in previous literature. In particular, the TRADES loss (Zhang et al., 2019a) and MMA loss (Ding et al., 2020) are both composed of a mixture of the cross-entropy loss and a form of robust loss. Nevertheless, the motivations of these methods are quite different. For example, TRADES was proposed based on the theoretical results suggesting robustness may be at odds with accuracy (Tsipras et al., 2019), while our training approach is mainly motivated by the optimization issue. Furthermore, the implementations of these methods also vary a lot. We use clipped hinge loss to achieve robustness due to its simplicity, and uses decaying Ả correlate p in fp-relaxation due the optimization problem in Section 4.1.
5 EXPERIMENTS
5.1 EXPERIMENTAL SETTING
In this section, we evaluate the proposed training strategy on benchmark datasets MNIST and CIFAR-10 to show the effectiveness of disttancc net.
Model details. We use exactly the same model as Zhang et al. (2021) for a fair comparison. Con- cretely, we consider the simple fully-connect -distanne nets defined in Equation (2). All hidden layers have 5120 neurons. We use a 5-layer network for MNIST and a 6-layer one for CIFAR-10.
Training details. In all experiments, we choose the Adam optimizer with a batch size of 512. The learning rate is set to 0.03 initially and decayed using a simple cosine annealing throughout the whole training process. We use padding and random crop data augmentation for MNIST and CIFAR-IO, 10, and also use random horizontal flip for CIFAR-10. The ty-relaxation starts at p = and ends at p = 1000 with increasing exponentially. Accordingly, the mixing coefficient À decays exponentially during the fp-relaxation process from As to a vanishing value Xend. We do not use further tricks that are used in Zhang et al. (2021), e.g. the lp weight decay warmup over perturbation e, to keep our training strategy clean and simple. The datasct dependent hyper-parament parameters, including 9, λo And and the number of epochs T, can be found in Appendix B. All experiments are run for 8 times on a single NVIDIA Tesla- V100 GPU, and the median of the performance number is reported.
Evaluation. We test the robustness of the trained models under c-bounded & -nom perturbations. Following the common practice (Madry et al., 2017), we mainly use = 0.3 for MNIST dataset and 8 8/555 for CIFAR-10 10 dataset. We also provide results under other perturbation magnitudes, e.g. e = 0.1 for MNIST and e 2/255, e = 16/255 for CIFAR-10. We first evaluate the robust test accuracy under the Projected Gradient Descent (PGD) attack (Madry al., 2017). The number of iterations of the PGD attack is set to large number of 100. We then calculate the certified robust accuracy based on the output margin.
5.2 EXPERIMENTAL RESULTS
Results are presented in Table 2. For each method in the table, we report the clean test accuracy without perturbation (denoted as Clean), the robust test accuracy under PGD attack (denoted as PGD), and the certified robust test accuracy (denoted as Certified). We also compare with random- ized smoothing (see Appendix D), despite these methods provides probabilistic certified guarantee and usually take thousands of times more time than other approaches for robustness certification.
7

---

Published as a conference paper at ICLR 2022
Table 2: Comparison of our results with existing methods.
Dataset
Method
Reference
Clcan
PGD
Certified
CAP
(Wong 2018)
98.92
96.33
IBP
(Gowal al., 2018)
98.92
97.98
97.25
CROWN-IBP
(Zhang et al., 2020b)
98.83
98. 19.19
97.76
0.1
IBP
(Shi ct al., 2021)
98.84
97.95
COLT
(Balunovic & Vochev, 2020)
99.2
97.1
foc-distance Net?
(Zhang al., 2021)
98.66
97.794
97.70
MNIST
fos-distance Net
This paper
98.93
98.03
97.95
IBP
(Gowal al., 2018)
97.88
93.22
91.79
CROWN-IBP
(Zhang et al., 2020b)
98.18
93.95
92.98
IBP
(Shi et al., 2021)
97.67
93.10
0.3
COLT
(Balunovic & Vechev, 2020)
97.3
85,71l
distance Net-MI.P
(Zhang al., 2021)
98.56
95.281
93.09
dis-tintance
(Zhang ct al., 2021)
98.54
94.71
92.64
Loo distance
This paper
98.56
94.73
93.20
CAP
(Wong 2018)
53.89
IRP
(Gowal al., 2018)
61.46
50.28
44.79
CROWN-IBP
(Zhang et al., 2020b)
71.52
59.72
53.97
IBP
(Shi ct al.. 2021)
66.84
52.85
2/255
COLT
(Balunovic & Vochev, 2020)
78.4
60.5ll
Randomized Smoothing
(Blum et al., 2020)
78.8
62.6
-oe-distance Net
(Zhang et al., 2021)
60.33
$1.45*
50.94
foo distance Net
This paper
60.61
54.28
54.12
IBP
(Gowal al., 2018)
50.99
31,27
29.19
CROWN-IBP
(Zhang al., 2020b)
45.98
34.58
33.06
CROWN-IBP
(Xu et al., 2020)
46.29
35.69
33.38
CIFAR-10
TBP
(Shi et al., 2021)
48.94
34,97
CROWN-LBP
(Lyu al., 2021)
48.06
37.95
34.92
8/255
COLT
(Balunovic & Vechev, 2020)
51.7
27.5
Randomized Smoothing
(Salman ct al., 2019a)
53.0
24.0
Randomized Smoothing
(Jeong & Shin, 2020)
52.3
25.251
too distanceee Nct+MLP
(Zhang ct al., 2021)
50.80
37.061
35.42
Loo disttnne Net
(Zhang al., 2021)
56.80
37.46*
33.30
8oo distance Net
This paper
54.30
41.84
40.06
IBP
(Gowal ct al., 2018)
31.03
23,34
21.88
CROWN-IBP IBP dis-tanencce
(Zhang el al., 2020b)
33.94
24.77
23.20
16/255
(Shi et al., 2021)
36.65
24.48
(Zhang et al., 2021)
55.05
26.02F
19.28
-isttant Net
This paper
48.50
32.73
29.04
The IBP results obtained from Zhang al. (20206).
results are obtained by rumning code in the authors' github. Appendix details.
1 The number PGD steps is chosen as in Zhang et (2021).
These methods provide probabilistic certified guarantees.
Calculating certified accuracy for these methods takes several days on single GPU, which is 4 to 6 orders of magnitude
slower than other methods.
Comparing with Zhang et al. (2021). It can seen that for all perturbation levels and datasets, proposed training strategy improves the performance of -is-tann nets. In particular, boost the certified accuracy on CIFAR-10 from 33.30% to 40.06% under c = 8/ 8/255, and from 19.28% 29.04% under a larger 16/255. Note that use exactly the same architecture as Zhang et al. (2021), and a larger network with better architecture may further improve the results. Another observation from Table that the improvement of our proposed training strategy gets more prominent with the increase of e. This is consistent with our finding in Section 4.1, in that the optimization is particularly insufficient for large e using hinge loss, and in this case our proposed objective function can significantly alleviate the problem.
Comparing with other certification methods. For most settings in Table 2, our results establish new sfate-of-the-arte over previous baselines, despite we use the margin-based certification which is much simpler. The gap is most noticeable for 8/255 on CIFAR-10, where we surpass recent relaxation-based approaches by more than 5 points (Shi et al., 2021: Lyu al., 2021). It can also be observed that f -ditancce net is most suitable for the case when &oo perturbation relatively large. This is not surprising since Lipschitz property is well exhibited in this case. If is vanishingly small (e.g. 2/255), the advantage of the Lipschitz property will not be well-exploited and lz -istaacee net will face more optimization and generalization problems compared with conventional networks.
8

---

Published as a conference paper at ICLR 2022
p-1
p-
p-100
pe 1000
50
40.0
40
45-
0.02
29.47
39.92
39.8
39:43
39.79
parcetags
20
sccurscy
0.05
39.57
32.97
39.76
mangh 2:0 marge
39.4
30-
cortified test
0.2
39.8
39.42
19.12
39.22
39.12
200
400
600
800
1000
1200
1e-4
Ze-4
Se-4
1e-3
2e-3
spoch
Ninge threshold idrv)
Acea
(b)
Figure 2: Experiments of loc distance net training on CIFAR-10 10 dataset (c = 8/255) using the proposed objective function (9). (a) The percentage of training samples with output margin greater than A (bluc), less than 0 (orange), or between 0 and & (green) throughout training. The dashed lines indicate different values of fp-relaxation. (h) The final performance of the trained network using different hinge threshold 9. Heatmap of certified accuracy with different syper-parameters An and Amn. Each grid shows the certified accuracy for pair of hyper-parameters.
5.3 INVESTIGATING THE PROPOSED TRAINING STRATEGY
We finally demonstrate by experiments that the proposed training strategy indeed addresses the opti- mization problem in Section 4.1. We first trace the output margin of the training samples throughout training on CIFAR-10 dataset (e 8/ 8/255), and plot the percentage of samples with margin greater than 0, less than O, or between () and 0, shown in Figure 2(a). In contrast to Figure (a), it can be seen that the loss does not degenerate in the whole training process. We then demonstrate in Figure 2(b) that the accuracy curve regarding different choices of hinge threshold 0 is well-behaved com- pared with Figure I(b). In particular, the best that maximizes the certified accuracy on training dataset approaches 2c (while for original hinge loss the value is 6c). The peak certified accuracy training dataset also improves by 10 points (see blue lines in the two figures). Such evidence clearly demonstrates the effectiveness of the proposed training strategy.
Sensitivity analysis. We perform sensitivity analysis on CIFAR-10 dataset (c = -8/255) over hyper- parameters including the hinge threshold 0 and the mixing coefficient A. Results are shown in Figure 2(b) and 2(c). It can be seen that (i) the certified accuracy is above 39% for a wide range of 0 (between 5e and Se); (ii) among the 20 hyper-parameter combinations of (Ao, Aend). all certified accuracy results surpass 39%, and half of the results can achieve certified accuracy of more than 39.75%. In summary, the performance is not sensitive to the choice of the soper-parameters 0 and X. See Appendix F for more details on other hyper-paue parameters.
A Ablation studies. We also conduct ablation experiments for the proposed loss function on CIFAR- 10 dataset (e 8/ 8/255). Due to the space limit, we put results in Appendix E. In summary, both the cross-entropy loss and clipped hinge loss are crucial to boost the certified accuracy. Using decaying mixing coefficient À can further improve the performance and stabilize the training.
RELATED WORK
In recent years substantial efforts have been taken obtain robust classifiers. Existing approaches mainly fall into two categories: adversarial training and certified defenses.
Adversarial training, Adversarial training methods first leverage attack algorithms generate ad- versarial examples of the inputs on the fly, then update the model's parameters using these perturbed inputs together with the original labels (Goodfellow al., 2014; Kurakin et al., 2016; Madry al., 2017). In particular, Madry et al. (2017) suggested using Projected Gradient Descent (PGD) as the universal attacker to find a perturbation that maximizes the standard cross-entropy loss, which achieves decent empirical robustness. Some recent works considered other training objectives that combine cross-entrope loss and a carefully designed robust surrogate loss (Zhang et al., 2019a; Ding et al., 2020; Wang et al., 2020), which show similarities to this paper. However, all methods above are evaluated empirically using first-order attacks such as PGD, and there is no formal guarantee whether the learned model is truly robust. This motivates researchers to study type of method

---

Published as a conference paper at ICLR 2022
called certified defenses, in which the prediction is guaranteed to remain the same under all allowed perturbations, thus provably resists against all potential attacks.
Relaxation- certified defenses. These methods adopt convex relaxation to calculate a convex region containing all possible network outputs for a given input under perturbation (Wong& & Kolter, 2018; Wong et al., 2018; Dvijotham et al., 2018; 2020; Raghunathan et al., 201 20;b;;;; Weng al., 2018; Singh et al., 2018; Mirman et al., 2018; Gehr et al., 2018; Wang et al., 2018; 2021; Gowal al., 2018; Zhang et al., 2018; 2020b; Xiao al., 2019; Croce al., 2019; Balunovic & Vechev, 2020; Lee et al., 2020; Dathathri et al.. 2020; Xu et al., 2020; Lyu et al., 2021; Shi et al., 2021). If all points in this region correspond to the correct prediction, then the network provably robust. How- ever, the relaxation procedure is usually complicated and computationally expensive. Furthermore, Salman et al. (2019h); Mirman et al. (2021) indicated that there might be an inherent barrier to tight relaxation for a large class of convex relaxation approaches. This is also reflected in experiments, where the trained model often suffers from severe accuracy drop even on training data.
Randomized smoothing for certified robustness. Randomized smoothing provides another way to calculate a probabilistic certification under l2 perturbations (Lecuyer et al., 2019; Li et al., 2019a; Cohen et al., 2019; Salman et al., 2019a; Zhai et al., 2020; Jeong & Shin, 2020; Zhang et al., 2020a; Yang et al., 2022; Horváth et al., 2022). For any classifier, if a Gaussian random noise is added to the input, the resulting "smoothed" classifier then possesses certified guarantee under é2 perturba- tions. Randomized smoothing has been scaled up to ImageNet and achieves state-of-the-ard certified accuracy for le perturbations. However, recent studies imply that it cannot achieve nontrivial certi- fied accuracy for lp perturbations under ((d'/=1122) when p > 2 which depends the input dimension (Yang et al., 2020a; Blum et al., 2020; Kumar et al., 2020; Wu et al., 2021). Therefore it is not suitable for Ex perturbation scenario if is not very small.
Lipschitz networks. An even simpler way for certified robustness is to use Lipschitz networks, which directly possess margin-based based certification. Earlier works in this area mainly regard the Lip- schitz property as a kind of regularization and penalize (or constrain) the Lipschitz constant of a conventional ReLU network based on the spectral norms of its weight matrices (Cisse et al., 2017; Yoshida & Miyato, 2017; Gouk et al., 2018; Tsuzuku et al., 2018; Farnia et al., 2019; Qian & Weg- man, 2019; Pauli et al., 2021). However, these methods either can not provide certified guarantees or provide vanishingly small certified radius. Anil et al. (2019) figured out that current Lipschitz networks intrinsically lack expressivity to some simple Lipschitz functions, and designed the first Lipschitz-universal approximator called GroupSort network. Li et al. (2019h); Trockman & Kolter (2021); Singla Feizi (2021) studied Lipschitz networks for convolutional architectures. Recent studies (Leino et al., 2021; Singla al., 2022) achieved the tfate-of-the-art certified robustness using GroupSort network under le perturbations. However, none of these approaches above can provide good certified results for lo robustness. The most relevant work to this paper is Zhang al. (2021), in which the author designed novel Lipschitz network with respect to foc -oorm. We show such architecture can establish new state-of-the-ar results in the &x perturbation scenario.
CONCLUSION
In this paper, we demonstrate that a simple foo -ic-ttnt net suffices for good certified robustness from both theoretical and experimental perspectives. Theoretically, we prove the strong expressive power of disttanne nets in robust classification. Combining with Mirman al. (2021), this re- sult may indicate that -dssttnnc nets have inherent advantages over conventional networks for certified robustness. Experimentally, despite simplicity, our approach yields a large gain over pre- vious (possibly more complicated) certification approaches and the trained models establish new state-of-thhe-ar certified robustness.
Despite these promising results, there are still many aspects that remain unexplored. Firstly, in the case when e very small, foc distance nets may have lot of room for improvement. Secondly, it is important to design better architectures suitable for image classification tasks than the simple fully connected network used in this paper. Finally, it might be interesting to design better optimization algorithms for -distance nets to further handle the model's non-smoothness and gradient sparsity. We hope this work can make promising the study of &o -distance nets, and more generally, the global Lipschitz architectures for certified robustness.
10

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This work was supported by National Key R&D Program of China (2018YFB1402600) BJNSF (L112037). Project 2020BD006 supported PKUBaidu Fund.
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting lipschitz function approximation. In Inter- national Conference on Machine Learning, pp. 291-301, 2019.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense se- curity: Circumventing defenses adversarial examples. In International conference on machine learning, pp. 274-283, PMLR, 2018.
Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. In Joint European conference on 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 sigh-dimensional images. arXiv preprint arXiv:2002.03517, 2020.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten de- tection methods. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pp. 3 3-14,12222 2017.
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. International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In International conference machine learning, pp. 2206- 2216. PMLR, 2020.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu net- works via maximization of linear regions. In the 22nd International Conference on Artificial Intelligence and Statistics, pp. 2057-2066. PMLR, 2019.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Ue- sato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy S Liang, and Pushmeet Kohli. Enabling certification of verification-annoe networks via memory- semidefinite programming. Advances Neural Information Processing Systems, volume 33, pp. 5318-5331, 2020.
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 on Learning Representations, 2020.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. arXiv preprint 1803 2018.
Krishnamurthy Dj Dvijotham, Robert Stanforth, Sven Gowal, Chongli Qin, Soham De, and Push- meet Kohli. Efficient neural network verification with exactness characterization. In Uncertainty in Artificial Intelligence, pp. 497-507. PMLR, 2020.
Farzan Farnia, Jesse Zhang, and David Tse. Generalizable adversarial training via spectral normal- ization. In International Conference Learning Representations, 2019.

---

Published as a conference paper at ICLR 2022
Timon Gehr, Matthew Mirman, Dana Drachsler- Cohen, Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. Ai2: Safety and robustness certification neural networks with abstract interpreta- tion. In 2018 IEEE Symposium Security and Privacy (SP), pp. 3-18. IEEE, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 2014.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arXiv preprint arXiv:
2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprini 1rXiv:1810.127/3: 2018.
Miklós Z. Horváth, Mark Niklas Mueller, Mare Fischer, and Martin Vechev. Boosting randomized smoothing with variance reduced classifiers. In International Conference Learning Represen- tations, 2022.
Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant as defense against adversarial examples. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 16-29. Springer, 2018.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, 33, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International
Conference on Learning Representations, 2015.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. International Conference on Machine Learn- ing, pp. 5458-5467. PMLR, 2020.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning scale. arXiv preprint arXiv:1611.01255 2016.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacc. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672 IEEE, 2019.
Sungyoon Lee, Jaewook Lee, and Saerom Park. Lipschitz-certiffable training with a tight outer bound. Advances in Neural Information Processing Systems, 33, 2020.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference on Machine Learning (ICML), 2021.
Bai Li. Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems, 32:9464-9474 2019a.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Joern-Henrik Jacobsen. Preventing gradient attenuation lipschitz constrained convolutional networks. Advances in Neural Information Processing Systems, 02:15590-15402. 2019b.
Zhaoyang Lyu, Minghao Guo, Tong Wu, Guodong Xu. Kehuan Zhang, and Dahua Lin. Towards evaluating and training verifiably robust neural networks. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 4308 4317, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1706::770.000888 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. PMLR, 2018.
12

---

Published as a conference paper at ICLR 2022
Matthew Mirman, Maximilian Baader, and Martin Vechev. The fundamental limits of interval arith- metic for neural networks. arXiv preprint arXiv:211 2021.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgower. Training robust neural networks using lipschitz bounds. IEEE Control Systems Letters, 2021.
Haifeng Qian and Mark N. Wegman. L2- nonexpansive neural networks. In International Conference on Learning Representations, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference Learning Representations, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S. Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp. 10900-10910, 2018b.
Hadi Salman, Greg Yang, Jenry Li. Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. In Pro- ceedings of the 33rd International Conference Neural Information Processing Systems, pp- 11292-11303, 2019a.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relax- ation barrier tight robustness verification of neural networks. Advances in Neural Information Processing Systems, 32:9835-9888 9846, 2019b.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training with short warmup. In ICMI. 202/ Workshop on Adversarial Machine Learning, 2021.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. Advances in Neural Information Processing Systems, pp- 10802-10813, 2018
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference Ma- chine Learning, volume 139, pp. 9056997566997 PMLR, 2021.
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on CIFAR-10 and CIFAR-100. In International Conference Learning Representations, 2022.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry, On adaptive attacks to
adversarial example defenses. Advances in Neural Information Processing Systems, 33, 2020.
Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be odds with accuracy. In International Conference on Learning Representa- tions, 2019.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in neural information processing systems, pp. 6541-6550, 2018.
Jonathan Uesato, Brendan O'donoghue, Pushmeet Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference on Machine Learning, pp. 5024-5034. PMLR, 2018
Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. Advances in Neural Information Processing Systems, 34, 2021.
13

---

Published as a conference paper at ICLR 2022
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representations, 2020.
Lily Weng. Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5276-5285. PMLR, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-525929 PMLR, 2018.
Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8410-8419, 2018.
Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large family of distributions. In International Conference Artificial Intelligence and Statistics, pp. 3763-37777.. PMLR, 2021.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Mahi Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In International Conference on Learning Representations, 2019.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33, 2020.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693- 10705. PMLR, 2020a.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ Salakhutdinov, and Kamalika Chaud- huri. A closer look accuracy robustness. In Proceedings of the 34rd International Confer- ence on Neural Information Processing Systems, 2020b.
Zhuolin Yang, Linyi Li, Xiaojun Xu, Bhavya Kailkhura, Tao Xie, and Bo Li. On the certified robust- ness for ensemble models and beyond. In International Conference on Learning Representations, 2022.
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint arXiv: 10941, 2017.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-fres and scalable robust training via maximizing certified radius. In International Conference on Learning Representations, 2020.
Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying l-infinity bustness using neural networks with l-inf-dist neurons. In International Conference on Machine Learning, pp. 12368-12379. PMLR, 2021.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certification with randomized smoothing: A functional optimization based framework. Advances in Neural Information Processing Systems, 2020a.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference Machine Learning, pp. 7472-7482. PMLR, 2019a.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. In International Conference on Learning Representations, 2019b.
14

---

Published as a conference paper at ICLR 2022
Huan Zhang, Tsui-Wei Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. Advances in Neural Information Processing Systems, 31:4939-4948 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference Learning Representations, 2020b.
15

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM 3.2 AND BEYOND
Theorem A.I. Let 'D be a dataset with n. elements satisfying the r-separation condition with respect loo norm. Then there exists two-layer Lo distancee net with hidden size n, such that the certified so robust accuracy is 100% on D under perturbation =
Proof. Consider layer -distanne net g defined in Equation (2). Let its parameters be signed by
(1..)) = J; 0; =0
for E [n]] for i E [m].] [K]
(25) = C. T(u: jj) - -CC
(10)
where = max4e[n] || so is a constant, and 1(-) is the indicator function. The chosen C' large enough that the following holds:
o æ, C/2
V(a, v.),
(Z), (1), E D
(11)
For the above assignment, the first layer simply calculates the loc distancee between and each sample in dataset D. We now derive the output of the second layer. We have
[g( [g(=)) = 2/ ||x(1) w (2.))
00 + (2(2))
(b(2,)) + max
[
(1) - w (
(c(n)
- + max
max (E(m),ui
2
(1) Cl2
max
|
(1)
C + max
max vE(n),ui
||| x; - Cl max
|| - -=;11o00
(12)
-C max
(C' x - 8; 1oo)
(13)
min :E|n],y1=j
|| 2:11
(14)
Here core step is Equation (13) which follows by using Inequality (11) when the image is in dataset DD
From Equation (14) the network g can represent a nearest neighbor classifier, that it outputs the negative of the nearest neighbor distance between input and the samples of each class. Therefore, given data x = æ; in dataset D, the output [g (x);; is either 0 or less than - 2r depending on whether j = Yi. due to the r-separation condition. Therefore the output margin least 2r. In other words, g achieves 100% certified robust accuracy on D.
We now give general result which shows that any L layer (L 2 loo distance net with hidden size O(n/L + K + d) can achieve perfect certified robustness. In this general setting, the total number of neurons in the network thus O(n + KL + dL) which is still close to real practice.
Theorem A.2. Let be a dataset with n elements satisfying the r-separation condition with respect to fe norm. Then there exists an L-layer foo distance net with hidden size no more than [,-r + K + 2d where d is the input dimension, such that the certified too robust accuracy is 100% on D under perturbation
Proof. The basic idea is to rearrange the computation process of the two-layer network in the above proof by order so satisfy the width constraint. To formulate the proof below, we first define some notations. Define K prefix arrays hy E [K]) as follows:
hg.k
min
| 221loo-
(15)
VE [
Note that we want the network output to be the negative of the nearest neighbor distance of all samples in a class j. i.e. min.g || oi which corresponds hj.n- For any hidden
layer (1) (1 E [T. - 1)), we separate it into four sets: I() (xt")) [d], 7 (x( :d <is
16

---

Published as a conference paper at ICLR 2022
2d). 00 (u,
(1) 2d <i 2d K} and 8 containing the rest
- neurons. We also denote
((4) -xx E [ } for ease of presentation.
We first make construction in which the neurons of z in each layer exactly represent the input æ, e.g. x. = n3 (1 v i S d). This feasible since an -istaacce neuron can represent the operation that fetches element of the neuron input bounded domain, e.g. the following operation
u(z fur, b)) || u ~c + b b= 2j Vz IK
(16)
we assign W/y = - domain K. In this way, all hidden neurons in the network can have access the network input æ.
C, wik = 0(k * j) where C is larger than twice the diameter of
We similarly let the neurons of 7 represent the input a again, e.g. Litd = x (d < S 2d).
Next, we aim at designing the following computation pattern for O!!)
O Uhy الا-م E e.g. 2d2+
(1)
h """
(17)
In this way O(L) (hia j E [K]] and the network exactly represents nearest neighbor classi- fier which is desired. To represent ((++1) in (17), we use the following recursive relation
(1+1) = h 1 max h 2d+j
max
|
2;
(18)
Note that h h 1 x
2dd+j is already calculated in O in the previous layer. The left thing is to
(1)
calculate | xo for all E [===1 + +1,
L-1 which can be done by the neurons of the set (()) in the previous layer (which will be proven later). Assume ( represents
(1) 50 2204x++** :i [m=1]]]
()) 22++K++
x
(19)
then the neuron 22d+j merges the information of neuron x2d+5 and part of neurons (1) depending whether y4 j. using the construction similar to (10). In detail,
(I+1)
(1)
244 in S(!)
(1+1) ((+1) ||x! w (+1.24+))) + -2--- h 2d++
(20)
holds by assigning
w (1+1,22 (111,2++)
=-C. =d
for k 2d K] C -C =) for E i==1
11+1, (12d,)
2dt K+i
= --C
24+5
where a sufficiently large constant.
Now it remains to represent g()) in (19). We first consider the simplest case when / 1. In this case (1) we can directly calculate x2d+K+1 = =||x æ;| by assigning proper weights and zero bias. Now assume 2. In this case, we cannot calculate the & -dittance directly since the previous layer has irrelavant neurons, e.g. the neurons in sets (t-1)) and ((I-1), We want to only use the sets of neurons (I-1) and ((-1)) in the previous layer.
Suppose the objective is to represent || - Delloo for some i. Note that
2: = max max - ( [x:1e xx). ||
kE(d]
We assign the parameters of the lo distance neuron (') ||-(1-1) w(l + 699 for some
as follows:
w (1j))
[ac/l - C for k E [d]
(l.i)
|20,|a + C for & E [d]
d4-k
2d++
(l.f)
O
for l: E
K + -
b5) -C
17

---

Published as a conference paper at ICLR 2022
where C' is sufficiently large constant. In this way
(1-11) w + +b,)
6 + max
(1-1)
(1.))
(1-1)
w (153))
(1-1) (1-3)
max kE|d]
wk
max keld
ddtk
wdtkk
max
2d+
ke
K+ b-1
C max
max(r
(1-1) [2:]k + C), max( kE(d]
-
d+b + [2,|e + c1]
(1-1
kE [d]
max
max( kEId]
[ max (mm)]k) keld
| 02|1o0
which is desired. Proof completes.
B ADDITIONAL EXPERIMENTAL DETAILS AND HYPER-PARAMETER
Our experiments are implemented using the Pytorch framework. We run all experiments in this paper using a single NVIDIA Tesla-V100 GPU. The CUDA version is 11.2.
The learnable scalar in Equation (9) is initialized to be one and trained using smaller learning rate that is one-fifth of the base learning rate. This is mainly to make training stable as suggested in Zhang al. (2019b) since the scalar scales the whole network output. The final performance is not sensitive to the scalar learning rate as long it is set to small value. For random crop data augmentation, we use padding = 1 for MNIST and padding 3 for CIFAR-10. The model initialized using identity-man map initialization (see Section 5.3 in Zhang et al. (2021)), and mean-shift batch normalization is used for all intermediate layers. The training procedure is as follows:
In the first e1 epochs, we set p in ep-relaxation and use X = Xg as the mixing coeffi cient;
In the next e2 epochs, p exponentially increases from 8 to 1000. Accordingly, À exponen- tially decreases from Ao to a vanishing small value Aendi
In the final eg epochs, p set to infinity and set to 0.
All hyper-parameters are provided Table Most hyper-parametend are directly borrow from Zhang et al. (2021), e.g. hyper- parameters of the optimizer, the batch size, and the value p in 4p- relaxation. The only searched hyper-paran parameerrssterss are the hinge threshold and the mixing coefficient do Ann- These hyper-parameters are obtained using a course grid search.
Table 3: parametrsssssrss used in this paper.
Dataset
MNIST
CIFAR-10
0.1
0.3
2/255
8/255
16/255
Optimizer
Adam 31
0.9, B2
0.99,
10 TD)
Learning rate
0.03
Batch size
512
Psunt
8
Pend
1000
Epochs
25,
375, 50
= 100, e2 = 1150, c3 50
Total Epochs
450
1300
Hinge threshold
0.6
20/255
48/255
80/255
Mixing coefficient Ao
0.05
0.05
0.05
0.1
0.1
Mixing coefficient Xend
2 x 10
2 x 10-4
2 x 10
5 x 10-4 x 10-4
We also run additional experiments using the training strategy in Zhang et al. (2021) for performance
comparison when the original paper does not present the corresponding results. This mainly includes the case 0.1 MNIST and 2/255, use the same hyper-paramette in Zhang et al. (2021), except for the hinge threshold e where we perform careful grid search. The choice of 0 is listed in Table 4.
/55 on CIFAR-10, as shown in Table 2. We
18

---

Published as a conference paper at ICLR 2022
Table Best hinge thresholds for different settings using the training strategy in Zhang al. (2021).
Dataset
MNIST
CIFAR- 10
0.1
0.3
2/255
8/255
16/255 128/255
Hinge threshold 0
0.8
0.9
32/255
80/255
200
Zhang et al. (2021)
175
This
150
Lipschitz
Loss
Average
Max
Zhang et al. (2021)
123.5
168.4
100
This paper
121.5
183,4
75
50
quannil
Figure 3: Approximating the Lipschitz constant of b, -dddstannce net when p 8, trained using differ- ent loss functions on CIFAR-10 dataset. The left figure plots the calculated value of (21) over the test each quantile. The right table provides the statistical information.
C THE LIPSCHITZ CONSTANT OF 4D-DISTANCE NET
We have shown in Section 4.1 that an L layer lp fddisttneee net with d neurons in each hidden layer is d4/p Lipschitz with respect to -nom.. The value becomes quite large if p is small. For example, Zhang et al. (2021) uses a 6-layer dp-dist net with d = 5120. This gives a Lipschitz constant of approximate 568 when p at the beginning of training.
One may ask whether such upper bound of Lipschitz constant (Proposition 4.1) is tight and reflects the true Lipschitz property in practice. To validate the tightness of the bound, run the following experiments. Consider the lo -distance net used in Zhang et al. (2021). We train this architecture following the training strategy either in Zhang et al. (2021) or this paper. After training finishes, we then set p = 8 without changing the model parameters. We approximate the Lipschitz constant of the model using Projected Gradient Descent (PGD), which provides a lower bound estimate. In detail, for each image x: in the test dataset, we estimate the quantity
1 max [[ + 8) g(x))l/o |
(21)
where g is the network and is small constant taken be 1/255. The expression (21) clearly lower bound of the Lipschitz constant (can be seen as the "local Lipschitz constant" near point æ)). can be further lower bounded by using the PGD solution = ÔPAN. We run PGD for each target label j and optimize
1 max [[g(x: 8)1, [g(m]]
(22)
6 [|
using 20 PGD steps with step size c/4.
Results are shown in Figure 3. It can be observed that the "local Lipschitz constant" around real data points is indeed far larger than one. The average value exceeds 100 which close to the theoretical upper bound.
D RANDOMIZED SMOOTHING FOR loo PERTURBATIONS
Randomized smoothing approaches typically provide probabilistic certified guarantees for l per- turbations. To apply these methods in the lo perturbation scenario, most of works convert the result of & perturbation into fxx perturbation using norm inequalities (Salman al., 2019a; Blum et al., 2020). Specifically, to certify the robustness under e-bounded foo perturbations, one can certify the robustness under (ev d)- bouunded l perturbations to obtain a lower bound estimate where the input dimension. On CIFAR- 10 dataset, the input dimension d 3072. This corresponds to l2 perturbation radius e = 0.4347 for &x perturbation radius e = 2/255, and corresponds to an & perturbation radius 1.739 for lo perturbation radius 8/255.
19

---

Published as a conference paper at ICLR 2022
For the case 2/255. Blum et al. (2020) directly reported certified aceuracy of 62.6% using randomized smoothing which currently state-of-the-an For the case é = 8 8/255, there are no literature results that directly report ( robustness, representative papers (Salman et al., 2019a; Jeong & Shin, 2020). Salman et al. (2019a) reported a certified accuracy of 24% and clean accuracy of 53% under & perturbation = 1.75 (Table 17 in their paper). Jeong & Shin (2020) reported a certified accuracy of 25.2% and a clean accuracy of 52.3% under l2 perturbation e 1.75 (Table I in their paper, o 0.5). For the case 16/2655 all randomized smoothing methods fail and only achieve a trivial certified accuracy of 10%.
the results of &g robustness from
E ABLATION STUDIES
In this section we conduct ablation experiments to the proposed loss. Let a training sample be (ær, y) where y is the label of æ, and denote g(x) as the output of an distancce net for input æ. Let niine 3/ = max mmax 2, - 2y + 1, 1,00 and (cE(2.y) ( exp(z;)) - Ey represent the hinge loss and cross-entropy loss, respectively. We would like to justify that (i) Cross-entropy loss can alleviate the optimization issue in en-relaxation (which is a better substitute over hinge loss), but the threshold of hinge loss is also crucial as it explicitly optimizes the certified accuracy, (ii) Combining cross- cross-entropy loss and clipped hinge loss leads to a much better performance; (ii) Using decaying mixing coefficient À can further boost the performance and stabilize the training.
We consider the following objective functions:
(1) The baseline hinge loss: Eninge (g(x)/0,,) with hinge threshold 0. This loss used in Zhang et al. (2021).
(2) The cross-entropy loss: (CE(s g(z), y) where is a scalar (temperature). Note that the information of the allowed perturbation radius is not encoded in the loss, and the loss only coarsely enlarges the output margin (see Section 4.2). Therefore it may not achieve desired certified robustness.
(3) A variant of cross-entropy loss with threshold: (cg(s: g(x 01y), v) where is scalar (temperature), 0 is the threshold hyper- and 1, is the one-hot vector with the yth element being one. Intuitively speaking, subtract the yth output logit by 9 before taking cross-entropy loss. Compared to the above loss (2), now the information is encoded in the threshold hyper-parameter 8. We point out that this loss be seen as smooth approximation of the hinge loss.
(4) The combination of cross-entropy loss and clipped hinge loss: Alcu(s g(x), + min (fning y). 1) with a fixed mixing coefficient X.
(5) The combination of cross-entropy loss and clipped hinge loss: Méca(s g(x), v) + min mfinnnnngg (gxx) y). 1) with decaying X. The loss is used in this paper.
We keep the training procedure the same for the different objective functions above. The hyper- parameters such as and A are independently tuned for each objective function to achieve the best certified accuracy. The scalar is learnable parameter in each loss except for objective function (2) where we tune the value of s. For other hyper-paramen parameters, we use the values Table 3. We independently run 5 experiments for each setting and the median of the performance is reported. Results are listed in Table 5, and the bracket in Table 5(b) shows the standard deviation over runs.
Table 5: Performance of ablation studies = 8/255 CIFAR-10).
(a) Performance of different objective functions with hest hyper- parameearametes.
(b) Performance using objective function (4)
with differrnn mixing coefficient X.
Loss
Clean
Certified
Hyper-paramett parameters
A
Clean
Certified
(1)
56.30
33.30
50/255
0.1
58.99(+0.35)
37.67(#0.25)
(2)
55.58
33.23
8 1.0
0.05
56.50(+0.25)
38.82(#0.14)
(3)
53.37
34.91
= 32/255
0.02
53.51(+0.40)
39.24(=0.37)
(4)
53,51
39.24
0 = 48/255, À 0.02
0.01
50.48(+1.83)
38.05(+1.31)
(5)
54.30
40.06
0 48/255, X = 0.1 +
0.005
47.51(#5.03)
37.03(#2.64)
0
10.0
10.0
20

---

Published as a conference paper at ICLR 2022
We can draw the following conclusions from Table 5:
Hinge loss and cross-entropy loss are complementary. Cross-entropy is better in the early training phase when the Lipschitz constant large, while hinge loss is better for certified robustness when the model is almost 1-Lipschitz in the later training phase. This can be seen from the results of objective functions (1-3) in Table 5(a), where (3) incorporates cross-entropy loss and the threshold in hinge loss, and outperforms both (1) and (2) by comparable margin.
Combining cross-entropy loss and clipped hinge loss leads to much better performance. This can be seen from the result of the objective function (4), which significantly outper- forms (1-3). However, this loss is very sensitive to the syper-parameee in Table 5(b). If À is too large, the certified accuracy gets worse. If À is too small, the train- ing becomes unstable and the clean accuracy drops significantly. In the extreme case when A = 0, the loss (4) reduces to the clipped hinge loss and the optimization fails because clipped hinge loss does not optimize for wrongly-classifie samples.
as is demonstrated
Using decaying mixing coefficient À can further boost the performance and stabilize the training. In contrast to the loss (4), we will show in Appendix F that the proposed objective function (5) in this paper is not sensitive to hyper-parameter
F SENSITIVITY ANALYSIS
In this section we provide sensitive analysis of the proposed objective function (9) with respect to hyper-parameters. We consider the setting 8/255 on CIFAR-10 dataset. For each choice of hyper-parameters, we independently run experiments and the median of the certified accuracy is reported.
The hinge threshold 0. The results are already plotted in Figure 2(b). We list the concrete numbers below.
Table 6: Sensitive Analysis over pappe--rrraeter
3e
4e
6e
7e
9c
10c
Certified
35.23
38.47
39.55
40.06
39.46
39.05
38.68
38.31
The mixing coefficients Xo and Xend- The results are already shown in Figure 2(c).
The number of epochs. Our best result reported in Table 2 is trained for 1300 epochs, which is longer than Zhang et al. (2021). We also consider using the same training budget by setting el 100, e2 650, e3 50 in Table 3. This yields total of 800 training epochs. In this way we can achieve 54.52 clean accuracy and 39.61 certified accuracy.
Adam hyper-parameters. While we use the same Adam typer-parameee note that the values are different from the default numbers in Pytorch (e.g. 82 = 0.999 and e 10 10-8), *). Instead, we use 32 = 0.99 and e 10-10 in all experiments.
Zhang et al. (2021),
For we find the value is essential to be small, because for the fy-distance function, the gradients of most of the elements are close zero when p large. For Adam optimizer (Kingma & Ba, 2015), the update is written as
M
W++1 wc lr
(23)
V + +
Then large e will dominate the denominator in Adam if i is close zero, which severely weakens the parameters' update and leads to worse performance. We find the value of e is not sensitive if it small enough, i.e. we can obtain almost identical performance for e = 10-10 10-11 or 10-12
The use of smaller B2 is mainly because of the fp relaxation. Since p increases exponentially during training, the network function changes through time, therefore the long-time-ago historical gradient information will become meaningless and even do harm to the training. This is why smaller B₂ is used, so that the -econd-order momentum (the term 22) in Adam only depends on recent gradient information. We find it is also OK to choice 82 =0.98 or 0.995, and the certified accuracy can reach 39.5%. However, the default value of 0.999 is too large, as it corresponds to 10 times more historical information than the value of 0.99.
21


Reviews:
[{"review_id": "sGe8Ia8gFp7", "reviewer": "Reviewer_TteL", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strength:\n1. It is very impressive to achieve 40% certified accuracy for 8/255 attack. The result significantly close the gap between the state-of-the-art of empirical robustness (~53% by TRADES) and that of certified robustness.\n2. The paper has a thorough analysis for the training problem in Zhang et al. (2021), and proposes a new method to resolve the issue.\n3. The theoretical analysis of expressive power of l_infty distance net is interesting, though it is a little out of the selling point of this paper.\n\nWeakness:\n1. The 2/255 experiment in Table 2 does not compare with randomized smoothing. Randomized smoothing is able to achieve 62.6% certified robustness for 2/255 radius (see Table 1 in [1]), which outperforms the proposed method by ~8%.\n[1] https://arxiv.org/pdf/2002.03517.pdf\n\nQuestions:\n1. Is there a particular reason that in Table 2, the 2/255, 8/255 and 16/255 experiments use different l_infty distance nets (they have different clean accuracy)?\n\n2. We know that adversarial training helps in randomized smoothing (see [2]). Does adversarial training helps in improving the certified robustness of l_infty distance net?\n[2] https://arxiv.org/pdf/1906.04584.pdf", "summary_of_the_paper": "This paper is a follow-up paper of Zhang et al. (2021). In Zhang et al. (2021), the authors proposed a new network architecture, l_infty distance net. By construction, the network is 1-Lipschitz w.r.t. l_infty distance. However, the training procedure therein is problematic. This paper resolves the issue by a new loss design of scaled cross entropy loss + clipped hinge loss. Without using MLP on top of the l_infty distance net backbone, the proposed new training method outperforms the original one in Zhang et al. (2021) and improves over the state-of-the-art by more than 5% for 8/255 and other radiuses. Theoretically, the paper shows the expressive power of l_infty distance net for well-separated data.", "summary_of_the_review": "Overall, I like the paper (in particular, the design of l_infty distance net, which is not the focus of this paper but of Zhang et al. (2021)). The design goes towards solving the robustness issue by new network design, rather than regarding the neural network as a black-box. The experiment result on 8/255 is promising and exciting.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "J37eJtXZUgg", "reviewer": "Reviewer_THnD", "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": "The paper is well-written and the improvement on empirical result is impressive. \nMy main concern is on the experiments. \n* The paper proposed multiple modifications on the loss function, including the scale factor on cross-entropy, clipped hinge loss and weight coefficient. The authors should provide comprehensive ablation study on the several modifications.\n* I recommend the authors to include sensitive analysis for the hyper-parameter $\\lambda$ and hinge threshold $\\theta$, which are important if we want to apply this method to different models.\n* For reproducibility, since the code is not provided, I recommend the author to provide a detailed instruction on how to reproduce the paper based on https://github.com/zbh2047/L_inf-dist-net.\n* After checking the hyper parameters, I found that the authors have tuned the beta_2 and eps of Adam optimizer. Is there any explanation for this tuning?\n", "summary_of_the_paper": "The paper proposed a new loss to improve the performance of Linf distance network a new network for Linf robustness and achieved impressive empirical results.", "summary_of_the_review": "The paper is well-written and the proposed method has an impressive empirical performance. My concern is mainly on the experiments and reproducibility.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "EYMQpCQSjaZ", "reviewer": "Reviewer_d51P", "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": "Major comments:\n- The main focus of the paper is on the training of $\\ell_\\infty$ net. The authors emphasize that the original training is hindered by the  $\\ell_p$ relaxation, and they use clipped hinge loss to relieve the issue. The authors also implemented scaled cross-entropy loss. From my point of view, the authors do not explain intuitions very well. Why clipped hinge loss can maintain the Lipschitz property of $\\ell_\\infty$ even when $\\ell_p$ relaxation is used? How should we decompose the effect of scaled cross-entropy and clipped hinge loss?\n- The empirical results of this paper seem pretty decent to me. The certified accuracy is able to beat IBP. I wonder how it compares to randomized smoothing?\n\nMinor comments:\n- When you search on the hyper-parameters, is any cross-validation performed?\n- How do you explain the generalization gap between the certified train and certified test? It seems larger than the previous training scheme.\n- How large is $\\theta$ in Figure 1(a) and 2(a)?", "summary_of_the_paper": "This paper proposed a simple modification of $\\ell_\\infty$ net training, which boosts the accuracy for certified robustness under $\\ell_\\infty$ attack. It provides a trainable scale on the output of the network and uses a clipped hinge loss. The paper also proves the expressive ability of $\\ell_\\infty$ nets for classification problems.", "summary_of_the_review": "My current assessment of this paper is slightly below the acceptance threshold because I think the intuitions are not well explained and there are questions that I think the authors should explain to readers. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "7r6mKxKpT-v", "reviewer": "Reviewer_WMpC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengthens:\n1. The paper overall is easy to read and follow.\n2. The authors study an important problem of improving the robustness of deep network from the perspective of reegurozation. \n\n\nWeakness:\n1. Moderate novelty. This paper follows a similar setting with prior work (Zhang et al. 2021) published in ICML 2021, specially targeted in $l_\\infty$ distance net for improving certified accuracy. The proposed method serves as a regularization term for the hinge loss to train a more robust network. Apart from that, this work has moderate novelty which shows a large portion of prior work with the same setting and experiment design. \n\n2. Limited experimental design. To the best of my knowledge, this work shares the same setup with prior work where experiments are not extensive enough. For example, the empirical study is limited to improving the robustness in small datasets such as MNIST. What about other bigger datasets? And also, is this proposed method applicable to other machine learning tasks other than the listed task in the paper?", "summary_of_the_paper": "The authors study to improve the certified robustness of $l_\\infty$ distance nets by introducing a regularization term to train the network. Guided by the fundamental assumption of \"existing a two-layer $l_\\infty$ net which has 100% robust accuracy\", this method shows better performance over other baselines.", "summary_of_the_review": "This paper is largely based on prior work (Zhang et al. (2021))  which follows the same setting and experimental design. The authors propose to prove the effectiveness of $l_\\infty$-distance net where they come up with a regularized hinge loss to learn robust classifiers guided by their proposed Theorem 3.2.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a follow-up paper of Zhang et al. (2021), that proposed a new network architecture for adversarial robustness, l_\infty distance net. Although the l_\infty network is provably 1-Lipschitz w.r.t. the l_\infty distance, its training procedure exploits the l_p relaxation to overcome the non-smoothness of the model but suffers from an unexpected large Lipschitz constant at the early training stage, an issue to be solved. This paper resolves this issue by a new loss design of scaled cross entropy loss and clipped hinge loss. Without using MLP on top of the l_\infty distance net backbone, the proposed new training method empirically outperforms the original one in Zhang et al. (2021) and improves over the state-of-the-art by more than 5% for 8/255 and other radiuses. Moreover, the paper shows the theoretical expressive power of l_\infty distance net for well-separated data.

There are some concerns about the moderate novelty and reproducibility of the results. Since the empirical results are indeed impressive, the paper could be accepted conditional on that the authors release their reproducible codes to the public.
Decision: Accept (Poster)