ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks
Authors: Yuezhu Xu
S Sivaranjani
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Neural Networks
Lipschitz Constant
Robustness
Primary area: learning_theory
TL;DR: We provide an extremely fast and scalable method to obtain tight bounds for the Lipschitz constant of deep neural networks.

Abstract: The Lipschitz constant plays a crucial role in certifying the robustness of neural networks to input perturbations. Since calculating the exact Lipschitz constant is NP-hard, efforts have been made to obtain tight upper bounds on the Lipschitz constant. Typically, this involves solving a large matrix verification problem, the computational cost of which grows significantly for both deeper and wider networks. In this paper, we provide a compositional approach to estimate Lipschitz constants for deep feed-forward neural networks. We first obtain an exact decomposition of the large matrix verification problem into smaller sub-problems. Then, leveraging the underlying cascade structure of the network, we develop two algorithms. The first algorithm explores the geometric features of the problem and enables us to provide Lipschitz estimates that are comparable to existing methods by solving small semidefinite programs (SDPs) that are only as large as the size of each layer. The second algorithm relaxes these sub-problems and provides a closed-form solution to each sub-problem for extremely fast estimation, altogether eliminating the need to solve SDPs. The two algorithms represent different levels of trade-offs between efficiency and accuracy. Finally, we demonstrate that our approach provides a steep reduction in computation time (as much as several thousand times faster, depending on the algorithm for deeper networks) while yielding Lipschitz bounds that are very close to or even better than those achieved by state-of-the-art approaches in a broad range of experiments. In summary, our approach considerably advances the scalability and efficiency of certifying neural network robustness, making it particularly attractive for online learning tasks.

ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks
Yuezhu Xu
Sivaranjani
Edwardson School of Industrial Engineering Purdue University
Edwardson School of Industrial Engineering Purdue University
West Lafayette, IN, USA
West Lafayette, IN, USA
xu17328purdue. edu
sseetha@purdue.eem
Abstract
The Lipschitz constant plays a erucial role in certifying the robustness of neural networks to input perturbations. Since calculating the exact Lipschitz constant is NP-hard, efforts have been made to obtain tight upper bounds on the Lipschitz constant. Typically, this involves solving large matrix verification problem, the computational cost of which grows significantly for both deeper and wider net- works. In this paper, provide compositional approach to estimate Lipschitz constants for deep feed-forward neural networks. We first obtain an exact decom- position of the large matrix verification problem into smaller sub-problems. Then, leveraging the underlying cascade structure of the network, we develop two algo- rithms. The first algorithm explores the geometric features of the problem and enables us to provide Lipschitz estimates that are comparable to existing methods by solving small semidefinite programs (SDPs) that only large the size of each layer. The second algorithm relaxes these sub-problems and provides a closed-form solution each sub-problem for extremely fast estimation, altogether eliminating the need to solve SDPs. The two algorithms represent different levels of trade-offs between efficiency and accuracy. Finally, we demonstrate that our approach provides a steep reduction in computation time (as much as several thou- sand times faster, depending on the algorithm for deeper networks) while yielding Lipschitz bounds that are very close to or even better than those achieved by state- of-the-art approaches in a broad range of experiments In summary, our approach considerably advances the scalability and efficiency of certifying neural network robustness, making particularly attractive for online learning tasks.
Introduction
The Lipschitz constant, which quantifies how neural networks output varies in response to changes in its inputs, is a crucial measure in providing robustness certificates [M]. [2] on downstream tasks such as ensuring resilience against adversarial attacks [[3, H] stability of learning-based models or systems with neural network controllers [[--],, enhancing generalizability [IC],, improving gradient- based optimization methods and controlling the rate of learning [[[]][2]] 'hee problem of calcu- lating the exact Lipschitz constant is NP-hard [ Therefore, efforts have been made to estimate tight upper bounds for the Lipschitz constant of feed-forward neural networks (FNNs) [14 [X] and other architectures such as convolutional neural networks (CNNs) [[T] Typical approaches in- clude formulating polynomial optimization problem [[2]] bounding the Lipschitz constant via quadratic constraints and semidefinite programming (SDP) [[ which in turn requires solving a
large-scale matrix verification problem whose computational complexity grows significantly with
"ttps://gttubbcoom////uuuuuuuCu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

both the depth and width of the network. These approaches have also motivated the development of methods design neural networks with certifiable robustness guarantees [19 23-2511
Contribution. In this paper, we provide a scalable compositional approach to estimate Lipschitz constants for deep feed-forward neural networks. We demonstrate steep reductions in computation time (as much as several thousand times faster than the state-of-ther totte-of- depending on the experiment), while obtaining Lipschitz estimates that are very close to or even better than those achieved by state-of-the-art approaches. Specifically, we develop two algorithms, representing different levels in the trade-off between accuracy and efficiency. allowing for application-speciffe choices. The first algorithm, ECLipSE, involves estimating the Lipschitz constant through a compositional layer-by- layer solution of small SDPs that are only as large as the weight matrix in each layer. The second algorithm, ECLipsE-Fast.
provides a closed-form solution to estimate the Lipschitz constant, completely eliminating the need to solve any matrix inequality SDPs. Both algorithms provably guarantee the existence of solutions at each step to generate tight Lipschitz estimates. In summary, our work significantly advances scalability and efficiency in certifying neural network robustness, making it applicable to variety of online learning tasks.
Theoretical Approach. We begin with the large matrix verification SDP for Lipschitz constant esti- mation under the well-known framework LipSDP [[Z]]. To avoid handling a large matrix inequality, we employ a sequential Cholesky decomposition technique to obtain an exact decomposition of the large matrix verification problem into a series of smaller, more manageable sub- tob--roblems that are only as large as the size of the weight matrix in each layer. Then, observing the cascade structure of the neural network, we develop (i) algorithm ECLipSE, which characterizes the geometric features of the optimization problem and enables us to provide an accurate Lipschitz estimate and (ii) algo- rithm ECLipsE- Fast, which further relaxes the sub-pro aub-problems, and yields a closed-form solution for each sub-problem that altogether eliminates the need to solve any SDPs, resulting in extremely fast implementations.
Related Work. The simplest way to estimate the Lipschitz constans is provide naive upper bound using the product of induced weight norms, which is rather conservative [26]] Another ap- proach to utilize automatic differentiation to approximate bound, which not strict upper bound, although it is often so in practice [[3]]. Additionally, compositions of nonexpansive av- eraged operators and affine operators [166]. Clarke Jacobian based approaches and other methods focusing on local Lipschitz constants
[ have also been studied. Recently, optimization-base
approaches such as sparse polynomial optimization [22]] and SDP methods such as the canonical LipSDP framework [[=]] have been successful in providing tighter Lipschitz bounds. SDP-based methods specifically exploit the slope-restrictedness of the activation functions to cast the problem of estimating Lipschitz constant
linear matrix verification problem. However, the computational cost of such methods explodes as the number of layers increases. A common strategy to address this is ignore some coupling constraints among the neurons to reduce the number of decision variables, yielding a more scalable algorithm at the expense of estimation accuracy [IE]]. Another strategy is
to exploit the sparsity of the SDP using graph-theoretic approaches to decompose it into smaller linear matrix inequalities (LMI) [ [28]. Along similar lines, [2]]] and [29]] employ a dissipativity-
based method and dynamic convolutional partition respectively to derive layer-wise LMIs that
applicable to both FÑNs and CNNs. Very recent developments also focus on enhancing the scalabil- ity of SDP-based implementations through eigenvalue optimization and memory improvement [20],
which are compatible with autodiff frameworks such as PyTorch and TensorFlow.
2 Problem Formulation and Background
Notation. We define ZN = (1....,.0 N). where N is natural number excluding zero A symmetric positive-definite matrix P E R=*" is represented as P > (and as P > 0, if it is positive semi- definite). We denote the largest singular value or the spectral norm of matrix A by oman The set of positive semi-definite diagonal matrices is written as D+.
2.1 Problem Formulation
We consider a feedforward neural network (FNN) of layers with input 2 E R and output y e R4 defined as y f(z). The function is recursively formulated with layers L, E Zi, defined as
L 20 = =(v(()) 2--1, L: y = f(=) = ==() =0 = =0(,, [0) = 2, (1)
2

---

where o(() = W22(1-1)++ +b, with W, and b, representing the weight and bias for layer L; respectively. and Φ Rd + Rdd: is a nonlinear activation function that acts element -ise on argument. The last layer L, is termed the oulput layer. We denote the number of neurons in layer L, by d,, i E Zu. Rd R is Lipschitz continuous
Definition 1. A function
2 C R if there exists f(z2)]l2 I L||21 - 22|12, Vz1, 22 E Z. The smallest positive L satisfying this inequality is termed the Lipschitz constant of the function f.
constant L > 0 such that (2] -
Without loss of generality, we assume W; * 0, i Ze, any weights being will lead to the trivial case where the output corresponding to any input will remain the same after that layer. Our goal is to provide scalable approach give an efficient and accurate upper bound for the Lipschitz constant L > O. Note that the proofs of all the theoretical results in this paper are included in Appendix A
2.2 Preliminaries
We begin with a slope-restrictedness property satisfied by most activation functions, which is typi- cally leveraged to to derive SDPs for Lipschitz certificates [[_=].
Assumption (Slope-restricteddees)) For the neural network defined in (I), the activation futivationfuncciion is stope-restricted in [a, B). B in the sense that Vui, 02 E R", we have atwi -2) S
<(v1) - 6(v2) S (11 U2) element-wise. Consequently, we have that for VA E D2+,
U1 - 22 ((v1) - (())) 02))
Pd MA
-mA] A
U1 U2 (((1)) - -(1))
S 0, p aB,
(a + B)/2.
(2)
Now, we can obtain an upper bound for the Lipschitz constant as follows; this result is equivalent to the well-known LipSDP framework [[=]].
Theorem (LipSDP), For the FNN (II) satisfying Assumption W1 if there exists F > 0 and positive
diagonal matrices A; E ID+, E Z1-1 such that with p a3 and m a+8
4 pW? W2
-mWFA
mA,
A1 pW? Wg
W.
0
Aa pW, AgWs
>> 0. (3)
0
m
A + P A:-1
-WW- Ar-a Ac-1 FWF W.
0
0
-mA-,WW--
(0) then 22 - 21 1/2
(1)
1/F
22 200
which provides a sufficient condition for the Lipschitz
constant to be upper bounded by VI/F.
Remark 1. LipSDP provides three variants that tradeoff accuracy and efficiency, namely, LipSDP- Network, LipSDP-Neuron and LipSDP-Layer, whose scalability increases sequentially the ex- pense of decreased accuracy. However, [30] provides counterexample showing that the Lipschitz estimate from LipSDP-Network is not striet upper bound; thus, only LipSDP-Neuron and LipSDP- Layer are valid. Theorem D here directly corresponds to LipSDP-Neurol If all A, E 2 in (+) are set to multiples of identity matrices, that is, ArT, E Z1-1, then it corresponds to LipSDP-Layer.
Assumption D holds for all commonly used activation functions; for example, it holds with 0. 8 = 1, that is, p = 0, m = 1/2 for the ReLU, sigmoid, tanh, exponential linear functions. Therefore, focus this case in this work.
3 Methodology
We now develop two fast compositional algorithms based on LipSDP-Layer and Lipschitz-Neuron respectively, Both algorithms are not only scalable and significantly faster, but also provide compa- rable estimates for the Lipschitz constant.
3.1 Exact Decomposition
We circumvent direct solution of the large matrix inequality in (L), which becomes computationally prohibitive as the FNN (I) grows deeper. Instead, we develop sequential block Cholesky decom- position method, akin to the technique introduced in [BI]], also expanded in [52, B3). We first restate
Lemma 2 of [[]] below.
3

---

