Lipschitz constant estimation for Neural Networks via sparse polynomial optimization
We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bound on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use structural properties of the network, such as sparsity, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the -Lipschitz constant, our approach yields superior estimates as compared to other baselines available in the literature.
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.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Lipschitz constant estimation for Neural Networks via sparse polynomial optimization
We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bound on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use structural properties of the network, such as sparsity, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the -Lipschitz constant, our approach yields superior estimates as compared to other baselines available in the literature.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



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