Year: 2018

Abstract:
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.

text: 1 INTRODUCTION
In this paper, we study adversarial attacks that induce misclassification when a learner has access to multiple classifiers. One of the most pressing concerns within the field of AI has been the welldemonstrated sensitivity of machine learning algorithms to noise and their general instability. Seminal work by (Szegedy et al., 2014) has shown that adversarial attacks that produce small perturbations can cause data points to be misclassified by state-of-the-art models, including neural networks. In order to evaluate classifiers’ robustness and improve their training, adversarial attacks have become a central focus in machine learning and security (Moosavi-Dezfooli et al., 2016; Koh & Liang, 2017; Liu et al., 2017; Nguyen et al., 2015).
Adversarial attacks induce misclassification by perturbing data points past the decision boundary of a particular class. In the case of binary linear classifiers, for example, the optimal perturbation is to push points in the direction perpendicular to the separating hyperplane. For non-linear models there is no general characterization of an optimal perturbation, though attacks designed for linear classifiers tend to generalize well to deep neural networks (Moosavi-Dezfooli et al., 2016).
Since a learner may aggregate decisions using multiple classifiers, a recent line of work has focused on designing attacks on an ensemble of different classifiers (Liu et al., 2017; Tramer et al., 2018; Abbasi & Gagné, 2017; He et al., 2017). In particular, this line of work shows that an entire set of state-of-the-art classifiers can be fooled by using an adversarial attack on an ensemble classifier that averages the decisions of the classifiers in that set. Given that attacking an entire set of classifiers is possible, the natural question is then:
What is the most effective approach to design attacks on a set of multiple classifiers?
The main challenge when considering attacks on multiple classifiers is that fooling a single model, or even the ensemble classifier (i.e. the model that classifies a data point by averaging individual predictions), provides no guarantees that the learner will fail to classify correctly. Models may have different decision boundaries, and perturbations that affect one may be ineffective on another. Furthermore, a learner can randomize over classifiers and avoid deterministic attacks (see Figure 1).
In this paper, we present a principled approach for attacking a set of classifiers which proves to be highly effective. We show that constructing optimal adversarial attacks against multiple classifiers is equivalent to finding strategies at equilibrium in a zero sum game between a learner and an adversary. It is well known that strategies at equilibrium in a zero sum game can be obtained by applying the celebrated Multiplicative Weights Update framework, given an oracle that computes a best response to a randomized strategy. The main technical challenge we address pertains to the characterization and implementation of such oracles. Our main contributions can be summarized as follows:
• We describe the Noise Synthesis FrameWork (henceforth NSFW) for generating adversarial attacks. This framework reduces the problem of designing optimal adversarial attacks for a general set of classifiers to constructing a best response oracle in a two player, zero sum game between a learner and an adversary;
• We show that NSFW is an effective approach for designing adversarial noise that fools neural networks. In particular, applying projected gradient descent on an appropriately chosen loss function as a proxy for a best response oracle achieves performance that significantly improves upon current state-of-the-art attacks (see results in Figure 2);
• We show that applying projected gradient descent on an appropriately chosen loss function is a well-principled approach. We do so by proving that for linear classifiers such an approach yields an optimal adversarial attack if the equivalent game has a pure Nash equilibrium. This result is shown via a geometric characterization of the decision boundary space which reduces the problem of designing optimal attacks to a convex program;
• If the game does not have a pure Nash equilibrium, there is an algorithm for finding an optimal adversarial attack for linear classifiers whose runtime is exponential in the number of classifiers. We show that finding an optimal strategy in this case is NP-hard.
Paper organization. Following a discussion on related work, in Section 2 we formulate the problem of designing optimal adversarial noise and show how it can be modeled as finding strategies at equilibrium in a two player, zero sum game. Afterwards, we discuss our approach for finding such strategies using MWU and proxies for best response oracles. In Section 2 .1, we justify our approach by proving guarantees for linear classifiers. Lastly, in Section 3, we present our experiments.
Additional related work. The field of adversarial attacks on machine learning classifiers has recently received widespread attention from a variety of perspectives (Carlini & Wagner, 2018; Athalye et al., 2018; Elsayed et al., 2018; Papernot et al., 2016b; Schmidt et al., 2018; Bubeck et al., 2018; Madry et al., 2018). In particular, a significant amount of effort has been devoted to computing adversarial examples that induce misclassification across multiple models (Moosavi-Dezfooli et al., 2017; Szegedy et al., 2014; Moosavi-Dezfooli et al., 2016). There has been compelling evidence which empirically demonstrates the effectiveness of ensembles as way of both generating and defending against adversarial attacks. For example, Tramer et al. (2018) establish the strengths of ensemble training as a defense against adversarial attacks. Conversely, Liu et al. (2017) provide the first set of experiments showing that attacking an ensemble classifier is an effective way of generating adversarial examples that transfer to the underlying models. Relative to their investigation, our work differs in certain key aspects. Rather than analyzing adversarial noise from a security perspective and developing methods for black-box attacks, we approach the problem from a theoretical point of view and introduce a formal characterization of the optimal attack against a set of classifiers. Furthermore, by analyzing noise in the linear setting, we design algorithms for this task that have strong guarantees of performance. Through our experiments, we demonstrate how these algorithms motivate a natural extension for noise in deep learning that achieves state-of-the-art results.
2 A FRAMEWORK FOR OPTIMAL ADVERSARIAL ATTACKS
Given a set of point-label pairs {(xi, yi)}mi=1 where (xi, yi) ∈ Rd × [k], a deterministic adversarial attack is a totally ordered set of noise vectors, V = (v1, . . . , vm) ∈ Rd×m. We say that q is an adversarial attack if q is a distribution over sets of noise vectors. An adversarial attack q is αbounded if for all sets V that have non-zero probability under q, each individual noise vector vi ∈ V has bounded norm, e.g ||vi||p ≤ α. We focus on the case where each vector vi is bounded to have ℓ2 norm less than a fixed value α, however, our model can be easily extended to a variety of norms.1
For a given classifier c : Rd → [k], a realization of the adversarial attack, V = (v1, . . . , vm), induces misclassification on (xj , yj) if c(xj + vj) ∕= yj . Given a finite set of classifiers C and a data set S = {(xi, yi)}mi=1 of point-label pairs as above, an optimal adversarial attack is a distribution q over sets of noise vectors that maximizes the minimum 0-1 loss of the classifiers in C:
argmax q min c∈C
1
m

