Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors introduce a framework for computing upper bounds on the Lipschitz constant for neural nets. The main contribution of the paper is to leverage the sparsity properties of typical feed-forward neural nets to reduce the computational complexity of the algorithm. Through experiments, the authors show that the proposed algorithm computes tighter Lipschitz bounds compared to baselines.

The approach proposed in the paper looks interesting. Although the presentation can be made clearer in places. For example, in equation (4), it would be helpful to explicitly state over which parameters the max is taken. There's also a number of small typos that need to be fixed. For example: "We refer to d as the depth, and we we focus on the case where fd has a single real value as output." on page 1.

I found the proposed algorithm and the discussions in Section 2 and 3 interesting, although I am not familiar enough with the literature on polynomial optimization to evaluate whether there is any significantly new idea presented in these sections. I found section 4 very interesting too, and very important towards making the algorithm actually computationally tractable. I have a couple of concerns with the rest of the paper however, which `I describe below:

1. It is nice that upper bounds for the local Lipschitz constant can be incorporated easily into the formulation. I would have liked to see some experiments on evaluating local Lipschitz constants though, and how they compare with other methods, since this is a very popular setting in which such techniques are used nowadays.

2. The paper overall I think would benefit from a better experimental evaluation. It would be interesting to see how much the sparsity pattern in convnets affect results compared to other baselines. It would also be interesting to see how the bound degrades as the network grows bigger, and in particular as the depth increases.

Given the lack of thorough experiments in the paper, I am giving the paper a borderline rating. I am however willing to increase my score based on discussions with the authors and other reviewers.

===================================

Edit after rebuttal: 
The latest draft addresses most of my concerns, and I am happy to recommend accepting this paper now.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper presents a general approach for upper bounding the Lipschitz constant of a neural network by relaxing the problem to a polynomial optimization problem. And the authors extend the method to fully make use of the sparse connections in the network so that the problem can be decomposed into a series of much smaller problems, saving large amount of computations and memory. Even for networks that don't have high-level sparse connections, the proposed method can still help to reduce the size of the problem. This paper also compares the proposed LiPopt method with another solution derived from a quadratically constrained quadratic program reformulation. Compared with this method, the LiPopt method can handle cases with more parameters efficiently.

Calculating a TIGHT upper bound of a neural network efficiently is very valuable and useful in many areas in deep learning community. And I really like the potential to use this LiPopt method to upper bound local Lipschitz constant in a given neighboring region, which will be very useful in certificated robustness application, etc..

I also like that the authors present results on networks trained on real-world dataset (MNIST). My only suggestion is that I'd like to see LiPopt's computation time and memory usage compared to its counterparts, as the authors argue the proposed method can fully exploit the sparse connections to reduce the problem size.

=======
Update: I am satisfied with the authors' solid response and would like to raise my score.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The authors study the problem of estimating the Lipschitz constant of a deep neural network with ELO activation function. The authors formulate the problem as a polynomial optimisation problem, which is elegant. Subsequently, they utilise an LP hierarchy based on the Krivine-Vasilescu-Handelman’s Positivstellensatz and suggest exploiting sparsity therein. The computational results are clearly not sufficient to apply this approach to real-world neural networks, but are still respectable.

Section 3 (Theorem 2) is not original work, as leaving the theorem without a reference would imply: the authors cite Section 9 of Lasserre's 2015 book later, so they are clearly aware of this, and there are many application even within verification, e.g.,
https://link.springer.com/content/pdf/10.1007%2F978-3-319-48989-6_44.pdf
https://ieeexplore.ieee.org/document/8493559

The suggestions as to the exploitation of sparsity (Section 4) are not original work either. The authors could cite, e.g., JB Lasserre: Convergent SDP-relaxations in polynomial optimization with sparsity (SIAM Journal on Optimization, 2006), as one of the early proponents of the exploitation of sparsity.

In Section 7:
-- The claim "We observed clear improvement of the Lipschitz bound obtained, compared to the SDP method" is not supported by the results the authors present. 
-- The authors do not present the run-time. This needs to be included, considering they imply that the key improvement over the traditional SDP is that this works with smaller variables and should be faster. 
-- The presentation of the experimental results should be improved, so as to follow the NIPS reproducibility checklist, or at least have error bars at one standard deviation and standard deviation in the table. 

Other than that, the paper is well written (modulo Section missing in "Section 5" at the top of Section 7), and I would recommend its acceptance. 
review_title: Official Blind Review #1

Meta-review: This paper improves upper bound estimates on Lipschitz constants for neural networks by converting the problem into a polynomial optimization problem.  The proposed method also exploits sparse connections in the network to decompose the original large optimization problem into smaller ones that are more computationally tractable. The bounds achieved by the method improve upon those found from a quadratic program formulation.  The method is tested on networks with random weights and networks trained on MNIST and provides better estimates than the baselines.

The reviews and the author discussion covered several topics.  The reviewers found the paper to be well written.  The reviewers liked that tighter bounds on the Lipschitz constants can be found in a computationally efficient manner.  They also liked that the method was applied to a real-world dataset, though they noted that the sizes of the networks analyzed here are smaller than the ones in common use.  The reviewers pointed out several ways that the paper could be improved.  The authors adopted these suggestions including additional comparisons, computation time plots, error bars, and relevant references to related work.  The reviewers found the discussion and revised paper addressed most of their concerns.

This paper improves on existing methods for analyzing neural network architectures and it should be accepted.
Decision: Accept (Poster)