Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies (instance-wise) certification for Deep Neural Networks. Quantitatively, this metric can be defined as an integral, and the common computational approach is using Monte Carlo simulation. 

The authors consider using statistical hypothesis testing as a surrogate of certification, and the key contribution is a more efficient sequential Monte Carlo algorithm. The theoretical guarantees of the proposed algorithm are by bounding the False Positive Rate and False Negative Rate. The theoretical results (Prop 1 to Prop 4) rely on the property of the Last Particle simulation, which is presented in Theorem 1.

The authors also demonstrate the efficiency and scalability of their algorithm.
main_review: The workhorse of the paper is a more efficient sequential Monte Carlo algorithm by using the last particle simulation. Both the algorithm and the theoretical analysis strongly rely on previous work. The algorithm improves the crude Monte Carlo simulation by using the Last Particle simulation. In the context of certification, the theoretical results are derived by simply bounding the False Positive Rate and False Negative Rate. It seems that the contribution of this work is incremental compared to previously known results.
limitations_and_societal_impact: Yes, the authors mentioned that the Last Particle simulation is sequential, which is not GPU friendly.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors provide a novel way of accessing neural network robustness. In the classification by [Singh et al., 2018] they provide a method that is complete, but not sound. In other words, their method is guaranteed to certify the model if it satisfies the property, but is capable of producing False Positives - e.g. models that do not satisfy the property can be certified. The derived method is based on statistical hypothesis testing - rather than looking at worst case scenarios, which is done often, they look at the probability of violation of the property over a density of perturbations. The core part of the method is the Last Particle algorithm, invented by [Guyader et al. [2011]], which come with a theorem that states the distribution of its output. This provides the mathematical framework needed to perform a hypothesis testing given a run of the algorithm. The authors demonstrate with several propositions, proved in the Appendices, how the critical probability p_c and the significant level \alpha affect the power of the test (it basically produces less False Positives as \alpha and p_c decrease). In addition the authors demonstrate that the proposed method scales logarithmically in the number of calls needed, which is in contrast to other approaches in literature that have linear dependence. Several empirical experiments validate the claims and showcase that indeed the method provides a computationally efficient method, with very good results.
main_review: The paper is written really good and is easy to follow with clear narrative, proposed method and experimental results. 
Unfortunately, I'm not too familiar with this area of research, hence I can not comment on how well do the authors present or omit any other competitive approaches. 
I think the comparison with ERAN on the simpler problems indeed show very significant promise for this method to be practically applicable. In fact potential combination with the sound solvers, provides both an upper and lower bound on the number of certifications, which can be useful in practice. 
limitations_and_societal_impact: As indicated by the authors, the two major limitations are the fact that the method is not parallelizable and does not make any use of model information (in the form of gradients or anything else). I think I would have liked them to provide some more detailed discussion on how this can be extended in the future, or if why there are fundamental blocks to it. For instance one can run multiple chains of the proposed algorithm in parallel, which would provide multiple draws from the same distribution and potentially these could be combined to improve the confidence level bound (though this is speculation, have not actually tried to prove this). In addition, the proposal distributions for resampling the new point seem relatively simple. Since they are looking for a MC that has as invariant distribution \pi_0, I wonder why they have not even discussed any more sophisticated MCMC methods (or why those would not be applicable to this problem). 

Finally, the ImageNet experiments seem a bit small - only 5 test images? Given that this runs on a laptop for 30sec per image, you could have run this over 1500 images per day (and this assuming you only have a single laptop!). I would like to see here a significantly broader evaluation, and with access to even several computers you can probably run this on the whole ImageNet test set. Also there is no comment on running ERAN on that example - how expensive is it or does it always reach infeasible results? From the results on MNIST it seems that it is an order of magnitude slower, but if that implies 30 minutes per image, this is still something that you can definitely run and show us the results.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper approaches the problem of the robustness assessment of neural networks. To be more precise, it focuses on the corruption robustness, which considers the modification of inputs with random noise instead of adversarial attacks. The main question here is to estimate the probability of the correct classification for the given network and noise model. 

The main development of the paper is the application of the algorithm proposed in (Guyader, 2011) to the robustness estimation. The algorithm iteratively updates a set of particles by simultaneously sampling from the given distribution (noise distribution in this case) and maximizing the target function. For the target function, the authors consider the classification error. Then, using Theorem 1 from (Guyader, 2011) the authors estimate the probability of false classification and certify whether this probability is below the user-specified threshold. 


(Guyader, 2011) Guyader, Arnaud, Nicolas Hengartner, and Eric Matzner-Løber. "Simulation and estimation of extreme quantiles and extreme probabilities." Applied Mathematics & Optimization 64, no. 2 (2011): 171-196.
main_review: Overall the proposed scheme sounds very reasonable and technically developed. To the best of my knowledge, the scheme is novel, although I might be unfamiliar with some of the relevant works. A surprising outcome of the provided analysis is that a lesser number of particles yields a better estimation of the error probability. This can be explained by the growing variance of the target function estimate, which assigns more probability mass to high values. Since we are interested in the quantiles around high values, the high variance is favorable. However, to perform the analysis the authors approximate Gamma distribution with the Gaussian using the central limit theorem. Since the tails analysis is important for this application I would expect a more careful study or some discussion of this phenomenon at least.

Unfortunately, the empirical study is a weak point of this paper. As I understand the target application, the algorithm should be tested for the certification error and for the running time. The authors provide the certification error for the ACAS Xu dataset in Table 2 but do not provide the running times for this dataset. For MNIST, the proposed algorithm runs faster than the competitor, but falsely certifies some networks as robust, hence, making errors. Thus, no clear conclusion can be made in terms of the overall performance (both running time and accuracy). Finally, for ImageNet, the authors do not compare against other algorithms at all. For both ImageNet and MNIST the authors test their algorithm on 5 images. I wonder why such a small number of images has been considered, especially when the algorithm runs quickly even on a laptop (as claimed by the authors).

I think the lack of systematic comparison against other algorithms (from different approaches outlined in the introduction) is a significant flaw of the paper. This comparison has to be done even if it's obvious that the proposed algorithm has better properties. For instance, I can imagine that the considered task is simple enough that an adversarial attack via gradient descent can find a counter-example whenever it is possible. Such a baseline would hint readers what to use and what to try in their concrete example.
limitations_and_societal_impact: The authors motivate the proposed algorithm by military applications in the introduction. They also provide the empirical study on the "Airborne Collision Avoidance System X for unmanned aircrafts" dataset. I think the Broader Impact section is incomplete without the discussion of these applications.
review_title: null

Meta-review: This paper uses a hypothesis testing based approach to provide a statistical assessment of corruption robustness, with a scalable MC-based computational approach. 

The authors have made an impressive effort to address the concerns of the reviewers. Though not all the concerns are fully addressed, the emerging consensus is that the additional comments, clarifications, and also experiments, have satisfactorily addressed many of the concerns raised. 
Decision: Accept (Poster)