Sarath Yasodharan
email: sarath@iisc.ac.in

Patrick Loiseau
email: patrick.loiseau@inria.fr

Nonzero-sum Adversarial Hypothesis Testing Games

We study nonzero-sum hypothesis testing games that arise in the context of adversarial classification, in both the Bayesian as well as the Neyman-Pearson frameworks. We first show that these games admit mixed strategy Nash equilibria, and then we examine some interesting concentration phenomena of these equilibria. Our main results are on the exponential rates of convergence of classification errors at equilibrium, which are analogous to the well-known Chernoff-Stein lemma and Chernoff information that describe the error exponents in the classical binary hypothesis testing problem, but with parameters derived from the adversarial model. The results are validated through numerical experiments.

Introduction

Classification is a simple but important task that has numerous applications in a variety of domains such as computer vision or security. A traditional assumption that is used in the design of classification algorithms is that the input data is generated without knowledge of the classifier being used, hence the data distribution is independent of the classification algorithm. This assumption is no longer valid in the presence of an adversary, as an adversarial agent can learn the classifier and deliberately alter the data such that the classifier makes an error. This is the case in particular in security applications where the classifier's goal is to detect the presence of an adversary from the data it observes.

Adversarial classification has been studied in two main settings. The first focuses on adversarial versions of a standard classification task in machine learning, where the adversary attacks the classifier (defender/decision maker) by directly choosing vectors from a given set of data vectors; whereas the second focuses on adversarial hypothesis testing, where the adversary (attacker) gets to choose a distribution from a set of distributions and independent data samples are generated from this distribution. The main differences of the latter framework from the former are that: (i) the adversary only gets to choose a distribution (rather than the actual attack vector) and data is generated independently from this distribution, and (ii) the defender makes a decision only once after it observes a whole data sequence instead of making a decision for each individual data sample it receives. Both of these frameworks have applications in a variety of domains, but prior literature has mainly focused on the first setting; see Section 1.1 for a description of the related literature.

In this paper, we focus on the setting of adversarial hypothesis testing. To model the interaction between the attacker and defender, we formulate a nonzero-sum two-player game between the adversary and the classifier where the adversary picks a distribution from a given set of distributions, and data is generated independently from that distribution (a non-attacker always generates data from a fixed distribution). The defender on his side makes a decision based on observation of n data points. Our model can also be viewed as a game-theoretic extension of the classical binary hypothesis testing problem where the distribution under the alternate hypothesis is chosen by an adversary. Based on our game model, we are then able to extend to the adversarial setting the main results of the classical hypothesis testing problem (see Section 2) on the form of the best decision rule and on the rates of decrease of classification errors. More specifically, our contributions can be summarized as follows:

1. We propose nonzero-sum games to model adversarial hypothesis testing problems in a flexible manner. 2. We show existence of mixed strategy Nash equilibria in which the defender employs certain likelihood ratio tests similar to that used in the classical binary hypothesis testing problem. 3. We show that the classification errors under all Nash equilibria for our hypothesis testing games decay exponentially fast in the number of data samples. We analytically obtain these error exponents, and it turns out that they are same as those arising in certain classical hypothesis testing problem, with parameters derived from the adversarial model. 4. We illustrate the results, in particular the importance of some assumptions, using simulations. Throughout our analysis, an important difficulty lies in that the strategy spaces of both the players are uncountable; we believe, however, that it is an important feature of the model to be realistic.

Related Work

Adversarial classification and the security of machine learning have been studied extensively in the past decade, see e.g., [START_REF] Dalvi | Adversarial classification[END_REF][START_REF] Lowd | Adversarial learning[END_REF][START_REF] Barreno | The security of machine learning[END_REF][START_REF] Huang | Adversarial machine learning[END_REF][START_REF] Li | Scalable optimization of randomized operational decisions in adversarial classification settings[END_REF][START_REF] Papernot | Towards the science of security and privacy in machine learning[END_REF]; here we focus only on game-theoretic approaches to tackle the problem. Note that, besides the adversarial learning problem, game theory has been successfully used to tackle several other security problems such as allocation of monitoring resources to protect targets, see e.g., [START_REF] Chen | A game theoretical framework on intrusion detection in heterogeneous networks[END_REF][START_REF] Korzhyk | Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness[END_REF]. We review here only papers relating to classification.

A number of game-theoretic models have appeared in the past decade to study the adversarial classification problem in the classical setting of classification tasks in machine learning. [START_REF] Dalvi | Adversarial classification[END_REF] studies the best response in an adversarial classification game, where the adversary is allowed to alter training data. A number of zero-sum game models were also proposed where the attacker is restricted on the amount of modifications he can do to the training set, see [START_REF] Kantarcioglu | Classifier evaluation and attribute selection against 344 active adversaries[END_REF][START_REF] Zhou | Adversarial support vector machine learning[END_REF][START_REF] Zhou | Adversarial learning with bayesian hierarchical mixtures of experts[END_REF]. [START_REF] Brückner | Static prediction games for adversarial learning problems[END_REF] studies the problem of choosing the best linear classifier in the presence of an adversary (a similar model is also studied in [START_REF] Brückner | Stackelberg games for adversarial prediction problems[END_REF]) using a nonzero-sum game, and shows the existence of a unique pure strategy Nash equilibrium. Similar to our formulation, the strategy sets in this case are uncountable, and therefore showing the existence and uniqueness of Nash equilibrium needs some work. However, in our formulation, there may not always exist a Nash equilibrium in pure strategies, which makes the subsequent analysis of error exponents more difficult. [START_REF] Lisý | Randomized operating point selection in adversarial classification[END_REF] studies an adversarial classification game where the utilities of the players are defined by using ROC curves. The authors study Nash equilibria for their model and provide numerical discretization techniques to compute the equilibria. [START_REF] Dritsoula | A game-theoretic analysis of adversarial classification[END_REF] studies a nonzero-sum adversarial classification game where the defender has no restriction on the classifier, but the attacker is limited to a finite set of vectors. The authors show that the defender can, at equilibrium, use only a small subset of "threshold classifiers" and characterize the equilibrium through linear programming techniques. In our model, the utility functions share similarities with that of [START_REF] Dritsoula | A game-theoretic analysis of adversarial classification[END_REF], but we work in the hypothesis testing framework and with uncountable action sets, which completely modifies the analysis. Several studies appeared recently on "strategic classification", where the objective of the attacker(s) is to improve the classification outcome in his own direction, see [START_REF] Hardt | Strategic classification[END_REF][START_REF] Dong | Strategic classification from revealed preferences[END_REF].

On the other hand, adversarial hypothesis testing has been studied by far fewer authors. [START_REF] Barni | The source identification game: An information-theoretic perspective[END_REF] studies a source identification game in the presence of an adversary, where the classifier needs to distinguish between two source distributions P 0 and P 1 in which the adversary can corrupt samples from P 0 before it reaches the classifier. They show that the game has an asymptotic Nash equilibrium when the number of samples becomes large, and compute the error exponent associated with the false negative probability. [START_REF] Barni | Binary hypothesis testing game with training data[END_REF] and [START_REF] Tondi | Detection games under fully active adversaries[END_REF] study further extensions of this framework.

A (non game-theoretic) hypothesis testing problem in an adversarial setting has been studied by [START_REF] Brandão | Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements[END_REF], which is the closest to our work. Here, there are two sets of probability distributions and nature outputs a fixed number of independent samples generated by using distributions from either one of these two sets. The goal of the classifier is to detect the true state of nature. The authors derive error exponents associated with the classification error, in both Bayesian and Neyman-Pearson frameworks using a worst-case maxmin analysis. Although we restrict to i.i.d. samples and let the non-attacker play a single distribution, we believe that our nonzero-sum game model with flexible utilities can better capture the interaction between adversary and classifier. There also exists extensive prior work within the statistics literature [START_REF] Ingster | Nonparametrie Goodness-of-Fit Testing Under Gaussian Models[END_REF] on minimax hypothesis testing, which relates to our paper, but we defer a discussion of how our work differs from it to after we have exposed the details of our model.

Game-theoretic models were also used to study adversarial classification in a sequential setting, see [START_REF] Soper | A non-zero-sum, sequential detection game[END_REF][START_REF] Bao | Binary hypothesis testing game with training data[END_REF][START_REF] Lye | Game strategies in network security[END_REF], but with very different techniques and results.

Basic Setup and Hypothesis Testing Background

In this section, we present the basic setup results in classical binary hypothesis testing.

Throughout the paper, we consider an alphabet set X that we assume finite. In a classical hypothesis testing problem, we are given two distribution p and q, and a realization of a sequence of independent and identically distributed random variables X 1 , . . . , X n , which are distributed as either p (under hypothesis H 0 ) or q (under hypothesis H 1 ). Our goal is to distinguish between the two alternatives:

