The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure

Introduction

Learning how to classify instances based on labeled examples is a fundamental task in machine learning. The goal is to find, with high probability, the correct label $c(x)$ of a given test instance $x$ coming from a distribution ${\bm{\upmu}}$. Thus, we would like to find a good-on-average “hypothesis” $h$ (also called the trained model) that minimizes the error probability $\Pr_{x\leftarrow{\bm{\upmu}}}[h(x)\neq c(x)]$, which is referred to as the risk of $h$ with respect to the ground truth $c$. Due to the explosive use of learning algorithms in real-world systems (e.g., using neural networks for image classification) a more modern approach to the classification problem aims at making the learning process, from training till testing, more robust. Namely, even if the instance $x$ is perturbed in a limited way into $x^{\prime}$ by an adversary $A$, we would like to have the hypothesis $h$ still predict the right label for $x^{\prime}$; hence, minimizing the “adversarial risk”

of the hypothesis $h$ under such perturbations, where “close” is defined by a metric. An attack to increase the risk is called an “evasion attack” (see e.g., ) due to the fact that $x^{\prime}$ “evades” the correct classification. One major motivation behind this problem comes from scenarios such as image classification, in which the adversarially perturbed instance $x^{\prime}$ would still “look similar” to the original $x$, at least in humans’ eyes, even though the classifier $h$ might now misclassify $x^{\prime}$ . In fact, starting with the work of Szegedy et al. an active line of research (e.g., see ) investigated various attacks and possible defenses to resist such attacks. The race between attacks and defenses in this area motivates a study of whether or not such robust classifiers could ever be found, if they exist at all.

A closely related notion of robustness for a learning algorithm deals with the training phase. Here, we would like to know how much the risk of the produced hypothesis $h$ might increase, if an adversary $A$ tampers with the training data ${\mathcal{T}}$ with the goal of increasing the “error” (or any “bad” event in general) during the test phase. Such attacks are referred to as poisoning attacks , and the line of research on the power and limitations of poisoning attacks contains numerous attacks and many defenses designed (usually specifically) against them (e.g., see and references therein).

The state of affairs in attacks and defenses with regard to the robustness of learning systems in both the evasion and poisoning contexts leads us to our main question:

What are the inherent limitations of defense mechanisms for evasion and poisoning attacks? Equivalently, what are the inherent power of such attacks?

Understanding the answer to the above question is fundamental for finding the right bounds that robust learning systems can indeed achieve, and achieving such bounds would be the next natural goal.

In the context of evasion attacks, the most relevant to our main question above are the recent works of Gilmer et al. , Fawzi et al. , and Diochnos et al. . In all of these works, isoperimetric inequalities for specific metric probability spaces (i.e., for uniform distributions over the $n$-sphere by , for isotropic $n$-Gaussian by , and for uniform distribution over the Boolean hypercube by ) were used to prove that problems on such input spaces are always vulnerable to adversarial instances. More formally, Gilmer et al. designed specific problems over (two) $n$-spheres, and proved them to be hard to learn robustly, but their proof extend to any problem defined over the uniform distribution over the $n$-sphere. Also, Fawzi et al. used a different notion of adversarial risk that only considers the hypothesis $h$ and is independent of the ground truth $c$, however their proofs also extend to the same setting as ours. The work of Schmidt et al. shows that, at least in some cases, being robust to adversarial instances requires more data. However, the work of Bubeck et al. proved that assuming the existence of classifiers that are robust to evasion attacks, they could be found by “few” training examples in an information theoretic way.

In the context of poisoning attacks, some classical results about malicious noise could be interpreted as limitations of learning under poisoning attacks. On the positive (algorithmic) side, the works of Diakonikolas et al. and Lia et al. showed the surprising power of algorithmic robust inference over poisoned data with error that does not depend on the dimension of the distribution. These works led to an active line of work (e.g., see and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees. The works of showed how to do list-docodable learning, and studied supervised learning.

Demonstrating the power of poisoning attacks, Mahmoody and Mahloujifar showed that, assuming an initial $\Omega(1)$ error, a variant of poisoning attacks that tamper with $\approx p$ fraction of the training data without using wrong labels (called $p$-tampering) could always increase the error of deterministic classifiers by $\Omega(p)$ in the targeted poisoning model where the adversary knows the final test instance. Then Mahloujifar et al. improved the quantitative bounds of and also applied those attacks to degrade the confidence parameter of any PAC learners under poisoning attacks. Both attacks of were online, in the sense that the adversary does not know the future examples, and as we will see their attack model is very relevant to this work. Koh and Liang studied finding training examples with most influence over the final decision over a test instance $x$–enabling poisoning attacks. Here, we prove the existence of $O(\sqrt{m})$ examples in the training set that can almost fully degrade the final decision on $x$, assuming $\Omega(1)$ initial error on $x$.

The work of Bousquet and Elisseeff studied how specific forms of stability of the hypothesis (which can be seen as robustness under weak forms of “attacks” that change one training example) imply standard generalization (under no attack). Our work, on the other hand, studies generalization under attack while the adversary can perturb a lot more (but still sublinear) part of instances.

The works of Madry et al. and Schmidt et al. employ an alternative definition of adversarial risk inspired by robust optimization. This definition is reminiscent of the definition of “corrupted inputs” used by Feige et al. (and related works of ) as in all of these works, a “successful” adversarial example $x^{\prime}$ shall have a prediction $h(x^{\prime})$ that is different from the true label of the original (uncorrupted) instance $x$. However, such definitions based on corrupted instances do not always guarantee that the adversarial examples are misclassified. In fact, even going back to the original definitions of adversarial risk and robustness from , many papers (e.g., the related work of ) only compare the prediction of the hypothesis over the adversarial example with its own prediction on the honest example, and indeed ignore the ground truth defined by the concept $c$.) In various “natural” settings (such as image classification) the above two definition and ours coincide. We refer the reader to the work of Diochnos et al. where these definitions are compared and a taxonomy is given, which we will use here as well. See Appendix A for more details.

