Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds
Authors: Yujia Huang
Huan Zhang
Yuanyuan Shi
J Zico Kolter
Anima Anandkumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: lipschitz constant
local lipschitz constant
certified defense
adversarial examples
robustness

Abstract: Certified robustness is a desirable property for deep neural networks in safety-critical applications, and popular training algorithms can certify robustness of a neural network by computing a global bound on its Lipschitz constant. However, such a bound is often loose: it tends to over-regularize the neural network and degrade its natural accuracy. A tighter Lipschitz bound may provide a better tradeoff between natural and certified accuracy, but is generally hard to compute exactly due to non-convexity of the network. In this work, we propose an efficient and trainable \emph{local} Lipschitz upper bound by considering the interactions between activation functions (e.g. ReLU) and weight matrices. Specifically, when computing the induced norm of a weight matrix, we eliminate the corresponding rows and columns where the activation function is guaranteed to be a constant in the neighborhood of each given data point, which provides a provably tighter bound than the global Lipschitz constant of the neural network. Our method can be used as a plug-in module to tighten the Lipschitz bound in many certifiable training algorithms. Furthermore, we propose to clip activation functions (e.g., ReLU and MaxMin) with a learnable upper threshold and a sparsity loss to assist the network to achieve an even tighter local Lipschitz bound. Experimentally, we show that our method consistently outperforms state-of-the-art methods in both clean and certified accuracy on MNIST, CIFAR-10 and TinyImageNet datasets with various network architectures.