H 0 : X 1 , X 2 , . . . , X n i.i.d. ∼ p versus H 1 : X 1 , X 2 , . . . , X n i.i.d. ∼ q.
In this setting, we could make two possible types of errors: (i) we declare H 1 , whereas the true state of nature is H 0 (Type I error, or false alarm), and (ii) we declare H 0 whereas the true state of nature is H 1 (Type II error, or missed detection). Note that one can make one of these errors arbitrarily small at the expense of the other by always declaring H 0 or H 1 .

The trade-off between the two types of errors can be captured using two frameworks. If we have knowledge on the prior probabilities of the two hypotheses, then we can seek a decision rule that minimizes the average probability of error (this is the Bayesian framework). On the other hand, if we do not have any information on the prior probabilities, then we can fix ε > 0 and seek a decision rule that minimizes the Type II error among all decision rules whose Type I error is at most ε (this is the Neyman-Pearson framework). In both of these frameworks, it can be shown that the optimal test is a likelihood ratio test, i.e., given x n = (x 1 , . . . , x n ) we compute the likelihood ratio q(x n ) p(x n ) and compare it to a threshold to make a decision (with possible randomization at the boundary in the Neyman-Pearson framework). Here, p(x n ) (resp. q(x n )) denotes the probability of observing the n-length word x n under the distribution p (resp. q). See Section II.B and II.D in [START_REF] Poor | An Introduction to Signal Detection and Estimation[END_REF] for an introduction to hypothesis testing.

For large enough n, by the law of large numbers, the fraction of i in an observation x n is very close to p(i) (resp. q(i)) under H 0 (resp. under H 1 ), for each i ∈ X . Therefore, one anticipates that the probability of correct decision is very close to 1 for large enough n. Hence, one can study the rate at which the errors go to 0 as n becomes large. It is shown that, under both frameworks, the error decays exponentially in n. In the Bayesian framework, the error exponent associated with the average probability of error is -Λ * 0 (0), where Λ * 0 (•) is the Fenchel-Legendre transform of the log-moment generating function of the random variable q(X) p(X) under H 0 , i.e., when X ∼ p. In the Neyman-Pearson case, the error exponent associated with the Type II error is -D(p||q) where D is the relative entropy functional. The above error exponents are known as Chernoff information and Chernoff-Stein lemma, respectively (see Section 3.4 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF] for the analysis on error exponents).

In this work, we propose extensions of the classical hypothesis testing framework to an adversarial scenario modeled as a game, both in the Bayesian and in the Neyman-Pearson frameworks; and we investigate how the corresponding results are modified. Due to space constraints, we present only the model and results for the Bayesian framework in the main body of the paper. The corresponding analysis for the Neyman-Pearson framework follows similar ideas and is relegated to Appendix A. The proofs of all results presented in the paper (and in Appendix A) can be found in Appendix B.

Hypothesis Testing Game in the Bayesian Framework

In this section, we formulate a one-shot adversarial hypothesis testing game in the Bayesian framework, motivated by security problems where there might be an attacker who modifies the data distribution and a defender who tries to detect the presence of the attacker. Game theoretic modelling of such problems has found great success in understanding the behavior of the agents via equilibrium analysis in many applications, see Section 1.1. We first present the model and then elaborate on its motivations and on how it relates to related works in statistics.

Problem Formulation

Let X = {0, 1, . . . , d -1} denote the alphabet set with cardinality d, and let M 1 (X ) denote the space of probability distributions on X . Fix n ≥ 1.

The game is played as follows. There are two players: the external agent and the defender. The external agent can either be a non-attacker or an attacker. In the Bayesian framework, we assume that the external agent is an attacker with probability θ, and a non-attacker (normal user) with probability 1 -θ. The non-attacker is not strategic and she does not have any adversarial objective. If the external agent is a non-attacker, she generates n samples independently from the distribution p. If the external agent is an attacker, she picks a distribution q from a set of distributions Q ⊆ M 1 (X ) and generates n samples independently from q. The defender, upon observing the n-length word generated by the external agent, wants to detect the presence of the attacker.

Throughout the paper, a decision rule implemented by the defender is denoted by ϕ :

X n → [0, 1],
with the interpretation that ϕ(x n ) is the probability with which hypothesis H 1 is accepted (i.e., the presence of an adversary is declared) when the defender observes the n-length word

x n = (x 1 , . . . , x n ). We say that a decision rule ϕ is deterministic if ϕ(x n ) ∈ {0, 1} for all x n ∈ X n .
To define the game, let the attacker's strategy set be Q ⊆ M 1 (X ), and that of the defender be

Φ n = {ϕ : X n → [0, 1]},
which is the set of all randomized decision rules on n-length words.

To define the utilities, consider the attacker first. We assume that there is a cost associated with choosing a distribution from Q which we model using a cost function c : Q → R + . The goal of the attacker is to fool the defender as much as possible, i.e., he wants to maximize the probability that the defender classifies an n-length word as coming from the non-attacker whereas it is actually being generated by the attacker. To capture this, the utility of the attacker when she plays the pure strategy q ∈ Q and the defender plays the pure strategy ϕ ∈ Φ n is defined as

u A n (q, ϕ) = x n (1 -ϕ(x n ))q(x n ) -c(q), (3.1)
where q(x n ) denotes the probability of observing the n-length word x n when the symbols are generated independently from the distribution q.

For the defender, the goal is to minimize the classification error. Similar to the classical hypothesis testing problem, there could be two types of errors: (i) the external agent is actually a non-attacker whereas the defender declares that there is an attack (Type I error, or false alarm), and (ii) the external agent is an attacker whereas the defender declares that there is no attack (Type II error, or missed detection). The goal of the defender is to minimize a weighted sum of the above two types of errors.

After suitable normalization, we define the utility of the defender as

u D n (q, ϕ) = - x n (1 -ϕ(x n ))q(x n ) + γ x n ϕ(x n )p(x n ) , (3.2)
where γ > 0 is a constant that captures the exogenous probability of attack (i.e., θ), as well as the relative weights given to the error terms.

We denote our Bayesian hypothesis testing game with utility functions (3.1) and (3.

2) by G B (d, n).
With a slight abuse of notation, we denote by

u A n (σ A n , σ D n ) and u D n (σ A n , σ D n )
, the utility of the players under a mixed strategy

(σ A n , σ D n ), where σ A n ∈ M 1 (Q), and σ D n ∈ M 1 (Φ n ).
For our analysis of game G B (d, n), we will make use of the following assumptions: (A1) Q is a closed subset of M 1 (X ), and p / ∈ Q.

(A2) p(i) > 0 for all i ∈ X . Furthermore, for each q ∈ Q, q(i) > 0 for all i ∈ X .

(A3) c is continuous on Q, and there exists a unique q * ∈ Q such that q * = arg min q∈Q c(q).

(A4) The point p is distant from the set Q relative to the point q * , i.e., {µ ∈ M 1 (X ) :

D(µ||p) ≤ D(µ||q * )} ∩ Q = ∅,
where D(µ||ν) = i∈X µ(i) log µ(i) ν(i) , µ, ν ∈ M 1 (X ), denotes the relative entropy between the distributions µ and ν.

Note that (A1) and (A2) are very natural. In (A2), if p(i) = 0 for some i ∈ X and q(i) > 0 for some q ∈ Q, then the adversary will never pick q, as the defender can easily detect the presence of the attacker by looking for element i. On the other hand, if p(i) = 0 and q(i) = 0 for all q ∈ Q, we may consider a new alphabet set without i. In (A3), continuity of the cost function c is natural and we do not assume any extra condition other than the requirement that there is a unique minimizer. Assumption (A4) is used to show certain property of the equilibrium of the defender, which is later used in the study of error exponents associated with classification error. Specifically, Assumption (A4) is used in the proofs of Lemma 4.4, Lemma 4.5 and Theorem 4.1; all other results are valid without this assumption. We will further discuss the role of (A3) and (A4) in Section 4.3 after Theorem 4.1.

Model discussion

Our setting is that of adversarial hypothesis testing, where the attacker chooses a distribution and points are then generated i.i.d. according to it. This is a reasonable model in applications such as multimedia forensics (where one tries to determine if an attacker has tampered with an image from signals that can be modeled as random variables following an image-dependent distribution) or biometrics (where again one tries to detect from random signals whether the perceived signals do come from the characteristics of a given individual or they come from tampered characteristics)-see more details about these applications in [START_REF] Barni | The source identification game: An information-theoretic perspective[END_REF][START_REF] Barni | Binary hypothesis testing game with training data[END_REF][START_REF] Tondi | Detection games under fully active adversaries[END_REF]. In such applications, it is reasonable that different ways of tampering have different costs for the attacker and that one can estimate those costs for a given application at least to some extent. Modeling the attacker's utility via a cost function is classical in other settings, for instance in adversarial classification [START_REF] Dritsoula | A game-theoretic analysis of adversarial classification[END_REF][START_REF] Soper | A non-zero-sum, sequential detection game[END_REF][START_REF] Brückner | Static prediction games for adversarial learning problems[END_REF] and experiments with real-world applications where a reasonable cost function can be estimated has been done, for instance, in [START_REF] Brückner | Static prediction games for adversarial learning problems[END_REF].

