We study the problem of designing provably optimal adversarial noise algorithms that induce misclassification in settings where a learner aggregates decisions from multiple classifiers. Given the demonstrated vulnerability of state-of-the-art models to adversarial examples, recent efforts within the field of robust machine learning have focused on the use of ensemble classifiers as a way of boosting the robustness of individual models. In this paper, we design provably optimal attacks against a set of classifiers. We demonstrate how this problem can be framed as finding strategies at equilibrium in a two player, zero sum game between a learner and an adversary and consequently illustrate the need for randomization in adversarial attacks. The main technical challenge we consider is the design of best response oracles that can be implemented in a Multiplicative Weight Updates framework to find equilibrium strategies in the zero-sum game. We develop a series of scalable noise generation algorithms for deep neural networks, and show that it outperforms state-of-the-art attacks on various image classification tasks. Although there are generally no guarantees for deep learning, we show this is a well-principled approach in that it is provably optimal for linear classifiers. The main insight is a geometric characterization of the decision space that reduces the problem of designing best response oracles to minimizing a quadratic function over a set of convex polytopes.
The paper studies the problem of adversarial examples generation. The authors phrase the following problem: given a set of models  C, we want to find an adversarial perturbation that maximizes the loss on an ensemble of models. However, the ensemble weights are chosen by the learner. In the case that we have one example, this is equivalent to asking that the same adversarial perturbation (or distribution over perturbations) fools all the individual models in my collection. This is a reasonable phrasing of the problem, though it seems different from versions studied in literature. In particular, previous works used uniform ensembles.
More generally, the authors consider a set of m examples, and the adversarial player now looks for a (distribution over) perturbations for each of the n examples. The learner player selects mixing weights to minimize the error rate. This is an interesting formulation of the problem: in particular, tying the mixing weights used for all examples is a non-intuitive change and does not have the clean interpretation above any more.
This notion of allowing mixing weights on the learner is a change from previous work. The authors would do well to explain why this formulation is chosen and what the interpretation is. It corresponds to a specific attack model where the learner and the adversary make choices in a very specific order, and could use further explanation on when this a reasonable attack model. Note that previous work looked at the setting of all weights being equal, and one natural variant is to allow a set of mixing weights per example, which would correspond to finding a perturbation (or distribution over perturbations) for this example that fool all models in the set C. The version studied here is left unexplained in the current work.
The authors then argue that we can solve this game by playing MW vs. best response. They propose using best response on the adversarial player. This player is then trying to find the perturbation that maximizes the p-weighted sum of the 0-1 (or rather surrogate) losses, where p represents the mixing weights on C. The authors show that in the convex case, if there is a pure NE, then the best response can be found: in this case we get a convex problem. They study the convex case a bit more, showing that there is at most an exponential number of values for the 0-1 loss, since a {0,1} vector defining which side of each classifier in C x falls in fully defines the loss at x. 
Finally, the authors move to the non-convex case where the experiments are done. The authors report interesting results on imagenet and for mnist for the convex case. I had some trouble understanding the imagenet results. For one, it seems fishy that their Madry et al. attack is worse than the FGM for many of the models and suggests strongly that the parameters for the Madry attack were not properly tuned. It is hard to know since the paper does not report on various parameters for these attacks. Second, these attacks are designed for l_infty and modifying them for l_2 would be necessary for a fair comparison. Finally, I am not sure why the authors do not compare to the Carlini and Wagner attacks on Imagenet, which is actually an l2 attack and makes the accuracy 0 at a slightly larger perturbation radius. Also, the authors would do well to emphasize that for larger perturbation radii, there are attacks which make the accuracy zero, and the contribution here seems to be look at smaller radii.
My primary concern with the work is that it is not clear to me how the specific two player game is motivated. The authors do not justify why it makes sense to allow weights on the ensemble, and also why these weights need to be tied together across examples. For a paper that makes strong claims about its approach being principled, this is a serious shortcoming in my view. Secondarily, the experiments section leaves me worried that the comparison is with improperly tuned versions of previous work. I would therefore not be in favor of accepting this paper.
Comments:
pg 1 : "One of the most pressing ..." : that is perhaps an unnecessary exaggeration.
pg 2: The name "NSFW" is an unfortunate choice, is completely non-informative about the contribution and I strongly recommend the authors reconsider it.
- As far as I can tell, Tramer et al. do not build an ensemble model at all; the ensemble word there refers to an ensemble of adversarial perturbations.
- The hinge loss is actually not smooth. However, I don't quite see why you need smoothness there.