1 Our Results

In this work, we draw a connection between the general phenomenon of “concentration of measure” in metric measured spaces and both evasion and poisoning attacks. A concentrated metric probability space $(\mathcal{X},{\mathbf{d}},{\bm{\upmu}})$ with metric ${\mathbf{d}}$ and measure ${\bm{\upmu}}$ has the property that for any set ${\mathcal{S}}$ of measure at least half (${\bm{\upmu}}({\mathcal{S}})\geq 1/2$), most of the points in ${\mathcal{X}}$ according to ${\bm{\upmu}}$, are “close” to ${\mathcal{S}}$ according to ${\mathbf{d}}$ (see Definition 2.4). We prove that for any learning problem defined over such a concentrated space, no classifier with an initial constant error (e.g., $1/100$) can be robust to adversarial perturbations. Namely, we prove the following theorem. (See Theorem 3.2 for a formalization.)

Suppose $(\mathcal{X},{\mathbf{d}},{\bm{\upmu}})$ is a concentrated metric probability space from which the test instances are drawn. Then for any classifier $h$ with $\Omega(1)$ initial “error” probability, there is an adversary who changes the test instance $x$ into a “close” one and increases the risk to $\approx 1$.

In Theorem 1.1, the “error” could be any undesired event over $h,c,x$ where $h$ is the hypothesis, $c$ is the concept function (i.e., the ground truth) and $x$ is the test instance.

The intuition behind the Theorem 1.1 is as follows. Let ${\mathcal{E}}=\left\{x\in{\mathcal{X}}\mid h(x)\neq c(x)\right\}$ be the “error region” of the hypothesis $h$ with respect to the ground truth concept $c(\cdot)$ on an input space ${\mathcal{X}}$. Then, by the concentration property of ${\mathcal{X}}$ and that ${\bm{\upmu}}({\mathcal{E}})\geq\Omega(1)$, we can conclude that at least half of the space ${\mathcal{X}}$ is “close” to ${\mathcal{E}}$, and by one more application of the same concentration property, we can conclude that indeed most of the points in ${\mathcal{X}}$ are “close” to the error region ${\mathcal{E}}$. Thus, an adversary who launches an evasion attack, can indeed push a typical point $x$ into the error region by little perturbations. This above argument, is indeed inspired by the intuition behind the previous results of , and all of which use isoperimetric inequalities for specific metric probability spaces to prove limitations of robust classification under adversarial perturbations. Indeed, one natural way of proving concentration results is to use isoperimetric inequalities that characterize the shape of sets with minimal boundaries (and thus minimal measure after expansion). However, we emphasize that bounds on concentration of measure could be proved even if no such isoperimetric inequalities are known, and e.g., approximate versions of such inequalities would also be sufficient. Indeed, in addition to proofs by isoperimetric inequalities, concentration of measure results are proved using tools from various fields such as differential geometry, bounds on eigenvalues of the Laplacian, martingale methods, etc, . Thus, by proving Theorem 1.1, we pave the way for a wide range of results against robust classification for learning problems over any concentrated space. To compare, the results of have better constants due to their use of isoperimetric inequalities, while we achieve similar asymptotic bounds with worse constants but in broader contexts.

We also prove variants of Theorem 1.1 that deal with the average amount of perturbation done by the adversary with the goal of changing the test instance $x$ into a misclassified $x^{\prime}$. Indeed, just like the notion of adversarial risk that, roughly speaking, corresponds to the concentration of metric spaces with a worst-case concentration bound, the robustness of a classifier $h$ with an average-case bound on the perturbations corresponds to the concentration of the metric probability space using an average-case bound on the perturbation. In this work we introduce the notion of target-error robustness in which the adversary targets a specific error probability and plans its (average-case bounded) perturbations accordingly (see Theorem 3.5).

Since a big motivation for studying the hardness of classifiers against adversarial perturbations comes from the challenges that have emerged in the area of image classifications, here we comment on possible ideas from our work that might be useful for such studies. Indeed, a natural possible approach is to study whether or not the metric measure space of the images is concentrated or not. We leave such studies for interesting future work. Furthermore, the work of observed that vulnerability to adversarial instances over “nice” distributions (e.g., $n$-Gaussian in their work, and any concentrated distribution in our work) can potentially imply attacks on real data assuming that the data is generated with a smooth generative model using the mentioned nice distributions. So, as long as one such mapping could be found for a concentrated space, our impossibility results can potentially be used for deriving similar results about the generated data (in this case image classification) as well.

