This paper considers label-flipping attacks, a type of data poisoning attack where an adversary relabels a small number of examples in a training set in order to degrade the performance of the resulting classifier. In this work, we propose a strategy to build linear classifiers based on deep features that are certifiably robust against a strong variant of label-flipping, where the adversary can target each test example independently. In other words, for each test point, our classifier makes a prediction and includes a certification that its prediction would be the same had some number of training labels been changed adversarially. Our approach leverages randomized smoothing, a technique that has previously been used to guarantee test-time robustness to adversarial manipulation of the input to a classifier. Further, we obtain these certified bounds with no additional runtime cost over standard classification. On the Dogfish binary classification task from ImageNet, in the face of an adversary who is allowed to flip 10 labels to individually target each test point, the baseline undefended classifier achieves no more than 29.3% accuracy; we obtain a classifier that maintains 64.2% certified accuracy against the same adversary. We generalize our results to the multi-class case, providing what we believe to be the first multi-class classification algorithm that is certifiably robust to label-flipping attacks.
Summary.
The paper investigates data poisoning type of attack. In such attacks, an adversary can alter/flip the labels of some of the training examples. The paper proposed a new approach towards certified robustness against this type of attack. In particular, the new classifier will output a prediction along with a certificate in which the prediction would not change if certain number of labels in the training data were flipped.
The authors use randomized smoothing on a binary linear classifier with logistic loss and deduce a radius of certification that is a function of the probability of flipping labels in the training data and the probabilistic separation p.
Major concerns.
1) I find the application of certification to data poisoning type adversarial attacks rather limited and is not of a major interest to the verification/certification community. Certification arose as a major issue since models implemented in practice can be fooled if subjected to noise at testing time. However, the proposed certification is on the flip rate of the labels in the training data. Since this is fixed, certification in this context is not of a major interest. The only potential relevance of such a problem is upon training models in a federated approach (online learning) even then, one can argue that the portion of the data that the adversary has access to is a small portion to the complete dataset. It feels to be that certification was somehow forced into data poisoning type of adversarial attacks although they jointly do not make much sense.
 While I do appreciate the work from authors, I am not convinced that certification in this context makes significant sense and has interest to only small group of researchers.
2) There are some serious limitation in the work specifically that the bounds are derived for a binary classifier. While the authors did indeed discuss the multi-class case, there are no experiments beyond the binary classification. The dataset sets where the sentiment analysis of IMDB, MNIST1/7 and the dog fish classes from ImageNet. Experiments on multi-class case is essential here for practical reasons.
3) May the authors clarify some few things in the experiments for me.
If I understand Figures 1,2,3 correctly, then what the authors do is that they train networks over different number of label flipping (shown as a percentage on the top of the figure). Then for each test example, they compute the maximum radius given in Eq 10 for multiple qs. If the number of flipping in the dataset is less than r (less than the maximum radius per sample) then the sample is certified.
	Question. I do not understand why is an example considered certifiable when it is both correctly classified and unaffected under at least r flips? In page 7 of the experiments section, the authors say "we plot the fraction of the test set that was both correctly classified and certified to not change under at least r flips".
	Question. Can the authors comment on the expected performance of the network upon comparing certified accuracy with networks having q as probability flip rate and when the training data flip rate percentage is exactly q. Will the certified accuracy for q that matches the flip rate in the dataset be better than the ones with q that does not match the training flip rate. For instance, in Figure 1, note that the percentage in the flip rate of the training dataset ranges from 0 to 14%, however the certified accuracy was for q that ranges from 30 to 47.5. Will the certified accuracy at a given percentage of the data be the highest for q that match the flip rate? 
	Question. Since the classifier is linear (since features are fixed), can the authors comment perhaps on the relation between p and q?

Minor comments.
1) The authors need to define what p is. The authors can correct me if I'm wrong, p is a lower bound on the separation of the probability for some class, i.e.  Prop(f(x) = 1) >= p. This is similar to Cohen et al. 19. This was not defined and come as a surprise in Eq 3.
2) Moreover, in the work of Cohen et al. the smoothed classifier g is smoothed in probability which is unlike definition 1. Perhaps definition 1 fits more the framework of Lecuyer et al 19 as they showed that if an algorithm A is differentially private (probability distribution do not change much under database perturbations), the expectation over the algorithm is also differentially private.
3) In the solution to the ridge regression, \alpha is a function of the tested sample, e.g. eq 11. This can be confusing and I advise authors to consider adding a superscript \alpha^j indicating that this is a function of the test sample j. Similarly, in the algorithm \alpha in Eq 7 and bullet point 1.
4) In example 3, the paper cited is a concurrent submission to ICLR20 and not 19.