We prove, under two sufficient conditions, that idealised models can have no adversarial examples. We discuss which idealised models satisfy our conditions, and show that idealised Bayesian neural networks (BNNs) satisfy these. We continue by studying near-idealised BNNs using HMC inference, demonstrating the theoretical ideas in practice. We experiment with HMC on synthetic data derived from MNIST for which we know the ground-truth image density, showing that nearperfect epistemic uncertainty correlates to density under image manifold, and that adversarial images lie off the manifold in our setting. This suggests why MC dropout, which can be seen as performing approximate inference, has been observed to be an effective defence against adversarial examples in practice; We highlight failure-cases of non-idealised BNNs relying on dropout, suggesting a new attack for dropout models and a new defence as well. Lastly, we demonstrate the defence on a cats-vs-dogs image classification task with a VGG13 variant.
The paper studies the adversarial robustness of Bayesian classifiers. The authors state two conditions that they show are provably sufficient for "idealised models" on "idealised datasets" to not have adversarial examples. (In the context of this paper, adversarial examples can either be nearby points that are classified differently with high confidence or points that are "far" from training data and classified with high confidence.) They complement their results with experiments.
I believe that studying Bayesian models and their adversarial robustness is an interesting and promising direction. However I find the current paper lacking both in terms of conceptual and technical contributions.
They consider "idealized Bayesian Neural Networks (BNNs)" to be continuous models with a confidence of 1.0 on the training set. Since these models are continuous, there exists an L2 ball of radius delta_x around each point x, where the classifier has high confidence (say 0.9). This in turn defines a region D' (the training examples plus the L2 balls around them) where the classifier has high confidence. By assuming that an "idealized BNN" has low certainty on all points outside D' they argue that these idealized models do not have adversarial examples. In my opinion, this statement follows directly from definitions and assumptions, hence having little technical depth or value. From a conceptual point of view, I don't see how this argument "explains" anything. It is fairly clear that classifiers only predicting confidently on points _very_ close to training examples will not have high-confidence adversarial examples. How do these results guide our design of ML models? How do they help us understand the shortcomings of our current models?
Moreover, this argument is not directly connected to the accuracy of the model. The idealized models described are essentially only confident in regions very close to the training examples and are thus unlikely to confidently generalize to new, unseen inputs. In order to escape this issue, the authors propose an additional assumption. Namely that idealized models are invariant to a set of transformations T that we expect the model to be also invariant to. Hence by assuming that the "idealized" training set contains at least one input from each "equivalence class", the model will have good "coverage". As far as I understand, this assumption is not connected to the main theorem at all and is mostly a hand-wavy argument. Additionally, I don't see how this assumption is justified. Formally describing the set of invariances we expect natural data to have or even building models that are perfectly encoding these invariances by design is a very challenging problem that is unlikely to have a definite solution. Also, is it natural to expect that for each test input we will have a training input that is close to L2 norm to some transformation of the test input?
Another major issue is that the value of delta_x (the L2 distance around training point x  where the model assigns high confidence) is never discussed. This value is _very_ small for standard NN classifiers (this is what causes adversarial examples in the first place!). How do we expect models to deal with this issue? 
The experimental results of the paper are essentially for a toy setting. The dataset considered ("ManifoldMNIST") is essentially synthetic with access to the ground-truth probability of each sample. Moreover, the results on real datasets are unreliable. When evaluating the robustness of a model utilizing dropout, using a single gradient estimation query is not enough. Since the model is randomized, it is necessary to estimate the gradient using multiple queries. By using first-order attacks on these more reliable gradient estimates, an adversary can completely bypass a dropout "defense" (https://arxiv.org/abs/1802.00420).
Overall, I find the contributions of the paper limited both technically and conceptually. I thus recommend rejection.
[UPDATE]: Given the discussion with the authors, I agree that the paper outlines a potentially interesting research direction. As such, I have increased my score from 3 to 5 (and updated the review title). I still do not find the contribution of the paper significant enough to cross the ICLR bar.
Comments to the authors:
-- You cite certain detention methods for adversarial examples (Grosse et al. (2017), Feinman et al. (2017)) that have been shown to be ineffective (that is they can be bypassed by an adaptive attacker) by Carlini and Wagner (https://arxiv.org/abs/1705.07263)
-- The organization of the paper could be improved. I didn't understand what the main contribution was until reading Theorem 1 (this is 6 pages into the paper). The introduction is fairly vague about your contributions. You should consider moving related work later in the paper (most of the discussion there is not directly related to your approach) and potentially shortening your background section.
-- How is the discussion about Gaussian Processes connected with your results?
-- Consider making the two conditions more prominent in the text.
-- In Definition 5, the wording is confusing "We define an idealized BNN to be a Bayesian idealized NN..."