ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks

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.

Strengths

- The paper is overall well-written (see caveat in the weakness section). - 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.] - 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). - 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. - The approach only applies to feedforward NN.

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? - 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. Minor remarks: - Authors could consider typesetting their algorithms as “Eclipse” and “Eclipse-Fast” to improve readability. - line 199: “such” missing.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The limitations are adequately addressed.

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

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. - The exact decomposition of the large matrix verification problem into smaller subproblems is very interesting. - 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. - 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? - 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? - Can the authors clarify if ECLipsE has to compute all subproblems at the same time or if a sequential approach is possible? - 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?

Questions

See Weaknesses

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

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.

Strengths

Originality: The proposed algorithm is novel and clearly distinguishes itself from prior works. Quality: 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. Clarity: The paper is well-written including the methodology, and the motivation is clear. Significance: 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. Overall, 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. ### **Quality** (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), (W-Q2) I feel that some use of words is misleading. 1. 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”. 2. 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. 3. 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. (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). (W-Q4) The proof of positive definiteness of $M_i$ is missing in Proposition 3 (Q3). (W-Q5) (minor) Some references should be adjusted: [2] was accepted at ICLR2018, some capital letters are missing (L of lipschitz)... ### **Clarity** (W-C1) Some parts may require clarifications (See also Questions): 1. (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. 2. (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. (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) (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. ### **Significance** (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. (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. (W-S3) I feel experiments of Subsection 4.2 are a little bit redundant (Q4). (W-S4) Limitations of the algorithms should be discussed in more detail and more explicitly.

Questions

Q1: Is Theorem 1 *necessary* and sufficient? If not, this should be added to the limitations of the work. Q2: Why did the authors set $M_i$ to $c_iW_{i+1}^\top W_{i+1}+N$ in Proposition 3? Q3: How is the positive definiteness of $M_i$ guaranteed in Equation (6) and Proposition 3? Q4: What was the motivation to run experiments of Subsection 4.2?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

There are several limitations of the algorithms that are worth mentioning: 1. 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. 2. 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. 3. The algorithms cannot be applied to CNNs and residual networks.

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.

Strengths

The targeted research problem is important and useful. The 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. The 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. (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. (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.

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.

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Discussion on discussion is pretty limited. For instance, it can be improved around the network width issue.

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.

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

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

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

Limitations are adequately addressed.

Thank you for the rebuttal

I thank the authors for their precise rebuttal, which answers adequately my questions. I raised my score accordingly.