One natural family of metric probability spaces for which Theorem 1.1 entails new impossibility results are product measure spaces under Hamming distance. Results of show that such metric probability spaces are indeed normal Lévy. Therefore, we immediately conclude that, in any learning task, if the instances come from any product space of dimension $n$, then an adversary can perturb them to be misclassified by only changing $O(\sqrt{n})$ of the “blocks” of the input. A special case of this result covers the case of Boolean hypercube that was recently studied by . However, here we obtain impossibilities for any product space. As we will see below, concentration in such spaces are useful beyond evasion attacks.

One intriguing application of concentration in product measure spaces is to obtain inherent poisoning attacks that can attack any deterministic learner by tampering with their training data and increase their error probability during the (untampered) test phase. Indeed, since the training data is always sampled as ${\mathcal{T}}\leftarrow({\bm{\upmu}},c({\bm{\upmu}}))^{m}$ where $c$ is the concept function and $m$ is the sample complexity, the concentration of the space of the training data under the Hamming distance (in which the alphabet space is the full space of labeled examples) implies that an adversary can always change the training data ${\mathcal{T}}$ into ${\mathcal{T}}^{\prime}$ where ${\mathcal{T}}^{\prime}$ by changing only a “few” examples in ${\mathcal{T}}$ while producing a classifier $h$ that is more vulnerable to undesired properties.

Our attacks of Theorem 1.2 are offline in the sense that the adversary needs to know the full training set ${\mathcal{T}}$ before substituting some of them. We note that the so-called $p$-tampering attacks of are online in the sense that the adversary can decide about its choices without the knowledge of the upcoming training examples. However, in that work, they could only increase the classification error by $O(p)$ through tampering by $p$ fraction of the training data, while here we get almost full error by only using $p\approx O(\sqrt{m})$, which is much more devastating.

Preliminaries

Let $(\mathcal{X},{\mathbf{d}})$ be a metric space. We use the notation $\mathsf{Diam}^{\mathbf{d}}(\mathcal{X})=\sup\left\{{\mathbf{d}}(x,y)\mid x,y\in\mathcal{X}_{i}\right\}$ to denote the diameter of $\mathcal{X}$ under ${\mathbf{d}}$, and we use $\mathcal{B}all_{b}^{\mathbf{d}}(x)=\left\{x^{\prime}\mid{\mathbf{d}}(x,x^{\prime})\leq b\right\}$ to denote the ball of radius $b$ centered at $x$. When ${\mathbf{d}}$ is clear from the context, we simply write $\mathsf{Diam}(\mathcal{X})$ and $\mathcal{B}all_{b}(x)$. For a set ${\mathcal{S}}\subseteq\mathcal{X}$, by ${\mathbf{d}}(x,{\mathcal{S}})=\inf\left\{{\mathbf{d}}(x,y)\mid y\in{\mathcal{S}}\right\}$ we denote the distance of a point $x$ from ${\mathcal{S}}$.

Unless stated otherwise, all integrals in this work are Lebesgue integrals.

We call $(\mathcal{X},{\mathbf{d}},{\bm{\upmu}})$ a metric probability space, if ${\bm{\upmu}}$ is a Borel probability measure over $\mathcal{X}$ with respect to the topology defined by ${\mathbf{d}}$. Then, for a Borel set ${\mathcal{E}}\subseteq\mathcal{X}$, the $b$-expansion of ${\mathcal{E}}$, denoted by ${\mathcal{E}}_{b}$, is defined as The set ${\mathcal{E}}_{b}$ is also called the $b$-flattening or $b$-enlargement of ${\mathcal{E}}$, or simply the $b$-ball around $A$.

We call $(\mathcal{X},{\mathbf{d}},{\bm{\upmu}})$ a nice metric probability space, if the following conditions hold.

Expansions are measurable. For every ${\bm{\upmu}}$-measurable (Borel) set ${\mathcal{E}}\in{\mathcal{X}}$, and every $b\geq 0$, its $b$-expansion ${\mathcal{E}}_{b}$ is also ${\bm{\upmu}}$-measurable.

Average distances exist. For every two Borel sets ${\mathcal{E}},{\mathcal{S}}\in{\mathcal{X}}$, the average minimum distance of an element from ${\mathcal{S}}$ to ${\mathcal{E}}$ exists; namely, the integral $\int_{\mathcal{S}}{\mathbf{d}}(x,{\mathcal{E}})\cdot d{\bm{\upmu}}(x)$ exists.

At a high level, and as we will see shortly, we need the first condition to define adversarial risk and need the second condition to define (a generalized notion of) robustness. Also, we remark that one can weaken the second condition above based on the first one and still have risk and robustness defined, but since our goal in this work is not to do a measure theoretic study, we are willing to make simplifying assumptions that hold on the actual applications, if they make the presentation simpler.

2 Classification Problems

We use calligraphic letters (e.g., ${\mathcal{X}}$) for sets. By $x\leftarrow{\bm{\upmu}}$ we denote sampling $x$ from the probability measure ${\bm{\upmu}}$. For a randomized algorithm $R(\cdot)$, by $y\leftarrow R(x)$ we denote the randomized execution of $R$ on input $x$ outputting $y$. A classification problem $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H})$ is specified by the following components. The set $\mathcal{X}$ is the set of possible instances, $\mathcal{Y}$ is the set of possible labels, ${\bm{\upmu}}$ is a distribution over $\mathcal{X}$, ${\mathcal{C}}$ is a class of concept functions where $c\in{\mathcal{C}}$ is always a mapping from $\mathcal{X}$ to $\mathcal{Y}$. We did not state the loss function explicitly, as we work with classification problems. For $x\in\mathcal{X},c\in{\mathcal{C}}$, the risk or error of a hypothesis $h\in\mathcal{H}$ is equal to $\mathsf{Risk}(h,c)=\Pr_{x\leftarrow{\bm{\upmu}}}[h(x)\neq c(x)]$. We are usually interested in learning problems $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H})$ with a specific metric ${\mathbf{d}}$ defined over $\mathcal{X}$ for the purpose of defining risk and robustness under instance perturbations controlled by metric ${\mathbf{d}}$. In that case, we simply write $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H},{\mathbf{d}})$ to include ${\mathbf{d}}$.