j∈[m] E V∼q [ℓ0-1(c, xj + vj , yj)] (1)
Optimal adversarial attacks are equilibrium strategies in a zero sum game. An equivalent interpretation of the optimization problem described in Equation (1) is that of a best response in a two player, zero sum game played between a learner and an adversary. When the learner plays classifier c ∈ C and the adversary plays an attack V , the payoff to the adversary is M(c, V ) = 1 m  j∈[m] ℓ0-1(c, xj + vj , yj), which is the average 0-1 loss of the learner.
2 The learner and the adversary can choose to play randomized strategies p,q over classifiers and noise vectors yielding expected payout E(c,V )∼(p,q) M(c, V ). The (mixed) equilibrium strategy of the game is the pair of distributions p,q that maximize the minimum loss maxq minp E(c,V )∼(p,q) M(c, V ).
Computing optimal adversarial attacks via MWU. As discussed above, the optimization problem of designing optimal adversarial attacks reduces to that of finding strategies at equilibrium in a zero sum game. It is well known that the celebrated Multiplicative Weight Updates algorithm can be used to efficiently compute equilibrium strategies of zero sum games when equipped with a best response oracle that finds an optimal set of perturbations for any strategy chosen by the learner:
BEST RESPONSE(p,α) def = argmax
V ∈Rd×m E c∼p [M(c, V )]; s.t ||vi||2 ≤ α ∀vi ∈ V (2)
Our framework for generating adversarial noise applies the Multiplicative Weight Updates algorithm as specified in Algorithm 1. The algorithm returns distributions p,q that are within δ of the equilibrium value of the game λ = minp maxq E(c,V )∼(p,q)[M(c, V )] by using T ∈ O( lnnδ2 ) calls to a best response oracle.3 In this work, we focus on developing attacks on neural networks and linear models. Yet, our framework is general enough to generate optimal attacks for any domain in which one can approximate a best response. We analyze the convergence of NSFW in Appendix G.
Approximating a best response. Given the framework described above, the main challenge is in computing a best response strategy. To do so, at every iteration, as a proxy for a best response, we apply projected gradient descent (PGD) to an appropriately chosen surrogate loss function. In particular, given C = {ci}ni=1 for every (x, y) ∈ Rd × [k] we aim to solve:
max v
n
i=1
p[i]ℓ(ci, x+ v, y) (3)
ℓ is a loss function that depends on the type of attack (targeted vs. untargeted) and the type of classifiers in C (linear vs. deep). We introduce a series of alternatives for ℓ in the following section. As we will now show, maximizing the loss of the learner by applying PGD to a weighted sum of loss functions is a well-principled approach to computing best responses as it is guaranteed to converge to the optimal solution in the case where C is composed of linear classifiers. While there are generally no guarantees for solving non-convex optimization problems of this sort for deep neural networks, in Section 3 , we demonstrate the effectiveness of our approach by showing that it experimentally improves upon current state-of-the-art attacks.
1For example, see Appendix H for extensions to the ℓ∞ norm. 2The adversary plays the role of the max player in our two player, zero sum game. 3In our experiments in Section 3, we show that the algorithm converges in a far fewer number of iterations.
Algorithm 1 Noise Synthesis FrameWork (NSFW) Input: Classifiers C = {c1, . . . , cn}, data points {(xi, yi)}mi=1, parameters α, T initialize p1 = ( 1n , . . . , 1 n );  =  ln |C|/T
for t = 1 to T do Set Vt = BEST RESPONSE(pt,α) Set pt+1[i] ∝ pt[i](1− )M(ci,Vt) for every i ∈ [n] end for Return: uniform distributions p,q over p1, . . . ,pT ; V1, . . . , VT
2 .1 PROVABLE GUARANTEES FOR COMPUTING OPTIMAL NOISE
The main theoretical insight that leads to provable guarantees for generating adversarial noise is a geometric characterization of the underlying structure of adversarial attacks. Regardless of the type of model, selecting a distribution over classifiers partitions the input space into disjoint regions, each of which is associated with a single loss value for the learner. Given a distribution over classifiers played by the learner, computing a best response strategy for the adversary then reduces to a search problem. In this problem, the search is for points in each region that lie within the noise budget and can be misclassified. The best response is to select the region which induces the maximal loss.
In the case of linear classifiers, the key observation is that the regions are convex. As a result, designing optimal adversarial attacks reduces to solving a series of quadratic programs. Lemma 1. Selecting a distribution p over a set C of n linear classifiers, partitions the input space Rd into kn disjoint, convex sets Tj such that:
1. For each Tj , there exists a unique label vector sj ∈ [k]n such that for all x ∈ Tj and ci ∈ C, ci(x) = sj,i, where sj,i is a particular label in [k].
2. There exists a finite set of numbers a1, . . . akn , not necessarily all unique, such thatn i=1 p[i]ℓ0-1(ci, x, y) = aj for a fixed y and all x ∈ Tj 3. Rd \ 
j Tj is a set of measure zero.
Proof Sketch (see full proof in Appendix C). Each set Tj is defined according to the predictions of the classifiers ci ∈ C on points x ∈ Tj . In particular, each region Tj is associated with a unique label vector sj ∈ [k]n s.t ci(x) = sj,i for all ci ∈ C. Since the prediction of each classifier is the same for all points in a particular region, the loss of the learner  i∈[n] p[i]ℓ0-1(ci, x, y) is constant over the entire region. Convexity then follows by showing that each Tj is an intersection of hyperplanes. This characterization of the underlying geometry now allows us to design best response oracles for linear classifiers via convex optimization. For our analysis, we focus on the case where C consists of “one-vs-all” classifiers. In the appendix, we show how our results can be generalized to other methods for multilabel classification by reducing these other approaches to the “one-vs-all” case. Given k classes, a “one-vs-all” classifier ci consists of k linear functions ci,j(x) = 〈wi,j , x〉 + bi,j where j ∈ [k]. On input x, predictions are made according to the rule ci(x) = argmaxj ci,j(x). Lemma 2. For linear classifiers, implementing a best response oracle reduces to the problem of minimizing a quadratic function over a set of kn convex polytopes.
Proof Sketch (see full proof in Appendix C). The main idea behind this lemma is that given a distribution over classifiers, the loss of the learner can be maximized individually for each point (x, y) ∈ S. Furthermore, by Lemma 1, the loss can assume only finitely many values, each of which is associated with a particular convex region Tj of the input space. Therefore, to compute a best response, we can iterate over all regions and choose the one associated with the highest loss. To find points in each region Tj , we can simply minimize the ℓ2 norm of a perturbation v such that x+ v ∈ Tj , which can be framed as minimizing a quadratic function over a convex set. These results give an important characterization, but it also shows that the number of polytopes is exponential in the number of classifiers. To overcome this difficulty, we demonstrate how when there exists a pure strategy Nash equilibrium (PSNE), that is a single set of noise vectors V where every vector is bounded by α and minci∈C M(ci, V ) = 1, PGD applied to the reverse hinge loss, ℓr, is
guaranteed to converge to a point that achieves this maximum for binary classifiers. More generally, given a label vector sj ∈ [k]n , PGD applied to the targeted reverse hinge loss, ℓt, converges to a point within the noise budget that lies within the specified set Tj . We define ℓr and ℓt as follows:
ℓr(ci, x, y) def =  y(〈wi, x〉+ bi) + ; ℓt(ci, x, j) def =  max l ∕=j ci,l(x)− ci,j +
(4)
The proof follows standard arguments for convergence of convex and β-smooth functions. Theorem 1. Given any precision  > 0 and noise budget α > 0:
• For a finite set of linear binary classifiers C and a point (x, y), running PGD for T = 4α/ iterations on the objective f(v) = n i=i p[i]ℓr(ci, x + v, y) converges to a point that is
within  of the pure strategy Nash equilibrium f(x+ v∗), if such an equilibrium exists;
• For a finite set of linear multilabel classifiers C, given a label vector sj ∈ [k]n and a distribution p over C, running PGD for T = 4α/ iterations on the objective f(v) =n
i=i p[i]ℓt(ci, x+v, sj,i) converges to a point x+v (T ) such that f(x+v(T ))−f(x+v∗) ≤
 where x+ v∗ ∈ Tj and ||v∗||2 ≤ α, if such a point exists.
