{'fraction_non_alphanumeric': 0.04774276266954585, 'fraction_numerical': 0.012720156555772993, 'mean_word_length': 3.9872118458690897, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Achieve Optimal Adversarial Accuracy for Adversarial Deep Learning using Stackelberg Game

Adversarial deep learning is to train robust DNNs against adversarial attacks, which is one of the major research focuses of deep learning. Game theory has been used to answer some of the basic questions about adversarial deep learning such as the existence of a classifier with optimal robustness and the existence of optimal adversarial samples for a given class of classifiers. In most previous work, adversarial deep learning was formulated as a simultaneous game and the strategy spaces are assumed to be certain probability distributions in order for the Nash equilibrium to exist. But, this assumption is not applicable to the practical situation. In this paper, we give answers to these basic questions for the practical case where the classifiers are DNNs with a given structure, by formulating the adversarial deep learning as sequential games. The existence of Stackelberg equilibria for these games are proved. Furthermore, it is shown that the equilibrium DNN has the largest adversarial accuracy among all DNNs with the same structure, when Carlini-Wagner's margin loss is used. Trade-off between robustness and accuracy in adversarial deep learning is also studied from game theoretical aspect.


Introduction
A major safety issue for deep learning [22] is the existence of adversarial samples [40], that is, it is possible to make little modifications to an input sample which are essentially imperceptible to the human eye, but the DNN outputs a wrong label or even any label given by the adversary. Existence of adversarial samples makes deep learning vulnerable in safety critical applications and adversarial deep learning has becomes a major research focus of deep learning [44]. The goal of adversarial deep learning is to train robust DNNs against adversarial attacks and well as developing more effective attack methods for generating adversarial samples.
Many adversarial defence models were proposed, including the adversarial training based on robust optimization [24,49], the gradient masking and obfuscation approaches [1,48], adversarial parameter attacks [41,23,47], universal adversaries [5,27], randomized smoothing [9], and the adversarial sample detection [7]. Many attack methods are also proposed, including the whitebox attacks based on gradient information of the DNN [6,24,30], the black-box attacks based on the transferability of the adversaries [31], the poisoning attacks for the input data [17,36], and the physical world attacks [21,2]. More details can be found in the survey [44].
Many of the defenses are found to be susceptible to new adversarial attacks, and stronger defences also are proposed against the new adversarial attacks. To break this loop of defences and attacks, a recent line of research based on game theory [14,38] tries to establish more rigourous foundation for adversarial deep learning by answering questions such as [5,8,25,32]: Question Q 1 : Does there exists a classifier which ensures optimal robustness against any adversarial attack?
Question Q 2 : Does there exist optimal adversarial samples for a given class of classifiers and a given set of data distribution?
To answer these questions, the adversarial deep learning was formulated as a simultaneous game between the Classifier and the Adversary. The goal of the Classifier is to train a robust DNN. The goal of the Adversary is to create optimal adversarial samples. A Nash equilibrium of the game is a DNN C * and an attack A * , such that no player can benefit by unilaterally changing its strategy and thus gives an optimal solution to the adversarial deep learning. Existence of Nash equilibria was proved under various assumptions [5,25,32].
Despite the grerat progresses, questions Q 1 and Q 2 are not answered satisfactorily. The main reason is that in order for the Nash equilibrium to exist, both the Classifier and the Adversary are either assumed to be a convex set of probability distributions or measurable functions. However, in practice, DNNs with fixed structures are used and Nash equilibria do not exist in this case. In this paper, we will show that questions Q 1 and Q 2 can be answered positively for DNNS with a fixed structure by formulating the adversarial deep learning as Stackelberg games.

Main contributions
A positive answer to question Q 1 is given by formulating the adversarial deep learning as a Stackelberg game G s with the Classifier as the leader and the Adversary as the follower, where the strategy space for the Classifier is a class of DNNs with a given structure, say DNNs with a fixed depth and width. We show that game G s has a Stackelberg equilibrium which gives the optimal robust DNN under certain robustness measurement (Refer to Theorem 3.5). We further show that when the Carlini-Wagner margin loss is used as the payoff function, the equilibrium DNN is the optimal defense which has the largest adversarial accuracy among all DNNs with the same structure (Refer to Theorem 4.4). Furthermore, the equilibrium DNN is the same as that of the adversarial training [24]. Thus, our results give another theoretical explanation for the fact that adversarial training is one of the most effective defences against adversarial attacks.
The trade-off property for deep learning means that there exists a trade-off between the robustness and accuracy [42,45,49]. We prove a trade-off result from game theoretical viewpoint. Precisely, we show that if a linear combination of the payoff functions of adversarial training and normal training is used as the total payoff function, then the equilibrium DNN has robustness not higher and accuracy no lower than that of the DNN obtained by adversarial training. We also show that trade-off property does not hold if using empirical loss to train the DNNs, that is, the DNNs with the largest adversarial accuracy can be parameterized by elements in an open set of R K , where K is the number of parameters, that is, there still exist rooms to improve the accuracy for DNNS with the optimal adversarial accuracy.
Finally, when using the empirical loss for a finite set of samples to train the DNN, we compare G s (denoted as G 1 in this case) with two other games: G 2 is the Stackelberg game with the Adversary as the leader and G 3 is the simultaneous game between the Classifier and the Adversary. We show that G 2 has a Stackelberg equilibrium and G 3 has a mixes strategy Nash equilibrium. Furthermore, the payoff functions of G 1 , G 2 , G 3 at their equilibria decrease successively. Existence of Stackelberg equilibrium for G 2 gives a positive answer to question Q 2 for DNNs with a given structure.

Related work
The game theoretical approach to adversarial machine learning was first studied in the seminal work of Dalvi, Domingos, Mausam, and Verma [11], where they formulated adversarial machine learning as a simultaneous game between the Classifier and the Adversary. Quite a number of work has been done along this line, by formulating adversarial machine learning both as a simultaneous game and as a Stackelberg game, which can be found in the nice surveys [50,20]. These works usually used linear models such as SVM for binary classifications, and used spam email filtering as the main application background.
Game theoretical approach to adversarial deep learning appeared recently and was partially stimulated by the fact that adversarial samples seem inevitable for deep learning [3,4,10,37]. The adversarial training was introduced in [24], which is one of the best practical training method to defend adversaries. In [32,5,16,25,29,18,34], the adversarial deep learning was all formulated as a simultaneous game. In [32], it was shown that the game exists no pure strategy Nash equilibrium, but mixed strategies give more robust classifiers. In [5], it was proved that Nash equilibrium exists when the strategy space for the Classifier is convex and the strategy space for the Adversary is certain probability distributions. In [16,25], it was proved that Nash equilibria exist and can be approximated by a pure strategy, when the strategy spaces for both the Classifier and Adversary are parameterized by distributions. In [29], the Classifier ensures the robustness of a fixed DNN by adding perturbation to the sample to counteract the Adversary. In [18,34], methods to compute mixed Nash equilibria were given. In [8], the adversarial deep learning was formulated as a Stackelberg game with the Adversary as the leader, but existence of equilibria was not given. In [13,19], properties and algorithms for local Stackelberg equilibria were studied. In above work, the adversarial deep learning is modeled as a non-cooperative game. In [35], the cooperative game is used to explain various adversarial attacks and defenses.
Most of the above work formulated adversarial deep learning as a simultaneous game and assume the strategy spaces to be certain convex probability distributions in order to prove the existence of the Nash equilibrium. In this paper, we show that by formulating the adversarial deep learning as a sequential game, Stackelberg equilibria exist for DNNs with a given structure, and the equilibrium DNN is the best defence in that it has the largest adversarial accuracy among all DNNs with the same structure.
The rest of this paper is organized as follows. In section 2, preliminary results are given. In section 3, the adversarial deep learning is formulated as a Stackelberg game and the existence of Stackelberg equilibria is proved. In section 4, it is proved that adversarial training with Carlini-Wagner loss gives the best adversarial accuracy. In section 5, two trade-off results are proved. In section 6, three types of adversarial games are compared when the data set is finite. In section 7, conclusions and problems for further study are given.

Adversarial training and robustness of DNN
Let C : X → R m be a classification DNN with m labels in Y = [m] = {1, . . . , m} [22]. Without loss of generality, we assume X = I n , where I = [0, 1]. Denote C l (x) ∈ R to be the l-th coordinate of C(x) for l ∈ [m], which are called logits of the DNN. For x ∈ X , the classification result of C is C(x) = argmax l∈Y C l (x). We assume that Relu is used as the activation function, so C is continuous and piecewise linear. The results are easily generated to any activation functions which are Lipschitz continuous.
To train a DNN, we need first to choose a hypothesis space H for the DNNs, say the set of CNNs or RNNs with certain fixed structure. In this paper, denote N W,D to be the set of DNNs with width W and depth D and use it as the hypothesis space. For a given hypothesis space H, the parameter set of DNNs in H is fixed and is denoted as Θ ∈ R K , where K is the number of the parameters. C can be written as C Θ if the parameters need to be mentioned explicitly, that is, Let the objects to be classified satisfy a distribution D over X × Y. Given a loss function L : R m × Y → R, the total loss for the data set is Training a DNN C Θ is to make the total loss minimum by solving the following optimization problem Θ * = argmin Θ∈R K ϕ 0 (Θ).
Given an attack radius ε ∈ R + , denote B(x, ε) = {x ∈ R n : ||x − x|| ≤ ε}. We use ∞ norm if not mentioned otherwise. We will find adversaries for x in B(x, ε). Precisely, x ∈ B(x, ε) is called an adversary of x with label y, if C(x) = y. In order to increase the robustness of a trained DNN, the adversarial training [24] is introduced which is to solve the following robust optimization problem Intuitively, the adversarial training is first computing a most-adversarial sample for x and then minimizing L(F(x a ), y) instead of L(F(x), y).
Given a DNN C and an attack radius ε, we define the adversarial robustness measure of C with respect to ε as follows which is the total loss of C at the most-adversarial samples. C is more robust if AR D (C, ε) is smaller. Then the adversarial training is to find a DNN in H with the optimal adversarial robustness measurement which is denoted as AR D (C, ε) and AR D (H, ε) have the following simple properties.
(3) In the optimal case, we have AR D (C, ε) = 0, which means that C gives the correct label for any x ∈ B(x, ε). In this case, we say that C is robust for the attack radius ε. It was proved that there exist robust classifiers for a separated data set [45].

Bounds and continuity of the DNN
Let C Θ : X → R m be a fully connected feed-forward DNN with depth D, whose l-th hidden layer is where is continuous on x and Θ, and [−ε, 1 + ε] n and [−E, E] n are compact. Ω(n, m, D, W, E, ε) can be derived from (7).
Thus C is Lipschitz on Θ and x.
Proof. Without loss of generality, let C be defined as in (7). Then C Θ (x) = Θ D (· · · σ(Θ 1 x) · · · ) with Θ to be the set of all weight matrices, that is, Θ = {Θ k |∀k ∈ [D] = {1, 2 · · · , D}} and σ is ReLU. The bias vectors are not considered, which can be included as parts of the weight matrices by extending the input space slightly, similar to [28]. We denote z k and z k respectively to be the outputs of the k-th hidden layers of C Θ and C Θ+α , which are z k = σ(Θ k (· · · σ(Θ 1 x) · · · )) and z k = σ( Θ k (· · · σ( Θ 1 x) · · · )) and Θ i is weight matrices of C Θ+α , in particular is clearly bounded and depends m, n, W, D, E, ε. Thus C Θ (x) is Lipschitz on Θ. The Lipschitz continuity on x can be proved similarly: We denote the coefficient as Λ(m, n, W, D, E, ε). The lemma is proved. We can also extend this result to convolutional neural networks.

Continuity of the loss function
Unless mentioned otherwise, we assume that the loss function L(z, y) is continuous on z ∈ R m for a fixed y ∈ Y. The mostly often used loss functions have much better properties. Consider the following loss functions: the mean square error, the crossentropy loss, and the margin loss introduced by Carlini-Wagner [6]: where 1 y ∈ R m is the vector whose y-th entry is 1 and all other entries are 0.
By Lemma 2.1, we can assume that the loss function is defined on a bounded cube: where B = Ω(n, m, D, W, E, ε). Since Y = [m] is discrete, we need only consider the continuity of L on z for a fixed y.
The lemma is proved.

Adversarial training as a Stackelberg game
In this section, we formulate the adversarial deep learning as a Stackelberg game and prove the existence of the Stackelberg equilibria.

Stackelberg game
Consider a two-player zero-sum minmax sequential or Stackelberg game G = (S L , S F , ϕ), where S L and S F are respectively the strategy spaces for the leader and the follower of the game and ϕ : S L × S F → R is the payoff function.
In the Stackelberg game G, the leader moves first by picking a strategy s l ∈ S L to minimize the payoff, knowing the existence of the follower. After knowing s l , the follower picks s f ∈ S F to maximize the payoff. Formally, is not empty for any s l ∈ S L , and We have the following result. Theorem 3.1 ( [39]). If the strategy spaces are compact and the payoff function is continuous, then the sequential game G has a Stackelberg equilibrium, which is also a subgame perfect Nash equilibrium of game G as an extensive form game [14].

Adversarial training as a Stackelberg game
We formulate adversarial deep learning as a two-player zero-sum minmax Stackelberg game G s , which is the best defence for adversarial deep learning in certain sense.
The leader of the game is the Classifier, whose goal is to train a robust DNN C Θ : I n → R m in the hypothesis space H in (1). Without loss of generality, we assume that the parameters of C are in for some E ∈ R + , that is, the strategy space for the Classifier is S c .
The follower of the game is the Adversary, whose goal is to create the best adversary within a given attack radius ε ∈ R + . The strategy space for the Adversary is where B ε = {δ ∈ R n : ||δ|| ≤ ε} is the ball with the origin point as the center and ε as the radius. By considering the L ∞ norm, S a becomes a metric space.
The payoff function. Given Θ ∈ S c and A ∈ S a , the payoff function is the expected loss From (9), the composition of L and For game G s , γ and Γ defined in (10) and (12) are and (15) is a continuous and bounded function.
Proof. It is clear that ϕ s (Θ, A) is continuous on Θ, since L is continuous on z and C Θ is continuous on Θ. Denote φ(x) = L(C Θ (x), y) : I n ε → R for fixed Θ and y. Then φ(x) is uniformly continuous by Lemmas 2.2 and 2.3. Given an A 0 ∈ S a and ǫ > 0, since φ(x) is uniformly continuous, there exists a δ > 0 such that for A(x) ∈ S a satisfying ||A 0 ( Since L(C(x), y) is continuous on x and B ǫ is compact, for every (x, y), argmax A(x)∈Bǫ L(C Θ (x + A(x)), y) exists. Thus, by choosing these maximum values, we obtain an A * ∈ S a , which achieves max A∈Sa ϕ s (Θ, A). The lemma is proved.
That is, Θ * s is the solution to the adversarial training (4).
Remark 3.6. As a consequence of Theorem 3.5, the Stackelberg game G s gives the best defence in the hypothesis space H for a given attack radius, if using AR D in (6) to measure the robustness. Precisely, let (Θ * s , A * s ) be a Stackelberg equilibrium of game G s . Then AR D (C Θ * s , ε) = AR D (H, ε).

Refined properties of Γ s
In the general case, γ s (Θ) defined in (16) may have more than one elements. In this section, we will prove that if γ s (Θ) contains a unique element, then Γ s defined in (16) is compact, which will be used in section 6.
Assumption  We first introduce three notations which will be used in this section. By Lemma 2.3, L(z, y) is Lipschitz for z over [−B, B] m when the loss functions in (8) are used, and let Ψ be the Lipschitz constant. By Lemma 2.2, C Θ (x) is Lipschitz for Θ and x, and let ∆ and Λ be the Lipschitz constants, respectively. Lemma 3.8. For any C Θ : I n ε → R m and D, ϕ s (Θ, A) defined in (15) is Lipschitz on Θ and A when the loss function is Lipschitz.
Proof. Firstly, consider ϕ s (Θ, A) for any fixed A. For any ǫ > 0, let δ = ǫ Ψ∆ . Then for any is Lipshitz continuous on Θ. The proof for the Lipschitz continuity on A is similar.
Lemma 3.9. For Θ i ∈ S c , if lim i→∞ Θ i = Θ 0 and g i ∈ γ s (Θ i ), then for any (x, y) ∼ D, the limit of any convergent subsequence of Proof. The result can be proved similar to that of Lemma 3.4.

Lemma 3.10. Under Assumption
Since Y is finite, we may assume y i = y 0 for all i. Then for any Θ, we will prove lim i→∞ A * (Θ)(x i ) = A * (Θ)(x 0 ). Suppose the contrary.

A Stackelberg game to achieve maximal adversarial accuracy
The adversarial accuracy of a DNN C with respect to an attack radius ε is which is the most widely used robustness measurement for DNNs. Comparing to the robustness measurement AR D in (6), AA D (C, ε) does not depends on the loss function. In this section, we will show that adversarial training with the Carlini-Wagner loss function will give a DNN with the optimal adversarial accuracy.
We first introduce a new game. Denote G a to be the two person zero-sum minmax Stackelberg game with the Classifier as the leader, the Adversary as the follower, and ϕ a (Θ, A) = E (x,y)∼D L A (C Θ (x + A(x)), y). (20) as the payoff function, where the loss function is defined as and L cw is the Carlini-Wagner loss function defined in (8).
be a Stackelberg equilibrium of game G s when the loss function is L cw in (8). Then C Θ * cw has the largest adversarial accuracy for all DNNs in H defined in (1), that is AA D (C Θ * cw , ε) ≥ AA D (C Θ , ε) for any C Θ ∈ H.

Trade-off between robustness and accuracy
In this section, we give trade-off results between the robustness and the accuracy in adversarial deep learning from game theoretical viewpoint.

Improve accuracy under maximal adversarial accuracy
By Remarks 3.6 and 4.5, adversarial training computes the DNNs with the best robustness measurement. A nature question is whether we can increase the accuracy of the DNN and still keep the maximal adversarial accuracy. That is, consider the bi-level optimization problem.
From Remark 3.7, if using the loss function L cw , γ s (Θ) contains a unique solution and Θ * s is unique in the generic case. In this case, we cannot increase the accuracy of the DNN when keeping the maximal robust measure AR D .
A more interesting case is to consider game G a defined in section 4, which uses the loss function L A defined in (21).
We first introduce an assumption. We train C Θ with stochastic gradient descent starting from a randomly choosing initial point, and most probably will terminate at a random point in the neighborhood of a minimal point or a saddle point of the loss function. Therefore, the following assumption is valid for almost all trained DNNs [46].
Assumption A 2 . The parameters of a trained C Θ are random values. We now estimate the possible values of Θ * s in (24). Suppose a finite data set is chosen iid from the distribution D, which are used to train the network. Then it can be shown that the game G a with payoff function (20) and trained with T has a Stackelberg equilibrium (Θ * a , A * a ) (See section 6 for more details). With these notations, we have Proposition 5.1. Under Assumption A 2 , there exists a ν ∈ R + such that for all Θ • a ∈ R K satisfying ||Θ • a − Θ * a || < ν, game G a has a Stackelberg equilibrium (Θ • a , A • a ).
is compact and φ(Θ, x) is continuous, there exists a ν i ∈ R + such that φ(Θ * a + ∆, x) < 0 for all x ∈ B(x i , ε) and all ∆ ∈ R K satisfying ||∆|| < ν i . Without loss of generality, we can assume Θ * a + ∆ ∈ S c . It is easy to construct the best response of the Adversary in this case for Θ • a = Θ * a + ∆: is also a compact set of dimension m for all ∆ ∈ R K and ||∆|| < ν i . In this case, A • a (x i ) can be any point in S i (Θ * a + ∆). By Assumption A 2 ,the trained parameters of C are random values. φ(Θ * a , x * ) = L cw (C Θ * a (x * ), y) = 0 implies that C Θ * a ,i (x * ) = C Θ * a ,j (x * ) for i = j, which gives an algebraic relation among the parameters of C Θ . This imposes an extra algebraic relation among the random parameters and thus will not happen under Assumption A 2 . So we have φ(Θ, x * ) = 0 under Assumption A 2 .
. The proposition is proved.
By Proposition 5.1, Θ * s in (24) takes values in a K-dimensional set. As a consequence, there exist rooms for increase the accuracy under the maximal adversarial accuracy.  Table 1. We then retrain the CNNs using the normal loss function in (2) to increase the accuracy. In order to keep the maximal adversarial accuracy fixed, the change of the parameters are limited to i% for i = 1, 2, 3 and the results are given in columns 1-i and 2-i, respectively. We can see that the adversarial accuracies are barely changed (up to 0.06% and 0.02% for networks 1 and 2), but the accuracies are increased evidently (up to 1.11% and 2.252% for networks 1 and 2).

An effective trade-off method
The bi-level optimization problem (24) is in general difficult to solve, especially when keeping the maximal adversarial accuracy as mentioned in the proof of Proposition 5.1. A natural way to train a robust and more accurate DNN is to do adversarial training with the following objective function ϕ t (Θ, A) = ϕ s (Θ, A) + λϕ 0 (Θ) (25) where λ > 0 is a small hyperparameter, ϕ 0 and ϕ s are defined in (2) and (15), respectively. Problem (25) is also often used as an approximate way to solve (24). We will prove a trade-off result in this setting.
Similar to Theorem 3.5, adversarial training with loss function (25) can be considered as a Stackelberg game G t with ϕ t as the payoff function. Then we have the following trade-off result.
where I ε = [−ε, 1 + ε]. For Θ ∈ S c and A = ((x i , y i )) N i=1 ∈ S a , the empirical adversarial loss is We consider three games.
The adversarial training game G 1 , which is the zero-sum minmax sequential game with the Classifier as the leader, the Adversary as the follower, and ϕ T (Θ, A) as the payoff function, that is, to solve the following minmax problem which is clearly equivalent to the adversarial training. By Theorem 3.1, game G 1 has a Stackelberg equilibrium (Θ * 1 , A * 1 ), since S c and S a are compact and ϕ T (Θ, A) is continuous. Similar to section 4, it can be shown that this game gives a DNN with the largest adversarial accuracy for the data set T , when the loss function is L cw .
The universal adversary game G 2 , which is the zero-sum maxmin sequential game with the Adversary as the leader and the Classifier as the follower, that is, to solve the following maxmin problem A * 2 = argmax A∈Sa min Θ∈Sc ϕ T (Θ, A) By Theorem 3.1, game G 2 has a Stackelberg equilibrium (Θ * 2 , A * 2 ). The solution (Θ * 2 , A * 2 ) of this game is to compute the optimal universal adversarial attack for the given hypothesis space H in (1), that is, A * 2 (x) is the best adversary for any (x, y) ∼ D and for all DNNs in H. It is clear that A * 2 is the optimal attack to the so-called nobox model proposed in [5], that is, nobox model has an optimal solution for DNNs with a given structure. This gives a positive answer to question Q 2 for the hypothesis space H in (1).
The simultaneous adversary game G 3 . We can also formulate the adversarial deep learning as a simultaneous game G 3 . In this game, the two players and their strategy spaces are the same as that of game G 1 . The difference is the way to play the game. In game G 3 , the Classifier picks its action without knowing the action of the Adversary, and the Adversary chooses the attacking adversarial samples without knowing the action of the Classifier. But, both players know the payoff function. A point (Θ * 3 , A * 3 ) ∈ S c × S a is called a pure strategy Nash equilibrium of game G 3 if In general, pure strategy Nash equilibria do not necessarily exist, and mixed strategy Nash equilibria are usually considered. Mixed strategies for the Classifier and the Adversary are two probability distributions Θ : S c → I and A : S a → I for Θ and A, respectively. For a mixed strategy ( Θ, A), the payoff function is Denote S c and S a to be the sets of the mixed strategies for the Classifier and the Adversary, respectively. Then ( Θ * 3 , A * 3 ) ∈ S c × S a is called a mixed strategy Nash equilibrium of game G 3 if Since the strategy spaces of the two players are compact and the objective function is continuous, by Glicksberg's theorem [15], game G 3 has a mixed strategy Nash equilibrium ( Θ * 3 , A * 3 ), and the minmax theorem holds for this equilibrium.
Remark 6.1. By Proposition 3.13, we can show that, under Assumption A 1 , game G 3 has a mixed strategy when the data set satisfies a general distribution D.
Proposition 6.2. Let (Θ * i , A * i ) be Nash equilibria of games G i for i = 1, 2, 3, respectively (mixed strategy for G 3 ). Then Proof. The mixed strategy (Θ * 3 , A * 3 ) can be written as two distributions ∆ c : S c → I and ∆ a : S a → I, respectively. To prove the first inequality, we have ≥ ϕ T (Θ * 3 , A * 3 ).
For the second inequality, we have The proposition is proved.
The following example shows that the inequalities in Proposition 6.2 could be strict. where 0 < a < 1. The strategy space for player one is the rows and its goal is minimize the payoff. Then, the Stackelberg game with player one as the leader is to solve the minmax problem and a Stackelberg equilibrium is (Row 1, Column 1) with payoff 0. The Stackelberg game with player two (column) as the leader is to solve the maxmin problem and a Stackelberg equilibrium is (Row 1, Column 2) with payoff −a. By the well known minmax theorem, the corresponding simultaneous game has no Nash equilibrium since minmax = maxmin, and a mixed strategy Nash equilibrium exists: the first player plays ( 1 1+a , a 1+a ) and the second player plays ( a 1+a , 1 1+a ) with payoff − a 1+a . We summarize the above discussion as follows: minmax payoff = 0 maxmin payoff = −a Mixed strategy payoff = − a 1+a ∈ (−a, 0).

Conclusion
In this paper, we give a game theoretical analysis for adversarial deep learning from a more practical viewpoint. In previous work, the adversarial deep learning was formulated as a simultaneous game. In order for the Nash equilibrium to exist, the strategy spaces for the Classifier and the Adversary are assumed to be certain convex probability distributions, which are not used in real applications. In this paper, the adversarial deep learning is formulated as a sequential game with the Classifier as the leader and the Adversary as the follower. In this case, we show that the game has Stackelberg equilibria when the strategy space for the classifier is DNNs with given width and depth, just like people do in practice.
We prove that Stackelberg equilibria for such a sequential game is the same as the DNNs obtained with adversarial training. Furthermore, if the margin loss introduced by Carlini-Wagner is used as the payoff function, the equilibrium DNN has the largest adversarial accuracy and is thus the provable optimal defence. Based on this approach, we also give theoretical analysis for other important issues such as the tradeoff between robustness and the accuracy, and the generation of optimal universal adversaries.
For future research, it is desirable to develop practical methods to use mixed strategy in deep learning, since it is proved that such strategy has more power than pure strategy when the depth and width of the DNNs are fixed. It is also interesting to analysis the properties of the Nash equilibria for adversarial deep learning, such as whether the equilibria are regular or essential [12,43]? Finally, we can use game theory to analyze other adversarial problems in deep learning.