show that Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds
Yujia Huang' Huan Zhang? Yuanyuan Shi Zico Kolter Anima Anandkumar
Califormia Institute of Technology "Carnegic Mellon University 3UC San Diego 4Bosch Center for AI SNVIDIA
yinuangecaltech. edu huan@huan caannuuuanzzangggg com yyshi ucsd.edu zkolterêcs emu edu anima@caltech. edu
Abstract
Certified robustness desirable property for deep neural networks in safety- critical applications, and popular training algorithms certify robustness of neural network by computing a global bound on its Lipschitz constant. However, such bound is often loose: it tends over-regularize the neural network and de- grade its natural accuracy. A tighter Lipschitz bound may provide better tradeoff between natural and certified accuracy, but is generally hard to compute exactly due to non-convexity of the network. In this work, we propose an efficient and trainable local Lipschitz upper bound by considering the interactions between activation functions (e.g. ReLU) and weight matrices. Specifically, when comput- ing the induced norm of a weight matrix, we eliminate the corresponding rows and columns where the activation function is guaranteed to be a constant in the neighborhood each given data point, which provides provably tighter bound than the global Lipschitz constant of the neural network. Our method can be used as plug-in in module to tighten the Lipschitz bound in many certifiable training algorithms. Furthermore, MaxMin) with a learnable upper threshold and a sparsity loss to assist the network achieve
propose to clip activation functions (c.g., ReLU and
tighter local Lipschitz bound. Experimentally, our method consistently outperforms state-of-the-ae methods in both clean and certified accuracy on MNIST, CIFAR- 10 and TinylmageNet datasets with various network architectures.
Introduction
With the ever-growing deployment of deep neural networks, formal robustness guarantees are needed in many safety-critical applications. Strategies to improve robustness such as adversarial training only provide empirical robustness, without formal guarantees, and many existing adversarial defenses have been successfully broken using stronger attacks [1]. In contrast, certified defenses give formal robustness guarantees that any norm-bounded adversary cannot alter the prediction of a given network.
Bounding the global Lipschitz constant of neural network is computationally efficient and scalable approach to provide certifiable robustness guarantees [2-4]. The global Lipschitz bound is typically computed as the product of the spectral norm of each layer. However, this bound can be quite loose because it needs to hold for all points from the input domain, including those inputs that are far away from each other. Training network while constraining this loose bound often imposes to high degree of regularization and reduces network capacity. It leads considerably lower clean accuracy in certified training compared to standard and adversarial training [5, 6].
local Lipschitz constant, on the other hand, bounds the norm of output perturbation only for inputs from a small region, usually selected as a neighborhood around each data point. It produces a
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

ReLU outputs under perturbation
Wix
Wis
Wia Wix
Constant
Wis
Wis
[|e - Sie
perturo
Verving
U8, xi UB,5
1.8g s x2 s UB2
ReldI
Wxn
Wiz
Constant
LBg
LB,
UB;
LBg
2/
UB
8
LBg
25
UB
x
Local Lipschitz bound
| ss 1P
Wiz
Waill|AAl|
Figure 1: Illustration of tighter (local) Lipschitz constant with bounded ReLU.
tighter bound by considering the geometry in a local region and often yields much better robustness certification [7. 8]. Unfortunately, computing the exact local Lipschitz constant is NP-complete [9]. Obtaining reasonably tight local Lipschitz bounds via semidefinite programming [10] mixed integer programming [11] is typically only applicable to small, previously trained networks since it is difficult to parallelize the optimization solver and make it differentiable for training. On the other hand, many existing certified defense methods have achieved success by using a training- approach with relatively weak but efficient bound [12-14]. Therefore, to incorporate local Lipschitz bound in training, a computationally efficient and baiming-friendle method must be developed.
Our contributions: We propose an efficient method to incorporate a local Lipschitz bound in training deep networks, by considering the interactions between an activation layer such as Rectified Linear Unit (ReL.U) layer and linear (or convolution) layer. Our bound is computed for each data point and this translates to different types of outputs from the activation function: constant or varying under input perturbations. If the outputs of some activation neurons are constant under local perturbation, we eliminate the corresponding rows in the previous weight layer and the corresponding columns in the next weight layer, and then compute the spectral norm of the reduced matrix.
Our main insight is to use training to make the proposed local Lipschitz bound tight. This is different from existing works that find local Lipschitz bound for fixed network [8, 10, 11]. Instead, we aim to enable network learn to tighten our proposed local Lipschitz bound during training. To achieve this, we propose to clip the activation function with an individually learnable threshold A. Take ReLU for example, the output of a "clipped" ReI.U becomes constant when input is greater than this threshold (see Figure 1). Once the input of the ReLU is greater than the threshold or less than 0 then this ReLU neuron does not contribute to the local Lipschitz constant, and thus the corresponding row or column of weight matrices can be removed. We also apply this method to Ron- activation functions such as MaxMin [15] to create constant output regions. Additionally, we also use a hinge loss function to encourage more neurons to have constant outputs. Our method can be used plug-in module in existing certifiable training algorithms that involve computing Lipschitz bound. Our contributions can be summarized as:
To the best of our knowledge, we are the first to incorporate a local Lipschitz bound during training for certified robustness. Our bound is provably tighter than the global Lipschitz bound and is also computationally efficient for training.
We propose use activation functions with learnable threshold encourage more fixed neurons during training, which assists the network to learn to tighten our bound. We show that more than 45% rows and columns can be removed from weight matrices.
We consistently outperform state-of-the-art Lipschitz based certified defense methods for &a norm robustness. On CIFAR-10 with perturbation 255 we obtain 54.3% verified accuracy with ReI.U activation function and 60.7% accuracy with MaxMin [15], outperforming the SOTA baselincs, and also achieve better clean accuracy. Our code is available at https: pettps://githut com/yjhie com/yjhuanged. local -il---ppphhhh.
2
Related work
Bounds on Local Lipschitz Constant sound upper bound local Lipschitz constant (simply referred to as "local Lispschitz bound" in paper) crucial property to determine the robustness

---

of classifier. Finding an exact local Lipschitz constant for neural network is generally NP hard [16], so most works focus on finding a sound upper bound. Hein and Andriushchenko [7] derived an analytical bound for 2 layer neural networks and found that local Lipschitz bounds could be much tighter than the global one and give better robustness certificates. RecurJac [8] is recursive algorithm that analyzes the local Lipschitz constant in a neural network using bound propagation [14] based approach. FastLip [17] is a special and weaker form of RecurJac. Fazlyab et al. [10] used a stronger semidefinite relaxation to compute a tighter bound of local Lipschitz constant. Jordan and Dimakis [1I] formulated the computation of Lipschitz as an mixed integer linear programming (MILP) problem and they were able solve the exact local Lipschitz constant. Although these approaches can obtain reasonably tight and sound local Lipschitz constants, none of them have been demonstrated effective for training certifiably robust network, where high efficiency and scalability are required. Note that although an empirical estimate of local Lipschitz constant can be easily found via gradient ascent (e.g., the local lower bounds reported in [4]), it is not sound bound and does not provide certifiable robustness guarantees.
Certifiably Robust Training using Lipschitz constants The Lipschitz constant plays a central role in many works training certifiably robust neural network, especially for E2 norm robustness. Since naturally trained networks usually have very large global Lipschitz constant bounds [18], most existing works train the network encourage small Lipschitz bound. Cisse et al. [2] designed networks with orthogonal weights, whose Lipschitz constants are exactly 1. As this can be too restrictive, later works mostly power iteration to obtain per-layer induced norms, whose product is a Lipschitz constant. Lipschitz Margin Training (LMT) [19] and Globally- Robuss Neural Networks (Gloro) [4] both upper bound the worst margin via global Lipschitz constant with different loss functions. LMT constructs a new logit by adding the worst margin to all its entries except the ground truth class. Gloro construct new logit with one more class than the original logit vector, determines whether the input sample can be certified. However, these approaches did not exploit the available local information to tighten Lipschitz bound and improve certified robustness. Box constrained propagation (BCP) [20] achieves tighter outer bound than global Lipschitz based outer bound, by taking local information into consideration via interval bound (box) propagation. They compute the worst case logit based on the intersection of a (global) ball and (local) box. Although box propagation considers local information, the ball propagation still uses global Lipschitz constant, and its improvement is still limited with low clean accuracy.
Other Certified Defenses Besides using Lipschitz constants, one of the most popular certifiable defense against for norm bounded inputs is via the convex outer adversarial polytope [21, 22]. [13] takes similar approach via abstract interpretation. These methods uses linear relaxations of neural networks to compute an outer bound at the final layer. However, because the convex relaxations employed are relatively expensive, these methods are typically slow to train. A simple and fast certifiable defense for Ex norm bounded inputs interval bound propagation (IBP) [12, 13). Since the IBP bound can be quite loose for general networks, its good performance relies on appropriate hyper-pan syper-parameters. CROWN-IBP [14] outperforms previous methods by combining IBP bound in a forward bounding pass and a tighter linear relaxation bound in a backward bound pass. [23] improved IBP with better initialization to accelerate training. Additionally, randomized smoothing [24-26] is a probabilistic method to certify la norm robustness with arbitrarily high confidence. The prediction of a randomized smooth classifier is the most likely prediction returned by the base classifier that is fed by samples from a Gaussian distribution. Salman et al. [27] further improves the performance of randomized smoothing via adversarial training.
3 Method
We begin with notations and background for Lipschitz bound. We introduce our method for local Lipschitz bound computation in Section 3.2. Then we introduce how to incorporate our efficient local Lipschitz bound in robust training (Section 3.3).
3

---

3.1 Notation and Background
the spectral norm of matrix A. Subscript of vector z denotes element, i.c., Hy is the i-th element of x. We use LB' and UB' to denote lower bounds and upper bounds of pre-ReLU activation values for layer I. Definition 1. The Lipschitz constant of a function f IRd + R over an open set X is defined as,
Notations. We denote the Euclidean norm of vector x as ||ж|| and ||A||
ll (v) f(x)]
M(f,N)= == sup C.NEX,a.
| wll
If L() exists and finite, we say that J. is Lipschitz continuous over Suppose = domí f', T...) is the global Lipschitz constant of J; if X is defined as the e-ball at point i.e, X {2'l]|=- x'Il S <), then (C) the local Lipschitz constant of f at x.
Global Lipschitz bound in existing works Consider a L-layer ReLU neural network which maps input z to output I F(;; W) using the following architecture, for 1, L
z; _+1 o(W
Wh26
(1)
where W = {W are the parameters, and o(.) max(- 0) is the element-wise ReLU activation functions. Here we consider the bias parameters Lipschitz bound. Since the Lipschitz constant of ReI.U activation c6()) ) is equal to 1, global Lipschitz bound of F is,
zero because they do not contribute to the
Lighab I ||W4|| ||W2-111 |W11
where ||W'|| equals the spectral norm (maximum singular value) of the weight matrix W However, the global Lipchitz bound ignores the highly nonlinear property of deep neural networks. In what follows, we introduce our method that considers the interaction between ReLU and linear layer to obtain tighter local Lipchitz bound in computationally efficient way, that allows us train a certifiably robust network using local Lipschitz bounds.
3.2 Our Approach for Efficient Local Lipschitz Bound
In this section, bound. We will discuss how to apply our method on other types of activation functions in Section 3.3. To exploit the piece-wise linear properties of ReLU neurons, discuss the outputs of ReLU case by case. Intuitively, if the input of ReLU neuron is always less or equal to zero, its output will always be zero, which is constant and not contributing Lipschitz bound. If the input of ReLU's can sometimes be greater than zero, the ReLU output will vary based on the input.
ReLU as example to describe how compute efficient local Lipschitz
We define diagonal indicator matrices ((2)) represent the entries where the ReLU outputs are varying and (2') for entries where the ReLU outputs are constaní under perturbation. Here 2 E R4 denotes the feature map of input x at layer 1. Throughout this paper, unless otherwise mentioned, the indicator matrix is function of the feature value 2", evaluated at given input
Given an input perturbation ||ا' =|| < e, suppose 2(xx) is bounded element- wise as LB 2²(') < UB', we define diagonal matrix 1/ and Le as:
<
(i,1)) - {1
iF > otherwise
Ic(1, = (1
if if < otherwise
(3)
By this definition, the ReL.U output can either be constant or vary with respect to input perturbation. Hence we have 14 1. where is the identity matrix. LB and UB can be obtained cheaply from interval bound propagation [12] or other bound propagation mechanisms [21, 28].
A crucial observation is that compute the local Lipschitz bound, we only need to consider the ReLU neurons which are non-fixed. The fixed ReLU neurons are always zero (locally, in the prescribed neighborhood around æ² and thus have impact to final outcome. We define a diagonal matrix Dy to represent the ReLU outputs that are varying. Then, a neural network function (denoted as F(x; W)) can be rewritten
Fxx; W) = w. DE D6-1Wh-1... D.W',
(WiI (IT - ( -
(4)

---

where
(i, (1 ((eLUU(z)
0) if (i,, =1 if ((1, =
(5)
where I denotes an indicator function.
Note here that we ignore bias terms for simplicity. Based on (4), an important insight used in our approach is that by combining the ReLU function with weight matrix, we have the opportunity to tighten Lipschitz bound by considering K&W', a whole based on whether there are ReLU outputs stay at constant under perturbation. Importantly since D' depends UB, (4) only holds in a local region of æ, which leads to a local Lipschitz constant bound at input x:
(x) S [|W - 1iiT-------66-- -.."""1-
The following theorem states that the local Lipchitz bound calculated via (6) is always tighter than the global Lipchitz bound in Eq (2), for all inputs.
Theorem 1 (Tighter Lipchitz Bound), For any input x E IR" and L-layer ReLU neural network F(x; W). the local Lipehitz bound calculated via (6) in any neighborhood of x no larger than the global Lipchitz bound in Eq (2), i.e, Vx, Tooodt (x) S leglob-
The proof of Theorem leverages the following proposition.
Proposition 1. If column and/or row added to a matrix, then the matrix spectral norm (maximum singular value) will be no less than the spectral norm of the original matrix. That is, given matrix E IR m, and y E Rm 2 E R", then
AA] (A)]
Tmax ([Alu)) 2 Jmaa (m Fmax (A),
Tmaa (A).
[A] [ The singular value of A' is defined as the square roots the
Proof of Proposition 1. Let A'
eigenvalues of AT A', where A A' A A4 2 AT A, that simply imply ||A']] = o maa (A') 2
Oman (A) = ||||]. Similar holds for A' [Aly]]
By Proposition 1, it is straightforward to show that | 1 S || since the left
hand side is the spectral norm of the reduced matrix, after removing corresponding rows/columns in W where the neuron output under local perturbation is constant. Therefore, the product of spectral norm of the reduced matrices is no larger than the product of the spectral norm of raw weight matrices, which leads to Va, (x) S Taglob-
3.3 Training for Tight Local Lipschitz
To encourage the network to learn which rows and columns need to be eliminated to make local Lipschitz bound tighter, we combine our local Lipschitz bound computation with certifiably robust training. This is different from existing works leveraging optimization tools to find local Lipschitz bound for a fixed network [10, 11]. By training with the proposed local Lipschitz bound, we can achieve good certified robustness on large neural networks.
More precisely. using our local Lipschitz bound, we can obtain the worst case logit =" that is used form robust loss for training: [( (x), where is the cross entropy loss function, (a,, v) is the image and label pair from the training datasets. A simple way to compute the worst logit 27 2, + V2eL for * y. 2y 2y (see [19]). Our approach is also compatible with tighter bounds on the worst case logit, such as the one used in BCP [20]. To give the network more capability to learn to tighten our proposed local Lipschitz bound, we propose the following approaches:
Allowing More Eliminated Rows via ReLUe The key to tighten our local Lipschitz bound is to delete rows and columns weight matrices that align with singular vectors corresponding to the largest singular value. To encourage more rows and columns to be deleted, we need to have more ReLU outputs to at constant under perturbation. Standard ReL.U only lower bounded by zero, but is not upper bounded. If we can set an "upper bound" of ReLU output, have more neurons
5

---

have fixed outputs at this upper bound. An upper bounded ReLU unit called ReLU6 is proposed in [29], where the maximum output is set constant 6. Different from ReLU6 that sets a constant maximum output threshold, we make the threshold to be a learnable parameter. We name the new type of activation function ReLUU, which is defined as:
0,
if 2 <=
RcLU0 0,)
=
Z4t 0,,
if < 2 < 0:
(8)
if 2; >= 02
where 0g a learnable upper bound of the ReL.U output. Similar to (3), the indicator matrices for the varying outputs of ReLU0 are
(i, = {
if fB > 0 and LBI < 8
(9)
otherwise
Depending on the ReLUA activation status, the output of ReLU@ neural network is,
F(x; W. 0) W=(Dk--wb-1... ... (D,W" x + D)).... ..... Dz-1),
(10)
where D/ denotes the ReLU output fixed at the maximum output value,
0; if t =1 0 if (f,
(6, - {
iB 2 0 otherwise
(11)
The local Lipchitz bound is still calculated as (6). However, the bound can be potentially learned tighter because we encourage ReLU outputs be constant in both directions, and there could be less varying outputs in Eq (9) than in Eq (3).
Extension to non-ReLU activation functions Our local Lipschitz bound can be applied on non- ReLU activation functions. The key is to create constant output regions for the activation function and delete the corresponding rows or columns in the weight matrices. Since the MaxMin activation function [15] has been shown to outperform ReLU on certified robustness [4, 30), we take MaxMin as an example to explain how apply our local Lipschitz bound. Let 21 and 22 be two groups of the input, the output of MaxMin is max(x1, x2), min(x1, x2). To exploit local Lipschitz, we created a clipped version of MaxMin, similar to ReLU0. The output of the clipped MaxMin is (max(())))))))) 272),00 a),, mnax(min(( output in MaxMin and b is a learnable lower threshold for the min output in MaxMin. Box propagation rule through MaxMin is straightforward to derive,
22). b). where is a learnable upper threshold for the max
can get the box bound on each entry after MaxMin. If the lower bounds of the Max entries are bigger than the upper threshold a, or the upper bounds of the Min entries are smaller than the lower threshold b, we can delete the corresponding columns in the successive matrix (similar to the procedure for ReLU networks).
Encouraging Fixed Neurons via Sparsity Loss To encourage more rows and columns to be deleted in the weight matrices, We design a sparsity loss to regularize the neural network towards this goal. For ReLU neural network, assuming that the i-th entry of the feature map at layer / is bounded by LB. < o! < UB|, we hope the neural network can learn to make as many UB; to be smaller than zero and LB; to be larger than 0, without sacrificing too much of classification accuracy. For Max neural network, let LBmax be the lower bounds of the Max entries, and UB be the upper bounds of the Min entries. We hope the neural network can learn to make as many LBmax to be larger than the upper threshold and UB to be smaller than the lower threshold b. The sparsity losses for ReLU and MaxMin networks are as follows:
spppsiiyy = m0 UB!) + max(0. (0, 0, - -BB),,
MaMMMiin (0, UBmin - b) + mammaax... (0, -IB max
(12)
Finally, our full training procedure is presented in Algorithm 1.
Computational cost To obtain the local Lipschitz bound, we must perform power iterations to
compute the spectral norm of reduced weight matrices for every input and its feature maps at each layer. Compared to other methods that use optimization tools (e.g., SDP, MII.P) to bound local Lipschitz, our method is computationally efficient since only matrix vector multiplication is used.

---

Algorithm 1: Local Lipchitz based Certifiably Robust Training
Input:
Training data (x, y) ~ D, perturbation size e, number of iterations for power method n, a neural network with L layers.
repeat
Compute the box outer bound [LB', UB"] for layers 1 to L;
Compute indicator matrix Iv using Eq (9);
II Compute local Lipcthiz bound [(x) for every imput a using Eg (6)
for layer from I to I. do
II Power method Initialize w' with the updated u' from the previous training episode; for i < do
If layer conv: v Reonv / /oon/// -2)'l u 4- IV "covvT (W", Ru)/ 1 / If layer is linear:
convT(W' .[v)
1 W' / W 1T''l
+ Wi Re Tullll
end
If layer is conv: o (x) D² R.cov(WWs, 1
layer linear: of (x) < nt w
end
Compute the worst logits using our local Lipschitz bound:
Update model parameters based on some loss functions (e.g., Cross-entropy loss).
until training ends; return Parameters of robust neural network
During training, compared to methods that only uses global Lipschitz bound, the local Lipeshitz bound varies based the inputs. For global Lipschitz bound, a common practice is to keep track of the iterate vector u in power iteration, and use it to initialize the power iteration in the next training batch. With this initialization, only few number of iterations is performed during training (typically the number of iterations is between 1 to 10 [20, 4J). To extend the initialization strategy for u to need to keep track of the iterate vectors based every input and its feature maps for every layer. Fortunately, this vector only provides an initialization for power iteration so it does not need to be stored accurately, and can be stored using low precision tensors. Further extensions could use dimension reduction or compression methods to store these vectors, or learn a network along the way predict a good initializer for power iteration. An alternative approach is to random initialize u in every mini-batchh but we find that more power iterations need to be performed during training for this approach have comparable performance the using saved u.
compute local Lipschitz,
During evaluation, to minimize the extra computational cost, we can avoid bound computation for two types of inputs: inputs that can already be certified using global Lipschitz bound can be attacked by adversaries (e.g.. a 100-step PGD attack). In practice, this typically rules out more than 80% samples CIFAR- 10 or larger datasets, and greatly reduce computational cost required to compute local I Lipschitz constants. In Section 4 we will show more empirical results on this aspect.
4 Experiment
In this section, we first show our method achieves tighter Lipschitz bounds in neural networks. When combined with certifiable training algorithms such as BCP [20] and Gloro [4], as well as training algorithms using orthogonal convolution and MaxMin activation function [30], our method achieves both higher clean and certified accuracy.
We train with our method to certify robustness within & ball of radius 1.58 on MNIST [31] and 36/26/ 36/255 on CIFAR-10 [32] and Tmmy-ema on various network architectures.
Experiment setup
'nttps://ttt httpe/////iinmmmmeeeeett hww.kuapp.cco
7

---

We denote neural network architecture by the number of convolutional layers and the number of fully-connected layers. For instance, 6C2F indicates that there are convolution layers and 2 fully- connected layers in the neural network. Networks have ReI.U activation function unless mentioned otherwise. For more details and hyper-parameter training, please refer to Appendix C. Our code is available at https: / thub. com/ y fiyhuncanddd /ocpd//ollllaooo pscch sechitz..
Tighter Lipschitz bound We compared the training process of our method and BCP [20] in Figure 2 (a-c). During training, our method uses local Lipschitz bound while BCP uses global Lipschitz bound for robust loss. We also tracked the global Lipschitz bound during our training and the average local Lipschitz bound (computed by our method) during BCP training for comparison. We can see from Figure (a) that our local Lipschitz bound is always tighter the global Lipschitz bound. Furthermore, it is crucial to incorporate our bound in training to enable the network to learn to tighten the bound. We can see that if we directly apply our method to BCP trained network after training, the local Lipschitz bound has much less improvement over global Lipschitz bound. In addition, tighter local Lipschitz bound by our method allows the neural networks to have larger global Lipschitz bound in the beginning of training. This potentially provides larger model capacity and eases the training in the early stage. As a consequence, we see a large improvement of both clean loss (Figure 2 (b)) and also robust loss (Figure (c)) throughout the training.
Sparsity of varying ReLU outputs We examine our 6C2F model trained on CIFAR-10 and report the proportion of varying (non-constant) ReLU outputs at all layers except the last colnecconee layer (Figure 3). We compared the proportion with that of a standard CNN (trained with only cross entropy loss unperturbed inputs) and robust CNN trained by BCP. As we can the standard neural networks has the most varying ReLU neurons, indicating that dense varying ReLU outputs may provide larger model capacity for clean accuracy but reduce robustness. Our method has more varying ReLU outputs than BCP, while achieving righter local Lipschitz bound than BCP. This indicates that our training method encourages the neural network to learn delete rows and columns that contribute most to local Lipsehitz constant during training, while keeping ReL.S for other rows or columns varying to obtain better natural accuracy.
a)
b)
Oura (Glubar)
145
Ouns (Loral)
claan Loo
1.5
BCP (Local)
BCP (GWbb))
Traning Clan
50
Traiiin
20-
100
0.0
1x
(5)
1/
140
15
104
0.6
50
100
150
150
Epochs
Figure 2: Certifiable training with our method and BCP on CIFAR-10. a) Global and average local
Lipschitz bound during training. Cross entropy loss b) on natural and c) the worst logits.
1200-
Meon=137
2003-
Retu Dirput
0.8
800-
0.6
600
Number
0.4
400-
Standard
200-
200
300
400
500
800 130
820
Index of Layer
Number of iterations
Figure 3: Proportion of ReLU neurons that vary (ReL.U outputs are not constants, see definition Section 3.2) under perturbation.
Figure 4: Histogram for the number of power iterations to ensure convergence for the second last linear layer of the 6C2F CIFAR-10 10 network.
Certified robustness Our method can used as a plug-in module in certifiable training algorithms that involves using & Lipschitz constant such as BCP [20] and Gloro [4]. We use Local-Lip-G and
8

---

Local-Lip-B to denote our method trained with the Gloro loss and BCP loss respectively (detailed formulation for each loss can be found in Appendix B). We compare the performance of our method against competitive baselines on both ReI.U neural networks [20, 4, 19, 12, 22, 33] and MaxMin neural networks [4, 30]. For each method, we report the clean accuracy (aceuracy on non-perturbed inputs), the PGD accuracy (accuracy on adversarial inputs generated by PGID attack [6]), and the certified accuracy (the proportion of inputs that can be correctly classified and certified within e-ball). For PGD attack, we use 100 steps with step size of e/4. In our experiments, we use box propagation (as done in BCP) to obtain the lower bound and upper bound of every neuron. With our tighter Lipchitz bound, we further improve clean, PGD, and certified accuracy upon BCP and Gloro, and achieve the state-of-the-an performance on certified robustness (Table 2). On CIFAR-10 10 with ReLU activation function, we improved certified accuracy from 51.3% (SOTA) to 54.3%. When MaxMin activation function is used, our local Lipschitz training approach also consistently improves clean, PGD and verified accuracy over baselines both CIFAR-10 and TinylmageNet datasets.
To demonstrate the effectiveness of incorporating our bound in training. we also use our local bound to directly compute certified accuracy for pretrained models using BCP. Our bound improves the certified accuracy of a pretrained BCP model from 51.3% (reported in Table 2) to 51.8%. The improvement is less than training with our bound (54.3% in Table 2). Therefore, it is crucial to incorporate our bound in training to gain non-trivial robustness improvements.
Initialization strategy for power method We used two initialization strategies for singular vectors u in power method during training. One option is to store u for all the inputs and feature maps and initialize u in the current training epoch with u from the previous epoch, which requires storage. The other option is to random initialize u. Table shows the performance of these two approaches on CIFAR-10 10 with the 6C2F architecture. The number of power iterations during training is listed in the bracket. Although random initialization memory-efficient, it needs more power iterations during training to achieve comparable performance compared to the approach of storing u. Too few iterations tend to cause inaccurate singular value and overfitting, resulting in lower certified accuracy.
Method
Clean (%)
PGD (%)
Certified (%)
Random init. (2 iters)
76.7
69.0
0.5
Random init. (5 iters)
73.7
66.8
46.0
Random init. iters)
72.0
65.8
51.6
Using saved (2 iters)
70.7
64.8
54.3
Table 1: Influence of initialization strategy used in power method. All numbers are accuracy of the 6C2F architecture on CIFAR-10.
Computational cost during evaluation time Since local Lipschitz bound needs to be evaluated for every input and global Lipschitz. bound does not depend on the input, our method involves additional computation cost during certification. Let utt) be the singular vector computed by power iteration at iteration f, we stop power iteration when |uu[t + 1) u(t)ll S 1c-3. To analyze the computational cost during evaluation time, plot the histogram of number of iterations for power method to converge for the second last layer in the 6C2F model in Figure 4. The average number of iterations for convergence is 137. The histograms for other layers are in Appendix C. To reduce the computational cost, we only need to compute local Lipschitz bound for samples that cannot be certified by global Lipschitz bound or cannot be attacked by adversaries. The proportion of those samples is (100% - PGD Err Global Certified Acc). For the 6C2F model on CIFAR- 10, the proportion of samples that can be certified using global Lipschitz bound is 51.0%, and the error under PGD attack is 35.2%. Hence we only need to evaluate local Lipschitz bounds on the remaining 13.8 13.8% samples, which greatly reduces the overhead of computing the local Lipschitz bounds.

---

Method
Model
Clean (%)
PGD (%)
Certified(%)
MNIST (e 1.58)
Standard
4C3F
99.0
45,4
0.0
LMT [19]
4C3F
86.5
53.6
40.5
CAP [21]
4C3F
88.1
44.5
CROWN-IBP [14]
4C3F
82.3
80.4
41.3
GloRo [4]
4C3F
92.9
68.9
50.1
Local-Lip-G (ours)
4C3F
96.3
78.2
55.8
BCP [20]
4C3F
92.4
65.8
47.9
Local- Lip- B (ours)
4C3F
93.0
66.7
48.7
CIFAR-10 (e
86/256)
Standard
4C3F
85.3
41.2
0.0
IBP [12]
4C3F
34.5
31.8
24.4
LMT [19]
4C3F
56.5
49.8
37.2
CAP [21]
4C3F
60.1
55.7
50.3
CROWN-IBP' [14]
4C3F
54.2
52.7
41.9
Rel.U-Stability [33]
4C3F
57.4
52.4
51.1
GloRo [4]
4C3F
73.2
66.3
49.0
Local-Lip-G (ours)
4C3F
75.7
68.6
49.7
BCP [20]
4C3F
64.4
59,4
50.0
Local-Lip-B (ours)
4C3F
70.1
64.2
53.5
Standard
6C2F
87.5
32.5
0.0
IBP [12]
6C2F
33.0
31.1
23.4
LMT [19]
6C2F
63.1
58.3
38.1
CAP [21]
6C2F
60.1
56.2
50,9
CROWN-IBP [14]
6C2F
53.7
52.2
41.9
GloRo [4]
6C2F
70.7
49.3
Local-Lip-G (ours)
6C2F
76.4
69.2
51.3
BCP [20]
6C2F
65.7
60,8
51.3
Local-Lip- (ours)
6C2F
70.7
64.8
54.3
GloRo MaxMin [4]
6C2F
77.0
69.2
58.4
Caylay MaxMin [30]
6C2F
75.3
67.7
59.2
Local-Lip-B MaxMin (ours)
6C2F
77.4
70.4
60.7
Imagennt
20/255)
Standard
7C1F
35.9
19.4
0.0
GloRo [4]
7C1F
31.3
28.2
13.2
Local-Lip-G (ours)
8C2F
37.4
34.2
13.2
BCP [20]
8C2F
28.7
26.6
20.0
Local-Lip-B (ours)
8C2F
30.8
28.4
20.7
Gloro MaxMin [4]
8C2F
35.5
32.3
22.4
Local-Lip-B MaxMin (ours)
8C2F
36.9
33.3
23.4
CROWN-IBP was originally designed for loo norm certified defense but its relcased
code also supports & training. use same hyperparamelers as foo training setting.
[33] was designed for foc norm with MIP verifier. We extend to the la norm setting and verify its robustness using the SOTA alpha-heta-CROWi verifier (see Section C.2).
Table 2: Comparison to other certified training algorithms. Best numbers are highlighted in bold.
Conclusion
In this work, we propose an efficient way to incorporate local Lipschitz bound for training certifiably robust neural networks. We classify the outputs of activation function as being constant varying under input perturbations and consider them separately. Specifically, we remove the redundant rows and columns corresponding to the constant activation outputs in the weight matrix to get a tighter local Lipschitz bound. We propose a learnable bounded activation and the use of a sparsity encouraging loss during training to assist the neural network to learn to tighten our local Lipschitz bound. Our method consistently outperforms of-te-of-the-ar Lipschitz based certified defend methods for & norm robustness. We no immediate negative socictal impact in the proposed approach.
10

---

Acknowledgements
Y. Huang is supported by DARPA LwLL grants. A. Anandkumar is supported in part by Bren endowed chair, DARPA LwLL grants, Microsoft, Google, Adobe faculty fellowships, and DE Logi grant. Huan Zhang is supported by funding from the Bosch Center for Artificial Intelligence.
References
[1] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283. PMLR, 2018.
[2] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usumier.
Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pages 854-863. PMLR, 2017.
[3] Haifeng Qian and Mark N Wegman. L2- L2-nonexpansive neural networks. arXiv preprint arXiv:1802.07886, 2018.
[4] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. arXiv preprint arXiv:2102.08452, 2021.
[5] Todd Huster, Cho- Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant as defense against adversarial examples. Joint European Conference on Machine Learning and Knowledge Discovery in Dalabases, pages 16-29. Springer, 2018.
[6] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 760836 2017.
[7] Matthias Hein and Maksym Andriushchenko, Formal guarantees on the robustness of a classifier against adversarial manipulation. Advances Neural Information Processing Systems, 2017.
[8] Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5757-5764, 2019.
[9] Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pages 97-117. Springer, 2017.
[10] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. arXiv preprint arXiv:1906.044 04893, 2019.
[11] Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. arXiv preprint arXiv:2003.0/2199 2020.
[12] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 12715, 2018.
[13] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pages 3575 3575-3583,220 2018
[14] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh, Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2020.
[15] Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference Machine Learning, pages 291-301. PMLR, 2019.

---

[16] Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. arXiv preprint arXiv.1805./065, 2018.
[17] Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning. pages
PMLR, 2018.
[18] Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 2013.
[19] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certifi- cation of perturbation invariance for deep neural networks. arXiv preprint 1rXivv/802.0044 2018.
[20] Sungyoon Lee, Jaewook Lee, and Saerom Park. Lipschitz-certtfffbll training with a tight outer bound. Advances in Neural Information Processing Systems, 33, 2020.
[21] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, 2018
[22] Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In NeurlPS, 2018.
[23] Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training via better initialization and shorter warmup. Advances Neural Information Processing Systems (NeurIPS), 2021.
[24] Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In ICML, 2019.
[25] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, pages 9464 9474, 2019.
[26] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEEE, 2019.
[27] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pages -1289-11300, 2019.
[28] Huan Zhang, Tsu Weng, Pin-Yu Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neu- ral network robustness certification with general activation functions. Advances in Neural Information Processing Systems, 2018.
[29] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv:1704.04861, 2017.
[30] Asher Trockman and Zico Kolter, Orthogonalizing convolutional layers with the cayley transform. arXiv preprint arXiv:2104.07167 2021.
[31] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database, 2010.
[32] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[33] Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Train- ing for faster adversarial robustness verification via inducing relu stability. arXiv preprint arXiv:1801 03008, 2018.
[34] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11Xiv.141..6980, 2014.
12

---

[35] Kaidi Xu, Huan Zhang. Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and Complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. In International Conference on Learning Representations, 2021.
[36] 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 complete and incomplete neural network verification. arXiv preprint arXiv:2103.06622 2021.
[37] Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (vnn-comp 2021): Summary and results. arXiv preprint arXiv:2109.00498, 2021.
[38] Hongyang Zhang, Yaodong Yu, Jiantao Jíao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pages 1472-7482) PMLR, 2019.
13


Reviews:
[{"review_id": "xyJTJP5uJjN", "reviewer": "Reviewer_Miuz", "summary": "This paper proposes a new method for certified robustness that tightly bounds the local Lipschitz constants for models by exploiting zero-activation of ReLU. For each data point, the proposed method first calculates the positions where feature maps become zero by ReLU. Next, since the row vector of the weight matrix before the ReLU outputs zero does not affect the output, the proposed method eliminates such row vectors and computes the Lipschitz constants of the modified weight matrix. Experiments demonstrate that the proposed method outperforms previous methods in terms of clean accuracy, robust accuracy against PGD, and certified robust accuracy.\n", "questions": "", "limitations": "", "rating": 5, "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": "The proposed approach is moderately interesting and its idea might inspire researchers of adversarial robustness. However, I think the technical contributions are not high and experimental results seem to be not very strong. Therefore, I tend to vote to reject.\n\n- Strength   \n   1. The idea that focuses on zero activations for ReLU is interesting. Ignoring weight vectors corresponding to these zero activations can contribute to more robust models or a better trade-off between clean accuracy and robustness.\n\n   1. Experiments demonstrate the proposed method outperforms other methods. These baseline methods seem to be sufficiently new and reasonable though I do not have very expertise in this research area.\n\n   1. This paper is well written and easy to follow.\n\n\n- Weakness  \n  1. Experimental results are not very strong.\nIn Table 1, the proposed method outperforms other methods. However, accuracies for GloRo in Table 1  are A few percentage points less than those reported in the original paper [4]. In addition, reported accuracies in [4] are higher than those of the proposed method in Table 1. I would like to know why these results are different from the original results.\n\n  1. Theoretical results are trivial, and the technical contribution is not very high. In fact, this paper does not provide proof of Theorem 1 because this result is obvious. Proposition 1 is also a trivial result, which is broadly known results in the matrix computation. \nThe techniques that constitute the proposed method are not very new. For example, the proposed method naively uses previous methods for computing upper and lower bounds of pre-activations for certifying zero-activation of ReLUs, and the proposed method exploits a power method to compute Lipschitz constants.\n\n\n- Minor comments  \n  1. The proposed method is based on the combination of ReLUs and linear operations. Can you use the proposed method with batch normalization? In addition, can you use the proposed method in the ResNet? [15] uses Wide ResNet for evaluation of BCP in , but this paper does not.\n  1. Are matrices D in equations (5) and (11) correct? If they are correct, I think the computation of each layer becomes $z=ReLU(Wx)\\odot Wx$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "wmnfVBrCjYn", "reviewer": "Reviewer_u352", "summary": "This paper provides a trainable local Lipschitz upper-bound for a neural network that is tighter than the global Lipschitz upper-bound computed via multiplying the Lipschitz constant of each individual layer. By making use of the interaction between the weight matrices and the piece-wise linear activation functions, the authors demonstrate that the global Lipschitz bound could be improved when the activation functions are constant locally. In addition, the authors proposed a variant of ReLU that is clipped at a certain upper threshold to increase the constant region to help achieve a tighter Lipschitz upper-bound. Empirically, the authors showed that optimizing the local Lipschitz bound, along with using the modified ReLU, improved the certified robust performance of existing algorithms on several standard image classification tasks.", "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": "## Strengths\n*Originality* - The proposed approach is elegant and seems to be easy to implement in existing neural network architectures.\n\n*Quality* - Theorem statements all make intuitive sense and are likely to be sound (though I admittedly did not carefully check all the proofs). \n\n*Clarity* - The paper is well-written and easy to follow. \n\n## Weaknesses\n*Significance* \n1. Several important baselines are missing from the experimental comparisons (e.g., [1, 4]). Also, why is the performance of GloRo reported in the current paper (Table 1, 49.0% certified accuracy for CIFAR-10) much weaker than the performance reported in the original GloRo paper? (Table 1, 58.4% certified accuracy for CIFAR10) [2].\n2. The proposed approach seems to successfully improve the performance of ReLU(-like) networks, but the best reported robust accuracy is still worse than existing Lipschitz-constrained models. For example, the best model in the current paper has a certified accuracy of 54.3% on CIFAR-10 benchmark while GloRo has already achieved 58.4% certified accuracy for the same benchmark.\n\nOverall, I think this paper presents an interesting approach that tightens the local Lipschitz bound, but the current empirical evaluations seem to suggest that the proposed approach has a weaker performance than some baselines in the literature. I wouldn't recommend acceptance before more thorough experiments and comparisons are made with these baselines.\n\n(See the limitation section for the references)\n\n***** Edit *****\nBased on the new results on MaxMin activation functions, I have decided to raise my score to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One major limitation of the work is that it would only tighten the Lipschitz constant bound when the activation functions have constant region (e.g., the output of the activation function is constant with a range of input). This can be an issue nowadays because it precludes the usage of activations without constant regions (e.g., MaxMin/OPLU [3, 5]). In particular, MaxMin has adapted in several recent works in Lipschitz-constrained neural networks and achieved better certified robust accuracy compared against ReLU (e.g., [1, 2, 4]). \n\n[1] Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=Pbj8H_jEHYv. \n\n[2] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6212–6222. PMLR, 18–24 Jul 2021. URL http://proceedings.mlr.press/v139/leino21a.html. \n\n[3] Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 291–301. PMLR, 09–15 Jun 2019. URL http://proceedings.mlr.press/v97/anil19a.html. \n\n[4] Qiyang  Li,  Saminul  Haque,  Cem  Anil,  James  Lucas,  Roger  B  Grosse,  and  Joern-Henrik  Jacobsen. Preventing  gradient  attenuation  in  lipschitz  constrained  convolutional  networks. In  H.  Wallach,   H.  Larochelle,   A.  Beygelzimer,   F.  d'Alch ́e-Buc,   E.  Fox,   and  R.  Garnett,   editors, Advances  in  Neural  Information  Processing  Systems,   volume  32.  Curran Associates,   Inc.,   2019. URL https://proceedings.neurips.cc/paper/2019/file/1ce3e6e3f452828e23a0c94572bef9d9-Paper.pdf.\n\n[5] Artem Chernodub and Dimitri Nowicki. Norm-preserving orthogonal permutation linear unit activation functions (oplu). arXiv preprint arXiv:1604.02313, 2016.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "qiTRuEcb4Hc", "reviewer": "Reviewer_jfER", "summary": "Summary: \nThe authors propose a training scheme that regularizes against the worst-case logit, as computed by a novel technique for bounding the local Lipschitz constant of a ReLU network. ", "questions": "", "limitations": "", "rating": 5, "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": "Originality: \nThe key novelty in this approach is to use box constraints to determine local information about the stability of ReLU neurons to yield a differentiable upper bound for the L2-Lipschitz constant. Several theoretical results are presented, though it is unclear if the authors' intended them to be taken as novel results: in particular, Theorem and Proposition 1 are known in the literature and can be explained as a simple application of Cauchy's interlacing theorem.  The application of a local Lipschitz upper bound to generate worst-case logits to be used is training is reminiscent of (and should be compared to) other differentiable techniques to generate worst-case logits for use in training, such as DiffAI. Similarly, the hinge-loss for IBP and the notion of regularizing to enforce ReLU stability is similar to the approach in \"Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability\" by Xiao et al and this should be cited/compared against. \n\nQuality: \nThe proposed Lipschitz estimation technique is sound, efficient, and differentiable; and while the theoretical underpinnings of removing rows/columns from matrices reducing their spectral radii is known, to the best of my knowledge, it had not been used in such a fashion to generate a Lipschitz upper bound. My primary complaint with this paper is the lack of thoroughness and comparisons in the experimental section. With respect to training a network to have a low Lipschitz constant and/or be adversarially robust, non-certifiable training methods such as AT/TRADES/etc should be considered and compared against (as these are known to regularize the Lipschitz constant of neural networks and provide robustness), as well as the other non-Lipschitz-based certifiable training methods. With respect to the proposed hinge loss for enforcing ReLU stability, the techniques proposed in Xiao et al (see above) should be considered. With respect to this Lipschitz estimate as a certification procedure, comparisons should be made against other techniques designed to certify a fixed, post-training, network (see the VNN challenge). \n\nClarity: \nWhile the paper was fairly easy to read follow, and explained the key concepts well, this paper could benefit from better organization. Separating and framing this approach as primarily a Lipschitz estimator, that can then be used during training to provide robustness, or alternatively that can be used after training to certify robustness would help clarify the novelties. The ReluTheta activation could then be presented as a means to encourage ReLU stability and thereby tighten the Lipschitz bound, in an orthogonal direction to other such relu-stability techniques. \n\nSignificance: Training neural networks that are certifiably robust against adversarial examples is a very important problem that has received significant attention from the community. Provable guarantees leveraging (local) Lipschitz continuity are a promising approach, however it is not clear to me that the proposed approach in this work advances the state of the art in a demonstrable fashion. \n\nOverall: \nThis approach is novel and promising. However it requires more thorough experimentation and comparison to other Lipschitz--approximation/robustness-certification/relu-stability techniques to be worthy of acceptance, in my opinion. \n\n**** Edited score after reading reviewer rebuttals from 3->5 *********", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitations were discussed, and negative societal impacts were not thoroughly considered. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mqxCTFR6_3E", "reviewer": "Reviewer_uE4r", "summary": "This paper proposes using local Lipschitz bound to obtain certified robust neural networks. The use of local Lipschitz constant strictly results in a provable tighter bound than the commonly used global Lipschitz bound. To incorporate the proposed certification method into training, the authors further proposed a modified ReLU function with a learnable upper threshold, and hinge loss to encourage the pre-activation states to be constant past ReLU function.\n\nThe proposed method is sound, numerical experiments show promising improvement over the existing certified robust training methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe use of local Lipschitz constant as certified upper bound for training robust neural networks is a novel contribution.\n\nQuality:\n\nThe submission is technically sound. The main claim is supported by the numerical experiments. The use of local Lipschitz constant is less aggressive on the limited network capacity, which results in better certified robustness. \n\nClarity:\n\nI believe that the submission needs more spelling checking. Especially in Sec 3.2 which is the main sub-section. I think equation (4) does not make clear sense based on the definitions of those notations.\n\nSignificance:\n\nCertified robustness training is an important direction in adversarial robustness researches. Although the proposal is simple, its effectiveness on the improvement can be appreciated by future works.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the computational cost of the proposed training method. I think the proposed method is practical since the extra computational overhead is not very heavy.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ixQGnB-YW98", "reviewer": "Reviewer_umTB", "summary": "Per data-example, a local Lipschitz bound on the neural network output is computed and then used to certify robustness. This bound is made tighter by exploiting invariances of the ReLU activations throughout the network under small perturbations around the given data point. The paper further increases invariances by clipping ReLU and training the clipping threshold.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ Simple and computationally efficient method of obtaining tight local Lipschitz bound makes this algorithm practical for usage in training\n+ The Lipschitz bound improvement relies only on ReLU outputs being constant in some region. This makes the method plug-and-play and also applicable to most modern neural networks.\n+ Experimental results show good improvements over baselines in terms of the bound, training loss, and final accuracy\n\nWeaknesses / suggestions:\n- Computational cost is explored in terms of number of iterations of the power method. A more appropriate metric would be total number of floating point operations or compute time. A comparison along these metrics can then be made with the other methods that use global Lipschitz bounds (such as GloRo)\n- The clipped version of ReLU can make it harder for the network to learn since there are more regions with zero-gradients. Does this happen? Are there ways this was overcome (e.g. through reducing the magnitude of the initialized weights?). This could be explored further to explore the strengths and limitations of the ReLU_theta approach\n- For local Lipschitz bound, the authors split the expression for F(x, W) in Eqn. 4 into a product of matrices, and then take the spectral norm of each. However, a direct spectral norm of the entire matrix that premultiplies x can be considered. This would provide an even tighter local Lipschitz bound due to the sub-multiplicative nature of spectral norm. While this method is likely to incur a large computational penalty (due to matrix-matrix multiplications), it could be tried on smaller problems (e.g. MNIST) and it would be interesting to know how much better the local Lipschitz bound can become and its eventual effect on certified accuracy. An alternative is to consider a different grouping of the matrices.\n\nTypos:\n- Abstract: “training algorithms can certified robustness” (grammar)\n- Line 147: I_c and I_v definition swapped?\n- Eqn 4 should have I_v instead of D_v. (since Wx already equals z_i, and so multiplying with D_v would produce z_i^2, which should not be there. \n- Eqn. 10 also seems to have a similar error as above", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No immediate societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aEBuPN-BMsu", "reviewer": "Reviewer_UGUy", "summary": "This paper studies certified robustness from the perspective of computing Lipschitzness bounds. Prior work compute global bounds on the Lipschitz constant of the network; this paper takes an alternative approach which computes local Lipschitz bounds around a specific input. These local Lipschitz bounds are based on interval bounds for the hidden layers on each data point, and computing a tighter Lipschitz constant based on eliminating rows/columns of the weight matrices when the interval bounds indicate that a neuron is inactive. \n\nTo train certifiably robust models, the worst-case loss is optimized based on these Lipschitz bounds. There are several other ingredients for the proposed method: a modified ReLU activation which truncates when the output is a large positive value, and a sparsity-inducing regularization meant to limit the number of neurons where the upper and lower activation bounds differ. The authors compare certified robustness w.r.t. $\\ell_2$ perturbations against other Lipschitzness-based baselines and demonstrate improvements. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes a certified robustness method based on nice and novel insights about training the local Lipschitz constants rather than the global constants. The method produces empirical improvements over existing methods; however, there is still some uncertainty about the effects of different components of the proposed methods, which aren't adequately addressed in the ablations.  (More details below.) For this reason, I'm recommending weak accept, but am willing to change my score based on the authors' response.\n\nOriginality: the idea of regularizing local Lipschitzness is novel and a nice way to improve over prior work. \n\nQuality: the paper appears to be technically sound, but it would be helpful to have more experiments which isolate the effects of each component of the proposed method (see below).\n\nClarity: the paper is generally well-written, though there are some portions where clarification would help (see questions below.)\n\nSignificance: setting aside the above concerns, this paper makes nice contributions to certified robustness.\n\nMore details about questions/ concerns:\n- First, regarding the different components of the objective -- it would be nice to see how much of the improvement is due to the sparsity-inducing loss and how much is due to regularizing the local Lipschitz constant. Table 5 in the supplementary material does perform an ablation on this, but when $\\lambda = 0$ (no sparsity loss), the reported numbers are actually worse than the reported numbers for BCP in Table 1. This makes me concerned that a lot of the improvement might actually come from including the sparsity loss, not regularizing the local Lipschitz constant. \n\nAnother concern is how much the change in architecture accounts for the differences in performance -- it would be nice to see an ablation study on the impact of the modified ReLU activation. \n\n-- It's also unclear how exactly the local lipschitz constant is optimized. E.g. is the power iteration unrolled, and backprop is performed through the power iterations?\n\nSome other questions/clarifications:\n-- The definition of D_V in (5) doesn't appear completely right -- shouldn't it be a binary diagonal matrix? \n-- For equation (6), would it also be possible to bound the Lipschitz constant by $\\|\\prod_l I^l W^l I^{l - 1} \\|$ instead of the product of the norms? This seems like it could lead to a tighter bound. \n\n=======================================================================\nUpdate after reading the author responses and other reviews. While I appreciate and thank the authors for their thorough response to my questions, I think this paper remains borderline, especially given some of the concerns raised by other reviewers. Thus, I'm keeping my score the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agreed that the paper provides interesting results in bounding the (local) Lipschitz constant of NNs with piece-wise linear activation functions. The reviewers had a number of concerns which were mostly resolved after the authors' responses. I would strongly recommend that the authors incorporate all the comments mentioned in the reviews in their updated version (e.g. the additional experimental results, comparison with prior work, etc).  
Decision: Accept (Poster)