Proof Sketch. From the definition of the reverse hinge loss, we see that ℓr(ci, x′, y) = 0 if and only if ℓ0-1(ci, x′, y) = 1. Similarly, the targeted loss ℓt(ci, x′, j) is 0 if and only if ci predicts x′ to have label j. For linear classifiers, both of these functions are convex and β-smooth. Hence PGD converges to a global minimum, which is zero if there exists a pure equilibrium in the game.
The requirement that there exist a feasible point x′ within Tj is not only sufficient, it is also necessary in order to avoid a brute force search. Designing an efficient algorithm to find the region associated with the highest loss is unlikely as the decision version of the problem is NP-hard even for binary linear classifiers. We state the theorem below and defer the proof to the appendix. Theorem 2. Given a set C of n binary, linear classifiers, a number B, a point (x, y), noise budget α, and a distribution p, finding v with ||v||2 ≤ α s.t. the loss of the learner is exactly B is NP-complete.
As we show in the following section, this hardness result does not limit our ability to compute optimal adversarial examples. Most of the problems that have been examined in the context of adversarial noise suppose that the learner has access only to a small number of classifiers (e.g less than 5) (Liu et al., 2017; Dong et al., 2017; Abbasi & Gagné, 2017; Tramer et al., 2018; He et al., 2017). In such cases we can solve the convex program over all regions and find an optimal adversarial attack, even when a pure Nash equilibrium does not exist.
3 EXPERIMENTS
We evaluate the performance of NSFW at fooling a set of classifiers by comparing against noise generated by using state-of-the-art attacks against an ensemble classifier. Recent work by Liu et al. (2017) and Tramer et al. (2018), demonstrates how attacking an ensemble of a set of classifiers generates noise that improves upon all previous attempts at fooling multiple classifiers. We test our methods on deep neural networks on MNIST and ImageNet, as well as on linear classifiers where we know that NSFW is guaranteed to converge to the optimal adversarial attack.
3 .1 EVALUATING NSFW ON DEEP NEURAL NETWORKS
We use the insights derived from our theoretical analysis of linear models to approximate a best response oracle for this new setting. Specifically, at each iteration of NSFW we compute a best response as in Equation (3) by running PGD on a weighted sum of untargeted reverse hinge losses, ℓut, introduced in this domain by Carlini & Wagner (2017). Given a network ci, we denote ci,j(x) to be the probability assigned by the model to input x belonging to class j (the jth output of the softmax layer of the model).
ℓut(ci, x, y) def =  ci,y(x)−max
j ∕=y ci,j(x)
+ (5)
For MNIST, the set of classifiers C consists of 5 convolutional neural networks, each with a different architecture, that we train on the full training set of 55k images (see Appendix for details). All classifiers (models) were over 97% accurate on the MNIST test set. For ImageNet, C consists of the InceptionV3, DenseNet121, ResNet50, VGG16, and Xception models with pre-trained weights
downloaded from the Keras repository (Chollet et al., 2015; He et al., 2016; Simonyan & Zisserman, 2014; Chollet, 2017; Szegedy et al., 2016; Huang et al., 2017).4
To evaluate the merits of our approach, we compare our results against attacks on the ensemble composed of C as suggested by Liu et al. (2017). More specifically, we create an ensemble by averaging the outputs of the softmax layers of the different networks using equal weights. We generate baseline attacks by attacking the ensemble using (1) the Fast Gradient Method by Goodfellow et al. (2014), (2) the Projected Gradient Method by Madry et al. (2018), and (3) the Momentum Iterative Method by Dong et al. (2017) which we download from the Cleverhans library (Papernot et al., 2016a).5
We select the noise budget α by comparing against the average ℓ2 distortion reported by similar papers in the field. For MNIST, we base ourselves off the values reported by Carlini & Wagner (2017) and choose a noise budget of 3.0. For ImageNet, we compare against Liu et al. (2017). In their paper, they run similar untargeted experiments on ImageNet with 100 images and report a noise budget of 22 when measured as the root mean squared deviation. Converted to the ℓ2 norm, this corresponds to α ≥ 8500. 6 We found this noise budget to be excessive, yielding images comparable to those in the leftmost column in Figure 2. Therefore, we chose α = 300 (roughly 3.5% of the total distortion used in Liu et al. (2017)) which ensures that the perturbed images are visually indistinguishable from the originals to the human eye (see rightmost column in Figure 2).
4Specific details regarding model architectures as well as the code for all our experiments can be found in our repository which will be made public after the review period in order to comply with anonymity guidelines. The test set accuracies of all ImageNet classifiers are displayed on the Keras website.
5Momentum Iterative Method won the 2017 NIPS adversarial attacks competition (Kurakin et al., 2018). 6In their paper, Liu et al. (2017) define the root mean squared deviation of two points x, x as (xi − xi )2/N where N is the dimension of x. For ImageNet, our images are of dimension 224×224×3, while for MNIST they are of size 28 × 28 × 1. For further perspective, if we convert our noise budgets from the ℓ2 norm to RMSD, our budgets would correspond to .77 and .11 for ImageNet and MNIST respectively.
For our experiments, we ran NSFW for 50 MWU iterations on MNIST models and for 10 iterations on ImageNet classifiers. We use far fewer iterations than the theoretical bound since we found that in practice NSFW converges to the equilibrium solution in only a small number of iterations (see Figure 5 in Appendix A). At each iteration of the MWU we approximate a best response as described in Equation 3 by running PGD using the Adam optimizer (Kingma & Ba, 2014) on a sum of untargeted reverse hinge losses. Specifically, we run the optimizer for 5k iterations with a learning rate of .01. At each iteration, we clip images to lie in the range [0, 1] for MNIST and [0, 255.0] for ImageNet.7
Finally, for evaluation, for both MNIST and ImageNet we selected 100 images uniformly at random from the set of images in the test sets that were correctly classified by all models. In Table 1, we report the empirical accuracy of all classifiers in the set C when evaluated on NSFW as well as on the three baseline attacks. To compare their performance, we highlight the average and maximum accuracies of models in C when attacked using a particular noise solution. From Table 1, we see that on ImageNet our algorithm results in solutions that robustly optimize over the entire set of models using only a small amount of noise. The maximum accuracy of any classifier is 17% under NSFW, while the best ensemble attack yields a max accuracy of only 68%. If we wish to generate a similar level of performance from the ensemble baselines, we would need to increase the noise budget to 8000 for FGM and the Madry attack and to 2000 for the Momentum Iterative Method. We present a visual comparison of the different attacks under these noise budgets required to achieve accuracy of 17% in Figure 2. On MNIST, we find similar results. NSFW yields a max accuracy of 22.6% compared to the next best result of 48% generated by the Madry attack on the ensemble. We summarize the results for MNIST in Table 2 presented in Appendix A.
3 .2 WHY ARE DIRECT ATTACKS ON ENSEMBLE NETWORKS POOR NOISE GENERATORS? ANALYZING DIFFERENCES IN DECISION BOUNDARIES VIA CLASS SALIENCY MAPS
As seen in the previous section, noise generated by directly attacking an ensemble of classifiers significantly underperforms NSFW at robustly fooling the underlying models. In this section, we aim to understand this phenomenon by analyzing how the decision boundary of the ensemble model compares to that of the different networks. In particular, we visualize the class boundaries of convolutional neural networks using the algorithm proposed by Simonyan et al. (2013) for generating saliency maps.8 The class saliency map indicates which features (pixels) are most relevant in classifying an image to have a particular label. 9 Therefore, they serve as one way of understanding the decision boundary of a particular model by highlighting which dimensions carry the highest weight.
In Figure 3, we see that the class saliency maps for individual models exhibit significant diversity. The ensemble of all 5 classifiers appears to contain information from all models, however, certain regions that are of central importance for individual models are relatively less prominent in the ensemble saliency map. Compared to our approach which calculates individual gradients for classifiers in C, creating an ensemble classifier obfuscates key information regarding the decision boundary of individual models. We make this discussion rigorous by analyzing the linear case in Appendix B.
7Further discussion regarding experiment setup and hyperparameters may be found in Appendix A. 8We make use of the implementation found at https://github.com/experiencor/deep-viz-keras. 9If we let ci,j(x) be the jth output of the softmax layer of network ci, they define the image-specific class saliency as the derivative ∂ci,j(x)/∂x. In the case of multichannel images, the value per pixel is defined as the maximum across all channels so as to yield a single grayscale image.
3 .3 EXPERIMENTS ON LINEAR CLASSIFIERS
In addition to evaluating our approach on neural networks, we performed experiments with linear classifiers. Since we have a precise characterization of the optimal attack on a set of linear classifiers, we can rigorously analyze the performance of different methods in comparison to the optimum.
We train two sets of 5 linear SVM classifiers on MNIST, one for binary classification (digits 4 and 9) and another for multiclass (first 4 classes, MNIST 0-3). To ensure a diversity of models, we randomly zero out up to 75% of the dimensions of the training set for each classifier. Hence, each model operates on a random subset of features. All models achieve test accuracies of above 90%. For our experiments, we select 1k points from each dataset that are correctly classified by all models.
In order to better compare across different best response proxies, we further extend NSFW by incorporating the label iteration method as another heuristic to generate untargeted noise. Given a point (x, y), the iterative label method attempts to calculate a best response by running PGD on the targeted reverse hinge loss for every label j ∈ [k] \ {y} and choosing the attack associated with the minimal loss. Compared to the untargeted reverse hinge loss, it has the benefit of being convex.
As for deep learning classifiers, we compare our results to the noise generated by the optimal attack on an ensemble of models in C. Since the class of linear classifiers is convex, creating an equal weights ensemble by averaging the weight vectors results in just another linear classifier. We can compute the optimal attack by running the best response oracle described in Section 2 .1 for the special case where C consists of a single model and then scaling the noise to have norm equal to α. As seen in the leftmost plot in Figure 4, even for linear models there is a significant difference between the optimal attack and other approaches. Specifically, we observe an empirical gap between NSFW equipped with the best response oracle as described in Lemma 2 vs. NSFW with proxy best response oracles, e.g. the oracle that runs PGD on appropriately chosen loss functions.10 This difference in performance is consistent across a variety of noise budgets. Our main takeaway is that in theory and in practice, there is a significant benefit in applying appropriately designed best response oracles. Lastly, on the right in Figure 4, we illustrate how the adaptivity of MWU is in general necessary to compute optimal attacks. While for most cases, NSFW converges to the equilibrium solution almost immediately, if the set of classifiers is sufficiently diverse, running NSFW for a larger number of rounds drastically boosts the quality of the attack. (See Appendix A for details.) 4 CONCLUSION Designing adversarial attacks when a learner has access to multiple classifiers is a non-trivial problem. In this paper we introduced NSFW which is a principled approach that is provably optimal on linear classifiers and empirically effective on neural networks. The main technical crux is in designing best response oracles which we achieve through a geometrical characterization of the optimization landscape. We believe NSFW can generalize to domains beyond those in this paper.
10We present a similar figure for binary classifiers in the appendix.
REFERENCES Mahdieh Abbasi and Christian Gagné. Robustness to adversarial examples through an ensemble of
specialists. CoRR, abs/1702.06856, 2017. URL http://arxiv.org/abs/1702.06856.
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 274–283, 2018. URL http://proceedings.mlr.press/v80/ athalye18a.html.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):270, November 2015. ISSN 1935-8237. doi: 10.1561/2200000050. URL http://dx.doi.org/10.1561/2200000050.
Sébastien Bubeck, Eric Price, and Ilya P. Razenshteyn. Adversarial examples from computational constraints. CoRR, abs/1805.10204, 2018.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pp. 39–57, 2017. doi: 10.1109/SP.2017.49. URL https://doi.org/10.1109/SP.2017. 49.
Nicholas Carlini and David A. Wagner. Audio adversarial examples: Targeted attacks on speechto-text. In 2018 IEEE Security and Privacy Workshops, SP Workshops 2018, San Francisco, CA, USA, May 24, 2018, pp. 1–7, 2018. doi: 10.1109/SPW.2018.00009. URL https://doi. org/10.1109/SPW.2018.00009.
François Chollet et al. Keras. https://keras.io, 2015.
Franois Chollet. Xception: Deep learning with depthwise separable convolutions. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1800–1807, 2017.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Xiaolin Hu, and Jun Zhu. Discovering adversarial examples with momentum. CoRR, abs/1710.06081, 2017. URL http://arxiv.org/abs/ 1710.06081.
Gamaleldin Fathy Elsayed, Shreya Shankar, Brian Cheung, Nicolas Papernot, Alex Kurakin, Ian Goodfellow, and Jascha Sohl-dickstein. Adversarial examples that fool both computer vision and time-limited human. 2018. URL https://arxiv.org/pdf/1802.08195.pdf.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119–139, August 1997. ISSN 0022-0000. doi: 10.1006/jcss.1997.1504. URL http://dx.doi.org/10.1006/jcss.1997.1504.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. CoRR, abs/1412.6572, 2014. URL http://arxiv.org/abs/1412.6572.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770– 778, 2016.
Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defense: Ensembles of weak defenses are not strong. In 11th USENIX Workshop on Offensive Technologies, WOOT 2017, Vancouver, BC, Canada, August 14-15, 2017., 2017. URL https://www.usenix.org/conference/woot17/ workshop-program/presentation/he.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2261–2269, 2017.
Satyen Kale. Efficient algorithms using the multiplicative weights update method, January 2007. URL http://search.proquest.com/docview/304824121/.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2014. URL http://arxiv.org/abs/1412.6980.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 1885–1894, 2017. URL http://proceedings. mlr.press/v70/koh17a.html.
Alexey Kurakin, Ian J. Goodfellow, Samy Bengio, Yinpeng Dong, Fangzhou Liao, Ming Liang, Tianyu Pang, Jun Zhu, Xiaolin Hu, Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, Alan L. Yuille, Sangxia Huang, Yao Zhao, Yuzhe Zhao, Zhonglin Han, Junjiajia Long, Yerkebulan Berdibekov, Takuya Akiba, Seiya Tokui, and Motoki Abe. Adversarial attacks and defences competition. CoRR, abs/1804.00097, 2018. URL http://arxiv.org/abs/1804.00097.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. In Proceedings of 5th International Conference on Learning Representations, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=rJzIBfZAb.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In CVPR, pp. 2574–2582. IEEE Computer Society, 2016.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 86–94, 2017.
Anh Mai Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pp. 427–436, 2015. doi: 10. 1109/CVPR.2015.7298640. URL https://doi.org/10.1109/CVPR.2015.7298640.
Nicolas Papernot, Ian Goodfellow, Ryan Sheatsley, Reuben Feinman, and Patrick McDaniel. cleverhans v1.0.0: an adversarial machine learning library. arXiv preprint arXiv:1610.00768, 2016a.
Nicolas Papernot, Patrick D. McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. 2016 IEEE European Symposium on Security and Privacy, pp. 372–387, 2016b.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. CoRR, abs/1804.11285, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409.1556, 2014. URL http://arxiv.org/abs/1409.1556.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. CoRR, abs/1312.6034, 2013. URL http://arxiv.org/abs/1312.6034.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL http://arxiv.org/abs/1312.6199.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2818–2826, 2016.
Florian Tramer, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id= rkZvSe-RZ.