Our setting is very similar to that of a composite hypothesis testing framework where nature picks a distribution from a given set and generates independent samples from it. However, in such problems, one does not model a utility function for the nature/statistician and one is often interested in existence and properties of uniformly most powerful test or locally most powerful test (depending on the Bayesian or frequentist approach; see Section II.E in [START_REF] Poor | An Introduction to Signal Detection and Estimation[END_REF]). In contrast, here, we specifically model the utility functions for the agents and investigate the behavior at Nash equilibrium using very different analysis, which is more natural in adversarial settings where two rational agents interact.

Our setting also coincides with the well-studied setting of minimax testing [START_REF] Ingster | Nonparametrie Goodness-of-Fit Testing Under Gaussian Models[END_REF] when c(q) = 0 for all q ∈ Q (and hence every q is a minimizer of c). Note, however, that this case is not included in our model due to Assumption (A3)-rather we study the opposite extreme where c has a unique minimizer. Our results are not an easy extension of the classical results because our game is now a nonzero-sum game (whereas the minimax setting corresponds to a zero-sum game). We can therefore not inherit any of the nice properties of zero-sum games; in particular we cannot compute the NE and we instead have to prove properties of the NE (e.g., concentration) without being able to explicitly compute it. In fact, our results too are quite different since we show that the error rate is the same as a simple test where H 1 would contain only q * , which is different from the classical minimax case.

Finally, in our model we fix the sample size n, i.e., the defender makes a decision only after observing all n samples. We restrict to this simpler setting since it has applications in various domains (see Section 1.1), and understanding the equilibrium of such games leads to interesting and non-trivial results. We leave the study of a sequential model where the defender has the flexibility to choose the number of samples for decision making as future work.

Main Results

Mixed Strategy Nash Equilibrium for G B (d, n)

We first examine the Nash equilibrium for G B (d, n). Note that the strategy sets of both the attacker and the defender are uncountable, hence it is a priori not clear whether our game has a Nash equilibrium.

Towards this, we equip the set Φ n of all randomized decision rules with the sup-norm metric, i.e.,

d n (ϕ 1 , ϕ 2 ) = max x n ∈X n |ϕ 1 (x n ) -ϕ 2 (x n )|, for ϕ 1 , ϕ 2 ∈ Φ n .
It is easy to see that the set Φ n endowed with the above metric is a compact metric space. We also equip M 1 (X ) with the usual Euclidean topology on R d , and equip Q with the subspace topology. Also, for studying the mixed extension of the game, we equip the spaces M 1 (Q) and M 1 (Φ n ) with their corresponding weak topologies. Product spaces are always equipped with the corresponding product topology.

We begin with a simple continuity property of the utility functions. Lemma 4.1. Assume (A1)-(A3). Then, the utility functions u A n and u D n are continuous on Q × Φ n .

We now show the main result of this subsection, namely existence and partial characterization of a NE for our hypothesis testing game. Proposition 4.1. Assume (A1)-(A3). Then, there exists a mixed strategy Nash equilibrium for

G B (d, n). If (σ A n , σD n ) is a NE, then so is (σ A n , φn )
where φn is the likelihood ratio test given by

φn (x n ) =    1, if q σA n (x n ) -γp(x n ) > 0, ϕ σD n , if q σA n (x n ) -γp(x n ) = 0, 0, if q σA n (x n ) -γp(x n ) < 0, (4.1)
where

q σA n (x n ) = q(x n )σ A n (dq), and
ϕ σD n = ϕ(x n )σ D n (dϕ).
The existence of a NE follows from Glicksberg's fixed point theorem (see e.g., Corollary 2.4 in [START_REF] Reny | Non-cooperative games: Equilibrium existence[END_REF]); for the form of the defender's equilibrium strategy, we have to examine the utility function u D n . Remark 4.1. Note that we have considered randomization over Φ n to show existence of a NE. Once this is established, we can then show the form of the strategy of the defender φn at equilibrium; the existence of a NE is not clear if we do not consider randomization over Φ n . Remark 4.2. Note that the distribution q σA n on X n cannot necessarily be written as an n-fold product distribution of some element from M 1 (X ). Therefore, the test φn is slightly different from the usual likelihood ratio test that appears in the classical hypothesis testing problem where samples are generated independently. Remark 4.3. Apart from the conditions of the above proposition, a sufficient condition for existence of pure strategy Nash equilibrium is that the utilities are individually quasiconcave, i.e., u A n (•, ϕ) is quasiconcave for all ϕ ∈ Φ n , and u D n (q, •) is quasiconcave for all q ∈ Q. However, it is easy to check that the Type II error term is not quasiconcave in the attacker's strategy, and hence the utility of the attacker is not quasiconcave. Hence, a pure strategy Nash equilibrium is not guaranteed to exist-see numerical experiments in Section C.1. Remark 4.4. Proposition 4.1 does not provide any information about the structure of the attacker's strategy at a NE. We believe that obtaining the complete structure of a NE and computing it is a difficult problem in general because the strategy spaces of both players are uncountable (and there is no pure-strategy NE in general), and we cannot use the standard techniques for finite games. However, we emphasize that we are able to obtain error exponents at an equilibrium (see Theorem 4.1) without explicitly computing the structure of a NE. Also, one could study Stackelberg equilibrium for our game G B (d, n) to help solve computational issues, although we note that most of the security games literature using Stackelberg games assumes finite action spaces (see, for example, [START_REF] Korzhyk | Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness[END_REF]); however we do not address the study of Stackelberg equilibrium in this paper.

Concentration Properties of Equilibrium

We now study some concentration properties of the mixed strategy Nash equilibrium for the game G B (d, n) for large n. The results in this section will be used later to show the exponential convergence of the classification error at equilibrium. Let e n denote the classification error, i.e., e n (q, ϕ) = -u D n (q, ϕ), q ∈ Q, ϕ ∈ Φ n . We begin with the following lemma, which asserts that the error at equilibrium is small for large enough n. Lemma 4.2. Assume (A1)-(A3). Let (σ A n , σD n ) n≥1 be a sequence such that, for each n ≥ 1, (σ A n , σD n ) is a mixed strategy Nash equilibrium for G B (d, n). Then, e n (σ A n , σD n ) → 0 as n → ∞.

The main idea in the proof is to let the defender play a decision rule whose acceptance set is a small neighborhood around the point p, and then bound e n (σ A n , σD n ) using the error of the above strategy. We now show that the mixed strategy profile of the attacker σA n converges weakly to the point mass at q * (denoted by δ q * ) as n → ∞. This is a consequence of the fact that q * is the minimizer of c, and hence for large enough n, the attacker does not gain much by deviating from the point q * . Lemma 4.3. Assume (A1)-(A3), and let (σ A n , σD n ) n≥1 be as in Lemma 4.2. Then, σA n → δ q * weakly as n → ∞.

Note that it is not clear from the above lemma that the equilibrium strategy of the attacker σA n is supported on a small neighborhood around q * for large enough n. By playing a strategy q that is far from q * we could still have u A n (q, σD n ) = u A n (σ A n , σD n ), since the error term in u A n could compensate for the possible loss of utility from the cost term. We now proceed to show that this cannot happen under Assumption (A4). We first argue that the equilibrium error is small even when the attacker deviates from her equilibrium strategy. Lemma 4.4. Assume (A1)-(A4), and let (σ A n , σD n ) n≥1 be as in Lemma 4.2. Then, sup q∈Q e n (q, σD n ) → 0 as n → ∞.

We are now ready to show the concentration of the attacker's equilibrium: Lemma 4.5. Assume (A1)-(A4), and let (σ A n , σD n ) n≥1 be as in Lemma 4.2. Let (q n ) n≥1 be a sequence such that q n ∈ supp(σ A n ) for each n ≥ 1. Then, q n → q * as n → ∞.

The above concentration phenomenon is a consequence of the uniqueness of q * and Assumption (A4). The main idea in the proofs of Lemma 4.4 and Lemma 4.5 is to essentially show that, for large enough n, the acceptance region of H 0 under (any) mixed strategy Nash equilibrium does not intersect the set Q. If we do not assume (A4), then the decision region at equilibrium could intersect Q, and we may not have the concentration property in the above lemma (we will still have the convergence property in Lemma 4.3 though, which does not use (A4)).