We call $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H},{\mathbf{d}})$ a nice classification problem, if the following two conditions hold:

$(\mathcal{X},{\mathbf{d}},{\bm{\upmu}})$ is a nice metric probability space.

For every $h\in\mathcal{H},c\in{\mathcal{C}}$, their error region $\left\{x\in{\mathcal{X}}\mid h(x)\neq c(x)\right\}$ is ${\bm{\upmu}}$-measurable.

The second condition above is satisfied, e.g., if the set of labels ${\mathcal{Y}}$ (which is usually finite) is countable, and for all $y\in{\mathcal{Y}},f\in\mathcal{H}\cup{\mathcal{C}}$, the set $\left\{x\in{\mathcal{X}}\mid f(x)=y\right\}$ is ${\bm{\upmu}}$-measurable.

3 The Concentration Function and Some Bounds

We now formally define the (standard) notion of concentration function.

Let $(\mathcal{X},{\mathbf{d}},{\bm{\upmu}})$ be a metric probability space and ${\mathcal{E}}\subseteq\mathcal{X}$ be a Borel set. The concentration function is then defined as

Variations of the following Lemma 2.5 below are in , but the following version is due to Talagrand (in particular, see Equation 2.1.3 of Proposition 2.1.1 in ).

Let ${\bm{\upmu}}\equiv{\bm{\upmu}}_{1}\times\dots\times{\bm{\upmu}}_{n}$ be a product probability measure of dimension $n$ and let the metric be the Hamming distance. For any ${\bm{\upmu}}$-measurable ${\mathcal{S}}\subseteq\mathcal{X}$ such that the $b$-expansion ${\mathcal{S}}_{b}$ of ${\mathcal{S}}$ under Hamming distance is also measurable,

Evasion Attacks: Finding Adversarial Examples from Concentration

In this section, we formally prove our main results about the existence of evasion attacks for learning problems over concentrated spaces. We start by formalizing the notions of risk and robustness.

Let $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H},{\mathbf{d}})$ be a nice classification problem. For $h\in\mathcal{H}$ and $c\in{\mathcal{C}}$, let $\mathcal{E}=\left\{x\in\mathcal{X}\mid h(x)\neq c(x)\right\}$ be the error region of $h$ with respect to $c$. Then, we define:

We might call $b$ the “budget” of an imaginary “adversary” who perturbs $x$ into $x^{\prime}$. Using $b=0$, we recover the standard notion of risk: $\mathsf{Risk}(h,c)=\mathsf{Risk}_{0}(h,c)={\bm{\upmu}}(\mathcal{E})$.

Target-error robustness. Given a target error $\rho\in(0,1]$, we define the $\rho$-error robustness as the expected perturbation needed to increase the error to $\rho$; namely,

where $\mathbf{1}_{\mathcal{S}}(x)$ is the characteristic function of membership in ${\mathcal{S}}$. Letting $\rho=1$, we recover the notion of full robustness $\mathsf{Rob}(h,c)=\mathsf{Rob}_{1}(h,c)=\mathop{{}\mathbf{E}}_{x\leftarrow{\bm{\upmu}}}\left[{\mathbf{d}}(x,\mathcal{E})\right]$ that captures the expected amount of perturbations needed to always change $x$ into a misclassified $x^{\prime}$ where $x^{\prime}\in{\mathcal{E}}$.

As discussed in the introduction, starting with , many papers (e.g., the related work of ) use a definitions of risk and robustness that only deal with the hypothesis/model and is independent of the concept function. In , that definition is formalized as “prediction change” (PC) adversarial risk and robustness. In Appendix A, we show that using the concentration function ${\bm{\upalpha}}(\cdot)$ and our proofs of this section, one can also bound the PC risk and robustness of hypotheses assuming that we have a concentration function. Then, by plugging in any concentration function (e.g., those of Lévy families) and obtain the desired upper/lower bounds.

In the rest of this section, we focus on misclassification as a necessary condition for the target adversarial example. So, in the rest of this section, we use Definition 3.1 to prove our results.

We now formally state and prove our result that the adversarial risk can be large for any learning problem over concentrated spaces. Note that, even though the following is stated using the concentration function, having an upper bound on the concentration function suffices for using it. Also, we note that all the results of this section extend to settings in which the “error region” is substituted with any “bad” event modeling an undesired region of instances based on the given hypothesis $h$ and concept function $c$; though the most natural bad event is that error $h(x)\neq c(x)$ occurs.

Let $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H},{\mathbf{d}})$ be a nice classification problem. Let $h\in\mathcal{H}$ and $c\in{\mathcal{C}}$, and let $\varepsilon=\Pr_{x\leftarrow{\bm{\upmu}}}[h(x)\neq c(x)]$ be the error of the hypothesis $h$ with respect to the concept $c$. If $\varepsilon>{\bm{\upalpha}}(b)$ (i.e., the original error is more than the concentration function for the budget $b$), then the following two hold.