heading: Appendix: Supplementary Material
text: A ADDITIONAL EXPERIMENTS AND DETAILS ON EXPERIMENTAL SETUP
We now discuss further details regarding the setup of the experiments presented in Section 3 . In the case of deep learning, we set hyperparameters for of all the baseline attacks (Fast Gradient Method, Madry attack, and the Momentum Iterative Method) by analyzing the values reported in the original papers. When running the Projected Gradient Method by Madry et al., given a noise budget α, we run the algorithm for 40 iterations with a step size of α/40 × 1.25 so as to mimic the setup of the authors. In the case of the Momentum Iterative Method, we run the attack for 5 iterations with a decay factor µ = 1.0 and a step size of α/5 as specified in Dong et al. (2017). FGM has no hyperparameters other than the noise budget. For all methods, we clip solutions to lie within the desired pixel range and noise budget.
When comparing different algorithms to compute best responses for linear multiclass classifiers as described in Section 3 .3, we run the NSFW algorithm with α = .2k for k ∈ [5]. In the case of binary classifiers (Figure 6), we find that the margins are smaller, and hence run NSFW with α = .05 + .1k for k ∈ [5]. For each value of α and choice of noise function, we run NSFW for 50 iterations. The one exception is that, for the multiclass experiments with α equal to .2 or .4, we ran the best response oracle for only 20 iterations due to computational constraints. When optimizing the loss of the learner through gradient descent (e.g when using PGD on appropriately chosen loses), we set the number of iterations to 3k and the learning rate to .01.
We set up the weight adaptivity experiment described at the end of Section 3 .3 (rightmost plot of Figure 4) as follows. We train 5 linear binary SVM classifiers on our binary version of the MNIST dataset. For each classifier, we zero out 80% of the input dimensions so that each model has nonzero weights for a strictly different subset of features, thereby ensuring maximum diversity in the decision
boundaries across models. In order to generate noise, we select 500 points uniformly at random from the test set that were correctly classified by all modes. We then run NSFW equipped with the best response oracle described in Lemma 2 for 50 iterations with a noise budget of .4.
B WHY ATTACKING AN ENSEMBLE IS NOT OPTIMAL
In this section, we provide a brief theoretical justification as to why methods designed to attack an ensemble constructed by averaging individual models in a set of classifiers (e.g. Liu et al. (2017); Tramer et al. (2018); He et al. (2017); Abbasi & Gagné (2017)) do not yield optimal adversarial attacks against a learner who selects classifiers from this set.
Attacks on ensemble classifiers, as seen in Liu et al. (2017), typically consist of applying gradient based optimization to an ensemble model E(C,p) made up of classifiers C and ensemble weights p. For concreteness, consider the simplest case where C is composed of linear binary classifiers. To find adversarial examples, we run gradient descent on a loss function such as the reverse hinge loss that is 0 if and only if the perturbed example x′ = x+ v with true label y is misclassified by ci.
Assuming x′ is not yet misclassified by the ensemble, running SGD on the ensemble classifier with the reverse hinge loss function results in a gradient update step of ∇ℓr(E(C,p), x′, y) =  i p[i]wi. This is undesirable for two main reasons:
• First, the ensemble obscures valuable information about the underlying objective. If x′ is misclassified by a particular model ci but not the ensemble, ci still contributes p[i]wi to the resulting gradient and biases exploration away from promising regions of the search space;
• Second, fooling the ensemble does not guarantee that the noise will transfer across the underlying models. Assuming the true label y is -1 and that x′ is correctly classified by all models, ℓr(E(C,p), x′, y) = 0 if and only if there exists a subset of classifiers T ⊆ C such that
 ct∈T p[t](〈wt, x ′〉 + bt) > 0, p[j](  cj∈C\T 〈wj , x ′〉 + bj) < 0 and