Error Exponents

With the results on concentration properties of the equilibrium from the previous section, we are now ready to examine the error exponent associated with the classification error at equilibrium. Let Λ 0 denote the log-moment generating function of the random variable q * (X) p(X) under H 0 , i.e., when

X ∼ p: Λ 0 (λ) = log i∈X exp λ q * (i) p(i) p(i), λ ∈ R. Define its Fenchel-Legendre transform Λ * 0 (x) = sup λ∈R {λx -Λ 0 (λ)}, x ∈ R.
Our main result in the paper (for the Bayesian case) is the following theorem. Theorem 4.1. Assume (A1)-(A4), and let (σ A n , σD n ) n≥1 be as in Lemma 4.2. Then,

lim n→∞ 1 n log e n (σ A n , σD n ) = -Λ * 0 (0).
Our approach to show this result is via obtaining asymptotic lower and upper bounds for the classification error at equilibrium e n (σ A n , σD n ). Since we do not have much information about the structure of the equilibrium, we first let one of the players deviate from their equilibrium strategy, so that we can estimate the error corresponding to the new pair of strategies, and then use these estimates to compute the error rate at equilibrium. The lower bound easily follows by letting the attacker play the strategy q * , and using the error exponent in the classical hypothesis testing problem between p and q * . For the upper bound, we let the defender play a specific deterministic decision rule, and make use of the concentration properties of the equilibrium of the attacker in Section 4.2.

Thus, we see that the error exponent is the same as that for the classical hypothesis testing problem of X 1 , . . . , X n i.i.d.∼ p versus X 1 , . . . , X n i.i.d.∼ q * (see Corollary 3.4.6 in [10]). That is, for large values of n, the adversarial hypothesis testing game is not much different from the above classical setting (whose parameters are derived from the adversarial setting) in terms of classification error. We emphasize that we have not used any property of the specific structure of the mixed strategy Nash equilibrium in obtaining the error exponent associated with the classification error, and hence Theorem 4.1 is valid for any NE. We believe that obtaining the actual structure of a NE is a difficult problem, as the strategy spaces are infinite, and the utility functions do not possess any monotonicity properties in general. For numerical computation of error exponents in a simple case, see Section 5.

We conclude this section by discussing the role of Assumptions (A3) and (A4). We used (A4) to obtain the concentration of equilibrium in Lemma 4.5. Without this assumption, Theorem 4.1 is not valid; see Section 5 for numerical counter-examples. Also, in our setting, unlike the classical minimax testing, it is not clear whether it is always true that the error goes to 0 as the number of samples becomes large, and whether the attacker should always play a point close to q * at equilibrium. It could be that playing a point far from q * is better if she can compensate the loss from c from the error term. In fact, that is what happens when (A4) is not satisfied, since there is partial overlap of the decision region of the defender with the set Q. Regarding (A3), when c has multiple minimizers, our analysis can only tell us that the equilibrium of the attacker is supported around the set of minimizers for large enough n; to study error exponents in such cases, one has to do a finer analysis of characterizing the attacker's equilibrium. All in all, using (A3) and (A4) allows us to establish interesting concentration properties of the equilibrium (which is not a priori clear) and error exponents associated with classification error without characterizing a NE, hence we believe that these assumptions serve as a good starting point.

Numerical Experiments

In this section, we present two numerical examples in the Bayesian formulation to illustrate the result in Theorem 4.1 and the importance of Assumption (A4). Due to space limitations, additional experiments in the Bayesian formulation are relegated to Appendix C, which illustrate (a) best response strategies of the players, (b) existence of pure strategy Nash equilibrium for large values on n as suggested by Lemma 4.5, and (c) importance of Assumption (A4). 1We illustrate the result in Theorem 4.1 numerically in the following setting. We fix X = {0, 1} (i.e. d = 2) and each probability distribution on X is represented by the probability that it assigns to the symbol 1, and hence M 1 (X ) is viewed as the unit interval. We fix p = 0.5. For numerical computations, we discretize the set Q into 100 equally spaced points, and we only consider deterministic threshold-based decision rules for the defender. To compute a NE, we solve the linear programs associated with attacker as well as the defender for the zero-sum equivalent game of G B (2, n).

For the function c(q) = |q -q * | with q * = 0.8, Figure 1(a) shows the error exponent at the NE computed by the above procedure as a function of the number of samples, from n = 10 to n = 300 in steps of 10. As suggested by Theorem 4.1, we see that the error exponents approach the value Λ * 0 (0) = 0.054 (the boundary of the decision region is around the point q = 0.66, and D(q||p) ≈ D(q||q * ) ≈ 0.054). We now consider an example which demonstrates that, the result on error exponent in Theorem 4.1 may not be valid if Assumption (A4) is not satisfied. In this experiment, we consider the case where Q = [0.6, 0.9] and q * = 0.9. Note that the present setting does not satisfy Assumption (A4). Figure 1(b) shows the error exponent at the equilibrium as a function of n, from n = 100 to n = 400 in steps of 100, for the cost function c(q) = 3|q -q * |. From this plot, we see that, the error exponents converge to somewhere around 0.032, whereas Λ * 0 (0) ≈ 0.111.

Concluding Remarks

In this paper, we studied hypothesis testing games that arise in the context of adversarial classification. We showed that, at equilibrium, the strategy of the classifier is to use a likelihood ratio test. We also examined the exponential rate of decay of classification error at equilibrium and showed that it is same as that of a classical testing problem with parameters derived from the adversarial model.

Throughout the paper, we assumed that the alphabet X is finite. This is a reasonable assumption in applications that deal with digital signals such as image forensics (an important application for adversarial hypothesis testing); and it is also a good starting point because even in this case, our analysis of the error exponents is nontrivial. Making X countable/uncountable will make the space M 1 (X ) infinite dimensional, and the analysis of error exponents will become more difficult (e.g., the continuity of relative entropy is no longer true in this case, which we crucially use in our analysis), but the case of general state space X is an interesting future direction.

Finding the exact structure of the equilibrium for our hypothesis testing games is a challenging future direction. This will also shed some light on the error exponent analysis for the case when Assumption (A4) is not satisfied. Another interesting future direction is to examine the hypothesis testing game in the sequential detection context where the defender can also decide the number of data samples for classification. In such a setting, an important question is to understand whether the optimal strategy of the classifier is to use a standard sequential probability ratio test.

B.4 Proof of Lemma 4.3

From Lemma 4.2, we have en

(σ A n , σD n ) → 0 as n → ∞. Since u A n (q * , σD n ) ≥ -c(q * ) and since (σ A n , σD n ) is a NE for all n ≥ 1, it follows that c(q)σ A n (dq) → c(q * )
as n → ∞. Since (σ A n ) n≥1 is a sequence of probability measures on the compact space Q, by Prohorov's theorem (see Theorem 1, Section 2 in Chapter 3 of [START_REF] Shiryaev | Probability-1[END_REF]), there exists a weakly convergent subsequence (say (n k ) k≥1 ). Let µ denote the weak limit of (σ A n k ) k≥1 . Then, we have,

c(q * ) = lim k→∞ c(q)σ A n k (dq) = c(q)µ(dq), (B.2)
where the last equality follows from weak convergence.

We now claim that µ = δq * . Suppose not. Then, there exists ε > 0 such that µ(B(q * , ε) c ) > 0. By Assumption (A3), for the above ε, there exists a δ > 0 such that c(q) > c(q * ) + δ whenever q ∈ B(q * , ε) c . Therefore,

Q c(q)µ(dq) = B(q * ,ε) c(q)µ(dq) + B(q * ,ε) c c(q)µ(dq) ≥ c(q * )µ(B(q * , ε)) + (c(q * ) + δ)µ(B(q * , ε) c ) = c(q * ) + δµ(B(q * , ε) c ) > c(q * ),
which contradicts (B.2). Therefore, it follows that µ(B(q * , ε) c ) = 0 for every ε > 0 and hence µ = δq * . Since µ is independent of the subsequence (n k ) k≥1 , it follows that the whole sequence (σ A n ) n≥1 converges to δq * (see Lemma 1, Section 3 in Chapter 3 of [START_REF] Shiryaev | Probability-1[END_REF]). This completes the proof of the lemma.

To prove Lemma 4.4, we need the following lemma, which asserts uniform convergence of integrals of the relative entropy functional w.r.t. the equilibrium strategy of the attacker. Therefore, for all µ ∈ B(µ, δ), we have

D(µ ||q)σ A n (dq) -D(µ||q)σ A n (dq) ≤ |D(µ ||q) -D(µ||q)|σ A n (dq)
≤ ε, for all n ≥ 1.

