On the Scalability and Memory Efficiency of Semidefinite Programs  for Lipschitz Constant Estimation of Neural Networks
Authors: Zi Wang
Bin Hu
Aaron J Havens
Alexandre Araujo
Yang Zheng
Yudong Chen
Somesh Jha
Venue: ICLR 2024 poster (2024)
Keywords: Semidefinite programming
Lipschitz constant
Deep learning
Primary area: optimization
TL;DR: We scale the SDP for Lipschitz constant estimation to practical CIFAR10/ImageNet networks.

Abstract: Lipschitz constant estimation plays an important role in understanding generalization, robustness, and fairness in deep learning. Unlike naive bounds based on the network weight norm product, semidefinite programs (SDPs) have shown great promise in providing less conservative Lipschitz bounds with polynomial-time complexity guarantees. However, due to the memory consumption and running speed, standard SDP algorithms cannot scale to modern neural network architectures. In this paper, we transform the SDPs for Lipschitz constant estimation into an eigenvalue optimization problem, which aligns with the modern large-scale optimization paradigms based on first-order methods. This is amenable to autodiff frameworks such as PyTorch and TensorFlow, requiring significantly less memory than standard SDP algorithms. The transformation also allows us to leverage various existing numerical techniques for eigenvalue optimization, opening the way for further memory improvement and computational speedup. The essential technique of our eigenvalue-problem transformation is to introduce redundant quadratic constraints and then utilize both Lagrangian and Shor's SDP relaxations under a certain trace constraint.  Notably, our numerical study successfully scales the SDP-based Lipschitz constant estimation to address large neural networks on ImageNet. Our numerical examples on CIFAR10 and ImageNet demonstrate that our technique is more scalable than existing approaches. Our code is available at https://github.com/z1w/LipDiff.

Published as a conference paper at ICLR 2024
ON THE SCALABILITY AND MEMORY EFFICIENCY OF SEMIDEFINITE PROGRAMS FOR LIPSCHITZ CONSTANT ESTIMATION OF NEURAL NETWORKS: SCALING THE COMPUTATION FOR IMAGENET
Zi Wang"*, Bin Hu Aaron J Havens", Alexandre Araujo,, Yang Zheng', Yudong Chen', Somesh Jha Department of Computer Sciences, University Wisconsin-Madiion
2. CSL & ECE, University of Illinois Urbana-Chan Chhama-hhampaign ECE, New York University
4. ECE, University of California San Diego
ABSTRACT
Lipschitz constant estimation plays important role in understanding generaliza- tion, robustness, and fairness deep learning. Unlike naive bounds based on the network weight norm product, semidefinite programs (SDPs) have shown great promise in providing less conservative Lipschitz bounds with polynomial-time complexity guarantees. However, due to the memory consumption and running speed, standard SDP algorithms cannot scale to modern neural network architec- tures. this paper, we transform the SDPs for Lipschitz constant estimation into eigenvalue optimization problem, which aligns with the modern large-scale op- timization paradigms based on first-order methods. This is amenable autodiff frameworks such PyTorch and TensorFlow, requiring significantly less mem- ory than standard SDP algorithms. The transformation also allows us to leverage various existing numerical techniques for eigenvalue optimization, opening the way for further memory improvement and computational speedup. The essen- tial technique of our higenvalue-problen transformation is to introduce redundant quadratic constraints and then utilize both Lagrangian and Shor's SDP relaxations under a certain trace constraint. Notably, our numerical study successfully scales the SDP-based Lipschitz constant estimation to address large neural networks on ImageNet. Our numerical examples on CIFARIO and ImageNet demonstrate that our technique is more scalable than existing approaches. Our code is available at https: /tttps://gituut com/ 21w/ LipDiff.
INTRODUCTION
The Lipschitz constant of neural network plays an important role in training stability (Miyato al., 2018), 8), robustness (Tsuzuku et al., 2018), and generalization (Bartlett et al., 2017). Given the fact that computing the Lipschitz constant of neural network NP-hard (Scaman & Virmaux, 2018), researchers have attempted to improve upon the naive norm product bound and devise methods to compute tighter and more efficient upper bounds to approximate this Lipschitz constant.
Recently, researchers have proposed use semidefinite programs (SDPs) to estimate the Lipschitz constant of neural networks (Fazlyab et al., 2019; Wang et al., 2022). LipSDP (Fazlyab et al., 2019) is among the first SDP-based conditions that used to estimate the Lipschitz constant of neural networks and has motivated numerous works on designing smooth network structures for achieving improved certified robustness (Araujo et al., 2023a; Wang & Manchester, 2023; Havens al., 2023; Fazlyab et al., 2024). Wang et al. (2022) have drawn the connections between the Lipschitz constant estimation problem and the matrix mixed norm problems, and hinted that semidefinite programming
Equal contribution.

---

Published as a conference paper at ICLR 2024
is likely the optimal method to estimate the Lipschitz constant within polynomial time assuming standard complexity theoretical conjectures.
Though SDPs are convex programs and can be solved by interior point methods (IPMs) within polynomial time (Ben-Tal & Nemirovski, 2001), the memory requirement of IPMs is enormous. Consequently, LipSDP cannot scale to modern neural network architectures, which contain at least thousands of neurons. Currently, general-purpose SDP solvers are not capable of addressing the scalability issue of LipSDP, placing significant hurdle for practical use of such methods. Recently, researchers have studied how to improve the scalability of LipSDP (Xue et al., 2022; Newton & Papachristodoulou, 2021). These methods mainly exploit the chordal sparsity contained in SDPs (Zheng et al., 2021). Chordal sparsity allows us to decompose a large SDP constraint to a set of smaller and coupled ones which might be more scalable to solve; see Zheng et al. (2021) for a recent review. However, these methods still cannot scale to practical networks on CIFARIO or ImageNet.
In this work, we aim to address the memory efficiency and scalability of LipSDP. Instead of ex- ploiting chordal sparsity, we transform the SDP-based Lipschitz constant estimation into an eigen- value optimization problem using exact penalty methods (Ruszczynski, 2011) and redundant trace constraint arguments (Liao et al., 2023). Our nonsmooth eigenvalue perspective is motivated by Dathathri et al. (2020) as well as the advances in large-scale SDP optimization using spectral bundle methods (Helmberg & Rendl, 2000; Ding & Grimmer, 2023; Liao et al., 2023). In addition to the eigenvalue problem transformation, we also provide several add-on techniques that enable faster eigenvalue estimation for SDPs induced from large networks and provide more effective strategies for initializing first-order subgradient methods. Previously, for large networks, we can only estimate the Lipschitz constant using the spectral norm product of weight matrices (Leino et al., 2021). With our initialization, we can recover this bound from the beginning of the iterative optimization process. In other words, we transform the Lipschitz constant estimation into an incremental optimization pro- cess, which is guaranteed to improve the spectral norm product and is convenient to terminate at any time. Our key contributions are summarized as follows.
We introduce an eigenvalue optimization formulation for LipSDP, which we call EP-LipSDP. Based on exact penalty methods, we add redundant trace constraints prove that EP-LipSDP is equivalent to LipSDP. We obtain the exact penalty parameter by properly introducing redundant quadratic constraints. EP-LipSDP has a special form such that first-order subgradient methods can be directly applied.
We propose a series of numerical techniques compatible with EP-LipSDP, such as eigenvector approximation, sparse matrix multiplication, and analytical initialization. These techniques fur- ther improve the speed and practical convergence of solving EP-LipSDP.
We implemented the algorithm as LipDiff and evaluated it on practical neural networks on CI- FAR10 and ImageNet. Notably, our numerical study successfully scales the SDP-based Lips- chitz constant estimation to address large networks on ImageNet. Our numerical examples on CIFAR1O 10 and ImageNet demonstrate that EP-LipSDP is more scalable than existing approaches.
2 RELATED WORK
The Lipchitz constant estimation of neural networks has been extensively studied in many recent works (Scaman & Virmaux, 2018: Fazlyab et al., 2019; Latorre al., 2020; Jordan & Dimakis, 2020; Wang et al., 2022; Chen et al., 2020; 2021; Pauli et al., 2024). This problem is in general NP-hard (Scaman & Virmaux, 2018; Jordan & Dimakis, 2020; Wang et al., 2022), and thus an exact estimation is infeasible in practice. It is more plausible to leverage approximations in convex forms such as LipSDP (Fazlyab et al., 2019; Wang al., 2022). However, a main issue for LipSDP is the lack of scalability to large networks. Recently, researchers have leveraged chordal sparsity to improve the scalability of LipSDP (Xue et al., 2022; Newton Papachristodoulou, 2021; Batten et al., 2021). Noticeably, such methods still cannot scale to networks on ImageNet CIFAR1O.
Interestingly, Dathathri et al. (2020) transformed the SDPs designed for neural-network local robust- ness verification (which is a different problem from Lipschitz constant estimation) into eigenvalue problem that can be solved using subgradient methods. Our approach is inspired by Dathathri et al. different problem, namely Lipschitz constant estimation. We develop new
(2020), and focuses optimization techniques tailored specifically for Lipschitz constant estimation, which enables any- time termination with quality guarantee.
2

---