ct∈T p[t](〈wt, x ′〉 + bt) > |p[j](  cj∈C\T 〈wj , x
′〉 + bj)|. Hence, the strength of an ensemble classifier is only as good as its weakest weighted majority.
C PROOF OF GEOMETRIC CHARACTERIZATION
Lemma 1. Selecting a distribution p over a set C of n linear classifiers, partitions the input space Rd into kn disjoint, convex sets Tj such that:
1. For each Tj , there exists a unique label vector sj ∈ [k]n such that for all x ∈ Tj and ci ∈ C, ci(x) = sj,i, where sj,i is a particular label in [k].
2. There exists a finite set of numbers a1, . . . akn , not necessarily all unique, such thatn i=1 p[i]ℓ0-1(ci, x, y) = aj for a fixed y and all x ∈ Tj 3. Rd \ 
j Tj is a set of measure zero.
Proof. Given a label vector sj , we define each Tj as the set of points x where ci(x) = sj,i for all i ∈ [n]. This establishes a bijection between the elements of [k]n and the sets Tj . All the Tj are pairwise disjoint since their corresponding label vectors in [k]n must differ in at least one index and by construction each classifier can only predict a single label for x ∈ Tj . To see that these sets are convex, consider points x1, x2 ∈ Tj and an arbitrary classifier ci ∈ C s.t. ci(x) = z for all x ∈ Tj . If we let x′ = γx1 + (1− γ)x2 where γ ∈ [0, 1] then the following holds for all j ∈ [k] where j ∕= z:
ci,z(x ′) = 〈wi,z, γx1+(1-γ)x2〉+bi,z = γ〈wi,z, x1〉+γbi,z+(1-γ)〈wi,z, x2〉+(1-γ)bi,z > γ〈wi,j , x1〉+γbi,j+(1-γ)〈wi,j , x2〉+(1-γ)bi,j = ci,j(x ′)
Furthermore, for each Tj , there exists a number aj ∈ R≥0 such that the expected loss of the learner i p[i] · l(ci, x, y) equals aj for all x ∈ Tj . Since the distribution p is fixed, the loss of the learner is uniquely determined by the correctness of the predictions of all the individual classifiers ci. Since these are the same for all points in Tj , the loss of the learner remains constant. Lastly, the set Rd \ 
i Ti is equal to the set of points x where there are ties for the maximum valued classifier. This set is a subset of the set of points K that lie at the intersection of two hyperplanes:
Rd \ 
i
Ti ⊂ {x|∃ ci,k, cj,l s.t ci,k(x) = cj,l(x)} (6)
Finally, we argue that K has measure zero. For all ε > 0, x ∈ K, there exists an x′ such that ||x − x′||2 < ε and x′ /∈ K since the intersection of two distinct hyperplanes is of dimension two less than the overall space. Therefore, Rd \  i Ti must also have measure zero.
Lemma 2. For linear classifiers, implementing a best response oracle reduces to the problem of minimizing a quadratic function over a set of kn convex polytopes.
Proof. We outline the proof as follows. Given a distribution p over C, the loss of the learner 1 m m t=1 n i=i p[i]ℓ0-1(ci, xt + vt, yt) can be optimized individually for each vt since the terms in the sum are independent from one another. We leverage our results from Lemma 1 to demonstrate how we can frame the problem of finding the minimum perturbation vj such that x + vj ∈ Tj as the minimization of a convex function over a convex set. Since the loss of the learner is constant for points that lie in a particular set Tj , we can find the optimal solution by iterating over all sets Tj and selecting the perturbation with ℓ2 norm less than α that is associated with the highest loss. The best response oracle then follows by repeating the same process for each point (x, y).
Given a point (x, y) solving for the minimal perturbation v such that x + v ∈ Tj can be expressed as the minimization of a quadratic function subject to n(k − 1) linear inequalities.
min v∈Rd
||v||22
subject to c1(x+ v) = sj,1 . . . .
cn(x+ v) = sj,n
(7)
Each constraint in (7) can be expressed as k − 1 linear inequalities. For a particular z ∈ [k], ci ∈ C we write ci(x+ v) = z as ci,z(x+ v) > ci,l(x+ v) for all l ∕= z. Lastly, squaring the norm of the vector is a monotonic transformation and hence does not alter the underlying minimum.
D BEYOND “ONE-VS-ALL” LINEAR CLASSIFICATION
Here we extend the results from our analysis of linear classifiers to other methods for multilabel classification. In particular, we show that any “all-pairs” or multivector model can be converted to an equivalent “one-vs-all” classifier and hence all of our results also apply to these other approaches. All-Pairs. In the “all-pairs” approach, each linear classifier c consists of  k 2  linear predictors ci,j trained to predict between labels i, j ∈ [k]. As per convention, we let ci,j(x) = −cj,i(x). Labels are chosen according to the rule:
c(x) = argmax i∈[k]
 j ∕=i ci,j(x) (8)
