Improved techniques for deterministic l2 robustness
Authors: Sahil Singla
Soheil Feizi
Venue: NeurIPS 2022 Accept (2022)
Keywords: provable defenses
adversarial examples
Lipschitz CNNs
formal guarantees

Abstract: Training convolutional neural networks (CNNs) with a strict 1-Lipschitz constraint under the l_{2} norm is useful for adversarial robustness, interpretable gradients and stable training. 1-Lipschitz CNNs are usually designed by enforcing each layer to have an orthogonal Jacobian matrix (for all inputs) to prevent the gradients from vanishing during backpropagation. However, their performance often significantly lags behind that of heuristic methods to enforce Lipschitz constraints where the resulting CNN is not provably 1-Lipschitz. In this work, we reduce this gap by introducing (a) a procedure to certify robustness of 1-Lipschitz CNNs by replacing the last linear layer with a 1-hidden layer MLP that significantly improves their performance for both standard and provably robust accuracy, (b) a method to significantly reduce the training time per epoch for Skew Orthogonal Convolution (SOC) layers (>30\% reduction for deeper networks) and (c) a class of pooling layers using the mathematical property that the l_{2} distance of an input to a manifold is 1-Lipschitz. Using these methods, we significantly advance the state-of-the-art for standard and provable robust accuracies on CIFAR-10 (gains of  +1.79\% and +3.82\%) and similarly on CIFAR-100 (+3.78\% and +4.75\% across all networks.

Improved techniques for deterministic ll robustness
Sahil Singla
Soheil Feizi
Department of Computer Science University of Maryland ssingla@umd. edu
Department of Computer Science University of Maryland sfeizi @umd. edu
Abstract
Training convolutional neural networks (CNNs) with strict 1-Lipschitz constraint under the l2 norm is useful for adversarial robustness, interpretable gradients and stable training. 1-Lipschitz CNNs usually designed by enforcing each layer have an orthogonal Jacobian matrix (for all inputs) to prevent the gradients from vanishing during backpropagation. However, their performance often significantly lags behind that of heuristic methods to enforce Lipschitz constraints where the resulting CNN is not provably 1-Lipschitz. this work, reduce this gap by intro- ducing (a) procedure to certify robustness of I-Lipschitz CNNs by replacing the last linear layer with 1-hidden layer MLP that significantly improves their perfor- mance for both standard and provably robust accuracy, (b) method to significantly reduce the training time per epoch for Skew Orthogonal Convolution (SOC) layers (> 30% reduction for deeper networks) and (c) a class of pooling layers using the mathematical property that the la distance of input a manifold is 1-Lipschitz. Using these methods, we significantly advance the state-of-the-art for standard and provable robust accuracies on CIFAR- 10 (gains +-1 1.79% and +3.82%) and sim- ilarly on CIFAR- (+3.78% and +4. 75%) across all networks. Code is available at httts:://iithbb
Introduction
The Lipschitz constant of a neural network f R + RS, denoted by Lip( controls the change in the output divided by change in the input (both changes measured in the l2 norm). Previous work provides evidence that small Lipschitz constant is useful for interpretable saliency maps Tssppas et al. 2018). generalization bounds [Long and Sedghi] 2020), Wasserstein distance estimation Villani 2008 adversarial robustness (Szegedy al.) 2014 and preventing gradient explosion during backpropagation [Xiao et al. 2018). Several prior works MMyato et al. 2018 Gulrajani et al., 2017 use heuristic methods enforce Lipschitz constraints to successfully address problems such as stabilizing GAN training. However, these methods do not enforce a guaranteed lipschitz bound and it remains challenging achieve strong results with provable guarantees.
Using the composition property i.e. Lip(g o h) < Lip(g) Lip(h), we can construct a 1-Lipschitz neural network by constraining each layer be 1-Lipschitz. However, key difficulty with this approach is that because a 1-Lipschitz layer can only reduce the gradient norm during backpropagation, for deeper networks, this results in small gradient values for layers closer the input making training slow and difficult. To address this problem. Anil et al. (2018) introduce Gradient Norm Preserving (GNP) architectures where each layer preserves the gradient norm during backpropagation. For I-Lipschitz Convolutional Neural Networks (CNNs), this involves using orthogonal convolutions (convolution layers with an orthogonal Jacobian matrix) [Li et al. 2019b Trockman and Kolter
In this work, we assume the Lipschitz constant under the la norm.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: CIFAR- 10 results using faster gradients, projection pooling, CRC-Lip
SOC layers
Time/epoch (secs)
Reduction
Standard accuracy
Provable robust accuracy
Ours
Previous
Ours
Previous
Ours
Previous
6
25.34
30.63
-17.27% %
79.36 %
76.68%
67.13%
60.09%
11
37.11
48.44
-23.39% %
79.57 %
77.73%
66.75%
62.82%
16
49.27
66.74
-26.17% %
79.44% %
77.78%
66.99%
62.75%
61.59
83.18
25.966%
79.13%
77.50%
66.45%
63.31%
26
71.51
100.70
28.99%
79.19% %
77.18%
66.28%
62.46%
84.00
119.55
299.74%
78.64%
74.43%
66.05%
59.65%
36
95.06
137.10
-30.66% %
78.57 %
72.73%
65.94%
57.18%
41
106.01
156.25
-32.16%
78.41 %
71.33%
65.51 %
55.74%
2021 Singla and Feizi 2021 Yu et al. [022]] Kiani et al. [022] and using a class of GNP activation
functions called Holder activations [Singla et al. 2022].
Among orthogonal convolutions, SOC [Singla and Feizi 2021 achieves state-of-the-art results on CIFAR-10. 100 (Singla et al., 2022]. SOC uses the following two mathematical properties to construct an orthogonal convolution: (a) the exponential of skew symmetric matrix is orthogonal and (b) the matrix exponential can be computed using the exponential series. drawback of using the exponential series is that it requires us to apply the convolution operation multiple times to achieve reasonable approximation of an orthogonal matrix. Consequently, during backpropagation, computing the gradient with respect to the weights for single SOC layer requires us to compute the weight gradient for each of these convolutions resulting in significant training overhead. In this work, we show that because the matrix is skew symmetric, using some approximations, the gradients with respect to weights can be computed in significantly reduced time with no loss performance. This enables us to reduce the training time per epoch using SOC by > 30% for networks with large number SOC layers (Results in Table T].
Another limitation of L-Lipschitz CNNs is that their performance is often significantly below com- pared that of standard CNNs. Recently, /Singla al. [2022) introduced a procedure for certifying robustness by relaxing the orthogonality requirements of the last linear layer (i.e. the linear layer mapping penultimate neurons to class logits) achieving state of the art results on CIFAR-10 10, 100 (Knihevskyy [2009] Since MLPs are more expressive than linear layers, one would expect improved stundard uccuracy by replacing the last linear layer with them. However, the resulting networks are not 1-Lipschitz and achieving high robustness guarantees (provable robust accuracy) is difficult.
To certifyy robustness for these networks, note that since the mapping from input to penultimate layer is L-Lipschitz, the robustness certificate for the penultimate output also provides a certificate for the input. Thus, we first replace the linear layer mapping penultimate output logits with a 1-hidden layer MLP (Multi layer Perceptron) because such MLPs are easier to certify compared to deep MLPs. Robustness Certificate or CRC (Singla and Feizi 2020]. To train MLP to have high robustness guarantees, we use variant of adversarial training that only applies adversarial perturbations to the MLP (not the whole network). We call our certification procedure CRC-Lip. This results in improved results for both the standard and also the provable robust accuracy across network architectures on CIFAR- 10 (> 1.63%, 2 3.14%) and CIFAR- 100 (2 2.49%, > 2.27% respectively). Results are in Tables
To centify robustness for the MLP, we use the Curvature-basse
and
While several works have attempted to construct novel and more expressive orthogonal convolution layers and GNP activation functions, current statc-of-the-ar 1-Lipschitz CNNs still use pooling layers by taking the max of different elements. In this work, we introduce a class of 1-Lipschitz pooling layers called projection pooling using the following mathematical property: Given manifold M C R and input x R", the function d. R + R defined the 12 distance of x to M is 1-Lipschitz. Thus, to construct a pooling layer, we can first define learnable manifold with parameters θ (Example in Section (). During training, for input x E R.", the pooling layer simply outputs (x) E R as the output, resulting in decrease in input dimension by factor of n. Moreover, since the output dx(xx) is also function of O can be learned during training. However, solving for the distance d (x) can be difficult especially when M is a high-dimensional manifold.

---

To address this limitation, (a) we use 2D projection pooling layers that reduce the dimension by factor of 2 and (b) we construct these layers using piecewise linear curves for which the distance can be computed efficiently by computing the minimum distance to all line segments and the connecting points (Example Appendix Figure 2 If the curve is closed and without self seff-intersections, we can also define signed projection pooling for which the signs of the output for points inside and outside the region enclosed by the curve are different (x and y in Figure 2). This allows the subsequent layers to distinguish between the inputs inside and outside the region. In this work, we show some preliminary results using a simple 2D projection pooling layer (Section 6.. We leave the problem of constructing high performance 2D projection pooling layers open for future research.
In summary, this paper, we make the following contributions:
We introduce a method for faster computation of the weight gradient for SOC layers. For deeper networks, we observe reduction in training time per epoch by > 30% (Table Dp.
We introduce a certification procedure called CRC-Lip that replaces the last linear layer with 1- hidden layer MLP and results in significantly improved standard and provable robust accuracy. For deeper networks (2 35 layers), we observe improvements of > 5.84%. 2 8.00% in standard and 2 8.76%, 2 8.65% in provable robust accuracy (22 radius 36/255) on CIFAR-10, 10,100 100 respectively.
We introduce a large class of 1-Lipschitz pooling layers called projection pooling using the mathematical property that the distance (x) of an input to the manifold M is 1-Lipsccitz.
On CIFAR-10, across all architectures, achieve the best standard and provable robust accuracy (at 36/ (2/2 of 79.57, 67.13% respectively (gain of +1.79% +3.82% from prior works). Similarly, on CIFAR-100, we achieve 51.84, 39. 27% 78%, +4.75% from prior works). These results establish new state-of-the-art results in the standard and provable robust accuracy on both datasets.
2 Related work
Provable defenses against adversarial examples: For a provably robust classifier, we can guarantee that its predictions remain constant within some region around the input. Most of the existing methods for provable robustness either bound the Lipschitz constant or use convex relaxations (Singh et al.
2017
2018a 2019a b Weng al. 2018 Salman et al. 2019b Zhang et al., 2019
2018 Wong
et al.
2018| Wong and Kolter 2018 [Snghh et |
201 8b| Raghunathan et al. 2018 Dvijotham et al. Croce al.] 2019 Gowal et al. [219 Dvijotham" * al. [2020] Lu and Kumar 2020 [Sinl
2018
and Feizi| 2020 Bunel et al. 2020 Leino et al. 202 Leino and Fredrikson] |021
Zhang et al.
2021
2022 Wang al. [021] Huang et al. 2021
Müller et al.] 2021 [Singh et al. 2022
Palma et al.
2021
However, these methods are often not scalable to large neura networks while ac achieving high
performance. In contrast, randomized smoothing [Liu al., 2018 Cao and Gong 2017 Lécuyer
ct al. 2018 Li ct al., 20 Cohen et al. 2019 Salman et al.) [219a]] Levine et al. 2019 Kumar
al. 2020a bl Salman al. 2020 2021] scales large neural networks but is probabilistically
certified defense: certilying robustness with high probability requires generating a large number of
noisy samples leading to high inference-time The defense we propose in this work is deterministic and not comparable to randomized smoothing.
The class of Gradient Norm Preserving (GNP) and 1-Lipschitz fully connected neural networks was first introduced by Anil et al. (2018. To design each layer to be GNP, they orthogonalize weight matrices and use class of piecewise linear GNP activations called GroupSort. Later, Singla et al. [0022) proved that for any piecewise linear GNP function to be continuous, different Jacobian matrices in neighborhood must change via householder transforma- tions, implying that GroupSort is a special case of more general HouseHolder activations. Several previous works enforce Lipschitz constraints on convolution layers using spectral normalization.
Provably Lipschitz neural networks:
clipping or regularization (Cissé et al., 2017 Tsuuuuu et al. 2018 Qian and Wegman| 2019 Gouk al., 20200 (edghi et al.] [2019] However, these methods either enforce loose lipschitz bounds or do not scale to large networks. To ensure that the Lipschitz constraint on convolutional layers is tight,
recent works construct convolution layers with an orthogonal Jacobian [Li et al. 2019b Trockman
and Kolter 2021 Singla and Feizi, 2021 Yu et al.) 2022 Su et al.) 2022 Kiani et al. 2022]. These
approaches avoid the aforementioned issues and allow training of large, provably 1-Lipschitz CNNs
achieving state-of-the ahe results for deterministic l robustness.
3

---

3 Problem setup and Notation
For vector v. V, denotes its 5th element. For matrix A, A,, and A, denote the jth row and btth column respectively. Both AJ. and A are assumed to be column vectors (thus A,, is the transpose of row of A). A denotes the element in jth row and hth column A. A.j.k denotes the matrix containing the first rows and lc columns of A. We define A, A.j.: and Aj. j.:.
Similar notation applies to higher order tensors. denotes the identity matrix, R to denote the field of real numbers. We construct 1- 1-Lipschitz neural network. is the number of classes) by composing 1-Lipschitz convolution layers and GNP activation functions. We often use the abbreviation Si ʃz TRd - R to denote the function so that:
R - R (d is the input dimension,
(J= 12) (x) [i(x) (x(x,
V E IRd
For matrix A E TRxx and tensor B E RRxxxx A denotes the vector constructed by stacking the rows of A and by stacking the vectors By j E [p - 1] so that:
T
AAT. AT. ... A-
B r
T
B
B Bp--1..
T
For a 2D convolution filter, L E RXx and input X E R we use L X E R to denote the convolution of filter L with X. We use the the notation L X 2 - (L + X) and
L X X. Unless specified, we assume zero padding and stride I in each direction.
4 Faster gradient computation for Skew Orthogonal Convolutions
Among the existing orthogonal convolution layers in the literature, Skew Orthogonal Convolutions (or SOC) by Singlla and Feizi| [202T] achieves state-of-the oh--th--rttttttt results on CIFAR-10,100 100 (Singla
et al. 2022 SOC first constructs convolution filter L whose Jacobian is skew-symmetric. This is followed by a convolution exponential [Hoogeboom et al. 22200 operation. Since the exponential of skew-symmetric matrix is orthogonal, the Jacobian of the resulting layer is an orthogonal matrix.
However, a drawback of this procedure is that convolution exponential requires multiple convolution operations per SOC layer to achieve reasonable approximation of the orthogonal Jacobian. Conse- quently, if we use k convolution operations in the SOC layer during forward pass, we need to compute the gradient with respect to the weights L (called convolution weight gradient) per convolution operation (I times) which can lead to slower training time especially when the number of SOC layers is large. To address this limitation, we show that even if we & convolutions in the forward pass of an SOC layer, the weight gradient for the layer can be computed using a single convolution weight gradient during backpropagation leading to significant reduction in training time.
For simplicity, let first consider the case of an orthogonal fully connected layer (i.e. not convolution) with the same input and output size (n). Later, we will see that our analysis leads to improvements for orthogonal convolutional layers. Further, assume that the weights i.e. E R=*x are skew-symmetric i.e. A AA and given the input x E R", the output z E R" is computed as follows:
k
z
x + b,
where A A=
(I)
i!
We approximate the exponential series: exp(A) ii=o A /il using finite number of terms (k). Forward pass (z): To compute z during the forward pass, we use the following iterations:
0
x
k
x (An An(++1)/ ((()+))/((-))))
k-k-2
It can be shown that z = () (Appendix C). During backpropagation, given the gradient of loss &
w.r.t. layer output i.e. Vz L, we want compute Vx é (input gradient) and V A l (weight gradient). Input gradient (Vx E): To compute Vx e, observe that z is a linear function of x. Thus, using the chain rule, skew-symmetricity (AT A) and the property (A:)² T (AT)), we have:
b
T
A)
V l -
(V e)
Σ
(Vz E
i!
i!
i=0

---

We can again approximate the exponential series using the same number of terms as in the forward pass i.e. k. To compute the finite term approximation. we use the following iterations:
Vx 2 - (Av(=))
i= k i k
(3)
Similar to forward pass, it can be shown that Vx 8 = (0) (Appendix C
Weight gradient A E): We first derive the exact expression for V in the Theorem below:
Theorem The gradient of the loss function E w.F. A i.e. VA E given by:
VAC-- Σ ((1A-())))) (A) (v(0)) v(0) (A (Ai)
(4)
where vlt is defined as in equation
(v()) and the second i.e. (v(') (A T Note that the first outer product i.e. (A transpose each other implying that each term in the summation is skew-symmetric. Although these outer products can be computed in straightforward way for orthogonal fully connected layers, this is not the case for orthogonal convolution layers (SOC in this case). This is because, for a convolution filter L RPx*xx*x, the term analogous to A 1-1 x is a patch of size q X and that analogous to v() is another patch of size x x resulting in an outer product of the desired size p X q patch. Thus, for SOC layers, each term inside the summation computed by summing over the outer products for all such patches. For large input sizes, the number of such patches can often be large, making this computation expensive. To address this limitation, we use the following approximation:
per
Vala- - (1()) (v!)) -v(1) (ua) T
(5)
In Appendix B. we show that the above approximation is principled because after subtracting the exact and upproximation gradients (equations (4) and ( and simplifying, each term in the resulting series is divided by a large value in its denominator (+= 0). This approximation is useful because in equation (5). the outer product needs to be computed once whereas in equation (4). the outer products need to be computed & times. Also, both u and ((1) are computed while computing (0)
during the forward pass and v0) Vx z during the backward pass using the recurrences in equations (2) and (3). Thus, we can simply store u1)), ((1) during the backward pass respectively so that V A can be computed directly using equation (5). In our experiments, we observe that this leads to significant reduction in training time with almost no drop in performance (Tables 3
5 Curvature-based Robustness Certificate
A key property of L-Lipschitz CNNs is that the output of each layer is 1-Lipschitz with respect to the input. Given an input x E IRd consider the penultimate output gxx) E RR. and logits f(x) E R for some 1-Lipschitz CNN. Existing robustness certificates (Li et al.; 2019b Singla et al. [022] rely on the linearity of the function from g(x) + fx). However, since MLPs have higher expressive power than linear functions [Cybenko 1989. one way to improve performance could be to replace this mapping with MLPs. However, certifying robustness for deep ML.ss is difficult.
To address these challenges, we first replace the mapping from g(x) + f(x) with a 1-hidden layer MLP because they are easier to certify compared to deeper networks. Because computing exact certificates for ReLU networks is known to be NP-complete [Sinha et al. [018). we use the differentiable Softplus activation [Dugas al. (2000) to certify robustness. To certily robustness,
we use the prrvtuure-based Robustness Certificate or CRC (Singla and Feizi 2020 because it provides exact certificates for a significant fraction of inputs for shallow MLPs. We provide a brief review of CRC in Appendix Section D Let g Rd + R" be a 1-Lipschitz continuous function and the predicted class
h: m + Re be a 1-hidden layer MLP such that f = o g. Further, for input i.e. ft(x) 2 maxişt fx(x). Since g is 1-Lipschitz, it can be shown that if h is provably robust in an la radius R around input (x)), then / also provably robust in the la radius R around
The resulting procedure is called CRC-Lip and is given in the following proposition:
5

---

(a) Rearrangement operation
Singla and Feizi
(b) 2D projection pooling
2021
Figure 1: Illustration of the rearrangement operation (left) and 2D projection pooling (right).
Proposition 1 (CRC-Lip) For input x such that fi(x) 2 maxigt f((x,, let R be the robustness certificate for h using input g(x), then R is also the robustness certificate for the function f:
min EA b h,("))
min
Ily* - g(x)ll2 2 R =
min Gfl
min f((x*)=f((x))
|x x 2 R
(6)
Proof is in Appendix A.2 In experiments, find that although replacing the linear layer with an MLP achieves high standard accuracy, directly using the above certificate often leads to very small robustness certificates and thus low certified robust accuracy. To address this problem,
introduce
(a) an adversarial training procedure that only applies to the input of the MLP g(x) ) (i.e. not the input of the neural network x) and (b) curvature regularization reduce the curvature of the MLP. was shown in Singla and Feizi [2021] that combining adversarial training with curvature regularization leads to significantly improved provable robust accuracy with small reduction in standard accuracy. This results in the following loss function for training:
[11-
e (hba(y" .1)) + y Kr
min $2, 4
max - (x)1lasp
In the above equation, Q denote the parameters of the MLP (i.e. It), Vi are the parameters of the 1 1-Lipschitz function g. Krs is the bound on the curvature of the MLP, p denotes the l2 perturbation radius and 7y denotes the curvature regularization coefficient. The curvature bound Nr. is the same as in [Singlla and Feizi (020). Also, since apply adversarial perturbations in the penultimate layer, we also need to backpropagate through this procedure to enable training previous layers. To this end, we simply an identity map (same gradient output the gradient imput) to backpropagate through the adversarial training procedure and find that it works well in practice, achieving significantly principled method of
better results compared the state-of-the-an backpropagation may lead to better results and we leave that avenue open for future research.
It is possible that
Projection pooling layers
In 1-Lipschitz CNNs, pooling is usually carried out follows: given input X Raxxxx (r is even), we first use rearrangement [Jacobsen et al., 2018 illustrated in Figure Ib to construct X' E ((Tx(//2)x((/2) Next, we apply an orthogonal convolution which gives an output of the same size Z (41x(r/2)x((/22) and divide it into two tensors of equal sizes (along the channel dimension) giving Z:2g (rxx and Z:zg: E IR (r/2) We then define (Z:2q Z2g) (or either one of Z:29: Zzg:) as the output of the pooling layer.
Although max is 1-Lipschitz, its expressive power is limited. For example, consider the 1-Lipschitz y, the eтror between || vlle and
function ||, ella Vz² y². is easy see that if max(x, y) can be arbitrarily large for large values of x, y. To address such limitations, we construct expressive pooling layers using the following mathematical property:
Theorem Given X E R and manifold M C R", the distance function (in l2 norm) is I-Lipschitz:
dx(x) = min x EM
||x" - x||2 = 1dm(())dx(3)) - dm(y)) S |x-
The above theorem provides a powerful method for constructing a learnable pooling layer by selecting learnable manifold Me R² (0 denotes the set of learnable parameters). To apply the pooling

---

Output Size
Layer
Output Size
Layer
Repeats
32 32 x 32
Conv + MaxMin
64 x 16 x 16
LipBlook-n/5
qxrxr
Input
128 8 x
LipBlock-n/5
QxTXr
Conv + MaxMin
n/5 -
256 4 X 4
LipBlock-n/5
xqx(r/2)x(r/2
Rearrange
512 x 2 x 2
LipBlock-n/5
(rx(r/2)x(r/22
Conv
1024 x x
LipBlock-n/5
2qx(r/2)x(r/22)
Pooling
# of classes
Linear/MLP11
(b) LipBlock-n/5
(a) LipConvnet-n Architecture
Table 2: LipConvnet-n and SipBlock-n//5 architectures
operation to an input x E R", we simply output its l2 distance to the manifold Me denoted by d.Mo (x). Since dmaa (x) while R", this operation reduces the input size by factor of
As an example, let Mn, = {u}. Here u E R is the learnable parameter and the distance function d.m, (x) || - ull2- Even in this very simple case, for 0, d_m, (x) = ||x||2 and for 2, this function can learn to represent the function ||æ, y/l2 discussed earlier exactly. We also prove that a signed l2 distance function can be defined when M satisfies certain properties:
Corollary If M is a connected manifold that divides R" into two nonempty connected sets A and & and every path from
such that A exists a signed le distance function with different signs in A and B.
and intersects point on M, then there
Proofs of Theorems 2 and Corollary I are given in Appendix A.3 and A respectively.
In practice, computing d'm can be difficult for high-dimensional M. To tackle this issue, we use 2D pooling layers where M is defined be a piecewise linear curve in 2D. The la distance can then be computed by finding the minimum distance to all the line segments and connecting points. We emphasize that even in this relatively simple case, M can have large number of parameters and d. can still be efficient to compute because these individual distances can be computed in parallel. We use Ma defined below (illustrated in Figure lb. lines L1, L2 correspond to ø = +0,- -0):
Mg [R(cos Φ. sin δ) R 0, ò E {+0, -0}}
In each colored region (Figure lb). dM,, can be computed using the following:
Rsin(a 0),
0
dma (R(cos sin
- Rs + 0),
0< a n/2
(9)
R.
otherwise
To apply projection pooling Z:zg Zzy: discussed previously, output dm (Z:2g: Zz
7 Experiments
We perform experiments under the setting of provably robust image classification on CIFAR-10
and CIFAR-100 datasets. We use the LipConvnet-5. 10, 15, ... 40 architectures for comparison. We use SOC as the orthogonal convolution and MaxMin as the activation in all architectures. All experiments were performed using 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. after 100 and 150 epochs. For adversarial training with curvature regularization, we use p 36/255 255 (0.1411). 7 0.5 for CIFAR-10 and 0.2, 7 = 0.75 for CIFAR- 100. We find that certifying robustness using CRC-Lip computationally expensive for CIFAR- 100 due to large number of classes. To address this issue, we only use classes with top-10 logits (instead of all 100 classes) for CIFAR-100 (Table Since CRC-Lip requires us to solve a convex optimization, we consider certificate be valid the input is correctly classified and gradient at the optimal solution is < 10-6 (0 otherwise). All results
7

---

Table Provable robustness results on CIFAR-10 (LipConvnet-55, 10 results in Appendix Table
LipCony
Methods
Standard Accuracy
Provable Robust Accuracy
Increase (standard)
net-
36/255
72/255
108/255
(36/255)
15
Baseline
77.78%
62.75%
46.34%
31.38%
+ Fast
77.75%
62.52%
46.23%
31.19%
-0.03%
-0.23%
+ CRC
79.44%
66.99%
52.56%
38.30% %
+1.66%
+4.24%
20
Baseline
77.50%
63.31%
46.42%
31.53%
+ Fast
77.13%
62.05%
45.86%
31.13%
-0.37%
-1.26%
+ CRC
79.13%
66.45%
52.45%
38.12%
+1.63%
+3.14%
25
Baseline
77.18%
62.46%
45.78%
31.16%
+ Fast
76.94%
61.91%
45.59%
30.69%
-0.24%
-0.55%
+ CRC
79.19%
66.28%
51.74%
37.99%
+2.01
+3.82%
30
Baseline
74.43%
59.65%
43.76%
29.16%
+ Fast
74.69%
58.84%
43.33%
28.93%
+0.26%
-0.81%
+ CRC
78.64%
66.05%
51.31%
37.30%
+4.21%
+6.40%
35
Baseline 72.73%
57.18%
42.08%
28.09%
Fast 72.91
57.58%
41.52%
27.37%
+0.18%
+0.40%
+ CRC
78.57%
65.94%
52.04%
37.63% %
+5.84%
+8.76%
40
Baseline
71.33%
55.74%
39.32%
26.06%
+ Fast
71.60%
56.15%
39.82%
25.63%
+0.27%
+0.41%
+ CRC
78.41% %
65.51%
51.32%
37.30%
+7.08%
+9.77%
reported using the complete test sets of CIFAR-10 and CIFAR-100. We compare the provable robust accuracy using 3 different 12 perturbation radii: 36/255, 72/255, 108 108/255.
Table details: For the baseline (" ("Baseline" in Tables certificate based on LLN (Singla et al. 2022] due to their superior performance over prior works. In Tables 3 and 4 for each architccture, + Fast" adds faster gradient computation, "+ CRC" replaces max pooling with projection pooling (cquation (9)) and replaces the last linear layer with 1-hidden layer MLP (CRC-Lip certificate) while also using faster gradients. For each architecture, the columns "Increase (Standard)" and "Increase (36/255)" denote the increase standard and provable robust accuracy relative to "Baseline" standard and provable robust accuracy (36/255). Results where Projection pooling and CRC-Lip are added separately are given in Appendix Tables
we use the standard max pooling with the
LipConvnet Architecture: We use 1-Lipschitz CNN architecture called LipConvnet-n where is a multiple and n + the total number of convolution layers. consists of an initial SOC layer that expands the number of channels from 3 to 32. This is followed by 5 blocks that reduce spatial dimensions (height and width) by half while doubling the number of channels. The architecture is summarized in Tables 2a and 2b The last layer outputs the class logits and is either a linear layer in which case we use LLN to certify robustness or a singlc-hidden layer MLP where we use CRC-Lip.
Correcting the certificates: Since SOC is an approximation, the Lipschitz constant of each SOC layer can be slightly more than and if we use large number of SOC layers (e.g. 41 LipConvnet- 40), the Lipschitz constant of the full network (Lip(f)) can be significantly larger than 1. To mitigate this issue, we take following steps: (a) We use large number of terms to approximate the exponential which results in small approximation error (using the error bound in Singla and Feizi 2021]) and (b) We compute Lip(f) by multiplying the lipschitz constant all SOC layers (using the power method) and then divide the certificate by Lip(f).
15) during test time

---

Table Provable robustness results on CIFAR- -00 (LipConvnet-5, results in Appendix Table
Lip
Methods
Standard Accuracy
Provable Robust Accuracy
Increase
net-
36/255
72/255
108/255
(standard)
(36/255)
15
Baseline
48.06%
34.52%
23.08%
14.70%
Fast
47.97%
33.84%
22.66%
14.26%
-0.09%
-0.68%
+ CRC
50.79% %
37.50%
26.16%
17.27% %
+2.73%
+2.98%
20
Baseline
47.37%
33.99%
23.40%
14.69%
Fast 46.41%
33.07%
22.06%
14.00%
-0.96%
-0.92%
+ CRC
51.84%
38.54%
27.32%
18.53%
+4.47%
+4.55%
25
Baseline 45.77%
32.08%
21.36%
13.64%
+ Fast 45.28%
31.67%
20.69%
13.26%
-0.49%
-0.41%
CRC
51.59%
39.27%
27.94%
19.06%
+5.82%
+7.19%
30
Baseline 46.39%
33.08%
22.02%
13.77%
+ Fast 45.86%
32.54%
21.18%
12.77%
-0.53%
-0.54%
CRC
50.97%
38.77%
27.73%
19.28%
+4.58%
+5.69%
35
Baseline 43.42%
30.36%
19.71%
12.66%
Fast 42.78%
29.88%
19.73%
12.52%
-0.64%
-0.48%
+ CRC
51.42%
39.01%
28.94%
20.29 %
+8.00%
+8.65%
40
Baseline 41.72%
28.53%
18.37%
11.49%
+ Fast 42.07%
28.51%
18.86%
11.89%
+0.35%
-0.02%
+ CRC
50.11% %
38.69%
28.45%
20.05 %
+8.39%
+10.16%
7.1 Results using Faster gradient computation
show the reduction in training time per epoch (in seconds) on CIFAR-10 Table T and CIFAR- 100 in Appendix Table 8 In both Tables, we observe that for deeper networks (2 25 layers), the reduction in time per epoch is zo 30%. The corresponding standard and provable robust accuracy numbers are given in 3 (CIFAR- 10) and 4 (CIFAR-100) in the row "+ Fast". From the columns "Increase (Standard)" and "Increase (36/255)" we observe that the performance is similar to the baseline across all network architectures. For deeper networks: LipConvnet-35, 40, observe increase in performance for CIFAR-10 and small decrease (< 0.64%) for CIFAR-100.
7.2 Results using projection pooling and CRC-Lip
We observe that using CRC and projection pooling (row "+ CRC") leads to significant improvements performance across all LipConvnet architectures. CIFAR-10, we observe significant improve- ments in both the standard (2 1.63%, column "Increase (standard)") and provable robust accuracy (2 3. 3.14, column "Increase (36/255)") across all architectures. CIFAR-100, we also observe significant improvements in the standard (2 2.49%) and provable robust accuracy (2 2.27%). For deeper networks (LipConvnet--)) 40), on CIFAR-10 we observe even more significant gains in the standard (2 5.84%) and provable robust accuracy (2 8. 3.76%). Similarly on CIFAR-100 observe gains 2 8.00% (standard) and 2 8.65% (provable robust).
Our results establish a new state-of-the-an for both the standard and provable robust accuracy across all attack radii. Table (CIFAR 10), the best "Baseline" standard and provable robust accuracy val- ues (at 36/255, 22/ 72/255 "+ CRC" values are 79.57% and 13%, 53. 17%. 38.60%. This results in improvements -1.9% and +3.82%, +6.75% +7.07% respectively. Similarly, in Table (CIFAR 100), the best "Baseline" standard and provable robust values are 48.06% and 34.52%, 23.40%. 14.70%. The best CRC" values are 51.84% (+3.78%) and 39.27% ( (+4.75%) 27.94% (+4.54%) 20. 20.29% (+5.59%).
108/200 (25) are 77. 77.78% and 63.31% %. 46.42%. 31.53% respectively. The best

---

8 Acknowledgements
This project was supported in part by NSF CAREER AWARD 1942230, a grant from NIST G0NANB20D134, HR001 19S0026 (GARD), ONR YIP award N00014-22-1-2271, Army Grant No. W911NF2120076 and the NSF award CCF2212458.
References
C. Anil, Lucas, and B. Grosse. Sorting out lipschitz function approximation. In ICML, 2018.
R. Bunel, J. Lu, Turkaslan, P. H. S. Torr, P. Kohli, and M. P. Kumar. Branch and bound for piccewise linear neural network verification. Mach. Learn. Res., 21:42:1-42:39, 2020.
X. Cao and N. Z. Gong. Mitigating evasion attacks to deep neural networks via region-based classification. In Proceedings of the 33rd Annual Computer Security Applications Conference, ACSAC 2017, page 278-287, New York, NY. USA, 2017, Association for Computing Machinery, ISBN 9781 9781450353458. doi: 10. (4/53134600.. 334666 URL stttps://ool org 1ttgg/0.11444 1145/
3134600. 3134666
M. Cissé, P. Bojanowski, E. Grave, Y. N. Dauphin, and N. Usunier. Parseval networks: Improving robustness adversarial examples. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, 17 Sydney, NSW, Australia, 6-1 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 854-863. PMLR, 2017. URL httth::/pproeeeediiiiiin
mlr ppwps/v70/ crvess/v7//cssee1 1esseeaaa....... html
J. M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. ICML, 2019.
F. Croce, M. Andriushchenko, and M. Hein. Provable robustness of relu networks via maximization of linear regions. AISTATS 2019, 2019.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control. Sig- nals, and Systems (MCSS), 2(4): Dec. 1989. ISSN 0932-4194. doi: 10.1007/BF02551274. URL http::/ttp/.....///e doi org/ 10. 1007/BF02551774
C. Dugas, Y. Bengio. Bélisle, C. Nadeau, and R. Garcia. Incorporating second- order functional knowledge for better option pricing. In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, vol-
13. MIT Press, 2000. URL htttts://ppoceeeecee http:::////popppppp//e//e 44458aecc44667770000000000808
Paper pdf
K. Dvijotham*, R. Stanforth, S. Gowal, T. Mann, and P. Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UA1-18), Corvallis, Oregon, 2018. AUAI Press.
K. D. Dvijotham², A. Raghunathan, J. Uesato, S. Dathathri, A. Kurakin, I. Goodfellow, Kohli, Steinhardt, and P. Liang. Hnabling certification of verification-agnostie networks via memory- efficient semidefinite programming. In Advances in Neural Information Processing Systems, pages 2020.
H. Gouk, F. Frank, B. Pfahringer, and M. J. Cree. Regularisation of neural networks by enforcing lipschitz continuity, 2020.
S. Gowal, K. Dvijotham", R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. A. Mann, and Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. In ICCV, volume 9, pages 2019.
I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of wasserstein gans. In I. Guyon, U. V. Luxburg, S. Bengio, Wallach, R. Fergus, S. Vishwanathan, and R. Gareett, editors, Advances in Neurul Information Processing Systems, volume 30, pages 5767-5777. Curran Associates, Inc., 2017. URL, ttt. htw.iggg....rpp.p...ppp.r.. 2017/fiiee/89220011666666 2017://il...cccaa.oocccccee2eee2
pdf
10

---

E. Hoogeboom, V. G. Satorras, J. Tomczak, and M. Welling. The convolution exponential and generalized sylvester flows. ArXiv, Abss2006.00910. 2020.
Y. Huang, H. Zhang, Y. Shi, J. Z. Kolter, and A. Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. In A. Beygelzimer, Y. Dauphin, P. Liang, and W. Vaughan, editors, Advances Neural Information Processing Systems, 2021. URL https
J. Jacobsen, A. Smeulders, and E. Oyallon. i-revnet: Deep invertible networks. In International Conference on Learning Representations, 2018. URL URL http::://ppoooreiiiiiii forr/ffr HJsjkMbOZ
B. Kiani, R. Balestriero, Y. Lecun, and S. Lloyd. projunn: efficient method for training deep networks with unitary matrices, 2022. BtLhstts::/// http://awxvv....aaabaea arg/abs/2203. 220222222232 05483
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
A. Kumar, A. Levine, S. Feizi, and T. Goldstein. Certifying confidence via randomized smoothing. In H. Larochelle, M. Ranzato. R. Hadsell, M. F. Balcan, and H. Lin, edi- tors, Advances in Neural Information Processing Systems, volume 33, pages 5165-5177 Cur- ran Associates, Inc., 2020a. URL https::/procceeeeeeeee werddiinnnnnuuiipppe neurins weeeurpps.ccppppee////eee htcppappe/2222//f110 pdf
A. Kumar, A. Levine, T. Goldstein, and S. Feizi. Curse of dimensionality randomized smoothing for certifiable robustness. In H. D. and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5458-5467. PMLR, 13-18 Jul 2020b. URL http:://proceedings mlr press/v119/ kumar20b.. html
M. Lécuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. K. K. Jana. Certified robustness to adversarial examples with differential privacy. In IEEE S&P 2019, 2018.
K. Leino and M. Fredrikson. Relaxing local robustness. In Neural Information Processing Systems (NIPS), 2021.
K. Leino, Z. Wang, and M. Fredrikson. Globally-robust neural networks. International Conference on Machine Learning (ICML), 2021.
A. Levine, S. Singla, and S. Feizi. Certifiably robust interpretation in deep learning, 2019.
B. Li, C. Chen, W. Wang, and L. Carin. Certified adversarial robustness with additive noise. In H. Wallach, H. Larochelle, A. Beygelzimer, F, Alche-Bue, E. Fox, and R. Garnett, edi- tors, Advances in Neurul Informution Processing Systems, volume 32, pages 9464-9474. Cur- ran Associates, Inc., 2019a. URL httpss: http:ttte/eprreeeiinggsssse wwweediiinnnnn.iiii.peeee newrips www.eiis..cpppppereeeeee. /sc/paper/2219/filee/ 010.0002244440033330000002202222
pdf
Q. Li, S. Haque, C. Anil, J. Lucas, R. Grosse, and J.-H. Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. Conference on Neural Information Processing Systems, 2019b.
X. Liu, M. Cheng, H. Zhang, and C. Hsieh. Towards robust neural networks via random self-ensemble. In ECCV, 2018.
P. M. Long and H. Sedghi. Generalization bounds for deep convolutional neural networks. In International Conference on Learning Representations, 2020. URL https::/openreviie: net/ forum? iidtmmddd-ree_ppF>>
J. Lu and M. P. Kumar. Neural network branching for neural network verification. In International Conference on Learning Representations, 2020. Jutphattpe///ppprrreeeeee/////rp Blevfa4tPB
T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018. URL https::/
openreview
Dpenreriew.net//ooummtsss www./eeeu///iiiie BattimmiddiBiggegee B-ggigT

---

C. Müller, F. Serre, G. Singh, M. Püschel, and M. Vechev. Scaling polyhedral neural network verification on gpus. A. Smola, A. Dimakis, and Stoica, editors, Proceedings of Machine Learning and Systems, volume 3, pages 733-746, 2021. URL /ttp: lasiiinngss................. mlsys
htt//pppe/2221111 http://///...oaooeeo./////22222.
A. D. Palma. H. Behl, R. R. Bunel, P. Torr, and M. P. Kumar. Scaling the convex barrier with active sets. In International Conference Learning Representations. 2021. URL https
//openreview wwt.:eee//oooo htte:/oorunnid-u0Eyylll.ll.
H. Qian and M. N. Wegman. L2-nonexpansive neural networks. In International Conference on Learning Representations, 2019. URL
A. Raghunathan, Steinhardt, and P. Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In NeurlPS, 2018.
H. Salman, J. Li, I. Razenshteyn, P. Zhang, H. Zhang, S. Bubeck, and G. Yang. Prov- ably robust deep learning via adversarially trained smoothed classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Ad- vances in Neural Information Processing Systems, volume 32, pages 11292-11303, Cur- ran Associates, Inc., 2019a. URL httpstt::://// htttps://proceeedings neur www.ipe.rrccccmmc pcppppp//ppp////////eeel pdf
H. Salman, G. Yang, H. Zhang, C.-J. Hsieh, and P. Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b. URL htttpss//procceednggss.sts Paper.. pdf
cc/ ht//appr//209/ httppp/e200/////a///6a2aaeeeffe0 2244a/65544eeeb5443eeaaa wwtpaa//166111dfffafammaa
Paper.
H. Salman, M. Sun, G. Yang. A. Kapoor, and J. Z. Kolter. Denoised smoothing: A provable defense for pretrained classifiers. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
H. Salman, S. Jain, E. Wong, and A. Madry. Certified patch robustness via smoothed vision transformers. CoRR, abs/2110.07719, 2021. URL httppp///aaxvvvoo//////////////
H. Sedghi, V. Gupta, and P. M. Long. The singular values of convolutional layers. In International Conference on Learning Representations, 2019. httptp:://opparreieee.eeeee/eeee IJevYoA9Fm
the G. Singh, M. Püishel, and M. Vechev. Fast polyhedra abstract domain. In Proceedings the 44th
ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, page 46-59, New York, NY, USA. 2017. Association for Computing Machinery. ISBN 978 1450346603. doi: /0rgg/10..0 10. /145/300993// 30098855
10.1 00.11455300988333309888
bttpsttss:///at htte//ii..og////////
G. Singh, T. Gehr, M. Mirman, M. Püschel, and M. Vechev. Fast and effective robustness certification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018a. URL https: //proceein/s. neurips. wttp:pppp.cpppppprppeeepe ccpppaperr/2001//iieee. f 7F
.df
G. Singh, T. Gehr, M. Mirman, M. Puschel, and M. T. Vechev. Fast and effective robustness certification. In NeurlPS, 2018b.
G. Singh, R. Ganvir, M. Püschel, and M. Vechev. Beyond the single neuron convex barrier for neural network certification. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox. and R. Gameet, editors. Advances in Neural Information Processing Systems, volume 32, Cur- ran Associates, Inc., 2019a. URL /tL.attpp://ppooeiiiss.oo http:/ccccgg..aooppp..c////rr/rp (afrabb17facccc77e000bbbb2222224
pdf
G. Singh, T. Gehr, M. Püschel, and M. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3POPLL.. jan 2019b. doi: 10. 145/32903344 htltpstss:: //doi org/10. /0/0 3245/429034
12

---

G. Singh, T. Gehr, M. Püschel, and M. Vechev. Robustness certification with refinement. In International Conference on Learning Representations, 2019c. URL ltttps://openrevierr net:fforunIdd-JgeehDooo
H. Singh, M. P. Kumar, P. Torr, and K. D. Dvijotham. Overcoming the convex barrier for simplex inputs. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https://openreviee. http:eerrweieeeeeeeeeeeeeeeeeeee JXREUkyHi7u
S. Singla and S. Feizi. Second-order provable defenses against adversarial attacks. In H. D. III and A. Singh, editors, Proceedings of the 37th Internaiional Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1981-8999 1-8991. PMLR, 13-18 Jul 2020. URL http::/proceedingge
mlr grres//v11/singlaat html
S. Singla and S. Feizi. Skew orthogonal convolutions. In ICML, 2021. URL httth:ttt//aaitii org/ abs/21055 11417
Singla, Singla, and S. Feizi. Improved deterministic 12 robustness on CIFAR-IO and CIFAR-100.
In International Conference on Learning Representations, 2022. URL https:://pperreview httpffforunndddtteeeaate
A. Sinha, H. Namkoong, and J. Duchi. Certifiable distributional robustness with principled adversarial
training. In International Conference on Learning Representations, 2018. URL https://
J. Su, W. Byeon, and F. Huang. Scaling-up diverse orthogonal convolutional networks with paraunitary framework. ICML, 2022. UtLptttps: http://wwwwwwwwwaaa//////// 2210//99110000011111
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL pettt://arrxin org//br/////// aa//////s/11./////////a/////1//a 6199
A. Trockman and J. Z. Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021. URL https:// net/
Forum?id JEHYV
D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry. Robustness may be odds with accuracy. In ICLR, 2018
Y. Tsuzuku, Sato, and M. Sugiyama. Lipschitz-margin training: Scalable certification of perturba- tion invariance for deep neural networks. In NeurIPS, 2018.
C. Villani. Optimal transport, old and new, 2008.
S. Wang, H. Zhang. K. Xu, X. Lin, S. Jana, C.-J. Hsieh, and J. Z. 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. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL ht httpp::/ http:///ppereieieeee net/forum iidiiddhhiii aaaaaaaaIIBBBFF.B
L. Weng, H. Zhang, H. Chen, Z. Song, C.-J. Hsieh, L. Daniel, D. Boning. and I. Dhillon. Towards fast computation of certified robustness for ReLU networks. In Dy and A. Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5276-5285. PMIR, 10-15 Jul 2018. URL /ttpps:/ proceedings. mlr. wwwppresvvvvv. v80/ h00///nn//// weng18a. html
E. Wong and Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5286-5295, Stockholnsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. http' //proceedings... mml
html
E. Wong, R. Schmidt, J. H. Metzen, and J. Kolter. Scaling provable adversarial defenses. In NeurIPS, 2018.
13

---

L. Xiao, Y. Bahri, J. Sohl-Dickstein, S. Schoenholz, and J. Pennington. Dynamical isome- try and mean field theory of CNNs: How to train 10,000-layer vanilla convolutional neu- ral networks. In J. Dy and A. Krause, editors, Proceedings of the 35th International Con- ference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5393-5402, Stockholmssässaa,, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:/ httt:://proceeding mlr, pww.s//0e////eeeeeeeeee hwtp://0xxii8aaa...a html
Yu, Li, Y. CAI, and P. Li. Constructing orthogonal convolutions in am explicit manner. In International Conference on Learning Representations, 2022. URL https::/eppnnreview .ntt/
forum?id=2r5f211
B. Zhang, T. Cai, Z. Lu, D. He, and L. Wang. Towards certifying linfinity robustness using neural networks with linfinity-dist neurons. In ICMI., 2021.
B. Zhang, D. Jiang, D. He, and L. Wang. Boosting the certified robustness of I-infinity distance nets. In International Conference on Learning Representations, 2022. URL htttp::/ net.fforumidd-Q(66kkkjjj
H. Zhang, T.-W. Weng, P.-Y, Chen, C.-J. Hsieh, and L. Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems (NIPS), arXiv preprint
dee 2018.
H. Zhang, P. Zhang, and C.-J. Hsieh. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. In AAAI Conference Artificial Intelligence (AAAI), arXiv preprint arXiv: 1810.111117100 dec 2019.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] in Section 7 we discuss how CRC-
Lipmight lead to slower certification.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A] because it expensive to run.
(d) Did you include the total amount compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica- ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "OiamgFIm0n", "reviewer": "Reviewer_idv1", "summary": "This paper presents techniques for accelerating and improving the training of 1-Lipschitz CNNs for certified $\\ell_2$ robustness. Specifically, the paper proposes an approximate gradient computation procedure for skew orthogonal convolutions (SOC) which reduces the training time of SOC-based CNNs. The paper also presents a trainable 1-Lipschitz projection-based pooling layer and proposes to replace the last linear layer of 1-Lipschitz CNNs with a certifiable 1-hidden layer MLP for improved robustness. The combination of these techniques improves the state-of-the-art provable $\\ell_2$ robustness on CIFAR-10 and CIFAR-100.", "questions": "1) How exactly is the certified robust accuracy computed? Is it just the fraction of test inputs whose certificate is smaller than the perturbation strength? It would be better to include this in the main manuscript. \n\n2) Continuing on the pooling layer, it seems to me from Tables 6 and 7 that adding the proposed pooling layers decreases performance. Why is that? and if it is the case then why is it needed? Does it work well in conjunction with the MLP layer? (i.e., is +MLP + pool better than +MLP with standard pool?)\n\n3) Is there a reason why the HouseHolder activation not being used in this work? The authors are aware that it provides improvements in robustness. Does it not stack well with the proposed methods?\n\n4) How long does to take to certify using the proposed methods? and how does it compare to the baselines used in the paper?\n", "limitations": "Paper does not properly address the limitations, e.g. what is the overhead of certification?", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well motivated and well written. The paper is clearly organized, and the proposed methods are explained pretty well. The theoretical results are clearly stated and all the proofs are provided in the Appendix\n- The experimental results seem to back the author's claims, in terms of demonstrating the improvement in certified robustness, however I have some questions regarding the efficacy of the pooling layer (see below)\n\nWeaknesses:\n- Going deeper with LipConvnet (as n increases) decreases the natural and robust accuracies consistently, which is counter-intuitive. I understand this is not due to the paper's proposed method, but it makes me wonder why go deeper with these networks in the first place?\n- The claim 1-Lipschitz is not technically correct, due to the exponential approximation performed in SOC, is this why going deeper hurts performance?\n- The method is restricted to $\\ell_2$ norm robustness\n- The pooling layer seems to be counter-productive, as it decreases the robustness (see Tables 5 & 6 in the Appendix) in a fairly consistent manner. \n- This is a bit unusual, but I have a found a lot of text similarities between this paper and that of the cited work [1]. A decent portion of the text seems to be copied or poorly paraphrased (e.g. Intro, parts of background). I understand the paper seems to be inspired by [1], as the titles are also similar and the methodology (improved last linear layer, improved non-linearity) are aligned. But, in my opinion, this does not justify such 'lazy' writing.\n\n\n[1] Singla, S., Singla, S., & Feizi, S. (2021, September). Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100. In International Conference on Learning Representations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KGezJsrEsd", "reviewer": "Reviewer_yBdY", "summary": "The work proposes 3 methods that could be used to improve the training of the 1-Lipschitz networks from different aspects: (1) an approximation approach for the calculation of gradients in SOC layers which makes the method more time-efficient; (2) changing the final linear layer of a network to an MLP and specifically apply adversarial training on the MLP yields superior performances; (3) a more expressive pooling method compared with max-pooling. The work then empirically demonstrates that using (1) results in time-efficient models with no significant sacrifice in performance and using (2)(3) together boost both natural accuracy and robustness of trained models.", "questions": "In the experiment section, it is not entirely clear how the individual components of the proposed methods contribute to the final results. Currently, the message is (1) the fast computation of gradients mostly makes the performances drop; (2) using all 3 proposed methods increases the performances, and (3) from Table 5 and 6 in the Appendix, it seems like using the projection pooling alone also sometimes sacrifices the performances. So does this mean that all the gain is from the usage of MLP? A more detailed ablation study could be done here to better investigate the effect of each individual component.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe overall presentation is clear and easy to follow. The relationships with prior arts are detailly discussed. Also, the empirical results show that the proposed methods are indeed helpful. \n\nWeaknesses:\nThe reviewer did not find any major flaws in the paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "APxmR5arYFt", "reviewer": "Reviewer_n1ze", "summary": "This paper proposes an 1-Lipschitz CNN with improved standard and provable robust accuracies on CIFAR-10 and CIFAR-100 with 1) faster gradient copmutation of SOC layers; 2) 1-hidden layer MLP instaed of last linear layer; 3) 1-Lipschitz pooling layer called projection pooling. ", "questions": "* This paper ends abruptly without a conclusion section. Is this intended? \n* CRC-Lip looks like an effective way to boost performance on 1-Lipschitz CNN, can it scale to larger problems ? \n* Comparison only includes LipConvnet, are there any other relavent works not mentioned? ", "limitations": "Assumptions and Limitations are mentioned in the paper, would be hepful to have a dedicated summarization. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* Originality: The proposed methods for improving 1-Lipschitz CNN on standard and provable robust accuracies is original. \n* Quality: The introduced methods for faster gradient computation of SOC layers using approximation, as well as using projection pooling with 1-hidden layer MLP instead of last linear layer is well motivated and justified.  \n* Clarity: The paper is clearly written with necessary details. \n\nWeakness: \n* Significance: The authors mentioned by themsleves that the proposed CRC-Lip for certifying robustness is computationally expensive even for CIFAR-100, this may limit its applicability to broader problems (e.g. ImageNet and etc.) ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5iUMMP3DnGu", "reviewer": "Reviewer_Rd49", "summary": "This paper improves and aggregates techniques for 1-Lipschitz CNNs with respect to the $l_2$ norm. First, the authors approximate the gradient for Skew Orthogonal Convolutions (SOC) so the throughput is increased. Second, the paper cooperates Curvature-based Robustness Certificate (CRC) into CNN to replace the last linear layer of the model. Third, it introduces a novel 1-Lipschitz pooling layer which is learnable. Combining these three techniques achieves better standard/robust accuracy on CIFAR-10/CIFAR-100 with a shorter training time.", "questions": "- Can you also report the state-of-the-art by other methods, e.g., randomized smoothing?\n- The best 36/255 provable robust accuracy on CIFAR-10 is achieved by LipConvnet-5, which is very different from previous results where the best is LipConvnet-20. Do you have any insights into the change?\n- In which part of the network do you apply the ``identity map'' in Line 217? Or do you mean that the gradient of the objective is computed as the gradient of $\\ell(h_{\\Omega}(g_{\\Phi}(x) + \\epsilon, l)) + \\cdots$ where $\\epsilon$ is the adversarial perturbation?\n- Does \"+CRC\" rows in tables include faster gradient computation? If not, what is the performance change for \"+CRC +Fast\"?\n\nMinor:\n- Line 49, there is no LipConvnet-$n$ in Table 1.\n- Eq (7), there is a missing bracket.\n- Line 212, why is $h$ a parameter of $g$?", "limitations": "I do not see the negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- This paper provides a good summary of previous techniques and some non-trivial improvements to them. \n- The majority of the empirical gain comes from applying CRC to the last layer, which is a decent empirical contribution but not completely novel.  \n- The new pooling layer is pretty novel as far as I know, but the performance gain is not consistent. Especially for CIFAR-100, the performance drops except for LipConvnet-5. Therefore, I am not sure whether it is a good contribution or not.\n- Faster gradient computation for SOC is novel and the speedup brought is notable. However, I am not sure if it is useful in practice because the decrease of provable robust accuracy is not negligible.\n- Some writing is not clear enough, especially for readers who are not familiar with previous works. See my questions below. I suggest thorough proofreading.\n- Figure 1(a) is very similar to Figure 3 of [Singla and Feizi, 2021]. Please reference.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept