Not many, but there are several approximations made in the derivation. Also the strong assumptions of convexity and norm-based defense were made.
Qualitative evaluation Quality:
The paper is technically sound for the most part, except for severals approximation steps that perhaps needs more precise descriptions. Experiments seem to support the claims well. Literature review is broad and relevant. Clarity:
The paper is written and organized very well. Perhaps the sections on data-dependent defenses are a bit complex to follow. Originality:
While the components such as online learning by regret minimization and minimax duality may be well-known, the paper uses them in the context of poisoning attack to find a (approximate) solution/certificate for norm-based defense, which is original as far as I know. Significance:
The problem addressed in the paper has been gaining importance, and the paper presents a clean analysis and experiments on computing an approximate upperbound on the risk, assuming a convex loss and/or a norm-based defense.
Detailed comments
I didn't find too many things to complain. To nitpick, there are two concerns about the paper.
1. The authors introduce several approximations (i -iii) which leaves loose ends. It is understandable that approximations are necessary to derive clean results, but the possible vulnerability (e.g., due to the assumption of attacks being in the feasible set only in lines 107-110) needs to be expanded to reassure the readers that it is not a real concern.
2. Secondly, what relevance does the framework have with problems of non-convex losses and/or non-norm type defenses? Would the non-vanishing duality gap and the difficulty of maximization over non-norm type constraints make the algorithm irrelevant? Or would it still give some intuitions on the risk upperbound?
p.3, binary classification: If the true mean is known through an oracle, can one use the covariance or any other statistics to design a better defense?
1. The authors introduce several approximations (i -iii) which leaves loose ends. It is understandable that approximations are necessary to derive clean results, but the possible vulnerability (e.g., due to the assumption of attacks being in the feasible set only in lines 107-110) needs to be expanded to reassure the readers that it is not a real concern.