Given an “all-pairs” classifier c, we show how it can be transformed into a “one-vs-all” classifier c′ such that c(x) = c′(x) for all x ∈ Rd.
c(x) = argmax i∈[k]
 j ∕=i ci,j(x)
= argmax i∈[k]
 j ∕=i 〈wi,j , x〉+ bi,j
= argmax i∈[k]
〈w′i, x〉+ b′i
= argmax i∈[k]
 j ∕=i c′i(x) = c ′(x)
Multivector. Lastly, we extend our results to multilabel classification done via class-sensitive feature mappings and the multivector construction by again reducing to the “one-vs-all” case. Given a function Ψ : Rd × [k] → Rn, labels are predicted according to the rule:
c(x) = argmax y∈[k]
〈w,Ψ(x, y)〉 (9)
While there are several choices for the Ψ, we focus on the most common, the multivector construction:
Ψ(x, y) = 
0, . . . , 0   ∈R(y−1)(d+1) , x1, . . . , xn, 1   ∈Rd+1 , 0, . . . , 0   ∈R(k−y)(d+1)
 (10)
w =  w1, . . . , wk  where wi ∈ Rd+1 ∀i (11)
This in effect ensures that (9) becomes equivalent to that of the “one-vs-all” approach:
c(x) = argmax i∈[k]
〈wi, x〉 (12)
E CONVERGENCE ANALYSIS OF PROJECTED GRADIENT DESCENT
Theorem 1. Given any precision  > 0 and noise budget α > 0:
• For a finite set of linear binary classifiers C and a point (x, y), running PGD for T = 4α/ iterations on the objective f(v) = n i=i p[i]ℓr(ci, x + v, y) converges to a point that is
within  of the pure strategy Nash equilibrium f(x+ v∗), if such an equilibrium exists;
• For a finite set of linear multilabel classifiers C, given a label vector sj ∈ [k]n and a distribution p over C, running PGD for T = 4α/ iterations on the objective f(v) =n
i=i p[i]ℓt(ci, x+v, sj,i) converges to a point x+v (T ) such that f(x+v(T ))−f(x+v∗) ≤
 where x+ v∗ ∈ Tj and ||v∗||2 ≤ α, if such a point exists.
