# adversarial_regression_with_multiple_learners__d4b48fef.pdf Adversarial Regression with Multiple Learners Liang Tong * 1 Sixie Yu * 1 Scott Alfeld 2 Yevgeniy Vorobeychik 1 Despite the considerable success enjoyed by machine learning techniques in practice, numerous studies demonstrated that many approaches are vulnerable to attacks. An important class of such attacks involves adversaries changing features at test time to cause incorrect predictions. Previous investigations of this problem pit a single learner against an adversary. However, in many situations an adversary s decision is aimed at a collection of learners, rather than specifically targeted at each independently. We study the problem of adversarial linear regression with multiple learners. We approximate the resulting game by exhibiting an upper bound on learner loss functions, and show that the resulting game has a unique symmetric equilibrium. We present an algorithm for computing this equilibrium, and show through extensive experiments that equilibrium models are significantly more robust than conventional regularized linear regression. 1. Introduction Increasing use of machine learning in adversarial settings has motivated a series of efforts investigating the extent to which learning approaches can be subverted by malicious parties. An important class of such attacks involves adversaries changing their behaviors, or features of the environment, to effect an incorrect prediction. Most previous efforts study this problem as an interaction between a single learner and a single attacker (Brückner & Scheffer, 2011; Dalvi et al., 2004; Li & Vorobeychik, 2014; Zhou et al., 2012). However, in reality attackers often target a broad array of potential victim organizations. For example, they craft generic spam templates and generic malware, and then disseminate these widely to maximize impact. The resulting *Equal contribution 1Department of EECS, Vanderbilt University, Nashville, TN, USA 2Computer Science Department, Amherst College, Amherst, MA, USA. Correspondence to: Yevgeniy Vorobeychik . Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s). ecology of attack targets reflects not a single learner, but many such learners, all making autonomous decisions about how to detect malicious content, although these decisions often rely on similar training datasets. We model the resulting game as an interaction between multiple learners, who simultaneously learn linear regression models, and an attacker, who observes the learned models (as in white-box attacks (Šrndic & Laskov, 2014)), and modifies the original feature vectors at test time in order to induce incorrect predictions. Crucially, rather than customizing the attack to each learner (as in typical models), the attacker chooses a single attack for all learners. We term the resulting game a Multi-Learner Stackelberg Game, to allude to its two stages, with learners jointly acting as Stackelberg leaders, and the attacker being the follower. Our first contribution is the formal model of this game. Our second contribution is to approximate this game by deriving upper bounds on the learner loss functions. The resulting approximation yields a game in which there always exists a symmetric equilibrium, and this equilibrium is unique. In addition, we prove that this unique equilibrium can be computed by solving a convex optimization problem. Our third contribution is to show that the equilibrium of the approximate game is robust, both theoretically (by showing it to be equivalent to a particular robust optimization problem), and through extensive experiments, which demonstrate it to be much more robust to attacks than standard regularization approaches. Related Work Both attacks on and defenses of machine learning approaches have been studied within the literature on adversarial machine learning (Brückner & Scheffer, 2011; Dalvi et al., 2004; Li & Vorobeychik, 2014; Zhou et al., 2012; Lowd & Meek, 2005). These approaches commonly assume a single learner, and consider either the problem of finding evasions against a fixed model (Dalvi et al., 2004; Lowd & Meek, 2005; Šrndic & Laskov, 2014), or algorithmic approaches for making learning more robust to attacks (Russu et al., 2016; Brückner & Scheffer, 2011; Dalvi et al., 2004; Li & Vorobeychik, 2014; 2015). Most of these efforts deal specifically with classification learning, but several consider adversarial tampering with regression models (Alfeld et al., 2016; Grosshans et al., 2013), although still within a single-learner and single-attacker framework. Stevens & Lowd (2013) study the algorithmic problem of Adversarial Regression with Multiple Learners attacking multiple linear classifiers, but did not consider the associated game among classifiers. Our work also has a connection to the literature on security games with multiple defenders (Laszka et al., 2016; Smith et al., 2017; Vorobeychik et al., 2011). The key distinction with our paper is that in multi-learner games, the learner strategy space is the space of possible models in a given model class, whereas prior research has focused on significantly simpler strategies (such as protecting a finite collection of attack targets). We investigate the interactions between a collection of learners N = {1, 2, ..., n} and an attacker in regression problems, modeled as a Multi-Learner Stackelberg Game (MLSG). At the high level, this game involves two stages: first, all learners choose (train) their models from data, and second, the attacker transforms test data (such as features of the environment, at prediction time) to achieve malicious goals. Below, we first formalize the model of the learners and the attacker, and then formally describe the full game. 2.1. Modeling the Players At training time, a set of training data (X, y) is drawn from an unknown distribution D. X 2 Rm d is the training sample and y 2 Rm 1 is a vector of values of each data in X. We let xj 2 Rd 1 denote the jth instance in the training sample, associated with a corresponding value yj 2 R from y. Hence, X = [x1, ..., xm]> and y = [y1, y2, ..., ym]>. On the other hand, test data can be generated either from D, the same distribution as the training data, or from D 0, a modification of D generated by an attacker. The nature of such malicious modifications is described below. We let β (0 β 1) represent the probability that a test instance is drawn from D 0 (i.e., the malicious distribution), and 1 β be the probability that it is generated from D. The action of the ith learner is to select a d 1 vector i as the parameter of the linear regression function ˆyi = X i, where ˆyi is the predicted values for data X. The expected cost function of the ith learner at test time is then 0) = βE(X0,y) D0 [ (X + (1 β)E(X,y) D[ (X i, y)]. where (ˆy, y) = ||ˆy y||2 2. That is, the cost function of a learner i is a combination of its expected cost from both the attacker and the honest source. Every instance (x, y) generated according to D is, with probability β, maliciously modified by the attacker into another, (x0, y), as follows. We assume that the attacker has an instance-specific target z(x), and wishes that the prediction made by each learner i on the modified instance, 0, is close to this target. We measure this objective for the attacker by (ˆy, z) = ||ˆy z||2 2 for a vector of predicted and target values ˆy and z, respectively. In addition, the attacker incurs a cost of transforming a distribution D into D 0, denoted by R(D After a dataset (X 0, y) is generated in this way by the attacker, it is used simultaneously against all the learners. This is natural in most real attacks: for example, spam templates are commonly generated to be used broadly, against many individuals and organizations, and, similarly, malware executables are often produced to be generally effective, rather than custom made for each target. The expected cost function of the attacker is then a sum of its total expected cost for all learners plus the cost of transforming D into D 0 with coefficient λ > 0: E(X0,y) D0 [ (X 0 i, z)]+λR(D As is typical, we estimate the cost functions of the learners and the attacker using training data (X, y), which is also used to simulate attacks. Consequently, the cost functions of each learner and the attacker are estimated by 0 i, y) + (1 β) (X i, y) (3) 0 i, z) + λR(X where the attacker s modification cost is measured by R(X 0, X) = ||X F , the squared Frobenius norm. 2.2. The Multi-Learner Stackerlberg Game We are now ready to formally define the game between the n learners and the attacker. The MLSG has two stages: in the first stage, learners simultaneously select their model parameters i, and in the second stage, the attacker makes its decision (manipulating X 0) after observing the learners model choices { i}n i=1. We assume that the proposed game satisfies the following assumptions: 1. The learners have complete information about param- eters β, λ and z. This is a strong assumption, and we relax it in our experimental evaluation (Section 6), providing guidance on how to deal with uncertainty about these parameters. 2. Each learner has the same action (model parameter) space Rd 1 which is nonempty, compact and convex. The action space of the attacker is Rm d. Adversarial Regression with Multiple Learners 3. The columns of the training data X are linearly inde- We use Multi-Learner Stackelberg Equilibrium (MLSE) as the solution for the MLSG, defined as follows. Definition 1 (Multi-Learner Stackelberg Equilibrium (MLSE)). An action profile ({ i=1, X ) is an MLSE if it satisfies i = arg min ci( i, X ( )), 8i 2 N s.t. X ( ) = arg min X02Rm d ca({ i}n where = { i}n i=1 constitutes the joint actions of the learners. At the high level, the MLSE is a blend between a Nash equilibrium (among all learners) and a Stackelberg equilibrium (between the learners and the attacker), in which the attacker plays a best response to the observed models chosen by the learners, and given this behavior by the attacker, all learners models i are mutually optimal. The following lemma characterizes the best response of the attacker to arbitrary model choices { i}n i=1 by the learners. Lemma 1 (Best Response of the Attacker). Given { i}n i=1, the best response of the attacker is X = (λX + z Proof. We derive the best response of the attacker by using the first order condition. The details are included in the supplementary material. Lemma 1 shows that the best response of the attacker, X , has a closed form solution, as a function of learner model parameters { i}n i=1. Let i = { j}j6=i, then ci( i, X ) in Eq. (5) can be rewritten as ci( i, i) = β (X ( i, i) i, y) + (1 β) (X i, y). (7) Using Eq. (7), we can then define a Multi-Learner Nash Game (MLNG): Definition 2 (Multi-Learner Nash Game (MLNG)). A static game, denoted as h N, , (ci)i is a Multi-Learner Nash Game if 1. The set of players is the set of learners N, 2. the cost function of each learner i is ci( i, i) defined in Eq. (7), 3. all learners simultaneously select i 2 . We can then define Multi-Learner Nash Equilibrium (MLNE) of the game h N, , (ci)i: Definition 3 (Multi-Learner Nash Equilibrium (MLNE)). An action profile = { i=1 is a Multi-Learner Nash Equilibrium of the MLNG h N, , (ci)i if it is the solution of the following set of coupled optimization problem: min i2 ci( i, i), 8i 2 N. (8) Combining the results above, the following result is immediate. Theorem 1. An action profile ({ i=1, X ) is an MLSE of the multi-learner Stackelberg game if and only if { i=1 is a MLNE of the multi-learner Nash game h N, , (ci)i, with X defined in Eq. (6) for i = i , 8i 2 N. Theorem 1 shows that we can reduce the original (n + 1)- player Stackelberg game to an n-player simultaneous-move game h N, , (ci)i. In the remaining sections, we focus on analyzing the Nash equilibrium of this multi-learner Nash game. 3. Theoretical Analysis In this section, we analyze the game h N, , (ci)i. As presented in Eq. (6), there is an inverse of a complicated matrix to compute the best response of the attacker. Hence, the cost function ci( i, i) shown in Eq. (7) is intractable. To address this challenge, we first derive a new game, h N, , (eci)i with tractable cost function for its players, to approximate h N, , (ci)i. Afterward, we analyze existence and uniqueness of the Nash Equilibirum of h N, , (eci)i. 3.1. Approximation of h N, , (ci)i We start our analysis by computing (λI + Pn presented in Eq. (6). Let matrix An = λI + Pn i , and A i = λI + P j . Then, An = A i + i > i . Similarly, let matrix Bn = λX + z Pn i , and B i = λX + z P j , which implies that Bn = B i + z > i The best response of the attacker can then be rewritten as X = Bn A 1 n . We then obtain the following results. Lemma 2. An and A i satisfy 1. An and A i are invertible, and the corresponding in- vertible matrices, A 1 i , are positive definite. Proof. The proof is included in the supplementary document. Adversarial Regression with Multiple Learners Lemma 2 allows us to relax (X ( i, i) i, y) as follows: (X ( i, i) i, y) (B i A 1 λ2 ||z y||2 Proof. Firstly, by using Sherman-Morrison formula we have X i = Bn A 1 = (B i + z > i i B i A 1 = (B i + z > (X i, y) = || Bn A 1 2 = ||(B i + z > 2 = ||B i A 1 i i y + (z y) > i i, y) + ||z y||2 By using Lemma 2, we have ( > i i)2 1 λ2 ( > which completes the proof. Note that in Eq. (9), B i and A i only depend on { j}j6=i. Hence, the RHS of Eq. (9) is a strictly convex function with respect to i. Lemma 3 shows that (X ( i, i) i, y) can be relaxed by moving i out of X ( i, i) and adding a regularizer ( > i i)2 with its coefficient ||z y||2 2 λ2 . Motivated by this method, we iteratively relax (X ( i, i) i, y) by adding corresponding regularizers. We now identify a tractable upper bound function for ci( i, i). ci( i, i) ci( i, i) = (X i, y) + β λ2 ||z y||2 where is a positive constant and < +1. Proof. We prove by extending the results in Lemma 3 and iteratively relaxing the cost function. The details are included in the supplementary material. As represented in Eq. (10), ci( i, i) is strictly convex with respect to i and j(8j 6= i). We then use the game h N, , ( ci)i as an approximation of h N, , (ci)i. Let eci( i, i) = ci( i, i) = (X i, y) + β λ2 ||z y||2 then h N, , (eci)i has the same Nash equilibrium with h N, , ( ci)i if one exists, as adding or deleting a constant term does not affect the optimal solution. Hence, we use h N, , (eci)i to approximate h N, , (ci)i, and analyze the Nash equilibrium of h N, , (eci)i in the remaining sections. 3.2. Existence of Nash Equilibrium As introduced in Section 2, each learner has identical action spaces, and they are trained with the same dataset. We exploit this symmetry to analyze the existence of a Nash equilibrium of the approximation game h N, , (eci)i. We first define a Symmetric Game (Cheng et al., 2004): Definition 4 (Symmetric Game). An n-player game is symmetric if the players have the same action space, and their cost functions ci( i, i) satisfy ci( i, i) = cj( j, j), 8i, j 2 N (12) if i = j and i = j. In a symmetric game h N, , (eci)i it is natural to consider a Symmetric Equilibrium: Definition 5 (Symmetric Equilibrium). An action profile { i=1 of h N, , (eci)i is a symmetric equilibrium if it is a Nash equilibrium and j , 8i, j 2 N. We now show that our approximate game is symmetric, and always has a symmetric Nash equilibrium. Theorem 3 (Existence of Nash Equilibrium). h N, , (eci)i is a symmetric game and it has at least one symmetric equilibrium. Proof. As described above, the players of h N, , (eci)i use the same action space and complete information of others. Hence, the cost function ci is symmetric, making h N, , (eci)i a symmetric game. As h N, , (eci)i has nonempty, compact and convex action space, and the cost function eci is continuous in { i}n i=1 and convex in i, according to Theorem 3 in Cheng et al. (2004), h N, , (eci)i has at least one symmetric Nash equilibrium. Adversarial Regression with Multiple Learners 3.3. Uniqueness of Nash Equilibrium While we showed that the approximate game always admits a symmetric Nash equilibrium, it leaves open the possibility that there may be multiple symmetric equilibria, as well as equilibria which are not symmetric. We now demonstrate that this game in fact has a unique equilibrium (which must therefore be symmetric). Theorem 4 (Uniqueness of Nash Equilibrium). h N, , (eci)i has a unique Nash equilibrium, and this unique NE is symmetric. Proof. We have known that h N, , (eci)i has at least one NE, and each learner has an nonempty, compact and convex action space . Hence, we can apply Theorem 2 and Theorem 6 of Rosen (1965). That is, for some fixed {ri}n i (0 < ri < 1, Pn i=1 ri = 1), if the matrix in Eq. (13) is positive definite, then h N, , (eci)i has a unique NE. r1r 1, 1ec1( ) . . . r1r 1, nec1( ) ... ... rnr n, 1ecn( ) . . . rnr n, necn( ) (13) We first let r1 = r2 = ... = rn = 1 n and decompose Jr( ) as follows, n P + 2β||z y||2 2 λ2n (Q + S + T), (14) where P and Q are block diagonal matrices such that Pii = X>X, Pij = 0, Qii = 4 i > i i I and Qij = 0, 8i, j 2 N, j 6= i. S and T are block symmetric matrices such that Sii = > i i I, Sij = > i j I, Tii = P j and Tij = j > i , 8i, j 2 N, j 6= i. Next, we prove that P is positive definite, and Q, S and T are positive semi-definite. Hence, Jr( ) is positive definite, which indicates that h N, , (eci)i has a unique NE. As Theorem 3 points out, the game has at least one symmetric NE. Therefore, the NE is unique and must be symmetric. Due to space limitation the details of this proof are included in the supplementary material. 4. Computing the Equilibrium Having shown that h N, , (eci)i has a unique symmetric Nash equilibrium, we now consider computing its solution. We exploit the symmetry of the game which enables to reduce the search space of the game to only symmetric solutions. Particularly, we derive the symmetric Nash equilibrium of h N, , (eci)i by solving a single convex optimization problem. We obtain the following result. Theorem 5. Let f( ) = (X , y) + β(n + 1) 2λ2 ||z y||2 2( > )2, (15) Then, the unique symmetric NE of h N, , (eci)i, { i=1, can be derived by solving the following convex optimization problem min 2 f( ) (16) and then letting i = , 8i 2 N, where is the solution of Eq. (16). Proof. We prove this theorem by characterizing the firstorder optimality conditions of each learner s minimization problem in Eq. (8) with ci being replaced with its approximation eci. Let { i=1 be the NE, then it satisfies i )>r ieci( i) 0, 8 2 , 8i 2 N (17) where r ieci( i) is the gradient of eci( i, i) with respect to i and is evaluated at { i=1. Then, Eq. (17) is equivalent to the equations as follows: 1) 0, 8 2 , j , 8j 2 N \ {1} (18) The reasons are: first, any solution of Eq. (17) satisfies Eq. (18), as { i=1 is symmetric; Second, any solution of Eq. (18) also satisfies Eq. (17). By definition of symmetric game, if j , then r 1ec1( 1) = r jecj( j), and we have j )>r jecj( j), 8 2 , 8j 2 N \ {1} Hence, Eq. (17) and Eq. (18) are equivalent. Eq. (18) can be further rewritten as 1=...= n 0, 8 2 . (19) We then let 1) = r 1ec1( 1 y) + 2β(n + 1) λ2 ||z y||2 1) where f( ) is defined in Eq. (15). Hence, we have 1) 0, 8 2 , (21) This means that 1 is the solution of the optimization problem in Eq.(16) which finally completes the proof. A deeper look at Eq. (15) reveals that the Nash equilibrium can be obtained by each learner independently, without knowing others actions. This means that the Nash equilibrium can be computed in a distributed manner while the convergence is still guaranteed. Hence, our proposed approach is highly scalable, as increasing the number of learners does not impact the complexity of finding the Nash equilibrium. We investigate the robustness of this equilibrium both using theoretical analysis and experiments in the remaining sections. Adversarial Regression with Multiple Learners 5. Robustness Analysis We now draw a connection between the multi-learner equilibrium in the adversarial setting, derived above, and robustness, in the spirit of the analysis by Xu et al. (2009). Specifically, we prove the equivalence between Eq. (16) and a robust linear regression problem where data is maliciously corrupted by some disturbance 4. Formally, a robust linear regression solves the following problem: 42U ||y (X + 4) ||2 where the uncertainty set U = {4 2 Rm d | 4T 4 = G : |Gij| c| i j| 8i, j}, with c = β(n+1) 2λ2 ||z y||2 2. Note that is a vector and i is the i-th element of . From a game-theoretic point of view, in training phase the defender is simulating an attacker. The attacker maximizes the training error by adding disturbance to X. The magnitude of the disturbance is controlled by a parameter c = β(n+1) 2λ2 ||z y||2 2. Consequently, the robustness of Eq. (22) is guaranteed if and only if the magnitude reflects the uncertainty interval. This sheds some light on how to choose λ, β and z in practice. One strategy is to overestimate the attacker s strength, which amounts to choosing small values of λ, large values of β and exaggerated target z. The intuition of this strategy is to enlarge the uncertainty set so as to cover potential adversarial behavior. In Experiments section we will show this strategy works well in practice. Another insight from Eq. (22) is that the fundamental reason MLSG is robust is because it proactively takes adversarial behavior into account. Theorem 6. The optimal solution of the problem in Eq. (16) is an optimal solution to the robust optimization problem in Eq. (22). Proof. Fix , we show that max 42U ||y (X + 4) ||2 2 = ||y X ||2 The left-hand side can be expanded as: max 42U ||y (X + 4) ||2 42U ||y X 4 ||2 42U ||y X ||2 42U ||4 ||2 42U ||y X ||2 (substitute 4T 4 = G) i |2Gii + 2 Now we define 4 = [pc i is the i-th element of and u is defined as: ||y X ||2 , if y 6= X any vector with unit L2 norm, otherwise Then we have: max 42U ky (X + 4) k2 ||y (X + 4 ) ||2 2 =||y X 4 ||2 (u is in the same direction as y X ) 6. Experiments As previously discussed, a dataset is represented by (X, y), where X is the feature matrix and y is the vector of labels. We use (xj, yj) to denote the j-th instance and its corresponding label. The dataset is equally divided into a training set (Xtrain, ytrain) and a testing set (Xtest, ytest). We conducted experiments on three datasets: Wine Quality (redwine),PDF malware (PDF), and Boston Housing Market (boston). The number of learners is set to 5. Due to space limitation the experimental results for the boston dataset are included in supplement. The Wine Quality dataset (Cortez et al., 2009) contains 1599 instances and each instance has 11 features. Those features are physicochemical and sensory measurements for wine. The response variables are quality scores ranging from 0 to 10, where 10 represents for best quality and 0 for least quality. The PDF malware dataset consists of 18658 PDF files collected from the internet. We employed an opensourced tool mimicus1 to extract 135 real-valued features 1https://github.com/srndic/mimicus Adversarial Regression with Multiple Learners from PDF files (Šrndic & Laskov, 2014). We then applied peepdf 2 to score each PDF between 0 and 10, with a higher score indicating greater likelihood of being malicious. Throughout, we abbreviate our proposed approach as MLSG, and compare it to three other algorithms: ordinary least squares (OLS) regression, as well as Lasso, and Ridge regression (Ridge). Lasso and Ridge are ordinary least square with L1 and L2 regularizations. In our evaluation, we simulate the attacker for different values of β (the probability that a given instance is maliciously manipulated). The specific attack targets z vary depending on the dataset; we discuss these below. For our evaluation, we compute model parameters (for the equilibrium, in the case of MLSG) on training data. We then use test data to compute optimal attacks, characterized by Eq. (6). Let X0 test be the test feature matrix after adversarial manipulation, ˆy A test the associated predicted labels on manipulated test data, ˆytest predicted labels on untainted test data, and ytest the ground truth labels for test data. We use root expected mean square error (RMSE) as an evaluation metric, where the expectation is with respect to the probability β of a particular instance being maliciously manipulated: q test ytest)T (ˆy A test ytest)+(1 β)(ˆytest ytest)T (ˆytest ytest) N , where N is the size of the test data. The redwine dataset: Recall that the response variables in redwine dataset are quality scores ranging from 0 to 10. We simulated an attacker whose target is to increase the overall scores of testing data. In practice this could correspond to the scenario that wine sellers try to manipulate the evaluation of third-party organizations. We formally define the attacker s target as z = y + , where y is the ground-truth response variables and is a real-valued vector representing the difference between the attacker s target and the ground-truth. Since the maximum score is 10, any element of z that is greater than 10 is clipped to 10. We define to be homogeneous (all elements are the same); generalization to heterogeneous values is direct. The mean and standard deviation of y are µr = 5.64 and σr = 0.81. We let = 5σr 1, where 1 is a vector with all elements equal to one. The intuition for this definition is to simulate the generating process of adversarial data. Specifically, by setting the attacker s target to an unrealistic value (i.e. in current case outside the 3σr of µr), the generated adversarial data X 0 is supposed to be intrinsically different from X. For ease of exposition we use the term defender to refer to MLSG. Remember that in Eq.(11) there are three hyper-parameters in the defender s loss function: λ, β, and z. λ is the regularization coefficient in the attacker s loss function shown in Eq.(4). It is negatively proportional to the attacker s strength. 2https://github.com/rohit-dua/pee PDF β is the probability of a test data being malicious. z is the predication targets of the attacker. In practice these three hyper-parameters are externally set by the attacker. In the first experiment below we assume the defender knows the values of these three hyper-parameters, which corresponds to the best case. The result is shown in Figure 1. Each bar is averaged over 50 runs, where at each run we randomly sampled training and test data. The regularization parameters of Lasso and Ridge were selected by cross-validation. Figure 1 demonstrates that MLSG approximate equilibrium solution is significantly more robust than conventional linear regression learning, with and without regularization. Figure 1. RMSE of y0 and y on redwine dataset. The defender knows λ, β, and z. In the second experiment we relaxed the assumption that the defender knows λ, β and z, and instead simulated the practical scenario that the defender obtains estimates for these (for example, from historical attack data), but the estimates have error. We denote by ˆλ = 0.5 and ˆβ = 0.8 the defender s estimates of the true λ and β.3 Remember that β is the probability of an instance being malicious and λ is negatively proportional to the attacker s strength. So the estimation characterizes a pessimistic defender that is expecting very strong attacks. We experimented with two kinds of estimation about z: 1) the defender overestimates z: ˆz = y + t1, where t is a random variable sampled from a uniform distribution over [5σr, 10]; and 2) the defender underestimates z: ˆz = y + t1, where t is sampled from [0, 5σr]. Due to space limitations we only present the results for the latter; the former can be found in the supplementary materials. In Figure 2 the y-axis represents the actual values of λ, and the x-axis represents the actual values of β. The color bar on the right of each figure visualizes the average RMSE. Each cell is averaged over 50 runs. The result shows that even if there is a discrepancy between the defender s 3We tried alternative values of ˆλ and ˆβ, and the results are consistent. Due to space limitations we include them in supplemental materials. Adversarial Regression with Multiple Learners estimation and the actual adversarial behavior, MLSG is consistently more robust than the other approaches. Figure 2. The average RMSE across different values of actual λ and β on redwine dataset. Upper Left: MLSG; Upper Right: Lasso; Lower Left: Ridge; Lower Right: OLS. The PDF dataset: The response variables of this dataset are malicious scores ranging between 0 and 10. The mean and standard deviation of y are µp = 5.56 and σp = 2.66. Instead of letting the be non-negative as in previous two datasets, the attacker s target is to descrease the scores of malicious PDFs. Consequently, we define = 2σp 1M, where M is the set of indices of malicious PDF and 1M is a vector with only those elements indexed by M being one and others being zero. Our experiments were conducted on a subset (3000 malicious PDF and 3000 benign PDF) randomly sampled from the original dataset. We evenly divided the subset into training and testing sets. We applied PCA to reduce dimensionality of the data and selected the top-10 principal components as features. The result for best case is displayed in Figure 3. Notice that when β = 0, MLSG is less robust than Lasso. This is to be expected, as β = 0 corresponds to non-adversarial data. Similarly as before we relaxed the assumption that the defender knows λ, β and z and let the defender s estimation of the true λ and β be ˆλ = 1.5 and ˆβ = 0.5. We also experimented with both overestimation and underestimation of z. The defender s estimation is ˆz = y t1M. For overestimation setting t is sampled from [2σp, 3σp], and for underestimation setting it is sampled from [σp, 2σp]. The result for underestimated ˆz is showed in Figure 4. Notice that in the upper left plot of Figure 4 the area inside the blue rectangle corresponds to those cases where ˆλ and ˆβ are overestimated and they are more robust than the remaining underestimated cases. Similar patterns can be observed in Figure 2. This further supports our claim that it is advantageous to overestimate adversarial behavior. Figure 3. RMSE of y0 and y on PDF dataset. The defender knows λ, β, and z. Figure 4. The average RMSE across different values of actual λ and β on PDF dataset. Upper Left: MLSG; Upper Right: Lasso; Lower Left: Ridge; Lower Right: OLS. 7. Conclusion We study the problem of linear regression in adversarial settings involving multiple learners learning from the same or similar data. In our model, learners first simultaneously decide on their models (i.e., learn), and an attacker then modifies test instances to cause predictions to err towards the attacker s target. We first derive an upper bound on the cost functions of all learners, and the resulting approximate game. We then show that this game has a unique symmetric equilibrium, and present an approach for computing this equilibrium by solving a convex optimization problem. Finally, we show that the equilibrium is robust, both theoretically, and through an extensive experimental evaluation. Adversarial Regression with Multiple Learners Acknowledgements We would like to thank Shiying Li in the Department of Mathematics at Vanderbilt University for her valuable and constructive suggestions for the proof of Theorem 4. This work was partially supported by the National Science Foundation (CNS-1640624, IIS-1526860, IIS-1649972), Office of Naval Research (N00014-15-1-2621), Army Research Office (W911NF-16-1-0069), and National Institutes of Health (R01HG006844-05). Alfeld, S., Zhu, X., and Barford, P. Data poisoning attacks against autoregressive models. In AAAI Conference on Artificial Intelligence, 2016. Brückner, M. and Scheffer, T. Stackelberg games for ad- versarial prediction problems. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 547 555, 2011. Cheng, S.-F., Reeves, D. M., Vorobeychik, Y., and Wellman, M. P. Notes on equilibria in symmetric games. In International Workshop on Game Theoretic and Decision Theoretic Agents, pp. 71 78, 2004. Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. Modeling wine preferences by data mining from physicochemical properties. Decision Support Systems, 47(4): 547 553, 2009. Dalvi, N., Domingos, P., Mausam, Sanghai, S., and Verma, D. Adversarial classification. In SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 99 108, 2004. Grosshans, M., Sawade, C., Brückner, M., and Scheffer, T. Bayesian games for adversarial regression problems. In International Conference on International Conference on Machine Learning, pp. 55 63, 2013. Laszka, A., Lou, J., and Vorobeychik, Y. Multi-defender strategic filtering against spear-phishing attacks. In AAAI Conference on Artificial Intelligence, 2016. Li, B. and Vorobeychik, Y. Feature cross-substitution in adversarial classification. In Advances in Neural Information Processing Systems, pp. 2087 2095, 2014. Li, B. and Vorobeychik, Y. Scalable optimization of ran- domized operational decisions in adversarial classification settings. In Conference on Artificial Intelligence and Statistics, 2015. Lowd, D. and Meek, C. Adversarial learning. In ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 641 647. ACM, 2005. Rosen, J. B. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica, pp. 520 534, 1965. Russu, P., Demontis, A., Biggio, B., Fumera, G., and Roli, F. Secure kernel machines against evasion attacks. In ACM Workshop on Artificial Intelligence and Security, pp. 59 69, 2016. Smith, A., Lou, J., and Vorobeychik, Y. Multidefender security games. IEEE Intelligent Systems, 32(1):50 60, 2017. Šrndic, N. and Laskov, P. Practical evasion of a learning- based classifier: A case study. In 2014 IEEE Symposium on Security and Privacy, pp. 197 211, 2014. Stevens, D. and Lowd, D. On the hardness of evading combinations of linear classifiers. In ACM Workshop on Artificial Intelligence and Security, 2013. Vorobeychik, Y., Mayo, J. R., Armstrong, R. C., and Ruthruff, J. Noncooperatively optimized tolerance: Decentralized strategic optimization in complex systems. Physical Review Letters, 107(10):108702, 2011. Xu, H., Caramanis, C., and Mannor, S. Robust regression and lasso. In Advances in Neural Information Processing Systems, pp. 1801 1808, 2009. Zhou, Y., Kantarcioglu, M., Thuraisingham, B. M., and Xi, B. Adversarial support vector machine learning. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1059 1067, 2012.