A STATISTICAL APPROACH TO ASSESSING NEURAL NETWORK ROBUSTNESS
We present a new approach to assessing the robustness of neural networks based on estimating the proportion of inputs for which a property is violated. Specifically, we estimate the probability of the event that the property is violated under an input model. Our approach critically varies from the formal verification framework in that when the property can be violated, it provides an informative notion of how robust the network is, rather than just the conventional assertion that the network is not verifiable. Furthermore, it provides an ability to scale to larger networks than formal verification approaches. Though the framework still provides a formal guarantee of satisfiability whenever it successfully finds one or more violations, these advantages do come at the cost of only providing a statistical estimate of unsatisfiability whenever no violation is found. Key to the practical success of our approach is an adaptation of multi-level splitting, a Monte Carlo approach for estimating the probability of rare events, to our statistical robustness framework. We demonstrate that our approach is able to emulate formal verification procedures on benchmark problems, while scaling to larger networks and providing reliable additional information in the form of accurate estimates of the violation probability.
Verifying the properties of neural networks can be very difficult.  Instead of
finding a formal proof for a property that gives a True/False answer, this
paper proposes to take a sufficiently large number of samples around the input
point point and estimate the probability that a violation can be found.  Naive
Monte-Carlo (MC) sampling is not effective especially when the dimension is
high, so the author proposes to use adaptive multi-level splitting (AMLS) as a
sampling scheme. This is a good application of AMLS method.
Experiments show that AMLS can make a good estimate (similar quality as naive
MC with a large number of samples) while using much less samples than MC, on
both small and relatively larger models.  Additionally, the authors conduct
sensitivity analysis and run the proposed algorithm with many different
parameters (M, N, pho, etc), which is good to see.
I have some concerns on this paper:
I have doubts on applying the proposed method to higher dimensional inputs. In
section 6.3, the authors show an experiments in this case, but only on a dense
ReLU network with 2 hidden layers, and it is unknown if it works in general.
How does the number of required samples increases when the dimension of input
(x) increases? 
Formally, if there exists a violation (counter-example) for a certain property,
and given a failure probability p, what is the upper bound of number of samples
(in terms of input dimension, and other factors) required so that the
probability we cannot detect this violation with probability less than p?
Without such a guarantee, the proposed method is not very useful because we
have no idea how confident the sampling based result is. Verification needs
something that is either deterministic, or a probabilistic result with a small
and bounded failure rate, otherwise it is not really a verification method.
The experiments of this paper lack comparisons to certified verification
methods. There are some scalable property verification methods that can give a
lower bound on the input perturbation (see [1][2][3]).  These methods can
guarantee that when epsilon is smaller than a threshold, no violations can be
found.  On the other hand, adversarial attacks give an upper bound of input
perturbation by providing a counter-example (violation). The authors should
compare the sampling based method with these lower and upper bounds. For
example, what is log(I) for epsilon larger than upper bound?
Additionally, in section 6.4, the results in Figure 2 also does not look very
positive - it unlikely to be true that an undefended network is predominantly
robust to perturbation of size epsilon = 0.1. Without any adversarial training,
adversarial examples (or counter-examples for property verification) with L_inf
distortion less than 0.1 (at least on some images) should be able to find. It
is better to conduct strong adversarial attacks after each epoch and see what
are the epsilons of adversarial examples.
Ideas on further improvement:
The proposed method can become more useful if it is not a point-wise method.
If given a point, current formal verification method can tell if a property is
hold or not.  However, most formal verification method cannot deal with a input
drawn from a distribution randomly (for example, an unseen test example). This
is the place where we really need a probabilistic verification method. The
setting in the current paper is not ideal because a probabilistic estimate of
violation of a single point is not very useful, especially without a guarantee
of failure rates.
For finding counter-examples for a property, using gradient based methods might
be a better way. The authors can consider adding Hamiltonian Monte Carlo to
this framework (See [4]).
References: 
There are some papers from the same group of authors, and I merged them to one.
Some of these papers are very recent, and should be helpful for the authors
to further improve their work.
[1] "AI2: Safety and Robustness Certification of Neural Networks with Abstract
Interpretation", IEEE S&P 2018 by Timon Gehr, Matthew Mirman, Dana
Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, Martin Vechev 
(see also "Differentiable Abstract Interpretation for Provably Robust Neural
Networks", ICML 2018. by Matthew Mirman, Timon Gehr, Martin Vechev.  They also
have a new NIPS 2018 paper "Fast and Effective Robustness Certification" but is
not on arxiv yet)
[2] "Efficient Neural Network Robustness Certification with General Activation
Functions", NIPS 2018. by Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui
Hsieh, Luca Daniel.  
(see also "Towards Fast Computation of Certified Robustness for ReLU Networks",
ICML 2018 by Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh,
Duane Boning, Inderjit S. Dhillon, Luca Danie.)
[3] Provable defenses against adversarial examples via the convex outer
adversarial polytope, NIPS 2018. by Eric Wong, J. Zico Kolter.
(see also "Scaling provable adversarial defenses", NIPS 2018 by the same authors)
[4] "Stochastic gradient hamiltonian monte carlo." ICML 2014. by Tianqi Chen,
Emily Fox, and Carlos Guestrin.
============================================
After discussions with the authors, they agree to revise the paper according to our discussions and my primary concerns of this paper have been resolved. Thus I increased my rating.