Also, using weak convergence of (σ A n ) n≥1 to the point mass at q * , there exists Nµ ≥ 1 such that

D(µ||q)σ A n (dq) -D(µ||q * ) ≤ ε for all n ≥ Nµ.
Note that, the sets B(µ, δ)µ∈Q is an open cover for M1(X ). By compactness of the space M1(X ), extract a finite subcover B(µi, δ), 1 ≤ i ≤ k. Put N = max{Nµ 1 , . . . , Nµ k }. Then, for all n ≥ N , we have

D(µ||q)σ A n (dq) -D(µ||q * ) ≤ D(µ||q)σ A n (dq) -D(µi||q)σ A n (dq) + D(µi||q)σ A n (dq) -D(µi||q * ) + |D(µi||q * ) -D(µ||q * )| ≤ 3ε,
where µi is such that µ ∈ B(µi, δ). The result now follows since ε and µ are arbitrary.

where (σ A n , ϕ n ) denotes the strategy profile where the attacker plays the mixed strategy σA n that comes form the equilibrium, and the defender plays the pure strategy ϕ n . We have,

en(σ A n , ϕ n ) = x n (1 -ϕ n (x n ))q(x n ) + γϕ n (x n )p(x n ) σ A n (dq) = q(Pxn ∈ Γ )σ A n (dq) + p(Pxn ∈ (Γ ) c ).
Consider the first term. Using the upper bound on the probability of observing a type under a given distribution (Lemma 2.1.9 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF]), we have q(Pxn ∈ Γ ) ≤ (n + 1) d e -n inf ν∈Γ D(ν||q) .

Fix ε > 0. Since the relative entropy is jointly uniformly continuous on Γ × Q, there exists a δ > 0 such that

D(ν||q) ≥ D(ν||q * ) -ε
for all ν ∈ Γ whenever ||q -q * ||2 < δ. For the above δ, by Lemma 4.5, there exists N δ such that ||q -q * ||2 < δ whenever q ∈ supp(σ A n ) for all n ≥ N δ . Therefore, we see that, for all n ≥ N δ and ν ∈ Γ , D(ν||q) ≥ D(ν||q * ) -ε for all q ∈ supp(σ A n ). Therefore, for all n ≥ N δ , we have q(Pxn ∈ Γ ) ≤ (n + 1) d e -n(inf ν∈Γ D(ν||q * )-ε) for all q ∈ supp(σ A n ). For the second term, using Lemma 2.1.9 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF], we have p(Pxn ∈ (Γ ) c ) ≤ e -n inf ν∈(Γ ) c D(ν||p) .

It can be easily shown that (for example, see Exercise 3.4.14(b) in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF]), inf ν∈Γ D(ν||q * ) = inf ν∈(Γ ) c D(ν||p) = Λ * 0 (0). Hence, the above implies that

lim sup n→∞ 1 n log en(σ A n , ϕ n ) ≤ -Λ * 0 (0) + ε.
Letting ε → 0, we get

lim sup n→∞ 1 n log en(σ A n , ϕ n ) ≤ -Λ * 0 (0).
Therefore, from (B.6) and the above inequality, we have

lim sup n→∞ 1 n log en(σ A n , σD n ) ≤ -Λ * 0 (0). (B.7)
The theorem now follows from (B.5) and (B.7).

B.8 Proof of Lemma A.1

We show sequential compactness of Φn. Let (ϕ k ) k≥1 be a sequence in Φn. Let x n 1 , . . . , x n 2 n denote the elements of X n . Since ϕn(x n ) ∈ [0, 1] for all x n ∈ X n , there exists a subsequence (k (1) l ) l≥1 along which ϕ(x n 1 ) converges. We can then extract a further subsequence (k

(2) l ) l≥1 of (k (1) l ) l≥1 along which ϕ(x n
2 ) converges. Repeating the above procedure 2 n times, we see that, there exists a subsequence (k l ) l≥1 along which ϕ(x n ) converges for all x n ∈ X n . Put

ϕ(x n ) = lim l→∞ ϕ k l (x n ), x n ∈ X n .
It is clear that dn(ϕ k l , ϕ) → 0 as l → ∞, and we have

P F A n (ϕ) = x n ϕ(x n )p(x n ) = x n lim l→∞ (ϕ k l (x n ))p(x n ) = lim l→∞ x n ϕ k l (x n )p(x n ) = lim l→∞ P F A (ϕ k l ) ≤ ε, since P F A (ϕ k l ) ≤ ε for all l ≥ 1.
This shows that the space Φn equipped with the metric dn is sequentially compact, and hence compact.

Bayesian Formulation

As explained in Section 5, we fix X = {0, 1} and p = 0.5. For numerical computations, we discretize the set Q into 100 equally spaced points, and we only consider deterministic threshold-based decision rules for the defender.

We first examine the best response of the players. We fix Q = [0.7, 0.9] and the cost function to be c(q) = |q-q * | where q * = 0.8. Figure 2(a) shows the best response of the players for n = 200. The x-axis shows the strategy space of the attacker and y-axis shows the defender's threshold. The blue curve plots the best response of the defender, and the red curve plots the best response of the attacker for 20 thresholds around the best response threshold corresponding to q * . As we see from the figure, the two curves do not intersect (the best threshold for 0.8 is 133, whereas the best value of q for threshold 133 is 0.7) and hence this suggests that there is no pure strategy equilibrium in this case. Figure 2(b) plots the best response curves for n = 250. We see that the two curves intersect (the point of intersection is when the attacker plays 0.8 and the defender plays the threshold 166). However, this does not mean that there is a pure equilibrium, as our discretization may not capture the exact value of the attacker strategy. To see whether this is the case, we plot the attacker revenue when the defender plays the threshold 166 over a finer grid around q * (1000 equally sized points on the interval of length 1/(100 * n) around q * ), which is shown in Figure 3(a). From this, we observe that the maximum of the attacker utility is indeed attained at the point q = 0.8. This suggests that there is a pure strategy Nash equilibrium when the attacker plays 0.8 and defender plays the threshold 166, though we could not prove this analytically.

Similar to the best response plots in Figure 2, we plot the best response plots for the quadratic cost function c(q) = (q -q * ) 2 where q * = 0.8. Figure 4(a) shows the best response plots for n = 700. Here, they don't intersect (the best threshold for 0.8 is 463 whereas the best value of q for threshold 463 is 0.7), which shows that there is no pure equilibrium for the game. Figure 4(b) shows the best repose plots for n = 800. Here, we see that the curves intersect (when the attacker plays 0.8 and defender plays the threshold 529). As before, Figure 3(b) shows a finer plot of the utility of the attacker around the point q * . We see that the utility of the attacker is indeed maximized at 0.8, which suggests that there is a pure strategy equilibrium when the attacker plays the strategy 0.8 and defender plays the threshold 529. (a) c(q) = 2|q -0.9| (b) c(q) = (q -0.9) 2 From these experiments for the linear as well as quadratic cost functions, as we expect, there is no incentive for the attacker to deviate much form the point q * , since for large values of n, the error term in the utility of the attacker does not contribute to the overall revenue. However, in the second case, since the cost function has zero derivative at q * , it is not clear whether a slight deviation form the point q * can increase the error term compared to the decrease in the cost function, so that the overall utility of the attacker increases. Therefore, the existence of a pure strategy Nash equilibrium with the attacker strategy being equal to q * is surprising in this case. However, in the first case, since the left and right derivatives of the cost function at q * are non-zero, the decease in the cost function is much larger compared to the possible increase in the error term as we slightly deviate from q * , and hence it is reasonable to expect the existence of a pure strategy equilibrium at q * for large n.

Comparing the two cost functions, a much higher value of n is needed in the second case for us to have a pure equilibrium at q * , since the increase in the cost function is much slower in the second case as we move away from the point q * . We now give two more examples that does not satisfy Assumption (A4) whose error exponents are different from Theorem 4.1. As before, Q = [0.6, 0.9] and q * = 0.9, and recall that Assumption (A4) is not satisfied in this case. We consider the linear cost function c(q) = 2|q -q * | and the quadratic cost function c(q) = (q -q * ) 2 . Figures 5(a) and 5(b) show the error exponent at the equilibrium as a function of n, from n = 100 to n = 400 in steps of 100. From these plots, we see that, the error exponents converge to somewhere around 0.023 and 0.011 respectively for the above two cost functions, whereas the value of Λ * 0 (0) is around 0.111.

C.2 Neyman-Pearson Formulation