Reaching adversarial risk at least half. Using only tampering budget $b$, the adversary can make the adversarial risk to be more than half; namely, $\mathsf{Risk}_{b}(h,c)>1/2.$

Reaching adversarial risk close to one. If in addition we have $\gamma\geq{\bm{\upalpha}}(b_{2})$, then the adversarial risk for the total tampering budget $b_{1}+b_{2}$ is $\mathsf{Risk}_{b_{1}+b_{2}}(h,c)\geq 1-\gamma$.

Let ${\mathcal{E}}=\left\{x\in{\mathcal{X}}\mid h(x)\neq c(x)\right\}$ be the error region of $(h,c)$, and so it holds that $\varepsilon={\bm{\upmu}}({\mathcal{E}})$. To prove Part 1, suppose for sake of contradiction that $\mathsf{Risk}_{b}(h,c)\leq 1/2$. Then, for ${\mathcal{S}}={\mathcal{X}}\setminus{\mathcal{E}}_{b}$, it holds that ${\bm{\upmu}}({\mathcal{S}})=1-{\bm{\upmu}}({\mathcal{E}}_{b})=1-\mathsf{Risk}_{b}(h,c)\geq 1/2$. By the assumption ${\bm{\upmu}}({\mathcal{E}})>{\bm{\upalpha}}(b)$, we have ${\bm{\upmu}}({\mathcal{S}}_{b})\geq 1-{\bm{\upalpha}}(b)>1-\varepsilon$. So, there should be $x\in{\mathcal{S}}_{b}\cap{\mathcal{E}}$, which in turn implies that there is a point $y\in{\mathcal{S}}$ such that ${\mathbf{d}}(y,x)\leq b$. However, that is a contraction as ${\mathbf{d}}(y,x)\leq b$ implies that $y$ should be in ${\mathcal{E}}_{b}={\mathcal{X}}\setminus{\mathcal{S}}$.

To prove Part 2, we rely on Part 1. By Part 1, if we use a tampering budget $b_{1}$, we can increase the adversarial risk to $\mathsf{Risk}_{b_{1}}(h,c)>1/2$, but then because of the second assumption $\gamma\geq{\bm{\upalpha}}(b_{2})$, it means that by using $b_{2}$ more budget, we can expand the error region to measure $\geq 1-\gamma$. ∎

The above theorem provides a general result that applies to any concentrated space. So, even though we will compute explicit bounds for spaces such as Lévy families, Theorem 3.2 could be applied to any other concentrated space as well, leading to stronger or weaker bounds than what Lévy families offer. Now, in the following, we go after finding general relations between the concentration function and the robustness of the learned models.

The following lemma provides a very useful tool for going from adversarial risk to robustness; hence, allowing us to connect concentration of spaces to robustness. In fact, the lemma could be of independent interest, as it states a relation between worst-case concentration of metric probability spaces to their average-case concentration with a targeted amount of measure to cover.

First, we make a few comments on using Lemma 3.3.

Lemma 3.3 can be used to compute the full robustness also as

Let $\nu({\mathcal{S}})=\int_{\mathcal{S}}{\mathbf{d}}(x,{\mathcal{E}})\cdot d{\bm{\upmu}}(x)$. Based on the definition of robustness, we have

where the left integral shall be interpreted as Lebesgue integral over the Lebesgue–Stieltjes measure associated with the cumulative distribution function $F(\cdot)$.

Claim 3.4 follows from the integration-by-parts (extension) for Lebesgue integral over the Lebesgue–Stieltjes measure. ∎

and so the robustness can be bounded from above as

The above lower bound on $\mathsf{Rob}_{\rho}({\mathcal{E}})$ and the upper bound of Inequality 4 conclude the proof. ∎

We now formally state our result that concentration in the instance space leads to small robustness of classifiers. Similarly to Theorem 3.2, we note that even though the following theorem is stated using the concentration function, having an upper bound on the concentration function would suffice.

Let $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H},{\mathbf{d}})$ be a nice classification problem. Let $h\in\mathcal{H}$ and $c\in{\mathcal{C}}$, and let $\varepsilon=\Pr_{x\leftarrow{\bm{\upmu}}}[h(x)\neq c(x)]$ be the error of the hypothesis $h$ with respect to the concept $c$. Then if $\varepsilon>{\bm{\upalpha}}(b_{1})$ and $1-\rho\geq{\bm{\upalpha}}(b_{2})$, we have

By Theorem 3.2, we know that $\mathsf{Risk}_{b_{1}}({\mathcal{E}})={\bm{\upmu}}({\mathcal{E}}_{b_{1}})\geq\frac{1}{2}$ which implies $\mathsf{Risk}_{b_{1}+b_{2}}({\mathcal{E}})=\mathsf{Risk}_{b_{2}}({\mathcal{E}}_{b_{1}})\geq\rho$. If we let $\rho^{*}=\mathsf{Risk}_{b_{1}+b_{2}}({\mathcal{E}})$, then we have

2 Normal Lévy Families as Concentrated Spaces

In this subsection, we study a well-known special case of concentrated spaces called normal Lévy families, as a rich class of concentrated spaces, leading to specific bounds on the risk and robustness of learning problems whose test instances come from any normal Lévy family. We start by formally defining normal Lévy families.

