Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper studies the adversarial robustness of neural networks by giving theoretical guarantees, providing statistical estimators and running experiments. It is a lot of work and it is reasonably written. The problem is that a fair bit of it is quite basic: for example the measurability property is very much expected -- noone was doubting it, and the proof is more of a formality than a contribution. Similarly with the statistical sampling: the method seems to rely on i.i.d. sampling -- has this reviewer missed any important details? If not, then it's only the bounds that are a contribution, but the method is not. We would appreciate more specific description of the main contribution, without it we cannot recommend the acceptance of this paper.

I am very grateful to the authors for their response. I feel now that a main weakness of this paper may be that it puts too many results in one place. I would strongly suggest re-writing it, possibly into separate papers, to make the things pointed out in the response more clear and self-standing.
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: Summary:

The paper formally defines local and global adversarial robustness. Following that, the paper investigates how to estimate local and global adversarial robustness using an estimator based on evaluating these quantities on the empirical distribution. Using a Chernoff bound, the papers evaluate probabilistic bounds on the deviation of the estimated quantities from the true quantities.  Finally, simulations are provided to evaluate these bounds for examples.

Comments:

The authors' insistence on their contribution being proving measurability does not make sense -- of course everything is measurable! Furthermore, the formal definitions or local and global robustness are well-known, the bounds in Theorems 1 and 2 are not novel and highly unlikely to be tight. The redeeming aspect of the paper is the experiments, where the authors show that these bounds can actually be (approximately) calculated. However, I feel that merely experimental results with correct but not significant theoretical contributions does not meet the bar for acceptance. 
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: This paper seeks to analyze the global robustness of neural networks, a concept defined in the paper. The authors show using concentration inequalities that the empirical local robustness approximates the global robustness. The authors investigate various other issues in the robustness literature, including the robustness/accuracy tradeoff, whether iterative pruning increases robustness, and the robustness of Bayesian networks.

I would vote for rejecting this paper for two key reasons. First, the notion of global robustness is not well-motivated (why do we want to compute this metric? What does it tell us that local robustness does not?). Second, the paper tries to do too many different things, and as a result does not give enough attention to any particular topic.

First, I believe it is up to the authors to motivate their study of global robustness further. While I acknowledge that a few prior works exists along these lines, I do not feel that this work provides much new insight into why global robustness is interesting to examine.

The authors go on to prove results showing that an empirical estimator of the local robustness will converge to the global robustness. The bounds require that the dataset size scales with eps^-2, where eps is the error. This is not terrible but also not great; for example, achieving 1% error requires a dataset size of 10^4 (realistically, even larger datasets would be required to achieve results with high probability).

Next, I would suggest that the authors avoid using the word “guarantees” if they are estimating empirical local robustness in an approximate (rather than exact) manner. Guarantees implies strict results, but the authors use a weak attack (FGSM) to approximate empirical local robustness. The results from FGSM could be far from optimal; the authors could use a stronger attack (e.g. PGD) in addition to changing the wording, or they could find provable guarantees using alternate methods.

Lastly, the authors try to tackle 3 extra questions beyond global robustness toward the end of the paper, and the last two questions are not properly fleshed out.

I like section 4.2, where the authors empirically show that networks that have better hyperparameters (for regular accuracy) tend to be less robust. This is a confirmation of a previously studied phenomena in the literature. Ideally, I would also appreciate it if the authors found the line of best fit to the dataset in addition to the plots provided. I would like a clarification on whether any of these networks were trained to be robust, although it appears that they were all trained normally. I would also like to see plot 2c (for the standard case of robustness of C(x_tilde) = C(x)), except for MNIST and CIFAR10 as well. I feel that the last-layer representation metric the authors analyze (f(x) is close to f(x_tilde)) could be misleading, as robustness on the last layer does not necessarily imply standard adversarial robustness.

Section 4.3 explores iterative pruning, but that seems fairly unrelated to the rest of the paper. Finally, Section 4.4 tries to show the opposite trend for Bayesian Neural Networks, but unfortunately the results for such networks do not yet scale beyond MNIST.

Additional Feedback:

- Why did you use R^emp and D^emp as opposed to just R^emp(g) and R^emp(g_bar)?
- In Figure 1, what is the dataset size |S|?
- In the last sentence of Section 4.3, I didn’t understand what you meant about the relationship between weight pruning and network regularization. Do you mean that weight regularization has no effect on robustness, just like iterative weight pruning?

review_title: Official Blind Review #1

Meta-review: The authors propose a framework for estimating "global robustness" of a neural network, defined as the expected value of "local robustness" (robustness to small perturbations) over the data distribution. The authors prove the the local robustness metric is measurable and that under this condition, derive a statistically efficient estimator. The authors use gradient based attacks to approximate local robustness in practice and report extensive experimental results across several datasets.

While the paper does make some interesting contributions, the reviewers were concerned about the following issues:
1) The measurability result, while technically important, is not surprising and does not add much insight algorithmically or statistically into the problem at hand. Outside of this, the paper does not make any significant technical contributions.
2) The paper is poorly organized and does not clearly articulate the main contributions and significance of these relative to prior work.
3) The fact that the local robustness metric is approximated via gradient based attacks makes the final results void of any guarantees, since there are no guarantees that gradient based attacks compute the worst case adversarial perturbation. This calls into question the main contribution claim of the paper on computing global robustness guarantees.

While some of the technical aspects of the reveiwers' concerns were clarified during the discussion phase, this was not sufficient to address the fundamental issues raised above.

Hence, I recommend rejection.
Decision: Reject