Proof. We know that if a function f is convex and β-smooth, then running projected gradient descent over a convex set, results in the following rate of convergence, where v is the optimal solution and v(1) is the initial starting point (See Theorem 3.7 in Bubeck (2015)).
f(v(T ))− f(v) ≤ 3β||v (T ) − v||2 + f(v(1))− f(v)
T (13)
Given n classifiers, the objective is n
i=1 p[i]||wi||2 smooth:
f(v) =
n
i=i
p[i]ℓr(ci, x+ v, y)
=
n
i=i
p[i]  y(〈wi, x+ v〉+ bi) +
||∇f(v)||2 ≤ n
i=1
p[i]||wi||2
Furthermore, since v∗ is a pure strategy Nash equilibrium, f(v) = 0 and the maximum difference between f(v)− f(v), for any v, is bounded by:
f(v)− f(v) ≤ n
i=1
p[i]  y(〈wi, x+ v〉+ bi) + − 0
=
n
i=1
p[i]  y〈wi, v − v〉+ y(〈wi, x+ v〉+ bi) + (Convexity of Noise Budget)
≤ n
i=1
p[i]  y〈wi, v′〉) + y(〈wi, x+ v〉+ bi) < 0
≤ n
i=1
p[i]||wi||2||v′||2 (Cauchy-Schwartz)
≤ α n
i=1
p[i]||wi||2 (Noise Budget)
Since ||v(T ) − v||2 ≤ α, we have that:
f(v(T ))− f(v) ≤ 4α n
i=1 p[i]||wi||2 T
(14)
Lastly, we can normalize all the wi such that ||wi||2 = 1 without changing the predictions of the ci and arrive at our desired result.
For the multiclass case, we have that:
f(v) =
n
i=1
p[i]ℓt(ci, x+ v, sj,i)
=
n
i=1
p[i]  max l ∕=sj,i 〈wi,l, x+ v〉+ bi,l − (〈wi,sj,i , x+ v〉+ bi,sj,i) +
A similar bound follows by using the logic for the binary case. If we let v′ = v − v, we know that by our initial assumption, maxl ∕=sj,i〈wi,l, x + v〉 + bi,l − 〈wi,sj,i , x + v〉 − bi,sj,i < 0. We use this fact in the second line of the following argument.
f(v)− f(v∗) ≤ n
i=1
p[i]  max l ∕=sj,i 〈wi,l, x+ v〉+ bi,l − (〈wi,sj,i , x+ v〉+ bi,sj,i) + − 0
≤ n
i=1
p[i]  max l ∕=sj,i 〈wi,l, v′〉 − 〈wi,l, v′〉 
≤ α n
i=1
p[i] max l ∕=sj,i
||wi,l||2 (Cauchy-Schwartz, Noise Budget)
Using the fact that all weight vectors wi,j can be transformed to have ℓ2 norm equal to 1, we have that f(v)− f(v∗) ≤ α n i=1 p[i]. Lastly, we can check that ℓt is β-smooth with β = α n i=1 p[i], which yields the same bound as in the binary case.
F BEST RESPONSE ORACLE IS NP-COMPLETE
Theorem 2. Given a set C of n binary, linear classifiers, a number B, a point (x, y), noise budget α, and a distribution p, finding v with ||v||2 ≤ α s.t. the loss of the learner is exactly B is NP-complete.
Proof. We can certainly verify in polynomial time that a vector v induces a loss of B simply by calculating the 0-1 loss of each classifier. Therefore the problem is in NP.
To show hardness, we reduce from Subset Sum. Given n numbers p1, . . . pn and a target number B,11 we determine our input space to be Rn, the point x to be the origin, the label y = −1, and the noise budget α = 1. Next, we create n binary classifiers of the form ci(x) = 〈ei, x〉 where ei is the ith standard basis vector. We let pi be the probability with which the learner selects classifier ci.12
We claim that there is a subset that sums to B if and only if there exists a region Tj ⊂ Rn on which the learner achieves loss B. Given the parameters of the reduction, the loss of the learner is determined by the sum of the probability weights of classifiers ci such that ci(x + v) = +1 for points x+ v ∈ Tj . If we again identify sets Tj with sign vectors sj ∈ {±1}n as per Lemma 2, there is a bijection between the sets Tj and the power set of {p1, . . . , pn}. A number pi is in a subset Uj if the ith entry of sj is equal to +1.
Lastly, we can check that there are feasible points within each set Tj and hence that all subsets within the original Subset Sum instance are valid. Each Tj simply corresponds to a quadrant of Rn. For any ε > 0 and for any Tj , there exists a vj with ℓ2 norm less than ε such that x + vj ∈ Tj . Therefore, there is a subset Uj that sums to B if and only if there is a region Tj in which the learner achieves loss B.
11Without loss of generality, we can assume that instances of Subset Sum only have values in the range [0, 1]. We can reduce from the more general case by simply normalizing inputs to lie in this range.
12We can again normalize values so that they form a valid probability distribution.
G CONVERGENCE ANALYSIS OF THE NSFW ALGORITHM
To facilitate our analysis, we overload our notation of the payoff function M(c, V ) described in Section 2 to accept distributions p,q as input. We write M(p,q) to indicate E(c,V )∼(p,q) M(c, V ).
Theorem 3. Given an error parameter δ, after O( lnnδ2 ) iterations, Algorithm 1 returns distributions p, q such that:
min ci∈C
M(ci,q ) ≥ λ− δ
max V
M(p, V ) ≤ λ+ δ
where λ = min q max p M(p,q) is the equilibrium value of the game .
Proof. The following analysis draws heavily upon the work of Freund & Schapire (1997), yet the precise treatment follows that of Kale (2007).
By guarantees of the Multiplicative Weights algorithm, we have that for any distribution p over [n] with losses in [0, 1] the following relationship holds:
T
t=1
M(p(t), V (t)) ≤ (1 + ε) T
i=1
M(p, V (t)) + lnn
ε
If we divide by T , and note that M(p, V ) ≤ 1, and M(p(t), V (t)) ≥ λ for all t (due to oracle guarantees), we have that for any distribution p:
λ ≤ 1 T
T
i=1
M(p(t), V (t))
≤ 1 T
T
i=1
M(p, V (t)) + ε+ lnn
εT
If we let p̃ be the optimal strategy for the min player, then M(p̃, V ) ≤ λ for any V . Next, if we set  = δ2 and T = ⌈ 4 lnn δ2 ⌉ we get that:
λ ≤ 1 T
T
i=1
M(p(t), V (t))
≤ 1 T
T
i=1
M(p̃, V (t)) + δ
≤ λ + δ
Therefore p, the uniform distribution over p(1), . . . ,p(T ) is an approximately optimal solution for the learner.
For the adversary, we know from the previous equations that the following holds for any strategy p played by the learner:
λ ≤ 1 T
T
i=1
M(p(t), V (t)) ≤ 1 T
T
i=1
M(p, V (t)) + δ
If we set q to be the distribution that assigns weight |{t:V (t)=V }| T to the particular set of noise vectors V then we have that for any distribution p:
λ ≤ 1 T
T
i=1
M(p(t), V (t)) ≤ M(p,q) + δ
Hence q is an approximately optimal strategy for the adversary:
λ − δ ≤ M(p,q)
H EXTENSIONS TO ℓ∞ NORM
While we focus on the ℓ2 norm as the main metric with which to gauge the magnitude of adversarial noise, our results can be readily extended to function with the ℓ∞ norm. We begin by illustrating how to extend the best response oracle to use the ℓ∞ norm: Lemma 3. For linear classifiers, implementing a best response oracle under the ℓ∞ norm reduces to the problem of finding feasible points in a series of kn convex polytopes.
Proof. The proof is identical to that of Lemma 2. The only change we need to make is to slightly modify the optimization problem outlined in (7) to the following format. Given a label vector sj and a point (x, y) we solve for:
min v∈Rd
0
subject to ci(x+ v) = sj,i ∀i ∈ [k] vi ≤ α ∀i ∈ [d]
(15)
To generalize gradient methods, we can alter the projection step of gradient descent to constrain noise to the ℓ∞ ball. The solution space remains convex and hence our theoretical guarantees still hold.

Review summaries:
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.

This paper is concerned with the problem of finding adversarial examples for an ensemble of classifiers. This is formulated as the task of finding noise vectors that can be added to a set of examples in such a way that, for each example, the best ensemble element performs as badly as possible (i.e. it’s a maximin problem).