ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks

Thank you for your encouraging evaluation of our work and thoughtful questions. We address all of them in detail as follows.

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).

Theorem 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.

Finally, 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.

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

For 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.

The approach only applies to feedforward NN.

We thank the reviewer for this question. Since this was also raised by other reviewers, we have answered point I of the General Response.

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?
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.

Propostion 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.

We will further clarify these points, as well as address typos and minor suggestions from the reviewer in the final version of our paper.

Thank you for your encouraging evaluation of our work and thoughtful questions. We address all of them in detail as follows.

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?

Since this was also raised by other reviewers, we have answered it in point I of the General Response.

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？

We 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.

Can the authors clarify if ECLipsE has to compute all subproblems at the same time or if a sequential approach is possible?

ECLipsE 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.

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?

Yes, 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.

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).

One of the main contributions of this work is the scalability of the proposed algorithms. [..] At least, comparing the algorithms with [..] [20] is important.

While [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.

Another 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.

The proof of positive definiteness of $M_i$ is missing in Proposition 3.

Thank you for raising this question. The 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.

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.

There 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. Since $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.

The algorithms were run on medium-scale neural networks, and it is difficult to imagine the scalability of ECLipsE and ECLipsE-Fast [..]

ECLipsE-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.

What was the motivation to run experiments of Subsection 4.2?

The 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).

[..] need that the last weight matrix is full row rank [..] cannot blindly apply them to any feed-forward neural network.

Since 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.

[..] cannot be applied to CNNs and residual networks.

Since this question was also raised by other reviewers, we have answered it under General Response - point I.

(a) l.10 [..] What do you mean by “tight” and “accurate”?
(b) Between l.462 and l.463, you write “$N/c_i(M_i)^{-1}\geq 0$ ”. Semi-positive definiteness was only defined for symmetric matrices but this one is not necessarily symmetric [..]

(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.

(b) By the definitions of $N$ and $M_i$, they are indeed guaranteed to be symmetric.

(minor) (a) l.111 “[..] the most accurate approach disproved by [30] could be explained [..]
(b) A mathematical comparison of the computational complexity between [..] LipSDP will largely help [..]

(a) [30] gives a counterexample showing that the Lipschitz estimate from LipSDP-Network is not a strict upper bound.

(b) Please see point (1) of our response to Reviewer kbMy for a computational complexity analysis (not repeated here due to space constraints).

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.

(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.

We 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.

From 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.

To 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.

Normalized Lipschitz Estimates for Randomly Generated Neural Network with 50 Layers

Time Used for Randomly Generated Neural Network with 50 Layers (Seconds)

In experiments, there seems a missing comparison with the “parallel implementation by splitting” version of Lip-SDP [...] to address the depth issue.

The ``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.

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.

We thank the reviewer for their suggestions on improving the clarity of our paper, and will revise accordingly - please see General Response point III.

Thank you for your insightful comments and positive evaluation of our work. We address your concerns as follows.

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).

We thank the reviewer for this question; since this was also raised by other reviewers, we have answered point I of the General Response.

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).

We 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.

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?

We 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.

We 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.

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.

We 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.

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?

The 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.

Theoretically, 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.