We fix ε = 0.1 and consider the piecewise linear cost function c(q) = |q -q * | on Q = [0.7, 0.8] where q * = 0.8. As suggested by Lemma A.3, there exists a pure strategy Nash equilibrium for G N P (ε, 2, n) for each n ≥ 1. We first compute the dominant decision rule of the defender by finding the appropriate value of threshold and randomization. Once this is done, we compute the equilibrium by finding the best response of the attacker corresponding to this dominant strategy of the defender (as before, we discretize the set Q into 100 equally-spaced points). We repeat the experiment for different values of n, and for the quadratic cost function c(q) = 0.001 * (q -0.8) 2 . Figure 6 and Figure 7 shows the results for the above two cost functions. Since the former cost function increases much faster than the latter as we move away from the point q * , we see that the attacker has much more incentive to play a strategy that is away from q * in the second case compared to the first. This is reflected in the equilibrium strategy of the attacker; from Figures 6(a

Figure 1 :

 1 Figure 1: Error exponents as a function of n

Lemma B. 1 .

 1 Let (σ A n , σD n ) n≥1 be as in Lemma 4.2. Then,sup µ∈M 1 (X ) D(µ||q)σ A n (dq) -D(µ||q * ) → 0 as n → ∞.Proof. Fix ε > 0 and µ ∈ M1(X ). Then, using the uniform continuity of the relative entropy function on M1(X ) × Q, there exists δ > 0 such that sup q∈Q |D(µ||q) -D(µ ||q)| < ε for all µ ∈ B(µ, δ).

  (a) n = 200 (b) n = 250

Figure 2 :Figure 3 :

 23 Figure 2: Best response plots for c(q) = |q -0.8|

21

 21

Figure 4 :

 4 Figure 4: Best response plots for the cost function c(q) = (q -0.8) 2

Figure 5 :

 5 Figure 5: Error exponents as a function of n

22

 22

  (a) Attacker's strategy as a function of n (b) Error exponent as a function of n

Figure 6 :

 6 Figure 6: c(q) = |q -0.8|

Figure 7 :

 7 Figure 7: c(q) = 0.001 * (q -0.8) 2

  ) and 7(a), we see that it takes much larger values of n for the equilibrium strategy of the attacker to become equal to q * in the second case compared to the first. From Figures6(b) and 7(b), we see that the error exponents approach the limiting value D(p||q * ) = 0.223.

Appendix C also contains numerical experiments in the Neyman-Pearson formulation presented in Appendix A. The code used for our simulations is available at https://github.com/sarath1789/ahtg_ neurips2019.

Acknowledgments

The first author is partially supported by the Cisco-IISc Research Fellowship grant. The work of the second author was supported in part by the French National Research Agency (ANR) through the "Investissements d'avenir" program (ANR-15-IDEX-02) and through grant ANR-16-TERC0012; and by the Alexander von Humboldt Foundation.

A Hypothesis Testing Game: Neyman-Pearson Formulation

In this section, we study the Neyman-Pearson version of the hypothesis testing problem. The presentation of results in this section is similar to the Bayesian case, and we will also use the same notation as in the Bayesian formulation.

A.1 Problem Formulation

In the Neyman-Pearson point of view, we do not assume any knowledge on the probability that the external agent is an attacker. Fix ε > 0. As before, the strategy set of the attacker is the set Q. For the defender, motivated by the Neyman-Pearson approach for the classical hypothesis testing problem, we define the strategy set as the set of all randomized decision rules on n-length words whose false alarm probability is at most ε, i.e., Φn = {ϕ : X n → [0, 1] : P F A n (ϕ) ≤ ε}, where P F A n (ϕ) = x n ϕ(x n )p(x n ) denotes the false alarm probability under the decision rule ϕ. We now define the utilities. Similar to the Bayesian framework, the utility of the attacker is defined as

Since we have already constrained the strategy set of the defender by imposing an upper bound on the Type I error, the utility of the defender is defined as u D n (q, ϕ) = -

x n

(1 -ϕ(x n ))q(x n ) , (A.2) which captures the Type II error.

We denote our two-player Neyman-Pearson hypothesis testing game with utility functions (A.1) and (A.2) by G N P (ε, d, n). Similar to the Bayesian case, we will use Assumptions (A1)-(A4) throughout the analysis of the Neyman-Pearson case.

A.2 Mixed Strategy Nash Equilibrium for G N P (ε, d, n)

We now examine the mixed strategy Nash equilibrium for the game G N P (ε, d, n). Similar to the Bayesian framework, we endow the set Q with the standard Euclidean topology on R d and the set Φn with the sup-norm metric. The following lemma asserts compactness of the strategy space of the defender. Lemma A.1. The set Φn equipped with the metric dn is a compact metric space.

We also have joint continuity of the utility functions of both the players, and it can be proved similar to Lemma 4.1. Lemma A.2. Assume (A1)-(A3). Then, the utility functions u A n and u D d are continuous on Q × Φn.

We are now ready to show the existence of a mixed strategy Nash equilibrium. Proposition A.1. Assume (A1)-(A3). Then, there exists a mixed strategy Nash equilibrium for

then σD n is the point mass at the most powerful ε-level Neyman-Pearson test for X1, . . . , Xn i.i.d. ∼ p versus (X1, . . . , Xn) ∼ q σA n .

The existence of a mixed strategy equilibrium easily follows from the compactness of strategy spaces and continuity of utility functions. To show the specific form of defender's equilibrium strategy, we appeal to the Neyman-Pearson lemma.

Let (σ A n , φn) denote a NE given by Proposition A.1.

A.3 Characterization of Equilibrium in the Binary case

Consider the game G N P (ε, d, n) in the binary case, i.e., d = 2. Here, there are some interesting monotonicity properties of the utility functions that allow us to get a pure strategy Nash equilibrium for G N P (ε, 2, n), in which the defender plays a threshold-based test, i.e., declares the presence of an adversary whenever the number of 1's in the observation exceeds a threshold: Lemma A.3. Assume (A1)-(A3). Then, the defender admits a strictly dominant strategy, and there exists a pure strategy Nash equilibrium for G N P (ε, 2, n).

Remark A.1. The monotonicity alluded to above is a consequence of the fact that u D n captures just the Type II error. In the Bayesian framework, we do not have this monotonicity in u D n , due to the presence of both the Type I and Type II errors in u D n , and hence, existence of a pure strategy Nash equilibrium in the binary case cannot be guaranteed in the Bayesian framework.

A.4 Concentration Properties of Equilibrium

In this section, we study some concentration properties of the equilibrium. We have the following two lemmas, which can be proved similar to the corresponding Lemmas for the Bayesian formulation in Section 4.2. Lemma A.4. Assume (A1)-(A3). Let (σ A n , φn)n≥1 be a sequence such that, for each n ≥ 1, (σ A n , φn) is a mixed strategy Nash equilibrium for G N P (ε, d, n). Then, en(σ A n , φn) → 0 as n → ∞. Lemma A.5. Assume (A1)-(A3), and let (σ A n , φn)n≥1 be as in Lemma A.4. Then σA n → δq * weakly as n → ∞.

We also have that the error at equilibrium goes to 0 even when the attacker deviates from her equilibrium strategy. Lemma A.6. Assume (A1)-(A4), and let (σ A n , φn)n≥1 be as in Lemma A.4. Then, sup q∈Q en(q, φn) → 0 as n → ∞.

The main idea in the proof of the above lemma is to show that the acceptance region of H0 under any equilibrium does not intersect the set Q. With this lemma at hand, we now have the following concentration property for the support of the equilibrium strategy of the attacker, which can be proved similar to Lemma 4.5 in the Bayesian formulation. Lemma A.7. Assume (A1)-(A4), and let (σ A n , φn)n≥1 be as in Lemma A. [START_REF] Barreno | The security of machine learning[END_REF]. Let (qn) n≥1 be a sequence such that qn ∈ supp(σ A n ) for each n ≥ 1. Then, qn → q * as n → ∞. Remark A.2. Note that, in one dimension (d = 1), the acceptance region of an optimal Neyman-Pearson test for a fixed alternative q will be a "vanishingly small neighborhood of the null distribution p" and that while it can still intersect Q for finite n, it may not for large-enough n; so that Lemma A.6 may always hold. However, it is unclear how this might generalize to higher dimension. Intuitively, in higher dimension, the acceptance region may become close to p only from certain directions. We also note that our proof of Lemma A.6 actually uses Assumption (A4) and not a weaker version of it-see the expression of Γn in the proof of Lemma A.6. Therefore, we believe that (A4) is needed in higher dimensions even for the Neyman-Pearson case; although it is possible that a weaker assumption will suffice in one dimension.

A.5 Error Exponents

Our main result in the Neyman-Pearson formulation is the following theorem. Theorem A.1. Assume (A1)-(A4), and let (σ A n , φn)n≥1 be as in Lemma A.4. Then,

Again, we note that the error exponent is the same as that of the classical Neyman-Pearson hypothesis testing problem between p and q * .

B Proofs

