Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work presents a method to efficiently compute upper bounds for the Local Lipschitz constant of ReLU networks. In short, Interval Bound Propagation techniques are applied to the backward computational graph, which yields an upper bound on the norm of the
Clarke Jacobian of the network, which constitutes an upper bound for the Local Lipschitz constant. Careful consideration of the bounds for well-known activation functions provide tighter results over previous baselines. Such improvements are confirmed on experiments using MLPs and Convolutional networks trained on MNIST/CIFAR10/TinyImagenet.

*** after rebuttal ***
Authors have addressed my main concerns. I am inclined to increase my score.
strengths_and_weaknesses: **Originality**: I think the main weakness is in this front, as to me the contribution is not clear. The authors claim that their contribution is to "generalize existing bound propagation methods originally used for NN verification, to a higher order backward computational graph for bounding the Clarke Jacobian". However, to me it appears that [B] precisely does that, with the caveat that their results are for differentiable activation functions, when the notion of Clarke Jacobian is just the normal Jacobian function. As such, I believe that this work rather adapts the technique in [B] to the setting of non-differentiable activation functions like ReLU, together with a more careful approach that provides tighter bounds in some cases, compared to the methods in [B]. This should be clarified by the authors and if it is the case, the claims should be toned down. In summary, I believe that applying Interval Bound Propagation techniques to the Jacobian (which is the backward computational graph) is already done in [B], although in a slightly different setting.

**Quality and Clarity**: The paper is in general well-written and easy to follow, and the bibliography appears all of previous related work. The differences with most previous works are clearly explained, again with the exception of RecurJac [B], where I believe the authors should expand. Also in line 151 the authors claim "Chain rule can be used to compute the Clarke Jacobian for the whole ReLU network", however it is well known that the notion of "Chain rule" is more complicated when dealing with non-smooth compositions, I would like the authors to clarify which "Chain rule" are they talking about. See for example Theorem 4 in [A].

**Significance**: I believe it is important to extend the method in [B] to the case of non-smooth activations, as activations like ReLU and LeakyReLU are commonly used in practice despite the fact that they do not have a "normal" gradient at all points. Moreover, **Theorem 4** in this work is a tightness result which implies that the relaxation presented in this work is the tightest possible, which is an important step in this line of research. However, related to my main criticism of the work, if indeed the idea of applying interval bound propagation to the backward computational graph is already present in [B], the method presented here would be more of a refinement of a previous method rather than a completely different approach, which is less significant.

In the experiments it is not clear why RecurJac is used despite it being tailored for differentiable activation functions, can the authors clarify if using RecurJac for non-smooth activation functions still provide a valid upper bound for the norm of the Jacobian? Another issue with the experiments is a lack of confidence intervals. Because the networks used are a result of a stochastic process (SGD) there might be differences due to randomness, and without confidence intervals it is hard to assess if the improvement is significant. For example the method LipBAB achieves a runtime of 2.92 for MLPs of width 32 and 4 layers, which is much faster than the method presented here, while providing a Lipschitz constant as good. However in other cases it is considerably slower and provides worse bounds. Adding confidence intervals could possibly let the authors conclude if their method is **consistently outperforming the baselines**.

Nevertheless,their method (without Branch-and-bound) appears to be consistently faster and more scalable than RecurJac. 

**References**
[A] Support functions of Clarke's generalized jacobian and of its plenary hull. Cyril Imbert.
[B] RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applications, Huan Zhang, Pengchuan Zhang, Cho-Jui Hsieh, AAAI 2019
questions: 1. Isn't RecurJac precisely an application of Interval Bound Propagation on the backward computational graph of the network (the Jacobian)? Could you expand and clarify the differences between your approach an RecurJac?
2. Could you clarify which "Chain rule" are you using for composition of non-differentiable functions?
3. Do you have new experimental results with confidence intervals, that you could add to the tables?
limitations: No negative societal impact. The main limitation is the cost of Branch-and-bound which the authors somehow address by providing an option to use the method without BaB.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper extends existing Clarke Jacobian estimation from interval bounds to the linear relaxation. The authors further apply the branch-and-bound method to tighten the estimation when the time budget allows. The experiments show that the linear-relaxed Clarke Jacobian with branch-and-bound produces more precise results than selected benchmarks. The authors also use the monotonicity analysis as an application of Clarke Jacobian.
strengths_and_weaknesses: Strengths:
This work provides tighter estimation of Clarke Jacobian norm estimation, which has practical benefits for the local Lipschitz constant evaluation. Local Lipschitz constant is an essential mathematical property of the neural network in an input region.

Weaknesses:
1. This work is incremental. Tightening neural-network certification from interval bounds to linear relaxation has been studied in a number of works, for example, [1] and [2]. The branch-and-bound method has also been used to compute the Lipschitz constant of neural networks [3]. This work brings little new insight or understanding to neural-network certification. The benefit is mostly practical from compiling known methods together, which is not surprising.
2. Line 179 mentions that in this paper, the authors mainly consider $\ell_\infty$-norm *for simplicity*. I doubt whether this is *for simplicity* or linear relaxed Clarke Jacobian is only able to handle linearly constraint perturbation space in practice (see the Questions section below).
3. The evaluation has doubts. The first part is related to 2. LipSDP is designed to compute Lipschitz constant with respect to $\ell_2$ perturbations. Scaling the result of LipSDP for $\ell_2$ perturbations seems an unfair comparison to LipSDP, unless the authors make it clear this work does not apply to $\ell_2$ perturbations. The second part is for the monotonicity analysis. The authors provide some numbers from experiments, but there is no justification on how good the result is.

