Measuring Neural Net Robustness with Constraints
Despite having high accuracy, neural nets have been shown to be susceptible to adversarial examples, where a small perturbation to an input can cause it to become mislabeled. We propose metrics for measuring the robustness of a neural net and devise a novel algorithm for approximating these metrics based on an encoding of robustness as a linear program. We show how our metrics can be used to evaluate the robustness of deep neural nets with experiments on the MNIST and CIFAR-10 datasets. Our algorithm generates more informative estimates of robustness metrics compared to estimates based on existing algorithms. Furthermore, we show how existing approaches to improving robustness "overfit" to adversarial examples generated using a specific algorithm. Finally, we show that our techniques can be used to additionally improve neural net robustness both according to the metrics that we propose, but also according to previously proposed metrics.
This paper introduces an algorithm to generate adversarial examples for NNs (ie. images with an imperceptible perturbation that are mislabeled by the NN). This algorithm constrains the adversarial example to be in the linear region of the activations of the ReLUs of the NN. Experiments in MNIST show that for the NN called LeNet, the adversarial examples introduced in the paper seem to be more harming than the adversarial examples introduced in previous works (in terms of L_inf norm of the perturbation).  
As in [5,20], this paper proposes a new algorithm to generate adverarial examples, and it uses the adversarial examples to re-train the NN. The algorithm to generate the adversarial examples is a bit different from previous works as it adds some additional constraints into to the optimization. I have two concerns regarding the motivation of these constraints:   -Theoretical. The constraints that are added to the algorithm to generate the adversarial perturbation are motivated by: "Since adversarial examples exists because of the linearity in the neural net [5], we restrict our search to the region around the input in which the neural net is linear". Yet, adversarial examples have also been found outside these linear region around the input. A clear case of this is that when the adversarial perturbation is multiplied by a relativelly large constant, the adversarial examples still negativelly affects the NN [5]. Moreover, there are not any theoretical guarantees that by constraining the adversarial examples to be in the aforementioned linear region, the adversarial example has minimum perturbation. There could be adversarial examples with smaller norm outside the search space of the algorithm introduced in the paper.  -Experimental. The conclusions extracted from the results do not seem to be general. The NN architectures are not state-of-the-art and not standard, and are applied in very simple datasets (MNIST and CIFAR). There are no sanity checks that the baseline of [20] has been correctly reproduced. Also, results show marginal improvements in MNIST over the baseline, and in CIFAR, the comparision with the baseline has been omitted.   Other comments:  -The results in CIFAR show that this method may not have much applicability to reduce the adversarial examples, as it takes about 15 seconds to generate one adversarial example using 8 CPUs. This will make it difficult to scale to ImageNet, and create sufficient adversarial examples to re-train the NN.  -The first time that $x_\star$ is introduced, it has been never defined before.  -It has been assumed that L_inf norm is the best measure to analyze the perceptibility of the adversarial perturbation.  -It has been mentioned that "[3] seeks to explain why neural nets may generalize well despite poor robustness properties". A more detailed explanation of [3] seems necessary here. Maybe the motivation of the constraints could be done from [3].