B.1 Proof of Lemma 4.1

Since we are on a metric space, it suffices to show sequential continuity. Let {(q k , ϕ k ), k ≥ 1} be a sequence such that (q k , ϕ k ) → (q, ϕ) as k → ∞. First, consider u D n . Notice that, for each x n , we have

12 Similarly, we also have

Therefore, we have that u D n (q k , ϕ k ) → u D n (q, ϕ) as k → ∞ which proves continuity of the utility of the defender. Using similar arguments, and by using the continuity of the cost function c on Q, we see that

, which shows the continuity of the utility of the attacker.

B.2 Proof of Proposition 4.1

) is a two-player game with compact strategy spaces. Also, by Lemma 4.1, the utilities (in pure strategies) of both the attacker and the defender are jointly continuous on Q × Φn. Therefore, an application of the Glicksberg fixed point theorem (see, for example, Corollary 2.4 in [START_REF] Reny | Non-cooperative games: Equilibrium existence[END_REF]) tell us that there exists a mixed strategy Nash equilibrium (NE) for the adversarial hypothesis testing game G B (d, n).

We now show the structure of the equilibrium strategy of the defender. Note that, for any ϕ ∈ Φn,

Therefore, using the characterization of a NE (see Proposition 140.1 in [START_REF] Osborne | An Introduction to Game Theory[END_REF]), it follows that for any ϕ ∈ supp(σ D n ), we have

, and that satisfies the above condition when x n is such that q σA n (x n ) -γp(x n ) = 0. Consider the strategy profile (σ A n , φn) where the defender plays the pure strategy φn. By the choice of φn, we see that

for any ϕ ∈ Φn. Therefore, using the characterization of a NE, we see that (σ A n , φn) is a NE. This completes the proof of the Proposition.

B.3 Proof of Lemma 4.2

By Assumption (A1), there exist a δ > 0 such that B(p, δ) ∩ Q = ∅, where B(p, δ) denotes an open ball of radius δ centered at p. Let ϕ δ denote the deterministic decision rule whose rejection region is the set B(p, δ) c , i.e., ϕ δ (x n ) = 1 whenever Pxn ∈ B(p, δ) c and ϕ δ (x n ) = 0 otherwise, where Pxn ∈ M1(X ) denotes the type of x n , i.e.,

where (σ A n , ϕ δ ) denotes the strategy profile where the attacker plays the mixed strategy σA n and the defender plays the pure strategy ϕ δ .

We now proceed to bound the error term en(σ A n , ϕ δ ). We have

We bound the first term above using a simple upper bound for the probability of observing a given type under a given distribution (see, for example, Lemma 2.1.9 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF]). Let Pn denote the set of all possible types of an n-length word. For any q ∈ Q, we have that

where the last inequality follows since |Pn| ≤ (n + 1) d . Therefore,

). The first term above goes to 0 as n → ∞, since inf ν∈B(p,δ),q∈Q D(ν||q) > 0. Also, by the weak law of large numbers, we see that Pxn converges to p in probability under the null hypothesis H0. Therefore, p(Pxn ∈ B(p, δ) c ) → 0.

Hence, we conclude that en(σ A n , ϕ δ ) → 0 as n → ∞. Combining this with (B.1) completes the proof of the Lemma.

B.5 Proof of Lemma 4.4

Recall the decision rule φn from Proposition 4.1. Note that if H0 is accepted under φn when the defender observes x n , then we have

(note that there could be randomization when equality holds above). By Proposition 4.1, notice that (σ A n , φn) is a Nash equilibrium, and en(q, σD n ) = en(q, φn) for all q ∈ Q. Therefore it suffices to show that sup q∈Q en(q, φn) → 0 as n → ∞.

Note that, the acceptance region of H0 under the decision rule φn is type-based, i.e., for every n-length word x n , φn(x n ) depends only on Pxn . Therefore, if H0 is accepted when the defender observes x n , the type Pxn must belong to the following subset of M1(X ):

Notice that, by Jensen's inequality, the acceptance region of H0 under the decision rule φn is a subset of the above set Γn. Also, it is easy to check that,

We now show that the set Γn does not intersect the set Q for large enough n. First, notice that, the set {µ ∈ M1(X ) : D(µ||p) ≤ D(µ||q * )} is closed in M1(X ). Therefore, by Assumption (A4), there exists η > 0

We show that there exists N ≥ 1 such that Q η ∩Γn = ∅ for all n ≥ N . Suppose not, then we can find a sequence (µn) n≥1 such that µn ∈ Q η and µn ∈ Γn for all n ≥ 1. Since Q η is compact, we can find a subsequence (n k ) k≥1 along which µn converges, and let µ = lim k→∞ µn k ∈ Q η . Since µn ∈ Γn for all n ≥ 1, using Lemma B.1, we see that µ satisfies D(µ||p) ≤ D(µ||q * ). This contradicts the fact that Q η ∩ Γn = ∅, and hence, there exists N ≥ 1 such that Q η ∩ Γn = ∅ for all n ≥ N .

By the law of large numbers, we have sup q∈Q q(Pxn / ∈ B(q, η)) → 0, and p(Pxn / ∈ Γn) → 0 as n → ∞. But, notice that en(q, φn) ≤ q(Pxn ∈ Γn) + γp(Pxn / ∈ Γn) ≤ q(Pxn / ∈ B(q, η)) + γp(Pxn / ∈ Γn) for all q ∈ Q and n ≥ N . Therefore, sup q∈Q en(q, φn) ≤ sup q∈Q q(Pxn / ∈ B(q, η)) + γp(Pxn / ∈ Γn)

B.6 Proof of Lemma 4.5

Fix ε > 0. By Lemma 4.4, there exists Nε such that en(qn, σD n ) ≤ ε for all n ≥ Nε. Therefore, u A n (qn, σD n ) ≤ ε -c(qn) for all n ≥ Nε. However, by playing the pure strategy q * , the attacker utility is u A n (q * , σD n ) ≥ -c(q * ) for all n ≥ 1. Since (σ A n , σD n ) is a Nash equilibrium, and since qn ∈ supp(σ A n ), we must have u A n (qn, σD n ) ≥ u A n (q * , σD n ) for all n ≥ Nε. That is, c(qn) ≤ c(q) + ε for all n ≥ Nε. Thus, it follows that, c(qn) → c(q * ) as n → ∞. Using the definition of q * , we see that qn → q * as n → ∞.

B.7 Proof of Theorem 4.1

First, we obtain the asymptotic lower bound. Towards this, we shall consider an equivalent zero-sum game for G B (d, n). For q ∈ Q and ϕ ∈ Φn, define u eq n (q, ϕ) =

Observe that, as far as the attacker is concerned, for any ϕ ∈ Φn, maximizing u A n (•, ϕ) is the same as maximizing u eq n (•, ϕ), as the extra term present in u eq n does not depend on the attacker strategy. Similarly, for any q ∈ Q, maximizing the defender's utility function u D n (q, •) is the same as minimizing u eq n (q, •), as the cost function c does not depend on the defender's strategy. Therefore, we see that G B (d, n) is best-response equivalent to a two-player zero sum game (with attacker being first player and defender being second player) with the above utility for the first player. Hence, any equilibrium for the original game is also going to be an equilibrium for the zero-sum equivalent game with utility function u eq n (see Definition 4 in [START_REF] Dritsoula | A game-theoretic analysis of adversarial classification[END_REF] and the remarks before Theorem 2). Consider the strategy profile (q * , σD n ), i.e., the attacker plays the pure strategy q * and the defender plays the mixed strategy σD n that comes from the equilibrium. By definition of the Nash equilibrium, and the equivalence of G B (d, n) with the above zero-sum game, we have

3) (u eq n (σ A n , σD n ) denotes the utility in mixed extension of the equivalent zero-sum game). Define the deterministic decision rule ϕ * n by

It is easy to see that ϕ * n minimizes en(q * , •). Writing the probabilities p(x n ) and q(x n ) in terms of Pxn , it is easy to check that, the acceptance region of ϕ * n is given by

i.e., ϕ * n (x n ) = 0 whenever Pxn ∈ Γ * n , and ϕ * n (x n ) = 1 otherwise. Noting that u eq n (q, ϕ) = en(q, ϕ) -c(q), (B.3) becomes

where the second inequality follows from the definition of q * , and the last inequality follows from the optimality of ϕ * n . The quantitiy in the RHS of the last inequality is the minimum Bayesian error for the following standard binary hypothesis testing problem: under the null hypothesis, each symbol in x n is generated independently from p, and under the alternate hypothesis, each symbol is generated independently from q * . It is well known that (see, for example, Corollary 3.4.6 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF]),

and hence, from (B.3) and (B.4), it follows that,

We now proceed to show the upper bound. Define the decision rule ϕ n by

