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: The article tackle the estimation of the Lipschitz constant of a neural network for norms $p \in \{ 2, \infty \}$. The authors rely on previously existing SDP techniques and propose new formulations that give new theoretical insights on Lipschitz estimations.
Indeed, the authors bound the approximation of the polynomial SDP relaxation, and provide formulation for norms $2$ and $\infty$.
The theory is developed for NN with one hidden layer and then extend to the general case, giving a new algorithm called GeoLip.
Finally, the paper provide experimental results that shows that GeoLip outperforms in accuracy and time previous state of the art methods on multi-layers straightforward neural networks.
strengths_and_weaknesses: The paper is clear, well written and properly motivated. The other approach in the literature are well discussed and the paper is honest at comparing itself. Overall, I really enjoyed reading this paper.

In all generality, the dual of $\ell^\infty$ is ill-defined (l120) and requires some more hypothesis, even though it does not matter here.

l131:
    In the problem description describe what is $y$ (one line it is $\sigma$, the next one it is $\sigma'$ if I get it) and explain the simplification made from the definition of neural network above (no bias).
    Use notations defined before, what is y here?
    Could we write f(x) = W2 sigma (W1 x), which would then reduce to eq(4) directly thanks to eq(3), while preserving the notations introduced before.
l147: ref for the majoration of $K_G$ and its link to eq (5).


* Conventions

Globally, why upper indices? In the paper it seems that lower indices should be enough and this would make the paper even clearer.

* Typos:
    - l92: "X [is] positive semidefinite";
    - l88,92,146: Sentences beginning with a symbol;
    - l103: no diag in the equation;
    - l109: almost everywhere (no parenthesis);
    - l112: say.

Check the end of sentences in particular after formulas as the punctuation is very often missing or incorrect (e.g. sentence finishing with a ','). In particular in the Appendix where the punctuation is chaotic.

References: many references are incomplete (lacks conference/journal)
questions: Where does the name 'GeoLIP' comes from?

In the experimental section, are NGeoLIP results taking into account the approximation bound in order to be upper-bounds?

It would be interesting to show an example in which NGeoLIP and DGeoLIP give different bounds in order to better assess the advantage of using a (fast) approximation algorithm.

Would it be possible to extend the current approach to "much bigger" feed-forward network such as CNN or residual nets? It seems it is a difficult question as is, but would specific SDP solving strategies exploit the characteristics of these operations instead of their matrix form (which would make it intractable)?
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed a new method for estimating the Lipschitz constant (more specifically, the ($\ell^p$-) Formal Global Lipschitz (FGL) constant) of DNNs.
First, this paper analyzed two-layer ReLU-DNNs and showed that $\ell^{\infty}$-FGL estimation is MAXSNP-hard (Theorem 3.2). Then, by relaxing the FGL-estimation problem and reducing it to SDP, this paper derived a polynomial algorithm with an approximation ratio $K_G$ (Theorem 3.3) for general $p=\infty$ and $\sqrt{\frac{\pi}{2}}$ for $p=2$ (Theorem 3.4).
Next, the $\ell^p$-FGL estimation problem of two-layer NNs was formulated as the maximization of perturbation of intermediate units with respect to that of the input. Then, this paper showed that this formulation is equivalent to the first formulation (l.211) and is dual to LipSDP (l.212--220) when $p=2$. In addition, this paper extended it to multi-layer NNs.
Finally, this paper evaluated the proposed method numerically and claimed that the proposed method performed tighter estimation than existing methods for the $\ell^{\infty}$-estimation problem of two-layer and multi-layer DNNs.
strengths_and_weaknesses: Strengths

- NGeoLip proposed in this paper has theoretical guarantees for the FGL-estimation problem of two-layer NNs.
- DGeoLIP proposed in this paper applies to multi-layer NNs, while competitive methods are limited to two-layer NNs.
- SDP allows a unified approach to $\ell^2$-FGL and $\ell^\infty$-FGL.

Weaknesses

- This paper is intended to apply the Lipshitz constant estimation to mitigate the vulnerability against adversarial attacks. However, this paper did not experimentally evaluate the effectiveness of the proposed methods in adversarial attacks.
- There is room for discussion on whether the proposed method sufficiently demonstrates its effectiveness (either theoretically or empirically) to the estimation problem in the multi-layer settings.
- There is room for improvements in the organization of the paper (see Clarity section).


Originality（Novelty）

- As this paper mentioned, existing literature employed the idea of reducing the Lipschitz constant estimation problem to SDP (l.55). However, this paper adopted this idea differently and proposed different algorithms.
- The authors claimed their work is guided by the principle that we should separate geometry-dependent and independent components. The authors think that this is a crucial idea underlying this paper. However, it was not clear to me how this principle works. For example, in Sections 3.1 and 3.2, $\ell^\infty$-FGL and $\ell^2$-FGL were first reduced to the mixed-norm problem and then were analyzed separately. In this example, is it correct to understand that the reduction to the mixed-norm problem is the geometrically-independent part? I suggest the authors write how they applied this principle to actual algorithms. 


Quality（Soundness）

- As far as I have checked, the mathematical statements and proofs are correct all in all.
- The details of the experimental setup are described in the Appendix. I can confirm the validity of the experiment.
- l.144: On which does the constant $K_G$ depend? Does $K_G$ depend on the Hilbert space $H$?


Clarity（Presentation）

- There is room for improvement in the organization of the paper. However, I think it does not significantly impact the paper's evaluation because I expect the authors can correct it quickly.
- I found Section 3.1 to be a bit difficult to read. Specifically, this section (1) explained the SDP relaxation for the matrix-norma problem (l.140--148), (2) changed the topic to the problem without relaxation and showed its hardness (l.149--152), and (3) went back to the problem with relaxation (l.153--169). Therefore, I suggest reconsidering the order of the three.
- I think the content of Section 4.1 should be in Section 3 rather than Section 4 since it is about two-layer NNs. Raghunathan et al. (2018), which applied two-layer NNs, is compared to eq. (6) in Section 3.1. Also, LipSDP and LipSDP-network appeared in Section 4.1. is compared with eq. (7) in Section 3.2.

Significance

- For two-layer NNs, this paper showed the theoretical and empirical effectiveness of the proposed methods well.
- For multi-layer NNs, the DGeoLIP does not have theoretical guarantees. In addition, it is not better than the baseline method by sampling (Table 1). Therefore, I have a question about the effectiveness of the proposed method for multi-layer settings.
- This paper intends to apply the estimation of the Lipschitz constant to mitigate the vulnerability of NNs to adversarial attacks. However, the numerical experiments are only performed on the pure Lipschitz constant estimation problem. Therefore, this paper would be more significant if it could show that the proposed method is effective against adversarial attacks in some way.
questions: - l.103: $f_i(x)=W^i\mathrm{diag}(\sigma(f_{i-1}(x))) + b_i$ → I think $\mathrm{diag}$ is not needed here.
- l.107: We do not usually use $\prod$ for matrix multiplications, which are non-commutative.
- l.160: Although we can understand the meaning of the term "approximation ratio" intuitively, I would suggest writing its mathematical definition explicitly since it is used in mathematical statements.
- l.169 (7): $A\cdot B$ is undefined.
- l.209: $f(x) = u\sigma(x)$ → $f(x) = u\sigma(Wx)$ ?
- l.563: I was not aware that $x$ in l.138 takes value in {-1, 1}^n. I suggest writing the range of $x$ more explicitly. I think l.563 does not hold in general (at least without any assumption). We should have:

\max_{x\in \{-1, 1\}^n} \|Ax\|_{1} = \max_{x\in \{-1, 1\}^n, , y\in \mathbb{R}^m, \|y\|_{\infty}=1} \langle Ax, y\rangle

So, I am wondering why we can restrict the range of $y$ to {-1, 1}^{m}
limitations: As far as I have checked, this paper did not discuss the proposed methods' limitations. However, the proposed method (1) only applies to ReLU-DNNs and (2) has no theoretical guarantees for multi-layer NNs. Therefore, it is desirable to discuss such limitations.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper the authors propose a new tool to estimate an upper bound on the Lipschitz constant of ReLU based feed forward networks. They focus on Lipschitz constant for L-infinity norms and L2 norms. The computation of the upper bound is based on SDP relaxations of the original problem, a standard approach of the literature. 

For L-infinity, as said by the authors, they "provide a rigorous derivation and simpler formulation, and also a sound theoretical analysis of the bound, which illustrate more insights to this problem" compared to the work of Raghunathan et al. (2018). Whereas for for L2-bounds they " show that LipSDP is dual of Equation (7) to estimate the ℓ2-FGL on two-layer networks".

Finally the release a software, GeoLip, that implements the SDP of interest for multil-layers neural networks (for l-infinity) and 2-layers neural networks (for l2). Not only the upper bound is improved compared to concurrent methods, but it is even cloaser to the lower bound obtained by sample or brute force by a small factor, even on deep networks. Moreover the running time is competitive even on those deep networks.
strengths_and_weaknesses: Strengths:

The paper makes a clear theoretial contribution by posing rigorously posing the problem. The link the Grothendieck inequality is very interesting and establish a clear bound toward algorithms must tend. The link between dual formulation (7) and previous work LipSDP 
is interesting. Claims in all theorems 3.2 3.3 and 3.4 seem to be significant contributions.

The SDP are clearly specified which allows independent implementation, and easier reproducibility. 

The speed and quality of the bounds of GeoLip software, whose code is made public, is very convincing and is validating theoretical claims.

The paper is well written, I learned a lot about this topic with which I am unfamiliar.

Weaknesses:

for reader unfamiliar with the topic some notations are a bit harsh: it took me some time to understand the motivation behind the definition of two-layers networks (l 135) : no bias since it does not play any role in computation of the upper bound (only in the pattern of activations between true Lipschitz constant and the FGL). diag(y) the pattern of activations, and u the weight of the last layer (with the NN seen as a function from R^n to R)

minor/typo: a parenthesis is lacking in equation (2)

questions: l 125 : "However, the algorithms presented in this work can be adapted with minor adjustments to other common activation functions."
Does it also work with non elementwise activation functions ? In this case the diag(y) is no longer diagonal. Is it a simple way to adapt the method to arbitrary diag(y) ?

From my limited understanding of the topic, I have two more naive (related) questions.

* For multi-layers ( i.e > 2) neural networks , do you have any theoretical guarantees like the ones of theorems 3.3 and 3.4 ?
* experiments on l2 norms for multi-layers neural networks are lacking. Is it because the duality result of section 4.1 does not extend further than the case of two-layers networks ?
limitations: Every result is clearly stated along with its hypothesis. The only part that could be subject to caution is the the running time of their solver, which might unfairly benefit from better software than other SDP based relaxations of literature, as acknowledged by the authors: "Notice that the running time is implementation and solver-dependent".
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper deals with estimating the Lipschitz constants of neural networks, aiming to unify different approaches based on semidefinite programming (SDP). More precisely, the authors would like to estimate the "formal global Lipschitz constant" (FGL) which is an upper-bound of the actual Lipschitz constant that's however sharper than the naive product of the norms of all weight matrices. They consider FGL estimation for two layer networks in the $\ell_\infty$ and $\ell_2$ topologies and also outline FGP estimation for multi layer networks. Furthermore, they show that some existing SDP based models are duals of the FGP problem. In their numerical results section the authors compare their formulations to some other methods which estimate the Lipschitz constant, like dual SDP problems or brute force methods.

########POST-REBUTTAL#########

Since there seems to be relatively strong support for the paper, I increase my score to 5 and ask the authors improve the organization of the paper.
strengths_and_weaknesses: Strengths: The numerical results seem to indicate that the presented method computes the same estimate for the Lipschitz constant as its dual SDP variants, however, in shorter time. Furthermore, it compares favorably against the chosen baseline method LiPopt and brute force estimatation. 

Weaknesses: I find the paper pretty poorly written and it's not clear what exactly the contribution or the novelty is. The theoretical part of the paper is relatively ad hoc. Furthermore, the numerical results are not entirely conclusive, see "Questions" further down. 
questions: I have a couple of questions and remarks that should be addressed: 

- p.3, l.103: I think the $\operatorname{diag}$ operator shouldn't be part of the forward pass of the network. Is this a typo?
- p.3, l.112, eq. (3): I guess that the matrices $W^i$ for $i=2,\dots,d-1$ should also appear in this formula, right?
- p.3, l.122: an interval of the form $[a,b]$ can never coincide with the set $\lbrace 0,1\rbrace$.
- p.3, l.131: I don't understand why $f(x)$ has this form. This is linear in $x$. Also: what's $y$ in $\operatorname{diag}(y)$?
- p.7, l.242: same thing here
- In general, the presentation of sections 3 and 4 is suboptimal and lacks a golden thread.
- The numerical results in Table 1 seem to suggest that sampling is the best way to estimate the Lipschitz constant. Maybe you should compare your methods with sampling based Lipschitz constant estimation methods like for instance [2].
- Given that Lipschitz regularization of neural networks is a very active field, the related work section and introduction does not paint a clear picture of the different approaches out there, such as e.g. the articles [1-5].

[1] Aziznejad, S., Gupta, H., Campos, J., & Unser, M. (2020). Deep neural networks with trainable activations and controlled Lipschitz constant. IEEE Transactions on Signal Processing, 68, 4688-4699.

[2] Bungert, L., Raab, R., Roith, T., Schwinn, L. and Tenbrinck, D., 2021, May. CLIP: Cheap Lipschitz training of neural networks. In International Conference on Scale Space and Variational Methods in Computer Vision (pp. 307-319). Springer, Cham.

[3] Gouk, H., Frank, E., Pfahringer, B., & Cree, M. J. (2021). Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110(2), 393-416.

[4] Krishnan, V., Makdah, A., AlRahman, A., & Pasqualetti, F. (2020). Lipschitz bounds and provably robust training by Laplacian smoothing. Advances in Neural Information Processing Systems, 33, 10924-10935.

[5] Terjék, D. (2019). Adversarial lipschitz regularization. arXiv preprint arXiv:1907.05681.




limitations: To my mind, a negative societal impact cannot be expected and is also not discussed. Also there is a discussion section, the possible shortcomings (and advantages) of the proposed method over sampling type methods for estimating the Lipschitz constant is not discussed.
review_title: null

Meta-review: metareview: All the reviewers agree that the paper is novel and interesting and it should be accepted. Please take into account the reviewers' comments while preparing the camera-ready version, particularly the ones on the clarity of the paper.
confidence: Certain
Decision: Accept