Published as a conference paper at ICLR 2024
It is worth mentioning that there have been significant research efforts improving the scalability of general SDPs via first-order methods (Wen et al., 2010; O' O'donoghue et al., 2016; Zheng et al., 2020: Garstka et al., 2021); see Majumdar al. (2020) and Zheng et al. (2021) for recent surveys. The formulation in this paper closely follows the nonsmooth eigenvalue perspective pioneered by Helmberg & Rendl (2000). This nonsmooth perceptive is well-suited for applying first-order meth- ods, from vanilla subgradient methods and cutting plane techniques to sophisticated bundle methods (Lemarechal & Zowe, 1994). Helmberg Rendl (2000) developed special class of spectral bundle methods for solving the nonsmooth eigenvalue formulation of dual SDPs with constant trace con- straints. Further developments appeared in Helmberg Kiwiel (2002) and Helmberg et (2014). The constant trace property has also been investigated in polynomial optimization literature (Mai et al., 2022). Very recently, comprehensive convergence rates of spectral bundle methods have been established in Ding & Grimmer (2023), and a comparison of spectral bundle methods for primal and dual SDPs is discussed in Liao et al. (2023).
Built upon LipSDP (Fazlyab al., 2019), several works (Araujo et al., 2023b; Wang & Manchester, 2023; Havens et al., 2023) have also developed direct parameterizations
SDP-based Lipschitz network layers. This allows the design of specific network structures with prescribed Lipschitz guarantees, leading to non-trivial certified robust accuracy. It is possible that our proposed analysis method can be used to develop less conservative Lipschitz network structures in the future.
BACKGROUND
Notation. We denote the x identity matrix and the n X zero matrix Luxa and 0,xns respectively. We will omit the subscripts when the dimension is clear from the context. Given a vector u, the notation 2 0 means that all the entries of non-negative. We denote the i-th entry of y as oz In addition, we use the notation diag(v) to denote the diagonal matrix whose (i, th entry is equal to For a vector ||||| denotes the Euclidean norm of v, i.e., ||a||| = V For matrix M, we use || denote the operator norm, i.e., the largest singular value of M.
3.1 A BRIEF REVIEW OF LIPSDP
The LipSDP approach can formulated in either the primal or dual domain, leading to pair of SDP conditions for the Lipschitz constant estimation of general neural networks. The original LipSDP was developed in the dual domain (Fazlyab et al., 2019). The primal form of LipSDP was later discussed in Wang al. (2022: 2023). To illustrate different forms of LipSDP, we first consider the simplest single-layer neural network in the form of fxx) = vo + 80) (P]+ b', where x E IR"s, W Rax== 8 E R" v E Rlx= b² E R, and (xx R. Here f is scalar, and the neuron number. The activation a is assumed to be slope-restricted on [0, 1). In the dual domain, the LipSDP (Fazlyab al., 2019) is formulated as follows:
min C,r
S
CT
WT diag(r) diigg( + + 3 30,
(I)
subject to diag(r)
T T 0,
where 7 E R" and Ç E R are the decision variables. The original proof in Fazlyab et al. (2019) is based the quadratic constraint argument. Given two arbitrary x. x' E R== set o(Wr: 89) and z' = a (Wa' + BO). Denote Ar x' - and A = - =2 the matrix inequality (1) holds, must have
Ax Az
CI
W diag(T) diag(r) TT
Ax A
S
diag(r)
which is equivalent to
|| A= 1 - |
Ar
0 diag(r)W
WT diag(7)
Az Az
S O.
A
-2 diag(T)
The third term on the left side is non- non-negative since a is slope-restricted on [0. 1] (see Fazlyab et al. (2019, section 2.2) and Wang al. (2022, section for detailed explanations). Then the sum of
3

---

Published as a conference paper at ICLR 2024
the first two terms has to be non-positive, and one has || & Az]l Hence one just needs to minimize Ç subject to the matrix inequality (1).
In the primal side, let W, denote the i-th row of W, and one starts with the following problem
Ax
subject to (Az, W,Ar)Ar S O, Vi E [rs],
whose solution gives upper bound for the Lipschitz constant of f due to the fact that is slope- restricted on [0, IJ. Since scaling Ax and A by the same constant always maintains the constraint, one show that the solution for the above problem is further upper bounded by the optimal value of the following quadratically constrained quadratic program (QCQP):
max
vAz
subject
(Az; WaAr) $0, e [n] Ar $
Then Shor's relaxation of the above QCQP gives the primal form of LipSDP, which is the dual SDP of (I). Specifically, the dual program of Shor's relaxation (2) is the following SDP:
min 6.777
5
subject to
0
-7I
W diag(T) 30,
diag(T)W
-2 diigg(T))
2 0,
2 0, 2 0.
which can be shown to give the same Lipschitz upper bound as (1) via Schur complement and some rescaling arguments'
The primal and dual forms of LipSDP give the same solution. One can also modify the above arguments to connect the primal and dual LipSDP forms for the more general case where is multi-layer network with a vector output. In this paper, will show that the solution to the original LipSDP for multi-layer networks (Fazlyab al., 2019, Theorem 2) can be recovered by another optimization problem that can be efficiently solved using first-order methods.
4 MAIN THEORETICAL RESULTS
The semidefinite constraint in LipSDP is non-trivial to deal with for large-scale problems. One com- mon idea for improving scalability and memory memory-efficiency the cost function via the exact penalty method (Ruszczynski, 2011). In this section, we derive the exact penalty form LipSDP (termed as EP-LipSDP). We show that EP-LipSDP and LipSDP have the same solutions. In addition, EP-LipSDP is an optimization problem with only box constraints and hence can be efficiently solved using first-order methods. To illustrate the essence our tech- nique, we first present EP- LP-Lip for the single-layer setting reviewed in Section 3.1. After that, we present EP-LipSDP for the multi-layer network case.
move the semidefinite constraint into
4.1 EP-LIPSDP FOR SINGLE-LAYER NEURAL NETWORK
Recall that we have f(x vo bD) +b where E Th W RR 80 E R" Rlxn E R. and f(x E R. The neural network f "== - R, has n neurons, and a is assumed to be slope-restricted on [0, 1]. For now, we consider the output dimension of f to be Due the page limit, the discussion on the vector output case is deferred to Appendix F. naive way to transform LipSDP to penalty form move the semidefinite constraint in 1) the cost:
WT diag(r) -2 uT 1):
+ S+pAit 220
min
Notice that the network is $ L-Lisschitz if the semidefinite constraint in (3) is feasible. Hence the optimal value of (3) corresponds to the product of 2 and the square root of the optimal value of (1). For completeness, include detailed proof in Appendix F. Some related arguments also given in Wang al. (2022; 2023).

---

Published as a conference paper at ICLR 2024
where M max(O, Amax (-)) with (max(.) denoting the maximum eigenvalue, and p > is a penalty parameter (Ruszezynski, 2011, Theorem 7.21). One can then apply first-order methods to solve this new nonsmooth optimization problem (4). However, crucial issue is that it is unclear how large the penalty parameter p has to be such that (4) and (1) can yield the same solution. The key issue here is that the dual form of (1) (which is the Shor's SDP relaxation of (2)) does not have an explicit trace constraint. Based on the discussion in (Liao et al., 2023, Section 3.2), redundant trace constraints may be used to derive the exact penalty form of SDPs. Next, we will enforce redundant trace constraint on the dual program of (3) to derive the exact penalty form of LipSDP.
We need to introduce an explicit trace constraint to the dual program of (1) without affecting its solution. We start by adding redundant constraints into (2) such that its Shor's SDP relaxation has an explicit trace constraint. Specifically, the constraint in (2) already states || S 1. Augmenting
the inequality (Az; - W,Ar) I 0 leads to a redundant constraint A S |W,r I ||Willop
(one interpretation for this redundant constraint is that a is slope-restricted on [o. 1] and hence has to be I-Lipschitz). Therefore, the following QCQP is feasible if and only if (2) is feasible:
max
vAz
subject
(Az; WaAr)Az S S0, Vi [n]
(5)
|xx] I 1
227 S || Vi E [n].
Denote a; = =|lWallop Then Shor's SDP relaxation of (5) has an explicit trace constraint 1+ || 2
| s 2 Σi= aj. One can verify that the dual the Shor's SDP relaxation of (5) reads as
min CAiITY
S
Σ
asdg +7-5 0
V WT diag(r) diag(T)W -2 diag(T) diag(A)
0
subject to
-71
1 0,
(6)
620 2 0, 7 O.
Here E R" corresponds to the slope-restricted property, X R" corresponds to the redundant constraints A2? s ||W:l12 and y corresponds to the constraint || || l2 S 1. Comparing (6) with (3), the only difference is that the redundant variable shows up in the (1, 1)-block and (3, (3,3)-blockk Intuitively, since the dual program of (6) has an explicit trace constraint, the penalty formulation of (6) will be exact; see (Liao et al., 2023, Section 3.2) for discussions. For simplicity, we define
ag 2,2g +
0
C=
0
W diag(r) diag(T)W -2 diag(r) diag(A)
-
T
Now we can transform (6) to its exact penalty form, leading to the following EP-LipSDP:
S+ 22+ +2(2+ Σ a3) Eas)attnm X (C).
min 220.220720.200
(7)
1=1
The penalty parameter is set as 2 + Σ}= aj. which is the trace bound in the dual SDP of (6). The dual programs of (6) and (3) differ by only redundant trace constraint. Hence EP-LipSDP (7) and the original LiPSDP (1) give the same Lipschitz bounds. This leads to the following main result.
Theorem 1. Let opt, be the optimal value of Problem (6) and opt, be the optimal value of Problem (7). In addition, let opt, be the optimal value of the original LipSDP (1). We have opt, = opt.2 = 2 /opt, Therefore, all three programs give the same Lipschitz bounds.
The detailed proof of the above theorem is presented in Appendix A. The nonsmooth problem (7) can be solved via subgradient methods and bundle methods (Helmberg & Rendl, 2000; Ding & Grim- mer. 2023; Liao al., 2023). In our case of Lipschitz constant estimation, we can utilize autodiff frameworks such as Py PoToc to get (sub)gradients of the cost function (7). Thus, this eigenvalue transformation opens the door applying modern machine learning architectures and first-order techniques based on sparse eigen-solvers and iterative subgradient methods. Finally, if we increase the penalty parameter such that p > 2 Σ)= aj. then we can ensure that the solutions (not just the optimal values) of (6) and (7) are equivalent. See Appendix A for detailed discussion.
5

---