The following theorem shows that classifying instances that come from a normal Lévy family has the inherent vulnerability to perturbations of size $O(1/\sqrt{n})$

Reaching adversarial risk at least half. If $b>{\sqrt{\ln({k_{1}}/{\varepsilon})}}/{\sqrt{k_{2}\cdot n}}$, then $\mathsf{Risk}_{b}(h,c)\geq 1/2$.

Reaching Adversarial risk close to one. If $b>{\sqrt{\ln({k_{1}}/{\varepsilon})+\ln({k_{1}}/{\gamma})}}/{\sqrt{k_{2}\cdot n}}$, then it holds that $\mathsf{Risk}_{b}(h,c)\geq 1-\gamma$.

Bounding target-error robustness. For any $\rho\in[\frac{1}{2},1]$, we have

Proof of Part 1 is similar to (part of the proof of) Part 2, so we focus on Part 2.

We now prove Part 3. By Theorem 3.5, we have

Here we remark on its interpretation in an asymptotic sense, and discuss how much initial error is needed to achieve almost full adversarial risk.

Let $\mathsf{P}_{n}$ be a nice classification problem defined over a metric probability space that is a normal Lévy family, and let $\varepsilon$ be the error probability of a hypothesis $h$ with respect to some concept function $c$.

Starting from constant error. If $\varepsilon\geq\Omega(1)$, then for any constant $\gamma$, one can get adversarial risk $1-\gamma$ for $h$ using only $O(1/\sqrt{n})$ perturbations, and full robustness of $h$ is also $O(1/\sqrt{n})$.

Starting from sub-exponential error. If $\varepsilon\geq\exp(-o(n))$, then one can get adversarial risk $1-\exp(-o(n))$ for $h$ using only $o(1)$ perturbations, and full robustness is also $o(1)$.

The amount of perturbation in normal Lévy families needed to (almost certainly) misclassify the adversarial example is $O(1/\sqrt{n})$, but this is also the case that “typically” metric probability spaces become normal Lévy under a “normalized” metric; meaning that the diameter (or more generally the average of distances of random pairs) is $\Theta(1)$. (E.g., when working with the unit $n$-sphere.) However, in some occasions, the “natural” metrics over those spaces is achieved by scaling up the typical distances to $\Theta(n)$ (e.g., the Hamming distance in the Boolean hypercube). In that case, the bounds of Theorem 3.7 also get scaled up to $O(\sqrt{n})$ (for constants $\varepsilon,\gamma$).

Here, we list some natural metric probability spaces that are known to be normal Lévy families. For the references and more examples we refer the reader to excellent sources . There are other variants of Lévy families, e.g., those called Lévy (without the adjective “normal”) or concentrated Lévy families with stronger concentration, but we skip them and refer the reader to the cited sources and general tools of Theorems 3.2 and 3.5 on how to apply any concentration of measure results to get bounds on risk and robustness of classifiers.

Unit cube and unit ball under Euclidean distance. Both the unit cube $^{n}$ and the unit $n$-ball (of radius $1$) are normal Lévy families under normalized Euclidean distance (where the diameter is $1$) and normalized Lebesgue distributions (see Propositions 2.8 and 2.9 in ).

Product distributions under Hamming distance. Any product distribution ${\bm{\upmu}}^{n}$ with normalized Hamming distance is a normal Lévy family . In particular, the Boolean hypercube $\{0,1\}^{n}$ with normalized Hamming distance and uniform distribution is a normal Lévy family . This also follows from the isoperimetric inequality of . In the next section, we will use the concentration of product spaces to obtain poisoning attacks against learners.

Symmetric group under Hamming distance. The set of all permutations $\Pi^{n}$ under Hamming distance and the uniform distribution forms a non-product Lévy family.

Poisoning Attacks from Concentration of Product Measures

In this section, we design new poisoning attacks against any deterministic learning algorithm, by using the concentration of space in the domain of training data. We start by defining the confidence and error parameters of learners.

The function $\varepsilon(\cdot)$ is the error parameter, and $1-\delta(m)$ is the confidence of the learner $L$.

Now, we formally define the class of poisoning attacks and their properties.

Let $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathcal{C}})$ be a classification with a learning algorithm $L$. Then, a poisoning adversary $A$ for $(L,\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathcal{C}})$ is an algorithm that takes as input a training set ${\mathcal{T}}\leftarrow({\bm{\upmu}},c({\bm{\upmu}}))^{m}$ and outputs a modified training set ${\mathcal{T}}^{\prime}=A({\mathcal{T}})$ of the same size Requiring the sets to be equal only makes our negative attacks stronger.. We also interpret ${\mathcal{T}}$ and ${\mathcal{T}}$ as vectors with $m$ coordinates with a large alphabet and let $\mathsf{HD}$ be the Hamming distance for such vectors of $m$ coordinates. For any $c\in{\mathcal{C}}$, we define the following properties for $A$.

$A$ is called plausible (with respect to $c$), if $y=c(x)$ for all $(x,y)\in{\mathcal{T}}^{\prime}$.

$A$ has tampering budget $b\in[m]$ if for all ${\mathcal{T}}\leftarrow({\bm{\upmu}},c({\bm{\upmu}}))^{m},{\mathcal{T}}^{\prime}\leftarrow A({\mathcal{T}})$, we have

