Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100
Authors: Sahil Singla
Surbhi Singla
Soheil Feizi
Venue: ICLR 2022 Spotlight (2022)
Keywords: provable robustness
adversarial examples

Abstract: Training convolutional neural networks (CNNs) with a strict Lipschitz constraint under the $l_{2}$ norm is useful for provable adversarial robustness, interpretable gradients and stable training. While $1$-Lipschitz CNNs can be designed by enforcing a $1$-Lipschitz constraint on each layer, training such networks requires each layer to have an orthogonal Jacobian matrix (for all inputs) to prevent the gradients from vanishing during backpropagation. A layer with this property is said to be Gradient Norm Preserving (GNP). In this work, we introduce a procedure to certify the robustness of $1$-Lipschitz CNNs by relaxing the orthogonalization of the last linear layer of the network that significantly advances the state of the art for both standard and provable robust accuracies on CIFAR-100 (gains of $4.80\%$ and $4.71\%$, respectively). We further boost their robustness by introducing (i) a novel Gradient Norm preserving activation function called the Householder activation function (that includes every $\mathrm{GroupSort}$ activation) and (ii) a certificate regularization. On CIFAR-10, we achieve significant improvements over prior works in provable robust accuracy ($5.81\%$) with only a minor drop in standard accuracy ($-0.29\%$). Code for reproducing all experiments in the paper is available at \url{https://github.com/singlasahil14/SOC}. 

Published as a conference paper at ICLR 2022
IMPROVED DETERMINISTIC l2 ROBUSTNESS ON CIFAR- 10 AND CIFAR-100
Sahil Singla', Surbhi Singla', Soheil Soheil Feizi!
University of Maryland, College Park (ssingla, sfeizi) @umd. edu', surbhisinglal 9950 com?
ABSTRACT
Training convolutional neural networks (CNNs) with strict Lipschitz constraint under the 22 norm useful for provable adversarial robustness, interpretable gradi- ents and stable training. While 1-Lipschitz CNNs can be designed by enforcing a I-Lipschitz constraint on each layer, training such networks requires each layer have orthogonal Jacobian matrix (for all inputs) prevent the gradients from vanishing during backpropagation. A layer with this property is said to be Gradient Norm Preserving (GNP). In this work, we introduce procedure certify the robustness of 1-1 1-L-iscchizz CNNs by relaxing the orthogonalization the last linear layer of the network that significantly advances the state of the art for both standard and provable robust accuracies on CIFAR-100 (gains of 4.80% and 4.71%, respectively). We further boost their robustness by introducing (i) a novel Gradient Norm preserving activation function called the Householder acti- vation function (that includes every GroupSort activation) and (ii) a certificate regularization. On 100 we achieve significant improvements over prior works in provable robust accuracy (5.81%) with only minor drop standard accuracy (-0.29%) Code for reproducing all experiments in the paper is available at /attps://gitee com/ himmm/aiiaaaai1//c
INTRODUCTION
Given a neural network f Rd - IRt the Lipschitz constan Lip(f) enforces an upper bound on how much the output allowed change in proportion change in the input. Previous work has demonstrated that a small Lipschitz constant useful for improved adversarial robustness (Szegedy
al. 2014 Cissé al. 2017), generalization bounds (Bartlett et al. [2177] Long & Sedghi 2020).
interpretable gradients TTipras et al. 2018) and Wasserstein distance estimation (Villani 2008
Lip(f) also upper bounds the increase in the norm of gradient during backpropagation and can thus prevent gradient explosion during training, enabling us to train very deep networks (Xiao et al. 2018) 8).
While heuristic methods to enforce Lipschitz constraints (Miyato et al. 2018,, Gulrajani et al. 2017)
have achieved much practical success, they do not provably enforce bound on Lip(J") globally and it remains challenging to achieve similar results when Lip(f) provably bounded.
Using the property: Lip(g h) < Lip(g) Lip(h), the Lipschitz constant of the neural network can be bounded by the product of the Lipschitz constant of all layers. While this allows us to construct 1- 1-Lipschitz neural networks by constraining each layer to be 1-Lipschitz, Anil et al. (2018) identified a key difficulty with this approach. Because a 1-Lipschitz layer can only reduce the norm of gradient during backpropagation, backprop through each layer reduces the gradient norm, resulting in small gradient values for layers closer to the input, making training slow and difficult. To address this problem, they introduce Gradient Norm Preserving (GNP) architectures where each layer preserves the gradient norm during backpropagation. This involves constraining the Jacobian of each linear layer to be an orthogonal matrix and using GNP activation function called GroupSort. GroupSort activation function (Anil et al. (018)) first separates the vector of preactivations E IR into groups of pre-specified sizes, sorts each group in the descending order and then concatenates these sorted groups. When the group size is 2, the resulting activation function is called MaxMin.
Unless specified, we assume the Lipschitz constant under the la norm in this work.

---

Published as a conference paper at ICLR 2022
For 1-Lipschitz CNNs, the robustness certificate for a sample from class 1 is computed as M, /22 where My(x) ()) = fi(x) - max441 (x).. Naturally, larger values of fi(x) and smaller values of max441 (x) will lead to larger certificates. This requires the last weight matrix in the network, denoted by W E Rkxm (k is the number of classes, m is the dimension of the penultimate layer, m > k), to enforce the following constraints throughout training:
Vj. W 3.2112 1, i + W W
where W.. denotes the tt row of W. Now suppose that for some input image with label 7, we want to update W to increase the logit for the t class. Since Wi,,lla is constrained to be 1, the logit can only be increased by changing the direction of the vector W..- Because the other rows { W.... i i I constrained to be orthogonal to W t.:. this further requires an update for all the rows of W. Thus during training, any update made to learn some class must necessitate the forgetting of information relevant for the other classes. This can be particularly problematic when the number of classes k and thus the number of orthogonality constraints per row (i.e., k 1) is large (such as in CIFAR-100).
To address this limitation, we propose to keep the last weight layer of the network unchanged. But then the resulting function is no longer 1-LLischitz and the certificate (x)x) /2 is not valid. Thus, we introduce new certification procedure that does not require the last weight layer of the network W to be orthogonal. Our certificate is then given by the following equation:
fI(x) fx(x)
min
Wt.- W.
However, limitation of using the above certificate is that because the weight layers are completely unconstrained, larger norms of rows (i.e., |W (::l) can result in larger values of [|W,: WW,:lla and thus smaller certificate values. To address this limitation, we normalize all rows to be of unit norm before computing the logits. While this still requires all the rows to be of unit norm, their directions now allowed change freely thus preventing the need update other rows and forgetting of learned information. We show that this provides significant improvements when the number of classes large. We call this procedure Last Layer Normalization (abbreviated as LLN). On CIFAR-100, this significantly improves both the standard (>> 3%) and provable robust accuracy (> 4% at p 36/255) across multiple 1-Lipschitz CNN architectures (Table T.. Here, p is the /2 attack radius.
Another limitation of existing 1- 1-Lipschitz CNNs (Li et al. 2019b Trockman & Kolter 2021 Singla la Feizi 202T) is that their robustness guarantees do not scale properly with the 1/ radius p. For example, the provable robust accuracy of (Singla & Feizi 2021 drops 30% at p 108 108/255 /55 compared to 36/25/ on CIFAR-10 (Table 2p. To address this limitation, we introduce a certificate regularization denoted by CR (Section 5) that when used along with the Householder activation results in significantly improved provable robust accuracy at larger radius values with minimal loss in standard accuracy. On the CIFAR- 10 dataset, we achieve significant improvements in the provable robust accuracy for large p 108/ /55 (min gain of +4.96%) across different architectures with minimal loss in the standard accuracy (max drop of -0.56%). Results are in Table 2
Additionally, we characterize the MaxMin activation function as a special case of the more general Householder (HH) activations. Recall that given z IR" the HH transformation is linear function reflecting 2 about the hyperplane v x = 0 ([|v]|2 = 1), given by (I 2vv")p j where I - 2vv is orthogonal because |||12 = The Householder activation function ov is defined below:
oz(z)= 2 (I-2vV )z,
V 2 0, v 2 < 0.
First, note that since z = (I- 22v along vTa = 0, ov continuous. Moreover, the Jacobian Vz av is either I or I 2 (both orthogonal) implying ov is GNP. Since these properties hold V v ||v|| = 1, v can be learned during the training. In fact, we prove that any GNP piecewise linear function that changes from Q to Q2z (Q1, Q2 are square orthogonal matrices) along v" 2 0 must satisfy Q2 = Q1 (I- 2vv") to be continuous (Theorem I). Thus, this characterization proves that every GroupSort activation is special case of the more general Householder activation function (example in Figure [ discussion in Section 6).
In summary, in this paper, we make the following contributions:
2

---

Published as a conference paper at ICLR 2022
We introduce certification procedure without orthogonalizing the last linear layer called Last Layer Normalization. This procedure significantly enhances the standard and provable robust accuracy when the number of classes is large. Using the LipConvnet-15 network on CIFAR-100, our modification achieves a gain of +4.71 % in provable robust accuracy (at 36/255) with a gain of +4.80% in standard accuracy (Table(T).
We introduce Certificate Regularizer that significantly advances the provable robust accuracy with small reduction in standard accuracy. Using LipConvnet-15 network on CIFAR-IO, we achieve +5.81% improvement in provable robust accuracy (at p 108/253) (28)) with only a - -0.29% drop in standard accuracy over the existing methods (Table
We introduce class of piecewise linear GNP activation functions called Householder or HH activations. We show that the MaxMin activation is a special case of the HH activation for certain settings. We prove that Householder transformations are necessary for any GNP piecewise linear function to be continuous (Theorem)
2 RELATED WORK
Provably Lipschitz convolutional neural networks: The class of fully connected neural networks (FCNs) which are Gradient Norm Preserving (GNP) and I-Lipschitz were first introduced by Anil al. 2018). They orthogonalize weight matrices and use GroupSort as the activation function to design each layer to be GNP. While there have been numerous works on enforcing Lipschitz constraints on convolution layers (Cissé et al., 2017: Tsuzuku et al. 2018 Qian & Wegman 2019 Gouk et al. 2020 (edghi et al., 2019). they either enforce loose Lipschitz bounds or are not scalable to large networks. To ensure that the Lipschitz constraint on convolutional layers is tight, multiple recent works try to construct convolution layers with orthogonal Jacobian matrix (Li et al. 2019b Trockman & Kolter, [02T Singla & Feizi 202T). These approaches avoid the aforementioned issues and allow the training of large, provably L-Lipschitz CNNs while achieving impressive results.
Provable defenses against adversarial examples: A provably robust classifier is one for which guarantee that the classifier's prediction remains constant within some region around the input. Most of the existing methods for provable robustness either bound the Lipschitz constant
of the neural network or the individual layers (Weng al., 2018 Zhang et al., 2019: 2018 Wong
iet al. 2018 Wong & Kolter [018 Raghunathan et al. 20188 Croce et al. [0199] Singh et al. 2018
Singla & Feizi 2020 Zhang et 1021|20222 Wang al. 2021 Huang al.)
[0021) However,
these methods do not scale to large and practical networks on the ImageNet dataset (Deng et al.
2009).
To scale to such large networks, randomized smoothing (Liu et al. 2018: Cao & Gong
2017 Lécuyer et al. 2018 Li et al., 2019a, Cohen et al., 2019 Salman et al.) 2019 Levine et al.
2019
Kumar et al.] 2020a b) has been proposed as a probabilistically certified defense. However,
certifying robustness with high probability requires generating large number of noisy samples leading to high inference- computation. In contrast, the defense we propose is deterministic and hence not comparable to randomized smoothing. While|Leving & Feizi (02II) provide deterministic robustness certificates using randomized smoothing, their certificates are in the l norm and not directly applicable for the la threat model studied in this work. We discuss the differences between 1
and la certificates in Appendix Section C
PROBLEM SETUP AND NOTATION
For vector v, Vj denotes its jth element. For a matrix A, Aj. and A, denote the jth row and ttth column respectively. Both Aj. and A., are assumed to be column vectors (thus Aj. is the transpose of jth row of A). A,, denotes the element in jth row and htth column of A. A.j.: denotes the matrix containing the first j rows and & columns of A. The same rules are directly extended higher order tensors. I denotes the identity matrix, IR to denote the field of real numbers. For 0 E R, J and J (f) denote the orthogonal matrices with determinants +1 and 1 defined as follows:
cos 0
sin 0
cos 0
sin
(0)
J (0) sin 0
sin 0
cos 0
cos
We construct a 1-Lipschitz neural network, f Rd + R (d is the input dimension, k is the number of classes) by composing 1-Lipschitz convolution layers and GNP activation functions.
3

---

Published as a conference paper at ICLR 2022
To certify robustness for some imput with prediction I, we first define the margin of prediction: M = max (0, fi(x) - g fx))) where f((x) is the logit for class i and is the correct label. Using Theorem 7 in Li et al. 2019b), can derive the robustmess certificate (in the l2 norm) as (x)/2v2 Thus, the lg distance of x to the decision boundary is lower bounded by M (x)/v2
Mx
min min *F1 f((x)=f((x"*
||x*
x||2
33)
V2
We often use the abbreviation St - ʃ3 IR_ R denote the function so that:
(Js - (1) (x) = -
v RDD
Our goal is to train the neural network f to achieve the maximum possible provably robust accuracy
while also simultaneously improving (or maintaining) standard accuracy.
LAST LAYER NORMALIZATION
To ensure that the network is 1-Lipschitz so that the certificate in equation is valid, existing 1-Lipschitz neural networks require the weight matrices of all the linear layers of the network to be orthogonal. For the weight matrix in the last layer of the network (that maps the penultimate layer neurons to the logits), W E R&xm (k is the number of classes, m is the dimension of the penultimate layer, m k), this enforces the following constraints on each row W., R
(4) Now suppose that for some input x with label I. we want to update W to increase the logit for the tth class. Since || Wi.:ll2 is constrained be 1, the gradient update can only change the direction of the vector Wt.. But now, because the other rows [Wi., * 1) are constrained to be orthogonal to Wi.: this further requires an update for all the rows of W. This has the negative effect that during training, any update made to learn some class must necessitate the forgetting of information relevant for the other classes. This can be particularly problematic when the number of classes &s is large (such as in CIFAR-100) and thus the number of orthogonality constraints per row i.c. k - 1 is large.
Vj, [ jull2 1,
Vi j. W j:: W.:
To address this limitation, first observe that the neural network from the input layer to the penultimate layer (i.e excluding the last linear layer) is 1-Lipschitz. Let 9 R + R. be this function so that f() = W (xx + b. This equation suggests that even W is not orthogonal, the Lipschitz constant of the function fi fi, can be computed by multiplying the Lipschitz constant of y (which is 1) and that of (Wi.- W..) (which WW:- (2). The robustness certificate can then be computed as M2(()) [ W..:l2. 122- This procedure leads the following proposition:
Proposition 1. Given L-Lipschitz continuous function g IRd + R" and W E Rxmm b E IR* (k the number of classes), construct new function f -d > RR defined as: f(x) = Wg(x) + b.
Let f((x)) > max;31 fx( The robustness certificate (under the 12 norm) is given by:
f((x) fx(x)
min Ef
min f((x fx(()))))())))))
I|x - x112 2 min
Wt.- W..
Proof Appendix Section
A.I
However, in our experiments, we found that using this procedure directly i.e without any constraint on the weight matrix W often results in large norms row vectors [W.::ll2, and thus large values of [|W, W la and smaller certificates (Thcorem [). To address this problem, normalize all rows of the matrix to be of unit norm before computing the logits so that for the input x, the logit (x(x) can be computed as follows:
(W..)* [(x) + b,
(x)
Wi.:ll2
The robustness certificate can then be computed as follows:
min (xx (x)
W js ll 95(x) (w(!) f(x) bj
where Vj. W
(w(n) L, W
(n)
While each row W s. is still constrained be of unit norm, unlike with orthogonality constraints (equation 44, their directions are allowed to change freely. This provides significant improvements when the number of classes is large. We call this procedure Last Layer Normalization (L.NN).
4

---

Published as a conference paper at ICLR 2022
%6 (4,
(2)-2a)
Gyl
2g)
cos
sin
sin
cos
sin
learnable)
learnable)
(a) Case 1: sin(0/2) cos(0/2)
(b) Case 2: sin(0/2) (0s(0/2) S
Figure Illustration the Householder activation, σø. each colored region, σg is linear. The Jacobian is I when (21 lies in the pink region (Case 1) and I 2vv" in the other region (Case 2)
where v = [sin(0/2) - ccos(0/2)]* Both these matrices are orthogonal implying og is GNP.
5 CERTIFICATE REGULARIZATION
A limitation of using cross entropy loss for training 1-Lipschitz CNNs is that it is not explicitly designed to maximize the margin My and thus, the robustness certificate. That is, once the cross entropy loss becomes small, the gradients will no longer try to further increase the margin M (x) even though the network may have the capacity to learn bigger margins.
To address this limitation, we can simply subtract the certificate (M,(x)/V3 from the usual cross entropy loss function during training. Observe that subtract the certificate because want to maximize the certificate values while minimizing the cross entropy loss. However, in our experiments we found that this regularization term excessively penalizes the network for the misclassified examples and as a result, the certificate values for the correctly classified inputs are not large. Thus, we propose to use the following regularized loss function during training:
min B(x,)~D (fa(xx, relu (M)r(O) V2
]]
(5)
In the above equation, Sa denotes the 1-Lipschitz neural network parametrized by Q, fx(x) denotes the logits for the input x, e (x)(x), 1) is the cross entropy loss for input x with label and >> is the regularization coefficient for maximizing the certificate. We have the minus sign in front of the regularization term y relu(My (x) /2) because we want maximize the certificate while minimizing the cross entropy loss. For wrongly classified inputs, , This ensures that the optimization tries to increase the certificates only for the correctly classified inputs. We call the above mentioned procedure Certificate Regularization (abbreviated as CR).
= relu(M, v2)
HOUSEHOLDER ACTIVATION FUNCTIONS
Recall that given z E RT, the Houscholder (HH) transformation reflects z about the hyperplane
v x 2vv is orthogonal because ||v||2 = 1. Now, consider the nonlinear function a, defined below:
where ||v|| = 1. The linear transformation given by the equation (I 2vv )z where
Definition 1. (Householder Activation of Order L) The activation function ov E. - Rm applied on E _ is called the m-dimensiooal Householder Activation of Order 1:
[z, (I AI-22vV]
Th z 0, T V 2 Z 5. 0.
ov(2)
Since σv is linear when vTz 0r V 0. it is also continuous in both cases. At the hyperplane separating the two cases (i.e., vTz = 0) we have: (I -I-20 1-2vv")z = 2(v 2)v = z (both linear functions equal). Thus, dy is continuous A E R Moreover, the Jacobian is either I or
5

---

Published as a conference paper at ICLR 2022
I I- 2vv" which are both square orthogonal matrices. Thus, By is also GNP and 1-Lipschitz. Since these properties hold for all v satisfying ||v/2 1, v can be made a learnable parameter.
While the above arguments suggest that HH transformations are continuous, we also prove that they are necessary. That is, we prove that if GNP piecewise linear function
sufficient to ensure such functions
Rmm - R transitions between different linear functions Q1 and Q2z (in an open set S C IR") along hyperplane v² = 0 (where l|vll2 = 1). then is continuous in if and only if Q2 = Q (I 2vv²"). This theoretical result provides a general principle for designing piecewise linear GNP activation functions. The formal result is stated in the following Theorem:
Theorem 1. Given an open set S C IR"" orthogonal square matrices Q1 + Q2. and vector v E R
(llv|12 1) such that S n { v 0} + 0, the function g defined as follows:
{
{ Qiz,
ZE S, v=z>0,
g(z)
Q2z,
2 z S, v ~
continuous S if and only if Q2 = Q1 (1- 2vv²)
Proof of Theorem is in Appendix A.2 Note that since the matrix I 2vv has determinant - the above theorem necessitates that det Q1) = det (Q2) i. the determinant of the Jacobian must change sign whenever the Jacobian of piecewise linear GNP activation function changes.
Recall that for the MaxMin activation function, MaxMin(21 22) = (2),2) if 21 > 22 and (22, 21) otherwise. Thus, the Jacobian of MaxMin for 21 22 case is I (0) while for
22 is J (T/2). Using Theorem | we can easily prove that MaxMin is special case of the more general Houscholder activation functions where the Jacobian J (T/2) is replaced with J J0)) and the conditions 21 > are replaced with 21 sin(f/2) 22 cos(8/2) (similarly for S). The construction of Householder activations in 2 dimensions, denoted by de is given in the following corollary:
Corollary 1. The function og R² + R22 defined
0
if 21 sin (0/2) cos (0/2) 0
0
1
22
og (21, 22)
cos 0
sin
0
21 22
if 21 sin (0/2) - 22 cos (0/2) <
sin 0
cos
0
continuous and is called 2D Householder Activation of Order 1.
The two demonstrated in Figure and Figure Ib respectively. Since dy is continuous, GNP and L-Lipschitz V e R, is a learnable parameter. For & = π in equation og is equivalent to MaxMin. Thus, 0g is least expressive as MaxMin.
major limitation of using ov (equation (6)) directly that it has only 2 linear regions and is thus limited in its expressive power. In contrast, MaxMin first divides the preactivation E R (assuming m is divisible by 2) into m/2 groups of size each. Since each group has linear regions, we get 2m/2 linear regions from the m/2 groups. Thus, to increase the expressive power, we similarly divide into m/2 groups of size 2 each and apply the 2-dimensional Householder activation function of Order (ar)) to each group resulting 2m/ linear regions (same as MaxMin).
To apply dg to the output of a convolution layer z E mxxXx (m is the number of channels and the spatial size), first split into tensors along the channel dimension giving the tensors: / and 7m/2....- Fach of these tensors is of size m//2 x n x n giving n²m/22 groups. We use the same 0 for each pair of channels (irrespective of spatial location) resulting in m/2 learnable parameters. We initialize each 0 = x/2 that dg is equivalent to MaxMin initialization.
EXPERIMENTS
Our goal is to evaluate the effectiveness of the three changes proposed in this work: (a) Last Layer Normalization, (b) Certificate regularization and (c) Householder activation functions. We perform experiments under the setting of provably robust image classification CIFAR-10 and CIFAR-100 datasets using the same 1-Lipschitz CNN architectures used by /inglla & Feizi (202T) (LipConvnet-5. 10, 15..... . 40) due to their superior performance over the prior works. We compare with the three

---

Published as a conference paper at ICLR 2022
orthogonal convolution layers in the literature: SOC Singla & Feizi 2021). BCOP (Li et al. 2019b
and Cayley (Trockman & Kolter 2021 using MaxMin as the activation function.
We use SOC with MaxMin the primary bascline for comparison in the maintext due to their superior performance over the prior works (BCOP, Cayley). Results using BCOP and Cayley convolutions are given in Appendix Sections H for completeness. We the same implementations for these convolution layers as given in their respective github repositories. We compare the provable robust accuracy using 3 different values of the la perturbation radius P = 36/2555, 72/255, 108/255. In both Tables | and 2 for all networks, we use SOC as the convolution layer. Using SOC, we achieve the same bound on the approximation error of an orthogonal Jacobian as achieved in Singla & Feizi (2021) i.c. 2.42 x 10-6 across all convolution layers in all networks. Thus, even for the network with 40 layers, this results in maximum Lipschitz constant of (1 2.42 x 10-6y10 = 1. 1.000097 < 1.0001. Thus, the Lipschitz constant across all our networks is bounded by 1.0001. The symbol HH (in Tables 2 is for the 2D Householder Activation of order or og (defined in equation (8).
All experiments were performed using 1 NVIDIA GeForce RTX 2080 Ti GPU, All networks were trained for 200 epochs with initial learning rate of 0.1, dropped by factor of 0.1 after 100 and 150 epochs. For Certificate Regularization (or CR), we set the parameter y 0.5.
7.1 RESULTS ON CIFAR-100
In Table 1 for each architecture, the row "SOC + MaxMin" uses the MaxMin activation, "+ LLN" adds Last Layer Normalization (uses MaxMin), "+ HH" replaces MaxMin with dg (also uses LLN) "+ CR" also adds Certificate Regularization with y 0.1 (uses both dg and LLN). The column, "Increase (Standard)" denotes the increase in standard accuracy relative to "SOC + MaxMin".
By adding LLN (the row "+ LLLN",, we observe gains in standard (min gain of 1.10%) and provable robust accuracy (min gain of 1.71% at p= 36/255) across all the LipConvnet architectures (gains relative to "SOC + MaxMin"). These gains are smallest for the LipConvnet-40 network with the maximum depth. However, replacing MaxMin with the σg activation further improves the standard (min gain of 3.65%) and provable robust accuracy (min gain of 4.46% p 36/ 36/255) across all networks (again relative to "SOC + MaxMin"). We observe that replacing MaxMin with dg significantly improves the performance of the deeper LipConvnet-35, 40 networks.
Adding CR further improves the provable robust accuracy while only slightly reducing the standard accuracy. Because L.NN significantly improves the standard accuracy, we compare the standard accuracy numbers between rows "+ CR" and "+ LLN" to evaluate the drop due to CR. We observe small drop in standard accuracy 0.00%, 0..11%) only for LipConvnet-5 and LipConvnet-15 networks. For the other networks, the standard accuracy actually increases.
7.2 RESULTS ON CIFAR-10
In Table for each architecture, the row "SOC + MaxMin" uses the MaxMin activation, the row "+ HH" uses ag activation (replacing MaxMin) and the row "+ CR" also adds Certificate Regularization with = 0.1 (again using dy as the activation). Due to the small number of classes in CIFAR-10, 10, we do not observe significant gains using Last Layer Normalization or LLN (Appendix Table (O). Thus, we do not include LLN for any of the results in Table 2 The column, "Increase (108/255) denotes the increase in provable robust accuracy with p = 108/255 255 relative to "SOC + MaxMin".
For LipConvnet-25,, 30, 35, 40 architectures, we observe gains in both the standard and provable robust accuracy by replacing MaxMin with the HH activation (i.e og). Similar what we observe for C1FAR-100) in Table [] the gains in provable robust accuracy (p = 108 108/255) are significantly higher for deeper networks: LipConvnet-35 (3.65%) and LipConvnet-40 (4.35%) with decent gains in standard accuracy (1.71 and 1.61% respectively).
Again similar to CIFAR- 100, adding CR further boosts the provable robust accuracy while slightly reducing the standard accuracy. Comparing "+ CR" with "SOC + MaxMin", we observe small drops in standard accuracy for LipConvnet-5,, 10...., 30 networks (max. drop of -0.56%), and gains for LipConvnet-35 (+0.52%) and LipConvnet-40 (+0.96%). For provable robust accuracy (p = 108 (255), we observe very significant gains of > 4.96% for all networks and > 8% for the deeper LipConveet-35, 40 networks.
7

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(Standard)
SOC + MaxMin
42.71%
27.86%
17.45%
9.99%
LLN
45.86%
31.93%
21.17%
13.21%
+3.15%
LipConvnet-5
+ НH
46.36%
32.64%
21.19%
13.12%
+3.65 %
CR
45.82%
32.99%
22.48%
14.79%
+3.11%
SOC + MaxMin
43.72%
29.39%
18.56%
11.16%
LLN
46.88%
33.32%
22.08%
13.87%
+3.16%
LipConvnet-10
НH
47.96%
34.30%
22.35%
14.48%
+4.24%
+ CR
47.07%
34.53% %
23.50%
15.66%
+3.35%
SOC + MaxMin
42.92%
28.81%
17.93%
10.73%
LLN
47.72%
33.52%
21.89%
13.76%
+4. 4.80%
LipConvnet-15
+ НH
47.72%
33.97%
22.45%
13.81%
+4.80 %
CR
47.61%
34.54%
23.16%
15.09%
+4.69%
SOC + MaxMin 43.06%
29.34%
18.66%
11.20%
+ LLN
46.86%
33.48%
22.14%
14.10%
+3.80%
LipConvnet-20
НH
47.71%
34.22%
22.93%
14.57%
+4.65%
CR
47.84%
34.77%
23.70%
15.84
+4.78%
SOC + MaxMin
43.37%
28.59%
18.18%
10.85%
LLN
46.32%
32.87%
21.53%
13.86%
+2.95%
LipConvnet-25
HH 47.70%
34.00%
22.67%
14.57%
+4.33%
CR 46.87%
34.09%
23.41
15.61
+3.50%
SOC MaxMin
42.87%
28.74%
18.47%
11.21%
LLN 46.18%
32.82%
21.52%
13.52%
+3.31%
LipConvnet-30
HH 46.80%
33.72%
22.70%
14.31%
+3.93%
CR 46.92%
34.17%
23.21 %
15.84%
+4.05 %
SOC + MaxMin
42.42%
28.34%
18.10%
10.96%
LLN 45.22%
32.10%
21.28%
13.25%
+2.80%
LipConvnet-35
HH 46.21%
32.80%
21.55%
14.13%
+3.79%
CR
46.88%
33.64%
23.34%
15.73%
+4.46%
SOC + MaxMin
41.84%
28.00%
17.40%
10.28%
LLN 42.94%
29.71%
19.30%
11.99%
+1.10%
LipConvnet-40
HH 45.84%
32.79%
21.98%
14.07%
+4.00%
CR
45.03%
32.57%
22.37%
14.76%
+3.19%
Table 1: Results for provable robustness against adversarial examples the CIFAR-100 dataset. Results with BCOP and Cayley convolutions are in Appendix Tables 13 and 14
CONCLUSION
In this work, we introduce procedure to certify robustness of 1-Lipschitz convolutional neural networks without orthogonalizing of the last linear layer of the network. Additionally, we introduce certificate regularization that significantly improves the provable robust accuracy for these models at higher l2 radii. Finally, introduce class of GNP activation functions called Householder (or HH) activations and prove that the Jacobian of any Gradient Norm Preserving (GNP) piecewise linear function is only allowed to change via Householder transformations for the function to be continuous
8

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(108/255)
SOC + MaxMin
75.78%
59.18%
42.01%
27.09%
LipConvnet-5
HH 76.30%
60.12%
43.20%
27.39%
+0.30%
CR
75.31%
60.37%
45.62% %
32.38%
+5.29%
SOC + MaxMin
76.45%
60.86%
44.15%
29.15
LipConvnet-10
HH 76.86%
61.52%
44.91%
29.90%
+0.75%
CR 76.23%
62.57%
47.70%
34.15%
+5.00%
SOC + MaxMin 76.68%
61.36%
44.28%
29.66%
LipConvnet-15
НH 77.41 %
61.92%
45.60%
31.10%
+1 1.44%
CR 76.39%
62.96%
48.47%
35.47%
+5.81%
SOC + MaxMin
76.90%
61.87%
45.79%
31.08%
LipConvnet-20
HH 76.99%
61.76%
45.59%
30.99%
-0.09%
CR 76.34%
62.63
48.69%
36.04%
+4.96%
SOC + MaxMin
75.24%
60.17%
43.55%
28.60%
LipConvnet-25
HH 76.37 %
61.50%
44.72%
29.83%
+1 1..3%
CR
75.21%
61.98%
47.93%
34.92%
+6.32%
SOC MaxMin
74.51%
59.06%
42.46%
28.05%
LipConvnet-30
HH 75.25%
59.90%
43.85%
29.35%
+ +1.30%
CR
74.23%
60.64%
46.51
34.08%
+6.03%
SOC + MaxMin
73.73%
58.50%
41.75%
27.20%
LipConvnet-35
+ НH
75.44%
61.05%
45.38%
30.85%
+3.65%
CR
74.25%
61.30%
47.60%
35.21%
+8.01% %
SOC + MaxMin
71.63%
54.39%
37.92%
24.13%
LipConvnet-40
HH 73.24%
58.12%
42.24%
28.48%
+4.35%
CR 72.59%
59.04%
44.92%
32.87% %
+8.74%
Table Results for provable robustness against adversarial examples on the CIFAR-10 dataset. Results with BCOP and Cayley convolutions are in Appendix Tables Yables[7andl and
which provides a general principle for designing piecewise linear GNP functions. These ideas lead to improved deterministic robustness certificates CIFAR-10 and CIFAR-100.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This project was supported in part by NSF CAREER AWARD 1942230, grant from NIST 60NANB20DI34, HR001 199002--ARD--F--02... 12090133, ONR YIP award N00014-22- 1-2271, Army Grant W91
REPRODUCIBILITY
The code for reproducing all experiments the paper is available at httts:://ithub..om singlasah1114/00
ETHICS STATEMENT
This paper introduces novel set of techniques for improving the provable robustness of 1-Lipschitz CNNs. We do not see any foreseeable negative consequences associated with our work.
REFERENCES
Cem Anil, James Lucas, and Roger B. Grosse. Sorting out lipschitz function approximation. In ICML, 2018.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. In Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6241-6254 USA, 2017. Curran Associates Inc. ISBN 978-1 5108-6096-4, URL http: //dp acm. wwwpooittttttoootttotoot../..ttt wtw.ccmmmm.m....... wttp:ccmmmmm2m2222.2.22 3295372
Xiaoyu Cao and Neil Zhenqiang Gong. Mitigating evasion attacks deep neural networks via region-based classification. In Proceedings of the 33rd Annual Computer Security Applications Conference, ACSAC 2017, pp. 278-287, New York, NY, USA, 2017. Association for Computing Machinery, ISBN 978 450353458, 10.1145/31 600 3134606
doi: (0.1145/3134600.313344
URL httpt:tt////// org/
Moustapha Cissé, Piotr Bojanowski, Edouard Grave, Yann N. Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, 854- 863. PMLR, 2017. URL
html
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In ICML, 2019.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. A/STATS 2019, 2019.
J. Deng, Wei Dong, R. Socher, L. Li, K. Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. Regularisation of neural networks by enforcing lipschitz continuity, 2020.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30, pp. 5767-5777. Curran Asso- ciates, Inc., 2017. URL
8 892c3b1 (cddccld23332ee7dddd
.
10

---

Published as a conference paper at ICLR 2022
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. A. Beygelzimer, Y. Dauphin, P. Liang. and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
net fort/f deninnddFFFFeT FF
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5177. Curran Asso- ciates, Inc., 2020a. URL httpss: ngs n neur pdf
ps cc/ wwtppppper//2///11.....
9d43 10w311112772220002222212
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensional- ity on randomized smoothing for certifiable robustness. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5458-5461 PMLR, 13-18 Jul 2020b. URL
httt:://rrocediini ngs. m w.w.spress/vi. 9/ www..aaa........mmmmmmmm
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and S. K. K. Jana. Certified robustmess to adversarial examples with differential privacy. In IEEE S&P 2019, 2018.
Alexander Levine and Soheil Feizi. Improved, deterministic smoothing for 11 certified robustness. In ICML, 2021.
Alexander Levine, Sahil Singla, and Soheil Feizi. Certifiably robust interpretation deep learning, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with ad- ditive noise. In H. Wallach, H. Larochelle, Beygelzimer, d Alche-Butt E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 9464-9474. Curran As- sociates, Inc., 2019a. URL htttttts///rrccccdingge neurips pctps//pppppep/11//111 pdf]]
335cd 135cc1b990s 0b 4ee 4aeeeeeeeebdddddeeeeeee22222---0
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger Grosse, and Jörn-Herrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. Conference on Neural Information Processing Systems, 2019b.
Xuanging Liu, Minhao Cheng, Huan Zhang, and C. Hsich. Towards robust neural networks via random self-ensemble. ECCV, 2018
Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In International Conference on Learning Representations, 2020. URL htttps::/opeereeiiieie
net/ Pett/forum?id=rle FpNFDr
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
/RL.https///ppeerrvee net/ forum? 1irrumm2iid11
Haifeng Qian and Mark N. Wegman. 1.2-nonexpansive neural networks. In International Confer- ence on Learning Representations, 2019. URL
ByxGS5R9FQ
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In NewrlPS, 2018.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché -Alché-Buc, Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32, pp. 11292-11303 Curran As- sociates, Inc., 2019. URL http:/ttttttpppceeeeiiiaea www.://ccceeiinnnnn.nnn.nr..e.ee neurips pss. cc httpssccppppper//11///////// 612226666666
3a24b25a7b09 (wwee222266611111111121
pdf
Hanie Sedghi, Vineet Gupta, and Philip M. Long. The singular values of convolutional layers. In International Conference on Learning Representations, 2019. URL /RR/Attts/:////eeeiiii net/ net:/forum:ildereevvo..

---

Published as a conference paper at ICLR 2022
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Puschel, and Martin T. Vechev. Fast and effective robustness certification. In NeurIPS, 2018.
Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8981-8991, PMLR, 13-18 Jul 2020. URL http: http:::/ppocceeddiggeo wmt.:eeeeeiinnsm........mmm..m.. mlr www.ppeesss...... setess/vi19// http///1///ingaaaaaaaaaa
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In ICMI,, 2021. URL https:
7/rxiiv.o org/ abs/ 20lps/21050 12105.1441
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014, UtLhttp:://aae org. atp//b/////33 6199
Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021. 2021. URL httpttt://pppeeee/////
net f (o jEHYv
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Tumer, and Aleksander Madry. Robustness may be at odds with accuracy. In ICLR, 2018.
Yusuke Tsuzuku, I. Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. In NeurlPS, 2018.
Cedric Villani. Optimal transport, old and new, 2008
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-CROWN: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL. RBeCFw
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 Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5276-5285, PMLR, 10-15 Jul 2018 URL htt.ttsss/pocceedinnneooooooo/ee mlr. www.ppressvvv... v80 vttp:/800//eeee /wegg 8a. htm.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th In- lernational Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 122865529, Stockholmsmässann Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:://rroceedingg mlr
html
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In NewrlPS, 2018
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and mean field theory of CNNs: How train 10,000-layer vanilla con- volutional neural networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5393-5402, Stockholmsmmssaa Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http://procedding..r mlr. wwwss http://wweecccooooooooopreeeeaaa
html
Bohang Zhang. Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying linfinity robustness using neural networks with linfinity-dist neurons. /CML, 2021.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of l-infinity distance nets. International Conference on Learning Representations, 2022. URL https net. ooo.e
//openrevies wwt.ee...eeeeeeeeeeeeeeeeeee
12

---

Published as a conference paper at ICLR 2022
Huan Zhang, Tsui- Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems (NIPS), arXiv preprint arXi::1811.00800 dec 2018.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. In AAAI Conference on Artificial Intelligence (AAAI), arXiv preprint arXiv: 1788,, dec 2019.
13

---

Published as a conference paper at ICLR 2022
A PROOFS
A.1 PROOF OF PROPOSITION
Proof. We proceed by computing the Lipschitz constant of the function fi - fi. The gradient of the function: fi - fi at x can be computed using the chain rule:
Vx - (Wi, Wa,)
Vxg
Since y is given to be 1-Lipschitz, the Lipschitz constant of fi Si can be computed using the above equation as follows:
V (fi - fi) l2 S (Wi, Ws.)" (Vxg) ll
V (fi - ft) ll WW. Wa.llal/V<glla & [W. W.
Thus, the distance of x to the decision boundary fi f. 0, is lower bounded by:
fx) fi(x)
min f=f((x))
x x||2 >
[W1, W.,
Thus, the distance to decision boundary across all classes * [ is lower bounded by:
fi(x) fx(x)
min (t
min fi(x"))(((x>)
I|x - x|12 2 min
Wt. W.
A.2 PROOF OF THEOREM II
Proof. We first prove that if Q2 (I ZvvT)Qu then the function is continuous.
First, observe that for v z > 0, gzz) = Qız which is continuous. Similarly, for v'2
g(z) Q2z which is again continuous.
This proves that the function is continuous when vTz > 0 or v < O.
Thus, prove continuity z S. we must prove that:
Q1z = = Q2z
Vz:vžz=0
Since Q2 = QI (v-2''"))), we have:
Q2 Qi = --2Q
(Q2 (====((Q:vv))) == -2Q (v²
The above equation directly proves 9
Now, we prove the other direction i.e if is continuous in S then, Q2 Qi (I-IIvv) (I-2v())
Since g is continuous for all z v² 0, we have:
Q Qız z QQ 2=
Vz ==
Vz v='z0
Since z E R we know that the set of vectors: {z v z = 0} spans m dimensional subspace. Thus, the null space of Q2 Q1 of size m - This in turn implies that Q2 Q1 is a rank one matrix given by the following equation:
Q2 Q1 uv?
(10)
where the vector u remains to be determined. Since Q and Q₂ are orthogonal matrices, we have the following set of equations:
Q Q2 (Qr + Tv (Q: + uv?))
(11)
Q (Q + uv (Q + )v
(12)
14

---

Published as a conference paper at ICLR 2022
We first simplify equation
0 Q2 = (Qf vu') (Q
I (Qv Th + (Q (u'u) w
0 v (Qf T + (Q v² (u' w - -uu"u) vV = =v + (Q u) T
Right multiplying both sides by v and using ||v||2 = 1, we get:
[u u) v Qiv) v + Q u
Qf (u u n² Q1v) v= Av
u XQ1 where À (u' u u Qiv)
(13)
Substituting u using equation 13 in equation
10 get:
Q2 -2-0. Q1 XQivv
Q2 = Qi (I+ (vv
Since Q7 Q2- = I, we have:
Q (Qr (I+ )vr")) T Qi (I+ \vr")
Q Q2 (I+ Avv") of (I+ Avv')
I AI+'" (I Avv")
I + 2\vv + X²vVT
x= 0 or X -
Since À = 0 would imply Q Q2 which is not allowed by the assumption of the Theorem that
Q + - is the only possibility allowed. This proves the other direction i.e:
Q2-
Q2 = =Q (1 (I- (1-2v"))")
A.3 PROOF OF COROLLARY
Proof. Subsitute Q1, follows in Theorem
1 0
Q
0
1
sin (0/2) cos (0/2)
Q2
2vV
sin (0/2)
Q2 0
[sin (0/2)
cos (0/2)
1
cos (0/2)
1
sin 2 (0/2)
-sin (0/2) cos (8/2)
Q2
0
1
sin (0/2) cos (0/2)
cos (0/2)
1- 2 sin (0/2)
2si (0) ()) cos (8/2)
Q2 2 sin (0/2) cos (0/2)
1 cos? (0/2)
cos(() ( (0
Q2
sin cos
Theorem then directly implies the corollary.
15

---

Published as a conference paper at ICLR 2022
A.4 PROOF OF THEOREM! 2
Theorem 2. Given; 0 S On < 0,.... < Onn = 2n + Oo such that Ei=o (02i+1 02.) = π and
a; = - 01-;(-1), The function de II22 - R² is continuous, GNP and 1-Lipschitz where j==
@ 10o, .....,, 02n-10 (also called 2D Householder Activation of order n):
00(21, 22)
COS a;
sin a;
21
0, S 4 < 0++1 (14)
(-11)' sina; (-1)it) cos aq
22
where & E [8u. B2n 2 80) and cos({p) 21 /2 + 23. sin(pp) = 22/ 22 + 2z.
Proof. We are given the following:
(02i11 - 022) = 1,
02 = Σ 01-5(-113
(15)
z=0
Note that by definition (equation continuous.
) the function is linear for 0, < p 0,41 and hence
Furthermore, since yp E 10o, Oza), we proceed to prove continuity for the following two cases:
Case 1: 0, - <<< 1 < 0, + ee,
<> 0, i 2
Case 2: Og < < 0o te,
Ozn - 6 < x Ozns e <>0
Proof for Case 1: Using equation (14). know that de realizes different linear functions for 0g 4p < 0g and 0, < & < 0 + c.
Thus, for de to be continuous, we require that the two linear functions be the same the boundary
ie 0;-
We first write the input (Z1, z2) in terms of shifted polar coordinates i.e: (r croosss), rsin(sp) where
r= V + 23 and cos = / / 2 + 22z sin yp = 22/ / + 2 x0 [0,, fo + 2T)
Thus, the function for 0, < < 0, is given by:
sin a de (r cos p, sin up) (-1) a (-1)² cos 0ii-1
cos 0
r cos gي rsin 4
(16)
Similarly, the function for 0. 4 < 0, + e is given by:
cos a
sin a₁ (-1)*th cos 0s
r yp) r
de (r cos p, sin (p)
(17)
(-1) sin aj
The difference in the function values at the boundary i.e sp 0,, obtained by subtracting equations and (66) is given as follows:
COS Og 1)¹ sin
sin a; (-1) cos aj
cosos 0:] r rsin 0:
cos a; (-1) sin 0;-1
sin a;
r cos 0g r rsin 0g
(-1)² cos a;=-
cos a; - COS a;-1
sin a; - sin
Coos 0: sin 0s
1)x sin a; (-1) 1
sin a
(-1)a+h 1+1 cos as (-1) cos a4-1
sin 0; sin a; 1)) a; + sin a1- (-1) (cos a; + cos 11-1)
cos a; cos a;-1
cos 0g sin 0g
r
Using sum-to sum-to-product trigonometric identities, the above equals:
2 sin
1-00 1
2
sin
2
+0g
sin 00
cos
a,tai
2
cos 0
=r
1)'
sin a-t0-11
COs
2( 1) i+1 cos
a1-1-00
CoS
a1-1ta
sin 0:
2r
sin
2
sin
sin
a1-1-ax
2
coS
auta.-1
2
Coos
1)² sin
CO8
2
(-1je+1 cos
01-1
-os
Oc-1 tix
sin 0,
2r
sin
Oi-
2
sin
as-1ta 2
aa-1to
}
ccos 0,
1)1s cos
Oi 04-1-a3
2
sin 0:
16

---

Published as a conference paper at ICLR 2022
Using equation [5). we directly have: a; 28, a;-1- Thus, the above equation reduces to:
sin (0: a;))
cos 0g
0.
2r
(-1)² cos (0; as))
[sin (0;) cos (0;))
sin 0g
0.
Hence, the linear functions given by equations (66) and 17 are equal at ip = 0,. This proves that the function is continuous for Case 1.
Proof for Case 2:
Using equation (14), we know that de realizes different linear functions for On < 4 < 0o and
82n - E < 82n.
Thus, for de to be continuous, require that the two linear functions be the same the boundary ie 0g.
first write the input (21, 22) in terms of shifted polar coordinates i.e: (r cos(),, si))
As before,
Thus, the function for 0o up Oo + is given by:
[oos ag
sin ao cos Crj
r cos yp) r
de (r cos pp, pp, rin up) sin Crg
(18)
Similarly, the function for 02n - < Φ < 2nn is given by:
C08 a22--1
sill 022--
c p rsin
de cos sp, rin up) = (-1) sin 022-1
(19)
(-1)at1 Co8 (22n-1
Using equation
[5 0/2n is given as follows:
2n-1
02n-1
2
Oz 02n-1-1(-1) =2 Σ
(02i41 -0z;) = 2m
x=
Thus, equation (19 reduces to:
[1 0 r cos y r sin yp
de (r cos sp, sin x)
(20)
The difference in the function values at the boundary i.e = og. obtained by subtracting equations 20 and 18) is given as follows:
1
0
cos 0o]
[oos Ogg sin op
sin Ox cos Oin
cos Bu r rsin 0o
0
1
sin 0o
1
cos aro
sin oo + cos or)
coos 0g sin 0o
sin Opp
Using the trigonometric identities: cos
2 sin (0/2(,
cos(f) 2 (002( and
sin(0) (0 cos(0/2), we have:
2 sin 2 00
-2 sinn Go
cos Co
cos 0o sin Og
sin
cos( no
2 cos" 2
sin(
cos 0o
2r
[sin( ma)
cos( [)
cos
sin Co
Using equation
15 we have: ag = 20g- Thus, the above equation reduces to:
sin(On) cos(
coos 0o
[o.]
2r
[sin(fo) - ccos(fo)]
sin Oo
=
0.
Hence, the linear functions given by equations 18) and 200 are equal at 0g. This proves that the function is continuous for Case 2.
17

---

Published as a conference paper at ICLR 2022
B SELECTION OF USING CROSS VALIDATION
Using 5000 held out samples from CIFAR-IO, I0, we tested different values of shown Table 3 and selected 7 0.5 because resulted in less than 0.5% decrease in standard accuracy while 4.96% increase in provably robust accuracy. We used the LipConvnet-5 network with the 20 Householder actívation function of order 2 i.e dg.
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
36/255
72/255
108/255
(108/255)
75.82%
59.66%
42.78%
26.92%
0.10
75.58%
59.74%
42.94%
28.04%
+0.94%
0.25
75.54%
60.22%
43.98%
29.50%
+2.58%
LipConvnet-5
0.50
75.30%
60.08% %
45.36%
31.88%
+4.96%
0.75
74. 14%
60.36%
46.08%
33.44%
+6.52%
1.00
73.86%
60.30%
46.80%
34.60%
+7.68%
Table Results for provable robustness against adversarial examples on the CIFAR-10 dataset for cross validation using 5000 held out samples from the training set.
C DIFFERENCES BETWEEN 4 AND l CERTIFICATE
By the equivalence of norms, we have the following result:
x XER
|x||
< |x|12 S /d|
(21)
Let us assume that we have 4 certificate for the input x so that the prediction of neural network remains constant in a region of 1 radius around the input x ie::
||x
x||1 S P1
(22)
We want compute the la certificate implied by the certificate given in equation 22) Let p2 be the 12 certificate so that:
x||2 S P2
xx - -x|1 S m
Using equation
21 we have the following set of equations:
||x
x S
P2
A -Xx x111
S p2
1x x||1 Vdp2
Using equation
22 we have the following:
P1 vdp2 P1 = P2 S
Hence, the la norm certificate induced by the norm certificate can be significantly smaller for high dimensional inputs. Using the l certificate used in Levine & Feizi 2021 i.e P 4 and d 32v3 for CIFAR-10 and CIFAR-100 100, get implied certificate of P2 4/(32/3) = 0.07225. In contrast, in this work we study la robustness for much higher certificate values i.e 36/255 0.14118.
D RESULTS USING REVISED LIPSCHITZ CONSTANTS
In Tables and 5 we show results where the Lipschitz constant was computed using product of Lipschitz constant of all layers. The Lipschitz constant of each layer was computed using direct power iteration on the linear layer (using 50 iterations) and not using the approximation bound provided in Singla & Feizi 2021
18

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(Standard)
SOC + MaxMin
42.71%
27.86%
17.45%
9.99%
+ LLN
45.86%
31.93%
21.17%
13.21%
+3.15%
LipConvnet-5
НH
46.36%
32.64%
21.19%
13.12%
+3.65% %
CR
45.82%
32.99%
22.48%
14.79%
+3.11%
SOC + MaxMin
43.72%
29.39%
18.56%
11.16%
LLN 46.88%
33.32%
22.08%
13.87%
+3.16%
LipConvnet-10
HH 47.96%
34.30%
22.35%
14.48%
+4.24%
CR
47.07%
34.53%
23.50%
15.66%
+3.35%
SOC + MaxMin
42.92%
28.81%
17.93%
10.73%
+ LLN
47.72%
33.52%
21.89%
13.76%
+4.80%
LipConvnet-15
HH 47.72%
33.97%
22.45%
13.81
+4.80%
CR
47.61%
34.54%
23.16%
15.09
+4.69%
SOC + MaxMin
43.06%
29.34%
18.66%
11.20%
LLN
46.86%
33.48%
22.14%
14.10%
+3. +3.80%
LipConvnet-20
HH 47.71%
34.22%
22.93%
14.57%
+4.65 4.65%
CR
47.84%
34.77% %
23.70%
15.83%
+4.78%
SOC + MaxMin
43.37%
28.59%
18.17%
10.85%
LLN
46.32%
32.87%
21.53%
13.86%
+2.95%
LipConvnet-25
HH 47.70%
34.00%
22.67%
14.57%
+4.33%
CR 46.87%
34.09%
23.41 %
15.61%
+3.50%
SOC + MaxMin
42.87%
28.74%
18.47%
11.20%
LLN 46.18%
32.82%
21.52%
13.52%
+3.31%
LipConvnet-30
HH 46.80%
33.72%
22.70%
14.31%
+3.93%
CR 46.92%
34.17%
23.21 %
15.84%
+4.05%
SOC + MaxMin
42.42%
28.34%
18.10%
10.96%
LLN 45.22%
32.10%
21.28%
13.25%
+2.80%
LipConvnet-35
HH 46.21%
32.80%
21.55%
14.13%
+3.79%
CR
46.88%
33.64%
23.34%
15.73%
+4.46%
SOC + MaxMin
41.84%
28.00%
17.40%
10.28%
LLN 42.94%
29.71%
19.30%
11.99%
+1.10%
LipConvnet-40
HH 45.84%
32.79%
21.98%
14.07%
+4.00%
+ CR
45.03%
32.56%
22.37 %
14.76%
+3.19%
Table 4: Results for provable robustness against adversarial examples on the C10AR-100 dataset. For all networks in this table, the maximum deviation of the Lipschitz constant from was measured to be 2.4609 x 10-5 The values shown in red were reduced by 0.01% from the corresponding values Table to the correction Lipschitz constant. All other values remained unchanged.
19

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(108/255)
SOC + MaxMin
75.78%
59.18%
42.01%
27.09%
LipConvnet-5
HH
76.30%
60.12%
43.20%
27.39%
+0.30%
+ CC
75.31% %
60.37%
45.62% %
32.38%
+5.29%
SOC + MaxMin
76.45%
60.86%
44.15%
29.15%
LipConvnet-10
HH 76.86%
61.52%
44.91%
29.90%
+0.75%
CR 76.23%
62.57%
47.70%
34.15%
+5.00
SOC + MaxMin
76.68%
61.36%
44.27%
29.66%
LipConvnet-15
HH 77.41%
61.92%
45.60%
31.10%
+ +1.44%
CR 76.39%
62.96%
48.47% %
35.47%
+5.81
SOC + MaxMin
76.90%
61.87%
45.79%
31.08%
LipConvnet-20
HH 76.99%
61.76%
45.59%
30.99%
-0.09%
CR 76.34%
62.63%
48.68%
36.04%
+4.96%
SOC + MaxMin
75.24%
60.17%
43.54%
28.60%
LipConvnet-25
HH 76.37% %
61.50%
44.72%
29.83%
+ 1 1.23%
CR
75.21%
61.98%
47.93%
34.92%
+6.32% %
SOC MaxMin
74.51%
59.06%
42.46%
28.04%
LipConvnet-30
+ HH
75.25%
59.90%
43.85%
29.35%
+ 1 1.30%
CR
74.23%
60.64%
46.51
34.08%
+6.04% %
SOC + MaxMin
73.73%
58.50%
41.75%
27.20%
LipConvnet-35
+ НH
75.44
61.05%
45.38%
30.85%
+3.65%
CR
74.25%
61.30%
47.60%
35.21% %
+8.01% %
SOC + MaxMin 71.63%
54.39%
37.92%
24.13%
LipConvnet-40
+ HH 73.24%
58.12%
42.23%
28.48%
+4.35%
CR
72.59%
59.04%
44.92%
32.87% %
+8.74%
Table Results for provable robustness against adversarial examples on the CIFAR-10 dataset. For all networks in this table, the maximum deviation of the Lipschitz constant from was measured to be 2.2072 x 10 The values shown in red were reduced by 0.01% from the corresponding values in Table 2 due to the correction in Lipschitz constant. All other values remained unchanged.
20

---

Published as a conference paper at ICLR 2022
1
00
J (
2y000
vin
Min
(2)
200000
7
2,
(1 Ag)
J ('(
2000 (0)
sin
4
-,000
1.00
00 0, 02)
(a) The output of always lies in the pink region. Applying dg this where + + 2 n further divides this region into two linear regions (light and original pink).
(b) In cach colored region, the function is lincar with the Jacobian mentioned. For the function to be continuous, must have 03 02 [0o, 01, O2. 0s) can chosen learnable parameters.
0g π. Thus, any of
Figure 2: Constructing Higher Order Householder activations (J and defined in equation
E VERIFICATION THAT 02 22) ALWAYS LIES ON ONE SIDE OF THE HYPERPLANE
Consider the case: 21 sin (0/2) 22 cos (0/2) >
In this case (21, 22) = (2) and the result follows directly.
Consider the other case: 21 sin (0/2) 22 cos (0/2)
a1
cos f
sin 0
2
21 cos 0 + 22 sin A
(2
sin 0
cos
[2
=
21 sin 0 22 cos
a1 sin (0/2) 02 cos (0/2) (z) cos 0 + 22 sin 0) sin (0/2) (z) sin 0 22 cos 0) cos (0/2)
21 (cos 0 sin (0/2) - sin 0 cos (0/2)) + (sin 0 sin (0/2) + cos O cos (0/2))
-1 sin (0/2) + 22 cos (0/2)
1
Since 21 sin (0/2) 22 cos (0/2) S 0, we have 22 sin (0/2) + 22 cos (0/2) 0.
F HIGHER ORDER HOUSEHOLDER ACTIVATION FUNCTIONS
We know that MaxMin(z1, 22) (max(21, #2). min(21, =2)) where 21, 22 E R. Because max(21, 22) > min(21, 22), applying MaxMin again gives the same result i.c M = MaxMin. Now consider the function de (discussed in the maintext, given below for convenience):
21
if 21 sin (0/2) - 22 cos (0/2) > 0
0
1
Tg (21,
22
cos 0
sin 0
Tzi]
if 21 sin (0/2) 22 cos (0/2)
sin 0
cos 0
22
From Figure 1 we observe that if (u1, u2) = (2 22), then (uy, U2) always lies on the right side of the hyperplane (pink colored region). In other words, sin (0/2) U2 cos (0/2) 0 V 21, (proof in Appendix This further implies that ag
observe that if Φ # + 2nT for some E Z, then as (u1, u2) * (u1, W2) for all (u1, u2) in the pink colored region (uy sin (0/2) U2 cos (0/2) > 0). This motivates us to construct the function ((n) IR² + g²a defined as follows:
However from Figure Za in the maintext,
different angle d where
o (n) 08 c 0g 0g 0gg
(23)
times, can be different
Clearly, (1)) has larger number of linear regions than de and thus expected have more expressive power. However, drawback of using (n) that it requires sequential application of og which can
21

---

Published as a conference paper at ICLR 2022
be expensive if the number of iterations is large. To address this limitation, first observe that dg re- alizes the same linear function for (21, 22) and (c21, C22) when e > Oie (22.,22) Tg = V (e2)) 0g- Since dg is piecewise linear, 0g (c2,, 622) = 00 22))- Thus, the input of the next function in the iteration is scaled by well and its linear function (or the Jacobian) remains unchanged. By induction, same holds for all the subsequent iterations. By chain rule, the Jacobian of composition of functions is equal to the product of Jacobian of each individual function. Since the Jacobian of each function is unchanged on scaling by > O, the Jacobian ((2,,22) g(n) also remains un- changed: (z),))) ((m) (een, ((m), This suggests that it is possible to determine the Jacobian (=))))) (()) for the input (21, 22) by first converting to the polar coordinates (v + 22 (p)
and
then using the phase angle ip alone (where cos(pp / V oं + 22 sin(pp /2/ 2 + 22)
This motivates us to construct another GNP piecewise linear activation that only depends on the phase of the input but unlike og. it allowed have more than 2 linear regions without requiring a sequential application. This construction is given in the following theorem (example in Figure 2b):
Theorem 2. Given: 0 S Go 01... 2n 2T + Ou such that E (02s+1 B2s) and a; = 2 Σ 0 0-- The function de TR:2 - RR2 is continuous, GNP and 1 1-Lipschitz where θ = 10,, 01....,. 02....,02a-111 (also called Householder Activation of order n in 2 dimensions):
00(21, 22) [
COS 04 ((-1)siino; 04
sin 0z (-1)(t) cos 04
21
0: S 4 < 0s+1
22
where yp E (0o: Ozn = 2x + 0o) and cos(pp) = 21 / V + 2z sin(p) = 22/ v 1 + oz.
Using the definition of ats 01 can be computed as follows:
2n-1
1
02 =2 2
0 1---11(-10 (-11 =
(02n-1-2) - 02n 22)) 3;)= 22 Σ (02j+1 - -02z) = 2n
==0
j=0
1=0
(2(21, 22)
Cos a'2n
sin Q-2n-1
[2] 22
22)
0g S 40 < 0g (= 9o + 2xx
sin 02n-1 Cos 0:2n
By continuity, 0e(21, when o 0 (or 22 0). However, learnable 9g offers the flexibility of choosing arbitrary intervals around the و = 0g to be the identity function (while of course allowing fg = 0). Since we can choose any interval of 2x for the phase angle, we choose i E [0o, 6zn A + 2 instead of the usual [0, 2x) to allow this possibility. We call (v2 + 23. (p), the shifted polar coordinates.
(21, for y Po. Thus if we set 6g = 0, de is fixed to be identity
Additionally, make the following observations about Theorem 2 First, by construction de has 2n linear regions. Second, since Ei (02+11 62x) n, the sum of angles subtended by linear regions with determinant -1 equals π. This in turn implies that sum of angles subtended by linear regions with determinant +1 1 must also equal π. Third, again using 5 nn- (02j+1 - 022) -T, we know that =i=
only 2n 1 of the 2n parameters in [0o, 61, 0z.... .... 62n- 1] can be chosen independently implying that ae has 2n. 1 learnable parameters. In contrast, (n)) has only n learnable parameters. Fourth, when n = 1, σe reduces to the original og activation.
Because every function of the form (n)) (equation (23) can have potentially 2n linear regions, while de has only 2n linear regions, de cannot express every function of the form o()), The primary benefit of using de is that it can be easily applied by first determining the angle (using shifted polar coordinates), the region (6t, 6.+1) to which şo belongs and the Jacobian for this region. This requires multiplication with the Jacobian instead of required for (n)).
G EXTENSION TO HIGHER DIMENSIONS
We introduced Householder activation function of Order 1 in m dimensions in maintext Definition] | However, it suffers from the limitation that has only 2 linear regions thus limiting its expressive power. The construction given in Appendix Section more than 2 linear regions but is valid only for 2 dimensional inputs. This motivates us to construct Householder activations that depend on all the components of input z E Rm (m 2 3) while allowing for more than 2 linear regions.
22

---

Published as a conference paper at ICLR 2022
A straightforward way of constructing such activation function is to apply orthogonal matrix Q E Rm*x,, followed by dividing the output Qz into groups of size each and then applying de to each group. However, since 1-Lipschitz neural networks involve multiplication with an orthogonal weight matrix followed by GNP activation anyway, this construction is trivial because does not lead to additional gains in expressive power using dimensional de activation functions.
Recall that the function dy is given by the following equation:
2 ([I -v-2vv²)
v 2 > 0,
(v(z)
(24)
2vv²'
T S 0.
By similar analysis for the 2-dimensional case (Figure 2 in maintext), repeated application of dv leads to increased number of linear regions and thus higher expressive power. This motivates us to construct the function ((,,)) Rm - R by applying the function By (equation (24) n times
iteratively with different learnable parameter each iteration:
(m.n) Ov dv Ov dv
times, different
ez i.e V, ov Vex ov when > 0, (m,,)) satisfies this property well. This suggests that it possible determine the Jacobian of o (m.n) for the given input by projecting onto unit sphere: 2/||z|/2. Moreover, want constructed function to have at least 2n linear regions while requiring iterations of av where is independent of n. This motivates the following open question:
Since dy realizes the same linear function for both the inputs
Open Problem. Can non-trivial order-n (n 1) householder activation functions with 2n linear regions be constructed for m dimensional input (m > 2) using iterations of 5v where k is independent of n (but may depend on m)?
H ADDITIONAL RESULTS ON CIFAR-10
The rows "BCOP", "Cayley" and "SOC (baseline)" all use the MaxMin activation function. "SOC + HH" replaces MaxMin with 2D Householder activation of order (aa), "+ CR" adds Certificate Regularization (CR) with y 0.1 (while using dg the activation function).
In Table the row "SOC (2) uses Householder activation of order (ag defined in Theorem 2}. "+ CR" adds Certificate Regularization (CR) with = 0.1 (while using the HH activation of order 2 i.c de as the activation function).
None of the results in Tables
8 and 9 include Last Layer Normalization (LLN).
23

---

Published as a conference paper at ICLR 2022
Running times (seconds)
Architecture
MaxMin
HH
LipConvnet-5
3.7864
3.86
LipConvnet- 10
5.3677
5.6014
LipConvnet-15
7.234
7.3503
LipConvnet-20
9.536
9.3753
LipConvnet-25
11.0512
11.2692
LipConvnet-30
12.5135
13.6866
LipConvnet-35
14.5539
15.0921
LipConvnet-40
17.1907
17.1928
Table 6: Inference times for various networks on the complete test dataset of CIFAR-10 with 10000 samples. None of these networks include Last Layer Normalization (LLN).
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(108/255)
BCOP
74.25%
58.01%
40.34%
25.21%
-1.8%%
Cayley
72.37%
55.92%
38.65%
24.27%
-2.82%
LipConvnet-5
SOC (baseline)
75.78%
59.18%
42.01%
27.09%
(+0%)
SOC HH
76.30%
60. 60%1
43.20%
27.39%
+0.30%
CR
75.31%
60.37 %
45.62%
32.38%
+5.29%
BCOP
74.47%
58.48%
40.77%
26.16%
-2.99%
Cayley
74.30%
57.99%
40.75%
25.93%
-3.22%
LipConvnet-10
SOC (baseline)
76.45%
60.86%
44.15%
29.15%
(+0%)
SOC HH
76.86
61.52%
44.91%
29.90%
+0.75%
CR
76.23%
62.57 %
47.70%
34.15%
+5.00
ВСОP
73.86%
57.39%
39.33%
24.86%
-4.80%
Cayley
71.92%
54.55%
37.67%
23.50%
-6. 6.16%
LipConvnet-15
SOC (baseline)
76.68%
61.36%
44.28%
29.66%
(+0%)
SOC HH
77.41
61.92%
45.60%
31.10%
+1 11.4%%
CR
76.39%
62.96 %
48.47 %
35.47%
+5.81
ВCОP
69.84%
52.10%
34.75%
21.09%
-9.99%
Cayley
68.87%
51.88%
35.56%
21.72%
-9.36%
LipConvnet-20
SOC (baseline)
76.90%
61.87%
45.79%
31.08%
(+0%)
SOC + HH
76.99%
61.76%
45.59%
30.99%
-0.09%
CR
76.34%
62.63 %
48.69
36.04%
+4.96
Table Results for provable robustness on the CIFAR-10 dataset using shallow networks. None of these results include Last Layer Normalization (LLN).
24

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(108/255)
BCOP
68.47%
49.92%
31.99%
18.62%
-9.98%
Cayley
64.00%
45.55%
29.24%
16.99%
-11.61%
LipConvnet-25
SOC (baseline)
75.24%
60.17%
43.55%
28.60%
(+0%)
SOC HH
76.37
61.50%
44.72%
29.83%
+1.23%
CR
75.21 %
61.98% %
47.93%
34.92%
+6.32%
ВCОP
64.11% %
43.39%
25.02%
12.15%
-15.90%
Cayley
58.83%
38.68%
22.07%
10.68%
-17.37%
LipConvnet-30
SOC (baseline)
74.51%
59.06%
42.46%
28.05%
(+0%)
SOC+ HH
75.25 %
59.90%
43.85%
29.35%
+1.30%
CR
74.23%
60.64%
46.51
34.08%
+6.03
ВCОP
63.05%
41.71%
23.30%
11.66%
-1.88%%
Cayley
53.55%
32.37%
16.18%
6.33%
-0.87%%
LipConvnet-35
SOC (baseline)
73.73%
58.50%
41.75%
27.20%
(+0%)
SOC HH
75.44%
61.05%
45.38%
30.85%
+3.65%
CR
74.25%
61.30% %
47.60
35.21 %
+8.01 %
ВCОP
60.17%
38.86%
21.20%
9.08%
-15.0%%
Cayley
51.26%
27.90%
12.06%
3.81%
-20332%
LipConvnet-40
SOC (baseline)
71.63%
54.39%
37.92%
24.13%
(+0%)
SOC
HH
73.24%
58.12%
42.24%
28.48%
+4.35%
CR
72.59%
59.04% %
44.92%
32.87%
+8.74%
Table Results for provable robustness against adversarial examples on CIFAR-10 dataset. None of these results include Last Layer Normalization (LLN).
25

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(108/255)
SOC + HH 2)
75.85%
59.66%
42.68%
27.44%
+0.35%
LipConvnet-5
+ CR
74.85%
60.56%
44.96%
31.98%
+4.59%
SOC + HH (2)
76.80%
61.44%
44.91%
29.70%
+0.55%
LipConvnet-10
+ CR
76.30%
62.1
47.85%
34.49%
+5.34%
SOC HH
77.41%
62.21 %
45.11%
30.49%
+0.83%
LipConvnet-15
+ CR
75.73%
62.21%
47.92%
35.26%
+5.60%
SOC + HH (2)
76.69%
61.58%
45.39%
30.89%
-0.19%
LipConvnet-20
CR
75.72%
62.61 %
48.30%
35.29%
+4.21%
SOC + HH
76.12%
61.24%
44.81 %
29.63%
+1 +1.03%
LipConvnet-25
+ CR
75.38%
61.94%
47.67%
34.22%
+5.62%
SOC HH 75.09%
60.01% %
44.22%
29.39%
+1.34%
LipConvnet-30
+ CR
74.88%
61.23%
46.63%
34.02%
+5.97%
SOC + HH (2)
73.93%
58.61% %
42.29%
28.47%
+1.27%
LipConvnet-35
CR
74.14%
60.72%
46.67%
34.64%
+7.44%
SOC + HH
70.90%
54.96%
38.94%
24.90%
+0.77%
LipConvnet-40
+ CR
72.28%
57.67%
43.00%
30.66%
+6.53%
Table 9: Results for provable robustness on CIFAR-10 using HH activation of Order (ae).
Increase (108/255) is calculated with respect to SOC baseline (from Tables 7 8) None of these results include Last Layer Normalization (LLN).
Architecture
Methods
Standard Accuracy
Provable Robust Acc. (p =)
Increase
(36/255)
(72/255)
(108/255)
(Standard)
SOC (no LLN)
75.78%
59.18%
42.01%
27.09%
(+0%)
LipConvnet-5
SOC + LLN
75.78 %
59.58%
42.45%
27.20%
+0.00 %
SOC (no LLN)
76.45%
60.86%
44.15%
29.15%
(+0%)
LipConvnet-10
SOC + LLN
76.69%
61.08%
44.04%
29.19%
+0.24%
SOC (no LLN)
76.68%
61.36%
44.28%
29.66%
(+0%)
LipConvnet-15
SOC + LLN
76.84%
61.94%
45.51 %
30.28%
+0.16% %
SOC (no LLN)
77.05%
61.87 %
45.79%
31.08%
(+0%)
LipConvnet-20
SOC + LLN
76.71%
61.44%
44.92%
30.19%
-0.34%
SOC (no LLN)
75.24%
60.17%
43.55%
28.60%
(+0%)
LipConvnet-25
SOC + LLN
76.54%
61.21% %
44.18%
29.47%
+1.30%
SOC (no L.LN)
74.51 %
59.06%
42.46%
28.05
(+0%)
LipConvnet-30
SOC + LLN
74.26%
58.97%
41.82%
26.93%
-0.25%
SOC (no LLN)
73.73%
58.50%
41.75%
27.20%
(+0%)
LipConvnet-35
SOC + LLN
74.32%
59.05%
42.34%
28.14%
+0,59 %
SOC (no LLN)
71.63%
54.39%
37.92%
24.13%
(+0%)
LipConvnet-40
SOC + LLN
74.03%
58.27 %
41.75%
27.12%
+2,40 %
Table 10: Results for provable robustness the CIFAR-10 dataset with and without LLN
26

---

Published as a conference paper at ICLR 2022
I ADDITIONAL RESULTS ON CIFAR-100
All results Tables and 15 include Last Layer Normalization (LLN).
The rows "BCOP", "Cayley" and "SOC (baseline)" all use the MaxMin activation function. "SOC + HH" replaces MaxMin with 2D Householder activation of order (aa), "+ CR" adds Certificate Regularization (CR) with 7 0.1 (while using dy as the activation function).
In Table 15 the row "SOC + HH uses Householder activation of order 2 (oe defined in Theorem 2 "+ CR" adds Certificate Regularization (CR) with y = 0.1 (while using the HH activation of order 2 i.e σg as the activation function).
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(Standard)
SOC + MaxMin
42.71%
27.86%
17.45%
9.99%
LLN
45.86%
31.93%
21.17%
13.21%
+3.15%
LipConvnet-5
HH 46.36%
32.64%
21.19%
13.12%
+3.65 %
CR 45.82%
32.99%
22.48%
14.79%
+3.11%
SOC + MaxMin
43.72%
29.39%
18.56%
11.16%
LLN 46.88%
33.32%
22.08%
13.87%
+3.16%
LipConvnet-10
HH 47.96%
34.30%
22.35%
14.48%
+4.24%
+ CC
47.07%
34.53%
23.50%
15.66%
+3.35%
Table 11: Results for provable robustness against adversarial examples on the CIFAR-100 dataset.
Running times (in seconds)
Architecture
MaxMin (no LLN)
MaxMin (LLN)
HH (LLN)
LipConvnet-5
3.7568
3.5002
3.6673
LipConvnet-10 10
5.3714
5.5482
5.5533
LipConvnet-15 15
7.3092
7.2595
7.3127
LipConvnet-20
9.005
9,2043
9.308
LipConvnet-25
10.9321
10.7868
11.726
LipConvnet-30
12.3198
13.2168
13.6275
LipConvnet-35
14.427
14.575
15.7069
LipConvnet-40
16.0911
16.2535
17.1015
Table 12: Inference times for various networks on the CIFAR-100 test dataset. Similar to CIFAR-10 (in Table 6). these numbers are for the whole test dataset with 10000 samples.
27

---

Published as a conference paper at ICLR 2022
Architecture
Methods
Standard Accuracy
Provable Robust Acc. (p =)
Increase
36/255
72/255
108/255
(108/255)
BCOP
46.31%
31.55%
20.34%
12.52%
-0.69%
Cayley
44.61 %
31.01%
19.84%
12.43%
-0.78%
LipConvnet-5
SOC (baseline)
45.86%
31.93%
21.17%
13.21 %
(+0%)
SOC + HH
46.36%
32.64%
21.19%
13.12%
-0.09%
+ CR
45.82%
32.99%
22.48%
14.79% %
+1 +1.58%
BCOP
45.36%
31.71%
20.48%
12.40%
-1.47%
Cayley
45.79%
31.91%
20.69%
12.78%
-1.9%
LipConvnet-10
SOC (baseline)
46.88%
33.32%
22.08%
13.87%
(+0%)
SOC + HH
47.96%
34.30%
22.35%
14.48%
+0.61%
CR
47.07%
34.53%
23.50%
15.66 %
+1.79%
BCOP
43.70%
30.11%
19.85%
12.29%
-1.47%
Cayley
45.05%
31.60%
20.32%
12.93%
-0.83%
LipConvnet-15
SOC (baseline)
47.72%
33.52%
21.89%
13.76%
(+0%)
SOC + HH
47.72% %
33.97%
22.45%
13.81 %
+0.05%
CR
47.61 %
34.54%
23.16%
15.09
+1.33%
ВCОP
39.77%
27.20%
17.44%
10.49%
-3.61%
Cayley
39.68%
26.93%
17.06%
10.48%
-3.62%
LipConvnet-20
SOC (baseline)
46.86%
33.48%
22.14%
14.10%
(+0%)
SOC + HH
47.71%
34.22%
22.93%
14.57%
+0.47%
CR
47.84%
34.77%
23.70%
15.84%
+1.74%
Table 13:
Results for provable robustness on the CIFAR-100 dataset using shallow networks. All of these results include Last Layer Normalization (LLN).
28

---

Published as a conference paper at ICLR 2022
Architecture
Methods
Standard Accuracy
Provable Robust Acc. (p =)
Increase
36/255
72/255
108/255
(108/255)
BCOP
34.15%
21.57%
13.52%
7.97%
-5,99%
Cayley
33.93%
21.93%
13.68%
8.19%
-5.67%
LipConvnet-25
SOC (baseline)
46.32%
32.87%
21.53%
13.86%
(+0%)
SOC + HH
47.70%
34.00%
22.67%
14.57%
+0.71%
+ CR
46.87%
34.09%
23.41 %
15.61 %
+1.75%
BCOP
29.73%
18.69%
10.80%
6%
-7.52%
Cayley
28.67%
18.05%
10.43%
6.09%
-7.43%
LipConvnet-30
SOC (baseline)
46.18%
32.82%
21.52%
13.52%
(+0%)
SOC + HH
46.80%
33.72%
22.70%
14.31%
+0.79%
CR
46.92%
34.17%
23.21%
15.84%
+2.32%
BCОP
25.65%
14.88%
8.47%
4.30%
-8.5%%
Cayley
27.75%
16.37%
9.52%
5.40%
-7.85%
LipConvnet-35
SOC (baseline)
45.22%
32.10%
21.28%
13.25%
(+0%)
SOC + HH
46.21 %
32.80%
21.55%
14.13%
+0.88%
CR
46.88%
33.64%
23.34%
15.73%
+2.48
BCОP
30.66%
18.68%
10.46%
5.92%
-6.07%
Cayley
25.54%
14.91%
8.37%
4.40%
-7.59%
LipConvnet-40
SOC (baseline)
42.94%
29.71%
19.30%
11.99%
(+0%)
SOC + HH
45.84%
32.79%
21.98%
14.07%
+2.08%
CR
45.03%
32.57%
22.37%
14.76%
+2.77%
Table 14: Results for provable robustness on the CIFAR-100 dataset using deeper networks. All of these results include Last Layer Normalization (LLN).
29

---

Published as a conference paper at ICLR 2022
Standard Accuracy
Provable Robust Acc. (p =)
Increase
Architecture
Methods
36/255
72/255
108/255
(108/255)
SOC HH
46.61%
32.50%
21.34%
13.22%
+0.01%
LipConvnet-5
CR
46.69%
33.22%
22.34%
14.30%
+1.09%
SOC+ + HH
47.47%
33.32%
21.84%
13.75%
-0.01 %
LipConvnet-10
CR
47.53%
34.52%
23.06%
15.07 %
+1.31 %
SOC HH
47.19%
33.67%
22.36%
13.78%
-0.09%
LipConvnet-15
CR
47.22%
34.04%
22.98%
15.28%
+1.41 %
SOC HH
47.86%
33.93%
22.44%
14.41%
+0.31%
LipConvnet-20
CR
47.54%
34.32%
23.53%
15.54%
+1.44%
SOC+ HH
47.86%
33.97%
22.78%
14.59%
+0.73%
LipConvnet-25
47.50%
34.38%
23.92%
15.92%
+2.06%
SOC HH
46.23%
32.64%
21.95%
14.00%
+0.48%
LipConvnet-30
+ CR
46.36%
33.20%
22.70%
14.85%
+1.33%
SOC (H
46.06%
32.35%
21.33%
13.65%
+0.40%
LipConvnet-35
CR
45.78%
33.24%
22.39 %
14.78%
+1.53%
SOC + HH
43.81%
30.59%
20.08%
12.56%
+0.57%
LipConvnet-40
CR
45.61%
32.50%
22.36%
14.84%
+2.85%
Table 15: Results for provable robustness on CIFAR- 100 using HH activation of Order (ae).
Increase (108/255) calculated with respect to SOC baseline (from Tables B 14). All of these results include Last Layer Normalization (LLN).
Architecture
Methods
Standard Accuracy
Provable Robust Acc. (p =)
Increase
(36/255)
(72/255)
(108/255)
(Standard)
SOC (no LLN)
42.71%
27.86%
17.45%
9.99%
(+0%)
LipConvnet-5
SOC + LLN
45.86 %
31.93%
21.17%
13.21
+3.15%
SOC (no LLN)
43.72%
29.39%
18.56%
11.16%
(+0%)
LipConvnet-10
SOC + LLN
46.88
33.32%
22.08%
13.87% %
+3.16% %
SOC (no LLN)
42.92%
28.81%
17.93%
10.73%
(+0%)
LipConvnet-15
SOC + LLN
47.72%
33.52%
21.89%
13.76%
+4.80
SOC (no LLN)
43.06%
29.34%
18.66%
11.20%
(+0%)
LipConvnet-20
SOC + LLN
46.86%
33.48
22.14%
14.10%
+3.80%
SOC (no LLN)
43.37%
28.59%
18.18%
10.85%
(+0%)
LipConvnet-25
SOC + LLN
46.32%
32.87% %
21.53%
13.86%
+2.95%
SOC (no L.LN)
42.87%
28.74%
18.47%
11.21%
(+0%)
LipConvnet-30
SOC + LLN
46.18%
32.82%
21.52%
13.52%
+3.31 %
SOC (no LLN)
42.42%
28.34%
18.10%
10.96%
(+0%)
LipConvnet-35
SOC + LLN
45.22%
32.10%
21.28%
13.25%
+2.80 %
SOC (no LLN)
41.84%
28.00%
17.40%
10.28%
(+0%)
LipConvnet-40
SOC + LLN
42.94%
29.71 %
19.30%
11.99%
+ +1.10% %
Table 16: Results for provable robustness the CIFAR-100 100 dataset with and without LLN
30


Reviews:
[{"review_id": "u3P1i92hIys", "reviewer": "Reviewer_imTR", "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": "Pros: \n1. The authors find several limitations of existing works and propose three novel methods to address them. Both methods are very novel and have their advantages to address the problems. \n2. The authors present their findings and current problems and introduce the proposed methods very clear from a high level to a very detailed level. The notations, equations, and proofs are easy to follow. \n3. The figures and tables are clearly designed. Figure 1 illustrates the HH activation very clear and makes it easier to be understood. We can clearly see the improvements achieved by each method from Table1. \n4. This paper contributes a lot to the research area of 1-Lipschitz CNNs, especially the class of piecewise linear GNP activation functions HH. \n\nCons: \n1. A minor issue is the structure of this paper. In the Introduction, the authors present the three methods in the order: HH, LLN, CR. However, the order in the method sections is LLN, CR, HH. The logic is a little bit messed up. \n2. It is not clearly explained why the original robustness certificate (Eq 4.) has a problem when the number of class k is large. And why LLB can not achieve significant gains on CIFAR10, just because of the small number of classes? \n\nQuestion: \n1. From Table 1, why the performance of LipConvnet-40 (45.84) is even worse than LipConvnet-5 (46.36) and other shallow networks? ", "summary_of_the_paper": "The authors propose three methods to improve deterministic l2 robustness certificates of 1-Lipschitz convolutional neural networks. \n\n1. Last Layer Normalization (LLN): \n    (1) Relax the orthogonalization of the last weight layer of the network W. \n    (2) The direction of the rows in W can change freely; do not need to update other rows in W and forgot the learned information.\n    (3) Efficient than original robustness certificate when the number of classes K is large. \n2. Certificate Regularizer (CR): \n    (1) Enable the gradients to continue increasing the margin M_f(x) while entropy loss becomes small by adding the regularization term. \n    (2) The relu function in the maximization term ensures that the optimization tries to increase the certificates only for the correctly classified inputs.\n3. Householder Activation Functions (HH): \n    (1) Introduce a general linear GNP activation function named HH for the special case MaxMin used in Anil et al., 2018. and other works. \n    (2) Prove this HH transformation is necessary for any GNP piecewise linear function to be continuous. \n   \nTheir experimental results demonstrate the effectiveness of these proposed methods compared to the baseline method SOC. ", "summary_of_the_review": "The paper proposed three novel methods to address some limitations of existing works. It appears to be technically sound, but I have not carefully checked every detail. The experimental evaluations convincingly support the main claims. This paper contributes some new ideas in this specific research area. ", "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": "ONwloA3hObi", "reviewer": "Reviewer_dTST", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "This paper is well-written. I am not very familiar with the field of certified robustness, but the three bullet points listed in my Summary of Paper are well motivated and justified, and their success has been proved in numerical experiments. My major concerns are about the explanation of the numerical results. The authors have observed improvement in standard accuracy in certain circumstances, which needs more explanation on why this happened. Is it because you relax the orthogonalization requirement of the last linear layer?\n\nA minor comment on Page 2, when introducing \\rho, it would be good to define what it is. For readers who are not familiar with the field, it looks a bit confusing. I only got what it means when reading later sections of the paper.\n\nAnother comment at the end of Section 2, where you mentioned some past work focusing on l1 norm certificate. Can you expand a little bit explaining what is the motivation for considering l2 certificate, difference and applicable settings for these two concepts?\n\nLastly about the numerical section, is it possible to include results on large datasets such as ImageNet, to test the effectiveness, scalibility of the proposed procedure? Also, you observed different performance gains on different architectures. Can you provide an explanation on why this is so, and give a short summary regarding when your procedure would work best, and when it yields negligible gains?", "summary_of_the_paper": "This paper proposed a procedure to certify the robustness of 1-Lipschitz CNNs by \n\n(i) relaxing the orthogonalization of the last linear layer of the network, while requiring that all rows of the last layer matrix are normalized -- Last Layer Normalization;\n\n(ii) introducing a certificate regularization that increases the robust certificate for correctly classified examples;\n\n(iii) introducing a class of Gradient Norm Preserving activation functions called Householder activations which are necessary for any GNP piecewise linear function to be continuous.\n\nThey proved the success of the proposed procedure on CIFAR-10 and CIFAR-100 by showing improvements in provable robust accuracy with a comparable standard accuracy.", "summary_of_the_review": "Overall I like this paper and the proposed ideas were well justified. My comments on the weakness mainly involve the explanation of the numerical results, and whether it is possible to include more results on larger datasets. It would be good if the authors can provide a short summary on when their method would work the best. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "J4Whe7uUqdj", "reviewer": "Reviewer_FsEx", "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": "Pros:\n- Excellent numerical improvements\n- The paper is clearly written\n- The contributions are mainly from the engineering point of view and this paper demonstrates the method works well, with coherent explanations.\n\nCons:\n- I have a minor concern w.r.t. the structure of the paper, I think some of the “Theorem” could be simply called “Proposition”: please don’t get me wrong, I simply think it’s good to distinguish crucial mathematical results from trivial properties (here continuous functions).\nTheorem 1, I think, should be phrased differently: it requires to introduce formally the robustness certificate first. Then, one find a property of this certificate which can be stated as a proposition. Again, I feel Theorem 2 is a too strong statement for this. It’s also strange to see that the Theorem 1 uses phrasing from the Definition 1 but is still above this latter.\n- I think the choice of the parameter $\\gamma$ should be fully detailed. In other words, that it has been cross-validated on a subset of the training set. Otherwise, a suspicious reader could believe the accuracy has been optimized on the test set.", "summary_of_the_paper": "This work is following the line of (Anil et al 2018), its goal is to propose criteria that allows to train models wirth orthogonal weights and to certify they are. The authors generalize (Anil et al 2018) by considering a more expressive non-linearity which leads to unitary jacobians, with a softer criterium during supervision which allows to obtain better accuracies. Overall, I feel the paper is well motivated, and the results are convincing.", "summary_of_the_review": "The scientific contribution of this paper is solid in my opinion: a problem is introduced, solved with a generalization of a previous framework. The explanations of the improvements are clear, and because the contribution is fully technical and the results are good, I think, except if I missed an element (such as a working with a similar result) that this paper would be a nice contribution to ICLR.", "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": "IcFLTRFgYm-", "reviewer": "Reviewer_zg69", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main issue of this paper is evaluation. And the SOC work (Singla & Feizi, 2021) has the same issue.\nThe Lipschitz constant of an SOC layer is not strictly bounded by 1 and is only approximately 1.\nLet X be the product of the Lipschitz constants of all layers in a network.\nWith many layers and multiplications, X could deviate sizably above 1.\nThis effect can get exacerbated after the extra loss term \"Certificate Regularizer\" (CR) is added which encourages the SOC layers to amplify logits and hence signals in all intermediate layers.\nThis explains why, in Table 2, the effect of CR grows stronger as the network gets deeper.\n\nTherefore, the reported provable robustness numbers, which are measured by margins in logits, are not reliable:\n* The absolute numbers of provable robust accuracies could be overestimated for all models in Tables 1 and 2.\n* The relatively comparisons in Tables 1 and 2 are not with constant X. Since the comparisons are in the range of a few percentage points, the actual robustness difference between models can easily get lost in the fluctuation of X of different networks.\n\nIn such situation, please consider the following:\n* Report measured robustness by running adversarial attacks. While doing that, the comparison should not be limited to SOC and should include other techniques like adversarial training.\n* After training is done, calculate the actual X of the final network and then divide logits by X before measuring margins for provable robustness assessment.\n", "summary_of_the_paper": "This paper addresses the problem of provable L2 robustness in image classification.\nThree techniques are proposed as additions on top of the SOC work (Singla & Feizi, 2021):\n1) let the last linear layer be non-orthogonal and adjust provable L2 robustness calculation accordingly;\n2) add a loss term that encourages larger margins in logits;\n3) a new nonlinearity.\n\nComparisons against the original SOC work are reported on CIFAR-10 and CIFAR-100.", "summary_of_the_review": "The evaluation setup is flawed and therefore unable to judge the value of the proposed techniques. Update: ratings adjusted based on new results from authors.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a procedure for certifying L2 robustness in image classification. The paper shows that the technique indeed works in practice by demonstrating it's accuracy on CIFAR-10 and CIFAR-100 datasets. 

The reviewers are positive about the paper. Please do incorporate feedback, especially around experimental setup to ensure that the work compares various methods fairly and provides a clear picture to the reader.
Decision: Accept (Spotlight)