Similar to the decision rule ϕ * n , the acceptance region of ϕ n can be written as

i.e., ϕ n (x n ) = 0 if Pxn ∈ Γ , and ϕ n (x n ) = 1 otherwise. By the definition of a Nash equilibrium, and noting that

B.9 Proof of Proposition A.1

By Lemma A.1, the strategy space of the defender is compact. Also, the strategy space of the attacker is compact under the standard Euclidean topology on R d . By Lemma A.2, we see that the utility functions of both players are jointly continuous. Therefore, by the Glicksberg fixed point theorem (see, for example, Corollary 2.4. in [START_REF] Reny | Non-cooperative games: Equilibrium existence[END_REF]), there exists a mixed strategy Nash equilibrium for the game G(ε, d, n).

We now show the structure of the equilibrium strategy of the defender. Let (σ A n , σD n ) denote a mixed strategy Nash equilibrium of G(ε, d, n). By the property of Nash equilibrium, we have that en(σ A n , ϕ) = en(σ A n , σD n ) for all ϕ ∈ supp(σ D n ). We claim that P F A (ϕ) = ε for all ϕ ∈ supp(σ D n ). If there exists ϕ ∈ supp(σ D n ) with P F A (ϕ) < ε, then we can find x n 0 ∈ X n such that ϕ(x n 0 ) = 0 and δ > 0 such that the decision rule defined by ϕ (x n ) = ϕ(x n ) for all x n = x n 0 , and ϕ (x n 0 ) = δ has the property that P F A n (ϕ ) ≤ ε and en(σ A n , ϕ ) < en(σ A n , σD n ). This contradicts the fact that, (σ A n , σD n ) is a Nash equilibrium, which proves our claim.

But, note that

where q σA n ∈ M1(X n ) is given by

That is, when the attacker plays the Nash equilibrium σA n , the defender faces the problem of distinguishing between the two alternatives: (i) (X1, . . . , Xn) is generated by i.i.d. p, versus (ii) (X1, . . . , Xn) is generated by q σA n . By the Neyman-Pearson lemma, we know that there exists a Neyman-Pearson decision rule φn ∈ Φn with the property that P F A ( φn) = ε and en(σ A n , •) is minimized by φn on Φn. Since every ϕ ∈ supp(σ D n ) minimizes en(σ A n , •), and P F A (ϕ) = ε, and since each x n ∈ X n has positive probability of observing under both H0 and H1, an application of the uniqueness part in Neyman-Pearson lemma (see, for example, Section 5.1 in [START_REF] Ferguson | Mathematical Statistics: A Decision Theoretic Approach[END_REF]) yields that that σD n = δ φn . This completes the proof.

B.10 Proof of Lemma A.3

Recall the definition of a Neyman-Pearson decision rule. In the binary case, since the comparison of the ratio q(x n ) p(x n ) to a threshold is the same as comparison of the number of 1's in the n-length word x n to some other threshold, we see that any Neyman-Pearson decision rule ϕ must necessarily be of the following form:

for some π ∈ [0, 1] and 0 ≤ k ≤ n. Here, Pxn (1) denotes the fraction of 1's in x n . The false alarm probability of the above decision rule is

Since every n-length word x n has positive probability under the distribution p, we see that, there exists a unique k and π such that P F A n (ϕ) = ε. Let φn denote the above Neyman-Pearson decision rule. Then, by the Neyman-Pearson lemma (see, for example, Proposition II.D.1 in [START_REF] Poor | An Introduction to Signal Detection and Estimation[END_REF]), we see that, φn = arg max ϕ∈Φn u D n (q, ϕ) for all q ∈ Q.

Thus, the defender has a unique strictly dominant strategy. Using the continuity of c, and the continuity of the Type II error term in the attacker's strategy, we see that u A n (•, φn) is continuous on Q, and hence there exist a maximum. Therefore, letting the attacker play a pure strategy qn that maximizes u A n (•, φn) yields a pure strategy Nash equilibrium (qn, φn).

To prove Lemma A.6, we need the following lemma, which can be proved similar to Lemma B.1. Let γn denote the threshold and π denote the randomization used in the decision rule φn, i.e., φn is of the form

We first claim that lim sup n→∞ γn ≤ 1. Since P F A ( φn) = ε, we have that

But, using the probability of observing an n-length word under a distribution (see, for example, Lemma 2.1.6 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF]), we have

= e -n(H(P x n )+D(P x n ||q)) σA n (dq), and p(x n ) = e -n(H(P x n )+D(P x n )||p) .

Therefore, + p e n(D(P x n ||p)-inf q∈Q D(P x n ||q)) ≥ γn, Pxn / ∈ B(p, δ)

By law of large numbers, p(Pxn / ∈ B(p, δ)) → 0, and hence the second term above goes to 0 as n → ∞. Suppose that lim sup n→∞ γn > 1, then there exists a subsequence (n k ) k≥1 such that γn k > 1 for all k ≥ 1. Therefore, along this subsequence, the first term above becomes

which goes to 0 as n → ∞ by the choice of δ. This implies that, p q σA n (x n ) p(x n ) ≥ γn → 0 as n → ∞, which contradicts (B.9). Therefore, we must have lim sup n→∞ γn ≤ 1.

We now argue that, for some η > 0, the acceptance set of H0 under φn does not intersect the set Q η . Towards this, consider the set

Notice that, by Jensen's inequality, the acceptance region of H0 under the decision rule φn is a subset of the above set Γn. Also, it is easy to check that,

We now show that the set Γn does not intersect the set Q for large enough n. First, notice that, the set {µ ∈ M1(X ) : D(µ||p) ≤ D(µ||q * )} is closed in M1(X ). Therefore,by Assumption (A4) there exists η > 0 such that {µ ∈ M1(X ) :

We show that there exists N ≥ 1 such that Q η ∩ Γn = ∅ for all n ≥ N . Suppose not, then we can find a sequence (µn) n≥1 such that µn ∈ Q η and µn ∈ Γn for all n ≥ 1. Since Q η is compact, we can find a subsequence (n k ) k≥1 along which µn converges, and let µ = lim k→∞ µn k ∈ Q η . Since µn ∈ Γn for all n ≥ 1, using Lemma B.2 and the fact that lim sup n→∞ γn = 0, we see that µ satisfies D(µ||p) ≤ D(µ||q * ). This contradicts the fact that Q η ∩ Γn = ∅, and hence, there exists N ≥ 1 such that Q η ∩ Γn = ∅ for all n ≥ N .

By the law of large numbers, we have sup q∈Q q(Pxn / ∈ B(q, η)) → 0

as n → ∞. But, notice that en(q, φn) ≤ q(Pxn ∈ Γn) ≤ q(Pxn / ∈ B(q, η))

for all q ∈ Q and n ≥ N . Therefore, sup q∈Q en(q, φn) ≤ sup q∈Q q(Pxn / ∈ B(q, η)) → 0

as n → ∞.

B.12 Proof of Theorem A.1

We proceed through similar steps as in the proof of Theorem 4.1. To show the lower bound, we let the attacker play the pure strategy q * instead of the her equilibrium strategy σA n for all n ≥ 1. Since u A n (q, ϕ) = en(q, ϕ) -c(q), and since (σ A n , φn) is a Nash equilibrium for G N P (ε, d, n), we see that en(σ A n , φn) ≥ en(q * , φn) -c(q * ) + c(q)σ A n (dq)

≥ en(q * , φn)

≥ en(q * , ϕ * n ) where ϕ * n denotes the best ε-level Neyman-Pearson test for distinguishing p from q * from n independent samples. Here, the second inequality follows from the definition of q * , and the last inequallity follows from the optimality of Neyman-Pearson test ϕ * n . Hence, using Stein's lemma (see, for example, Lemma 3. We now show the upper bound. Fix 0 < δ < 1 such that B(p, δ) ∩ Q = ∅, and consider the deterministic decision rule ϕ δ with acceptance region B(p, δ), i.e., ϕ δ (x n ) = 0 whenever Pxn ∈ B(p, δ) and ϕ δ (x n ) = 1 otherwise. To obtain the upper bound, we let the defender play the strategy ϕ δ n for all n ≥ 1. Since (σ A n , φn) is a Nash equilibrium, and u D n (q, ϕ) = -en(q, ϕ), we have en(σ A n , φn) ≤ en(σ A n , ϕ δ ) = q(Pxn ∈ Γ δ )σ A n (dq) ≤ (n + 1) d e -n inf ν∈Γ δ D(ν||q) σA n (dq), (B.11

where the last inequality follows form the upper bound in Lemma 2.1.9 in [START_REF] Dembo | Large Deviations: Techniques and Applications[END_REF]. By Lemma A. The result now follows form (B.10) and (B.12).