<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Robust learning under clean-label attack</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>2021</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10289073</idno>
					<idno type="doi"></idno>
					<title level='j'>Conference on Learning Theory</title>
<idno></idno>
<biblScope unit="volume">34</biblScope>
<biblScope unit="issue"></biblScope>					

					<author>A. Blum</author><author>S. Hanneke</author><author>J. Qian</author><author>H. Shao</author><author>M. Belkin</author><author>S. Kpotufe</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[We study the problem of robust learning under clean-label data-poisoning attacks, where the at-tacker injects (an arbitrary set of) correctly-labeled examples to the training set to fool the algorithm into making mistakes on specific test instances at test time. The learning goal is to minimize the attackable rate (the probability mass of attackable test instances), which is more difficult than optimal PAC learning.   As we show,  any robust algorithm with diminishing attackable rate can achieve the optimal dependence on ε in its PAC sample complexity,  i.e., O(1/ε). On the other hand, the attackable rate might be large even for some optimal PAC learners, e.g., SVM for linear classifiers.  Furthermore, we show that the class of linear hypotheses is not robustly learnable when the data distribution has zero margin and is robustly learnable in the case of positive margin but requires sample complexity exponential in the dimension.  For a general hypothesis class with bounded VC dimension, if the attacker is limited to add at most t >0 poison examples, the optimal robust learning sample complexity grows almost linearly with t.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">Introduction</head><p>Data poisoning is an attack on machine learning algorithms where the attacker adds examples to the training set with the goal of causing the algorithm to produce a classifier that makes specific mistakes the attacker wishes to induce at test time. In this paper, we focus on clean-label attacks in which an attacker, with knowledge of the training set S and the test instance x, injects a set of examples labeled by the target function into the training set with the intent of fooling the learner into misclassifying the test instance x. This type of attack is called a clean-label attack because the attacker can only add correctly-labeled examples to the training set, and it has been proposed and studied empirically by <ref type="bibr">Shafahi et al. (2018)</ref>.</p><p>In the realizable setting when the target function belongs to the hypothesis class H, any empirical risk minimizer (ERM) will achieve error of O( VCdim(H) m ) with training set size m. This means that an ERM learner will still have error rate at most O( VCdim(H) m ) even in the presence of a clean-label attack; i.e., the attacker cannot significantly increase the overall error rate. However, an attacker could still cause the ERM learner to make specific mistakes that the attacker wishes. For example, consider an ERM learner for the hypothesis class of intervals over [0, 1] that predicts the positive interval of maximum length consistent with the training data, in the case that the target function labels all of [0, 1] negative. Then any test instance not in the training set is attackable for this ERM learner by an adversary that adds enough poison examples so that the interval that the test instance is in becomes the largest interval in the training set. On the other hand, for any target interval, for the ERM learner that outputs the smallest consistent interval, the attackable test instances will only have probability mass O(1/m) (see Example 1 for more details). Also, notice that for the hypothesis class of threshold functions over [0, &#8734;), any ERM learner has a small portion of attackable test instances because the disagreement region of all consistent hypotheses is small and only test instances in the disagreement region are attackable.</p><p>From these examples, we can see that given an ERM learning algorithm A and a training set S, the probability mass of the attackable region (the set of attackable test instances) is at least as large as the error rate of the ERM learner and no greater than the disagreement region of all consistent hypotheses, and it depends on the specific algorithm A. In this paper, we study the problem of whether we can obtain a small rate of attackable test instances in binary classification. In the process we find interesting connections to existing literature on the sample complexity of PAC learning, and complexity measures arising in that literature. Specifically, we study this problem in the realizable setting as it is unclear how to best define "clean-label" in the agnostic case.</p><p>Related work Clean-label data-poisoning attacks have been studied extensively in the literature <ref type="bibr">(Shafahi et al., 2018;</ref><ref type="bibr">Suciu et al., 2018)</ref>, and <ref type="bibr">Shafahi et al. (2018)</ref> show that clean-label attacks can be very effective on neural nets empirically. For example, <ref type="bibr">Shafahi et al. (2018)</ref> show that in natural image domains, given the knowledge of the training model and of the test point to be attacked, the attacker can cause the model retrained with an injection of clean-label poisoned data to misclassify the given test instance with high success rate. Moreover, the attacker is able to succeed even though the overall error rate of the trained classifier remains relatively unchanged. <ref type="bibr">Mahloujifar and Mahmoody (2017)</ref>; <ref type="bibr">Mahloujifar et al. (2018</ref><ref type="bibr">Mahloujifar et al. ( , 2019b</ref>) study a class of cleanlabel poisoning attacks called p-tampering attacks, where the attacker can substitute each training example with a correctly labeled poison example with independent probability p, and its variants. <ref type="bibr">Mahloujifar and Mahmoody (2019)</ref>; <ref type="bibr">Mahloujifar et al. (2019a)</ref>; <ref type="bibr">Etesami et al. (2020)</ref> consider a more powerful adversary that can attack training examples of its choosing (rather than chosen at random) and show that the attacker can increase the probability of failing on a particular test instance from any non-negligible probability &#8486;(1/ poly(m)) to &#8776; 1 by replacing O( &#8730; m) training examples with other correctly labeled examples. In contrast, in our setting the attacker cannot modify any of the existing training examples and can only add new ones. In addition, we mainly focus on attacks with an unlimited budget.</p><p>Data poisoning without requiring the poisoned data to be clean has been studied extensively (see <ref type="bibr">Biggio et al. (2012)</ref>; <ref type="bibr">Barreno et al. (2006)</ref>; <ref type="bibr">Papernot et al. (2016)</ref>; <ref type="bibr">Steinhardt et al. (2017)</ref> for a non-exhaustive list). Robustness to data poisoning with a small portion of poison examples has been studied by <ref type="bibr">Ma et al. (2019)</ref>; <ref type="bibr">Levine and Feizi (2020)</ref>. The concurrent work of <ref type="bibr">Gao et al. (2021)</ref> studies the instance-targeted poisoning risk (which is the probability mass of the attackable region in the classification task) by various attacker classes, which have a budget controlling the amount of training data points they can change. They mainly focus on the relationship between robust learnability and the budget.</p><p>There are other studied attacking methods, including perturbation over training examples <ref type="bibr">(Koh and Liang, 2017)</ref>, perturbation over test examples <ref type="bibr">(Szegedy et al., 2013;</ref><ref type="bibr">Goodfellow et al., 2014;</ref><ref type="bibr">Bubeck et al., 2019;</ref><ref type="bibr">Cullina et al., 2018;</ref><ref type="bibr">Montasser et al., 2019</ref><ref type="bibr">Montasser et al., , 2020) )</ref> and etc. Another different notion of robust learning is studied by <ref type="bibr">Xu and Mannor (2012)</ref>, where the data set is partitioned into several subsets and the goal is to ensure the losses of instances falling into the same subset are close. Another line of related work is covariate shift, where the training distribution is different from the test distribution (see <ref type="bibr">Quionero-Candela et al. (2009)</ref> for an extensive study).</p><p>Notation For any vectors u, v, we let u denote the 2 norm of u and &#952;(u, v) denote the angle of u and v. We denote by e i &#8712; R n the one-hot vector with the i-th entry being one and others being zeros. We let B n (c, r) = {x| x -c &#8804; r} denote the the ball with radius r centered at c &#8712; R n in the n-dimensional space and &#915; n (c, r) denote the sphere of B n (c, r). We omit the supscript n when it is clear from the context. For any a, b &#8712; R, denote a &#8743; b = min(a, b) and a &#8744; b = max <ref type="bibr">(a, b)</ref>. We use ln to represent natural logarithms and log to represent logarithms with base 2. Given a data set S = {(x 1 , y 1 ), . . . , (x m , y m )} with size m, for any hypothesis h, we let err S (h) = 1 m m i=1 1[h(x i ) = y i ] denote the empirical error of h over S. For a data distribution D, we let err D (h) = E (x,y)&#8764;D <ref type="bibr">[1[h(x)</ref> = y]] denote the error of h. For any A &#8838; X , we let P D (A) = P (x,y)&#8764;D (x &#8712; A) denote the probability mass of A. The subscript D is omitted when it is clear from the context. For any data set S, we let S X = {x|(x, y) &#8712; S} and for (x, y) &#8764; D, we let D X denote the marginal distribution of x. For a finite set of hypotheses H, we let Major(H) denote the majority vote of H and for simplicity denote Major(H, x) = Major(H)(x) 1[ h&#8712;H h(x) &#8805; |H|/2 ].</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Problem setup and summary of results</head><p>Let X denote the instance space and Y = {0, 1} denote the label space. Given a hypothesis class H &#8838; Y X , we study the realizable case where there exists a deterministic target function h * &#8712; H such that the training set and the test set are realized by h * . Let D h * = {(x, h * (x))|x &#8712; X } denote the data space where every instance is labeled by h * . A learning algorithm A is a map (possibly including randomization), from a labeled data set S (an unordered multiset) of any size, to a hypothesis h, and for simplicity we denote by A(S, x) = A(S)(x) the prediction of A(S) at an instance x. An attacker Adv maps a target function h * , a training data set S trn and a specific test instance x to a data set Adv(h * , S trn , x) (a multiset) and injects Adv(h * , S trn , x) into the training set with the intent of making the learning algorithm misclassify x. We call Adv a clean-label attacker if Adv(h * , S trn , x) is consistent with h * . Then for any deterministic algorithm A, we say a point x &#8712; X is attackable if there exists a clean-label attacker Adv such that A(S trn &#8746; Adv(h * , S trn , x), x) = h * (x) .</p><p>To be clear, we are defining S trn &#8746; Adv(h * , S trn , x) as an unordered multiset. Formally, we define clean-label attackable rate as follows.</p><p>Definition 1 (clean-label attackable rate) For a target function h * , a training data set S trn and a (possibly randomized) algorithm A, for any distribution D over D h * , the attackable rate by Adv for (h * , S trn , A) is defined as</p><p>The clean-label attackable rate is defined by the supremum over all clean-label attackers, i.e., atk D (h * , S trn , A) sup Adv atk D (h * , S trn , A, Adv) .</p><p>Then we define our learning problem as follows.</p><p>Definition 2 ((&#949;, &#948;)-robust learnability) For any &#949;, &#948; &#8712; (0, 1), the sample complexity of (&#949;, &#948;)robust learning of H, denoted by M rbst (&#949;, &#948;), is defined as the smallest m &#8712; N for which there exists an algorithm A such that for every target function h * &#8712; H and data distribution over D h * , with probability at least 1 -&#948; over S trn &#8764; D m ,</p><p>It is direct to see that the error of A(S trn ) is the attackable rate by attacker Adv 0 which injects an empty set to the training set, i.e., Adv 0 (&#8226;) = &#8709;. Therefore, for any algorithm A, we have</p><p>which indicates any hypothesis class that is not PAC learnable is not robust learnable. For any deterministic A, let us define ATK(h * , S trn , A, Adv) {x &#8712; X |A(S trn &#8746; Adv(h * , S trn , x), x) = h * (x)} the attackable region by Adv. For any ERM learner and any clean-label attacker Adv, we have ATK(h * , S trn , ERM, Adv) &#8838; DIS(VS H,Strn ), where VS H,Strn is the version space of S trn , i.e., the set of all hypotheses in H that classify S trn correctly and DIS(VS </p><p>For S trn = {(x 1 , y 1 ), . . . , (x m , y m )}, w.l.o.g. assume that x 1 &#8804; . . . &#8804; x m and let x 0 = 0, x m+1 = 1 for notation simplicity. Then for any x &#8712; (x i , x i+1 ), the attacker can add enough poison data points to intervals {(x j , x j+1 )} j =i to make (x i , x i+1 ) be the interval with the maximum length. Therefore, so long as D has no point masses, A 2 's attackable rate is atk D (h * , S trn , A 2 ) = P D (DIS(VS H,Strn )) = 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Main results</head><p>We summarize the main contributions of this work.</p><p>&#8226; In Section 3, we present results on robust learnability under assumptions based on some known structural complexity measures, e.g., VC dimension d = 1, hollow star number k o = &#8734;, etc. In addition, we show that all robust algorithms can achieve optimal dependence on &#949; in their PAC sample complexity.</p><p>&#8226; In Section 4, we show that the n-dimensional linear hypothesis class with n &#8805; 2 is not (&#949;, &#948;)robust learnable. Then we study the linear problem in the case where the data distribution D has margin &#947; &gt; 0. We propose one algorithm with sample complexity O(n(2/&#947;) n log(2/&#947;)) and show that the optimal sample complexity is e &#8486;(n) . We propose another algorithm in 2-dimensional space with sample complexity O(log(1/&#947;) log log(1/&#947;)). We also show that even in the case where &#947; is large and the attacker is only allowed to inject one poison example into the training set, SVM requires at least e &#8486;(n) samples to achieve low attackable rate. ). We also show that there exists a hypothesis class with VC dimension d such that any algorithm requires &#8486;( dt &#949; ) samples to achieve &#949; attackable rate.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">Connections to some known complexity measures and PAC learning</head><p>In this section, we analyze the robust learnability of hypothesis classes defined by a variety of known structural complexity measures. For some of these, we show they have the good property that there exists an algorithm such that adding clean-label points can only change the predictions on misclassified test instances and thus, the algorithm can achieve atk(h * , S trn , A) &#8804; err(A(S trn )).</p><p>For some other structure, we prove that there will be a large attackable rate for any consistent proper learner. We also show the connection to optimal PAC learning in Section 3.2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1.">Connections to some known complexity measures</head><p>Hypothesis classes with VC dimension d = 1 are (&#949;, &#948;)-robust learnable. First, w.l.o.g., assume that for every x = x &#8712; X , there exists h &#8712; H such that h(x) = h(x ) (otherwise, operate over the appropriate equivalence classes). Then we adopt the partial ordering &#8804; H f for any f &#8712; H over X proposed by <ref type="bibr">Ben-David (2015)</ref> defined as follows.</p><p>By Lemma 5 of <ref type="bibr">Ben-David (2015)</ref>, &#8804; H f for d = 1 is a tree ordering. Due to this structural property of hypothesis classes with VC dimension d = 1, there is an algorithm originally proposed by Ben-David (2015) (Algorithm 4 in Appendix A.1) such that adding clean-label poison points can only narrow down the error region (the set of misclassified instances). Roughly, the algorithm finds a maximal (by &#8804; H f ) point x in the data such that h * (x ) = f (x ), and outputs the classifier labeling all x &#8804; H f x as 1 -f (x) and the rest as f (x). We show that this algorithm can robustly learn H using m samples, where</p><p>The detailed algorithm and proof are given in Appendix A.1.</p><p>For intersection-closed hypothesis classes, there is a general learning rule, called the Closure algorithm <ref type="bibr">(Helmbold et al., 1990;</ref><ref type="bibr">Auer and Ortner, 2007)</ref>. For given data S, the algorithm  if there is no positive sample and otherwise, output the consistent union of minimum number of closed intervals, each of which has minimum length. More specifically, given input (poisoned) data</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Unions of intervals are</head><p>The algorithm A can robustly learn union of intervals H k using m samples, where</p><p>The detailed proof can be found in Appendix A.2.</p><p>Hypothesis classes with finite star number are (&#949;, &#948;)-robust learnable. The star number, proposed by <ref type="bibr">Hanneke and Yang (2015)</ref>, can measure the disagreement region of the version space. </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2.">All robust learners are optimal PAC learners</head><p>There is an interesting connection between algorithms robust to clean-label poisoning attacks and the classic literature on the sample complexity of PAC learning. Specifically, we can show that any learning algorithm that is robust to clean-label poisoning attacks necessarily obtains the optimal dependence on &#949; in its PAC sample complexity: that is, O(1/&#949;). This is a very strong property, and not many such learning algorithms are known, as most learning algorithms have at least an extra log(1/&#949;) factor in their sample complexity (see e.g., <ref type="bibr">Haussler, Littlestone, and Warmuth, 1994;</ref><ref type="bibr">Auer and Ortner, 2007;</ref><ref type="bibr">Hanneke, 2009</ref><ref type="bibr">Hanneke, , 2016b,a;,a;</ref><ref type="bibr">Darnst&#228;dt, 2015;</ref><ref type="bibr">Bousquet, Hanneke, Moran, and Zhivotovskiy, 2020)</ref>. Thus, this property can be very informative regarding what types of learning algorithms one should consider when attempting to achieve robustness to clean-label poisoning attacks. This claim is formalized in the following result. Its proof is presented in Appendix A.4.</p><p>Theorem 1 Fix any hypothesis class H. Let A be a deterministic learning algorithm that always outputs a deterministic hypothesis. Suppose there exists a non-negative sequence R(m) &#8594; 0 such that, &#8704;m &#8712; N, for every target function h * &#8712; H and every distribution D over D h * , for S trn &#8764; D m , with probability at least 1/2, atk D (h * , S trn , A) &#8804; R(m). Then there exists an (R-dependent) finite constant c R such that, for every &#948; &#8712; (0, 1), m &#8712; N, h * &#8712; H, and every distribution D over D h * , for S trn &#8764; D m , with probability at least 1 -&#948;, atk D (h * , S trn , A) &#8804; c R m log 2 &#948; .</p><p>An immediate implication of this result (together with Markov's inequality) is that any deterministic A outputting deterministic predictors, if E Strn&#8764;D m [atk D (h * , S trn , A)] &#8804; R(m)/2 &#8594; 0 for all h * &#8712; H and D on D h * , then for any h * &#8712; H, D on D h * , &#948; &#8712; (0, 1), err D (A(S trn )) &#8804; c R m log 2 &#948; with probability at least 1 -&#948;. As mentioned, this is a strong requirement of the learning algorithm A; for instance, for many classes H, many ERM learning rules would have an extra log(m) factor <ref type="bibr">(Hanneke, 2016a)</ref>. This also establishes a further connection to the hollow star number, which in some cases strengthens the result mentioned above (and detailed in Appendix A). Specifically, <ref type="bibr">Bousquet, Hanneke, Moran, and Zhivotovskiy (2020)</ref> have shown that when k o = &#8734;, for any fixed &#948; sufficiently small, any proper learning algorithm has, for some infinite sequence of m values, that &#8707;h * &#8712; H and D on D h * for which, with probability greater than &#948;, err D (A(S trn )) &#8805; c log(m) m for a numerical constant c. Together with Theorem 1, this implies that for such classes, any deterministic proper learning algorithm cannot have a sequence R(m) &#8594; 0 as in the above theorem. Formally, using the fact that atk D (h * , S, A) is non-increasing in S (see the proof of Theorem 1), we arrive at the following corollary, which removes the "consistency" requirement from the result for classes with k o = &#8734; stated above, but adds a requirement of being deterministic.</p><p>Corollary 1 If k o = &#8734;, then for any deterministic proper learning algorithm A that always outputs a deterministic hypothesis, there exists a constant c &gt; 0 such that, for every m &#8712; N, &#8707;h * &#8712; H and distribution D on</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">Linear hypothesis class</head><p>In this section, we first show that n-dimensional linear classifiers</p><p>Then we study a restrictive case where the support of the data distribution has a positive margin to the boundary. We introduce two robust learners and prove a robust learning sample complexity lower bound. In addition, we also show the vulnerability of SVM.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1.">Linear hypothesis class is not robust learnable</head><p>In this section, we show that the class of linear hypotheses is not robust learnable.</p><p>Theorem 2 For n &#8805; 2, the class of linear hypotheses is not robust learnable.</p><p>Proof sketch We present the proof idea in the case of n = 3 here and for simplicity, we allow the decision boundary to be either positive or negative. The construction details of limiting the boundary to be positive and the construction for n = 2 are deferred to Appendix B.</p><p>Consider the case where X = &#915; 3 (0, 1) is the sphere of the 3-dimensional unit ball centered at the origin and the target function is uniformly randomly chosen from all linear classifiers with the decision boundary at distance 1/2 from the origin, and the boundary labeled different from 0, i.e., h * &#8764; Unif(H * ), where</p><p>. The data distribution is the uniform distribution over the intersection of the decision boundary and the sphere, i.e., D X = Unif(C w * ), where C w * = {x| w * , x -1 2 = 0} &#8745; &#915; 3 (0, 1). Then all training data come from the circle C w * and are labeled positive.</p><p>Given training data S trn &#8764; D m and a test point x 0 &#8712; C w * (not in S trn,X ), the attacker constructs a fake circle C w tangent to C w * at point x 0 , i.e., C w = {x| w , x -1 2 = 0} &#8745; &#915; 3 (0, 1) where w = 2 x 0 , w * x 0 -w * . Then the attacker adds m i.i.d. samples from the uniform distribution over C w and labels them negative. Any algorithm cannot tell which circle is the true circle and which one of {1[ w * , x -1 2 &#8805; 0], 1 -1[ w , x -1 2 &#8805; 0]} is the true target. Hence, any algorithm will misclassify x 0 with probability 1/2. Algorithm 1 Robust algorithm for 2-dimensional linear classifiers 1: input: data S 2: initialize l &#8592; 0, h &#8592; 2&#960; and &#946; &#8592; l+h </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.">Linear hypothesis class is robust learnable under distribution with margin</head><p>In this section, we discuss linear classifiers in the case where the distribution has a positive margin. Specifically, considering the instance space X &#8838; B n (0, 1), we limit the data distribution D to satisfy that &#8704;(x, y) &#8712; supp(D), (2y -1)( w * , x + b * ) &#8805; &#947; w * /2 for some margin &#947; &#8712; (0, 2] and target function h</p><p>It is easy to check that such a V always exists. Then given input data S, the learner outputs a classifier:</p><p>predicting randomly. Note that Adv does not necessarily need to be restricted to such margin.</p><p>Theorem 3 The algorithm can robustly learn linear classifiers with margin &#947; using m samples where</p><p>Then with probability at least 1</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.2.">A LEARNER FOR n = 2</head><p>In the 2-dimensional case, the hypothesis class can be represented as</p><p>Then we propose a robust algorithm based on binarysearch for the target direction &#946; * as shown in Algorithm 1.</p><p>denote the maximum distance between the boundary and two parallel lines (on positive side and negative side respectively) such that the probability between the boundary and either line is no greater than &#949; . With probability at least 1 -&#948; over S trn &#8764; D m , Algorithm 1 achieves</p><p>Proof sketch First, by uniform convergence bound in PAC learning <ref type="bibr">(Blumer et al., 1989)</ref>, when m &#8805; 24 &#949; log 13 &#949; + 4 &#949; log 2 &#948; , every linear classifier consistent with S trn has error no greater than &#949; . For any fixed &#946;, the probability mass of union of error region of all (&#946;, b) consistent with the training data is bounded by 2&#949; . Then given a target (&#946; * , b * ), the binary-search path of &#946; is unique and adding clean-label poison examples will only change the depth of search. When h -l &lt; arctan(f (&#949; )/2), the attackable rate caused by deeper search is at most 2&#949; . Combining these results together proves the theorem. The formal proof of Theorem 4 is included in Appendix C.</p><p>Theorem 5 For any &#947; &#8712; (0, 2], Algorithm 1 can (&#949;, &#948;)-robustly learn 2-dimensional linear classifiers with margin &#947; using m samples where</p><p>Theorem 5 is the immediate result of Theorem 4 as</p><p>SVM is a well-known optimal PAC learner for linear hypothesis class <ref type="bibr">(Bousquet et al., 2020)</ref>. In this section, we show that even in the case where &#947; &#8805; 1/8 and the attacker is limited to add at most one poison point, SVM requires e &#8486;(n) /&#949; samples to achieve &#949; attackable rate.</p><p>Theorem 6 For n-dim linear hypothesis class, for any &#949; &lt; 1/16, there exists a target h * &#8712; H and a distribution D over D h * with margin &#947; = 1/8 such that E Strn&#8764;D m [atk D (h * , S trn , SVM)] &gt; &#949; when the sample size m &lt; e n/128 768&#949; &#8744; 1 8&#949; . Proof sketch Consider the case where</p><p>is the union of a half sphere and a point -e 1 . The target function is h * = 1[ w * , x &#8805; -&#947;/2] with w * = e 1 and margin &#947; = 1/8. Note that h * labels all points on the half sphere positive and -e 1 negative. Then we define the data distribution D X by putting probability mass 1 -8&#949; on -e 1 and putting probability mass 8&#949; uniformly on the half sphere.</p><p>Then we draw training set S trn &#8764; D m and a test point (x 0 , y 0 ) &#8764; D. Condition on that x 0 is on the half sphere, with high probability, x 0 , w * &#8804; 1/8. Then we define two base vectors v 1 = w * and v 2 = x 0 -x 0 ,w * w *</p><p>x 0 -x 0 ,w * w * in the 2-dimensional space defined by w * and x 0 . With high probability over the choice of S trn , for all positive training examples x on the half sphere, we have x, v 1 &#8804; 1/8 and x, v 2 &#8804; 1/8. Then the attacker injects a poison point at -&#947;v 1 + 1 -&#947; 2 v 2 , which is closer to x 0 than all the positive samples in S trn . Since the poison point is classified as negative by the target function, SVM will misclassify x 0 as negative. The detailed proof can be found in Appendix D.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2.4.">LOWER BOUND</head><p>Here we show that robust learning of linear hypothesis class under distribution with margin &#947; &gt; 0 requires sample complexity e &#8486;(n) /&#949;.</p><p>Theorem 7 For n-dimensional linear hypothesis class with n &gt; 256, for any &#949; &#8804; 1/16 and for any algorithm A, there exists a target function h * &#8712; H and a distribution D over D h * with margin</p><p>For convenience, here we relax the instance space by allowing X &#8838; B n (0, 9/8).</p><p>The construction of the target function and the data distribution is similar to that in the proof of Theorem 6. To attack a test instance x 0 , the attacker adds the reflection points of all training points through the hyperplane defined by x 0 and w * such that any algorithm will misclassify x 0 with probability 1/2. The detailed proof is included in Appendix E.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.">Results for finite-point attackers</head><p>In this section, instead of considering the case where the attacker can add a set of poison examples of arbitrary size, we study a restrictive case where the attacker is allowed to add at most t poison examples for some t &lt; &#8734;, i.e., |Adv(h * , S trn , x 0 )| &#8804; t for any h * , S trn , x 0 . Following Definition 1 and 2, we define t-point clean-label attackable rate and (t, &#949;, &#948;)-robust learnability as follows.</p><p>Definition 6 (t-point clean-label attackable rate) For a target function h * , a training data set S trn and a (possibly randomized) algorithm A, for any distribution D over D h * , the t-point cleanlabel attackable rate is</p><p>Definition 7 ((t, &#949;, &#948;)-robust learnability) A hypothesis class H is (t, &#949;, &#948;)-robust learnable if there exists a learning algorithm A such that &#8704;&#949;, &#948; &#8712; (0, 1), &#8707;m(t, &#949;, &#948;) &#8712; N such that &#8704;h * &#8712; H, &#8704;D over D h * , with probability at least 1 -&#948; over S trn &#8764; D m , atk D (t, h * , S trn , A) &#8804; &#949; .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.1.">Algorithms robust to t-point attacker</head><p>Robustness to a small number of poison examples has been studied by <ref type="bibr">Ma et al. (2019)</ref>; <ref type="bibr">Levine and Feizi (2020)</ref>. <ref type="bibr">Ma et al. (2019)</ref> show that differentially-private learners are naturally resistant to data poisoning when the attacker can only inject a small number of poison examples. <ref type="bibr">Levine and Feizi (2020)</ref> propose an algorithm called Deep Partition Aggregation (DPA), which partitions the training set into multiple sets by a deterministic hash function, trains base classifiers over each partition and then returns the majority vote of base classifiers. They show that for any instance x, the prediction on x is unchanged if the number of votes of the output exceeds half of the number of the total votes by t. But the attackable rate of DPA is not guaranteed. Here we propose several algorithms similar to DPA but with guarantees on the attackable rate. In Algorithm 2, we provide a protocol converting any given ERM learner L to a learner with small t-point clean-label attackable rate. </p><p>Proof sketch For every misclassified point x 0 &#8712; X , there are at least 5t + 1 classifiers among {L(S (i) )} 10t+1 i=1 misclassifying x 0 . Since there are at most t blocks containing poison data, there are at least 4t+1 non-contaminated classifiers (output by blocks without poison data) misclassifying x 0 . Then t-point clean-label attackable rate is bounded by bounding the error of one non-contaminated classifier. The detailed proof is provided in Appendix F.</p><p>As we can see, Algorithm 2 is improper even if L is proper. Inspired by the projection number and the projection operator defined by <ref type="bibr">Bousquet et al. (2020)</ref>, we propose a proper robust learner in Algorithm 3. First, let us introduce the definitions of the projection number and the projection operator as follows. For a finite (multiset) H &#8838; H, for l &#8805; 2, define the set X H ,l &#8838; X of all the points x on which less than 1 l -fraction of all classifiers in H disagree with the majority. That is,</p><p>Definition </p><p>The proof adopts the same idea as the proof of Theorem 8 and is included in Appendix G. For the hypothesis class with infinite projection number, we can obtain a proper learner in a similar way: randomly selecting &#949; |S|/3t samples with replacement from input data set S and run ERM over the selected data. We show that this algorithm can (t, &#949;, &#948;)-robustly learn H using O( dt &#949; 2 log d &#949; + d &#949; log 1 &#948; ) samples. The details of the algorithm and the analysis can be found in Appendix G.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2.">Lower bound</head><p>Theorem 10 For any d &#8805; 1 and &#949; &#8804; 3 8 , there exists a hypothesis class H with VC dimension 5d such that for any algorithm A, there exists a target function h * &#8712; H and a data distribution D on D h * , such that E Strn&#8764;D m [atk D (t, h * , S trn , A)] &gt; &#949; when the sample size m &lt; 3td 64&#949; .</p><p>Proof sketch Consider d disjoint spheres in R 3 and the target function is chosen by randomly selecting a circle on each sphere. Then label each circle differently from the rest of the sphere the circle lies on. Specifically, we flip d independent fair coins, one for each circle to decide whether the circle is labeled positive or negative. The data distribution puts probability mass t 8m uniformly on each circle and 1 -td 8m probability mass on an irrelevant point (not on any of the spheres). Then we can show that with constant probability, every unseen point on each circle can be attacked by an attacker similar to the one in the proof sketch of Theorem 2. The detailed proof is included in Appendix H.</p><p>Remark 1 Actually, our algorithms above even work for t-point unclean-label attackers (where the poison data are not necessarily labeled by the target function) as well, which indicates that cleanness of poison examples does not make the problem fundamentally easier in the worst-case over classes of a given VC dimension, in the t-point attack case (although it can potentially make a difference for particular algorithms or particular classes H).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.">Discussion and future directions</head><p>In this paper, we show the impossibility of robust learning in the presence of clean-label attacks for some hypothesis classes with bounded VC dimension, e.g., the class of linear separators, and the robust learnability of some hypothesis classes characterized by known complexity measures, e.g., finite star number. There are several interesting open questions.</p><p>&#8226; The first question is what are necessary and sufficient conditions for (&#949;, &#948;)-robust learnability.</p><p>Finite star number is a sufficient but not necessary condition. Here is an example where the instance space is X = N and the hypothesis class is</p><p>One intriguing possible complexity measure is the largest number k such that there is a set of distinct points S = {x 1 , . . . , x k } &#8712; X k and classifiers {h 0 , . . . , h k }, where for any i &#8712; [k], there exists an involutory function f &#8226; Another open question is whether abstention helps. Considering the case where the algorithm is allowed to abstain on &#949;-fraction of inputs if the algorithm detects abnormality. That is to say, the algorithm outputs a selective classifier ( h, CR(S trn )), where the prediction hypothesis h is a map from X to Y and CR(S trn ) &#8838; X is the confidence region of the prediction. The algorithm predicts A(S trn , x) = h(x) if x &#8712; CR(S trn ) and A(S trn , x) =&#8869; if x / &#8712; CR(S trn ), where &#8869; means the algorithm predicts "I don't know". Then for any deterministic algorithm, we say a test instance x &#8712; X is attackable if there is a clean-label attacker such that x is predicted incorrectly as well as x is in the confidence region, i.e.,</p><p>We define the event E(h * , S trn , A, Adv, x, y) = {A(S trn &#8746; Adv(h * , S trn , x), x) = h * (x) &#8745; x &#8712; CR(S trn &#8746; Adv(h * , S trn , x))} and then define the selective attackable rate as</p><p>We are curious about the sample complexity required to achieve &#949; selective attackable rate while keeping the probability mass of the confidence region P (x,y)&#8764;D (x &#8712; CR(S)) &#8804; &#949; for any input S &#8839; S trn .</p><p>Appendix A. Proof of results in Section 3  <ref type="bibr">Ben-David (2015)</ref>, &#8804; H f for d = 1 is a tree ordering. Thus, all points labeled differently by f and h * should lie on one path, i.e., for every Proof First, we prove that</p><p>} is also an ordered set. If the set is not empty, x m in the algorithm is well-defined. Now note that either h = f or else x m is defined and then every x with h</p><p>In particular, if P D (X) &#8804; &#949; the above facts imply atk D (h * , S trn , A) &#8804; &#949;. Otherwise if P D (X) &gt; &#949;, then we let X &#949; &#8838; X be any minimal set such that P D (X &#949; ) &#8805; &#949; 2 and for every x &#8712; X \ X &#949; and every x &#8712; X &#949; , x &#8804; H f x. If P D (X &#949; ) &#8805; &#949;, there exists an element x &#8712; X &#949; with probability mass at least &#949; 2 . When m &#8805; 2 ln(1/&#948;) &#949;</p><p>, with probability at least 1 -&#948;, x is in S trn and therefore ATK(h * , S trn , A, Adv) &#8838; X &#949; \ {x}, so that atk D (h * , S trn , A) &#8804; &#949; 2 . Otherwise, if &#949; 2 &#8804; P D (X &#949; ) &lt; &#949;, then as long as S trn contains at least one example from X &#949; , then ATK(h * , S trn , A, Adv) &#8838; X &#949; , so that atk D (h * , S trn , A) &#8804; P D (X &#949; ) &lt; &#949;. Since S trn contains an example from X &#949; with probability at least 1 -(1 -&#949; 2 ) m , when m &#8805; 2 ln(1/&#948;) &#949; we have that with probability at least 1 -&#948;, atk D (h * , S trn , A) &#8804; &#949;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A.2. Union of intervals</head><p>Theorem 12 The algorithm described in Section 3 can (&#949;, &#948;)-robustly learn union of intervals H k using m samples, where</p><p>Proof We denote the target function by</p><p>In the following, we will construct two classifiers consistent with the training set and then prove that the attackable rate of our algorithm is upper bounded by the sum of the error rates of these two classifiers. For any i &#8712; [k * ], we define c + i as the minimum consistent positive interval within (a 2i-1 , a 2i ), i.e.,</p><p>Similarly, for i = 0, . . . , k * , we define c - i as the minimum consistent negative interval within [a 2i , a 2i+1 ]. Since x = 0 and x = 1 are labeled as 0 by every hypothesis in H k , we would like c - 0 to include x = 0 and c k *to include x = 1. Then we denote by S trn = S trn &#8746; {(0, 0), (1, 0)} and then define c - i as</p><p>Let us define two classifiers:</p><p>are consistent with S trn and the VC dimension of H k is 2k, by classic uniform convergence results <ref type="bibr">(Vapnik and Chervonenkis, 1974;</ref><ref type="bibr">Blumer et al., 1989)</ref>, for any data distribution D, with probability at least</p><p>It is easy to see that the algorithm (even under attack) will always predicts 1 over c + i as the attacker cannot add negative instances into c + i . Then for any attacker Adv and any i &#8712; [k * ], for any</p><p>We can prove a similar result for ATK(h * , S trn , A, Adv)&#8745;{x|h * (x) = 0}. If the algorithm (under attack) predicts 1 on any</p><p>Note that the algorithm always correctly labels points in [0, a 1 ] and [a 2k * , 1] as there are no positively-labeled points in these two intervals. Therefore, ATK(h * , S trn , A, Adv)&#8745;{x|h * (x) = 0} &#8838; {x|h - c (x) = 1, h * (x) = 0}. Then for any point in the attackable region, it is either in the error region of h + c or in the error </p><p>For the second part, by Markov's inequality, we have</p><p>which completes the proof. with increasing size {k i } &#8734; i=1 with k 1 &#8805; 3. Then following the proof of Theorem 13, for any m &#8804; (k i -1)/2 for some i, there exists a target function and a data distribution such that the expected attackable rate is at least 1/4 with sample size m. Since k i &#8594; &#8734; as i &#8594; &#8734;, this theorem is proved.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A.4. Proof of Theorem 1</head><p>Here we present the proof of Theorem 1 establishing that any deterministic robust learner necessarily obtains a sample complexity with O(1/&#949;) dependence on &#949;. Proof of Theorem 1 Without loss of generality, we suppose R(m) &#8804; 1 and R(m) is nonincreasing, since we can always replace it with sup m &#8805;m min{R(m ), 1}, which is monotone and inherits the other assumed properties of R. For convenience, let us also extend the function R(m) to non-integer values of m by defining R(&#945;) = R( &#945; ), and defining R(0) = 1. Also define Log(x) = log 2 (x) for any x &#8805; 1.</p><p>Fix any h * &#8712; H. Since A is deterministic, note that for any finite multiset S &#8838; D h * there is a set ATK S &#8838; X corresponding to the points that would be attackable for A if S trn = S. Moreover, we may note that the set ATK S is non-increasing in S (subject to S &#8838; D h * ), since adding any (x, y) &#8712; D h * to S is equivalent to constraining the adversary to include these points in its attack set. Log(1/&#948;) . In particular, this implies that, with probability at least 1 -(1/2) Log(1/&#948;) &#8805; 1 -&#948;, at least one i &#8804; Log(1/&#948;) will satisfy this inequality. Moreover, by the monotonicity property of ATK, we know that ATK Strn &#8838; i&#8804;Log(1/&#948;) ATK S i . Thus, with probability at least 1 -&#948;,</p><p>The remainder of the proof follows a familiar "conditioning" argument from the literature on log factors in the sample complexity of PAC learning (e.g., <ref type="bibr">Hanneke, 2009</ref><ref type="bibr">Hanneke, , 2016a))</ref>. Fix any distribution D over D h * . We proceed by induction on m, establishing for each m that &#8704;&#948; &#8712; (0, 1), for S trn &#8764; D m , with probability at least 1-&#948;, atk D (h * , S trn , A) &#8804; c m Log 1 &#948; , where c is a finite R-dependent constant. Note that this suffices to establish the theorem by taking c R = c (assuming base 2 in the log). The claim is trivially satisfied for m &lt; 3 Log 1 &#948; , as the claimed bound is vacuous (taking any c &#8805; 3). Now as an inductive hypothesis suppose m &#8805; 3 Log 1 &#948; is such that, for every m &lt; m, for S trn &#8764; D m , for any &#948; &#8712; (0, 1), with probability at least 1 -&#948;, atk D (h * , S trn , A) &#8804; c m Log 1 &#948; .</p><p>Fix any &#948; &#8712; (0, 1) and let S trn &#8764; D m . Note that atk D (h * , S trn , A) = P (x,y)&#8764;D (x &#8712; ATK Strn ). Let S m/2 be the first m/2 of the data points in S trn , and let T = (S\S m/2 )&#8745;(ATK S m/2 &#215;Y): that is, T are the samples in the last m/2 points in S trn that are in the attackable region when A has training set S m/2 .</p><p>Since </p><p>.</p><p>By the inductive hypothesis, with probability at least 1-&#948; 3 , we have that atk D (h * , S m/2 , A) &#8804; c m/2 Log 3 &#948; &#8804; 3c m Log 3 &#948; . For any &#945; &#8805; 1, define R (&#945;) = 1 &#945; sup 1&#8804;&#945; &#8804;&#945; &#945; R(&#945; ), and note that R(&#945;) &#8804; R (&#945;) for all &#945; &#8805; 1, and &#945;R (&#945;) is nondecreasing in &#945; &#8805; 1. Therefore, on the above event,</p><p>Now note that lim &#945;&#8594;&#8734; R (&#945;) = 0. To see this, for the sake of contradiction, suppose &#8707;&#949; &gt; 0 and a strictly increasing sequence &#945; t &#8805; 1 with &#945; t &#8594; &#8734; such that R (&#945; t ) &#8805; &#949;, and let &#945; t be any sequence with 1 &#8804; &#945; t &#8804; &#945; t and 1 &#945;t &#945; t R(&#945; t ) &#8805; R (&#945; t )/2 &#8805; &#949;/2. If there exists an infinite subsequence t i with &#945; t i bounded above by some finite &#945;, then lim i&#8594;&#8734;</p><p>again, a contradiction. Thus, since we have just established that lim &#945;&#8594;&#8734; R (&#945;) = 0, there exists a sufficiently large choice of c for which R 3c 4 &#8804; 1 9 , so that 9c m Log 1 &#948; R 3c 4 &#8804; c m Log 1 &#948; . Altogether, by the union bound, we have established that with probability at least 1 -&#948;, either atk D (h * , S trn , A) &lt; 16 m ln 3 &#948; or atk D (h * , S trn , A) &#8804; c m Log 1 &#948; . Taking c sufficiently large so that c &#8805; 16 ln(3e), both cases imply that atk D (h * , S trn , A) &#8804; c m Log 1 &#948; . The theorem now follows by the principle of induction.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Appendix B. Proof of Theorem 2</head><p>In this section, we first formally prove the statement in the case of n = 3, for which we already provided a proof sketch in Section 4. In the proof sketch, we relax the definition of linear hypothesis class by allowing the decision boundary to be either positive or negative. Here, we adopt the convention that the boundary is only allowed to be positive. Then we prove the statement in the case of n = 2, which requires a more delicate construction. Before proving Theorem 2, we first introduce a lemma.</p><p>Lemma 1 For any hypothesis class H, any algorithm A and any m &gt; 0, if there exists a universal constant c &gt; 0, a distribution &#181; over H, and a set of distributions D(h) over D h for every</p><p>Proof First, take &#949; = c, we have by the definition of sup, there exists an h * &#8712; H such that,</p><p>Then by Markov's inequality,</p><p>Hence, H is not (&#949;, &#948;)-robust learnable.</p><p>Proof of Theorem 2 in n = 3 We divide the proof into three parts: a) the construction of the target function and the data distribution, b) the construction of the attacker and c) the analysis of the attackable rate.</p><p>The target function and the data distribution. We denote by &#915; = &#915; 3 (0, 1) the sphere of the 3-dimensional unit ball centered at the origin. For some small 0 &lt; &#951; &lt; 1/6, let</p><p>denote a set of linear classifiers with boundary 1/2 or 1-&#951; 2 away from the origin. Let K w = {x| w, x -1 2 = 0} denote the hyperplane of the boundary of h = 1[ w, x -1 2 &#8805; 0] and C w = K w &#8745; &#915; denote the intersection of K w and &#915;, which is a circle with radius &#8730; 3/2 centered at w/2. We consider the target function h * selected uniformly at random from H &#951; , which is equivalent to: randomly picking w &#8764; Unif(&#915;) and randomly picking j &#8764; Ber(1/2);</p><p>Note that all instances on the circle C w are labeled as j by h * w,j . We will show that the expected attackable rate E h * &#8764;Unif(H&#951;),Strn&#8764;D m [atk D (h * , S trn , A)] &#8805; 1/2. Combining with Lemma 1, we prove Theorem 2 in n = 3.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>The attacker.</head><p>Then we define the attacker Adv in the following way. We first define a map m x 0 : &#915; &#8594; &#915; for some x 0 &#8712; &#915; such that m x 0 (x) = 2 x 0 , x x 0 -x. Here, m x 0 (x) is the reflection of x through the line passing the origin and x 0 . Note that m x 0 (m x 0 (x)) = x. This symmetric property will help to confuse algorithms such that no algorithm can distinguish the training data and the poisoning data. For S trn &#8764; D m w,j , we define m x 0 (S trn ) = {(m x 0 (x), 1 -y)|(x, y) &#8712; S trn }, and let</p><p>Now we show that Adv is a clean-label attacker. In the second case of Adv(h * w,j , S trn , x 0 ) = &#8709;, it is clean-labeled trivially. In the first case of S trn,X &#8745; B(x 0 , 3&#951;/2) = &#8709;, we discuss two cases:</p><p>&#8226; The target function h * = h * w,j = 1[ w, x -1 2 &#8805; 0] has its decision boundary 1 2 away from the origin, i.e., j = 1. Then every training instance is labeled by 1 and for any training instance x, w, m x 0 (x) -1 2 = x 0 , x -1 &lt; 0. Hence Adv(h * w,j , S trn , x 0 ) is clean-labeled.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>&#8226; The target function h</head><p>has its decision boundary 1-&#951; 2 away from the origin, i.e., j = 0. For each training instance x, since x / &#8712; B(x 0 , 3&#951;/2), we have</p><p>Hence Adv(h * w,j , S trn , x 0 ) is clean-labeled.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Analysis.</head><p>Let E 1 (h * w,j , S trn , x 0 ) denote the event of {A(S trn &#8746; Adv(h * w,j , S trn , x 0 ), x 0 ) = h * w,j (x 0 )} and E 2 (S trn , x 0 ) denote the event of S trn,X &#8745; B(x 0 , 3&#951;/2) = &#8709;. It is not hard to check that E 2 (S trn , x 0 ) = E 2 (m x 0 (S trn ), x 0 ) due to the symmetrical property of the reflection. Besides, conditional on E 2 (S trn , x 0 ), the poisoned data set S trn &#8746; Adv(h * w,j , S trn , x 0 ) = m x 0 (S trn ) &#8746; Adv(h * mx 0 (w),1-j , m x 0 (S trn ), x 0 ) and thus, any algorithm A will behave the same (under attack) at test instance x 0 given training set S trn or m x 0 (S trn ). Since h * w,j (x 0 ) = h * mx 0 (w),1-j (x 0 ), we know that 1[E 1 (h * w,j , S trn , x 0 )] = 1[&#172;E 1 (h * mx 0 (w),1-j , m x 0 (S trn ), x 0 )] conditional on E 2 (S trn , x 0 ). Let f w,j (x) denote the probability density function of the marginal distribution of D w,j (i.e., the uniform distribution over C w ) and then we have f w,j (x) = f mx 0 (w),1-j (m x 0 (x)). For any fixed x 0 , the distributions of w and m x 0 (w) and the distributions of j and 1 -j are the same respectively. The training set S trn are samples drawn from D w,j , and hence we can view m x 0 (S trn ) as samples drawn from D mx 0 (w),1-j . Then for any algorithm A, we have</p><p>where Eq. ( <ref type="formula">2</ref>) uses the fact E 2 (S trn , x 0 ) = E 2 (m x 0 (S trn ), x 0 ) and that conditional on E 2 (S trn , x 0 ), 1[E 1 (h * w,j , S trn , x 0 )] = 1[&#172;E 1 (h * mx 0 (w),1-j , m x 0 (S trn ), x 0 )]; Eq. ( <ref type="formula">3</ref>) uses the fact that for any fixed x 0 , the distributions of w and m x 0 (w) and the distributions of j and 1 -j are the same respectively; and Eq. ( <ref type="formula">4</ref>) is the average of Eq. ( <ref type="formula">1</ref>) and Eq. ( <ref type="formula">3</ref>).</p><p>Proof of Theorem 2 in n = 2 Again, we divide the proof into three parts.</p><p>The target function and the data distribution. In 2-dimensional space, we denote by w = (cos &#952;, sin &#952;) and represent the target function</p><p>Then the target function is selected in the following way: uniformly at random selecting a point o from a 2-dimensional ball centered at 0 with some large enough radius r &#8805; 4, i.e., o &#8764; Unif(B 2 (0,r)), then randomly selecting a direction &#952; * &#8764; Unif([0, 2&#960;)), and letting the target function be h * = 1[ (cos &#952; * , sin &#952; * ), x -o &#8805; 0]. Then for any m &#8712; N, we construct the data distribution over 2m discrete points, where all points are labeled the same and the distance between every two instances is independent of h * . Specifically, the data distribution D is described as follows.</p><p>&#8226; We randomly draw s &#8764; Ber(1/2). We define two unit vectors v 1 = (sin &#952; * , -cos &#952; * ) and</p><p>Here v 1 is perpendicular to w * and v 2 is in the same direction as w * if s = 1 and in the opposite direction of w * if s = 0.</p><p>&#8226; Let X m = {x 1 , . . . , x 2m } be a set of 2m points. For notation simplicity, we also define x 0 and x 2m+1 . Let x 0 = o and for all i &#8712; [2m+1], let x i = x i-1 +l cos(&#946; i-1 )v 1 +l sin(&#946; i-1 )v 2 , where &#946; i = 7&#946; i-1 , &#946; 0 = 7 -2m &#8226; &#960; 6 and l = 1 2m .</p><p>&#8226; Let the marginal data distribution be a uniform distribution over X m . Note that if s = 1, all training points lie on the positive side of the decision boundary and are labeled by 1; if s = 0, all training points lie on the negative side and are labeled by 0.</p><p>Here</p><p>x in this new coordinate system. Then the decision boundary of the target function is represented as x, v 2 = 0 and for any x &#8712; X m we have x, v 2 &gt; 0. It is worth noting that for any i &#8712; [2m], if the positions of three points x i-1 , x i , x i+1 are fixed, then o, s, v 1 , v 2 are all fixed.</p><p>The attacker. For any</p><p>and x i+1 are collinear. We denote by L x i the line passing z i and x i . Then for any i &#8712; [2m], let</p><p>be the reflection of x across L x i as illustrated in Fig. <ref type="figure">1</ref>. For S trn &#8764; D m , we let U = X m \ S trn,X denote the set of points not sampled in X m , where |U | &#8805; m. Then we define Adv as</p><p>Now we need to show that Adv is a clean-label attacker. We will show that Ref Lx i (x j ), v 2 &lt; 0 for all j = i &#8712; [2m], which implies that the poison data is correctly labeled when x i &#8712; U . First, we claim that for any j = i, x j lie in the polytope above the line passing x i-1 , x i+1 , the line passing x i-1 , x i and the line passing x i , x i+1 . Formally speaking, for any j = i, x j satisfies</p><p>This claim is not hard to prove. At a high level, we prove this claim by that {&#946; i } 2m i=0 is monotonically increasing and that the polygon defined by connecting every pair of neighboring points in X m &#8746; {x 0 , x 2m+1 } is convex. For the first constraint, it is satisfied trivially when j = i -1, i + 1. If j &#8805; i + 2, by direct calculation, we have</p><p>It is easy to check that x j satisfies the second and the third constraints using the same way of computation, which is omitted here. Based on that x j lie in the polytope for all j = i, then we only need to prove that Ref Lx i (x), v 2 &lt; 0 for the points lying on the faces of the polytope, which are</p><p>Hence, we only need to prove the statement for points lying on the first two faces.</p><p>For any two vectors u, v, we denote by &#952;(u, v) the angle between u and v. Then let us denote by &#952; 1 = &#952;( x i+1 -z i , x i -z i ) the angle between x i+1 -z i and and x i -z i and &#952; 2 = &#952;( x i -z i , v 1 ) the angle between x i -z i and v 1 . Then we have both</p><p>where the last inequality is by 3&#946; i-1 &#8804; &#960; 6 . On the other hand, we have</p><p>Combining these two equations, we have sin &#952; 1 &gt; sin &#952; 2 , which indicates that &#952; 1 &gt; &#952; 2 . Then since</p><p>It is easy to check that &#946; i-1 &#8804; &#952; 2 (let p denote the intersection of the line passing x i-1 and x i and the line x, v 2 = 0, &#946; i-1 = &#952;( x i -p, v 1 ) and &#952; 2 is the external angle of triangle with vertices p, z i and x i ). Then for</p><p>&lt;0 .</p><p>Now we complete the proof of Ref Lx i (x j ), v 2 &lt; 0 for all j = i and that Adv is a clean-label attacker. It is worth noting that L x i = L x i , where L x i is defined over {x j |j &#8712; [2m]} in the same way as L x i defined over {x j |j &#8712; [2m]}. This is because reflections of z i and x i over L x i are themselves. This symmetric property plays an important role in the analysis.</p><p>Analysis. Our probabilistic construction of the target function h * and the data distribution D and the random sampling process of drawing m i.i.d. samples from D is equivalent to: sampling a multiset of indexes I trn &#8764; Unif([2m]) first; then selecting the target function and the data distribution to determine the positions of the m training points; mapping I trn to S trn by adding instance-label pair (x i , h * (x i )) to S trn for each i in I trn . We let I u = [2m] \ I trn denote the indexes not sampled. As we know from the construction, for any i &#8712; [2m], once s and the positions of o and x i is determined, the positions of other points in X m and h * are determined. Then we consider an equivalent way of determining the target function and the data distribution. That is, randomly selecting the position of x i (dependent on the randomness of o, &#952; * , s) and then considering the following two different processes of selecting s and o.</p><p>&#8226; Given a fixed x i , randomly select s &#8764; D(s|x i ) and select o &#8764; D(o|s, x i ), where D(s|x i ) and D(o|s, x i ) denote the conditional distributions of s and o respectively. Note that when</p><p>) is a uniform distribution over the circle with radius r i centered at x i , where r i is the distance between o and x i and is a constant according to the definition.</p><p>&#8226; Given (x i , s, o) selected in the above process, if x i &#8804; r -2, we let s = 1 -s and o = Ref Lx i (o) (where x i+1 and x i-1 is determined by (x i , s, o)); otherwise we let s = s and o = o. It is easy to check that the distribution of s conditional on x i is Ber(1/2) and the distribution of o conditional on</p><p>Therefore, the distributions of s and s and the distributions of o and o are the same given x i respectively. Our following analysis depends on the event of x i &#8804; r -2, the probability of which is P (</p><p>We let S trn (x i , s, o) denote the training set by mapping I trn to the positions determined by (x i , s, o) and let h * (x i , s, o) denote the target function determined by (x i , s, o). Note that when x i &#8804; r -2 and x i is not in the training set, the poisoned data sets with the training sets generated in the above two different processes are the same, i.e., S trn</p><p>. This is due to the symmetric property of the attacker. Hence, any algorithm will behave the same at point x i no matter whether the training set is S trn (x i , s, o) or S trn (x i , s , o ). In addition, the target functions produced in the two different processes classify x i differently when</p><p>Then for any i &#8712; I u , conditional on E 2 (x i ), for any algorithm A, we have</p><p>(5)</p><p>Similar to the proof in the case of n = 3, we have the expected attackable rate</p><p>when r &#8805; 4. Here Eq. ( <ref type="formula">6</ref>) holds due to Eq. ( <ref type="formula">5</ref>) and Eq. ( <ref type="formula">7</ref>) holds since the distributions of s and s and the distributions of o and o are the same given x i respectively. Combining with Lemma 1, we complete the proof.</p><p>binary-search for &#946; will not search in depth and output (0, b) for some consistent b. Therefore, atk(h * , S trn , A) &#8804; P({x|&#8707;b &#8712; [-2, 2], h 0,b (x) = h * (x), &#8704;(x , y ) &#8712; S trn , y = h 0,b (x )}) &#8804; 2&#949; .</p><p>In the case of |b * | &#8804; 1, let A z {x|(cos &#946; * , sin &#946; * ) &#8226; x + b * &#8712; [-z, z]} for z &#8805; 0. We will show that when h -l &#8804; arctan(z/2) for z &#8804; 2, the classifier boundary K &#946;,b must lie in A z , i.e., K &#946;,b {x|(cos &#946;, sin &#946;) &#8226; x + b = 0, x &#8804; 1} &#8838; A z . This indicates that when hl &#8804; arctan(z/2), the algorithm can only make mistakes at points inside A z . If it is false, let {q 1 , q 2 } = {x|(cos &#946; * , sin &#946; * ) &#8226; x + b * = 0} &#8745; &#915;(0, 1) with &#946; * -&#952;((q 2 -q 1 ), e 1 ) = &#960; 2 (mod 2&#960;) if the intersection of the target function boundary and the unit circle has two different points; or let q 1 = q 2 = q where {q} = {x|(cos  <ref type="figure">(&#946;,</ref><ref type="figure">b</ref>) and the unit circle has only one point. The definitions of q 1 , q 2 , p 1 , p 2 are illustrated in Fig. <ref type="figure">2</ref>. Then at least one of {p 1 , p 2 } is not in A z and w.l.o.g., assume that p 2 / &#8712; A z . It is easy to check that p 1 , p 2 must lie on the same side of the boundary of the target function, otherwise |&#946; -&#946; * | = &#952;((p 2 -p 1 ), (q 2 -q 1 )) &gt; arctan(z/2), which contradicts h -l &#8804; arctan(z/2). Then there exists a consistent classifier h = 1[ w, x -p 2 &#8805; 0] with w = (q 12 -p 22 , p 21 -q 11 ) (whose boundary is the line passing q 1 and p 2 ). Then let &#946; denote the direction of h , i.e., cos &#946; = q 12 -p 22 w and sin &#946; = p 21 -q 11 w , and we have |&#946; -&#946; * | = &#952;(p 2 -q 1 , q 2 -q 1 ) &gt; arctan(z/2), which contradicts that h -l &#8804; arctan(z/2).</p><p>We let z = f (&#949; ). When h -l &#8804; arctan(f (&#949; )/2), the classifier can only make mistakes inside A f (&#949; ) and thus the attackable rate is upper bounded by 2&#949; . In addition, when h -l &gt; arctan(f (&#949; )/2), the binary-search has searched to at most the log 2 ( 2&#960; arctan(f (&#949; )/2) ) +1-th depth, which leads to at most 2&#949; ( log 2 ( 2&#960; arctan(f (&#949; )/2) ) + 1) attackable rate. Combining these results together, when m &#8805; 4 &#949; log 2 &#948; + 24 &#949; log 13 &#949; , with probability at least 1 -&#948; over S trn &#8764; D m , we have</p><p>where Eq. ( <ref type="formula">8</ref>) holds because arctan(x/2) &#8805; &#960;/4 when x &#8805; 2 and arctan(x/2) &#8805; &#960;x/8 when x &#8712; [0, 2].</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Appendix D. Proof of Theorem 6</head><p>To prove Theorem 6, we first introduce a lemma on the behavior of uniform distribution on a unit sphere.</p><p>Lemma 2 (Lemma 2.2 by <ref type="bibr">Ball et al. (1997)</ref>) For any a &#8712; [0, 1), for x &#8764; Unif(&#915; n (0, 1)), with probability at least 1 -e -na 2 /2 , we have x, e 1 &#8804; a.</p><p>Proof of Theorem 6 One essential hardness for robust learning of linear classifiers in high dimension is that for a fixed test instance x 0 on the sphere of a unit ball, with high probability over the selection of a set of training points from the uniform distribution over the sphere, every training instance has small component in the direction of x 0 as shown by Lemma 2. Taking advantage of this, the attacker can add a point (labeled differently from x 0 ) which is considerably closer to x 0 than all of the training instances, thus altering the behavior of SVM at x 0 as he wishes. In the following, we prove the theorem based on this idea. We divide the proof into three parts: a) the construction of the target function and the data distribution, b) the construction of the attacker and c) the analysis of the attackable rate.</p><p>The target function and the data distribution. The target function is h * = 1[ w * , x &#8805; -&#947;/2] with w * = e 1 and margin &#947; = 1/8. We define the marginal data distribution D X by putting probability mass 1 -8&#949; on -e 1 and putting probability mass 8&#949; uniformly on the half sphere of a unit ball {x| x = 1, x, e 1 &#8805; 0}. We let D + denote the uniform distribution over this positive half sphere. We draw m i.i.d. training samples S trn from D and then let S + trn denote the positive training samples. Let m + = S + trn denote the number of positive training samples. The attacker. For a given test instance x 0 &#8712; {x| x = 1, x, e 1 &#8805; 0}, we define two base vectors v 1 = e 1 and v 2 = x 0 -x 0 ,e 1 e 1 x 0 -x 0 ,e 1 e 1 2 . Note that v 2 is well-defined almost surely. Then we define an attacker Adv as</p><p>The target function and the data distribution. We denote every point in R n by (x, z) for x &#8712; R n-1 and z &#8712; R. The target function h * is selected uniformly at random from H * , where H * = {1[ (jw * , 1), (x, z) &#8805; j&#947;/2]|j &#8712; {&#177;1}, w * &#8712; &#915; n-1 (0, 1)}. Let &#947; = 1 8 . For target function h * = h w * ,j = 1[ (jw * , 1), (x, z) &#8805; j&#947;/2], the marginal data distribution D w * ,j,X puts probability mass 1 -8&#949; on the point e n , then put the remaining 8&#949; probability uniformly over the half sphere of a (n -1)-dimensional unit ball &#915; w * ,&#947; &#215; {0}, where &#915; w * ,&#947; = &#915; n-1 (&#947;w * , 1) &#8745; {x| w * , x &#8805; &#947;}. Then since every hypothesis in H * predicts e n positively, we only need to focus on the half sphere in the lower dimension. Note that the label of every point on the half sphere is determined by j. We sample S trn &#8764; D m w * ,j and S trn,w * ,j denote the samples on &#915; w * ,&#947; &#215;{0}&#215;Y. Let m w * ,j = |S trn,w * ,j |.</p><p>The attacker. For any</p><p>0} denote the homogeneous (passing through the origin) hyperplane perpendicular to the vector</p><p>For any given test instance (x 0 , 0) with x 0 &#8712; &#915; w * ,&#947; , we define two base vectors v 1 = w * and v 2 = x 0 -x 0 ,w * w *</p><p>x 0 -x 0 ,w * w * . Note that v 2 is well-defined almost surely. Denote</p><p>x's component on the hyperplane defined by v 1 , v 2 and x &#8869; = x -x denote the component perpendicular to v 1 , v 2 and then we define</p><p>x 0 2 x 0 -x as the reflection of x through K x 0 . Then we define an attacker Adv as</p><p>where E 1 (w * , S trn , x 0 , m w * ,j ) = &#8704;(x, 0) &#8712; S trn,X , x, w * &#8804; 1 8 + &#947;, x, x 0 -x 0 , w * w * x 0 -x 0 , w * w * &#8804; 1 8</p><p>Here E 1 (w * , S trn , x 0 , m w * ,j ) is thought as a condition to attack x 0 . Then we show that Adv is a clean-label attacker. If E 1 (w * , S trn , x 0 , m w * ,j ) holds, we have</p><p>Claim II For any homogeneous hyperplane L u 1 &#8712; R n-1 with normal vector u 1 , for any u</p><p>Proof of Claim II We consider two cases. If u 2 &#8712; L u 1 , then we have,</p><p>which completes the proof.</p><p>Claim III Conditional on E 3 (Q trn , t 0 ), the poisoned datasets S trn &#8746; Adv(h w * ,j , S trn , (x 0 , 0)) and S trn &#8746; Adv(h w * , j , S trn , ( x 0 , 0)) are identical. Proof of III Denote by K = K &#947;e 1 +t 0 (e 1 ) the homogeneous hyperplane perpendicular to e 1 -&#947;e 1 + t 0 , e 1 &#947;e 1 +t 0 &#947;e 1 +t 0 2 . Thus we have,</p><p>By Claim I, we know that E 3 (Q trn , t 0 ) and E 1 (w * , S trn , x 0 , m w * ,j ) are equivalent. Thus, conditional on E 3 (Q trn , t 0 ), Adv(h w * ,j , S trn , (x 0 , 0</p><p>where Eq. ( <ref type="formula">9</ref>) holds by applying Claim II. Similarly, for Adv(h w * , j , S trn , (x 0 , 0)), the plane of</p><p>each block has m 0 points, we have</p><p>Notice here, if m 0 is fixed, the randomness of A can be regarded as selecting N c first and drawing n c m 0 samples uniformly at random from S trn without replacement to construct S (i 1 ) , S (i 2 ) . . . , S (in c ) . More specifically, conditioned on N c , the randomness of A on h i 1 is only through drawing S (i </p><p>In the following, we will bound the error of h i 1 for each value of m 0 . Let E denote the event of err Strn (h i 1 ) &#8804; (d+1) ln(em/d) m 0</p><p>and by Lemma 4 we have P A (&#172;E|N c ) &#8804; d em . Then with probability at least 1 -&#948; over the choice of S trn , for each fixed value of m 0 , we have</p><p>where Eq. ( <ref type="formula">16</ref>) applies Lemma 3. Then when m 0 &#8805; 960d &#949; ln 2640etd &#949; + 19d ln(1/&#948;) &#949;t , we have that</p><p>Combined with Eq. ( <ref type="formula">13</ref>), we have that when data points and at least t(10k p -1) + 1 blocks do not contain any attacking points, i.e., n c &#8805; t(10k p -1) + 1. Given any fixed x &#8712; X , if</p><p>, then x &#8712; X H ,kp , thus h(x) = Major(H , x) = h * (x). Thus we have, given training data S trn , for any x &#8712; X , any m 0 and any t-point attacker Adv to make each block has m 0 points, we have</p><p>Then we bound E A [err(h i 1 )|N c ] in the same way as the proof of Theorem 8. Following the same calculation process of Eq. ( <ref type="formula">17</ref> </p><p>Then for any t-point attacker Adv, we have</p><p>Conditioned on E, S 0 is a set of i.i.d. samples uniformly drawn from S trn . By classic uniform convergence bound, err Strn (h 0 ) &#8804; 2 m 0 (d log(2em 0 /d) + log(2/&#948; 0 )) with probability at least 1 -&#948; 0 over the choice of S 0 (for a fixed S trn ). Let E 1 denote the event of err Strn (h 0 ) &#8804; 2 m 0 (d + 1) log(2em 0 /d) and it is easy to check that P A (&#172;E 1 ) &#8804; d em 0 . Similar to the proof of Theorem 8, with probability at least 1 -&#948;, we have ). We start with proving this statement in the base case of d = 1 and then extend it to d &#8805; 2. We divide the proof into four parts: a) construction of the hypothesis class, the target function and the data distribution in d = 1, b) computation of the VC dimension of the hypothesis class, c) construction of the attacker, and d) generalization to d &#8805; 1.</p><p>The hypothesis class, the target function and the data distribution. We denote by &#915; = &#915; 3 (0, 1) the sphere of the 3-d unit ball centered at the origin. First, consider a base case where the domain X = &#915; &#8746; 0, which is the union of the sphere of a unit ball centered at the origin and the origin. For any point q &#8712; &#915;, We let C q = &#915; 3 (q, 1) &#8745; &#915; denote the circle of intersection of the sphere of two unit balls. Then we define h q,1 = 1[C q ], which only classifies the circle C q positive and h q,0 = 1[&#915; \ C q ] only classifies the circle and the origin negative. Our hypothesis class is H = {h q,j |q &#8712; &#915;, j &#8712; {0, 1}}. We draw our target h * uniformly at random from H, which is equivalent to drawing q &#8764; Unif(&#915;) and j &#8764; Ber(1/2). The marginal data distribution D q,j,X puts probability mass &#950; &#8712; (0, t 8m ] uniformly on the circle C q and puts the remaining probability mass on 0, where the value of &#950; is determined later. We draw S trn &#8764; D m q,j .</p><p>The VC dimension of the hypothesis class. Then we show that the VC dimension of H is 5. Since all classifiers in H will classify 0 as negative, 0 cannot be shattered and thus, we only need to find shattered points on the sphere. Then we show that H can shatter 5 points. It is not hard to check that the following set of 5 points can be shattered:</p><p>2 cos( 2k&#960; 5 ), .</p><p>Then we show that H cannot shatter 6 points. For any 6 points P = {p 1 , . . . , p 6 }, if the 6 points can be shattered, then for any subset P 1 &#8838; P with size 3, there exists a hypothesis classifying P 1 as 0s and P \ P 1 as 1s. That is, there exists a circle of radius &#8730; 3 2 such that either only P 1 is on the circle or only P \ P 1 is on the circle. Then we claim that no 4 points can be on a circle of radius 2 . Therefore, any 6 points cannot be shattered. The attacker. We adopt the reflection function m x 0 (&#8226;) defined in the proof of Theorem 2 where m x 0 (x) = 2 x 0 , x x 0 -x for x &#8712; &#915;. For S trn &#8764; D m q,j , we let S q = C q &#8745; S trn,X denote the training instances in C q (with replicants) and we further define m x 0 (S trn ) = {(m x 0 (x), 1 -y)|(x, y) &#8712; S q &#215; Y}, and let Adv(h * , S trn , x 0 ) = m x 0 (S trn ) if x 0 / &#8712; S trn,X , |S q | &#8804; t , &#8709; else .</p><p>If x 0 / &#8712; S trn,X , then h q,j is consistent with S trn &#8746; Adv(h q,j , S trn , x 0 ). That is, Adv(h q,j , S trn , x 0 ) is clean-labeled.</p><p>Analysis. Due to the construction, we have</p><p>Then by Markov's inequality, we have</p><p>Let E 1 (A, Adv, h q,j , S trn , x 0 ) denote the event of {A(S trn &#8746; Adv(h q,j , S trn , x 0 ), x 0 ) = h q,j (x 0 )} and let E 2 (S trn , x 0 , q) denote the event of {|S q | &#8804; t &#8745; x 0 / &#8712; S trn,X }. It is easy to check that E 2 (S trn , x 0 , q) = E 2 (m x 0 (S trn ), x 0 , m x 0 (q)). Besides, conditional on E 2 (S trn , x 0 , q), we have the poisoned data set S trn &#8746; Adv(h q,j , S trn , x 0 ) = m x 0 (S trn ) &#8746; Adv(h mx 0 (q),1-j , m x 0 (S trn ), x 0 ) and thus, any algorithm A will behave the same at the test instance x 0 no matter whether the training set is S trn or m x 0 (S trn ). Since h q,j (x 0 ) = h mx 0 (q),1-j (x 0 ), we have 1[E 1 (A, Adv, h q,j , S trn , x 0 )] = 1[&#172;E 1 (A, Adv, h mx 0 (q),1-j , m x 0 (S trn ), x 0 )] conditional on E 2 (S trn , x 0 , q). Let f q (x) denote the probability density function of Unif(C q ) and then we have f q (x) = f mx 0 (q) (m x 0 (x)). For any fixed x 0 , the distributions of q and m x 0 (q) and the distributions of j and 1 -j are the same respectively. Since S trn are samples drawn from D m q,j , m x 0 (S trn ) are actually samples drawn from D m mx 0 (q),1-j . Then we have E h * &#8764;Unif(H),Strn&#8764;D m [atk D (t, h * , S trn , A)] =&#950;E q&#8764;Unif(&#915;),j&#8764;Ber( <ref type="formula">1</ref>2 ),Strn&#8764;D m q,j ,x&#8764;Unif(Cq),A [1[E 1 (A, Adv, h q,j , S trn , x)]] &#8805;&#950;E q&#8764;Unif(&#915;),j&#8764;Ber( <ref type="formula">1</ref>2 ),Strn&#8764;D m q,j ,x&#8764;Unif(Cq),A [1[E 1 (A, Adv, h q,j , S trn , x) &#8745; E 2 (S trn , x, q)]] =&#950; x&#8712;&#915; E q&#8764;Unif(&#915;),j&#8764;Ber( <ref type="formula">1</ref>2 ),Strn&#8764;D m q,j ,A [f q (x)1[E 1 (A, Adv, h q,j , S trn , x) &#8745; E 2 trn , x, q)]] dx =&#950; x&#8712;&#915; E q&#8764;Unif(&#915;),j&#8764;Ber( <ref type="formula">1</ref>2 ),Strn&#8764;D m q,j ,A [f mx(q) (x)1[&#172;E 1 (A, Adv, h mx(q),1-j , m x (S trn ), x)]</p><p>&#8226; 1[E 2 (m x (S trn ), x, m x (q))]]dx =&#950; x E q&#8764;Unif(&#915;),j&#8764;Ber( <ref type="formula">1</ref>2 ),Strn&#8764;D m q,j ,A [f q (x)1[&#172;E 1 (A, Adv, h q,j , S trn , x)] &#8226; 1[E 2 (S trn , x, q)]] dx</p><p>[f q (x)1[E 2 (S trn , x, q)]] dx &gt; 3&#950; 8 , which completes the proof for d = 1 by setting &#950; = min( t 8m , 1). Extension to general d &#8805; 1. To extend the base case to d &gt; 1, we construct d separate balls and repeat the above construction on each ball individually. For i &#8712; [d], let &#915; i = &#915; 3 (3ie 1 , 1) denote the sphere of a ball with radius 1 centered at 3ie 1 . Consider the domain X = &#8746; i&#8712;[d] &#915; i &#8746;{0} as the union of d non-overlapping unit balls and the origin. For q i &#8712; &#915; i , let h 1 q i = 1[&#915; 3 (q i , 1) &#8745; &#915; i ] denote the hypothesis classifying only points on the circle of &#915; 3 (q i , 1) &#8745; &#915; i positive and h 0 q i = 1[&#915; i \ &#915; 3 (q i , 1)] denote the hypothesis classifying only points on &#915; i positive except the circle &#915; 3 (q i , 1) &#8745; &#915; i . Let h s q 1 ,...,q d = i&#8712;[d] h s i q i , where s &#8712; {0, 1} d denote the hypothesis combining all d balls and H = {h s q 1 ,...,q d |q i &#8712; &#915; i , &#8704;i &#8712; [d], s &#8712; {0, 1} d }. We have the VC dimension of H is 5d. Our target function is selected uniformly at random from H and similar to the case of d = 1, we assign probability &#950; = min( 1 d , t 8m ) to each circle on the balls and the remaining probability mass on the origin. Since every ball is independent with other balls and thus, we have E h * &#8764;Unif(H),Strn&#8764;D m [atk D (t, h * , S trn , A)] &gt; 3d&#950; 8 = min( 3td 64m , 3 8 ). In all, there exists a target function h * &#8712; H and a data distribution D over D h * such that E Strn [atk D (t, h * , S trn , A)] &gt; &#949; when m &lt; 3td 64&#949; for &#949; &#8804; 3 8 .</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_0"><p>&#169; 2021 A. Blum, S. Hanneke, J. Qian &amp; H. Shao.</p></note>
		</body>
		</text>
</TEI>