Published as a conference paper at ICLR 2024
4.2 EP-LIPSDP FOR MULTI-LAYER NEURAL NETWORKS
Next, we present the result for the general multi-layer case. For ease of exposition, we still consider the scalar output case. The extension the vector output is explained in Appendix F. Specifically, consider a multi-layer network:
(0) I. (())) (( + B(k-1)) h: == d, f(x) = (x) + b(4)
(8)
Suppose FA " Again, consider the case that is vector and f is scalar output. The original LipSDP has the following form:
min (((7("))=
subject to Aę- = (iag(((()),
-(0)
2 0,
7(0) E R (20,
CER,
-SI
(W(O))
0
0
1
-2A1
0
( Ad-1
0
I 0.
A
2A AdW(d-1)
(W(d-1)TA Aa
0
-24 + v.v
99)
Similar to the equivalent relationship between (1) and (3), we can show that the following SDP can give the same Lipschitz bound (9):
min 12-1
(
subject to
(20
0,
720,
As diag(r())),
(k) 0,
7()) RR for k = 1, ...
5
0
0
-
(W(0))AA
0
0
A₁ (())
-211
3 0.
0
(W(d-2))TA. Ad-1
0
Ad- (dd22
2AA-1 AqW(d-1)
(W(d-1))TA,
T
0
-2Aa
(10)
Notice (10) can be viewed as the multi-layer extension of (3). Denote the i-th row of W as (R)
For k: 1,... d, denote Ckj | (II-> [| for j 1,... ng. Then
can use the same argument for the single-layer case to show that 2 + Σi=1 Σ}= Ckj provides an explicit redundant trace constraint the multi-layer QCQP, and hence can be used to derive the exact penalty formulation of the multi-layer LipSDP. Specifically, we define S₁ diag(A (A0) with (k) 2 0 being vector in R Then define
En. Ckj
0
-
(W(O))TA)
0
0
A (0))
2A - S1
C=
(W(d-2) (y(d-2))AAd-1 Ad-1
-7 Sd
(W( Ad
T
0
(d-(d-1)
-2A4
Sa
(11)
With the above choice of C, we can immediately show the following EP-LipSDP for the multi-layer network case:
n& S (2+ Σ Σ
min
Cks
A (C).
(12)
220,
k=1

---

Published as a conference paper at ICLR 2024
Now can use similar proof for Theorem 1 to show the following result for multi-laye networks.
Theorem 2. Let 4 be the optimal value of Problem (10) and opt, be the optimal value of Problem (12). In addition, let opt. be the optimal value of the original LipSDP (9). We have opt, = opts 2oop other words, all three programs give the same Lipschitz bounds.
The proof is similar to the one of Theorem presented in the appendix. Now we have obtained the exact penalty form of LipSDP which can be solved using first-order methods.
5 ADD-ON TECHNIQUES FOR LMPROVING PRACTICAL PERFORMANCES
In this section, we discuss a few techniques that can further improve the performance in terms of running time and practical convergence of first-order algorithms for solving EP-LipSDP in Section 4.
Eigenvalue approximation. We formulate the Lipschitz constant estimation as an eigenvalue op- timization problem that is differentiable almost everywhere. Consequently, estimating the extreme eigenvalue of a given matrix becomes important sub-task. There exist various efficient algorithms to estimate the extreme value of a given matrix, and the efficiency can significant improved via compromising the precision little bit. In this work, we also consider the Lanczos algorithm (Lanc- zos, 1950) to compute the largest eigenvalue of a matrix as in Dathathri et al. (2020). Lanczos algorithm is iterative algorithm used to find the extreme eigenvalues of symmetric matrices. It computes a small sub-matrix whose extreme eigenvalues are close to those of the original matrix. One can specify the size of the sub-matrix. The larger the submatrix is, the closer the eigenvalue is to the original value with a cost of higher computational resources.
Sparse matrix multiplication. When using the Lanczos algorithm compute the extreme eigen- value of matrix A, we only need access - Ax, instead of the explicit form of A. That is, we only need to know what Ax for any vector æ. This provides further optimization opportunities when using the Lanczos algorithm. The matrix considered in this work has fixed sparse pattern, ie., it is almost a tridiagonal matrix, which encodes the computation of the (convolutional) neural network. For deep/wide (convolutional) networks, the SDP constraint matrix is very sparse. Thus, we can implement a native sparse matrix multiplication routine, which can significantly improve the efficiency of method in addressing large networks on CIFAR10 10 and ImageNet.
Analytical initialization. Theoretically, we can initialize the variables of our first-order iteration randomly and apply (sub)gradient method for infinitely many steps with sufficiently small step size (learning rate) to ensure the convergence to the global minimum. In practice, we can only run the first-order subgradient method for finitely many steps. To ensure that our first-order method is better than the naive matrix norm product bound, we develop a special analytical initialization scheme. Specifically, we derive specialized analytical solution to (11), which exactly recovers the naive norm product bound. This analytical solution is then used to initialize Consequently, EP-LipSDP with such an initialization produces at least as tight Lipschitz bound as the matrix norm product. To derive this analytical initialization, ment lemma and the block matrix inversion formula. The details are presented in Appendix B.
subgradient method.
mainly the Schur comple-
EVALUATION AND DISCUSSION
In this section, we conduct several experiments to empirically evaluate the algorithm proposed in this work. The evaluation aims to answer the following research questions: (R1) Does EP-LipSDP produce the same value as the original LipSDP when both problems are fully solved? (R2) Does our algorithm possess running time and memory advantage compared to LipSDP? (R3) How does each add-on technique from Section 5 contribute the overall performance of EP-LipSDP?
Based on the PyTorch package, we developed first-order implementation of EP-LipSDP, termed as LipDiff. The pseudocode is described in Appendix We use the ADAM optimizer (Kingma & Ba. 2015) as LipDiff's 's gradient descent optimizer and tune the number of gradient steps and step size (learning rate) accordingly for each problem. We also implemented the following variants (the details of these variants can be found in Appendix D):
1. LipDiff-Ex is the algorithm using exact eigenvalue instead of the Lanczos approximation.

---

Published as a conference paper at ICLR 2024
Table 2: In this table, we present results comparing different variants of our approach to LipSDP. In MNIST-DNN experiment, if we compare the benchmark values from LipSDP and LipDiff-Ex, we can find that their values are very close. By tuning the parameters, we can get results fairly close to LipSDP value in a much shorter time. For MNIST-CNN, the SDP constraint size is of 4021 x 4021 and the Mosek solver used for Lip triggers the out-of-memory (OOM) error, while all other LipDiff variants can still run. Furthermore, LipDiff-Ex can reduce the Lipschitz constant estimation by 48% compared to the norm product method. For CIFARIO-CNN, LipDiff can reduce the Lipschitz constant by 58% compared to the norm product.
Datasets
Models
Product
LipSDP
LipDiiT
LipDitV-Ex
LipDiff-Dense
LipDiff- Rand
Result
9.31
4.82
4,90
4.86
4.96
5.89
MNIST
DNN
Time (8)
0.13
54.57
28.69
19.27
12.48
29.27
Memory (MB)
1.54
169.83
118
114
114
118
Result
24.79
0OM
14.76
13.08
14.66
2201.66
MNIST
CNN
Time (s)
0.16
178.99
559.08
185.34
186.89
Memory (MB)
18.77
2640
1534
1536
2640
Result
35.45
00M
14.82
18.52
12
1731.82
CIFARIO
CNN
Time (8)
98.08
2777.07
36000
25126.01
2723.02
Memory (GB)
0.51
60.05
51.39
51.41
60.05
2. LipDiff-Dense implements the Lanczos algorithm with explicit matrix multiplication.
3. LipDiff-Rand initializes the algorithm from a random initialization rather than the analytical solution and also implements the Lanczos algorithm in the sparse matrix multiplication way.
Baseline. We use two main baselines: 1. Product, the weight matrix norm product, which provides a naive upper bound for the Lipschitz constant of the neural network, and is currently the only method for large networks on ImageNet (Leino et al., 2021; Hu et al., 2023); 2. LipSDP (Fazlyab et al., 2019), which is implemented using the CVXPY package (Diamond & Boyd, 2016) and relies on the Mosek solver (ApS, 2019) to solve the SDP. In our experiments, the LipSDP implementation is run on CPU. In contrast, the LipDiff variants are GPU-friendly, and hence run on GPU.
First Part of Experiments: MNIST and CIFAR10.. To provide good sanity checks, we first run our algorithms on three networks: 1. an MNIST (LeCun & Cortes, 2010) dense network, with a single hidden layer of 128 ReLU nodes; 2. An MNIST convolutional network, with convolutional layer, and 2 fully connected layers; 3. CIFARIO convolutional network with 3 convolutional layers and fully connected layers. These networks are summarized in Table 1.
Each of the networks has 10 classes. We will compute the Lipschitz constant of the function corresponding to 8th label as in the evaluation of Wang et al. (2022). For the evaluation, we set the timeout for each experiment to be 10 hours. If the running time is over 10 hours, we will terminate the program and report the best number. To answer RQI and RQ2, we will compare the performances of LipSDP and LipDiff variants in terms of the results, and memory and running time needed for the computation. To answer RQ3, we will compare the results of LipDiff variants. The results of the evaluation for this part are summarized in Table 2.
Table 1: Models used for the experiments.
Model
Structure
Parameters
Act.
SDP size
MNIST-DNN MNIST-CNN CIFARIO-CNN
ITC
203-530
97%
1041
1041
IC2FC
314982
98%
x 4021
3C3FC
1 131
80%
22
529
22 529
RQ1. If we compare the result for MNIST-DNN in table 2, we can find that LipDiff-Ex computes almost the same value as LipSDP does. In addition, LipDiff and LipDiff- Dense produce similar results as LipSDP's value. These results provide an affirmative answer to RQ1, that our eigenvalue optimization formulation gives the same value as LipSDP, as showed in Theorem 1.
RQ2. In terms of memory consumption, because LipDiff variants are run on GPU while LipSDP run on CPU with different package implementations, direct comparison between the numbers is not sensible. However, we can still compare between experiments. Recall that the SDP constraints for MNIST-DNN, MNIST-CNN and CIFAR 10-CNN are of sizes 1041 x 1041, 4021 x 4021 and 22529 x 22529. As we can observe from Table 2, the memory consumption for LipDiff roughly scales linearly to the size of the SDP constraint. However, for LipSDP, the memory requirement is much more beyond linear. For example, the total memory of the server is 528 GB, 4000 times larger than 118 MB, and LipSDP cannot even work network with the SDP constraint size 4021 x 4021,
8

---

Published as a conference paper at ICLR 2024
MNIST-CNN
CIFAR-CNN
30
40
LpDrf
Lip Rand
LipDiff
LigDiffRRnd
25
LipDitt-Rand (logscale)
10
Lip (logscalo)
20
25
LipOiff
LiDD
10
20
15
10
10
10
5
5
0
10
10"
292
2300
1250 1750
(a)
(b)
Figure 1: These plots show the minimization of LipDiff' and LipDiff- on MNIST-CNN Fig- ure Ia and CIFAR-CNN models Figure lb. The left axis of each plot shows LipDiff (blue) and the right axis shows LipDiff-Rand (orange) in log scale. The x-axis describes the number step of the optimization. We observe that LipDiff obtains a much lower value than LipDiff- LipDiff-Rand due to its bet- ter initialization. Additionally, LipDiff shows sharp decrease at the beginning the optimization, making it an efficient method for improving over the product bound when the time budget is limited.
which is roughly 16 times larger than the MNIST-DNN. This comparison establishes the memory efficiency of LipDiff. For running time, because we can tune the number of steps and step size for gradient descent, we can obtain fairly decent result within a short time. This tuning process offers more flexibility than closed-form solver.
RQ3. From all experiments in Table 2, we can draw a conclusion that with the analytical solution initialization, LipDiff is consistently better than LipDiff-Rande This is particularly true when the network is large and it is hard for the subgradient method from a bad initial state to converge with many free variables. For approximating extreme eigenvalue using the Lanczos algorithm, we always save significant running time, at a price of a little potential precision loss. When using the sparse matrix representation for matrix multiplication. the benefit is only significant when the network is large enough. For small networks such as the MNIST DNN, matrix multiplication using dense representation is faster than the sparse representation. The reason is that for small networks, the SDP constraint is almost always dense rather than sparse. However, at the scale of the CIFARIO network, the sparse matrix multiplication can save almost 90% of running time. For memory consumption, we can consistently find that LipDiff-Ex uses least memory and LipDiff uses the most. This comes from our design choice: For the implementations using Lanczos algorithm approximate the maximum eigenvalue, we also include the original constraint to compute the exact eigenvalue. Therefore, the Lanczos tools would compute an extra Lanezos submatrix. The sparse representation will further implement an additional sparse multiplication routine and thus consume even more memory.
Second Part of Experiments: ImageNet. To fully test the scalability of our proposed method, additionally applied LipDiff on the pretrained AlexNet (Krizhevsky al., 2017), which was designed for ImageNet classification (Deng et al., 2009). AlexNet is composed of a feature ex- traction sub-network and classification sub-network. Noticeably, AlexNet is much larger than all the MNIST/CIFARIU 10 networks considered in our previous experiments. To address a network at this scale, we need combine all the add-on techniques in Section Importantly, we use the sub-m cobb-iipiplcctyy of norms to decompose AlexNet, and apply LipDiff on the sub-networks, which eventually reduces the total Lipschitz constant of AlexNet by 73%, compared to the matrix norm product bound. To the best of our knowledge, this is the first time that LipSDP is successfully scaled to ImageNet. More details of our ImageNet experiments can be found in Appendix H.
Conclusion.
Overall, we can conclude that LipDiff' is much more memory- than the original default interior point implementation tion, it is hard for LipDiff to converge from random initialization. With all the add-on techniques proposed in our work, for the first time, we can estimate the Lipschitz constant of large networks on CIFAR10 and ImageNet, and this estimation is always at least as good as the naive matrix norm bound. Our algorithm can terminate at any time, which further offers more flexibility for users with different time budgets.
LipSDP. However, without our specialized analytical solu-

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
Z. Wang and S. Jha are partially supported by DARPA under agreement number 885000, NSF CCF- MMiTF--13699 and ONR N00014-21-1-2492. Havens and Hu are generously supported by the NSF award CAREER-2048J00 and the AFOSR award FA9550-23-1-0733 Y. Zheng is partially supported by NSF ECCS-2 2154500 and NSF CMMI-2320697. Chen partially supported by NSF CCF-1704828 and NSF CCF-2233152.
REFERENCES
MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019. URL http://doct //tcs///ccs./ooo mosek. http//////ooooooo///////o wtttoooooo/..neee..ooo///eeee/ee html.
Alexandre Araujo, Aaron J Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A uni- fied algebraic perspective lipschitz neural networks. In The Eleventh International Confer- ence on Learning Representations, 2023a. URL https: https://apenreviee. /wwp//pppeeeeeeeeeeeeee net/ forum? ddd=
k71IGLC8cfc.
Alexandre Araujo, Aaron J Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A uni- fied algebraic perspective on lipschitz neural networks. In The Eleventh International Confer- ence on Learning Representations, 2023b. URL https:://///.. /wwp//ppwwwwww.coo//// net/ www.:nnnttnooooeeeeem forum?id- k71IGLC8cfc.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalize margin bounds for neural networks. In Guyon, U. Von Luxburg, Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL httppp::/ppocceeeeettttttt newripss.......................m wwwpuurrisscccppppeeeo cc/paper pdf.
files
Ben Batten, Panagiotis Kouvaros, Alessio Lomuscio, and Yang Zheng. Efficient neural network verification via layer-based semidefinite relaxations and linear cuts. In Zhi-Hua Zhou (ed.), Pro- ceedings of the Thirtieth International Joint Conference on Artificial Intelligence IJCA/-21, pp- 2184-2190. International Joint Conferences on Artificial Intelligence Organization, 8 2021, doi: 2224966/jcaii222213000 URL https:///oii: Track.
2021 301. Main /tt.//oiiio//// wttp:/iooor/..2//././. 2etpr//.....449//11 2021
Aharon Ben- Tal and Arkadi Nemirovski. Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics, 2001. doi: 10.1137/1 1911177711.7888888888888,, URL https://
epubs. siam. oogooo/g/oooooo. /owi/aaaaaao 113.7.1.111111111 httpp//....1331.179988877770880 07w.119998899999999.
Tong Chen, Jean-Bernare Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimiza- tion for lipschitz constants of relu networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Asso-
ciates Inc. ISBN 9781713829546.
Tong Chen, Jean I Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic representation of monotone deep equilibrium models and applications to certification. Advances Neural In- formation Processing Systems,
2021.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Ue- sato, Rudy R Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy S Liang, and Pushmeet Kohli. Enabling certification of verification-agnosiic networks via memory-effiiiee semidefinite programming. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5318-5331, Cur- ran Associates, Inc., 2020, URL htwp:::ttt//ttt http::::ss////pcpeeeeeeee .ww.riinnnnnnnnnnnnoeeeeee....ee htt.pp.cc//eeee cctppppee/02./////////// pdf..
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10.1 0WW./CCVR.2009.5006222.
10

---

Published as a conference paper at ICLR 2024
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
Lijun Ding and Benjamin Grimmer. Revisiting spectral bundle methods: Primal-dual (sub) linear convergence rates. SIAM Journal on Optimization, 33(2):1305 303--332, 2023.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pap- pas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Н. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: http:: http::::///cpceedeeeeeeoooo newriineursssp.. wew1133ebbb2037777743535
wwweurpps.ccppppereeeeeeee wttpcc/pppe//////1/222... pdf.
fab
Mahyar Fazlyab, Taha Entesari, Aniket Roy, and Rama Chellappa. Certified robustness via dynamic margin maximization and improved lipschitz regularization. Advances Neural Information Processing Systems, 36, 2024.
Michael Garstka, Mark Cannon, and Paul Goulart. COSMO: A conic operator splitting method for convex conic problems. Journal of Optimization Theory and Applications, 190(3);77--810, 2021.
Aaron Havens, Alexandre Araujo, Siddharth Garg, Farshad Khorrami, and Bin Hu. Exploiting nections between Lipschitz. structures for certifiably robust deep equilibrium models. Advances in Neural Information Processing Systems, 36, 2023.
Christoph Helmberg and Krzysztof C Kiwiel. A spectral bundle method with bounds. Mathematical Programming, 13399173-- 2002.
Christoph Helmberg and Franz Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10(3):673 696, 2000.
Christoph Helmberg, Michael I. Overton, and Franz Rendl. The spectral bundle method with second- order information. Optimization Methods and Software, 29(4):855-877 2014.
Kai Hu, Andy Zou, Zifan Wang, Klas Leino, and Matt Fredrikson. Unlocking deterministic robust- ness certification on imagenet. Advances Neural Information Processing Systems, 36, 2023.
Matt Jordan and Alexandros Dimakis. Exactly computing the local lipschitz constant of relu networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 7344-7353, Curran Asso- ciates, Inc., 2020. URL https: htttps::/pproceedingss neurips. wtt.ccc/ppppee wttp//appe//20///e//eee 5227 9a1 71teeeeeeae111111000111
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URI. http: //aaxiiv.rrg///.e.l............e abs 11121411220 6980.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep con- volutional neural networks. Commum. ACM, 60(6):84-90 90, may 2017. ISSN 0001-0782. doi: 10. 10.1145/3065386. URL wwt.h:tt///// //t:i org/10. 1145533000 /145/365388.
Comelius Lanezos. An iteration method for the solution of the eigenvalue problem of linear differ- ential and integral operators. 1950.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Representations, 2020. URL https: http://pppwteeeeeeeeeeeeee net wewee//oorriddrrrteeoee
XBFDB.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URLhttp://yann: lecun. com exdb /ntp///nn//....mmmm
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference Machine Learning (ICML), 2021.

---

Published as a conference paper at ICLR 2024
Claude Lemarechal and Jochem Zowe. A condensed introduction to bundle methods in nonsmooth optimization. In Algorithms for continuous optimization: the state of the art, pp. 357-382. Springer, 1994.
Feng- Yi Liao, Lijun Ding, and Yang Zheng. An overview and comparison of spectral bundle meth- ods for primal and dual semidefinite programs. arXiv preprint arXiv:2307.0765) 2023.
Ngoc Hoang Anh Mai, J. B. Lasserre, Victor Magron, and Jie Wang. Exploiting constant trace property in large-scale polynomial optimization. ACM Trans. Math. Softw., 48(4), dec 2022. ISSN 0098-3500. doi: 10.1 10.1145/555309 URL ht http///oiiooo wtt.:///..........11.
Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Annual Review of Control, Robotics, and Autonomous Systems, 3:331-360, 2020.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 2018.
Matthew Newton and Antonis Papachristodoulou. Exploiting sparsity for neural network veri- fication. In Ali Jadbabaie, John Lygeros, George J. Pappas, Pablo Parrilo, Benjamin Recht, Claire Tomlin, and Melanie N. Zeilinger (eds.), Proceedings of the 3rd Conference on Learn- ing for Dynamics and Control, volume 144 of Proceedings of Machine Learning Research, pp. 715-727. PMLR, 07 - 08 June 2021. URL https: newton21a html.
htt.tttss:/pprocee /ptp:ce///ceeeeeee ang.mllmle ml paal..press/v144.
Brendan O' O'donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applica- tions, 169:1042-1063 2016.
Patricia Pauli, Aaron J Havens, Alexandre Araujo, Siddharth Garg, Farshad Khorrami, Frank Allgöwer, and Bin Hu. Novel quadratic constraints for extending lipsdp beyond slope-restricted activations. In The Twelfth International Conference on Learning Representations, 2024.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances in neural information processing systems, 31, 2018.
Andrzej Ruszezynski. Nonlinear optimization. Princeton university press, 2011.
Kevin Scaman and Aladin Virmaux.
Lipschitz regularity of deep neural networks: Analysis and efficient estimation. Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18. pp. Inc.
Red Hook, NY, USA, 2018. Curran Associates
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certi- fication of perturbation invariance for deep neural networks. Advances in neural information processing systems, 31, 2018.
Ruigang Wang and Ian Manchester. Direct parameterization of lipschitz-bounded deep networks. In International Conference on Machine Learning, pp. 36093-361 10. PMLR, 2023.
Zi Wang, Gautam Prakriya, and Somesh Jha. A quantitative geometric approach neural-netword smoothness. In Thirty-Sixth Conference on Neural Information Processing Systems, 2022. URL net
https://cpenree wwwp://wwwweeeetttteeeeeeeeee porrummddd2opppaaiii
Zi Wang, Somesh Jha, and Krishnamurthy (Dj) Dvijotham. Efficient symbolic reasoning for neural-
network verification. arXiv preprint arXiv:2303. /3588, 2023.
Zaiwen Wen, Donald Goldfarb, and Wotao Yin. Alternating direction augmented lagrangian meth- ods for semidefinite programming. Mathematical Programming Computation, 2(3-4):203-233) 2010.
12

---

Published as a conference paper at ICLR 2024
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 st Conference Decision and Control (CDC), pp. 3389-3396, 2022. doi: 10.1109/CDC51099. 2022.9992 0022.9993136.
Richard Zhang, On the tightness of semidefinite relaxations for certifying robustness to adversarial examples. Advances in Neural Information Processing Systems, 33:3808-3888 2020.
Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. Chordal decomposition in operator-splitingg methods for sparse semidefinite programs. Math- ematical Programming,
2020.
Yang Zheng, Giovanni Fantuzzi, and Antonis Papachristodoulou. Chordal and factor-width decom- positions for scalable semidefinite and polynomial optimization. Annual Reviews in Control, 52: 243-279, 2021.
13

---

Published as a conference paper at ICLR 2024
A TECHNICAL PROOFS
In this section, we provide a detailed proof for Theorem
Proof. We first prove opt < - This direction is straightforward. Suppose that optimal solution to Problem (6) is A", :")). By definition, this solution is also feasible to Problem (7). Furthermore, the corresponding matrix C' 0, and thus (C) = O. Hence have opt, opt
Next, we prove opt, I optz. Suppose an optimal solution to Problem (7) is (C - -0:70) this solution makes the corresponding matrix C 3 O, then it is also feasible Problem (6) with the same cost value _ In this case, we have opt, S optz. If Amax
> 0, then this solution is feasible Problem (6). However, we can construct another optimal solution by exploiting the structure of C. Specifically, we choose
7 - aa, X = -²= (2 _ a2)a, 7'=
(13)
We show that this new solution is optimal for Problem (7) and also feasible for Problem (6). Denote A1 = diag(r'), 2/2 = diag(X'). AQ diag(r"), ), and Ag = diag(>"). Recall the structure of C' and have
az
-1'
W A 2 N/1
NWW
Σ aj
m
10 0
5"
0
1
W AT
aI 0.
T
A
22 - Ag
Thus, the new solution in (13) feasible for Problem (6). Furthermore, is easy to verify that the ) in Problem (7), which is
new solution in (13) has the same cost the solution ( 77, Xo, ,0,7")
s' 5 + 2 Σ aj)a.
2 2
1=1
We thus also have opt; S opt2-
The proof of opt; 2 optz be seen from the equivalence of various forms of LipSDP, i.e. SDP forms (I), (3), and (6). See detailed proof for the equivalence of (1), (3), and (6) in Appendix E. Now our proof is complete.
Upon choosing > 2+ Ej=1 a as the penalty parameter in Problem (7), one can further show that any optimal solution to (7) makes the corresponding C < O, thus the second case in the proof above never happens. We put this result as lemma below.
Lemma Let > 2 + Ei= Oj as the penalty parameter in Problem (7). Then any optimal solution to (7) makes the corresponding C' 3
Proof. Let (C,, ,0, 70) be arbitrary optimal solution Problem (7). For the sake of deriving
contradiction, suppose the corresponding Co has Amax (C*) solution T', by
0. We construct another
m
ス' = 7 ta, = +a, 5²=50 +
Σ
ag + a. 4/ 7'= 70
(14)
j=1
Then the corresponding C" satisfies
1 a + + + 5
V
c²
-YI
WTAY
v
WW
22, No.
Σj a 1 70
5D
0
10
A
aT 3.
T
AQW
2A
Ag
14

---

Published as a conference paper at ICLR 2024
When p 2+ Σラ= aj. find that T',,,' ,') has the strietly lower cost than (5), 70, 20, ,0);))
- + p ( 2 j=1
m
5
2 + pa = -
Σ o a a+0
2 + p (C
which contradicts the optimality of (5 79, Xo 70) to Problem (7).
B ANALYTICAL SOLUTION FOR THE EIGENVALUE PROBLEM
Let us start with the two-layer network and derive an initial solution to the SDP problem (Equa- tion (7)). We use the SDP for two-layer network as example. Recall that
m
ajAÿ
==
WTA A 2A
0
W
2
where A, diag(r), and A₂ diag(A). Clearly, A2 comes from redundant constraints. Now can let À = 0, then we basically reduce C to a similar constraint of LipSDP, then we want to find an analytical solution to
S
V W A
C
0
I
3 30,
A,W
W
2AA
and minimize Ç.
I WA
-WTA] 2A1
Let A
By the Schur complement lemma, to have C 3 0, need A > 0 and
<-7- (0, v)) ((0, - 2 0. We use (A (A-1)22 denote the second row and second column block matrix of A-1 Again, by the Schur complement lemma, to have A > O, we need >> and
2A WW T W 2
We can set A₁ = aT, and 7 = |W
a²
WTW 2 a(2 71.
2al
b [
Then we need 25 a.
From the block matrix inversion formula, have
(A-))22 (2T TW WT/))--)
With the choice of A₁ and 7, we have
(A )22 llop 5 <(a(2 - 9))
b
a(bb a)
Then
v(A-1 122 5 a(b a
|||||
To have - 10---v(A1)) v(A-1) 2 0, we need
C-7 a(b a)
||0|| 2 2 0,
15

---

Published as a conference paper at ICLR 2024
then need
+ b
= b=bllWloo
a(2b a) 11012
We can let b
| [W ll
then we have
<= 2 llop ||/||
Because we will divide the by 2, this recovers the naive upper bound of &g Lipshitz constant: [[Wllap ||o]].
For general multi-layer networks, the derivation is essentially the same as the two-layer network case. It is a more careful recursive application of the Schur complement lemma and the block matrix inversion formula. Let three-layer network to illustrate the recursive structure for multi-layer networks.
We have
7 7-6 S
TI
W.A. A1
0
C
I 0
A W
-2A1
W2A2
T
A2W2
-2A
and minimize Ç.
Let
71
WTA
0 A2
C
W
2A1
0
A2
2A₂
and
7
-WTAI]
C2
A
2A1
Let
II
WTAA
0 0
A
W
A
0
0
and
0
0
0
A2 = 0
A1
W2AA2
0
A22W2
2A2
so A + A2
From the Schur complement lemma, we need
h-7- (0. 0
and C > 0.
To have Ci > O, we can have A and A2 > (we need at least one striet inequality, and our final assignment of the values will achieve this). To have Ai > O. we have y >> 0 and
A1 A N.WWWAA A1
We can set 7 a(IlWW llop [Wl 2 and A
W2 2 I:
1 W3 2
op W W > bl (1- b )
1 I
a W ll
To have A₂ 2 0, we need b > 0 and
2A₂ A2W, W2 W2A2/ A2W..W2A///
(b/ 0.
16

---

Published as a conference paper at ICLR 2024
We can set A2 cl:
W2 W2 = c(2 rr
2cT
b b 2
As result, only need s and S 26.
To have
5-7- (0.0 2
we need to use the block inversion formula:
|Cr (-2A, (0, (0
22 W/AA1///1))
[T 3a3 (2cl (A2 W WW
|| lasllop
[122d - (A2W2 - WT W/AAAWW/)/))WWWW..).. 2 WW2llop (2b ||22llpp || / /a)-
'llp 5 (2c
Notice that this has recursive inequalities to make the constraint work: || 1lop S <
To have
--r- v(T )arr vao 2 0,
only need
< -= [=a(lWWlloop | W12llop) + || (2c c² |W2llep (2b W2lll b2 || (a)-
We set = b = W. Wal This would recover the naive bound of || olop Wellop ||v||
[ell
More generally, we have general multiple- network, we only need to apply the Schur com- plement lemma and the matrix inverse formula recursively:
Σ
M +
0 I
V
WOA
0
T
0
Ad AW
-2Ag-1
S
We can set all S 0, and for each A,
IT d-1
c Wall where
n
|ill
7
[|a]] 1= ||Wallop and ( = 2 ||ll| m W|
C PSEUDOCODE OF LIPDIFF
Here we provide the pseudo-code of the LipDiff algorithm (Algorithm 1). Notice that one can substitute the direct ADAM optimizer with more complicated scheduling methods on learning rates and other optimizers such the stochastic gradient descent optimizer.
D OTHER EXPERIMENTAL SPECIFICATIONS
LipDiff variants specification. LipDiff uses all the optimization techniques proposed in Section 5. LipDiff-Ex uses the explicit matrix formulation to exactly compute the cigenvalue, thus it is dense representation, and also it applies the analytical initialization. LipDiff-Dens uses eigenvalue ap- proximation but implements it using dense matrix multiplication. LipDiff-Rand uses the sparse
17

---

Published as a conference paper at ICLR 2024
Algorithm The LipDiff Algorithm
Input:
The weight matrices [Wi] of a neural network.
Output: The Lipschitz constant the neural network.
Hyperparameters: Number of Iterations n; Lanczos steps I; Step size
1: Declare decision/dual variables in Equation (11) and assign their values according to Ap- pendix
2: Create ADAM optimizer for the dual variables with learning rate
3: for iterations do
4: Create the SDP constraint Equation (11) with [Wi] and the dual variables.
5: Compute the Lanczos submatrix L of size x I of C
6: Define the loss function Equation (12)
7: Compute the subgradient of the loss function via autodiff and update the dual variables
8: end for
9: Return the loss value
matrix multiplication to approximate the eigenvalue but initializes the algorithm with random as- signments. We made the following design choice: For the implementations using the Lanezos algo- rithm to approximate the maximum eigenvalue, we also include the original constraint to compute the exact eigenvalue, and all the reported numbers come from the exact eigenvalue.
Server specification. All the experiments are run on a server with thirty-two AMD EPYC 7313P 16-core processors, 528 GB of memory, and four Nvidia A100 GPUs. Each GPU GB of memory.
Training specification. We train all the networks with the SGD optimizer with a learning rate 0.02, momentum 0.9, and weight decay of 0.0008. We train MNIST networks for 50 epochs, and CIFARIO networks for 200 epochs.
LipDiff specifications. For LipDiff, we apply the interval scheduling of step sizes. We divide the number of iterations into groups. Within each group, we start from step size a and exponentially decay the step size to a/10.
For MNIST-DNN, we run LipDiff for a total of 1000 iterations, and divide the 1000 iterations into groups. The step size is initialized to 0.04. We use Lanczos steps 15.
For MNIST-CNN, we run LipDiff for a total of 2000 iterations, and divide the 1000 iterations into groups. The step size initialized 0.05. We use Lanezos steps 30.
For CIFAR10-CNN, we run LipDiff for total of 2000 iterations, and divide the 2000 iterations to groups. The step size is initialized to 0.06. We use Lanczos steps 50.
E ON THE EQUIVALENCE OF DIFFERENT FORMS OF LIPSDP
E. ON THE EQUIVALENCE OF SDP FORMS (1) AND (3)
In this section, we establish the equivalence between (1) and (3). To make our proof more readable, slightly change the notation of (1). Specifically, (1) is exactly the same the following problem:
min č.
S
(15)
WT diag(()) (+)
subject to ddiag(F
30,
4 42 0,
-2 diag(F) - - T.y
18

---

Published as a conference paper at ICLR 2024
We restate (3) below
min G.T
5
subject
0
-71
W diag(T) -2 diag(T)
3 30,
(16)
v
diag(T)W
2 0, T 0, 7 0.
Next, we will prove the following result which establishes the equivalence of (15) and (16).
Proposition Denote the optimal values of (15) and (16) as Ç and 5" respectively. Then (* = 2
Proof. If 0, then we trivially have 5* = For the rest of the proof, we assume that not a zero vector. In this case, any feasible solution to (16) implies that 7 - C < 0. By Schur complement, (16) is equivalent to the following problem:
min Ç CiTY
W diag(T) (iag(T)W -2 diag(r) <-> oTo 30,
-71
subject
(17)
>< C, ( 0, 0, 7
In other words, the optimal solution for (17) is also given by C*.
Let (5", 4*) be the optimal feasible point for (15). we choose & = Vē+ 27 2 and
T 75" = V²- then we have
WT diag(r) diag(r)W -2 diag(r) + 5- u
--
W diag(f*) diag(f*))) W -2 diag(f* uT 3 0.
-51
Therefore, the above choice (7, C, T) must feasible point for (17). Consequently, the optimal value of (17) must be upper bounded by the value of Ç in this feasible point, which is Ç = 2 2//"" Therefore, we have Ç* s 2
Next, we show 5* 2 22/5" Eo. Let us introduce the following problem
min
2V7(S-11 -7)
C.7.7
-71
WT diag(r)
(18)
subject to
diag(T)
-2 diag(T) uTo 30,
>< C, 0, 0,0,
This problem has the same feasible set (17). Note that, for any point in the feasible set, must have 2/7(5- 7>) < Ç (this is equivalent to (² -57 + 4,² > 0). Therefore, considering the same feasible point, the objective function (18) is always upper bounded by the objective function of (17). Denote the optimal solutions of (18) and (17) (ct,ri,)) and (S","", r","", respectively. Clearly, """""" is also a feasible point for (18). Then we must have
2 2 7t) < 2 - SC
-c
(19)
Finally, if we choose f = (c1 - )r and - r -7!). Then we have
- WT diag(f))
-771
WT diag((T))
=(st -g)) ddag(r))) -2 diag(r!) + -T u
30
diag(F)W -2diag(f) T
19

---

Published as a conference paper at ICLR 2024
Therefore, this choice of (C, gives feasible point for (15), and we have
~* -<-="(((->>)
(20)
trivial combination of (19) and (20) leads to the desired conclusion Ç" 2 2 2
To summarize, we have established that Ç" - 22 Our proof is now complete.
Remark 1. The above proof gives the right scaling between S and Č. Now we provide a more intuilive treaiment to explain how the factor of appears in the scaling, Specifically, as mentioned in our main paper, if the semidefinite constraint in (3) is feasible, then the neural network is &- Lipschitz. Now we provide a proof for this fact. Recall that we have f(x) = vo x + bD) b².
where (z) is a scalar. Obviously, the tightest Lipschitz bound is given by
1f(x') f(x))
Luuin max x².00
(21)
|| - x||
For any L
Limin we have (f f(x) s Llla' =ll Va',.. x. By using the slope-restricted
property af a, upper bound for Liinn is provided by the solution of the following problem which busically replaces with the quadratic constraint in Fazlyab et al. (2019, section 2.2):
AA2 A
WAr A=
diag(r) 1 -2 -idiag())
WAx A
max Ar.As
diag(r)
2 0,
(22)
where Az = (W +0) o 69), === and T is any vector whose entrieis are all non-negative. we scale AE and AU with common factor, the constraint in (22) is maintained, and the cost remains unchanged. Therefore, (22) is equivalent to the following problem
[Wr Az
0 diag(T) -2 diag(r)
[
1 [Ar A=
max uA= Az,
S.
diag(r)
2 0, ||a||=
Notice that the absolute value in the objective is removed due to the fact that scaling (Ax, Ae) with -1 does not affect feasibility. If we replace the equality constraint || 1 with inequality
constraint Ax|l S 1, then we get the following problem whose solution is an upper bound for (22).
WAr A2 A2
0
diag(T) 1 -2 diagg(()) (T)
WAr Au
max vA= S. Ar,A:
2 20, |A.|| 1
(23)
diag(r)
Denote the optimal value of the above problem as L Then L" is an upper bound for Lmuin- It obvious that any upper bound for L will also be Lmin- Next, we will show that if the semidefinite constraint in (3) is feasible, then we have $ L" 2 Lunin and hence f is S L-ppschiizz Specifically, if the semidefinite constraint in (3) is feasible, we immediately have
C
O -I diag(r)W
V WT diag(r) -2 diagg(7))
Ax Az
Ax 0 Az
T
which leads to
Ax
W diag(T) -2 diag(7)
Ar A=
(1-1|Az|1 20
<+
Az
diag(r)
Under the constraints in (23), we have
||a I and
Ar A=
O
W diag(r) -2 diag(T)
Ar
2 0.
diag(r)W
Az
Therefore, must have vAs S and & becomes upper bound of L.". This leads the clusion that f is & S-iisschitz. The factor of is due to vAz + T = 2vA for the scalar output case.
20

---

Published as a conference paper at ICLR 2024
E.2 ON THE EQUIVALENCE OF SDP FORMS (3) AND (6)
In this section, we establish the equivalence between (3) and (6). Formally, we have the following result.
Proposition 2. Denote the optimal values of (3) and (6) as S and Çt, respectively, Then we have C²
Proof. First, will prove Ç" 2 ç²_ Suppose the optimal feasible point for (3) is given by ("","",>")) Then we can choose < T r², Y 7", and À = O, which gives a feasi- ble point for (6). Then this feasible point whose value is exactly ( gives an upper bound for the optimal value of (6). Consequently, we must have Ç* 2 2(
Next, we will prove Ç- S <τ. Suppose the optimal feasible point for (6) given by (St,At, 7!). Then we choose = <t, T = 7 + Xt, and 7 = y² Σj=1 aj and show this gives a feasible point for (3) which has the value çt. To show that our choice gives feasible point for (3), we only need to verify that the following matrix inequality holds for our choice (S, T, 7,):
7
-rI
W diag(r) diag(T)
30
(24)
diag(r)W
To verify (24), we can perform the following calculation:
5
0
-
WT diag(r)
T
diag(T)W
-2
7
+
j=1 a-2}- -5
0
v W diag(r+ # Xt)
0
-(7 Σÿ= a, diag(r* + WtW
T
2 diag( ( + At)
Σ 12
0
j=1
v W diag(r+) diag(ri)W -2 -2dig(r))) (A+)
0
-
+
Cy= a,2))z
W diag(A))
T
0
(iag()+))
- diag(AF)
where the first term is known to be negative semidefinite due to the fact that (5², At, r y!) gives feasible point for (6). Therefore, (24) holds desired if we can show that the second term also negative semidefinite. By Schur complement, this is equivalent to verifying
ajat) + T diag(A (FFW N
Since we have T diag(>))W Σラ XW W, we only need verify
Cart) Σ WWTW, 30 J=1
Since aj = ||5 we do have XWW,W, 3 XLa,1 for all j. This leads the desired conclusion that (24) holds. Therefore, we have obtained a feasible point for (3) which gives the value ç², and the optimal value of (3) can only be smaller than equal çt. This proves (* < Ct.
To summarize, we must have 5" = , and hence (3) and (6) are equivalent.
F EXTENDING OUR RESULTS TO THE VECTOR OUTPUT CASE
In this section, we discuss how to extend EP-LipSDP for the scalar output case to the vector output case. The extension is actually quite straightforward. First, consider the single-layer case. Con- sider f(x) = Vo + 60) + b², where x E R"*, W E R=x", 50 E R", u Rm b² e R" m has neurons, and is assumed to be and f(x) E m The neural network f RR
21

---

Published as a conference paper at ICLR 2024
slope-restrictdd on [0, 1]. In this primal domain, the following QCQP provides the Lipschitz upper bound for f:
max subject to
|VA==l² (Az; A, S 0, W E [x] | 1
(25)
Obviously, Shor's relaxation of the above QCQP is the dual program of the original LipSDP (for the vector output setting). Similar to our previous development, we can introduce redundant trace constraints to (25) and obtain
|| |
max subject to
(Az; W,Ar) 10, Vi Vi [n]
(26)
|
A I Willlep Vi E [n]
Then it is straightforward to verify the dual of the Shor's SDP relaxation of (26) reads as
min
5
ajAj +7-5
j=
subject to
0
W diag(r) diag(T) -2 diag(r) diag(A (A) VTV
II
30,
(27)
0
2 A2 0,
Since the dual program of the above SDP has explicit trace constraint, the penalty formulation of the above SDP will be exact. We define
ΣE= ag2g 47-5
:=
W diag (T) diag(r)W -2 diag(7) diag() (A) + VTV]
-71
Then we have the following EP-LipSDP for the vector output case:
min (20.220,720r2
S+ (2+ Σ as) Xitnne
(28)
The penalty parameter is set 2+ ++E= aj. which aligns well with our previous developments. We can use the same argument that we developed previously to show that the above EP-LipSDP form has exactly the same optimal value as the original LipSDP.
By slightly modifying the above argument, output network. Specifically, one just removes v and T from the matrix C and then add VTV to the last block of C. Then the rest of the EP-LipSDP formulation will hold exactly the same as the scalar output case.
also obtain EP-LipSDP for multi Muyer vector-
F.1 INITIALIZATION FOR THE VECTOR OUTPUT CASE
Recall the SDP for the vector output of two-layer network is
min CA,,,y
<
Σ n
EE ajAÿ
+
0
0 W diag(
subject to
0
I
30,
(29)
0
diag(T)W -2 diag(T) - diag (A) + VTV
<
12 0,
T 0, 0.
I
WT diag(T)
We can choose Xy 0, and then we only need y < < 0 and
diag(r) W
- 2 2iaa((T) + VTV
1
By Schur's lemma, we only need: ? > and
2 diag(r)
vT diag(r)WW* diag(r) ž 0.
22

---

Published as a conference paper at ICLR 2024
Let diag(7) al, then we want
a² EwT = 0. 2al - V
We can choose [ and 7 [|v || op and C |
| Because will
square root to estimate the Lipschitz constant, this recovers the naive upper bound of the Lipschitz constant:
| |Wll'p''
For 3-layer network, the SDP constraint is:
2
0
0
0
0
71
W A
O
c=
30
0
A
-2A
W2A2
0
0
AgW2
-2A + VTV
Let
7
C
0
0
0
C1
0
0
0
0
0
0
C2
-
-7
WT
A
0
W
A1
0_
O
and
0
0
0
C3
-A
W2A2
A2
2A
VVV
Clearly, C= + C2 C3, then we only need C₁, C2 C3 0.
We can have A₁ al, A2 bl. To have C3 x 0. then by the Schur complement lemma, we need
b2
2b/ v
W.W, 0.
We can have b = =|V and a = | |W
To have C2 < we need
á al
W W.W. 0.
We can have |[ 11 In general, for a multi-layer network, we can apply the above argument recursively:
1| 1
=
C
0
0
0
I
W(
0
0
A A
-2A8-1 + VTV
We will have 7
[T-11 || 2 [ and A, = m
|1 | J.
23

---

Published as a conference paper at ICLR 2024
Table In this table, we present results of comparing different variants of our approach to LipSDP on few MNIST DNNs. Among all the results, we can see that if we use the exact eigenvalue computation instead of Lanezos approximation, LipDiff results in very close values to MOSEK's results on all three DNN architectures.
Dalasets
Models
Product
LipSDI-MOSEK
LipSDP-SCS
LipDilT
LipDifT-Es
Lipliff-Denee
LipDitT-Rand
LB
Result
9.31
4.82
4.82
4,90
4,86
4.3G
5.89
1.57
MNITT
Time
0.13
54.57
2706.5
28.69
19.27
12.48
29.27
4.86
Menoory
1.54
Rosult
9.27
4.93
4.89
1.51
MNIST
WIDE
Time (4)
0.10
214.67
5014993
65,89
41,85
29.03
64.
4.88
Memory (MB)
3.25
297.88
415.90
230
192
192
230
2424
Result
17.29
7.43
7.38
7.76
7.51
7,60
11.47
2.03
MINIST
DNN3
Time
0:12
649.40
128.50
83.55
4.95
Mensory (GB)
3.23
810
284
284
362
G ADDITIONAL EXPERIMENTAL RESULTS
additional architectures on MNIST that the LipSDP-MOSEK solver can handle: 1. A single hidden layer with 512 hidden nodes (denoted as WIDE); 2. two- hidden-layer network (denoted as DNN3), and each of the hidden layers has 512 ReLU nodes.
We provide more experiments
Additionally, we provide two new baselines: LB and LipSDP-SCS, For LB, we randomly sampled 500, 000 points from the input space and computed the maximum & norm of all the gradients in- duced on these samples, which serve as a lower bound. For SCS, we used the default SCS solver provided by CVXPY to solve the SDP program, with max iterations of 2, 500. Notice that SCS solver cannot scale to the MNIST-CNN network, similar to the MOSEK solver. The specification of MNIST-DNN is included in the main paper.
The results are summarized in Table 3.
Notice that we not know how good the lower bound is because the number of samples is un- likely to be sufficient. For example, even if only consider the vertices of the input on the [0, hypercube, there would be 2784 vertices for MNIST and 23072 vertices for CIFARIO, which are much greater than 500,000.
For SCS, we notice that if we set the max iterations too small (for example. 50), the result can be very unstable. It return either 0 or inf, which is not useful at all. On MNIST-DNN3, SCS provided a value smaller than the MOSEK solver, which we do not know whether it is valid upper bound for the Lipschitz constant. However, LipDiff always returns valid upper bound.
On the other hand, because the network is relatively small compared to CNNs, computing exact eigenvalue and using the dense representation of the matrix is more efficient than the sparse repre- sentation. The results from LipDiff-Ex and LipDiff- are more desirable. However, because the main goal of LipDiff is to scale LipSDP huge networks that the general SDP solver cannot handle at all, sparse representation and the Lanczos approximation would be more appropriate for these cases, shown in Table 2.
H ALEXNET EXPERIMENTAL RESULT
AlexNet consists of two parts: feature extraction sub-network and a classifier sub-network. Be- cause the operator norm is sub-multiplicative, we apply the scalar LipDiff on the classifier, and also the vector output version LipDiff on the feature extraction network. More specifically, the feature extraction network contains three separated convolutional parts, and we apply LipDiff on the final convolutional part, which consists of three consecutive convolutional layers, and all of them have 3 x 3 kernels and padding 1. For the classifier sub-network, it contains fully connected layers.
For the classifier, we again choose class as in the evaluations of MNIST and CIFARIO. If we expand the matrix of the classifier, the SDP has size of 17 409 17 409. The matrix norm product bound of the classifier 67.77, while LipDiff produces the Lipschitz constant of 22.41, which leads to 66.9% decrease.
For the three convolutional layers, we expand the matrix of the classifier, the SDP has size of 140 609 x 140 609. The matrix norm product bound of the classifier is 2886.73 73, while LipDiff
24

---

Published as a conference paper at ICLR 2024
Table 4: We summarize AlexNet experimental results: we run scalar-LipDiff on the classifier part, and vector-LipDiff on a sub-network of the feature extractor. On the classifier, LipDiff achieves a 66.9% improvement on the Lipschitz constant estimation; and on the feature extractor, LipDiff decreases the Lipschitz constant by 18.4%, compared to the matrix-norm bound. Combining these two results, LifDiff achieves a total of 73% improvement for AlexNet Lipschitz constant estimation compared to the matrix norm product bound.
Model
Structure
SDP size
Matrix Norm Bound
LipDiff
Improvement
classifier
3FC
17 17409x x 409
67.77
22.41 2354.77
66.9%
feature extractor
3C
140 609 x 140 609
73
18.4%
produces the Lipschitz constant of 2354.77, which leads to 18.4% decrease. In this experiment, because the matrix is very large, we are unable to get the exact eigenvalue, instead we used Lanezos algorithm to estimate the eigenvalue with Lanczos steps 9200. The initialization for the vector ex- LipSDP comes from appendix F.I.
Combining the results from both parts, LipDiff reduces the Lipschitz constant of AlexNet by 73% compared to the naive matrix norm product bound.
1 FURTHER DISCUSSIONS AND EXPLANATIONS
I.1 TECHNICAL NOVELTY
In this section, we briefly summarize the technical novelty of our work.
Adding redundant trace constraint: To obtain the exact penalty form of LipSDP, we need to add an explicit redundant trace constraint to the primal form of LipSDP. How to add this explicit trace constraint highly depends on the network structure, and there is no general recipe for doing this. We delicately exploit the structure of the neural network to add the redundant trace constraint in layer-by-layer manner, leading to the first exact penalty form of LipSDP.
Proof techniques beyond Liao et al. (2023) and Ding & Grimmer (2023): Our exact penalized SDP formulation is motivated by the recent advances on first-order methods for convex nonsmooth optimization (Liao et al., 2023; Ding & Grimmer, 2023). However, our result is not simply direct application of their results. In particular, all the existing results from Liao al. (2023) and Ding & Grimmer (2023) require the penalty parameter to be strictly larger than the trace bound of the semidefinite variable, while our main technical results in Theorem I and Theorem 2 allow for the non-strict inequality, i..., penalty parameter only needs to be larger than equal to the trace bound. Also, our proofs for Theorem and Theorem 2 directly exploit the neural network structure, and consequently
argument is simpler than those in Liao al. (2023) and Ding & Grimmer (2023). Our proof is also self-contained, while those of Liao et al. (2023); Ding & Grimmer (2023) reply on other technical results, such strong duality and a general penalized result in Ruszczynski (2011, Theorem 7.21).
Network-deeendent tricks for making our algorithm LipDiff work on practical problems: In Section 5, we provide further network-dependent tricks for making our method LipDiff work on practical problems. Our tricks include analytically deriving an initialization with nontrivial matrix analysis (see Appendix B) and utilizing the sparse structure of the constraint to faster approximate the maximum eigenvalue. This analytical initialization guarantees that our method is always as good as the matrix norm product (which is currently the state-of the----rrtttttte technique for estimating Lipschitz bounds of large neural networks) and makes LipDiff practical. From our empirical evaluation, for large networks (MNIST/CIFAR IO-CNss, if we randomly initialize the variables, it is very hard for LipDiff to find a good solution. We propose to initialize from a feasible point that exactly cor- responds to the matrix norm product bound, and we leverage matrix analysis tools to derive the analytical form of this initial point. Such a development depends on the network structure, and is completely contribution.
25

---

Published as a conference paper at ICLR 2024
1.2 POSSIBILITY OF TIGHTENING LIPSDP
To the best of our knowledge, LipSDP is recognized as the method that can give the least conser- vative fz-Lipschitz upper bound with polynomial time guarantees. On small-scale problems where LipSDP can be efficiently solved, numerically it has been very difficult to find a polynomial-time algorithm that can give less conservative Ez-Lipschitz upper bounds than LipSDP. Therefore, it is reasonable to focus on how to make LipSDP scalable and memory- -efnoorreffiiient.. How to tighten LipSDP beyond the scope of this paper. Tightening LipSDP is an interesting problem and hence should be pursued in the future. In the meantime, given the current redundant trace constraint, tuning the pa- rameter o may not be the right way to tighten LipSDP. Specifically, we have theoretically proved that LipSDP with or without the redundant trace constraint (i.e. (3) and (6) in our paper) actually give the same solution (see Appendix E for detailed proof). It is true that adding redundant constraints can refine the solutions for many SDP relaxations. However. for LipSDP, it is quite unfortunate that the current redundant trace constraint does not refine the solution quality. Consequently, given the current redundant trace constraint, tuning / does not seem to be the plausible way to tighten LipSDP. We agree that it is possible to develop other redundant constraints that may be incorporated into the original QCQP formulation to tighten LipSDP. This will be future direction for us.
1.3 RELATION BETWERN SDPs IN LIPSCHITZ ESTIMATION AND LOCAL ROBUSTNESS VERIFICATION
There are recent advances in SDP formulation for the robustness verification of neural networks. One of the early formulations appeared in Raghunathan et al. (2018). Indeed, the high-level ideas in both robustness verification and Lipschitz constant estimation are very similar: both of them formu- late the problems into a QCQP form and then relax the QCQP using standard Lagrangian relaxation or Shor'r relaxation. In principle, one can formulate a better QCQP form (i.e., adding some ef- fective redundant constraints, see e.g., Batten et al. (2021)). the resulting SDP formulation would provide a better estimation. Some tightness analysis was carried out in Zhang (2020), however, the assumptions therein are very restrictive, which may not hold for practical neural networks. The paper by Dathathri et al. (2020) aims to develop a customized first-order solver to improve the scal- ability of the SDP in Raghunathan et al. (2020). We note that the SDP formulations for the robustness verification of neural networks and Lipshcitz estimation are indeed very different. The line of work on robustness verification may give new insights, but it is nontrivial to directly apply those advances. For example, we have proved that adding some redundant constraints in our formulation does not improve the tightness of the resulting SDP formulation. It is promising direction to unify the QCQP and SDP formulations and their solutions for both robustness verification and Lipchitz constant estimation.
al. (2018). Our work is also partially motivated by Dathathri
I.4 RELATED WORK ON POLYNOMIAL OPTIMIZATION
Mai et al. (2022) considers a constant trace property in polynomial optimization. In particular, the variable X satisfies trace(X) = c, which is a constant. Then, Mai et al. (2022) translate this con- stant trace formulation into eigenvalue problem via standard procedure in Helmberg & Kiwiel (2002). However, this property does not hold in LipSDP arising from the Lipschitz constant estima- tion of neural networks. Indeed, our first theoretical guarantees in Theorem 1 and Theorem offer new exact penalty SDP formulations that are suitable for the application of first-order subgradient methods. Our penalized SDP formulation is motivated by the recent advances in convex nons- mooth optimization (Liao et al., 2023; Ding & Grimmer, 2023). We exploit the problem structure (especially the neural network structure) to provide a simple elegant proof of our main theoretical guarantees in Theorem and Theorem 2.
I.5
IPM VS FIRST-ORDER METHODS
The per iteration computation of first-order methods is much cheaper than IPM, while IPM requires much less iterations in total to achieve an e-solution. To achieve e-approximate solution, the total iteration number required by IPM is on the order of Oloog(1<e). For LipDiff, we are applying subgradient method to solve convex nonsmooth optimization problem, and the total iteration number needed to get an e solution is on the order of ((1e²). However, for each iteration, the computational/memory efficiency for IPM is much worse than our first-order subgradient method.
26

---

Published as a conference paper at ICLR 2024
In practice, Lipschitz estimation of neural networks typically does not require using very small e, ie. é is typically set to be on the order of 0.1 or at most 0.01. Therefore, we argue that per iteration complexitylefficienny matters more for the Lipschitz estimation problem of larger neural networks. In addition, we have developed the special analytical initialization to reduce the iteration number needed by LipDiff (see Appendix B). This justifies the significance of our contribution.
1.6 COMPARISON WITH COSMO
We have tried COSMO in some additional experiments, and it did not work well. The COSMO solver is implemented Julia and may be called by the JuMP optimization modeling framework. We implemented LipSDP in Julia with the COSMO solver which gave accurate solution (identical to MOSEK) for small networks with SDP dim 10 x 10. Unfortunately, for small MNIST networks of just layers (resulting in SDP of dim 800 800), COSMO appears to be unstable and will not converge. Finally, we want to comment that COSMO aims to solve the KKT condition of conic programs, and does not guarantee the returned solution to be valid Lipschitz upper bounds. In contrast, our proposed first-order method LipDiff (EP-LipSDP) guarantees that any value returned by LipDiff is always valid upper bound higher than equal to LipSDP's optimal value, because the iterations of LipDiff naturally correspond to feasible points of LipSDP which directly gives Lipschitz upper bounds.
1.7 CONVEX NONSMOOTH OPTIMIZATION Vs. MINIMAX FORMULATION
Here clarify that treat EP-LipSDP convex nonsmooth optimization problem instead of minimax problem. For simplicity, we restate the EP-LipSDP problem here as
min
J(S == c (2+ Σ 03 A (C(S, j=1
220.20.220220
where C(S, X, 7, is defined as
C(GATT,5)) = j=1
agAj + 7 5
0
V
0
W diag(r) diag(T)W -2 diagg(r - diag (A)
-71
T
Since C is linear in (ç, (S,A,T,) T, one can show that J a convex nonsmooth function of (Ç. X, T, 7)- The nonsmoothness is introduced by the operation A We emphasize that J is function of A, A, T. 7). Although / is nonsmooth, we can still apply the subgradient method with box projection solve the above problem. Notice that the operation A not performing maximization over (G, A, F, 7), and hence we are not solving a minimax problem.
27


Reviews:
[{"review_id": "uHCx8Abg6s", "reviewer": "Reviewer_CCdS", "summary": "The authors proposed an interesting reformulation (LipDiff) to use SDP to estimate the Lipschitz smoothness of a Neural Network (specifically, LipSDP.) The major observation is that there is a trace bound on the Shor's relaxation on the \"Rayleigh quotient\" QCQP of the Lipschitz-smoothness problem inspired by [Wang et al., 2022, section 5]. And inspired by [Liao et.al., 2023], the SDP primal problem with an explicit trace bound has an equivalent objective value to a dual optimization problem with only box constraints and a \"simple\" objective function with linear + $\\rho\\cdot$positive(eigmax(X)) for large enough penalty $\\rho$ that's computable. For such a boxed-contrained optimization problem with maximum eigenvalue in the objective function, the authors apply the Lanczos-inspired optimization method [Dathathri et al., 2022] and try to exploit the sparse structure in LipDiff. In the experiment section, the authors demonstrate the proposed method on \"classical\" multiple-layer CNN trained on realistic datasets.", "questions": "1. Please explicitly clarify the relationship between the objective values in the different formulations (scaling / square roots).\n2. P3 after eq (1): The \"last\" term, not the 2nd term.\n3. Footnote 2: I'm unconvinced about the abovementioned equivalence. Also, please explain why it's $\\epsilon/2$-smooth.\n4. P5 on adding a trace norm: the rationale is not explained unless the reader goes to [Liao et.al., 2023].\n5. P5 on the exact penalty: [Liao et al., 2023] doesn't apply directly to the non-negative constraints, but your proof is correct.\n6. P13 in Appendix A: the $\\Lambda$s are not defined. Also, why $\\xi/2$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is surprisingly correct, given so many omitted parts. The result that the LipSDP can be reformulated as a boxed-constrained minimax eigenvalue problem is surprising and probably has some deeper connections. Further, although the proposed method is \"inspired\" by many recent papers, there are generally some adaptions/improvements to the original formulation or proofs. For example, the QCQP \"Rayleigh quotient\" problem considered in  [Wang et al., 2022, section 5] is L-$\\infty$-based, but it's L2-based in this work. The proofs in [Liao et al., 2023] require strict feasibility, but the authors generalized it to boxed constraints without requiring strict feasibility. The Lanczos-inspired optimization method in [Dathathri et al., 2022] doesn't exploit sparsity, but the authors try it in the work. Thus, the paper is not just a blind combination of various state-of-the-art methods. Thus, I would recommend an acceptance.", "weaknesses": "First, let me complain that the authors should have included more context in the description and derivations. This makes verification hard, but fortunately, the proofs are short and correct. Other than that, my biggest concern is the equivalence of the formulations in eq (1) and (3), in which the authors \"proved in the footnote\" by stating \"it can be proved\". Unfortunately, I didn't find the equivalence in the mentioned literature. In the worst case, eq (3) is an upper bound of eq (1) for the additional constraints (not equivalence), which is still okay due to its computational advantages. Further, the paper didn't do an approximation ratio analysis like [Wang et al., 2022, section 5] and other works. Finally, I am not sure the minimization of linear + positive(maxeig) objective function is easier to solve than the original SDP or the manifold alternatives (E.g., ManOpt.) The proposed formulation minimax in nature so the gradient-based method may be pretty unstable.", "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": "", "extra_scores": {}}, {"review_id": "7VQdVgFHi2", "reviewer": "Reviewer_LyYu", "summary": "The authors tackle the problem of Lipschitz constant estimation of neural networks. Semidefinite programs (SDP) have shown great success for Lipschitz constant estimation, but the memory and time consumption avoid them to scale to modern neural network architectures. By transforming the problem into an eigenvalue problem, the proposed method is more memory efficient than the existing methods for solving SDP, and performs much better than simple matrix production norm bound.", "questions": "1. Could the authors list the time and memory of each method, so it is clearer for comparison?\n2. Is it possible to provide some kind of lower bound to show how good the proposed method is? LipSDP serves as a comparison target, but is only viable in one of the compared architectures. Showing that the proposed method is competitive with LipSDP on more architectures can make the paper more convincing.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The proposed method seems reasonable and promising.\n2. The reduction into the eigenvalue problem is very useful and makes the proposed method practical and provides potential for further optimization.", "weaknesses": "1. While I can get that transforming into an eigenvalue problem would be beneficial (as there are many past developments in solving such problems), it is still kind of vague why and to what extent the proposed method is more memory efficient.", "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": "", "extra_scores": {}}, {"review_id": "zMYdf5OIVE", "reviewer": "Reviewer_peb1", "summary": "The authors consider the classical Shor semidefinite programming (SDP) relaxation of the Lipschitz constant of neural networks. \nThey formulate this SDP program as a non-smooth eigenvalue problem with an exact penalty (EP) parameter. The resulting formulation is called EP-LipSDP. \nThe exact penalty parameter is obtained by means of proper redundant quadratic constraints. \n\nThen they provide different numerical algorithms to handle this eigenvalue optimization, including eigenvector approximation via Lancsoz' method, sparse matrix multiplication, and analytical initialization. These different algorithms allow one to tune the running time and convergence of the optimization process.\n\nThe resulting algorithm, called LipDiff is compared to standard techniques on three neural network benchmarks: MNIST DNN, MNIST CNN and CIFAR10 CNN.", "questions": "- p2: \"Dathathri et al. (2020) solved a different problem\" => which problem?\n\n- p7: Typo \"the the\"", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors can obtain a non-trivial Lipschitz constant estimate on the CIFAR10 CNN.\nThanks to the different numerical techniques, the resulting algorithm can be tuned for adaptation to allocated computational resources, in particular memory.", "weaknesses": "1. The initial problem of Lipschitz constant computation can actually be formulated as a polynomial optimization problem. The authors have almost completely forgotten to mention related papers based on techniques from this field (at the exception of the one by Latorre et al.), in particular the following ones:\n\n- Chen et al. Semialgebraic optimization for Lipschitz constants of ReLU networks\n- Chen et al. Semialgebraic representation of monotone deep equilibrium models and applications to certification\n- Mai et al. Exploiting constant trace property in large-scale polynomial optimization\n\nThe latter paper relies on the constant (rather than bounded) trace property, and a proper comparison would be valuable. \n\n\n2. The LipDiff algorithm might not be very accurate in general. From the comparison on the basic benchmark MNIST DNN, one notices that LipSDP obtains a better bound. It would be interesting to see how LipSDP behaves on, e.g., MNIST CNN by using LipSDP with Mosek on a scalable computing platform with more RAM. \nFirst order methods are usually much faster than second-order solvers (in particular interior-point methods) but they are also much less accurate in general. The trade-off between accuracy and efficiency should be more explicitly investigated. \nIt would be also interesting to see what kind of results first-order SDP solvers like COSMO would yield.", "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": "", "extra_scores": {}}, {"review_id": "a4DBWTb1Y7", "reviewer": "Reviewer_GVUd", "summary": "Papers concerns a new SDP method to approximate the Lipschitz constant of neural networks, with the main benefit being its scalability due to the reduction of explicit constraints as penalizations. The proposed methods is itself useful, however the paper did not convince me of its technical innovation. It just seems to me that the authors simply took the methods from (Liao et al., 2023) and applied it to the LipSDP method to ensure that they have the same optimal solution.", "questions": "Not questions, but I encourage the authors to check a major line of work concerning the SDP verification of robustness of neural networks. That problem and your Lipschitz problem are very similar from a technical standpoint, and there are already a number of different branches in that space. For example brand-and-bound methods, non-convex cut, chordal decomposition (as you have mentioned), and theoretical analysis of relaxation quality. By exploring that problem I think you can benefit the Lipschitz problem as well.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The proposed technique itself is nice, and may be beneficial in many aspects. The numerical experiments are also convincing, demonstrating its usability. The presentation is clear and easy to follow.", "weaknesses": "1. The theoretical innovation is relatively weak, because anyone can apply different techniques in the convex programming space and use it on LipSDP to claim as a new idea. I didn't see any specific analysis and/or new technique proposed specifically for the Lipschitz problem of NN.  Maybe I am overlooking some details, and if so please point me to these places.\n\n\n2. The authors only showed that their new formulation has the same optimal value as the old LipSDP problem. However since LipSDP is a relaxation, there are no guarantees of its accuracy. The authors introduced redundant constraints in this paper, and this kind of technique is usually used to tighten relaxation gap in classic literature, so I hope the authors could also touch upon the tightness of relaxation, especially by tuning the parameter $\\rho$, as I believe this is possible to analyze.\n\nTypos\n- On page 3, it seems like when you say \"second term of the left hand, etc\" you meant the third term, and you grouped the first two terms together implicitly. Also please explain how your third term ties to the relu function (experts may understand, but since you're explaining here please be more precise).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)