Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization
Authors: Mahyar Fazlyab
Taha Entesari
Aniket Roy
Rama Chellappa
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep Learning
Adversarial Robustness
Certified Radius
Lipschitz Constants
TL;DR: A new training procedure to improve the robustness of deep classifiers using Lipschitz regularization and margin maximization.

Abstract: To improve the robustness of deep classifiers against adversarial perturbations, many approaches have been proposed, such as designing new architectures with better robustness properties (e.g., Lipschitz-capped networks), or modifying the training process itself (e.g., min-max optimization, constrained learning, or regularization). These approaches, however, might not be effective at increasing the margin in the input (feature) space. In this paper, we propose a differentiable regularizer that is a lower bound on the distance of the data points to the classification boundary. The proposed regularizer requires knowledge of the model's Lipschitz constant along certain directions. To this end, we develop a scalable method for calculating guaranteed differentiable upper bounds on the Lipschitz constant of neural networks accurately and efficiently.  The relative accuracy of the bounds prevents excessive regularization and allows for more direct manipulation of the decision boundary. Furthermore, our Lipschitz bounding algorithm exploits the monotonicity and Lipschitz continuity of the activation layers, and the resulting bounds can be used to design new layers with controllable bounds on their Lipschitz constant. Experiments on the MNIST, CIFAR-10, and Tiny-ImageNet data sets verify that our proposed algorithm obtains competitively improved results compared to the state-of-the-art.

Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization
Mahyar Fazlyab', Taha Entesari; Aniket Roy, Rama Chellappa
Department of Electrical and Computer Engineering Johns Hopkins University (mahyarfazlyab, tentesal, aroy28, Sthella4@@jhu edu edu
Abstract
To improve the robustness of deep classifiers against adversarial perturbations, many approaches have been proposed, such designing new architectures with better robustness properties (e.g.. Lipschitz- networks). or modifying the training process itself (e.g., min-max optimization, constrained learning, or regu- larization). These approaches, however, might not be effective at increasing the margin in the input (feature) space. In this paper, we propose differentiable regu- larizer that is lower bound on the distance of the data points to the classification boundary. The proposed regularizer requires knowledge of the model's Lipschitz constant along certain directions. To this end, we develop scalable method for calculating guaranteed differentiable upper bounds on the Lipschitz constant neural networks accurately and efficiently. The relative accuracy of the bounds prevents excessive regularization and allows for more direct manipulation of the decision boundary. Furthermore, monotonicity and Lipschitz continuity of the activation layers, and the resulting bounds be used to design new layers with controllable bounds on their Lips- chitz constant. Experiments on the MNIST, CIFAR-10 10, and Tiny-ImageNet data sets verify that our proposed algorithm obtains competitively improved results compared to the state-of-the-art.
Lipschitz bounding algorithm exploits the
Introduction
Motivated by the vulnerability of deep neural networks adversarial attacks [T] i.e., impercep- tible perturbations that can drastically change model's prediction, researchers and practitioners have proposed various approaches to enhance the robustness of deep neural networks, including adversarial training (2 regularization (5) (). constrained learning (7), randomized smoothing (8-
10), relaxation-based defenses [11, [2], and model ensembles [3 14]. These approaches modify
the model architecture, the optimization procedure (loss function and algorithm). the inference mechanism, or the dataset itself [15] enhance accuracy both natural and adversarial examples.
However, most of these methods typically do not directly operate on input margins and rather target the output margin its surrogates. For example, is established property that deep models trained with the eross-entropy loss, which is a surrogate for maximizing the output margin (see Appendix A.2 are prone adversarial attacks [T]. From this perspective, it is critical to design regularized loss functions that can explicitly and effectively target the margin the input space [16]
Equall contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our Contribution (1) Using first principles, we design a novel regularized loss function for training adversarially robust deep classifiers. We design a differentiable regularizer, using the Lipschitz constants of the logit differences, that is a lower bound on the input margin. We empirically show that this regularizer promotes larger margins the input space. (2) We develop a scalable method for calculating guaranteed analytic and differentiable upper bounds on the Lipschitz constant of deep networks accurately and efficiently. Our method, called LipLT, hinges on the idea of Loop Transformation on the nonlinearities, which allows us to exploit the monotonicity and Lipschitz continuity of activations functions effectively. We prove that the resulting upper bound is better than the product of the Lipschitz constants of all layers (the so-called naive bound), and in practice, it is significantly better. Furthermore, our Lipschitz bounding algorithm can be used to design new layers with controllable bound on their Lipschitz constant. (3) We integrate our Lipschitz estimation algorithm within the proposed training loss to develop a robust training algorithm that eliminates the need for any inner-loop optimization subroutine. We utilize the recurring structure of the calculations that enable parallelized implementation on GPUs. When integrated into training, the relative accuracy of the bounds prevents excessive regularization and allows for more direct manipulation of the decision boundary.
Experiments on the MNIST, CIFAR-10, and Tiny-ImageNet data sets verify that our proposed algorithm obtains competitively improved results compared to the sfat-oofthe--an Code available on https//gtthbb.comoolll///MMMLLL
1.1 Related Work
In the interest of space, we only review the most relevant literature and defer the comprehensive version to the supplementary materials.
Enhancing Robustness via Optimization The most well-known approach in adversarial de- fenses is perhaps adversarial training (AT) (4) and its certified variants [11 19 23), which involves minimizing a worst-case loss (or its approximation) using uniformly- perturbations to the training data. Since these approaches might hurt accuracy on non-adversarial examples, several regularization-baat based methods have been proposed to trade off adversarial robustness against natural accuracy (5| 6 24 25). Intuitively, these approaches aim control the variations of the model close to the decision boundary or around the training data points. In general, the main challenge to formulate computationally efficient differentiable regularizers that can directly increase the margin of the classifier. Of notable recent work in this direction is [8]. in which the authors design regularizer that directly increases the margin in the input space and prioritizes more vulnerable points by leveraging the dynamics of the decision boundary during training. Our loss function also takes advantage of this approach, but rather than using an iterative algorithm to compute the margin, we use Lipschitz continuity arguments to find closed-form differentiable lower bounds on the margin.
Robustness and Lipschitz Regularity To obtain efficient and scalable certificates of robustness one can bound or control the global Lipschitz constant of the model. To train robust networks, the global Lipschitz bound is typically computed as the product of the spectral norm of linear layers (the naive bound), which provides computationally efficient but overly conservative certificates (5 19
26). If these bounds are localized (e.g., in neighborhood of each training data point), conservatism
can be mitigated at the expense of losing computational efficiency 20 27). However, it is not clear
if this approach provides any advantages over other local bounding schemes (28) 29] that can be more accurate with comparable complexity. Hence, for training purposes, it is highly desirable to have global but less conservative differentiable Lipschitz bounds. Of notable work in this direction is the semidefinite programming (SDP) approach of (30) (as well as its local version (3T) to provide accurate numerical bounds, which has also been leveraged in training Low-Lipschitz networks (32). However, these SDP-based approaches are restricted to small-scale models. In comparison, LipLT less accurate than LiPSDP but can scale to significantly larger models and larger input dimensions. Compared to the naive method, LipL.T is significantly more accurate but has a comparable practical complexity thanks to a specialized GPU implementation that exploits the recursive nature of the algorithm.
2

---

Lipschitz Layers Another approach to improving robustness is to design new layers with control- lable Lipschitz constant. Various methods have been proposed design the so-called I-Lipschitz networks 7 (7). Inspired by the LipSDP framework of [30], the recent work (38] designs 1-L.ipschitz layers that generalize many of the aforementioned I-L.isschitz designs. However, their proposed approach is currently not applicable to multi-layer networks. In [39], the authors propose
a reparameterization that directly satisfies the SDP constraint of LipSDP, but the proposed method
cannot handle skip connections. [21] introduces &oo distance neurons that are I-Lipschitz and provide inherent robustness against &oo perturbations.
1.2 Preliminaries and Notation
The log-sum sum-exp function is defined as LSE(x) log Ei= exp(x:)). For any O, the per- spective (40) of the log-sum-exp function satisfies the inequalities max; (z:) < LSE S (x,, + log(n). We denote the cross-entropy loss by C'E(q. p) = - Σ Pae log(gk). where p. q E RKK are on the probability simplex. For an integer E {1, ... K}. we define uy E R as the y-th standard unit vector. For vector a E RK we have ||a||p (Σ = la P)///)/ Additionally, we have ||a ||p = ||a|la, where 1/p + 1/4 1. When p = 1, it is understood that q co. For matrix A E Rmxn, ||A]| denotes a matrix norm of A. In this paper we focus on ||A]|2 = max (A), i... the spectral norm of the matrix A. We. however, note that except for the implementation notes regarding the power iteration, the rest of the Lipschitz estimation algorithm is valid in any other matrix norm well. We denote the indicator function of the event E 1g, where 1g outputs 1 if the event E' is realized and otherwise.
2 Certified Radius Maximization (CRM)
where f(x;0) = softmax(=(1; 8)) is the vector of class probabilities, and 2(x; 0) is deep network. If data point classified correctly as y E f1.... K}. then the logit margin 7 (2(x; 0), y), the difference between the largest and second-larges, logit, is >=2(2((22)))))>)> 0). y) 2, (2; 0) maxj 2x; 0).
Consider a K-class deep classifier C(z; = arg max
Several existing loss functions for training classifiers are differentiable surrogates for maximizing the logit margin, including the cross entropy, and its combination with label smoothing (see Appendix for more details). However, maximizing the logit margin, or surrogates, does not necessarily increase the margin in the input space. This can happen, for example, when the model has rapid variations close to the decision boundary. Thus, we need a regularizer targeted for maximizing the input margin.
Regularization Based on Certified Radius For a correctly-elassiiies data with label y. the distance of x to the decision boundary can be calculated by solving the optimization problem [18).
R(x, 0) = inf || æ|l subject to (2(2; 0), v) = O,
(1)
where the constraint enforces à to be on the decision boundary. To ensure a large margin in the input space, we must, in principle, maximize the radius R(x, y: 0) of all correctly classified data points. To achieve this goal, we can add a regularizer that penalizes small input margins.
min E El 6
+ (E (1((())))) R(x y; 8))]
(2)
where À > 0 is the regularization constant and g: R R is decreasing function promote larger certified radii. See appendix A.2 for more discussion on the properties of g.
To optimize 2 we must compute and differentiate through R(x, y; 0). For Eo norm and ReLU activations, we can reformulate [T) as a mixed-integer linear program by using binary representation
We note that we can replace the equality constraint with the inequality constraint ((((2;)) v) S 0 and get the same result.
3

---

of the activation functions. However, it is not affordable to solve this optimization problem during training. Hence, we must resort to computing lower bounds R(z, y: instead.
By replacing the logit margin with its soft lower bound in the constraint of ①
we obtain a lower
bound on R(x, y; 0),
R(x, y; min
|| Ar--fl =1ll
s.t. By 2z(2;
log
cl2y(1:0) S 0. 5テリ
To solve this non-convex problem, the authors of (18) adapt the successive linearization algorithm of 4I]. which in turn does not provide provable lower bound. To avoid this iterative algorithm and to provide sound lower bounds, we propose to use Lipschitz continuity arguments.
Lipschitz-Basse Based Surrogates for Certified Radius Suppose add norm- comm-buuneed perturbation to a data point æ that classified correctly as y. For the label of x + 8 to not change, we must enforce
Azy + 5) zy(x 0:0) 2(x 0:0) 4i y.
Suppose the logit difference + (z) is Lipschitz continuous with constant Lyt (in p norm), implying (2 6)0) Zzy (z) S Lyrllö| Vx, 8. Then we can write
( + 6;0) 2 A (x;; 0) Lyr|1ö|l Vi Hy..
The right-hand side remaining positive for * y is sufficient condition for the correct classifica- tion of x + as This sufficient condition yields lower bound on R(a, y; 0) as follows,
Zy (x; 0)
(a;;;; 0) I ((E,,300)
R(x, y: 0) == min
(4)
Lyg
This lower bound is the pointwise minimum of logit differences normalized by their Lipschitz constants. This lower bound is not differentiable everywhere, but similar to the logit margin, we propose smooth underapproximation of the min operator using scaled LSSE:
log( Σ exp(p By (a (2; 0) <x; 0) ))-
R Reoft (x, v;
Lyg
In addition to differentiability. another advantage of using this soft lower bound is that as opposed to R(x, y; f), which involves only two logits, the soft lower bound R.oft (x, 0) includes all the logits, and hence, makes more effective use of information.
Proposition 1 We have the following relationship between Reoft (xx 0) defined R(x, y: f)) defined in
(
and
Roo (x,y;0) R(x, 12oft( (0, log( K 1)
In summary, we use the following loss function train classifier,
min
v)] - AB (atp::/:ppplltttteeo:ooosoooppo/ (z, v 0))]
(6)
The first and the second terms are differentiable surrogates to the negative logit margin, and the input margin, respectively. For example, as we show in Appendix(A.2 the negative cross-entropy loss a dif- ferentiable lower bound the logit margin, i.e.,
choose (=; 0) (CF(s(a;; (), uy).
It now remains to estimate the Lys' 's (the Lipschitz constants of x + Azy (x)) that are needed to compute the second term in the loss function. While any guaranteed upper bound on Lys would suffice to preserve the lower bound property in 44 more accurate upper bound prevents excessive regularization and allows for more direct manipulation of the decision boundary. To achieve this goal, propose new method which we will discuss next.

---

3 Scalable Estimation of Lipschitz Constants via Loop Transfor- mation (LipLT)
In this section, we propose a general-purposs algorithm for computing a differentiable upper bound on the Lipschitz constant of deep neural networks, which is also of independent interest. For simplicity in the exposition, we first consider single hidden layer neural networks of the form h(x) = W o ((Wx), where W w have compatible dimensions, and the bias terms are ignored without loss of generality, The activation layers & are of the form ((=) (fp(z)), , <0(2, )) E R where y: IR + +R the activation function, which we assume to be monotone and Lipschitz continuous, implying S (p(x)) - (z()))((x= - x') 3 Va + x' for some 0 I < B < xc [30] 42). In [30]. the authors propose an SDP for computing an upper bound on the global Lipschitz constant of multi-layer
neural networks when &g norm is considered in both input and output domains. This result for the single hidden layer case is formally stated the following theorem.
Theorem (30) Consider a single-layer neural network described by h(x)) = W o(W))). Sup- pose ((x): R R = ( (( )} where & is slope-restricted over R with parameters 0 S a S B < co. Suppose there exist > 0 and diagonal T E $4 such that the matrix inequality
M(p,T)= = -2,3w00 TW plno
(a + B)- T
W 30,
(7)
(a + 3)7W
-77 W
holds. Then [l(xz) h(y)lla S Vplr- yll2 for all 2, R
The key advantage of this SDP formulation is that we can exploit several properties of the structure, namely monotonicity (a 2 0) and Lipschitz continuity (6 < oo) of the activation functions, well as using the same activation function in the activation layer. However, solving this SDP and enforcing them during training can be challenging even for small-scale neural networks. The recent work [43) has exploited the chordal structure of the resulting SDP imposed by the sequential structure of the network to solve the SDP for larger instances. However, these approaches still unable to scale to larger problems and are not suitable for training purposes.
To guide the search for analytic solutions to the linear matrix inequality (LMI) of Theorem | the authors in (38] consider the following residual structure,
h(x) Hx Go(Wz).
(8)
Then it can be shown that the LMI condition generalizes to condition details).
(see Appendix
A.3 for
M(p T) 2aBB T TW + H -P (a (W+ H (a + BYTW + G H
30,
(9)
-2 G
By choosing p- 11 and G -(a TT then the LMI (9) simplities (a 3)TTWW 3 2T (all blocks in the LMI except for the lower diagonal block become zero). When we restrict 7 to be positive definite, then the latter condition is equivalent to (a W < 27-1, which can be satisfied analytically using various choices of T (38). summary, the function h(x) = x S)W TT((az) is guaranteed to be 1 l-Lipschitz long (a+ ()+ 2
potential issue with the above parameterization (and I-Lipschitz networks in general) that, since the true Lipschitz constant of the layer can be less than one, the multi-layer concatenation can become overly contractive. One way to resolve this limitation is to modify the parameterization as follows. Proposition 2 Suppose WWT
2p 7 for some p 0 and some diagonal positive definite [a+p)>?"
T. Then the following function Vp-Lipschitz.
1(x))= Var a 3
W To(Wa)).
(10)
Now if we make a cascade connection of L 2 2 layers of the form 10 (each having its own p). a naive bound on the Lipschitz constant of the corresponding deep network would be _ P: 1/2
However, this upper bound can still be very crude. We now propose an alternative approach to compute an analytic upper bound on the Lipschitz constant of (8). For the multi-layer case, we then show that our method can capture the coupling between different layers to improve the naive bound. For the sake of space, we defer all the proofs to the supplementary materials.
5

---

a+ GW
H
1
W
A(x)
W
G
h(x)
Loop Transformation
(1ra) v(22))
((x))
613
(ur, v((r))
(1ry ((2))
Mlkg)
olas)
-32
-13
-12
10
-20 -1
-6
63
05
12
Figure 1: Loop transformation on residual layer of the form h((x) = Hr + Go(Wa). Here we use ((x) tanh ir for the illustration of the loop transformation.
The power of loop transformation Starting from (8) Lipschitz constant of h can be computed as
using the fact that & is B-Lipschitz, a global
[+(x)
[I (1)+- 6(Wx)))I
(|) + BIGGI|
| 2'11
(11)
Leuive
This upper bound is pessimistic as it does not exploit the monotonicity (a 2 0) of activation functions. In other words, this bound would not change long as a 2 -3. To inform the bound with monotonicity, we perform loop transformation 44 45 to bring the non-linearities to the symmetric sector [-(3 22 (3 22), resulting in the representation
3 h(x) = (H +
GW) x + Ge(Ww),
(12)
2
where (xx) == (xx) 0+0 is the loop transformed nonlinearity, which is no longer monotone, and 8-0 Lipschitz- see Figure
We can now compute Lipschitz constant as
a B
[M(x)-(<')) =I(H
GW) - x') (C
2
B
$ |1(
- -
(W>)))
(13)
+ a a
GWI + 8
[|
| | -z-1l||-
2
LAr
As show below, this loop transformation does improve the naive bound. In Appendix A.3 we also prove the optimality of the transformation.
Proposition 3 Consider single-layer residual structure given by h(*) Hr + GoWwz). Suppose
6: R + "R ((x) = (x((1)) .-- --(p(( )}, where is slope restricted in [a,, .8). Then h is Lipschitz at9
continuous with constant || + 2 GW|
B-a G [|]| < Luaive-

---

Bound refinement. For the case of the &2 norm, we can further improve the derived bound in (3)
Specifically, we can bound the Lipschitz constant the second term of in (12 analytically using LipSDP, which we summarize in the following theorem. P
Theorem Suppose there exists a diagonal T that satisfies GT 8 in &g norm is given by
TT. Then Lipschitz constant of
(LT- = I|H 3
B a || || TWT GW +
2
2
By optimizing over the choice of diagonal T satisfying GT 3 T, we can find the best Lipschitz bound achievable by this method. In this paper, however, we are more interested in analytical choices of 7. Using the same techniques outlined in (38), we have the following choices:
1. Spectral Normalization (SN): We satisfy GT T simply by choosing T TsN |
In this case, (T'ss) = | a= GWIl2 - |22]22/ = LLT.
AOL [36]
Choose T. = شラ=1 |G Glay. As result, G G is real-symmetric and diagonally dominant with positive diagonal elements, and thus, is positive semidefinite.
3. SLL 388; Choose Tü Σラ=1 |G Gloy Si, where q: 0. [38] uses the Gershgorin circle
|GT
theorem to prove that this choice of 7 satisfies G
3.1 Multi-layer Neural Networks
We now extend the proposed technique to the multi-layer case. Consider the following structure,
yk WA k ==00 =, ..............................
(14)
Fk++1 Haæ GRØ(yn) ==
with Wr I for consistency. Then yr. æ is the output of the neural network. To compute a Lipschitz constant, we first apply loop transformation to each activation layer, resulting in the following representation.
Lemma Consider the sequences in (4) Define fy H& + at @t2 for k: = 0.... ,,. Then
uk+1 WK Hawo +
Σ W Mr Hyt1)) =- --1 (15)
We now ready state result for the multi-layer case.
Theorem Let my A: 2 be defined recursively as
8 a
m = [W H Holl + 2
W Hy -.HH+11,,mmm,
(16)
j=0
with mi = |Woll- Then my is Lipschitz constant of xo + ykk, k 0, ... I. In particular, my is a Lipschitz constant of the neural network Zo + yr. T..
Similar to the single-layer case, we can refine the bounds for the & norm. For the sake of space, we defer this to the Appendix, and we use the bounds in 16) in our experiments.
Complexity For an I--layer network, the recursion (66) requires O(I.²) number of matrix norm calculations. For the naive bound, this number is exactly T.. Despite this increase in complexity, utilize the recurring structure of the calculations that enable parallelized implementation on GPUs. This utilization results reduction of the time complexity (L), the same the naive Lipschitz estimation algorithm. We provide a more detailed analysis of the computational and time complexity and the GPU implementation in Appendix A.4 A.4
The Theorem of 30 assumes that 2 0 (monotonicity). but it can be shown that the theorem holds long 00 < a, which is the case loop-transformed nonlinearity.
NNte that we let Hs H |= I.
7

---

4 Experimental Results
In this section, we evaluate our proposed method for training deep classifiers on the MNIST (46). CIFAR-10 10 [47] and Tiny-Imagement [48) datasets. We compare results with the closely related state-of-the-art methods. We further analyze the efficiency of our improved Lipschitz bounding algorithm and leverage it to compute the certified robust radii for the test dataset.
4.1 Eg-Robustness
Experimental setup We train using our novel loss function to certify robustness (6. using cross- entropy as the differentiable surrogate, against &g perturbations of size 1.58 on MNIST and 36/255 on CIFAR-10 10 and T We train convolutional neural networks of the form mCnF with ReLU activation functions, as in (20). where m and n denote the number of convolutional and fully connected layers, respectively. The details of the architectures, training process, and most
hyperparameters are deferred to the supplementary materials.
Baselines For basclines, we consider recent state-of-the-ar methods that have provided results on
convolutional neural networks of similar size. We consider: (1) GloRo (5) which uses naive Lipschitz estimation with a smoothness regularizer inspired by TRADES; (2) Local-lip-B/G (+ MaxMin) (20) which uses local Lipschitz constant calculation along with cut-off ReLU and MaxMin activation functions; (3) LipConvnet-5/10//
(34) that uses I-Lipschitz convolutional networks with GNP Householder activations; (4) SmLlsmall (SDP-based Lipschitz Layers) (38) which is much larger
27 layer I-Lipschitz network; (5) AOL-Small AOL-Small/Medium (36) which presents much larger 1-Lipschitz networks trained to have almost orthogonal layers.
Evaluation We evaluate the accuracy of the trained networks under 3 criteria; standard accuracy, adversarial accuracy, and certified accuracy. For adversarial accuracy we perform PGD attacks using 4 (hyperparameters provided in supplementary material). For certified accuracy, we calculate the certified radii using (4) and verify if they are larger than the priori-assigned perturbation budget. For the methods of recent literature, we report their best numbers as per the manuscript.
Results The results of the experiments presented in Table I On MNIST, we outperform the otate-of-the-art by a margin of 7.5% on verified accuracy whilst maintaining the same standard accuracy. On CIFAR-10 10 surpass all of the state-of-ther aottte--ttt--ttiiee in verified accuracy. Furthermore, methods using networks of similar sizes, i.c., 6C2F or LipConvnet-5, we surpass by a margin of around 4%. The networks of the recent literature AOL (36) and SLL. (38) are achieving slightly worse certified accuracy even with much larger networks. On Tiny-Imagened our current best results are on par with the tthee-of-the-art.
4.1.1 Lipschitz Estimation
A key part of our method is the new improved Lipschitz estimation algorithm (LipLT) and the effective use of pairwise Lipschitz constants. Unlike previous works that estimate the pairwise Lipschitz between class and j by the upper bound v2L.g (20), where L.g is the Lipschitz constant of the whole network, or as L; + L, (5). where L; is the Lipschitz constant of the i-th class, we approximate this value directly as Lij by considering the map z; (2; 0) (x; 0). Table 2 shows the average statistic for Lipschitz constants estimated using different methods. Our improved Lipschitz calculation algorithm provides near an order-of order-of-magniuue maggitude improvement over the naive method. Furthermore, Table portrays the superiority of using pairwise Lipschitz constants instead of other proxies. Figure 2a illustrates the difference between using LipLT versus the naive method to calculate the certified radius. In this experiment, the naive method barely certifics one percent of the data points at the perturbation level of 1.58. However, using LipLT, we can certify a significant portion of
We selected these values for the perturbation budget for consistency with prior work.
8

---

Table Comparison with recent certified training algorithms. Best certified training accuracies are highlighted in bold.
Due size mismutcc that iteration, had modily the urchilecture slightly changing the pailing of some the convolutional layers. The supplememmry
same ociginal architecture in 20).
Method
Model
Clean (%)
PGD (%)
Certified(%)
MNIST
1.58)
Standard GloRo
4C3F
99.0
45.4
0.0
4C3F
92.9
68.9
50.1
Local-L.ip
4C3F
96.3
78.2
55.8
CRM (ours)
4C3F
96.27
88.04
63.37
CIFAR-10
36/255)
Standard
6C2F
87.5
32.5
0.0
GloRo
6C2F
77.0
69.2
58.4
Local-Lip-GG
6C2F
76.4
69.2
51.3
Local-Lip-B
6C2F
70.7
64.8
54.3
Local-Lip-B + MaxMin
6C2F
77.4
70.4
60.7
LipConvnet
5-CR
75.31
60.37
LipConvnet
10-CR
76.23
62.57
LipConvnet
15-CR
76.39
62.96
SLL
Small
71.2
62.6
AOL
Small
69.8
62,0
AOL
Medium
71.1
63.8
CRM (ours)
6C2F
74.82
72.31
64.16
Tiny-Imagenet (e 36/255)
Standard
8C2F
19.4
0.0
Local-Lip-G
8C2F
13.2
Local-Lip-B
SC2F
20.7
GloRo
SC2F
22.4
Local-Lip-B + MaxMin
8C2F
23.4
SLL
Small
19.5
CRM (ours)
8C2F
23.97
23.04
17.98
389
05
20
Poesaalay
280
2
00
35
29
6.1
0.2
0.80
8301
6:022
0004
(a)
(b)
(c)
Figure 2: (a) Distribution of certified radii calculated using direct pairwise Lipschitz constants for the MNIST test dataset for the network trained using CRM. (b-c) Comparison of the distribution of the certified radii for model trained using CRM (top) versus standard trained model (bottom) for MNIST (b) and CIFAR-I0 (c). For any given e, the probability curves denote the empirical probability of data point from that data set having certified radius of least c.
the data points.
We further conduct an analysis of the certified radii of the data points for regularized versus unregular- ized networks for MNIST and CIFAR-10. Figures 2b and 2c illustrate the distribution of the certified radii. These radii were computed using the direct pairwise Lipschitz bounding. When comparing the results of the CRM-trained models (top figures) with the standard models (bottom figures), becomes evident that our loss function enhances the certified radius.

---

Table Comparison of average pairwise Lipschitz constant calculated using the naive and improved method on networks trained using CRM. We use the same architectures as Table To calculate the averages, we form all unique pairs and calculate the Lipschitz constant according to the relevant formulation and then take the average.
MNIST
CIFARIO
Tiny- Imagenete
Lij
L + L,
V2L
Lij
L Lj
V2
Lij
L
Lj
V2L
Naive Improved
266.08
1285.18 212.68
2759.63
93.52
131.98
139.75
313.62
485 185.62
2057.00 60.37
64.10
419.83
11.26
18.30
23.43
9.46
14.77
5
Limitations
Although our proposed formulation has elegant mathematical structure, there exist some limitations: (1) We are still using global Lipschitz constants to bound the margin, which can be conservative. We will investigate how we can localize our calculations without a significant increase in computation. (2) Computation of pairwise Lipschitz bounds for very deep architectures and or a large number of classes become computationally intensive for training purposes (see Appendix A.4 for further discussions). (3) Several hyper-paramette parameters require manual tuning. It is highly desirable to explore adaptive approaches automatically select these hyper-parameters.
6 Conclusion
Adversarial defense methods are numerous and their approaches are different, but they all attempt to explicitly or implicitly increase the margin of the classifier, which is a measure of adversarial robustness (or vulnerability). From this perspective, it is highly desirable develop adversarial defenses that can manipulate the decision boundary and increase the margin effectively and efficiently, We attempt to maximize the input margin by penalizing the Lipschitz constant of the neural network along vulnerable directions. Additionally, we develop new method for calculating guaranteed analytic and differentiable upper bounds the Lipschitz constant of the deep network. LipLT is provably better than the naive Lipschitz constant. We have also provided a parallelized implementation of LipLT using the recurring structure of the calculations, which is fast and scalable. Our proposed method achieves competitive results in terms verified accuracy on the MNIST and CIFAR-10 datasets.
10

---

References
[1] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitra Erhan, lan Goodfellow, and Rob Fergus. "Intriguing properties of neural networks". In: arXiv preprini arXiv:1312.6199 (2013).
[2] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. "Explaining and harnessing adversarial examples". In: arXiv preprint arXiv: 14l..61126722 (2014).
[3] Alexey Kurakin, lan Goodfellow, and Samy Bengio. "Adversarial machine learning at scale". In: arXiv preprint 1eXivv1611.. 1.01236 (2016).
[4] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian
Vladu. "Towards deep learning models resistant to adversarial attacks". In: arXiv preprint arXiv:/706.000 06083 (2017).
[5] Klas Leino, Zifan Wang, and Matt Fredrikson. "Globally-robust neural networks". In: Interna- tional Conference on Machine Learning. PMLR. 2021, pp. 6212-6222.
[6] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. "Theoreticalll principled trade-off between robustness and accuracy". In: International conference on machine learning. PMLR. 2019, pp. 7472-7482.
[7] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. "Par- seval networks: Improving robustness adversarial examples". In: International Conference on Machine Learning. PMLR. 2017, pp. 854-863.
[8] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. "Certified adversarial robustness via random- ized smoothing". In: infernational conference machine learning. PMLR. 2019, pp. 1310- 1320.
[9] Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. "Certifying confidence via randomized smoothing". In: Advances in Neural Information Processing Systems 33 (2020),
pp. 5165-5177.
[10] Hadi Salman, Jerry Li, Ila 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 32 (2019).
[11] Eric Wong and Zico Kolter. "Provable defenses against adversarial examples via the convex outer adversarial polytope". In: International Conference on Machine Learning. PMLR. 2018,
pp. 5286-5295.
[12] Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy R Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy Liang, et al. "Enabling certification of verification-agnosicc networks via memory-effiiient semidefinite programming". In: Advances in Neural Information Processing Systems (2020), pp. 5318- 5331.
[13] Fangzhou Liao, Ming Liang, Yinpeng Dong, Tianyu Pang, Xiaolin Hu, and Jun Zhu. "Defense against adversarial attacks using high-level representation guided denoiser". In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2018, pp. 1778-1787.
[14] Florian Tramèr, Alexey Kurakin, Nicolas Papernt, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. "Ensemble adversarial training: Attacks and defenses". In: arXiv preprint 17Xivv/705.0777 (2017).
[15] Nikolaos Tsilivis, Jingtong Su, and Julia Kempe. "Can we achieve robustness from data alone?"
In: arXiv preprint 22XX::2207.1172 (2022).
[16] Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. "Mma training: Direct input space margin maximization through adversarial training". In: arXiv preprint arXiv:1812.02633 (2018).
[17] Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. "Geometry-wwan instance-reweighted adversarial training". In: arXiv preprint arXiv:2010.011 01766 (2020).
[18] Yuancheng Xu, Yanchao Sun, Micah Goldblum, Tom Goldstein, and Furong Huang. "Exploring and Exploiting Decision Boundary Dynamics for Adversarial Robustness". In: arXiv preprint 2xXiv:2302.03015 (2023).
[19] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. "Lipschhtt-margin training: Scalable certification of perturbation invariance for deep neural networks". In: Advances neural information processing systems 31 (2018).

---

[20] Yujia Huang. Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. "Training certifiably robust neural networks with efficient local lipschitz bounds". In: Advances in Neural Information Processing Systems 34 (2021), pp. 22745-2277
[21] Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. "Towards certifying l-infinity robustness using neural networks with l-inf-dist neurons". In: International Conference on Machine Learning. PMLR. 2021, pp. 12368-122 12379.
[22] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. "On the effectiveness of interval bound propagation for training verifiably robust models". In: arXiv preprint arXiv:/810. 12715 (2018).
[23] Sungyoon Lee, Jaewook Lec, and Saerom Park. -Lipschit training with a tight outer bound". In: Advances in Neural Information Processing Systems 33 (2020), pp. 16891-16902.
[24] Judy Hoffman, Daniel A Roberts, and Sho Yaida. "Robust learning with jacobian regulariza- tion". In: arXiv preprint arXiv: 1908. 02729 (2019).
[25] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. "Regularisation of neural networks by enforcing lipschitz continuity". In: Machine Learning 110 (2021), pp- 393-416
[26] Christina Back, Yiding Jiang, Aditi Raghunathan, and Zico Kolter. " "Agreement-on-tton -ine: Predicting the performance of neural networks under distribution shift". In: Advances in Neural Information Processing Systems 35 (2022): pp. 19274-19289.
[27] Zhouxing Shi, Yihan Wang, Huan Zhang. J Zico Kolter, and Cho-Jui Hsieh. "Efficiently computing local Lipschitz constants of neural networks via bound propagation". In: Advances in Neural Information Processing Systems 35 (2022). pp. 2350-2364.
[28] Gagandcep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. "An abstract domain for certifying neural networks". In: Proceedings of the ACM on Programming Languages 3.POPL (2019), pp. 1-30.
[29] Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. "Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification". In: Advances in Neural Information Processing Systems 34 (2021),
pp. 29909-29921.
[30] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. "Efficient and accurate estimation of lipschitz constants for deep neural networks" In: Advances in Neural Information Processing Systems 32 (2019).
[31] Navid Hashemi, Justin Ruths, and Mahyar Fazlyab. "Certifying incremental quadratic con- straints for neural networks via convex optimization". In: Learning for Dynamics and Control. PMLR. 2021, pp. 842-853.
[32] Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. "Training robust neural networks using Lipschitz bounds". In: IEEE Control Systems Letters 6 (2021),
pp. 121-126.
[33] Sahil Singla and Soheil Feizi. "Skew orthogonal convolutions". In: International Conference
on Machine Learning. PMLR. 2021, pp. 9756-9766.
[34]
Sahil Singla, Surbhi Singla, and Soheil Feizi "Improved deterministic 12 robustness on CIFAR-
10 and CIFAR- 100". In: arXiv preprint arXiv:2108.0400 (2021).
[35]
Cem Anil, James Lucas, and Roger Grosse. "Sorting out Lipschitz function approximation".
In: International Conference Machine Learning. PMLR. 2019, pp. 291-301.
[36] Bernd Prach and Christoph H Lampert. "Almost-orthogona" layers for efficient general-purpose Lipschitz networks". In: Computer Vision-ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022. Proceedings, Part XXI. Springer. 2022, pp. 350-365.
[37] Asher Trockman and Zico Kolter. "Orthogonalizing convolutional layers with the cayley transform". In: arXiv preprint a7X1v:2104.07167 (2021).
[38] Alexandre Araujo, Aaron Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu, "A unified algebraic perspective on lipschitz neural networks". In: arXiv preprint arXiv:2303.033 (2023).
[39] Ruigang Wang and Ian Manchester. "Direct parameterization of lipschitz-buunded bounded deep networks". In: International Conference on Machine Learning. PMLR. 2023, pp. 36093- 36110. 10.
12

---

[40] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[41] Francesco Croce and Matthias Hein. "Minimally distorted adversarial examples with a fast adaptive boundary attack". In: International Conference Machine Learning. PMLR. 2020, pp. 2196-2205.
[42] Mahyar Fazlyab, Manfred Morari, and George J Pappas. "Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming". In: IEEE Transactions on Automatic Control 67.1 (2020), pp. 1-15.
[43] Anton Xue, Lars Lindemann, Alexander Robey, Hamed Hassani, George J Pappas, and Rajeev Alur. *Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks". In: 2022 IEEE 61 Conference on Decision and Control (CDC). IEEE. 2022, pp. 3389-3396.
[44] Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. Linear matrix inequalities in system and control theory. Vol. 15. Siam, 1994.
[45] Charles A Desoer and Mathukumalli Vidyasagar. Feedback systems: input-output properties.
STAM, 2009.
[46] Yann LeCun. "The MNIST database of handwritten digits". In: http://yann. lecun. com/exub/mniis// (1998).
[47] Alex Krizhevsky, Geoffrey Hinton, et al. "Learning multiple layers of features from tiny images". In: (2009).
[48] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. "Imagenet: A large- scale hierarchical image database". In: 2009 IEEE conference on computer vision and pattern recognition. Icee. 2009. pp. 248-2552
[49] Tsui- Weng. Huan Zhang. Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. "Towards Fast Computation of Certified Robustness for ReLU Networks". In: arXiv preprint arXiv:
(2018).
[50] Trevor Avant and Kristi A Morgansen. "A "Analytical bounds on the local Lipschitz constants of affine-ReLU functions". In: arXiv preprint arXiv:2008. 06144 (2020).
[51] Tsui- Wei Weng, Huan Zhang, Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. "Evaluating the robustness of neural networks: An extreme value theory approach". In: arXiv preprini arXiv:1801. 10578 (2018).
[52] Aladin Virmaux and Kevin Scaman. "Lipschitz regularity of deep neural networks: analysis and efficient estimation". In: Advances in Neural Information Processing Systems. 2018, pp. 3835-3844.
[53] Fabian Latorre, Paul Rolland, and Volkan Cevher. "Lipschitz constant estimation of Neural Networks via sparse polynomial optimization". In: International Conference on Learning Representations. 2020.
[54] Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. "Semialgebraic optimiza- tion for lipschitz constants of relu networks". In: Advances in Neural Information Processing Systems 33 (2020), pp. 19189-19200.
[55] Matt Jordan and Alexandros G Dimakis. "Exactly computing the local lipschitz constant of relu networks". In: Advances in Neural Information Processing Systems 33 (2020), pp. 7344-7353.
[56] Patrick L Combettes and Jean- Chrr-thittpphe Pesquet. "Lipschitz certificates for layered network structures driven by averaged activation operators". In: SIAM Journal on Mathematics of Data Science 2.2 (2020). pp. 529-557.
[57] Gal Chechik, Geremy Heitz, Gal Elidan, Pieter Abbeel, and Daphne Koller. "Max-margin Classification of Data with Absent Features." " In: Journal of Machine Learning Research 9.1 (2008).
[58]
Johan AK Suykens and Joos Vandewalle. "Least squares support vector machine classifiers". In: Neural processing letters (1999), pp. 293-300.
[59] Gamaleldin Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. "Large margin deep networks for classification". In: Advances in neural information processing systems 31 (2018).
[60] Ziang Yan, Yiwen Guo, and Changshui Zhang. "Deep defense: Training dans with improved adversarial robustness". In: Advances in Neural Information Processing Systems 31 (2018).
[61] Yiwen Guo and Changshui Zhang. "Recent advances in large margin learning". In: IEEE Transactions on Pattern Analysis and Machine Intelligence (2021).
13

---

[62] Feng Liu. Bo Han, Tongliang Liu, Chen Gong, Gang Niu, Mingyuan Zhou, Masashi Sugiyama, al. "Probabilistic margins for instance reweighting adversarial training". In: Advances in Neural Information Processing Systems 34 (2021), pp. 23258 23269.
[63] Matthew Mirman, Timon Gehr, and Martin Vechev. "Differentiable abstract interpretation for provably robust neural networks". In: International Conference on Machine Learning. 2018,
pp. 3575-3588
[64]
Huan Zhang, Tsui-Wei Weng, Pin- Chen, Cho-Jui Hsich, and Luca Daniel. "Efficient neural network robustness certification with general activation functions". In: Advances in neural information processing systems. 2018, pp. 4939 4948.
[65] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. "Semidefinite relaxations for cer- tifying robustness to adversarial examples". In: Advances in Neural Information Processing Systems. 2018, pp. 10900-10910.
[66] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. "Certified defenses against adversarial examples". In: arXiv preprint arXiv: 89344 (2018).
[67] Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin Vechev. "TAPS: Connecting Certified and Adversarial Training". In: arXiv preprint 2.dv::2305.05574 (2023).
[68] Diederik P Kingma and Jimmy Ba. "Adam: A method for stochastic optimization", In: arXiv
preprint arXiv: 22. 2.80 (2014).
14


Reviews:
[{"review_id": "gTfbplgFPp", "reviewer": "Reviewer_U11m", "summary": "\nThis paper proposes a loss to induce robustness w.r.t. adversarial attacks. This loss is composed of a term for enlarging the logit difference (such as classical  Cross-Entropy Loss), and a surrogate term to  maximize the robust radius. The latter imply to compute an upper bound of the Lipschitz constant (called L_ij) of the difference of logits z_y-z_i (y is the true class and any other class i).\nInspired by work in [39], the authors propose to take into consideration the motonicity of activation functions to compute a tigher lower bound of a residual-like layer than the classical one. They also propose an extension for computing an upper bound of the Lipschitz constant of a multilayer residual NN.\nNote that Batchnorm layers and dropout are not supported. \nThey also claim to compute these L_ij with the same complexity as computing the Lipschitz constant of each layer (supplementary materials)\nExperiments are done on MNIST,CIFAR10 and TinyImagenet. Comparison is provided with several methods, reporting clean accuracy, adversarial accuracy (PGD attack) and certified accuracy, and report higher certified accuracy. They also compare the Lipschitz estimation to classical bounds (sqrt(2)Lz, Li+Lj and theirs Lij) and claims an improvement of up to 200.\n", "questions": "The paper is rather easy to read. Even if without the supplementary materials, \nSeveral errors or inexactitude can be found in  Notation and equation and proof\nComputation of a tight upper bound of NN seems new and interesting. However enlarging the margin under lipschitz constraint or regularization is not new. And besides main loss and regularization may have contradictory objectives (see detail comments)\n\nDetailed remarks:\n\nL31: correlation between robustness and lipschitz constant of NN is an established property , cite[1]\nL33: “constraining the model (e.g. 1-Lipschitz models) can lead to excessive regularization in addition to potentially limiting expressivity.”: it has been shown that 1-Lipschitz NN have the the same expressivity has non constrained networks (see “pay attention to your loss”, Bethune et al. Neurips’22). Thus this sentence is false.\nL43: “hinges on the idea of loop transformation on the nonlinearities”: the notion of “loop transformation” is not clear. Please clarify or add a reference.\nL54: choice of tiny-imagenet is not justified. Authors claim for scalability (L84) but restrain the learning to tiny-Imagenet.This must be explained\nL92: notation for matrix norm  is not described in this section, and ||.|| can be confusing: frobenius nor, spectral norm,…\nL100: “A unified perspective on margin maximization” : this section title is not justified. Please explain which unification is provided in this section?\nL111: “we note that maximizing the logit margin…..in the input space”: this is a well known property ([1])\nL125: “many choices for h, we use the same function proposed in [17] (see supplementary materials) “ but no information is given in the supplementary matrials\nL132: eq 4 this equation is not use in the following, confusing in notation with eq (7), and not evaluated. Probably useless for paper understanding\nL134: .”Solving (4) still requires an iterative inner loop within the outer loop of training”: transformation from inf formulation to outer loop is unclear. Please precise if this loop is an adversarial search or any other method\nL146: “This lower bound is not differentiable”: min function is differentiable. A least subderivative. Justification l149 is a better one. \nEq 9: it is known that CE loss aims to increase the Lipschitz constant of the NN during training (see paper Bethune et al cited earlier), and the regularization in (6) aims to reduce this Lipschitz constant. Please explain how these two antagonist objectives will be balanced. \nL169: inequality soes not represent the lispchitz constraint. A divide operator is missing\nTheorem 3.1: this theorem isbased on supposition of existence of \\rho and T, but in the following justifications of this existence is not clear\nL185: “analytic solutions to the LMI of Theorem 3.1,”: acronym LMI is not defined\nL192: same remark as on line L33\nL204: ||H|| isnot clear can be ether frobenius norm or spectral norm?\nL247: “,we calculate the certified radii using(6)” (6) is only applicable for ReLU like activation. Please justify how this certified robustness is computed for NN such as MaxMin (2)\nL249: “CRM hyperparameters”: first use of this acronym. Please detail\nL251: contradiction of justification given in eq (8). Please justify why the choice of h is not the same for each dataset.\nL255: “For Tiny-Imagenet, as the number of classes is far larger, bounding the pairwise Lipschitz would be computationally heavy.” Such a sentence and footnote 4  need justification. Please detail the computational complexity induced by your method\nTable 1: In related works, author indicate that 1-Lipschitz NN are harder to train and have a lower expressivity. However, clean performance of the proposed solution has performances equivalent to   1Lip solutions and far from classical performances. Please justify\nNo software provided to verify the correctness of the paper \n\n\nSupplementary materials:\nL532: “However, the expressive power of 1-Lipschitz networks needs to be addressed and some works study their limitations [47]. ” this sentence is false. See remark on line 33\nL580: \\gamma is non differentiable. : Max operation is differentiable?\nL598: h function was supposed to be described in the supplementary materials \nL605 (equation) replace (1-t) by (1-t^hat)\nL615 (equation) i\\neqy is replaced in this eq by i\\in[1,K-1] pleae justify?\nL638: please justify te existenceof T and \\rho?\nL660 m_k is not the lipschitz constant, but an upper bound of the Lipschitz constant\nL660 (eq) m_{k+1} should be lower than \nL673: eq 33 : lack ||\nL719: “   Calculating the ℓ 2 norm of a general rectangular matrix can be performed by \nusing the power iteration”: confusing notations: power iteration is for spectral norm and is often in general notes ||.||_2 and not l_2. Confusing with frobenius norm\n\nreferences: clean references for papers that are published and not preprint", "limitations": "Limitations are addressed", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The algorithm described in section 3.1 seems new and results presented in table 1 indicate that it enhance the lipschitz estimation.. ", "weaknesses": "-Clean performances are low and equivalent to 1LipchitzNN but author indicate in the related work that it should have a higher expressivity\n\n-No evaluation of computational complexity is provided. Scalability os the method is not clear\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive criticism and detailed comments. We have provided a global response to address the comments that are common to all the reviewers. Here we address the comments specific to the reviewer. \n\n> Batchnorm layers and dropout are not supported.\n\nAs batch normalization layers are linear, our method readily applies to them. In fact, if the batch normalization layer is next to a linear layer, the batch normalization could essentially be absorbed into the linear layer. The exact formula for the scenario in which batch normalizations are present in the architecture was not provided as it is architecture dependent. For future work, we hope to make the framework modular so that it can parse the architecture and adapt the algorithm.\n\n> Clean performances are low and equivalent to 1LipchitzNN...\n\nWe are obtaining similar or better clean performance compared to 1-LipschitzNNs but with *smaller* architectures (please see Table 1 in the original submission)\n\n> No evaluation of computational complexity is provided. Scalability of the...\n\nWe kindly refer the reviewer to the global response: “Complexity Analysis of Lipschitz Estimation Algorithm”, in which we provide a complexity analysis and support the analysis with new experiments. Remarkably, these experiments confirm the scalability of the method as the depth of the model increases. \n\n### Detailed Remarks:\n\n-L33: We thank the reviewer for bringing the paper “Pay attention to your loss” to our attention, which had slipped through our literature review. We have removed the comments about the lack of expressivity of 1-Lipschitz neural networks.\n\n-L43: We agree with the reviewer. Please see the global response: “Details on Loop Transformation”, where we explain the details and provide a reference.\n\n-L54: The bottleneck in scalability is due to the use of pairwise Lipschitz constants and *not* the Lipschitz constant estimation algorithm itself. To elaborate, the number of pairwise Lipschitz constant calculations is $ k_m \\choose 2$, where $k_m$ is the number of classes in the mini-batch. For datasets with a relatively small number of classes, it is very likely that each mini-batch chosen from the randomly shuffled dataset will contain samples from all classes. A workaround that we will investigate for larger datasets in the future is to modify the data loaders such that each mini-batch would only contain samples from a handful of classes: we would choose $k$ (relatively small) random classes, and draw random samples from these $k$ classes. We understand that this sampling might affect the performance of the model. Thus, we will leave a rigorous treatment of this approach to future work.\n\nAnother possibility to improve the scalability for larger datasets is to use per-class Lipschitz bounds or the Lipschitz constant of the whole network. \n\n-L100: Our hope was to present a unifying loss function in Eq. (6) that can recover several existing loss functions. For example, in Line #618, we showed that regularizing the Lip. the constant of the whole network is simply an upper bound to our regularizer.  Overall, we tend to agree that this may not be the best title for the section, and we propose to change the title to “Dynamic margin maximization for neural network classifiers” if the paper gets accepted.\n\n-L125 In the experiments, we elaborated on what $h$ function we used. Hence, there was no need to refer to supplementary materials in line #125. We apologize for this. We have a paragraph in the supplementary material about $h$ (lines #594-599)\n\n-L134: For each data point (x, y), solving (4) requires an iterative optimization algorithm (the inner loop). After solving (4) for the whole minibatch, the algorithm then needs to update the weights of the model (the outer loop). \n\n-Eq9: There is an inherent trade-off between clean accuracy and adversarial robustness, as established in, for example, [17]. Our regularizer is used to balance this trade-off: by increasing the regularization parameter $\\lambda$, adversarial robustness will tend to increase at the expense of reduced clean accuracy. \n\n-Thm3.1: Thanks for pointing out this subtle point. For simplicity, let’s assume $\\alpha=0$. Suppose $T \\succeq 0$ is chosen such that ${W^1}^\\top W^1 - 2T \\prec 0$. This is always possible. For example, choose $T = 0.5 (\\sigma^2_{\\max}(W^1)+\\epsilon^2) I $. \n\nThen we can use Schur Complements for positive semidefinite matrices to obtain the following equivalent condition to the LMI:\n\n$-\\beta^2 {W^0}^\\top T ({W^1}^\\top W^1 - 2T)^{-1} T W^0 \\preceq \\rho I$. \n\nAgain, this is feasible by choosing $\\rho$ to be at least equal to the maximum singular value of the positive definite matrix on the left hand side. In conlcusion, the LMI is always feasible. A similar analysis can be done for a more general case of $\\alpha>0$. We will discuss the feasibility of this LMI in the appendix.\n\n-L247: Eq. (6) is applicable to MaxMin activations, but our Lipchitz constant estimation algorithm does not currently support such activations. We envision that we can handle GroupSort activations by representing them equivalently as multiple ReLU layers. We leave this for future work. \n\n-L249: We apologize for not defining the abbreviation. CRM stands for Certified Radius Maximization to refer to our method. \n\n-L251: For our updated experiments on CIFAR10 and Tiny-Imagenet, we are now using the same choices for h and obtaining similar results. For reproducibility, we will release the code upon acceptance. \n\n-L255: As shown by Fig. 4 in the appended document, our Lipschitz calculation algorithm scales linearly with network size thanks to the highly specialized implementation. \n\nAbout Footnote 4: at the time of submission, achieving the best hyper-parameter tuning was not possible due to the long run times on Tiny-Imagenet. Nevertheless, even with the suboptimal tuning of the hyper-parameter,s we are obtaining a similar performance (Table 1). \n\n"}, {"review_id": "1M9hdNZkjs", "reviewer": "Reviewer_9vGY", "summary": "This paper developed a robust training algorithm whose objective is to increase the margin while regularizing the Lipschitz constant of the model along vulnerable directions. The authors also developed an improved Lipschitz estimation for a multi-layer networks with residual connections. Experiments on MNIST and CIFAR-10 shows superior performance of the proposed method compared to the state-of-the-art.", "questions": "- In section 3, the proposed scalable Lipschitz estimation method seems to be work on neural networks with residual connections (Eq 16). But in the experiments, the model architectures seems to not have residual connections. How to apply the proposed bounds then?  \n\n- What is loop transformation? I am not familiar with the term.\n\n- Line 221, Recurring structure can reduce the complexity by dynamic programing, but the operations are still sequential rather than parallel since we need m_j, j<=k to compute m_{k+1}. How does the parallelized implementation on GPU work?\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- A novel regularized loss function that directly promote larger margins in the input space is proposed.\n- A scalable Lipschitz bounding algorithm is proposed, which is tighter than the naive bound while being efficient. \n- Experiments on MNIST and CIFAR-10 showed the effectiveness of the proposed methods.", "weaknesses": "- This paper proposed many interesting methods, but I sometimes find it hard to see the motivation of each proposed method and the connections between them. It may be good to spend some more space to set up the preliminaries: \n    - The name is section 2 is a unified perspective on margin maximization, I'd hope to see what margin maximization algorithms it unified.  For instance, the variant of (6) may result in different algorithms, replacing L_{yi} with \\sqrt(2)L will results to Lipschitz margin training [Tsuzuku et al. 2018]. \n    - It would be good to decouple the effectiveness of each component: the use of pairwise Lipschitz, the use of log-sum-exp to make max/min to be differentiable, the use of the new Lipschitz bounding algorithm. It would be interesting to see the contribution from each of these to the certified accuracy.\n\n- It would be good if the authors can discuss the sensitivity of the proposed method wrt the choice of hyper-parameters. An ablation study on CIFAR-10 with various hyper-parameters and the corresponding certified robustness performance would be helpful. The proposed method is not performing as well on Tiny-Imagenet, I understand that it may be because of the inferior choice of hyper-parameters, but it may be good to debug more into that, especially giving table 2, the improved pair-wise Lipchitz of Tiny Imagenet seems to be much better than other Lipschitz, it is surprising that it does not lead to better certified robustness.\n\n- It would be nice to provide the computational cost of the proposed method in terms of Flops or running time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful suggestions and constructive criticism. In the following, we respond to the weaknesses raised by the reviewer.\n\n### Addressing weaknesses\n- Our hope was to present a unifying loss function in Eq. (6) that can recover several existing loss functions. For example, in Line #618, we showed that regularizing the Lip. the constant of the whole network is simply an upper bound to our regularizer. Overall, we tend to agree that this may not be the best title for the section, and we propose to change the title to “Dynamic margin maximization for neural network classifiers” if the paper gets accepted.\n- We have run new experiments to further portray the effect of the different parts of the algorithm as you had kindly suggested. The results are reported in Table 1 of the supplementary pdf of the global rebuttal. We performed the analysis on training CIFAR10. We used two sets of hyperparameters that yielded good results from our experiments under different scenarios and reported the best number in Table 1. The different columns are as follows:\n  - Soft Radius: Training using $ \\underline{R}^{soft}$ (Eq. (7)) + our Lipschitz estimation algorithm.\n  - Hard Radius: Training using $ \\underline{R} = \\min_{i \\neq y} \\frac{z_y - z_i}{L_{yi}} $ (Eq. (6)) + our Lipschitz estimation algorithm.\n  - Naive: Training using $ \\underline{R}^{soft}$ (Eq. (7)) + naive Lipschitz estimation.\n\n- In addition to Table 1 provided in the attached pdf, we would like to refer the reviewer to tables 5, 6, and 7 in the appendix of the original submission that perform several sensitivity studies.\n\n- In our revised manuscript, we have addressed this comment and have added a section on the complexity analysis of our Lipschitz estimation algorithm. For a brief summary of our analysis, you can refer to the global rebuttal section \"Complexity Analysis of Lipschitz Estimation Algorithm.\" We have portrayed the claimed Linear performance in Figure 4 of the supplementary pdf. Furthermore, we have provided run times in the following table for your consideration. We used the *torch.cuda.Event* functionality to precisely time our algorithm. The experiments were conducted on a single NVIDIA RTX A5000 with 24GB of RAM. We used a batch size of 512 for training CIFAR10. The numbers in the table show the average time $ \\pm $ standard deviation in milliseconds (ms). CRM is short for our training method. LipLT is our improved Lipschitz estimation algorithm. In the table, *Lipschitz calculation* measures only the time required to calculate the Lipschitz constant using the relevant method in each iteration, and *Full iteration* measures the full time required for that particular iteration.\n\n  |   | CRM with LipLT | CRM with Naive | Standard|\n  |--------|--------|--------|--------|\n  | Full iteration | 122.7 $\\pm$ 27.2 | 51.6 $\\pm$ 10.9 | 16.4 $\\pm$ 7.1 |\n  |Lipschitz calculation | 43.1 $\\pm$ 6.5 | 13.3 $\\pm$ 1.1 | $\\quad-$ |\n\n ### Question\n- Q1: We initially based our architecture as that of equation (12), derived from [17], to provide further insight on the previous works that use this architecture. To maintain generality, we provided our Lipschitz estimation algorithm for this more general architecture. To provide a more fair comparison with relevant previous work such as [19, 24, 18], we used feed-forward neural networks without residual connections. As our results in Table 1 of the main manuscript portray, we are able to acquire similar or better results than other more complicated residual networks that use many more layers. Thus, we only conducted our experiments on normal feed-forward networks. In case your question also regards the applicability of our derived Lipschitz estimation algorithm to feed-forward networks, we note that this is acquired by setting $H=0$ and $G=I$. In our appendix section A.3, from equation (35) onwards, we derive the relevant formulas for normal feed-forward networks. Furthermore, in A.3.2 we describe all the implementation notes that allow our method to run in Linear time. We kindly ask the reviewer to further elaborate on their question if these comments do not address their concern.\n\n- Q2: Please refer to the global rebuttal section \"Details on Loop Transformation.\"\n\n- Q3: Your observation of the sequential structure required for calculating $m_{k + 1}$ is valid. However, we emphasize that the main point of complexity for calculating $m_{k + 1}$ is calculating the different matrix norms that appear. The way we prevent this sequential structure from slowing down our computation is that our algorithms first calculate all the different norms that appear in all the terms of $m_i$ for $ i \\leq L$. After these norms have been calculated, we are able to calculate the $m_i$ sequentially as they consist of only scalar-scalar multiplications. The details of the algorithm are involved and we refer the reviewer to algorithm 2 of our appendix."}, {"review_id": "ohFVw6t7Fb", "reviewer": "Reviewer_4zXU", "summary": "The authors explore how a model’s robustness to local pertubations in the input space can be enhanced through regularization at a low cost on the clean accuracy. \nThe goal is to have large margins on the desicion boundaries in input space.\nSince adding a regularization directly on the size of these margins is very costly, the authors introduce an alternative and efficient proxy to regularize this.\nThey use the Lipschitz constants of the logit difference function between pairwise classes to identify the most important directions to regularize.\nSince computing the constants is exactly is costly, but naive estiamtes are very conservative as they do not take into account the correlation between the trained layers, the authors introduce a new approximation that is efficient to compute.\nThey show that the method is comparing well with SOTA adversarial robustness methods.\n", "questions": "1. In L.3 you mention Lipschitz-capped networks and argue on to say that these approaches are not good at increasing the input margin. Why is that exactly, does your own approach not follow a similar idea?\n2. L.90, can you elaborate in a half-sentence on the problems of applying this to multilayer networks?\n3. Can you comment at some point, on why you exclude wrongly classified examples from the regularizer and if this sequential inclusion is expected to have some effect?\n4. I like the notation with the underline for the differentiable functions. However, since \\underline{R}_t^soft is not computing the same version as the R_t^soft and is more closely related to \\underline{R} I find the repetition of the names not optimal. Especially in L.249-252 the notation is confusing. First, in L. 251 there is a repetition (replace … with … with) and also it is not clear to me if h(x) in L.249 takes x=R_t^soft(x’,y,theta) so that the condition is a double application of R_t(R_t^soft(…)). I tried to understand it in different ways but I settled on the following to interpret the results: replace R(..) by x only in the case distinction in L.250 and the second ‘with' in L.51 to ‘and’. Could you please clarify if that is correct?\n5. It would be nice if you could spend 2 more sentences explaining what you mean by loop transformation. To me the term was new and difficult to google, I checked the appendix to understand what was going on.\n6. In (17) you use the function psi(.) which is not introduced in the main draft, only in the appendix - maybe you can explain that jointly with the loop transformation.\n7. I did not find a definition of the Standard baseline, so I am just guessing that it is normal training without any regularization…\n8. Can you give an intuition why you chose the specific values of l_2 perturbations in L.231/232? Is there a good reason why this was not tested for other values?\n9. Can you give a clearer comparison how costly the computation of the approximate Lipschitz constants is in comparison to the backpropagation in terms of GPU time in your expeiments? O(L) is mentioned but it would be nice to understand what this means in practice. \n\n\nMinor comments:\n1. In L.81 introduce the abbreviation SDP\n2. L.88 constantS\n3. L.95 To keep with convention, iterate over small i instead of small k in the CE\n4. L.158 eqref missing\n5. In (10) you just say ‘’compatible dimensions’ but then use dimensions in Thm.3.1 without introduction  — it would be nice to make them clear from the start if you are going to use them anyways.\n6. L.185 Abbreviation of LMI not introduced\n7. L.189 blockS\n8. The numbering of the equations in the Supplementary material is very confusing, as theorems and text have different numberings but are not distinguished (so the eq numbers are somehow in seemingly random order)", "limitations": "The authors are clear about the limitations of their method in the paper. I would like to add that it is not immediately clear to me how more complex architectures would be amenable to similar estimates of the Lipschitz constants. Adversarial robust training which only relies on adapting the training data can achieve this for any architecture, so if this is not given, I would include it as a limitation.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors explore a new regularizer that is efficient to compute and can trade off the margin maximation in the input space via Lipschitz regularization which is still efficient to be used on classical toy datasets. They show that this regularizer is on par with existing approaches and may even outperform them.\n2. They provide a new strategy to efficiently approximate Lipschitz constants which is of independent interest.\n3. The paper overall is well written and structured; and can be followed comfortably.\n", "weaknesses": "1. In the experimental evaluation, I would find it valuable to study your model also independently to see how the accuracy of the improved Lipschitz estimate affects the final accuracy outcome. The claim that the less conservative estimates lead to a better regularizer can be checked independently of other state-of-the-art methods. I think interesting experiments to support that claim could be: Comparing how the estimated (and naive) Lipschitz constant evolves throughout training for training with and without regularizer for the same architecture; replacing the improved estimate of the Lipschitz constant with the naive one; introducing a global hyperparameter that replaces L_{ij} and tunes it at the computational budget available to the Lipschitz constant estimation. These are just a few suggestions that would improve the understanding of the actual efficiency of the introduced loss regularizer.\n2. The method relies on estimates for Lipschitz constants for every pair of classes, this scaling becomes unreasonable for datasets with many different classes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their perceptive remarks and suggestions. We will add your useful experiment and ablation study suggestions to the final manuscript. We'll try to address your concerns in the following:\n\n### Addressing weaknesses\n- In the limited rebuttal period we were able to incorporate two of your suggestions. First, we trained three networks under different training methods and logged the average pairwise Lipschitz constants using both the naive and improved methods after each epoch of training. The training methods are as follows (CRM represents our proposed loss function):\n  - CRM with improved Lipschitz estimates at train time\n  - CRM with naive Lipschitz estimates at train time\n  - Standard clean training\n\n  The results of these experiments are provided in Figures 1, 2, and 3 of the attached pdf, respectively. To better showcase the data we have used a logarithmic scale for the y-axis.\n\n  We also performed a set of runs to study the effect of each component. The results are reported in Table 1 of the attached pdf. We performed the analysis on CIFAR10. We used two sets of hyperparameters that yielded good results from our experiments under different scenarios and reported the best number in Table 1. The different columns are as follows:\n  - Soft Radius: Training using LogSumExp (with our improved Lipschitz).\n  - Hard Radius: Training using \n  $  \\underline{R} = \\min_{i \\neq y} \\frac{z_y - z_i}{L_{yi}} $\n  (with our improved Lipschitz).\n  - Naive: Training using LSE but with naive Lipschitz estimation.\n\n- **For a moderate number of classes**: computing pair-wise Lipschitz constants would only require changing the last linear layer. This means that a lot of operations in our algorithm would remain the same, which we exploit. Kindly see Appendix A.3.2 for more details.\n\n  **For a large number of classes**: we can use two levels of relaxation:\n\n  - $L_{ij} \\leq L_i + L_j$: this will reduce the number of Lip. calculations from quadratic (in # of classes) to linear. \n\n  - $L_{ij} \\leq \\sqrt{2} L$: this will reduce the number Lip. calculations from quadratic to constant.\n \n  Nevertheless, regardless of what relaxation we use, our Lipschitz estimation algorithm provably improves the naive bound while being efficient. \n\n\n### Questions\n- Q1: Lipschitz-capped neural networks put a pre-defined bound on the Lipschitz constant, which would guarantee a lower bound on the certified radius. However, this lower bound can be loose and hence, ineffective (please see paragraph #618). By directly regularizing a tighter lower bound on the certified radius, we will have a more direct control over the certified radius\n- Q2: For multi-layer networks, the resulting LMI will be tri-block-diagonal. It is not possible to make the LMI block diagonal using the proposed technique in [39]. The same reference has left the multi-layer case for future work.\n- Q3: If an example is classified wrongly, increasing its margin would make it **robustly wrong**, i.e., away from the classification boundary but in the wrong class. To avoid this, we should regularize points only when they get classified correctly during the training process. Since initially, many points are classified wrongly, we start the robust training after a few epochs of normal training (i.e., w/o the regularizer), so that a relatively good proportion of points will be classified correctly.\n- Q4: We apologize for the confusion. In the revised manuscript, we are now using the same $h$ across all data sets. Specifically, we are now using  $h(x, y; \\theta) = \\begin{cases}  -\\underline{R}_t^{soft}(x, y; \\theta) & \\underline{R}_t(x, y; \\theta) \\leq r_0 \\\\\\\\ 0 &  O.W. \\end{cases} $. This $h$ was only used for the MNIST dataset, but now we are able to obtain similar performance on other datasets using the same function $h$.\n- Q5: Kindly refer to our global response for a detailed explanation of this.\n- Q6: Thanks for the great suggestion. We intend to bring the $\\psi$ notation to the main body to better explain the concept of loop transformation. This would require condensing Section 2 to open up some space.\n- Q7: Yes you are correct. The standard baseline is for when the network is trained using only the cross entropy loss function.\n- Q8: These are the $\\ell_2$ norm bounds that are common in previous work [19, 24]. We would like to point out that Fig. 1 of the paper does portray the distribution of the certified radii.\n- Q9: We kindly refer the reviewer to the section “Complexity Analysis of Lipschitz Estimation Algorithm” in the global rebuttal for an overview of your comment.  Furthermore, we present the following table addressing your comment.\n\n  We used the *torch.cuda.Event* functionality to precisely time our algorithm. The experiments were conducted on a single NVIDIA RTX A5000 with 24GB of RAM. We used a batch size of 512 for training CIFAR10. The numbers in the table show the average time $ \\pm $ standard deviation in milliseconds (ms). CRM is short for our training method. LipLT is our improved Lipschitz estimation algorithm. In the table, *Lipschitz calculation* measures only the time required to calculate the Lipschitz constant using the relevant method in each iteration, and *Full iteration* measures the full time required for that particular iteration.\n\n  |   | CRM with LipLT | CRM with Naive | Standard|\n  |--------|--------|--------|--------|\n  | Full iteration | 122.7 $\\pm$ 27.2 | 51.6 $\\pm$ 10.9 | 16.4 $\\pm$ 7.1 |\n  |Lipschitz calculation | 43.1 $\\pm$ 6.5 | 13.3 $\\pm$ 1.1 | $\\quad-$ |\n"}, {"review_id": "XIDdoDvrRK", "reviewer": "Reviewer_XLJR", "summary": "This paper proposes a new bound for margin maximization, as well as tighter estimation of Lipschitz constant, to improve the adversarial robustness of neural networks. Experiments on three benchmark datasets are presented to show the proposed method can improve the certified radius. ", "questions": "See above. ", "limitations": "The novelty of margin regularization is limited and the experimental results are not sufficient. ", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- This paper is written well and clearly\n- New bound for input margin as regularization term\n- New estimation of Lipschitz constant for multi-layer networks \n- Experiments are conducted to show improved robust radius ", "weaknesses": "- Regarding the improved bound for input margin, I think the contribution is limited since the similar strategy has be used frequently in recently works. \n- The authors argued that the estimation of Lip. constant is scalable for multi-layer networks, but experimental results are not verified. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments. \n\n>Regarding the improved bound for input margin, I think the contribution is limited since the similar strategy has be used frequently in recently works.\n\n> The novelty of margin regularization is limited and the experimental results are not sufficient.\n\nKindly refer to our global response, where we highlight the novel aspects of the proposed regularizer, and how it combines the advantages of various proposed methods in the literature. With the added experiments in the rebuttal (please see the global response and the attached pdf), we believe that our theoretical results are now backed by experiments. \n\n> The authors argued that the estimation of Lip. constant is scalable for multi-layer networks, but experimental results are not verified.\n\nPlease see our global response “Complexity Analysis of Lipschitz Estimation Algorithm”  in which we provide a complexity analysis of our Lipschitz estimation algorithm. We have done more experiments to show the scalability of our Lipshschitz estimation method. In Figure 4 of the attached pdf, as we increase the number of layers, the Lip. calculation runtime increases almost linearly, similar to the naive bound. \n\n"}]

Author rebuttal:
We would like to sincerely thank all the reviewers for their useful comments and feedback. We have improved the paper in terms of presentation, related work, notation, and technical aspects. Below, we report a list of global responses that would be useful for all the reviewers. 

**A new regularization term:** To capture the inherent trade-off between natural accuracy and adversarial robustness [23], we use the cross-entropy loss for clean accuracy and use a new regularizer for adversarial robustness. Our regularizer, inspired from and built upon prior works [17,31,18,24], has the following novel features:

- It is interpretable and explicit: since our regularizer is precisely a lower bound on the distance to the decision boundary, it directly increases the input margins instead of relying on their indirect approximations, enabling a more controllable and efficient enhancement of robustness.

- Our regularizer is differentiable, and computationally efficient thanks to an efficient method to estimate the Lipschitz constant of neural networks.

- Our regularizer is dynamic, in that it uses a barrier function (the function $h$) to prioritize data points that are closer to the decision boundary, as opposed to assigning a fixed robustness margin to all data points.

**A new algorithm for Lipschitz estimation:** We develop a truly scalable and differentiable method for bounding the Lipschitz constant of neural networks. This bound is provably better than the “naive” bound (product of norms of weights) at the expense of an increase in the number of matrix norms we need to compute. To offset this cost, we develop a highly parallelized GPU-enabled implementation that reduces the practical complexity to that of the naive method (please see Figure 4 in the attached pdf). While this algorithm can be of independent interest in several other domains, we tailor it toward robust training in this paper. The ultimate bottleneck in scalability is due to the use of pairwise Lipschitz constants and not the Lipschitz constant estimation itself. We can mitigate this by using the per-class Lipschitz constant or the Lipschitz constant of the whole networks, as also done in [18,24]. We also note in our algorithm, a lot of operations for computing pair-wise Lip. or per-class Lip would remain the same and only the very last iteration would change.


**Details on Loop Transformation:** We apologize for not explaining this concept in more detail, which is the core idea behind the efficiency of the proposed Lipschitz estimation method. Historically, loop transformation has been used in the context of robust control. In our context, loop transformation refers to the operation outlined in equation after line #651, where we subtract a linear term from the nonlinear term $G\phi(Wx)$ and add it to the linear term $Hx$, resulting in an equivalent representation of the layer $h(x)$:

$h(x) = (H + \frac{\alpha+\beta}{2}GW)x + G\psi(W x)$

Where now $\psi$ is the “transformed” nonlinearity. Applying the naive bound on this equivalent representation will provably improve the Lipschitz bound. In the appendix, we have provided both theoretical and intuitive justification as to why this “loop transformation” improves the naive bound. In section A.3.1, we have also proven the optimality of this transformation in the sense that, if we shift the nonlinearity by $\gamma x$, where $\gamma$ is a scalar, the optimal value of $\gamma$ that results in the smallest upper bound is $\gamma=(\alpha+\beta)/2)$. Intuitively, we are shifting the nonlinearities to make them slope-restricted in a symmetric interval, which would minimize the conservatism of the naive bound (please see lines #205-#209) 

The term loop transformation comes from a control-block-diagram interpretation of the above technique. For detailed descriptions of loop transformations, please see the book by Desoer and Vidyasagar [R1, p50]. We will cite this reference in the revised manuscript.

[R1]:  Desoer, Charles A., and Mathukumalli Vidyasagar. Feedback systems: input-output properties. Society for Industrial and Applied Mathematics, 2009.

**Complexity Analysis of Lipschitz Estimation Algorithm:**  We apologize for not being clear in the analysis of complexity. We have added a new section to the paper to address this. We state the final result here: 

As we are utilizing the power method to calculate the norm of matrices, the main computational complexity is introduced by passing a vector/tensor through a linear layer. Thus to simplify exposition, we present the result in terms of the number of passes through the different weights of the network (as pointed out in Algorithms (1) and (2), the power method involved passing a vector though $W_i$ and $W_i^T$): For the fully connected architecture stated in equation (35), which is the architecture used for the experiments of the paper, if we had L layers and performed N iterations of the power method, the naive Lipschitz estimation bound requires $O(NL)$ passes through different weights. For our method, the number of passes is $O(NL^3)$. However, we can use the recurrent structure of the calculations to our advantage based on the explanation of Algorithm 2. By performing $O(L^3)$ concatenations in the batch dimension, we would then need to only perform $O(NL)$ passes through different weights. Figure 4 in the attached pdf confirms this: as we increase the number of layers, the Lip. calculation runtime increases almost linearly, similar to the naive bound.  


Meta-review: The paper introduces a novel loss function to enhance the robustness of neural networks by enlarging the input space margin. One contribution is the proposal of an efficient method for estimating the Lipschitz constant, which is simple and performs well. Experiments on standard datasets like MNIST, CIFAR-10, and TinyImageNet showcase improved certified accuracy and robust radius, establishing the method's superiority over state-of-the-art approaches. Overall, the paper is well-written, theoretically grounded, and provides valuable insights that advance the field. I recommend acceptance.
Decision: Accept (poster)