$A$ has average tampering budget $b$, if we have:

Before proving our results about the power of poisoning attacks, we need to define the confidence function of a learning algorithm under such attacks.

For a learning algorithm $L$ for a classification problem $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathcal{C}})$, we use $\mathsf{Conf}_{A}$ to define the adversarial confidence in the presence of a poisoning adversary $A$. Namely,

By $\mathsf{Conf}(\cdot)$, we denote $L$’s confidence function without any attack; namely, $\mathsf{Conf}(\cdot)=\mathsf{Conf}_{I}(\cdot)$ for the trivial (identity) attacker $I$ that does not change the training data.

The chosen-instance error for $x$ (without attacks) is then defined as $\mathsf{Err}(m,c,x)=\mathsf{Err}_{I}(m,c,x)$ using the trivial adversary that outputs its input.

2 Decreasing Confidence and Increasing Chosen-Instance Error through Poisoning

The following theorem formalizes (the first part of) Theorem 1.2. We emphasize that by choosing the adversary after the concept function is fixed, we allow the adversary to depend on the concept class. This is also the case in e.g., $p$-tampering poisoning attacks of . However, there is a big distinction between our attacks here and those of , as our attackers need to know the entire training sequence before tampering with them, while the attacks of were online.

For any classification problem $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathcal{C}})$, let $L$ be a deterministic learner, $c\in{\mathcal{C}}$ and $\varepsilon\in$. Also let $\mathsf{Conf}(m,\varepsilon,c)=1-\delta$ be the original confidence of $L$ for error probability $\varepsilon$.

For any $\gamma\in$, there is a plausible poisoning adversary $A$ with tampering budget at most $\sqrt{-\ln(\delta\cdot\gamma)\cdot m}$ such that, $A$ makes the adversarial confidence to be as small as $\gamma$:

There is a plausible poisoning adversary $A$ with average tampering budget $\sqrt{-\ln(\delta)\cdot m/2}$ eliminating all the confidence:

Before proving Theorem 4.5, we introduce a notation.

For $\overline{x}=(x_{1},\dots,x_{m})\in\mathcal{X}^{m}$ we use $(\overline{x},c(\overline{x}))$ to denote $\big((x_{1},c(x_{1})),\dots,(x_{m},c(x_{m}))\big)$.

We first prove Part 1. Let ${\mathcal{F}}=\left\{\overline{x}\in\mathcal{X}^{m}\mid L((\overline{x},c(\overline{x}))=h,\mathsf{Risk}(h,c)>\varepsilon\right\}$, and let ${\mathcal{F}}_{b}$ be the $b$ expansion of ${\mathcal{F}}$ under Hamming distance inside $\mathcal{X}^{m}$.

We now define an adversary $A$ that fulfills the statement of Part 1 of Theorem 4.5. Given a training set ${\mathcal{T}}=(\overline{x},c(\overline{x}))$, the adversary $A$ does the following.

If $\overline{x}\in{\mathcal{F}}_{b}$, it selects an arbitrary $\overline{x}^{\prime}\in{\mathcal{F}}$ where $\mathsf{HD}(\overline{x},\overline{x}^{\prime})\leq b$ and outputs ${\mathcal{T}}^{\prime}=(\overline{x}^{\prime},c(\overline{x}^{\prime}))$.

If ${\mathcal{T}}\not\in{\mathcal{F}}_{b}$, it does nothing and outputs ${\mathcal{T}}$.

By definition, $A$ is using tampering budget at most $b$, as its output is always in a Hamming ball of radius $b$ centered at $\overline{x}$. In addition, $A$ is a plausible attacker, as it always uses correct labels.

We also know that if $A$ goes to Case 1, it always selects some $\overline{x}^{\prime}\in{\mathcal{F}}$, and that means that the generated hypothesis using $A$’s output will have a $\mathsf{Risk}$ greater than or equal to $\varepsilon$. Also, if $A$ goes to Case 2 then it will output the original training set which means the generated hypothesis will have a $\mathsf{Risk}$ less than $\varepsilon$. Therefore, we have

Before proving Part 2, we state the following claim, which we prove using McDiarmid Inequality.

simply because for all $\overline{x}\in{\mathcal{S}}$ we have $f(\overline{x})=0$. Thus, we get $a\leq\sqrt{{-\ln(\varepsilon)\cdot m}/{2}}$. ∎

Now we prove Part 2. We define an adversary $A$ that fulfills the statement of the second part of the theorem. Given a training set ${\mathcal{T}}=(\overline{x},c(\overline{x}))$ the adversary selects some $\overline{x}^{\prime}\in{\mathcal{F}}$ such that $\mathsf{HD}(\overline{x},\overline{x}^{\prime})=\mathsf{HD}(\overline{x},{\mathcal{F}})$ (i.e., one of the closest points in ${\mathcal{F}}$ under Hamming distance). The adversary then outputs ${\mathcal{T}}^{\prime}=(\overline{x}^{\prime},c(\overline{x}^{\prime}))$. It is again clear that this attack is plausible, as the tampered instances are still within the support set of the correct distribution. Also, it is the case that $\mathsf{Conf}_{A}(\varepsilon,c,m)=0$, as the adversary always selects $\overline{x}^{\prime}\in{\mathcal{F}}$. To bound the average budget of $A$ we use Claim 4.6. By the description of $A$, we know that the average number of changes that $A$ makes to $\overline{x}$ is equal to $\operatorname*{\mathbf{E}}_{\overline{x}\leftarrow{\bm{\upmu}}^{(m)}}[\mathsf{HD}(\overline{x},{\mathcal{F}})]$ which, by Claim 4.6, is bounded by $\sqrt{{-\ln(\varepsilon)\cdot m}/{2}}$. ∎

As should be clear from the proof of Theorem 4.5, this proof directly extends to any setting in which the adversary wants to increase the probability of any “bad” event $B$ defined over the hypothesis $h$, if $h$ is produced deterministically based on the training set ${\mathcal{T}}$. More generally, if the learning rule is not deterministic, we can still increase the probability of any bad event $B$ if $B$ is defined directly over the training data ${\mathcal{T}}$. This way, we can increase the probability of bad predicate $B$, where $B$ is defined over the distribution of the hypotheses.

We now state our results about the power of poisoning attacks that increase the average of the error probability of learners. Our attacks, in this case, need to know the final text instance $x$, which makes our attacks targeted poisoning attacks .

For any classification problem $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathcal{C}})$, let $L$ be a deterministic learner, $x\in\mathcal{X}$, $c\in{\mathcal{C}}$, and let $\varepsilon=\mathsf{Err}(m,c,x)$ be the chosen-instance error of $x$ without any attack.