[1]Zhang, H., Weng, T., Chen, P., Hsieh, C., and Daniel, L. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems, pp. 4944–4953, 2018. URL https://proceedings.neurips.cc/paper/2018/hash/d04863f100d59b3eb688a11f95b0ae60-Abstract.html.

[2]Lyu, Z., Ko, C., Kong, Z., Wong, N., Lin, D., and Daniel, L. Fastened CROWN: tightened neural network robustness certificates. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 5037–5044, 2020. URL https://aaai.org/ojs/index.php/AAAI/article/view/5944.

[3]Bhowmick, A., D’Souza, M., and Raghavan, G. S. Lipbab: computing exact lipschitz constant of relu networks. In International Conference on Artificial Neural Networks, pp. 151–162. 332 Springer, 2021.
questions: 1. My experience with (interval)-Clarke Jacobian is that it provides very loose result in the $\ell_2$-case. The $\ell_2$ matrix norm (largest singular value) computation is also very different from $\ell_\infty$-norm. As a result, section 4.2 would be very different in the $\ell_2$-case. I do not know how much the improvement brought from linear bound propagation would be in the $\ell_2$-case. If this work only applies to $\ell_\infty$ and $\ell_1$ (linear constraint) perturbation space, please be upfront in the abstract or intro; otherwise, please provide some comparison with LipSDP in the $\ell_2$-case.
2. Optimality result: The optimality result of CROWN has been shown in [2]. The linear constraint propagation provided in this paper appears very similar to CROWN, except this work is for the backward Clarke Jacobian analysis. Why is Theorem 4 not a corollary of the theorem in [2], given Propositions 2 and 3?
limitations: No major concerns. One suggestion for paper writing: please use other graphical features than colors to distinguish different parts of the plot. This is not friendly for color-blind readers or black and white printers.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper presents a novel method to compute upper bounds to the local Lipschitz constant of a neural network, by using linear bound propagation to bound the norm of the Clarke Jacobian of the network. The authors demonstrate that the proposed approach computes tighter bounds than the state-of-the-art in reasonable time on synthetic networks, and on networks trained for popular image datasets. Finally, the method is tested on monotonicity analysis, as an example application.
strengths_and_weaknesses: The authors make a more careful use of linear bound propagation techniques in the context of estimating a network's local Lipschitz constant, resulting in tighter bounds than the state-of-the-art estimators in reasonable time. Furthermore, the algorithm supports branching to tighten the bounds, and a custom branching strategy is presented, which appears to work well in the considered experimental settings. While the approach is not entirely original, and it draws on existing techniques (such as RecurJac), it is clearly presented and effective. I believe it might be of interest to the community.

For what concerns the weaknesses, the experimental section is somewhat limited, as it mostly relies on small and synthetic networks. It would be interesting to test the algorithm on larger networks, and possibly on neural network verification, as for instance done by the RecurJac authors. At that point, I would be curious to see how Lipschitz-based algorithms compare with common incomplete verifiers (especially those based on optimized linear bounds such as alpha and beta-CROWN). Analogously, it would be interesting to see an extension of section 4.2 on l_2 norm (which bounding algorithms for Lipschitz constants routinely support).
questions: - It would be interesting to compare the presented branching strategy against existing strategies proposed in the context of network verification, such as input splitting or FSB from https://arxiv.org/abs/2104.06718, which was notably applied in beta-CROWN

- Given that it relies on similar techniques, RecurJac should trivially support convolutional layers. Implementing this support would provide a fairer comparison.

- It would be interesting to see whether the baselines yield any different results in Table 4, for the monotonicity analysis.
limitations: The authors adequately discuss the limitations of their work. However, it would be better for the reader to have them condensed in a section in the appendix.
review_title: null

Meta-review: metareview: The paper develops a methodology for computing the Lipschitz constant of ReLu neural networks (when the input perturbations are measured in the L_infinity norm). The method is based on computing tight upper bounds on the Clarke Jacobian. The basic idea is to apply Interval Bound Propagation techniques to the backward computational graph, which yields an upper bound on the norm of the Clarke Jacobian of the network. Experimental results show superiority over SOTA in terms of scalability, runtime, and the computed bound. 

The reviewers had a number of concerns most of which were addressed during the discussion phase. I recommend that the authors revise the paper and the experiments according to the reviewers' comments as well as their own responses. The paper was also discussed among the reviewers. One main point of discussion was the novelty of the work (compared to prior art, e.g. Lyu et al) and the fact that bounding the norm of Clarke Jacobian seems to be only beneficial for L_infinity perturbations. However, some reviewers argued (and I agree) that the paper improves over SOTA methods quite notably in terms of efficiency and tightness, and the method scales to much larger models compared to prior works (scale is actually an important challenge in this topic). As a result, I would vote for accepting the paper. 

As a matter of taste, I don't think I agree with this sentence in the abstract (and similar sentences in other parts of the paper): "Existing methods for computing Lipschitz constants either are  computationally inefficient or produce loose upper bounds." We do have good methods that provide non-trivial upper bounds on the Lipschitz constant of NNs. While I agree that the scalability of those methods are still to be improved, we can not really call them inefficient. Hence, I believe that this sentence (and similar sentences in the paper) could be better rephrased. 
confidence: Certain
Decision: Accept