Thank you for your evaluation and your feedback. In the following, we address your concerns and your question. Plase do let us know if you have follow-up questions, additional concerns or suggestions.

The main concern I have is that this paper seems to be an extension of two works Fazlyab'19 and Wang'22 to the case of having sum-preserving activations like GroupSort, Maxmin, and Householder, which seems incremental.

We think that our contribution in deriving new quadratic constraints for GroupSort, MaxMin, and Householder are novel and significant, complementing the existing works such as Fazlyab'19 and Wang'22. We provide a detailed response in our general response (Part 1). Let us restate some of our key points here. We also included Appendix B to discuss the issue in our revised paper. The underlying idea in the quadratic constraint approach is to abstract "challenging", e.g., nonlinear, uncertain or time-varying elements using quadratic constraints. This abstraction allows us to formulate an SDP that can be solved effectively. Since the introduction of the quadratic constraint framework in the 1960s, many papers appeared that are only devoted to deriving new quadratic constraints. For example, Kao'07 derives quadratic constraints for a delay-difference operator to describe varying time delays, Pfifer'15 uses a geometric interpretation to derive new quadratic constraints for delayed nonlinear and parameter-varying systems, and Carrasco'16 summarizes the development of Zames-Falb multipliers based on frequency domain arguments for slope-restricted nonlinearites. In the context of NNs, so far only quadratic constraints for slope-restricted nonlinearities were utilized. By formulating quadratic constraints for GroupSort/Householder activations, we are the first ones to study multivariate activations, to formulate quadratic constraints for NNs that go beyond slope-restriction or Lipschitz continuity and in general the first to present quadratic constraints for sum-preserving elements. Finding novel quadratic constraints is by no means trivial. It requires to study and understand the characteristics of the underlying nonlinearity and then to capture the identified property using a quadratic form. There is no recipe for such a derivation and finding a quadratic constraint does not guarantee that it improves the analysis over other methods. The tighter the description of the nonlinearity by quadratic constraints, the better the analysis in terms of conservatism. The idea we used to derive these quadratic constraints is creative in the sense that it is very different from all the existing quadratic constraint derivations, hence offering unique new insights and complementing the large body of existing arguments in deriving quadratic constraints. To understand the technical details of our derivation, we refer to the proofs in Appendices C.2 and C.3.

How frequently are GroupSort, Maxmin, and Householder being used in practice?

Please see our general response (Part 2). GroupSort, MaxMin, and Householder activations are gradient norm preserving and have been of particular interest when fitting Lipschitz functions and for the design of certifiably robust neural networks (NNs). There are many works (e.g. Leino'21, Singla'21, Trockman'21, Huang'21, Singla'22, Prach'22, Hu'23) that use MaxMin activations and provide state-of-the-art certified robust accuracy (please see our general response, Part 2 for a detailed list of the references). To compute the certified robust accuracy, these works rely on information of Lipschitz bounds and prediction margins. Hence LipSDP for MaxMin networks is of great interests. Another interesting application of MaxMin NNs is in learning-based control (Yion'23), where the information of the Lipschitz constant of a neural network in the loop can be useful to verify safety and robustness. Please note that we included a section on applications of MaxMin NNs as Appendix A.

The results would be more interesting and valuable if using GroupSort, Maxmin, and Householder activations have some implicit bias towards having an NN with a smaller Lipschitz constant.

The implicit bias towards smaller Lipschitz constant of neural networks is typically governed by specific neural network structures (e.g. Singla'21, Trockman'21, Prach'22) or regularization terms in the training objective (e.g. Leino'21,Huang'21, Hu'23), but not directly through the choice of the activation function. The popularity of the MaxMin activation (or GroupSort and Householder in general) for certifiably robust networks is mainly due to their gradient norm preserving (GNP) properties, since the GNP properties can help the training of certifiably robust neural networks become more stable.

Thank you for your thorough evaluation of our paper. We would like to address your comments as below. We are also available to address any potential follow-up questions/suggestions.

Additional details on why the GroupSort and Householder activations are of particular interest for Lipschitz constant estimation?