For any $\gamma\in(0,1]$, there is a plausible poisoning adversary $A$ with budget $\sqrt{-\ln(\varepsilon\cdot\gamma)\cdot m}$ such that

There is a plausible poisoning adversary $A$ with average budget$\sqrt{-\ln(\varepsilon)\cdot m}$ such that

The proof is very similar to the proof of Theorem 4.5. We only have to change the description of ${\mathcal{F}}$ as

and then everything directly extends to the new setting. ∎

First now remark on the power of poisoning attacks of Theorems 4.5 and 4.8.

References

Appendix A Risk and Robustness Based on Hypothesis’s Prediction Change

The work of Szegedy et al. , as well as a big portion of subsequent work on adversarial examples, relies on defining adversarial risk and robustness of a hypothesis $h$ based on the amount of adversarial perturbations that change the prediction of $h$. Their definition is independent of the concept function $c$ determining the ground truth. In particular, for a given example $(x,c(x))$ where the prediction of the hypothesis is $h(x)$ (that might indeed be different from $c(x)$), an adversarial perturbation of $x$ is $r$ such that for the instance $x^{\prime}=x+r$ we have $h(x^{\prime})\neq h(x)$ (where $h(x^{\prime})$ may or may not be equal to $c(x^{\prime})$). Hence, since the attacker only cares about changing the prediction of the hypothesis $h$, we refer to adversarial properties (be it adversarial perturbations, adversarial risk, adversarial robustness) under this definition as adversarial properties based on “prediction change” (PC for short)– as opposed to adversarial properties based on the “error region” in Definition 3.1.

In this section, we show that using the concentration function ${\bm{\upalpha}}(\cdot)$ and our proofs of Section 3, one can also bound the PC risk and robustness of hypotheses assuming that we have a concentration function. Then, one can use any concentration function (e.g., those of Lévy families) and obtain the desired upper/lower bounds, just as how we did so for the the results of Subsection 3.2.

Whenever we consider a classification problem $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathbf{d}})$ without explicitly denoting the concept class ${\mathcal{C}}$, we mean that $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},{\mathcal{C}},\mathcal{H},{\mathbf{d}})$ is nice for the trivial set ${\mathcal{C}}$ of constant functions that output either of $y\in Y$. The reason for this definition is that basically, below we will require some concept class, and all we want is that preimages of specific labels under any $h$ are measurable sets, which is implied if the problem is nice with the simple ${\mathcal{C}}$ described.

Prediction change (PC) risk. The PC risk under $b$-perturbation is

PC robustness. For a given non-constant $h\in\mathcal{H}$, we define the PC robustness as the expected perturbation needed to change the labels as follows

Let $(\mathcal{X},\mathcal{Y},{\bm{\upmu}},\mathcal{H},{\mathbf{d}})$ be a nice classification problem. For any $h\in\mathcal{H}$ that is not a constant function, the following hold.

On the other hand, we know that ${\bm{\upmu}}(\mathcal{X}^{2})\geq 1/2$, therefore we have

The proof Part 2 directly follows from the definition of ${\bm{\upalpha}}$ and an argument identical to that of Part 2 of Theorem 3.2.

Let ${\mathcal{E}}=\left\{x\in\mathcal{X}\mid\exists\,x^{\prime}\in\mathcal{B}all_{b}(x),h(x)\neq h(x^{\prime})\right\}$. We know that ${\bm{\upmu}}({\mathcal{E}})\geq 1/2$, therefore by Theorem 3.5 we have

Part 4 follows from an argument that is identical to that of Theorem 3.5.∎

the following corollary directly follows Theorem A.2 above and Definition 3.6 of Lévy families, just the same way Corollary 3.8 could be derived from Theorems 3.2 and 3.5 (by going through a variant of Theorems 3.7 for PC risk and robustness that we skip) to get asymptotic bounds of risk and robustness of classification tasks over Lévy spaces.

Let $\mathsf{P}_{n}$ be a nice classification problem defined over a metric probability space that is a normal Lévy family.