A Spectral View of Adversarially Robust Features
Given the apparent difficulty of learning models that are robust to adversarial perturbations, we propose tackling the simpler problem of developing adversarially robust features. Specifically, given a dataset and metric of interest, the goal is to return a function (or multiple functions) that 1) is robust to adversarial perturbations, and 2) has significant variation across the datapoints. We establish strong connections between adversarially robust features and a natural spectral property of the geometry of the dataset and metric of interest. This connection can be leveraged to provide both robust features, and a lower bound on the robustness of any function that has significant variance across the dataset. Finally, we provide empirical evidence that the adversarially robust features given by this spectral approach can be fruitfully leveraged to learn a robust (and accurate) model.
The paper studies the very timely problem of feature robustness - it provides a new perspective on this problem with spectral approach. In particular, it wants to define functions that are robust to adversarial perturbations and vary across data points. Towards that goal, it shows connections between the spectral properties of the dataset, and the robustness of features.   Detailed comments:  - l.26: what are examples created in the real world? - l.48 why is it necessarily a good idea to disentangle the problems of accuracy, and robustness? any design that would try to address both simultaneously is necessarily bound to fail? - the notation for the distance metric,  is the same as the dimension of the input space - this is not ideal. - l.79 - why does the variance have to be close to 1 necessarily? - l.127 - the statement that there is no effort in trying to understand the geometry properties in the robustness problem is probably an overstatement (see the work of Alhussein Fawzi for example, as mentioned later) - the section between lines 166 and 175, contains quite a few notation problems, or imprecisions; it might be worth revising that part carefully. Also, it it not clear at this stage why the dataset is augmented with x? And does it mean that a new graph is built for each new x?  - at several places, the authors talk about suitable conditions for arguments or theorems (like in line 200 for example). These conditions should be clarified in the text - it would be a nice addition to have a sketch of the Th.2 in the main text. And actually, the discussion of Th.1 should come before Th 2 for better readability. - is there any constructive way to pick the correct threshold in lines 226-228? - the spectral view might appear as an overstatement in general - the authors mostly look at the Fiedler vector, and not at the full spectrum, in their analysis, and fonction construction. - the bounds defined by the authors, appear to be very loose, mostly because of the underlying assumptions: are they useful at all at the end? The authors should discuss in more details the relevance of the proposed bounds (esp. the lower one).  - Figure 2: this one is not very convincing: one can argue against the author’s statement that there is a clear (linear) relationship + outliers...  - recent works have studied the bounds on robustness, and relations to accuracy, e.g., the 2018 arxiv paper of Fawzi et al.. These works have to be discussed to provide a complete overview of the closely related literature, as they address some aspects of the key questions raised at l.38. - the are a few English typos, that should be corrected. E.g., lines 10,18, 133, 167 (index 0 misplaced), 169 (0 should be x_0??), 213, 336...  Overall, the paper takes an interesting, and new spectral perspective on robustness. They derive also new bounds, that could potentially bring interesting insights on the robustness problem. The classification function stays unfortunately trivial (and classical in graph-based problem), and is not learned or trained for the target task, as this was hinted in the introduction. As a result, the paper brings interesting insights, but fails to be completely convincing about the relevance of this theoretical study and its results. It could be accepted however, as it will probably trigger interesting discussions on a timely topic.