Please see our general response (Part 2). GroupSort and Householder activations are gradient norm preserving and have been of particular interest when fitting Lipschitz functions and for the design of certifiably robust neural networks (NNs). There are many works published in top machine learning conferences (e.g. Leino'21, Singla'21, Trockman'21, Huang'21, Singla'22, Prach'22, Hu'23) that use MaxMin activations and provide state-of-the-art certified robust accuracy (we provide details in our general response, Part 2). To compute the certified robust accuracy, these works rely on information of Lipschitz bounds and prediction margins of the trained networks. Hence LipSDP for MaxMin networks is of great interests. Another interesting application of MaxMin NNs is in learning-based control (Yion'23), where the information of the Lipschitz constant of a neural network in the loop can be useful to verify safety and robustness. Please note that we included a section on applications of MaxMin NNs as Appendix A.

I would also appreciate it if the authors could provide running times for the naive estimation strategies.

We are happy to provide this additional information. We recalculated the computation times for all our naive bounds. The computation times of the matrix product bound are for all our networks below 10s, so they are basically instantaneous. This means there definitely is a price for the tighter bounds using our method. The computation times for the lower bounds from sampling based on 200k samples range between 12 and 23 s. The FGL bound takes 4.54s for the 2FC-16 NN and 81.92s for the 2FC-32 NN. For larger NNs it however becomes intractable (we stopped our code for 2FC-64 after 4 hours).

Find the running times of all naive l2 bounds for our networks in Table 1 in the table below:

Finally, perhaps the authors can comment on the difficulty of deriving the quadratic constraints for the SDPs.

Please see our general response (Part 1) for a detailed response. We are also happy to restate some of our key points here. We also included Appendix B to discuss this issue in our revised paper. The underlying idea in the quadratic constraint approach is to abstract "challenging", e.g., nonlinear, uncertain or time-varying elements using quadratic constraints. This abstraction allows us to formulate an SDP that can be solved effectively. Since the introduction of the quadratic constraint framework in the 1960s, many papers appeared that are only devoted to deriving new quadratic constraints. For example, Kao'07 derives quadratic constraints for a delay-difference operator to describe varying time delays, Pfifer'15 uses a geometric interpretation to derive new quadratic constraints for delayed nonlinear and parameter-varying systems, and Carrasco'16 summarizes the development of Zames-Falb multipliers based on frequency domain arguments for slope-restricted nonlinearites. In the context of NNs, so far only quadratic constraints for slope-restricted nonlinearities were utilized. By formulating quadratic constraints for GroupSort/Householder activations, we are the first ones to study multivariate activations, to formulate quadratic constraints for NNs that go beyond slope-restriction or Lipschitz continuity and in general the first to present quadratic constraints for sum-preserving elements. Finding novel quadratic constraints is by no means trivial. It requires to study and understand the characteristics of the underlying nonlinearity and then to capture the identified property using a quadratic form. There is no recipe for such a derivation and finding a quadratic constraint does not guarantee that it improves your analysis over other methods. The tighter your description of the nonlinearity by quadratic constraints, the better the analysis in terms of conservatism. The idea we used to derive new quadratic constraints is creative in the sense that it is very different from all the existing quadratic constraint derivations, hence offering unique new insights on how to use properties such as sum-preservation.

Thanks for responding to my concerns and for providing the timings of the naive baseline methods. I also appreciate the inclusion of LipSDP-RR along with runtimes. I think these results provide a more nuanced view of LipSDP-NSR and fit well with the paper's story, which was motivated by better bounds in the L2 norm. I am not particularly concerned that LipSDP-RR sometimes has better performance for the L-infinity norm since computing the constant in the L-infinity norm is most "value added" in my opinion.

It is surprising to me that FGL is faster than LipSDP-NSR for small networks despite being an exponential time algorithm. Of course, this time complexity catches up for larger models as you mention. I suppose the constant-factor overhead for the SDP solver dominates when running on small architectures.

The matrix-product approach (MP), while naive, is very fast and provides acceptable-looking bounds when the number of layers is eight or less. I think it's worth including the runtimes you provided here in the paper (appendix is fine) and including a comment on the trade-off between efficiency and tightness for MP. In many cases it may be worth obtaining a loose bound quickly, which MP does well.