Theorem (Restatement of Lemma 2 of [3I]). A symmetric block tri-diagonal matrix defined as
P
R₂
R2
P
Rs
R
P2
Ra
(4)
RT-1
P
Ri
0
R
P1_
is positive definite if and only X; O, Vi [0] U 111 where
X; [P P: R
ii==0 0, EiEZ--1
(5)
Theorem 3. Let Pt be defined as in (L) with p 0,m m 1/2. Then, the Lipschitz certificate Pt 0 holds if and only if the following sequence of matrix inequalities is satisfied:
M, 0, ViE Z1-2.
M FWT Wi > 0,
(6)
where
[T M, A, - (MM ie Z
i=
(7)
Theorem provides an exact decomposition (G), and allows us to establish necessary and suffi- cient conditions through small matrix incqualities that scale with the size of the weight matrices of each layer. rather than that of the entire network. To accurately estimate the Lipschitz constant, we need decide on A₁, Z1-1 that generate tight upper bound the last stage. In other words, want M FW? W/ we provide compositional algorithms to decide the appropriate A,, E Z sequentially, so that we only need to solve one small problem corresponding to each layer.
yield the smallest estimate for v1/F. In the following subsection,
3.2 Compositional Algorithms
first propose two practical algorithms here. The theory supporting the algorithms and the geo- metric intuition are deliberately deferred, and will be thoroughly discussed in the next subsection.
The first algorithm, ECLipsE, explores the geometric features that enables us provide an accurate Lipschitz estimate by solving small semidefinite programs (SDPs), which are of the size of the weight matrices on each layer. The second algorithm, ECLipsE-Fast relaxes the sub-problems at each stage and yields closed-form solution for each sub-problem that makes it extremely fast. These algorithms represent different trade-offs between efficiency and accuracy; one may choose ECLipSE if pursuing accuracy, and ECLi SCLissE-Fast for applications where time is of the essence.
We observe in (Q)) that M; obtained in a recursive manner and depends on A, and M;-1, Z1-1- Therefore, we decide A, and then calculate M, for i E - sequentially. Thus, these two algorithms be implemented layer-by-layer in compositional manner.
Concretely, for ECLipsE, we obtain A4, i E Z,-1 at each stage using the information from the next layer, i.e. Wi+1. by solving the following small SDP:
A WT - WWT)AA
84 WHI
(W, > O, A. 4 >>0
max & s.t.
1
(8)
For ECLipsE-Fast, A; is reduced to X,T, i E Z1-1 and \; is calculated in closed-form
A σ maz (W((M)-)--W??)
Note that this completely eliminates the need to solve matrix incquality SDPs altogether. At last, after all A,s, i Σ1-1 are decided, we obtain the smallest 1/F, which yields the smallest Lipschitz estimate L / /IFF, follows
1/F man (W.
(10)

---

We choose to directly calculate the smallest 1/F rather than first derive the largest F. This is because obtaining the largest first involves taking the inverse of W?" WW, which can cause numerical issues due to potential singularity of W7'W, Wi. In contrast, directly calculating the smallest 1/F involves taking the inverses of M1-1, which is already guaranteed to be strictly positive definite layer when deciding 1-1-
Remark 2.
We summarize the algorithms as one in Algorithm M. Algorithms ECLipsE and ECLipsE-Fast are respectively preferable based on whether the priority is on accuracy or speed.
Algorithm ECLipsE and ECLipsE-Fast
Input Weights {Wi) from FNN (I) with activation function slope-restricted in [0, 1]
Output Lipschitz estimate L
1: Set Mo =
2: for 1, 2... do
3: if ECLipsE (pursuing accuracy) then
4: Obtain A, from the optimal solution of (8)
5: else if ECLipsE-Fast (pursuing speed) then
6: Obtain A; from (H)
7:
A, + -x
8:
end if
9:
Obtain M, from (1) with A, and M,-1
10:
end for
11:
Obtain 1/F from (II)
Return L 1/F
3.3
Theory
Now we dive into the cascade structure of behind the two algorithms. We analyze the compositional algorithms in Section BM2 in a backward manner, starting with the output layer. After all A,, Z,-1 are decided, M, > E - hold. From Theorem R. it remains to guarantee that Mi- FW? W. > 0, and consequently, (II). for which we state the following result.
neural networks and demonstrate the theory
Proposition 1. For given Ng E Ze-1 that satisfies M; i Z1-2, the tightest upper bound for Lipschitz constant L / Jmar (WM)((M))))))))
Now, at stage | /-1. 1, when deciding A Ar, i E 21-2 are fixed and thus Mr-2 is fixed. According Proposition
would like choose Ar-1 such that Fmax (W (M(M-i)) -1), where M a function of A is as small as possible. We have the following result.
Lemma 1. M4, O, then W W W++1 (M,) and eigenvalues.
(Ma))=((W++1)) share the same non-zero
Note that at stage i, it is guaranteed that M, > O. Taking i = 1 1, Lemma II infers that it is equivalent to minimize omax (WI(M,))) W7) when deciding A1 Note that Mi- and consequently, the existence of M,] is already guaranteed when we reach the last stage. For the sake of conciseness, we define F. A W:(M--1)-'w?? i Z1-1. From (0), M, A A.F.AA We further write out the recursive expression for F, as
WWW
i=0
Fit1 = - -W. = W HA
(11)
E
Lemma 2. For any constant ?: E (0, any Ar E D_ that satisfies Mr A, IAFFA > also a feasible solution for M, 2 A; - {Ai(FF)A > 0. In other words, the feasible region
(A; M, 0, A; E TD+ (A, M, > 0, 0 ED)).
Lemma @ gives us the observation that a contraction - FFor E (0, 1) yields larger fea- sible space for A, E D4 to ensure M, > 0. Mcanwhile, (LI) shows that for any given A4.
5

---

smaller Fi leads to smaller Fi+1 for the next stage. We can characterize how 'small' F, is by its spectral norm O manr (F)). Then, minimizing o maz (F.) aligns with our goal of minimizing = Fmer (W((M(-1)-WWW
Omar (W7 (M(-1))) words, smaller Fi at the start will generally translate to a tighter Lipschitz estimate at output layer we always choose minimize the spectral norm man (Fi) each stage.
mez (Fi) at the last stage. In other
Now we focus on how to specifically optimize A,, E Z1-1. At stage i, the goal is to seek for the A₃ that minimizes mez (F.+1), where Fi+1 We+1 (A, A,F,AA W as in (IT). Note that M,-1 1 and Fi are already fixed and can be regarded as constants at the i-th stage.
Proposition If there exists a singular matrix N 2 such that M, - &WWWy + N, with constant C₁ > O, then Fmax(Fi41)
1/c, Vi 2
In other words, we need to find the largest & > 0 to minimize mman (F++1) = 1/c. Recall that M, A; & A,J.A is function of Aç- We state the following proposition that is used derive the small sub-problems at each stage.
Proposition 3. Consider the following optimization problem for Vi Z1-1-
max 6
Ci S.L. A: -.W.(MM--)-- c.
-GW W
O, A, 4 a>0
(12)
Then, the optimal value is the largest constant such that M, can be written as M, e; WWT w+1 W + N, where is some singular matrix such that N 2 Moreover, the feasible region for the optimization problem is always nonempty.
Geometric Analysis: We illustrate the process of achieving the largest e; > 0 in Fig. I We geo- metrically represent positive semidefinite matrix by the ellipsoid generated by the transformation of a unit ball in the Euclidean space by the matrix. For simplicity of exposition, we refer to this ellipsoid as the 'shape' of the matrix. We plot the shapes of M, and W W1+1 in green and blue, respectively, in 2D. The positive definiteness of the constraint in ((2) is equivalent to the ellipsoid of W W being contained in the ellipsoid corresponding to Mj/c,. Specifically, when e; > 1, Fig. DR demonstrates the maximum contraction of M,, corresponding to the largest C₁ such that ellipsoid of W.+.W.. W i is still contained in ellipsoid of e,M, Similarly, for the case where e; < Fig. MI demonstrates the minimum extent (the smallest 1/c,) to which M; needs to expand, such that the ellipsoid of WT' 4+1 W4+1 is contained. Algebraically, in both cases, e; is the ratio of the lengths of the green and pink arrows. By Proposition 2. the resulting ellipsoid (depicted in pink) is W++1 + N/c, for both cases, and is tangent to the ellipsoid of W W Moreover, the vector pointing from the origin to the tangency point aligns with the direction of eigenvectors (the grey vector in the plots) corresponding the zero eigenvalues of the singular matrix N 2
Mr/c, = W
Wi. V
W., Plas
(a) Intuition with e >
(b) Intuition with e < 1
Figure 1: Geometric Analysis of ECLipSE
Combining Proposition 2 and B. we can derive an optimization problem to sequentially find the appropriate A, E Z1 The first constraint in (I2) is quadratic in A,, which makes it unattractive for practical purposes. Therefore, we apply the Schur Complement to transform it into the linear matrix inequality (IMII) constraint in (8). Thus, the optimization problem in Proposition E becomes equivalent to the SDP (8), yielding algorithm ECLipSE. Notice that there are several ways to write the Schur complement of the constraint in (I2). We choose this specific structure to avoid singularity of the diagonal entries and ensure positive definiteness.
ECLipsE-Fasts achieves remarkable speed by further reducing A,, E 21-1 to a multiple of identity matrix \,d, where X; O, and by relaxing the sub-problems. While our goal remains to minimize T maz maz((Ft)) = Fmaz (W+11A, - AAA,AA -W? we intentionally disregard infor-
mation from W4+1, and instead focus solely on minimizing the spectral norm of (A₃ (A, AAF

---

Roughly speaking, smaller man ((A - (AF.FA,)-)) yields smaller Fmaw (mna((Fsts (Fs+1). This relax- ation allows us derive closed-form solution for A,, -1 as follows.
Proposition 4. Choosing X; [F.J > 0 minimizes mmaz ((Ai (A.FIA.)-1) where A; X;I under the constraint that M A; A,,,AA, > 0. Moreover, this closed-form solution for X; always satisfies M; 0, Z1-1-
By the definition of Fi, Proposition EI matches with (H), yiclding algorithm ECLipsE-Fast. Al- though this relaxation may result in a loss of tightness, the closed-form solution offers the advantage of significantly increased computational speed.
Geometric Analysis: We now demonstrate the geometric analysis behind the development of ECLipsE-Fast and compare with ECLipsE in the case where & > 1 (Fig. 2). We also include the case < 1 in Appendix B. The key idea behind ECLipsE-Fast is that instead of keeping the shape of M, fixed, and contracting the ellipsoid itself, as ECLipsE, we first find the largest inscribed ball (dark green) for the ellipsoid of M,. Then, contract this ball to the maximum extent such that it still contains W W,-1- The resulting ball (dark blue) is precisely the smallest circumscribing ball for the ellipsoid of W W Note that this approach serves as an approximation for the process of contraction depicted in Fig. ME (corresponding ECLipsE), thus yielding smaller с.- We use this approximation to achieve closed-form solution, which significantly increases the computational speed.
W.
W.
(a) Geometric Intuition of ECLipsE-Fast
(b) Geometric Intuition of ECLipSE
Figure Comparison between ECLipsE-Fast and ECLipsE with G >
Remark 3. In Lemma A the analysis initially fixes the shape of F; However, when optimizing Ar the shape of the feasible region depends Fú which can vary with different A;- Z4- Thus, this approximation, which allows for scalable distributed algorithm to solve the centralized problem (L) introduces an unavoidable but minor tradeoff in achieving global optimality.
Experiments
We implement our algorithms randomly generated neural networks and ones trained the MNIST dataset. The details of the experimental setup, and training of the neural networks (both randomly generated and trained on the MNIST dataset) are described in Appendix D
Baselines, For ECLipsE, A.. E Z,11 can have different diagonal entries, which bench- marks to LipSDP-Neuron. For ECLipsE-Fast, A₃ = A4I, i Z,-1, which benchmarks LipsDr-Layer. Additionally, we compare our Lipschitz estimates the naive upper bound Lnaive I [1212[26), CPLip [[[] and LipDiff [20]. The codes for these baselines are avail- able at [54, (35, 20). Note that LipDiff is accelerated using node with 2 NVIDIA A100 GPUs (80G)
and 512 GB of memory.
4.1 Randomly Generated Neural Networks
We first consider randomly generated networks, where the number of layers are chosen from (2, 5, 10, 20, 30, 50, 75, 100), and number of neurons are chosen from {20, 40, 60, 80, 100), amount- ing to total of 40 experiments for each algorithm (including the baselines). We quantify the com- putation time and tightness of the Lipschitz bounds (raw data in Appendix E). The Lipschitz bounds presented in the following figures are normalized to the trivial upper bound for ease of comparison.
'htps://githbb.co www.m//uehuu//CCL.......
Note that SeqLip [T3] also often- used benchmark; however, we not consider since it does not represent a true upper bound for the Lipschitz constant. We also note that we do not include Chordal- -ipsSD [ as baseline. since only the case where = 0 in that work is valid, and all other cases, are no longer valid certifying the Lipschitz constant as discussed in Remark W as well [TS].

---

Case 1: Varying network depth (number of layers), We select a network with 80 neurons per layer, and demonstrate the scalability of our algorithm as network depth increases. Note that all baseline approaches fail to provide a Lipschitz estimate within a computational cutoff time of 15 min for networks larger than this size (see results in Appendix E) As the number of layers increases, the computation time for CPL.pp algorithm explodes (the algorithm does not return a Lipschitz esti- mate within the cutoff time beyond 20 layers); however, CPLip provides the most accurate estimates in smaller networks. LipDiff provides inadmissible Lipschitz estimates even for moderate networks, returning as much as 10-100 times the trivial bound (see Table 2a, Appendix [D for the estimates). Also, while LipDiff has similar computational time for smaller networks, computational time grows for deeper networks as recorded in Appendix EEI Table 2b. Consequently, we do not include these re- sults in the plots. SOSDD--Nuuro and LipSDP-Layer are also scalable to some extent; however, they fail for a networks of 30 and 50 layers respectively. In contrast, the computation time for ECLipsE and ECLipsE-Fast stays low and grows only linearly with respect to the number of layers (Fig. (B.. Notably, ECLipsE-Fast is significantly faster (thousands of times) than LipSDP-Layer owing to the closed-form solution at each stage, while ECLipsE is also considerably faster than LipSDP-Neuron. The Lipschitz estimates given by algorithms ECLipsE and ECLipsE-Fas are very close the ones from LipSDP-Neuron and LipSDP-Layer respectively (Fig. (R), and out- perform the trivial bound. As the number of layers increases, the normalized Lipschitz estimates are smaller, indicating that our algorithms are well-suited very deep networks.
Nomaton to
250
Lo500 layee
LiSD
0a- 04-
Pa-K
200
Cou
dayle
50
28
60
63
100
23
400
Number Lapera
Number Lapers
(a) Lipschitz estimates normalized to trivial bound
(b) Computation time (scconds)
Figure 3: Performance of ECLipsE-Fast and ECLipsE, with respect to baselines for increasing network depth, with 80 neurons per layer. The red x markings indicate that the algorithm fails to provide an estimate within the computational cutoff time beyond this network size.
Case 2: Varying neural network width (number of neurons per layer). We now examine the per- formance of our algorithms for wider (more hidden neurons per layer), rather than deeper networks (with more layers), and demonstrate the results for networks with 20 and 50 layers respectively (Fig. () While the complete raw data is presented in Appendix EL we discuss the results for 20 and 50 layer networks here, since they represent the network sizes where different baselines fail return Lipschitz estimates beyond the computation cutoff time of 15 min. Note that while LipDiff also manages to generate estimates for all network sizes in our 50 layers case, it once again provides inadmissible Lipschitz constants, returning as much as 10* - 10 times the trivial bound. Therefore, we do not include these results in Fig. @ (see Tables 3a and 3b in Appendix for the estimates and computation time.) We can observe from Figs. IR and Aril that the computation time needed for CPLip, LipSDP-Layer, and LipSDP-
significantly increases with the number of neurons, while the computation time of our method still grows linearly. Meanwhile, the Lipschitz estimates from algorithms ECLipsE and ECLipsE-Fase
are close to the ones from LipSDP- -Nuurnn and LipSDP-Layer respectively (Figs. 1. and (d).. Thus, we can conclude that our method significantly improves scalability for wider neural networks.
Case 3: Comparison with LipSDP implementations. In order to address the scalability issue as the size of the network grows, LipSDP utilizes splitting approach, where the network is split into smaller sub-networks and the Lipschitz constants for each sub-network are composed at the end to obtain the final estimate. We benchmark our approach with respect to the performance of LipSDP- considering different sub-network sizes. Note that our algorithms do not
Layer and LipSDP require any splitting, since they remain scalable to large networks. As the FNNs are larger than the ones in previous cases, we change the cutoff time to 30 minutes. We conduct two sets of experiments
8

---

Lnn Lod00rige 0%%
300
OCURIC
230
130
20
20
60
75
130
25
70
No mibrrr of Neusons
Numbor of Ve Jonn
(a) Lipschitz estimates normalized trivial bound
(b) Computation time (seconds)
02
9.5
Lidt'
CouReE
Number of Nevsons
Numborr of 1000
(c) Lipschitz estimates normalized to trivial bound
(d) Computation time (scconds)
Figure 4: Performance of ECLipsE-Fast and ECLipsE with respect to baselines network width increases, for a randomly generated network with 20 layers ((a) and (b)) and 50 layers ((c) and (d)). The Red x markings indicate that the algorithms fail to provide estimate within the computational cutoff time of 15 min beyond this network size.
study how our algorithms perform on considerably deep neural networks and how network width affects these results.
In the first set of experiments, consider FNNs with 100 layers, with the number of neurons chosen from the set 180, 24, 160). The splitting sizes for LipSDP- and LipSDP-Layer are 5 and 10. We represent different FNN sizes by shapes and different algorithms by the color in Fig. BL By plotting the normalized Lipschitz estimates and computation times on the two axes, we illustrate how efficient and accurate an algorithm is by how close the correspond- ing data point is to the origin. We observe that the data points for ECLipsE-Fast are at the leftmost extreme of the plot, in- dicating that it is the most efficient algo- rithm. Further, ECLipsE-Fast also out- performs the red cluster (LipSDP-layer with the network split into 3) in both tightness and speed. Comparing data points of the same shape, ECLipsE-Fast outperforms LipSDP- Layer for all sub-network splits both in terms of the Lipschitz estimate and the computation time. Finally, the data points corresponding to ECLipsE are clustered at the bottom left, demonstrating that it is relatively more accurate and efficient than all LipSDP methods, matter how the network is split.
teurcee
120 neurnee 140 nourons
180 rouroes
DCLipet cckeet-rot Lioiue upor in
Nomalbed
Ladiof-eaaanit Licice oppeii
Luston 12
0.85
0.8
0.55
200
1200
1600
Time Used
Computation time vs estimation ac- curacy for ECLipsE, ECLipsE- -Fast and LipSDP splitting with different nub-network sizes.
Figure 5:
In the second set experiments, we explore even wider networks. Specifically, we choose a fairly deep neural network with 50 layers and vary the width from 150 to 1000. The splitting size for LipSDD-Neuroo and LipSDP-LLaer 5. The resulting Lipschitz estimates (normalized with respect to trivial upper bounds) and the computation time are provided in Tables 4a and 4b of Appendix

---

EII due to space limitations. From these results, we observe that ECLipsE-Fast is extremely fast even for very wide networks, with a running time of only 15.63 seconds for a network width of 1000, while the computation time for LipSDP-Layer grows significantly. Also, while ECLipSE fails when the width reaches 300, it is comparable to LipSDP-Neuron split into 5 sub-networks in terms of time performance.
Remark 4. We notice that when the neural networks are significantly wide, ECLipsE takes more than 30 minutes while ECLipsE-Fast remains efficient. This observation can be explained by examining the computational complexity of these algorithms. Note that we directly state the com- putational complexity of each algorithm here for brevity; the detailed derivations are included in Appendix Q1 Suppose a neural network has hidden layers with m neurons. Then, the computa- tional cost for LipSDP and ECLipsE are O(n' 'm') ) and (nnm²) respectively. We can observe that the complexity is significantly decreased in terms of the depth, but is the same in terms of the width, immediately indicating the advantage for deep networks. Nevertheless, as m grows, the difference between On (n'mm²) "m") and (nm²² is still drastically enhanced, especially with large More impor- tantly, for ECLipSE-FaS FFastt the computational cost drops to O(nm²). This is the fastest one can expect if the weights each layer are treated whole.
4.2 Neural Networks Trained on MNIST.
We now demonstrate algorithms four networks trained on the MNIST dataset (see Appendix D for details) to achieve an accuracy of at least 97%. The resulting networks are not very deep (3 layers), with 100, 200, 300, and 400 neurons. We set a computational cutoff' time of 30 min to obtain Lipschitz estimates. As described in the note on Baselines earlier in this section, ECLipsE benehmarked against LipSDP-Neumm Neuron and ECLipsE-Fast is benchmarked against the faster LipSDP-Layer due to their mathematical structure. From Fig. DR we can see that ECLipsE-Fast sigmificantly faster than LipsD,-Layer, while ECLipSE is also considerably faster than LipSDP- Neuron. Note that all algorithms provide very similar Lipschitz estimates (Fig. ba). Therefore, for networks that are not very deep, such as those this example, ECLipsE-Fast choice, since it significantly outperforms all algorithms in terms of speed, while the approximation error due to the closed-form solution not too significant compared to the baselines.
the optimal
1000
ECUDEE
1400
1230
Nonakloo Lasen
03
1000
430
200
200
400
202
202
400
Numbar of Nousona
Nambor of No.noms
(a) Lipschitz estimates normalized to trivial bound
(b) Computation time (seconds)
Figure 6: Performance of ECLipsE-Fast and ECLipSE, with respect to baselines for increasing number of neurons, for a 3-layer network trained on MNIST. The red x markings indicate that the algorithm fails to provide an estimate within the computational cutoff time beyond this network size.
5
Conclusion
We propose a scalable approach to estimate Lipschitz constants for deep neural networks by develop- ing a new matrix decomposition that yields two fast algorithms. Our experiments demonstrate that our algorithms significantly outperform the state-of-the-art in terms of computation speed, while providing comparable Lipschitz estimates. We envision that further computational speedup can be achieved through sparse matrix multiplication and eigenvalue estimation techniques, and leveraging autodiff frameworks, along the lines of [20]] While we can unroll the convolutional layers in CNN structure to a large fully connected neural network layer to apply ECLipsE and ECLipsE-Fast to estimate Lipschitz constant, better compositional methods that are tailored to feature the convolu- tional layers are expected for future work. Similarly, other architectures, such as residual networks, present additional challenges due to their unique structures and will be considered in future research.
10

---

Acknowledgment. This work was partially supported by the Air Force Office of Scientific Research grant, FA9550-23-1-0492.
References
[1] M. Fazlyab, M. Morari, and G. J. Pappas, "Safery verification and robustness analysis of neu- ral networks via quadratic constraints and semidefinite programming." IEEE Transactions on Automatic Control, vol. 67, no. 1, pp. 1-15, 2020.
[2] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, "Spectral normalization for generative adversarial networks," in International Conference on Learning Representations, 2018.
[3] C. Finlay, A. M. Oberman, and B. Abbasi, "Improved robustness to adversarial examples using lipschitz regularization of the loss," 2018.
[4] Y. Tsuzuku, I. Sato, and M. Sugiyama, "Lipschitz-marge" training: Scalable certification of perturbation invariance for deep neural networks," Advances neural information processing systems, vol. 31, 2018.
[5] I.. Brunke, M. Greeff, A. W. Hall, Z. Yuan, S. Zhou, J. Panerati, and A. P. Schoellig, "Safe learning in robotics: From learning-based control safe reinforcement learning," Annual Re- view of Control, Robotics, and Autonomous Systems, vol. 5, pp. 411-444 2022.
[6] H. Yin, P. Seiler, and M. Arcak, "Stability analysis using quadratic constraints for systems with neural network controllers," IEEE Transactions on Automatic Control, vol. 67, no. 4, pp. 1980- 1987, 2021.
[7] A. Aswani, H. Gonzalez, S. S. Sastry, and C. Tomlin, "Provably safe and robust learning-based model predictive control," Automatica, vol. 49, no. pp. 1216-1226, 2013.
[8] W. G. Y. Tan and Z. Wu, "Robust machine learning modeling for predictive control us- ing lipschitz-comstrainedd neural networks," Computers & Chemical Engineering, vol. 180, 108466, 2024.
[9] Y. Xu and S. Sivaranjani, "Learning dissipative neural dynamical systems," IEEE Control Sys- tems Letters, vol. pp. 3531-3536, 2023.
[10] P. L. Bartlett, D. J. Foster, and M. J. Telgarsky, "Spectrally normalized margin bounds for neural networks," Advances in neural information processing systems, vol. 30, 2017.
"Spectrally-normalized
[11] H. Zhang, Z. Zheng, and J. Lavaei, "Gradient- based algorithms for convex discrete optimiza- tion via simulation." Operations research, vol. 71, no. pp. 1815-1834, 2023.
[12] C. Herrera, F. Krach, and Teichmann, "Estimating full lipschitz constants of deep neural networks," stat, vol. 1050, p. 8, 2020.
[13] A. Virmaux and K. Scaman, "Lipschitz regularity of deep neural networks: analysis and effi- cient estimation." " Advances in Neural Information Processing Systems, vol. 31, 2018.
[14] M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. Pappas, "Efficient and accurate es- timation of lipschitz constants for deep neural networks," Advances in Neural Information Processing Systems, vol. 32, 2019.
[15] A. Xue, L. Lindemann, A. Robey, H. Hassani, G. J. Pappas, and R. Alur, "Chordal sparsity for lipschitz constant estimation of deep neural networks." in 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3389-3396, IEEE, 2022.
[16] I.. Combettes and J.-C. Pesquet, "Lipschitz certificates for layered network structures driven by averaged activation operators," SIAM Journal on Mathematics of Data Science, vol. 2, no. 2, pp. 529-557, 2020.
[17] M. Jordan and G. Dimakis, "Exactly computing the local lipschitz constant of relu net- works," Advances in Neural Information Processing Systems, vol. 33, pp. 7344-7353, 2020.
11

---

[18] Z. Wang, G. Prakriya, and S. Jha, "A quantitative geometric approach to neural-network smoothness." Advances in Neural Information Processing Systems, vol. 35, pp. 34201-34215, 2022.
[19] M. Fazlyab, T. Entesari, A. Roy, and R. Chellappa. "Certified robustness via dynamic margin maximization and improved lipschitz regularization, Advances in Neural Information Process- ing Systems, vol. 36, 2024.
[20] Z. Wang, B. Hu, A. J. Havens, A. Araujo, Y. Zheng, Y. Chen, and S. Jha, "On the scalability and memory efficiency of semidefinite programs for lipschitz constant estimation of neural networks," in The Twelfth International Conference on Learning Representations, 2024.
[21] Pauli, D. Gramlich, and Allgöwer, "Lipschitz constant estimation for 1d convolutional neural networks," in Learning for Dynamics and Control Conference, pp. 1321-1332, PMLR, 2023.
[22] Latorre, Rolland, and V. Cevher, "Lipschitz constant estimation of neural networks via sparse polynomial optimization." arXiv preprint arXiv:2004. 08688, 2020.
[23] R. Wang and I. Manchester, "Direct parameterization of lipschitz-bounder deep networks," in International Conference on Machine Learning, pp. 36093-361 10, PMLR,, 2023.
[24] A. Araujo, A. Havens, B. Delattre, A. Allauzen, and B. Hu, "A unified algebraic perspective on lipschitz neural networks," arXiv preprint arXiv:2303..m 03169,11699 2023.
[25] A. Havens, A. Araujo, S. Garg, F. Khorrami, and B. Hu, "Exploiting connections between lipschitz structures for certifiably robust deep equilibrium models," Advances in Neural Infor- mation Processing Systems, vol. 36, 2024.
[26] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, "In- triguing properties of neural networks," arXiv preprint 1311v:131..6199, 2013.
[27] Z. Shi, Y. Wang, H. Zhang. J. Z. Kolter, and C.-J. Hsieh, "Efficiently computing local lips- chitz constants of neural networks via bound propagation," Advances in Neural Information Processing Systems, vol. 35, pp. 2350-2364 2022.
(28) M. Newton and A. Papachristodoullu, "Exploiting sparsity for neural network verification," in Learning for Dynamics and Control, pp. 715-727, PMLR, 2021.
[29] Y. Sulehman and T. Mu, "Scalable lipschitz estimation for cnns," arXiv preprint arXiv:2403.18613. 2024.
[30] Pauli, Koch, Berberich, P. Kohler, and Allgöwer, "Training robust neural networks using lipschitz bounds," IEEE Control Systems Letters, vol. 6, pp. 121-126, 2021.
[31] E. Agarwal, S. Sivaranjani, V. Gupta, and P. Antsaklis, "Sequential synthesis of distributed controllers for cascade interconnected systems," in 20/9 American Control Conference (ACC), pp. 5881--8811111 IEEE, 2019.
[32] E. Agarwal, S. Sivaranjani. V. Gupta, and P. J. Antsaklis, "Distributed synthesis of local con- trollers for networked systems with arbitrary interconnection topologies," IEEE Transactions on Automatic Control, vol. 66, no. 2. pp. 683-698, 2020.
[33] F. Agarwal, S. Sivaranjani, V. Gupta, and P. Antsaklis, "Compositional verification of passivity for cascade interconnected nonlinear systems," in 2020 28th Mediterranean Conference on Control and Automation (MED), pp. 319-324, IEEE, 2020.
[34] A. Robey, "Lipsdp: Lipschitz estimation for neural networks." Attps:: github com/ arobevi/LipSDE 2024. Accessed: 2024-05-22.
[35] A. Xue, "Chordal-lipsd:: chordally sparse formulation of the lipsdp technique for bounding lipschitz constants of a feedforward neural network."
AntonXue chorda lippdp, 2024. Accessed: 2024-05-22.
12

---

Appendices
A
Technical Proofs
Proof of Relation in Assumption II We show how the slope-restrictedness of the activation func-
tion implies (l). The inequality a(vi - 02) S d(vi) ((12) S B(11 - U2) that holds elementwise yields
A [()(e)) - ((v2)) a(vi - v2)1, x ((((v)) - ((1))) B(ui u2)1, S O,
VY' 00
where subscript i indexes the Tt element of the vector.
Summing all the inequalities for E IR" and letting A = diag(A X2 ,2.... )²), we have
((())))-(1=)))aaff - -2)]² A ((((c)))((12)))
-22] 50.
In other words, we have the following quadratic inequality
+ 3
(ő(v1)- ( a +
(p((11))(((22)) (22) A(vi v2)
2 (u1 v2) )
u2) A(v1 U2) S 0,
which can be directly rewritten (2) with p a and a+L
2
Proof of Theorem 1. For any two inputs 21 and 22 let 2
22
(i) (6) (1)
11
i Z. be computed
as in (.)) Define Az 2( 22
(t) i {0} U Z and Av(i)
1
(1)
2/2
())
.J Z, By both left
and right multiplying the left hand side in (E) by the vector (A (0) Ag Ag A=TTT we have
(0) A2 (0) +
Σ
1-1
A
T
PWTAW, -MWTT A, Wm,,W;
A=
A
A
(13)
1=1
- -F(A. W O.
Now, we show that every summand in the above inequality (L3) is negative semidefinite. In fact, with Assumption II using notation An =0(") 2 and taking A = A;, we can write
(6) and (p(x()) = (()l1) ((12))) e Z,
Anli) Ao(c(o)
I'
PAd -mA,
-mA,]
Av(
50.
(14)
A;
A
Note that Ar(O = (W;z) (1-1) + b:) (Wi=h--)) express these relationships in matrix form as
+ b,) = (11 and Ad(Ut) = Ast. We can
Av(i) Ad(u(o)
] =
W 0 A
0
1
A=
(15)
Substituting (15) into (1 (4, we have
A A2(1-1)7 T
PWT AWW, W,
-mW?TA Ar
(2(1-1)
5..
(16)
(
A
Combining (13) and (IG), we have
(A F(A= WT W (1-1 2 0.
(17)
Similarly, as the last layer is a linear layer, A (r (1) (1- Then (l7) is exactly
(A < ) 00=00)=~Z00
yielding upper bound / for the Lipschitz constant.
13

---

Proof of Theorem 2. Applying Lemma in [B we define
R, WT, A 2t,
(18)
and
if 0,
P. =
Aj F47-F
i E 21-21
(19)
if = 1-1
Then, with P; and R, defined above, we directly have
X Xx + FWTWi
if E (Z) if 1
(20)
In other words, the sufficient and necessary condition
X; > 0, E {0) U U is equivalent to FW, M FW, Wi 0,
M, O,
V Zi-2,
(21)
which is the same (2I1).
Proof of Proposition 1. As M; i Ze-2 has been guaranteed, it remains ensure that
Mi-1 - FW? Wi > 0 by Theorem B. This is equivalent to Mi-1/F > WFW, W,. Therefore, the
smallest possible 1/F is man (W7 (M Then by Theorem M. the upper bound for the
Lipschitz constant is 11FF Vo mman (W7 (((M)))--)).
Proof of Lemma 1. M, > indicates (M,) 0. Then for Vou + 0,
1/ T W (M.) (MM:)-WW110 10 (WI+ v0) (M.) W 00 2 0,
(22)
meaning that all eigenvalues of W;+1 (Ma) are non-negative. As W++ * 0, we know that the largest eigenvalue is positive and should be the same as a mar (W (M -' > 0.
141
Now consider any non-zero eigenvalue Ar of matrix Wi+ (M.) 141 -W and let e * 0 be its corre- sponding eigenvector. Then,
W (M-
dava-
(23)
Left multiplying both sides with WTT E+1 we have
W ++1 (M,) 22) = W 1+1 W (M+) = W Aeta = Aa Aa (24)
As A * O, know that WT. c+1 Uo * 0 from (23) (Otherwise, Adva with va # 0 will lead >₂ = 0). With W * 0, (2E)) implies that Xa is also eigenvalue of WT W (M,)
corresponding to eigenvector WT Va + Conversely, for any non-zero eigenvalue A of W W.r:W.i ( corresponding to eigenvector
26 * 0, we have
W W (M,) (M.)) -0p = Ap
(25)
Let U. X, (M+1(M)-- We have 2s W. Ve. Then we substitute th on the both sides in and obtain
14
WT W = > No WH, W (M.)
Left multiplying both side with W:+ (M,) we further have
W W1+1 W WT. W
= (M, 141
Let v.a W441(M)
-w WWH Vo. we finally have
W -
ADVA-
Similarly, we can conclude that A * the eigenvalue of ( and 2a the corre- sponding cigenvector.
14

---

Proof of Lemma? 2. To prove that {Aş M, > 0, E D M, > 0,A, E D+}. it suffices
to show that M; - M, 2 0 for any 7 E (0, 1). In fact,
M, M, = A, A,F,A, (A, 1 A.F.)) 1-7 A.FAA,
(26)
At stage i, M, > is guaranteed. Then, similar to (22), we know that F, = WI(M 2 0 Since A, E D+ and 0 < 7 < 1, implying -/2 > O, we have 1 F,AA 2 0.
Proof of Proposition 2. Recall that by definition, Fi+t = W - Applying Lemma II
we have man (Fs+1) = maz (WT, 141 W Meanwhile, with M, c; WT W411 + N,
W H41 W Wc+)(MM) = (W W + W + W (a 241 W44 + +N)
1
N
G Ci (M)
I
(27) WIth N 2 0 and M, > 0 after A, is decided, we show that N (M,) only has non -egative cigenvalues. As M, > is guaranteed to symmetric according to (.). there exists symmetric square root for (M;) and we denote it to be (M:) Then N(M)) is similar to (M) ((M)) 1 thus sharing the same eigenvalues. Furthermore, for Vz o O,
x² *M..) N(.)) 2x ((M)) N (M.) tx 2 0.
indicates (M,)-N((M.) only has non-negative eigenvalues. The first equation holds by the symmetry of (M,) and the second inequality is because of the definition of positive semi- definiteness of N. Therefore, with G; > O, the eigenvalues of N c, (M,) = N(M)) are all non-negative. and all eigenvalues of W (M.) should be less than equal 1/c. On the other hand, as N is singular, N (M,) -1 is also singular, thus having eigenvalue 0. Therefore,
mmaa (Fi-)) = maz (W 2 ( -1) 1/a.
Proof of Proposition 3. We first show that if M > 0, the feasible region is always non-empty for Vi E Z1-1. 1. We use a to denote maaz (W; - o maa (Fi). We take A; 2 and As W, + 0, i Z, we have and mann (F,) > O, ensuring A, D+
C a-Emez (W2, W(11) and O > O. Further,
A
AM WW? A. c, 1
A,
4
2
1
14
0.9
1
aT
(WT WH+1)
(28)
0
4
σ Tmax (WT,.
1
0.9
> O.
Therefore, the feasible region least includes the A, and o, we specified, and is thus not empty. To make the feasibility complete, we prove that M, > 0, Vi E (0) 2 by induction. When i = O, M;- = My = T> O. When it comes to stage we have by induction that M,-1 > is true. As A; are obtained satisfying (I2) with q > 0 and recall the recursive relation for M,, i Z,-1 to 0.
be M, A, - (M,, "W"" A,, we have M, > c, eWT,
We now prove by contradiction that the optimal value & is the largest constant such that M, can be written M, e; c&WH+ W + N, where N is some singular matrix that N 2 0. M; c; WT Wi+1 + N. Suppose there exists a è > e such that satisfies all the constraints. Then, from the first constraint in (I2)), we have
(a & W) W4+1 + N = M, &W W > 0
(29)
Let * 0 be the eigenvector of N corresponding to eigenvalue O. Observe that 8" ((G - W. W + N) v
= ((G WWW W4ta a
(30)
= (a - 2.) o" (W 2 W 0 u 0.
15

---

The last step holds because - < 0 by definition of é. It contradicts (29)
Proof of Proposition 4. When A; ArT,
(^r I AAFiAA)) -1
115 - -1-12177)
As M, = A₁ A,,FA, > O, we have
maa ((N-
(31)
X -4 No (Fi)/4
Minimizing the above spectrum is equivalent to maximizing the denominator X - Xm (Fi) in (EI), which is quadratic in A To find the optimal X, we set the derivative of the denominator with respect to X; to be 0, and obtain the closed-form solution X; (F,)
Moreover, with A,
Omas and Fi 0 guaranteed stage i, have
1
M = A, - A,A., m (Fi)
1
B Geometric Analysis for ECLipsE-Fast
The geometric analysis for algorithm ECLipsE-Fast analogous to Fig. comparing the case where G and in other cases shown in Fig. M
(a) For > 1
(b) For other cases
Figure 7: Geometric Intuition of "ELLipsE-Fasttie & > 1 and otherwise.
C Computational Complexity Derivation
We derive the time complexity for both ECLipsE and ECLipsE-Fast in detail here. Suppose neural network has n hidden layers with m neurons. Then, the large matrix in Theorem MI has dimension nm + O(1) and the decision variable is of size nm + O(1.. Note that the computational complexity for solving an LMI with the size of the matrix constraint being size A and the number of decision variables being B is A + A A²B²). Therefore, the computational cost for LipSDP is O(n'm²), Contrarily, ECLipsE solves sub-problems as in Eq. ( each involving matrix of size ((m) and m decision variables. The corresponding total computational cost is n (O(m² 3 + +mm?)) = O(nm²). This directly indicates the advantage of ECLipSE for deep networks. Also, as grows, the difference between O(n'm²) and (nnm² is still significantly enhanced, especially with large n. Regarding ECLipsE-Fast. we note that we do not need to solve any SDPs and the computational cost drops to O(m²) Onnm²). This is the fastest one can expect the weights on each layer are treated as whole.
O(nm + O(1)) + (nm + 0(1)) + 0(1))
D Experimental Setup and Data Generation
Experimental Setup. All experiments implemented Windows laptop with 12-core CPU with 16GB of RAM.
Randomly Generated Neural Networks. We set the input dimension to be 4 and the output dimen- sion to be 1. The activation functionsare chosen to be ReL.U, and the number of neurons in each hidden layer is set to be the same. We randomly generate weights for each layer to follow the normal
16

---

distribution. Also. in order to avoid the case where the Lipschitz constant is too large or too small and may cause numerical issues, we scale the weights on each layer such that the norm randomly chosen in [0.4, 1.8), following uniform distribution.
MNIST. For training the dataset MNIST, the input dimension is 784 and output dimension is 10, which is compatible with the dataset. he activation functionsare chosen to be ReLU, and the number of neurons in each hidden layer is be the same. We train neural networks using the SGD optimizer with a learning rate of 0.01 and momentum of 0.9 until they achieve at least 97% accuracy on test data.
17

---

E Additional Experimental Results
The Lipschitz constant estimates and computation times for randomly generated neural networks with the number of layers chosen from {2.5, 10, 20, 30, 50, 75, 100), and number of neurons are chosen from {20, 40, 60, 80, 100); are provided below.
Table la: Lipschitz constant estimates
Neurons') Aitronss(Lapp Layers
2
5
10
20
30
50
75
100
Trivial Bound
20
1.020
3.171
1.173
6.725
3,430
49.696
1.091
0.002
40
0.952
3.356
0.910
3,431
0.004
260.807
2.895
0.119
60
1,433
2.830
0.040
0.067
0.706
0.013
16.433
8,890
80
0.875
0.418
0.681
4.023
0.010
0.057
1.291
0.054
100
1.046
0.626
4.144
0.346
2.521
46.466
6.933
95.263
Neurons's LLyers
2
5
10
30
50
75
100
20
0.856
2.485
0.822
4.189
1.985
18.974
0.290
0.000
ECLipsE
40
0.775
2.696
0.722
2.434
0.003
137.421
1.413
0.043
1.207
2.391
0.031
0.051
0,480
0.008
9.187
4.388
80
0.737
0.338
0.565
3.078
0.007
0.039
0.810
0.030
100
0.884
0.527
3.414
0.276
1.904
33.261
4.524
57.734
Neurons' Layers
Layers
2
10
30
50
75
100
SCLipsE-Faal Fast
20
0.941
2.825
0.990
5.354
2.612
30.884
0.568
0.001
0.868
3.030
0.814
2.912
0.003
191.736
2.026
0.072
60
1.324
2.611
0.035
0.059
0.588
0.010
12.355
6.285
80
0.809
0.378
0.622
3.544
0.009
0.047
1.027
0.041
0.968
0.577
3.779
0.310
2.204
39.529
5.633
74.570
Neurons's Layers
2
5
10
20
30
50
75
100
LipSDP-Neuron
20
0.856
2.481
0.819
4.165
1.978
18.851
0.287
0.775
2.693
0.721
2.430
0.003
137.025
60
1.207
2.390
0.031
0.051
0.479
80
0.737
0.338
0,564
3.077
100
0.884
0.526
3.413
0.276
Neurons' Layers
2
5
10
20
30
50
75
100
LipSDP-Laye Layer
20
0.938
2.814
0.985
5.327
2.607
30.763
0,565
0.863
3.019
0.812
2.901
0.003
190.489
60
1.319
2.606
0.035
0.059
0.584
0.010
0.806
0.377
0.621
3.531
0.009
100
0.965
0.575
3,770
0.310
2.77
Neurons Neurons\Layer Layers
2
5
10
20
30
50
75
100
0.469
1.408
0.493
2.669
CPLip
40
0.432
1.510
0.406
1.451
60
0.660
1.303
0.018
0.029
80
0.403
0.189
0.311
100
0.483
0.288
1.885
18

---

Table 1b: Computation time (scconds)
Trivial Bound
Neurons's LLayers
2
5
10
20
30
50
75
100
N/A
Neurons Layers
2
5
10
20
30
50
75
100
20
0.374
1.393
2.776
6.243
10.246
16.731
24.533
37.118
ECLipsE
0.572
2.115
4.263
8.944
15.730
27.977
36.769
52.201
60
1.007
3.551
7.768
14.938
25.616
46.128
72.479
109.913
80
1.381
5.428
11.650
28.458
43.255
82.461
120.167
157.274
100
2.346
7.818
18.265
35.685
53.392
102.400
160.400
188.536
Neurons') Layers
2
5
10
20
30
50
75
100
20
0.001
0.002
0.001
0.002
0.003
0.006
0.007
0.010
ECLipsE-
40
0.002
0.004
0.008
0.018
0.029
0.036
0.060
0.057
60
0.002
0.005
0.010
0.026
0.038
0.057
0.076
0.083
0.004
0.009
0.024
0.051
0.056
0.089
0.127
0.136
100
0.007
0.016
0.021
0.070
0.058
0.095
0.151
0.190
Neurons' Layers
2
5
10
20
30
50
75
100
LASDP-Neuron
5.684
6.691
8.944
9.876
15.356
83.294
153.800
373.500
40
6.974
8.192
12.519
30.342
87.703
498.750
15min
60
8.285
9.410
18.654
110.670
438.040
> 15min
8.812
10.749
43.734
303.440
15min
100
8.876
15.009
88.894
789.330
Neurons's Layers
2
5
10
20
30
50
75
100
5.594
5.941
7,800
9,013
9.831
23.968
117.23
342.93
LipSDP-Laye
40
6.941
7.616
8.829
19.676
40.463
216.22
15min
7.849
8.790
12.591
51.714
140.270
692.47
80
8.087
9.834
17.815
125.050
393.480
>> 15min
100
8.431
10.356
33.859
210.090
687.710
Neurons Layers
2
20
75
100
20
==
0.001
0.105
158.603
15min
CPLip
40
R²0
0.003
0.385
614.917
R=0
0.006
0.59
15min
80
R=0
0.018
1.633
15min
100
==
0.079
3.851
19

---

Table 2a: Normalized Lipschitz Estimates for Randomly Generated NN with 80 Neurons
Layers
ECLipsE
ECLipsE-Fan Fast
LipDiff
LipSDP-Neuron
LipSDP-Layer
CP-Lip
20
0.765184
0.88079
1.72459
0.76481
0.877786
>15min
30
0.737564
0.863682
155,8985
>15min
0.861134
50
0.669903
0.823353
5.320799
>15min
75
0,627432
0.795877
18.57997
100
0,557111
0.751101
>15min
Table 2b: Time used (sec) for Randomly Generated NN with 80 Neurons
Layers
ECLipsE
ECLipsE--Fas
LipDiff
LipSDP-Neuron
LipSDP-Layer
CP-Lip
20
28.45839
0.0515
22.23
303.44
125.05
>15min
30
43.25548
0.05645
51.22
>15min
393.48
50
82,46052
0.089058
178.03
>15min
75
120.1665
0.126933
532
100
157.2741
0.136244
>15min
Table 3a: Normalized Lipschitz Estimates for Randomly Generated NN with 50 layers
Neurons
ECLipsE
ECLiisEE-Fas
LipDiff
LipSDP-Neuron
LipSDP-Layer
CP-Lip
20
0.381796
0.621443
118628.2
0.379323
0.619014
>15min
40
0.526908
0.735163
2635012.67
0.525388
0.730384
60
0.649970
0.810128
23.46069
>15min
0.808237
80
0.669903
0.823353
5.505175
>15min
100
0.71581
0,850702
10622.75
Table 3b: Time used (sec) for Randomly Generated NN with 50 Layers
Neurons
ECLipsE
ECLipsE-Fass
LipDiff
LipSDP-Neuron
LipSDP-Layer
CP-Lip
20
16.73062
0.005613
12.31672
83.294
23.968
>15min
40
27.97682
0.03643
34.29124
498.75
216.22
60
46.12812
0.056791
86,27217
>15min
692.47
80
82.46052
0.089058
178.2235
>15min
100
102.4001
0.095034
327.946
20

---

Table 4a: Normalized Lipschitz Estimates for Randomly Generated NN with 50 Layers
Neurons
ECLipsE
ECLipsE-Far Fast
LipSDP-Neuron Split by LipSDP-Layer Split by
150
0.743745
0.867548
0.758217
0.87342
200
0.773494
0,883758
0.785171
0.888306
300
>30min
0.897008
>30min
0.899164
400
0.899916
>30min
500
0.903529
1000
0.912093
Table Time Used (sec) for Randomly Generated NN with 50 Layers
Neurons
ECLipsE
ECLipsE-Fast
LipSDP-Neuron Split by 5
LipSDP-Layer Split by
150
387.7
0.387262
451.07
93.129
200
1386.6
0.584115
1377.9
210.16
300
>30min
1.321177
>30min
612.47
400
2.657505
2110.9
500
3.7435
>30min
1000
15.63342
Broader Impacts
This work is primarily theoretical and pertains obtaining upper bounds on the Lipschitz constant, which can serve as measure of the robustness of deep neural networks, and does not have any direct societal impact.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims our abstract and introduction accurately reflect the paper's scope and contributions. All the theoretical and experimental results are aligned with the claims made in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We clearly discuss all the theoretical assumptions behind our work and the classes of networks for which this work is applicable. We also discuss and demonstrate the computational efficiency of the proposed algorithms for different network sizes.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
22

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide the complete list of assumptions behind the theoretical results in Sections 2 and 3 of the main paper. We also provide the key ideas and geometric intu- ition behind the proofs in Section 3. The detailed proofs of all results are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the experimental details are described in the Appendix, and all the code and data are submitted along with the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
23

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code and data submitted along with the paper, and will be open- sourced upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
public /ucc/quidee CCdeeSuome ss wswonnoloocooooo for more details.
While we encourage the release of code and data, understand that this might be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ittps:
//nips, cC/ http://c/cbbbcccccceeeeeeo /Codee/Codeeurre as casssooPooccn for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Yes, the paper details the experimental setting and benchmarks in Section
and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our algorithms to compute Lipschitz constant bounds are deterministic, and always yield the same result for given neural network up within numerical accuracy bounds.
24

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: The computational resources and computation time required for each experi-
ment are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics, and ensured that our paper conforms to these regulations.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
25

---

Answer: [Yes]
Justification: The paper is primarily theoretical, and does not have any immediate societal impact. We discuss this in the Appendix section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not pose any such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the datasets used to train our neural networks, and the code for the papers utilized as benchmarks evaluate algorithms are cited in the main text and in our code.
Guidelines:
The answer NA means that the paper does not existing assets.
26

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode com/ dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pas re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: All the code and data are submitted along with the paper, and will be released publicly with detailed documentation upon publication.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper mainly theoretical and does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
27

---

This paper is mainly theoretical and does not involve crowdsourcing or human subjects.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "cqFBgZhcuQ", "reviewer": "Reviewer_qsZt", "summary": "The authors are able to decompose a particular case of LipSDP-neuron exactly into a series of sub-problems leading to the proposed algorithm ECLipSE. In the case of the relaxed LipSDP-layer, it can be shown that each sub-problem can be solved analytically and eliminate the need for solving an SDP. The proposed algorithm ECLipSE-fast can provide Lipschitz estimates of deep-NN quite fast at the expense of increased conservativeness.", "questions": "-How does the full row rank assumption limit the applications of ECLipSE’s? Is it possible to relax this assumption? It seems like networks considered in this paper are only of constant width or decreasing in output dimension in the case of MNIST which will usually satisfy the full row-rank assumption.\n\n-Can you comment on the slight gap between the Lipschitz constant estimates shown in Appendix E between ECLipsE and LipSDP-Neuron? Is it that LipSDP is not as accurate in larger settings or is ECLipsE somehow slightly conservative?", "limitations": "Limitations are adequately addressed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "-The paper is well written and the theoretical arguments are well motivated and connected to the the numerical experiments. The paper mainly builds upon LipSDP, but I believe the theoretical insights to be novel.\n \n-The insight that LipSDP may be simplified into sub-problems is a significant contribution and advances the practical value of LipSDP. In particular, the proposal of ECLipsE-Fast which is an analytical solution to a relaxed sub-problem shows a significant improvement over the previous naive product bound and is very scalable.", "weaknesses": "-It seems that the approach doesn’t yet apply to residual networks or CNN commonly found in state-of-the-art vision models. For this reason, it seems difficult to show improved certified robustness on common image classification benchmarks which would benefit the most from increased scalability (CIFAR10-100, Tiny-imagenet, etc).\n\n-Certified robustness is mentioned as an application at several points in the paper. While the scalable and tighter Lipschitz estimates on random networks and MNIST certainly suggest some improvements, no practical measures of certified robustness are presented (e.g. robust accuracy).  For certified robust accuracy on MNIST, it is common to use 1-Lipschitz parameterization (SLL, AOL, other direct parameterizations) which eliminates the need for Lipschitz estimation. Would applying ECLipSE to composed 1-Lipschitz networks provide significantly tighter estimates in this case?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and positive evaluation of our work. We address your concerns as follows. \n>**It seems that the approach doesn't yet apply to residual networks or CNN commonly found in state-of-the-art vision models. For this reason, it seems difficult to show improved certified robustness on common image classification benchmarks which would benefit the most from increased scalability (CIFAR10-100, Tiny-imagenet, etc).**\n\nWe thank the reviewer for this question; since this was also raised by other reviewers, we have answered point I of the General Response.\n>**Certified robustness is mentioned as an application at several points in the paper. While the scalable and tighter Lipschitz estimates on random networks and MNIST certainly suggest some improvements, no practical measures of certified robustness are presented (e.g. robust accuracy).**\n\nWe show in experiments that for both randomly generalized networks, as well as ones trained for specific tasks, our algorithms consistently give promising results. Thus, we believe our method will benefit studies that certify robustness by building a relationship between the Lipschitz constant and robustness metrics (e.g. robust accuracy). For instance, [19] builds Lipschitz-based surrogates for certified radius, which is a classical robustness measure for classification tasks. We believe that such applications will benefit from our efficient Lipschitz estimation algorithms.\n>**For certified robust accuracy on MNIST, it is common to use 1-Lipschitz parameterization (SLL, AOL, other direct parameterizations) which eliminates the need for Lipschitz estimation. Would applying ECLipSE to composed 1-Lipschitz networks provide significantly tighter estimates in this case?**\n\nWe thank the reviewer for this question. While we consider a very general FNN structure, with only a slope restrictedness assumption on the activation functions, we anticipate that incorporating side information corresponding to specific parametrizations will yield better estimates in any algorithm. However, this is the subject of future work. Moreover, to the best of our knowledge, there is no theoretical guarantee of obtaining a tighter estimate for 1-Lipschitz networks. \n\nWe now turn to the question of whether Lipschitz constant estimation is necessary, given developments like 1-Lipschitz networks. While 1-Lipschitz parameterization is commonly used in robust training and the robustness is guaranteed by way of parameterization, the 1-Lipschitz parameterization has limited expressive power. For example, AOLs restrict the output to be a sum of individual contributions from inputs, which may not be sufficient for some complex tasks. In contrast, our theory applies to FNNs, which are a very general network structures with universal expressive power adopted in various network designs. Moreover, our theoretical development only requires the rather mild assumption of slope-restrictedness of the activation function, which is satisfied for most cases. Thus, our work facilitates fast Lipschitz constant estimation for more general structures, while still being applicable to direct parametrizations.\n> **How does the full row rank assumption limit the applications of ECLipSE’s? Is it possible to relax this assumption? It seems like networks considered in this paper are only of constant width or decreasing in output dimension in the case of MNIST which will usually satisfy the full row-rank assumption.**\n\nWe thank the reviewer for this question. Since this was also raised by another reviewer, we have answered it under the General Response section - see part II therein for a detailed response. In short, this assumption is not necessary, and both algorithms apply even when it is not satisfied.\n>**Can you comment on the slight gap between the Lipschitz constant estimates shown in Appendix E between ECLipsE and LipSDP-Neuron? Is it that LipSDP is not as accurate in larger settings or is ECLipsE somehow slightly conservative?**\n\nThe slight gap in performance, in fact, exhibits the high accuracy of ECLipsE.  While LipSDP-Neuron provides en efficient approach to estimate Lipschitz constants, it is practically not as scalable as our algorithms for large networks, and yields unacceptably long running times (>15min for 50 layers with only 60 neurons). Therefore, to implement LipSDP-Neuron, as suggested in [14], the NN must be split into several small sub-networks. However, the different sub-networks are treated independently, and their Lipschitz constants are multiplied at the end, thus completely cutting off the relationship among sub-networks. In contrast, our method always keeps the information from previous layers due to the exact decomposition in Theorem 2. This explains why LipSDP-Neuron yields less accurate results compared to EClipsE for the large networks discussed in Section 4.1 Case 3, and is precisely where our advantages lie. \n\nTheoretically, LipSDP is a centralized method where solving a large matrix SDP is unavoidable. In this context, we note that ECLipsE, being a distributed algorithm, will naturally result in a trade-off between speed and accuracy, yielding more conservative estimates than centralized algorithms like LipSDP. However, as we demonstrate in our experiments, the Lipschitz constant estimates from both ECLipsE and ECLipsE-Fast are fairly close to those obtained using LipSDP, while providing a significant computational advantage.", "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": "r7yr1eTZPm", "reviewer": "Reviewer_kbMy", "summary": "The paper proposes two novel Lipschitz constant estimation algorithms ECLipsE and ECLipsE-Fast. They are supported by a new decomposition theory developed for the Lip-SDP framework, derived by applying an existing theory (Lemma 2 of [31]). Experiments demonstrate the estimation accuracy and acceleration using toy radom networks and networks trained on MNIST data, by comparing with classical Lipschitz constant estimation method.", "questions": "The authors are invited to address my comments (1) and (2) in weakness section. If possible, it would be good to see some added results to help understand more the width capacity of the proposed algorithms.", "limitations": "Discussion on discussion is pretty limited. For instance, it  can be improved around the network width issue.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The targeted research problem is important and useful.\n\nThe decomposition theory is new and the two estimation algorithms are novel. I highly appreciate the beauty of the application of Lemma 2 of [31] in the proposed theory development.\n\nThe achieved result improvement is satisfactory for deep networks.", "weaknesses": "(1) The proposed algorithm is efficient at addressing network depth, but does not look at the width.  The theory behind self-explains the success of its capability of handling depth.  However, layers with very high numbers of neurons still pose challenges for the sub-problems, e.g., solving for Eq. (6) and Eq. (7). There is a lack of mentioning of this. Also the experiments only studied some modest widths up to 100 neurons. It would be good to see more empirical results with higher neuron numbers in each layer,  to understand the limit of the proposed algorithms on network width.\n\n(2) In experiments, there seems a missing comparison with the “parallel implementation by splitting” version of Lip-SDP as reported in their paper [14], which was proposed to address the depth issue.\n\n(3) The  method description can be improved, e.g., being more organised. The paper can present information that is more important and helpful to practitioners and general readers’ understanding in main paper, while leave some analysis and supporting lemmas to appendix. Personally, I find it helpful to see in the main paper a description of the existing Lemma 2 in [31] and the pseudo code of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging evaluation of our work and for the insightful questions on our experiments. We address all your questions as follows, and provide additional experiments to show the strength of our method for wide networks.\n\n>**(I). The proposed algorithm is efficient at addressing network depth, but does not look at the width. The theory behind self-explains the success of its capability of handling depth. However, layers with very high numbers of neurons still pose challenges for the sub-problems, e.g., solving for Eq. (6) and Eq. (7). There is a lack of mentioning of this. (II). Also the experiments only studied some modest widths up to 100 neurons. It would be good to see more empirical results with higher neuron numbers in each layer, to understand the limit of the proposed algorithms on network width. (III). Discussion on discussion is pretty limited. For instance, it can be improved around the network width issue.**\n\nWe thank the reviewer for these important questions, and answer them here. While we acknowledge that our computational advantage is more pronounced with respect to network depth, the speedup for wide networks is also significant, especially when the  network is also deep. To see this, we can assess the computational complexity for ECLipsE and LipSDP-Neuron. Suppose a neural network has $n$ hidden layers with $m$ neurons. Then, the large matrix in Theorem 1 has dimension $nm+O(1)$ and the decision variable is of size $nm+O(1)$. The computational complexity for solving an LMI with decision variables of matrix size $A$ and $B$ is $O(A^3+A^2B^2)$. Therefore, the computational cost for LipSDP (solving SDP involving the large matrix) is $O((nm+O(1))^3+(nm+O(1))^2(nm+O(1))^2)=O(n^4m^4)$. Contrarily, ECLipsE solves $n$ sub-problems as in Eq. (6), with each involving matrix of size $O(m)$ and $m$ decision variables. The corresponding total computational cost is $n\\times (O(m^3+m^2m^2))=O(nm^4)$. We can see that the complexity is significantly decreased in terms of the depth, but is the same in terms of the width, immediately indicating the advantage for deep networks. Nevertheless, as $m$ grows, the difference between $O(n^4m^4)$ and $O(nm^4)$ are still enlarged drastically, especially with large $n$. More importantly, for ECLipsE-Fast, we note that we  do not need to solve any SDPs as the solutions are all provided in closed-form from Propositions 1 and 4. Thus, the computational cost drops to $n\\times O(m^3)=O(nm^3)$. This is the fastest one can expect if the weights on each layer are treated as a whole. Admittedly, if a neural network is considerably wide, it can still pose challenges to the sub-problems regardless of all the accelerations we have achieved, in which case we will have to apply methods that split the weights themselves, introducing some unavoidable conservativeness. \n\nFrom the experiment side, we initially considered networks with up to 100 neurons, since benchmark methods like LipSDP-Neuron with 50 neurons and LipSDP-Layer with 70 neurons already fail to return estimates within the cutoff time of 15 min (see Figure 4). Meanwhile, both ECLipsE and ECLipsE-Fast still work well in these settings, demonstrating our advantages regarding width. \n\nTo further illustrate the strengths and limitations, we consider  randomly generated NNs with 50 layers as shown below, and find that (i) ECLipsE-Fast is extremely fast even for very wide networks, with a running time of only 15.63 seconds  for a width of 1000, while the computation time for LipSDP-Layer grows significantly, and (ii) ECLipsE is comparable to LipSDP-Neuron split into 5 sub-networks in terms of time performance (note that LipSDP-Neuron cannot return estimates for any of the cases without splitting, which slightly decreases its accuracy with respect to ECLipsE). We will include these additional results and discussions in the final version. Note that all the estimates are normalized with respect to trivial upper bounds.\n\n**Normalized Lipschitz Estimates for Randomly Generated Neural Network with 50 Layers**\n| Neuron | ECLipsE  | ECLipsE-Fast | LipSDP-Neuron Split by 5 | LipSDP-Layer Split by 5 |\n|--------|-------|--------------|--------------|----------------------|\n|150|0.743745|0.867548|0.758217| 0.87342|\n|200| 0.773494 | 0.883758|0.785171| 0.888306|\n|300| >30min|0.897008| >30min|0.899164|\n|400|   |0.899916|       | >30min|\n|500|    |0.903529|   |  |\n|1000|   |0.912093|   |    |\n\n**Time Used for Randomly Generated Neural Network with 50 Layers (Seconds)**\n| Neuron | ECLipsE | ECLipsE-Fast | LipSDP-Neuron Split by 5 | LipSDP-Layer Split by 5 |\n|--------|---------|--------------|--------------------------|-------------------------|\n| 150 | 387.7| 0.387262 | 451.07 | 93.129 |\n| 200 | 1386.6| 0.584115 | 1377.9  | 210.16 |\n| 300 | >30min| 1.321177 | >30min | 612.47     |\n| 400 |   | 2.657505 |  | 2110.9 |\n| 500 |  | 3.7435 |  | >30min |\n| 1000 |  | 15.63342 | |  |\n\n>**In experiments, there seems a missing comparison with the “parallel implementation by splitting” version of Lip-SDP [...]  to address the depth issue.**\n\nThe ``parallel implementation by splitting'' version of LipSDP is implemented in Section 4.1 Case 4.3 directly using the code provided by [32], where we compare 3 ways of splitting, namely into 3, 5, and 10 layers respectively. The results are promising as discussed in Case 4.3: ECLipsE-Fast is the fastest algorithm and outperforms LipSDP-Layer regardless of how we split the neural networks. ECLipsE is also shown to be relatively more accurate and efficient than all LipSDP methods, no matter the split.\n>**The method description can be improved, e.g., being more organised [...] I find it helpful to see in the main paper a description of the existing Lemma 2 in [31] and the pseudo code of the proposed algorithm.**\n\nWe thank the reviewer for their suggestions on improving the clarity of our paper, and will revise accordingly - please see General Response point III.", "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": "WfB9y9jyYy", "reviewer": "Reviewer_kXCT", "summary": "The paper proposes two algorithms, ECLipsE and ECLipsE-Fast, to estimate the Lipschitz constant of a feed-forward neural network. The estimation of the Lipschitzness plays a crucial role in certifying the robustness of neural networks and is known to be an NP-hard problem. The proposed algorithms are based on the LipSDP of Fazlyab et al. (2019), which describes the semidefinite program (SDP) that an upper bound of such a Lipschitz constant should generally satisfy. The authors decompose the original large SDP into smaller layer-wise SDPs to improve the scalability of the original approach. The validity of the resulting methods, ECLipsE and ECLipsE-Fast, is supported by theoretical analyses. Experiments show a steep reduction in computation time while maintaining competitive accuracy compared to the LipSDP.", "questions": "Q1: Is Theorem 1 *necessary* and sufficient? If not, this should be added to the limitations of the work.\n\nQ2: Why did the authors set $M_i$ to $c_iW_{i+1}^\\top  W_{i+1}+N$ in Proposition 3?\n\nQ3: How is the positive definiteness of $M_i$ guaranteed in Equation (6) and Proposition 3?\n\nQ4: What was the motivation to run experiments of Subsection 4.2?", "limitations": "There are several limitations of the algorithms that are worth mentioning:\n\n1. The algorithms (Lemma 1) need that the last weight matrix is full row rank. So, we cannot blindly apply them to any feed-forward neural network.\n\n2. There is a simplification when transforming Theorem 2 into Proposition 3 by limiting the expression of  $M_i $ to $c_iW_{i+1}^\\top  W_{i+1}+N$. This may lead to looser bounds than the original LipSDP.\n\n3. The algorithms cannot be applied to CNNs and residual networks.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The proposed algorithm is novel and clearly distinguishes itself from prior works.\n\nQuality: The motivation of the work is clearly stated and explained. Prior works are also well-discussed. The authors provide thorough and sound mathematical justification and geometrical intuitions for the two algorithms.\n\nClarity: The paper is well-written including the methodology, and the motivation is clear.\n\nSignificance: Compared to LipSDP, the proposed algorithm provides significant improvement in terms of efficiency and addresses concerns stated in the motivations of the paper in the beginning.\n\nOverall, I feel this is a good paper with a promising approach equipped with a thorough and interesting mathematical justification.", "weaknesses": "Overall, in my view, the main weakness of this paper is that there is no explicit comparison with other works trying to improve the scalability of LipSDP (such as [20]). As a result, while the paper indeed improves the original LipSDP in a new way, it is unclear how significant this work is taking into account existing literature. In addition, the limitations should be more carefully discussed. See below for further detailed comments and advice.\n\n### **Quality**\n \n(W-Q1) There are some typos: l.60 (constans), p.3 eqation (3) (index of the bottom right element is i+1 but should be l), l.172 (in the matrix WMW there are 2 unnecessary “L”), l.264 (computatinoal), between l.420 and l.421 (i\\in \\mathbb{R}^n), p.13 equation (18) (if i=0 should be if i=1?), l.477 (functionsare), l.480 (the is norm), \n\n(W-Q2) I feel that some use of words is misleading.  \n\n1. l.60 “We develop a sequential Cholesky decomposition technique to obtain […]“: If this is about Theorem 2, it directly uses the result of Agarwal et al., so maybe “use, employ” would be better than “develop”.\n\n2. l.10 “The first algorithm [...] enables us to provide a *tight* Lipschitz constant”, l.56 “ algorithm [...] enables us to provide an *accurate* Lipschitz”... What do you mean by “tight” and “accurate”? Since the proposed algorithms are using some simplifications, I think that those adjectives should be relative, i.e., only used in comparison with something else. Notably, the experiments (e.g., Figure 3) show that CPLip is far more precise than the proposed algorithms so the authors should clarify the meaning of “tight” and “accurate” (or delete them if there is no justification) when describing their own algorithms.\n\n3. Between l.462 and l.463, you write “$N/ci(M_i)^{-1}\\ge0$”. Semi-positive definiteness was only defined for symmetric matrices but this one is not necessarily symmetric. There should be an easy fix, but it is ambiguous what you mean by this sign. \n\n(W-Q3) In Proposition 3, the authors simplify Theorem 2 by setting $M_i$ to $c_iW_{i+1}^\\top  W_{i+1}+N$ without any proper discussion about this choice (Q2).\n\n(W-Q4) The proof of positive definiteness of $M_i$ is missing in Proposition 3 (Q3). \n\n(W-Q5) (minor) Some references should be adjusted: [2] was accepted at ICLR2018, some capital letters are missing (L of lipschitz)...\n\n### **Clarity**\n\n(W-C1) Some parts may require clarifications (See also Questions):\n\n1. (minor) l.111 “[30] provides a counterexample to the most accurate approach”: The concrete property of the most accurate approach disproved by [30] could be explained in a few words.\n2. (minor) A mathematical comparison of the computational complexity between your approach and LipSDP will largely help the reader to quickly understand the difference in scalability.\n\n(W-C2) While limitations of proposed algorithms are all stated, they are dispersed throughout the paper. A short subsection summarizing them would be useful. (See also Limitations)\n\n(W-C3) It was a bit difficult to understand the idea of the proposed algorithms from Subsection 3.2. Perhaps showing Algorithm 1 in the main text would be better.\n\n### **Significance**\n \n(W-S1) (major) One of the main contributions of this work is the scalability of the proposed algorithms. However, the authors do not compare their method with other accelerations of LipSDP. Therefore, it is difficult to situate their work within the broader context of efforts to improve the scalability of LipSDP. At least, comparing the algorithms with that of Wang et al. (2024) [20] is important to clarify these points. \n\n(W-S2) The algorithms were run on medium-scale neural networks, and it is difficult to imagine the scalability of ECLipsE and ECLipsE-Fast. Experiments with even larger architectures (for example, those for training on CIFAR or ImageNet) would be more convincing.  \n\n(W-S3) I feel experiments of Subsection 4.2 are a little bit redundant (Q4). \n\n(W-S4) Limitations of the algorithms should be discussed in more detail and more explicitly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough reading of our manuscript and providing several suggestions to improve the clarity of our presentation (see General Response - point III). We individually address the technical questions raised by the reviewer below, and provide additional experiments benchmarking our algorithms (results in **attached PDF** of the General Response and discussion below). \n>**One of the main contributions of this work is the scalability of the proposed algorithms. [..] At least, comparing the algorithms with [..] [20] is important.**\n\nWhile [20] was too recent to reproduce at the time of our submission (<1 month), we can now provide additional experiments using their open-source code and considering the same NNs in Section 4.1 Case 1 and Case 2. The results in the **attached PDF** (in the General Response) demonstrate that (i) ECLipsE and [20] have similar computation times for smaller networks; however, the computation time for [20] grows more rapidly for both deeper and wider networks, and (ii) ECLipsE-Fast remains orders of magnitude faster than all algorithms while providing Lipschitz estimates that are very close to those achieved by LipSDP-Layer, and (iii) **importantly**, [20] provides inadmissible estimates for moderate networks, returning as much as $10^4-10^6$ times and 10-100 times the trivial bound in Tables 2a and 1a respectively. Note that all the estimates are normalized with respect to trivial upper bounds.\n\nAnother work on improving the scalability of LipSDP is [33]. However, as acknowledged by the authors in their footnote, their acceleration depends on LipSDP-Network, which is proved to be invalid by [30]. Therefore, we do not include it as a benchmark.\n\n>**The proof of positive definiteness of $M_i$ is missing in Proposition 3.**\n\nThank you for raising this question.\nThe first part of the proof of Proposition 3 (l.463-465) showing the non-emptiness of the feasible region implies the positive definiteness of $M_i$ for the next stage. This is because $M_i=\\Lambda_i-\\frac{1}{4}\\Lambda_iW_i(M_{i-1})^{-1}W_i^T\\Lambda_i$. From (10), $M_i>c_iW_{i+1}^TW_{i+1}>0$ as $c_i>0$ and $W_{i+1}^TW_{i+1}\\geq 0$. Then, with $M_0>0$, $M_i$ is guaranteed to be positive definite at each step. We will supplement the proof for clarity. \n\n>**In Proposition 3, the authors simplify Theorem 2 by setting $M_i$ to $c_iW_{i+1}^TW_{i+1}+N$ without any proper discussion about this choice.**\n\nThere is no simplification here, and we can write $M_i$ **exactly** as $c_iW_{i+1}^TW_{i+1}+N$. We briefly summarize the proof here. \nSince $M_i$ is positive definite (see response above), and $W_{i+1}^TW_{i+1}$ is positive semidefinite, there exists constant $C$ such that for any $c\\in[0,C]$, $M_i-cW_{i+1}^TW_{i+1}\\geq 0$. Now, for the $i$-th layer, let $c_i$ be the largest possible $C$ such that $M_i-cW_{i+1}^TW_{i+1}\\geq 0$ holds. Then, $N=M_i-c_iW_{i+1}^TW_{i+1}$ is a positive semidefinite matrix and also a singular matrix. We show this by contradiction in the proof of Proposition 3; see lines 465-468, starting at `we now prove by contradiction..'. (we do not include this here for brevity). Therefore, we can equivalently write $M_i=c_iW_{i+1}^TW_{i+1}+N$, where $N$ is a positive semidefinite matrix and also a singular matrix.  \n>**The algorithms were run on medium-scale neural networks, and it is difficult to imagine the scalability of ECLipsE and ECLipsE-Fast [..]**\n\nECLipsE-Fast has closed-form solution and is therefore scalable, no matter the network size. We did not present larger networks because the existing benchmarks already exceed the cutoff time of 30 min for medium-sized networks. Further, from existing experiments, our acceleration is already pronounced with promising accuracy, and the advantage will be even more significant for larger networks. \n>**What was the motivation to run experiments of Subsection 4.2?**\n\nThe motivation for Section 4.2 is two-fold. First, we show that our algorithms apply not only to randomly generated weights but also to those trained for some specific tasks. Second, although ECLipsE provides a tighter estimate in general, we show an interesting case where ECLipsE-Fast is more favorable compared to ECLipsE (with similar accuracy but much faster speed).\n>**[..] need that the last weight matrix is full row rank [..] cannot blindly apply them to any feed-forward neural network.**\n\nSince this was also raised by another reviewer, we address it in point II of the General Response. In short, this assumption is not necessary, and both algorithms apply even when it is not satisfied.\n>**[..] cannot be applied to CNNs and residual networks.**\n\nSince this question was also raised by other reviewers, we have answered it under General Response - point I.\n>**(a) l.10 [..] What do you mean by “tight” and “accurate”? \\\n(b) Between l.462 and l.463, you write “$N/c_i(M_i)^{-1}\\geq 0$\n”. Semi-positive definiteness was only defined for symmetric matrices but this one is not necessarily symmetric [..]**\n\n(a) In the Introduction, \"tight\" and \"accurate\" are used in a general sense, to express that our method provides Lipschitz estimates that are comparable to existing methods while achieving significantly enhanced scalability. We will rephrase in response to the reviewer's suggestions.\n\n(b) By the definitions of $N$ and $M_i$, they are indeed guaranteed to be symmetric. \n>**(minor) (a) l.111 “[..] the most accurate approach disproved by [30] could be explained [..]\\\n(b) A mathematical comparison of the computational complexity between [..] LipSDP will largely help [..]**\n\n(a) [30] gives a counterexample showing that the Lipschitz estimate from LipSDP-Network is not a strict upper bound.\n\n(b) Please see point (1) of our response to Reviewer kbMy for a computational complexity analysis (not repeated here due to space constraints).", "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": "d6rOzfOfYu", "reviewer": "Reviewer_LaVm", "summary": "This paper tackles the problem of computing the Lipschitz constant of a neural network. Since computing the exact Lipschitz constant is NP-hard, efforts have been made to obtain tight upper bounds on the Lipschitz constant. This paper builds on the work of LipSDP [1], which involves solving a large matrix verification problem. Since that the large matrix verification problem grows significantly for both deeper and wider networks, this paper proposes a compositional approach to estimate the Lipschitz constants of deep feed-forward neural networks more efficiently. First, the authors obtain an exact decomposition of the large matrix verification problem into smaller sub-problems and, then, exploiting the underlying cascade structure of the network the authors develop two algorithms to compute a bound on the Lipschitz constant:\n- The first algorithm explores the geometric features of the problem and provides a tight estimate of the Lipschitz constant by solving small semidefinite programs (SDPs) that are only as large as the size of each layer.\n- The second algorithm relaxes these subproblems and provides a closed-form solution to each subproblem for extremely fast estimation, altogether eliminating the need to solve SDPs altogether.\n\nFinally, the authors provide extensive experiments to show the different levels of tradeoffs between efficiency and accuracy of the two algorithms. They show that their approach provides a steep reduction in computation time while yielding Lipschitz bounds that are very close to, or even better than, those achieved by state-of-the-art approaches.", "questions": "See Weaknesses", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clear and well written. The problem of providing a scalable algorithm for computing the Lipschitz of neural networks is interesting and important. \n- The exact decomposition of the large matrix verification problem into smaller subproblems is very interesting.\n- The two algorithms for computing the sequence of inequalities provide interesting trade-offs. The first algorithm (ECLipsE) looks, if I understand correctly, like a direct improvement of LipSDP, since ECLipsE provides the same value as LipSDP in a more efficient way. \n- The second algorithm also looks interesting as it provides a way to compute the Lipschitz constant without SDPs.", "weaknesses": "- it looks like the approach is restricted to a very limited set of neural networks (feedforward neural networks), can the approach be used for convolutional neural networks?\n- In the experiments, the authors use randomly generated neural networks for their first set of experiments, in my experience it is usually easier to compute SDP on random weight matrices than on trained weight matrices due to conditioning, could the authors provide results of these experiments with trained networks? \n- Can the authors clarify if ECLipsE has to compute all subproblems at the same time or if a sequential approach is possible? \n- I assume that the ECLipsE algorithm uses Matlab for SPD optimization, have the authors tried using a deep learning framework (e.g. PyTorch) for ECLipsE-Fast? Could ECLipsE-Fast be used during training, e.g. for regularization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging evaluation of our work and thoughtful questions. We address all of them in detail as follows.\n>**It looks like the approach is restricted to a very limited set of neural networks (feedforward neural networks), can the approach be used for convolutional neural networks?**\n\nSince this was also raised by other reviewers, we have answered it in point I of the General Response.\n>**In the experiments, the authors use randomly generated neural networks for their first set of experiments, in my experience it is usually easier to compute SDP on random weight matrices than on trained weight matrices due to conditioning, could the authors provide results of these experiments with trained networks？**\n\nWe do in fact have experiments for both cases. Section 4.1 considers randomly generated neural networks and Section 4.2 considers neural networks trained for  MNIST tasks. Note that our algorithms estimate the Lipschitz constant for a given model, that is, all the parameters are fixed and the algorithms are implemented out after the model is trained. Therefore, we did not observe any additional difficulties in estimating the Lipschitz constant for trained weight matrices. Please see Section 4.2 for detailed results on trained weight matrices.\n>**Can the authors clarify if ECLipsE has to compute all subproblems at the same time or if a sequential approach is possible?**\n\nECLipsE computes the subproblems by sequence. Starting with $i=1$, the SDP problem as expressed in (6) requires the information matrix $M_{i-1}$ passed on from the computation at the $(i-1)$-th stage. Therefore, it is a sequential approach, aligning with the cascaded neural network structure.\n>**I assume that the ECLipsE algorithm uses Matlab for SPD optimization, have the authors tried using a deep learning framework (e.g. PyTorch) for ECLipsE-Fast? Could ECLipsE-Fast be used during training, e.g. for regularization?**\n\nYes, ECLipsE uses Matlab with solver Mosek to solve the SDPs. For ECLipsE-Fast, the solutions for $\\Lambda_i$s at each step are actually obtained in closed-form as stated in Proposition 4, and at the last step the Lipschitz estimate is also in closed-form as given in Proposition 1. Thus, there is no need to solve any SDPs at all for ECLipsE-Fast; we obtain fast estimates by only evaluating closed-form analytical expressions without the need to use any deep learning framework. Lastly, we believe our efficient, scalable and accurate methods like ECLipsE-Fast will facilitate robust training for neural networks in the future, although this is beyond the scope of the present paper.", "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": "0gEHbiITqh", "reviewer": "Reviewer_3iDD", "summary": "This paper presents two novel algorithms for computing the Lipschitz constant of feedforward neural networks (NN). The starting point is a previously-known semi-definite programming (SDP) problem which enables to compute the Lipschitz constant. The paper proposes a decomposition of this SDP in sequential subproblems over layers, then relax the subproblems to enable iterative computations across layers, instead of solving a joint problem on all layers. This approach scales much better with both width and depth, as demonstrated by experiments on neural networks at initialization and after training on MNIST.", "questions": "- I believe that Proposition 4 shows that ECLipsE-Fast provably gives an upper-bound on the true (unknown) Lipschitz constant of the neural network. Is this correct?\n- Does ECLipsE also always give an upper-bound on the true Lipschitz constant? If so, are there assumptions for this to hold? If not, at which steps are approximations made? I guess this should more or less follow from Lemmas 1 and 2, and Propositions 2 and 3, but it is not clearly stated in the paper.\n\nMinor remarks:\n- Authors could consider typesetting their algorithms as “Eclipse” and “Eclipse-Fast” to improve readability.\n- line 199: “such” missing.", "limitations": "The limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is overall well-written (see caveat in the weakness section). \n- The question of computing the Lipschitz constant of neural networks is important for a number of downstream tasks. The proposed method provides estimates that are experimentally on-par with approaches based on SDP methods, while being order of magnitude faster.", "weaknesses": "[EDIT (Aug.7): the rebuttal answered my questions adequately. In particular, the method does provide provably-correct upper-bounds.]\n\n- Theoretical results in Section 3.3 are a bit hard to follow, because the section gives the story behind the proposed relaxation, as well as geometric interpretation, but does not provide a main result summarizing the theoretical guarantees of the proposed approach. This is a key point, because provably correct upper-bounds on the Lipschitz constant are of course much preferable. Although it is suggested that the proposed algorithms are indeed provably correct, it is not clearly stated in the paper. So the paper would highly benefit from a clear statement on this fact, as well as a summary of the theoretical results into a theorem (see also Questions).\n- The comparison with methods in the literature is limited to SDP methods, which is OK given that the main contribution is to provide a clever relaxation of these methods, but still a broader comparison would have been interesting. \n- The approach only applies to feedforward NN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging evaluation of our work and thoughtful questions. We address all of them in detail as follows.\n>**Theoretical results in Section 3.3 are a bit hard to follow, because the section gives the story behind the proposed relaxation, as well as geometric interpretation, but does not provide a main result summarizing the theoretical guarantees of the proposed approach. This is a key point, because provably correct upper-bounds on the Lipschitz constant are of course much preferable. Although it is suggested that the proposed algorithms are indeed provably correct, it is not clearly stated in the paper. So the paper would highly benefit from a clear statement on this fact, as well as a summary of the theoretical results into a theorem (see also Questions).**\n\nTheorem 2 provides a provable guarantee for the upper-bounds on the Lipschitz constant estimates. Specifically, we show that as long as there exist $\\Lambda_i>0$, $i\\in \\mathbb{Z}_{l-1}$, such that the inequalities in (4) hold, the Lipschitz estimate we obtain is a strict upper bound for the Lipschitz constant. Thus, the existence of positive $\\Lambda_i$s and the conditions in (4) already provide the theoretical guarantee. Then, we proceed to develop two algorithms to find the  positive $\\Lambda_i$s that will satisfy the provable guarantees in Theorem 2.  Finally, the theory and intuition for finding good $\\Lambda_i$s are detailed in Section 3.3. We further note that the relaxation between ECLipsE and ECLipsE-Fast solely pertains to finding positive $\\Lambda_i$s while trading off computational speed for accuracy, while the upper bound on the Lipschitz constant is still strict for both algorithms. \n\nFinally, as we discuss in the General Response - point III, we will move the pseudo-code of the algorithm, and additional theoretical results from the Appendix to the main text for clarity of exposition as suggested by the reviewers.\n>**The comparison with methods in the literature is limited to SDP methods, which is OK given that the main contribution is to provide a clever relaxation of these methods, but still a broader comparison would have been interesting**\n\nFor non-SDP based methods, we have included a benchmark method CPLip (green dash line in Fig. 3, 4) in our experiments, which turns out to be exponentially expensive in computational cost and is therefore not scalable to the deep neural networks we consider (see Fig. 4). Of course, as the reviewer rightly points out, we do indeed focus most of our comparisons on SDP methods.\n\n>**The approach only applies to feedforward NN.**\n\nWe thank the reviewer for this question. Since this was also raised by other reviewers, we have answered point I of the General Response.\n\n>**I believe that Proposition 4 shows that ECLipsE-Fast provably gives an upper-bound on the true (unknown) Lipschitz constant of the neural network. Is this correct?\\\nDoes ECLipsE also always give an upper-bound on the true Lipschitz constant? If so, are there assumptions for this to hold? If not, at which steps are approximations made? I guess this should more or less follow from Lemmas 1 and 2, and Propositions 2 and 3, but it is not clearly stated in the paper.**\n\nPropostion 4 states the closed form solution for $\\Lambda_i$s and guarantees the positive definiteness of $M_i$ at each stage. As discussed in the first point of this review response above, the Lipschitz estimate given by ECLipsE and ECLipsE-fast are thus both provably strict upper bounds by Theorem 2.\n\nWe will further clarify these points, as well as address typos and minor suggestions from the reviewer in the final version of our paper.", "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:
We are extremely grateful to the reviewers for their detailed, thorough, and constructive feedback. We are glad to read that the reviewers found paper to be interesting, novel, practical and well-written. We appreciate the suggestions from Reviewers kbMy, 3iDD on enhancing the clarity of writing, Reviewer kXCT on providing additional experiments benchmarking to the state-of-the-art, and Reviewers qsZt, kXCT, LaVm, 3iDD on the generalization of our algorithms to other neural network architectures. We address all the reviewers' concerns and questions in individual responses, and provide additional  experiments to illustrate the strength of our methods. First, we address common questions raised by multiple reviewers and ones that provide additional benchmarking experiments here.

**I. On the applicability of our algorithms to other neural network architectures such as CNNs (Reviewer qsZt, Reviewer kXCT, Reviewer LaVm, Reviewer 3iDD):**

Several reviewers raise the question of whether our algorithms are applicable beyond feedforward neural networks (FNNs) to other classes such as convolutional neural networks (CNNs) and residual networks. While our work exploits the mathematical structure of the underlying matrices arising from cascaded architectures to develop fast algorithms, the applicability of our algorithms is not restricted to only FNNs. In the case of CNNs, we can adopt a strategy similar to LipSDP where the CNN can be unrolled into a large fully connected neural network, following which we can apply both ECLipsE and ECLipsE-Fast.

While our current study focuses on significantly accelerating the computation of Lipschitz constants for FNNs, future work will involve exploring the mathematical structures of other architectures such as residual networks to develop similarly fast algorithms for Lipschitz constant estimation. 

**II. On the full row rank assumption on the last weight matrix in Lemma 1 (Reviewer qsZt, Reviewer kXCT):**

We thank the reviewers for this insightful question. First, we would like to clarify that both ECLipsE and ECLipsE-Fast are still valid even if the full row rank assumption is not satisfied. This is due to the fact that at the last stage, the Lipschitz estimate is in fact given by a closed-form expression with no requirement on the row rank of $W_l$ as Proposition 1. We note that the reason that this assumption was made is solely for ease of exposition of the intuition arising from the geometric features of the problem. Specifically, as discussed after Lemma 2, if the weight matrix is full ranked, then minimizing $\sigma_{max}(F_i)$ aligns with minimizing $\sigma_{max}\left(W_l^TW_l(M_{l-1})^{-1}\right)=\sigma_{max}\left(W_l(M_{l-1})^{-1}W_l^T\right)=\sigma_{max}(F_{l})$ at the last stage, from a geometric perspective. However, we note that the algorithms themselves do not rely on this fact due to the closed-form expression in Proposition 1. 

Also, practically speaking, it is common to set the dimension of the last hidden layer to be much larger than the output dimension. Thus, $W_l$, as a fat matrix, is almost always full row ranked (see the discussions after Lemma 1).

We acknowledge that this choice of presentation may have caused some ambiguity regarding the necessity of this assumption. We will clarify this in the final version of the paper.

**III. On the organization of the algorithm description in the paper (Reviewer kbMy, Reviewer kXCT, Reviewer 3iDD):**

Several reviewers have suggested moving the existing Lemma 2 in [31] and the pseudo code of the proposed algorithm to the main paper for better organization and presentation of the theoretical results in the paper. We thank the reviewers for this suggestion. Given the additional page available for the camera-ready version, we will incorporate them into the main body of the final paper. We will also fix all typos and take into account editorial suggestions from various reviewers in the final version. 

**IV. Additional Benchmarking Experiments (Reviewer kXCT):**

Reviewer kXCT suggested that our algorithms should be benchmarked against those in [20]. While [20] was too recent to reproduce at the time of our submission (<1 month), we now provide additional experiments (see attached PDF) 
benchmarking our algorithms with respect to [20], considering the same NNs in Section 4.1 Case 1 and Case 2. In short, (i) ECLipsE and [20] have similar computation times for smaller networks; however, the computation time for [20] grows more rapidly for both deeper and wider networks, and (ii) ECLipsE-Fast remains several orders of magnitude faster than all algorithms while providing Lipschitz estimates that are very close to those achieved by LipSDP-Layer, and (iii) **importantly**, [20] provides inadmissible estimates for moderate networks, returning as much as $10^4-10^6$ times and 10-100 times the trivial bound in Tables 2a and 1a respectively.

Meta-review: This paper proposes a novel, efficient algorithm to estimate the Lipschitz constant of neural networks. The algorithm is based on SDP based methods, developed to estimate the Lipschitz constant. The main idea is breaking the SDP into sequential subproblems which involve matrix inequality on smaller matrices.  Using this decomposition, the paper proposes two algorithms with different computational cost and accuracy, allowing to establish cost-accuracy trade-offs. In particular, the proposed method significantly reduces the computational complexity with depth. Experiments show that this proposed method can achieve almost the same estimate while being scalable to deeper networks. The paper is well-motivated, well-written with a solid contribution. While the proposed method is limited to feedforward networks, this limitation is included in the discussion. Thus, I recommend to accept this paper for a spotlight presentation.
Decision: Accept (spotlight)