Overall, I am convinced that the paper has practical use and that the quadratic constraints are of theoretical interest, so I will increase my score to 6. However, I do feel this paper is closer to 7 (although this doesn't exist for ICLR) and lean towards accepting the submission.

We appreciate your comments and evaluation of our work. We will address your concerns in the following and are happy to answer any follow-up questions.

The result seems to be weak since the quadratic constraints only applied to 2 specific activations. It would be more interesting if it can be applied to a class of activaitons.

We would consider GroupSort and HouseHolder as two classes of activations. Both generalize MaxMin which is widely used for robust networks due to the ease of implementation. Our constructions of quadratic constraints are also general in the sense that our GroupSort quadratic constraint also holds for the class of all sum-preserving activations. We now clearly state this in introduction of the revised version of the paper.

How does the new formaulation compare to the original LipSDP for MaxMin networks in terms of computational efficiency/runtime?

Thank you for this question. To investigate this question, we used the description of the MaxMin acitvation using a residual ReLU network (4), as shown in our motivating example in Section 3. For this equivalent formulation we then implemented an SDP for the residual ReLU equivalent form of MaxMin (the multi-layer variants of (5) under either $\ell_2$ or $\ell_\infty$ setting) using quadratic constraints for slope-restricted activations to compute Lipschitz bounds. We denote the SDP on the residual ReLU formulation by LipSDP-RR. We added our results in the paper and for convenience also state the new results in the table below, where we compare the bounds and the computation times. We observe that our LipSDP-NSR provides better bounds in most cases, with two exceptions for 2-layer networks under the $\ell_\infty$ setting, i.e. $\ell_\infty$ Lipschitz bounds for 2FC-64 and 2FC-128. For 5- and 8-layer networks, our LipSDP-NSR is always better than LipSDP-RR, and there even is a significant gap. Notice that LipSDP-NSR outperforms LipSDP-RR in all cases under the $\ell_2$ setting. This is consistent with the intuition provided by our motivating example in Section 3 of our paper. Specifically, our motivating example in Section 3 implies that the quadratic constraints derived from slope-restricted properties of ReLU have severe fundamental limitations in addressing the $\ell_2$ case of MaxMin Lipschitz analysis, i.e. it cannot recover the basic 1-Lipschitz property of the MaxMin activation under the $\ell_2$ setting. Our new quadratic constraints derived for MaxMin fix that, and our numerical results support our claim. In the $\ell_\infty$ setting, the output is always a scalar and the 1-Lipschitzness of MaxMin activation is not explicitly needed for SDP-based analysis. Hence our motivating example does not indicate much for the $\ell_\infty$ setting. However, our LipSDP-NSR still outperforms LipSDP-RR in most cases under the $\ell_\infty$ setting. Finally, we want to comment on the computation efficiency. We want to point out that advantages in computational efficiency of the MaxMin quadratic constraint formulation become apparent only for larger networks. It is interesting to notice that for small neural networks, LipSDP-RR can sometimes be faster, and this can be explained by the different implementations of the two problems. The computation time depends on the number of decision variables and on the conditioning of the problem. While the number of decision variables are the same in both problems, the multiple constraints for LipSDP-NSR are much smaller than the one constraint in LipSDP-RR. For networks larger than 8FC-64 we even run into memory problems when solving the SDP for the residual ReLU network formulation.

Practical Use of MaxMin and Relevance of Lipschitz Estimation of MaxMin Networks

In the deep learning field, MaxMin activations have been widely used to address certified robustness of neural networks. The following papers are all published in top machine learning venues and use MaxMin to improve certified robust accuracy of deep neural networks.

[Leino'21] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. ICML

[Singla'21]. Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. ICML

[Trockman'21] Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the Cayley transform. ICLR

[Huang'21] Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local Lipschitz bounds. NeurIPS

[Singla'22] Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100. ICLR

[Prach'22] Bernd Prach and Christoph H Lampert. Almost-orthogonal layers for efficient general-purpose lipschitz networks. ECCV

[Hu'23] Kai Hu, Andy Zou, Zifan Wang, Klas Leino, and Matt Fredrikson. Unlocking deterministic robustness certification on imagenet. NeurIPS

The above papers provide state-of-the-art (deterministic) certified robust accuracy for neural networks, and all these works use MaxMin as activation functions. The state-of-the-art certified robust accuracy for Imagenet is actually achieved using MaxMin activations (Hu'23), and Huang'21 for example states that MaxMin can achieve significantly better results on certified robust accuracy than its ReLU counterpart. To compute the certified robust accuracy, one needs to use the information of the Lipschitz constant and the prediction margin of the trained networks. Therefore, studying LipSDP for improving the Lipschitz constant estimation of MaxMin networks is of great interest to the deep learning community.

In addition, LipSDP for MaxMin networks can also be useful for learning-based control with neural network controllers. Very recently, researchers have started to use MaxMin activations for Lipschitz neural network controllers in this field (Yion'23). LipSDP for MaxMin can potentially reduce the conservatism in the stability and robustness analysis of such MaxMin network controllers.