PAC-learning in the presence of evasion adversaries

Daniel Cullina
Princeton University
dcullina@princeton.edu

Arjun Nitin Bhagoji
Princeton University
abhagoji@princeton.edu

Prateek Mittal
Princeton University
pmittal@princeton.edu

Abstract
The existence of evasion attacks during the test phase of machine learning algorithms represents a significant challenge to both their deployment and understanding. These attacks can be carried out by adding imperceptible perturbations to
inputs to generate adversarial examples and finding effective defenses and detectors
has proven to be difficult. In this paper, we step away from the attack-defense arms
race and seek to understand the limits of what can be learned in the presence of anevasion adversary. In particular, we extend the Probably Approximately Correct(PAC)-learning framework to account for the presence of an adversary. We first
define corrupted hypothesis classes which arise from standard binary hypothesis
classes in the presence of an evasion adversary and derive the Vapnik-Chervonenkis(VC)-dimension for these, denoted as the adversarial VC-dimension. We then showthat sample complexity upper bounds from the Fundamental Theorem of Statisticallearning can be extended to the case of evasion adversaries, where the sample
complexity is controlled by the adversarial VC-dimension. We then explicitly
derive the adversarial VC-dimension for halfspace classifiers in the presence of asample-wise norm-constrained adversary of the type commonly studied for evasionattacks and show that it is the same as the standard VC-dimension. Finally, we
prove that the adversarial VC-dimension can be either larger or smaller than thestandard VC-dimension depending on the hypothesis class and adversary, making
it an interesting object of study in its own right.

1

Introduction

Machine learning (ML) has become ubiquitous due to its impressive performance in domains as
varied as image recognition [48, 71], natural language and speech processing [22, 24, 39], gameplaying [11, 57, 70] and aircraft collision avoidance [42]. However, its ubiquity provides adversaries
with both opportunities and incentives to develop strategic approaches to fool machine learning
systems during both training (poisoning attacks) [8, 41, 58, 65] and test (evasion attacks) [7, 15,
34, 55, 56, 61, 75] phases. Our focus in this paper is on evasion attacks targeting the test phase,particularly those based on adversarial examples which add imperceptible perturbations to the input
in order to cause misclassification. A large number of adversarial example-based evasion attacks havebeen proposed against supervised ML algorithms used for image classification [7, 15, 18, 34, 61, 75],
object detection [20, 52, 80], image segmentation [3, 31], speech recognition [16, 83] as well asother tasks [21, 36, 43, 82]; generative models for image data [46] and even reinforcement learningalgorithms [40, 47]. These attacks have been carried out in black-box [6, 10, 19, 51, 59, 60, 75] as wellas in physical settings [27, 49, 69, 73].
To counter these attacks, defenses based on the ideas of adversarial training [34, 53, 76], input denoising through transformations [5, 23, 26, 67, 81], distillation [63], ensembling [1, 4, 74] and featurenullification [77] have been proposed. A number of detectors [30, 31, 33, 35, 54] for adversarial
examples have also been proposed. However, recent work [12–14] has demonstrated that modifications to existing attacks are sufficient to generate adversarial examples that bypass both defenses
32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada.

and detectors. In light of this burgeoning arms race, defenses that come equipped with theoreticalguarantees on robustness have recently been proposed [45, 64, 72]. These have been demonstrated forneural networks with up to four layers.
In this paper, we take a more fundamental approach to understanding the robustness of supervisedclassification algorithms by extending well-understood results for supervised batch learning instatistical learning theory. In particular, we seek to understand the sample complexity of Probably
Approximately Correct (PAC)-learning in the presence of adversaries. This was raised as an open
question for halfspace classifiers by Schmidt et al. [66] in concurrent work which focused on thesample complexity needed to learn specific distributions. We close this open question by showing thatthe sample complexity of PAC-learning when the hypothesis class is the set of halfspace classifers
does not increase in the presence of adversaries bounded by convex constraint sets. We note that
the PAC-learning framework is distribution-agnostic, i.e. it is a statement about learning given
independent, identically distributed samples from any distribution over the input space. We show thisby first introducing the notion of corrupted hypothesis classes, which arise from standard hypothesis
classes in the binary setting in the presence of an adversary. Now, in the standard PAC learning
setting, i.e. adversaries present, the Vapnik-Chervonenkis (VC)-dimension is a way to characterizethe ‘size’ of a hypothesis class which allows for the determination of which hypothesis classes arelearnable and with how much data (i.e. sample complexity). In the adversarial setting, we introduce
the notion of adversarial VC-dimension which is the VC-dimension of the corrupted hypothesis
class. With these definitions in place, we can then prove sample complexity upper bounds from theFundamental Theorem of Statistical Learning in the presence of adversaries that utilize the adversarial
VC-dimension.
In this setting, we explicitly compute the adversarial VC-dimension for the hypothesis class comprising all halfspace classifiers, which then directly gives us the sample complexity of PAC-learning in thepresence of adversaries. This hypothesis class has a VC-dimension of 1 more than the dimension of
the input space when no adversaries are present. We prove that this does not increase in the presenceof an adversary, i.e., the adversarial VC-dimension is equal to the VC-dimension for the hypothesis
class comprising all halfspace classifiers. Our result then raises the question: is the adversarial
VC-dimension always equal to the standard VC-dimension? We answer this question in the negative,
by showing explicit constructions for hypothesis classes and adversarial constraints for which theadversarial VC-dimension can be arbitrarily larger or smaller than the standard VC-dimension.
Contributions: In this paper, we are the first to provide sample complexity bounds for the problem of
PAC-learning in the presence of an evasion adversary. We show that an analog of the VC-dimension
which we term the adversarial VC-dimension allows us to establish learnability and upper boundsample complexity for the case of binary hypothesis classes with the 0-1 loss in the presence ofevasion adversaries. We explicitly compute the adversarial VC-dimension for halfspace classifierswith adversaries with standard `p (p ≥ 1) distance constraints on adversarial perturbations, and showthat it matches the standard VC-dimension. This implies that the sample complexity of PAC-learning
does not increase in the presence of this type of adversary. We also show that this is not always thecase by constructing hypothesis classes where the adversarial VC-dimension is arbitrarily larger orsmaller than the standard one.

2

Adversarial agnostic PAC-learning

In this section, we set up the problem of agnostic PAC-learning in the presence of an evasion adversary
which presents the learner with adversarial test examples but does not interfere with the training
process. We also define the notation for the rest of the paper and briefly explain the connections
between our setting and other work on adversarial examples.
We summarize the basic notation in Table 1. We extend the agnostic PAC-learning setting introduced
by Haussler [37] to include an evasion adversary. In our extension, the learning problem is asfollows. There is an unknown P ∈ P(X × C).1 The learner receives labeled training data (x, c) =((x0 , c0 ), . . . , (xn−1 , cn−1 )) ∼ P n and must select ĥ ∈ H. The evasion adversary receives a labelednatural example (xTest , cTest ) ∼ P and selects y ∈ N (xTest ), the set of adversarial examples in theFormally, we have a sigma algebra Σ ⊆ 2X ×C of events and P(X × C) is the set of probability measureson (X × C, Σ). All hypotheses must be measurable functions relative to Σ.
1

2

Symbol

Usage

XSpace of examples
C = {−1, 1}
Set of classes
H ⊆ (X → C)
Set of hypotheses (labelings of examples)`(c, ĉ) = 1(c 6= ĉ)
0-1 loss function
R⊆X ×X
Binary nearness relation
N (x) = {y ∈ X : (x, y) ∈ R} Neighborhood of nearby adversarial examples
Table 1: Basic notation usedneighborhood of xTest . The adversary gives y to the learner and the learner must estimate cTest . Theirperformance is measured by the 0-1 loss, `(cTest , ĥ(y)).
The neighborhoods N (x) of possible adversarial samples are generated by the binary nearness relation
R: N (x) = {y ∈ X : (x, y) ∈ R}. We require N (x) to be nonempty so some choice of y is always
available.2 When R is the identity relation, IX = {(x, x) : x ∈ X }, the neighborhood is N (x) = {x}and y = xTest , giving us the standard problem of learning without an adversary. If R1 , R2 are nearness
relations and R1 ⊆ R2 , R2 represents a stronger adversary. One way to produce a relation R is froma distance d on X and an adversarial budget constraint : R = {(x, y) : d(x, y) ≤ }. This provides
an ordered family of adversaries of varying strengths and has been used extensively in previous
work [17, 34, 66].
Now, we define the Adversarial Expected and Empirical Risks to measure the learner’s performancein the presence of an evasion adversary.
Definition 1 (Adversarial Expected Risk). The learner’s risk under the true distribution in thepresence of an adversary constrained by the relation R is
LP (h, R) = E(x,c)∼P [ max `(h(y), c)].
y∈N (x)

Let h∗ = argminh∈H LP (h, R). Then, learning is possible if there is an algorithm that, with highprobability, gives us ĥn such that LP (ĥn ) − LP (h∗ ) → 0.
Since the learner does not have access to the true distribution P , it is approximated with the distributionof the empirical random variable, which is equal to (xi , ci ) with probability 1/n for each i ∈{0, . . . , n − 1}.
Definition 2 (Adversarial Empirical Risk Minimization (AERM)). The adversarial empirical risk
minimizer AERMH,R : (X × C)n → (X → C) is defined as
AERMH,R (x, c) = argmin L(x,c) (h, R),h∈H

where L(x,c) is the expected loss under the empirical distribution.
Clearly, a stronger adversary leads to worse performance for the best possible classifier and in turn,worse performance for the learner.
Lemma 1. Let A : (X × C)n → (X → C) be learning algorithm for a hypothesis class H. Suppose
R1 , R2 are nearness relations and R1 ⊆ R2 . For all P ,inf LP (h, R1 ) ≤ inf LP (h, R2 ).

h∈H

h∈H

For all P and all (x, c),
LP (A(x, c), R1 ) ≤ LP (A(x, c), R2 ).
Proof. For all h ∈ H,{(x, c) : ∃y ∈ N1 (x) . h(y) 6= c} ⊆ {(x, c) : ∃y ∈ N2 (x) . h(y) 6= c}
so LP (h, R1 ) ≤ LP (h, R2 ).
2

Additionally, for all y ∈ X , {x ∈ X : (x, y) ∈ R} should be measurable.

3(1)

In other words, if we design a learning algorithm for an adversary constrained by R2 , its performanceagainst a weaker adversary is better. Crucially, note that the algorithm A on both sides of theinequality in Eq. 1 must be the same for the inequality to hold.
While it is clear that the presence of an adversary leads to a decrease in the optimal performance forthe learner, we are now interested in the effect of an adversary on sample complexity. If we add anadversary to the learning setting defined in Definition 3, what happens to the gap in performance
between the optimal classifier and the learned classifier?
Definition 3 (Learnability and Sample Complexity). A hypothesis class H is learnable by empiricalrisk minimization in the presence of an evasion adversary constrained by R if there is a function
mH,R : (0, 1)2 → N (the sample complexity) with the following property. For all 0 < δ < 1 and
0 <  < 1, all n ≥ mH,R (δ, ), and all P ∈ P(X × C),
P n (x, c) : LP (AERMH,R (x, c), R) − inf LP (h, R) ≤  ≥ 1 − δ.
h∈H3Adversarial VC-dimension and sample complexity

In this section, we first describe the notion of corrupted hypotheses,
which arise from standard hypothesis classes with the addition of an
adversary. We then compute the VC-dimension of these hypotheses,
which we term the adversarial VC-dimension and use it to prove
the sample complexity upper bounds learning in the presence of anevasion adversary.
3.1

1
−1

Corrupted hypotheses

The presence of an evasion adversary forces us to learn using acorrupted set of hypotheses. Unlike ordinary hypotheses that always
output some class, these also output the special value ⊥ that means“always wrong”. This corresponds to the adversary being able toselect whichever output does not match c. This is illustrated in
Figure 1.
Let Ce = {−1, 1, ⊥}, where ⊥ is the special “always wrong” output.
e⊆
We can combine the information in H and R into a single set H
e(X → C) by defining the following mapping where κR : (X →e and κR (h) : X → C:eC) → (X → C)−1 ∀y ∈ N (x) : h(y) = −1
κR (h) = x 7→ 1∀y ∈ N (x) : h(y) = 1

⊥∃y0 , y1 ∈ N (x) : h(y0 ) = −1, h(y1 ) = 1.

(a) Optimal evasion attacks against
halfspace classifiers with circles
representing the nearness relation
R

1

⊥

−1

(b) Corrupted halfspace classifier

Figure 1: Combining thefamily of hypotheses withe = {κR (h) : h ∈ H}.
the nearness relation R. The
The corrupted set of hypotheses is then H
top figure depicts some h ∈We note that the equivalence between learning an ordinary hypothe- H and the bottom shows
sis with an adversary and learning a corrupted hypothesis without an κ (h) ∈ H.
eR
adversary allows us to use standard proof techniques to bound thesample complexity.
Lemma 2. For any nearness relation R and distribution P ,LP (h, R) = LP (κR (h), IX ).
Proof. Let h̃ = κR (h). For all (x, c),max `(h(y), c) = 1(∃y ∈ N (x) . h(y) 6= c) = 1(h̃(x) 6= c) = max `(h̃(y), c)y∈N (x)y∈{x}

so LP (h, R) = E[maxy∈N (x) `(h(y), c)] = E[maxy∈{x} `(h̃(y), c)] = LP (h̃, IX ).
4

Now, we define the loss class that arises from a hypothesis class. Each element of a loss class isa function produced from the combination of the loss function with a classifier function. The loss
function derived from a classifier h is λ(h) : X × C → {0, 1}, λ(h) = (y, c) 7→ `(c, h(y)). Thus wee → (X ×C → {0, 1}). Define F, Fe ⊆ (X ×C → {0, 1})have the higher order function λ : (X → C)e respectively: F = {λ(h) : h ∈ H} and Fe = {λ(h̃) :to be the loss classes derived from H and Heh̃ ∈ H}.
Using this concept and notation, we can restate a standard result from the Rademacher complexity
approach to proving sample complexity bounds.
Lemma 3 ( [68] Theorem 26.5). Let fˆ = λ(κR (AERMH,R (x, c))). With probability 1 − δ,rˆe c))) + 32 log(4/δ)
EP (f (x, c)) − inf EP (f (x, c)) ≤ 2R(F(x,
e
n
f ∈F
where
e c) = {(f˜(x0 , c0 ), . . . , f˜(xn−1 , cn−1 )) : f˜ ∈ F}
e
F(x,
X
1
sup sT t.
R(T ) = nn2n t∈Ts∈{−1,1}

In the case of non-adversarial learning, i.e. R = IX , this gives a familiar upper bound on LP (ĥ) −inf h∈H LP (h). To get the correct generalization for the adversarial case, we needed to work with theloss class rather than the hypothesis class.
3.2

Adversarial VC-dimension: VC-dimension for corrupted hypothesis classes

We begin by providing two equivalent definitions of a shattering coefficient, which we use todetermine VC-dimension for standard binary hypothesis classes and adversarial VC-dimension for
their corrupted counterparts.
Definition 4 (Equivalent shattering coefficient definitions). The ith shattering coefficient of a familyof binary classifiers H ⊆ (X → C) is σ(H, i) = maxy∈X i |{(h(y0 ), . . . , h(yi−1 )) : h ∈ H}|.
The alternate definition of shattering in terms of the loss class F ⊆ (X × C → {0, 1}) is
σ 0 (F, i) =maxi i |{(f (y0 , c0 ), . . . , f (yi−1 , ci−1 )) : f ∈ F}|.
(y,c)∈X ×C

Note that these two definitions are indeed equivalent. If F achieves k error patterns on (y, c), then H
achieves k classification patterns on y. If H achieves k classification patterns on y, then F achieves
k error patterns on (y, c) for any choice of c. Thus, σ(H, i) = σ 0 (F, i).
The ordinary VC-dimension is then VC(H) = sup{n ∈ N : σ(H, n) = 2n } = sup{n ∈ N :e ⊆ (X →σ 0 (λ(H), n) = 2n }. The second definition naturally extends to our corrupted classifiers, HeeC), because λ(H) ⊆ (X × C → {0, 1}).
Definition 5 (Adversarial VC-dimension). The adversarial VC-dimension ise n) = 2n }.
AVC(H, R) = sup{n ∈ N : σ 0 (λ(H),These definitions and lemmas can now be combined to obtain a sample complexity upper bound for
PAC-learning in the presence of an evasion adversary.
Theorem 1 (Sample complexity upper bound with an evasion adversary). For a space X , a classifierfamily H, and an adversarial constraint R, there is a universal constant C such thatd log(d/) + log(1/δ)
mH,R (δ, ) ≤ C.
2
where d = AVC(H, R).
Proof. This follows from Lemma 2, Lemma 3, the Massart lemma on the Rademacher complexity ofa finite class [68], and the Shelah-Sauer lemma [68].
Note that the upper bound on sample complexity can be improved via the chaining technique [25].
54

The adversarial VC-dimension of halfspace classifiers

In this section, we consider an evasion adversary with a particular structure, motivated by the practical`p norm-based constraints that are usually imposed on these adversaries in the literature [17, 34]. We
then derive the adversarial VC-dimension for halfspace classifiers corrupted by this adversary andshow that it remains equal to the standard VC-dimension.
Definition 6 (Convex constraint on binary adversarial relation). Let B be a nonempty, closed, convex,
origin-symmetric set.
The seminorm derived from B is kxkB = inf{ ∈ R≥0 : x ∈ B} and the associated distancedB (x, y) = kx − ykB .
Let VB be the largest linear subspace contained in B.
The adversarial constraint derived from B is R = {(x, y) : y−x ∈ B}, or equivalently N (x) = x+B.
Since B is convex and contains the zero-dimensional subspace {0}, VB is well-defined. Note that
this definition of R encompasses all `p bounded adversaries, as long as p ≥ 1.
Definition 7. Let H be a family of classfiers on X = Rd .
For an example x ∈ X and a classifier h ∈ H, define the signed distance to the boundary to beδB (h, x, c) = c · h(x) ·infy∈X :h(y)6=h(x)dB (x, y)

For a list of examples x = (x0 , . . . , xn−1 ) ∈ X n , define the signed distance set to be
DB (H, x, c) = {(δB (h, x0 ), . . . , δB (h, xn−1 )) : h ∈ H}
Let X = Rd and let H be the family of halfspace classifiers: {(x 7→ sgn(aT x − b)) : a ∈ Rd , b ∈ R}.
For simplicity of presentation, we define sgn(0) = ⊥, i.e. we consider classifiers that do not give a
useful value on the boundary. It is well known that the VC-dimension of this family is d + 1 [68].
Our result can be extended to other variants of halfspace classifiers. In Appendix A of our pre-print,
we provide an alternative proof that applies to a more general definition.
For halfspace classifiers, the set DB (H, x, c) is easily characterized.
Theorem 2. Let H be the family of halfspace classfiers of X = Rd . Let B be a nonempty, closed,
convex, origin-symmetric set. Let R = {(x, y) : y − x ∈ B}. Then AVC(H, R) = d + 1 − dim(VB ).
In particular, when B is a bounded `p ball, dim(VB ) = 0, giving AVC(H, R) = d + 1.
Proof. First, we show AVC(H, R) ≤ d + 1 − dim(VB ). Define kwkB∗ = supy∈B wT y, the dual
seminorm associated with B.
For any halfspace classifier h, there are a ∈ Rd and b ∈ R such that f (x) = sgn(g(x)) whereg(x) = aT x − b. Suppose that aT y = 0 for all y ∈ VB . Let H0 be the set of classifiers thatare represented by such a. For a labeled example (x, c), the signed distance to the boundary isc(aT x − b)/kakB∗ . Any point on the boundary can be written as x − z for some  ≥ 0 and z ∈ B.
We have aT (x − z) − b = 0 sodB (x, x − z) ≥  =aT x − baT x − b
≥
.
T
a z
kakB∗

(2)
T

Because B is closed, there is some vector z ∗ ∈ B that maximizes aT z. The point x − akakx−bz ∗ is onB∗the boundary, so the inequality 2 is tight.
If we add the restriction kakB∗ = 1, each h ∈ H0 has a unique representation as sgn ◦g. For
inputs from the set G = {(a, b) ∈ Rd+1 : kakB∗ = 1, ∀y ∈ VB . aT y = 0}, the function (a, b) 7→
δB (f, x, c) is linear. Thus the function (a, b) 7→ (δB (f, x0 , c0 ), . . . , δB (f, xn−1 , cn−1 )) is also linear.
G is a subset of a vector space of dimension d + 1 − dim VB , sodim(span(DB (H0 , x, c))) ≤ d + 1 − dim VB
for any choices of x and c.
6

Now we consider the contribution of the classifiers in H \ H0 . These are represented by a suchthat aT y 6= 0 for some y ∈ VB , or equivalently kakB∗ = ∞. In this case, for all (x, c) ∈ Rd × C,aT (x + VB ) = R. Thus x + VB intersects the classifier boundary, h̃(x) = ⊥, and the distance from x
to the classifier boundary is zero: δB (h, x, c) = 0. Thus DB (H \ H0 , x, c) = {0}, which is alreadyin span(DB (H0 , x, c)).
Let U = span(DB (H, x, c)), let k = dim(U ), and let n > k. Suppose that there is a list of examplesex ∈ X n and a corresponding list of labels c ∈ C n that are shattered by the corrupted classifiers H.
nLet η ∈ {0, 1} be the error pattern achieved by the classifier h. Then ηi = 1(δB (h, xi , ci ) ≤ 1). In
other words, the classification is correct when ci and h(xi ) have the same sign and the distance fromxi to the classification boundary is greater than 1.
Let 1 be the vector of all ones. For each error pattern η, there is some h ∈ H that achieves it if andonly if there is some point in DB (H, x, c) − 1 with the corresponding sign pattern.
Since k < n, then by the following standard argument, we can find a sign pattern that is not achievedby any point in U − 1. Let w ∈ Rn satisfy wT z = 0 for all z ∈ U , w 6= 0, and wT 1 ≥ 0. Thereis a subspace of Rn of dimension n − k of vectors satisfying the first condition. Since n > k, thissubspace contains a nonzero vector u. At least one of u and −u satisfies the third condition.
If a point z ∈ U − 1 has the same sign pattern as w, then wT z > 0. However, we have chosen w suchthat wT z ≤ 0. Thus the classifier family H does not achieve all 2n error patterns, which contradicts
our assumption about (x, c).
e
Now we show AVC(H, R) ≥ d + 1 − dim(VB ) by finding (x, c) that are shattered by H.
Let t = d − dim(VB ), x0 = 0, and (x1 , . . . , xt ) be a basis for the subspace orthogonal to VB . For asubset S ⊆ {1, . . . , t}, consider the affine function gS (x) = aTS x + bS such that (i 7→ g(xi )) = 1(S)and aTS x = 0 for all x ∈ VB . We would like to use the hyperplane gS (x) = 21 to achieve the labelingassociated with S. Let δS = maxx∈B aTS x, which is some finite value because g only varies alonglines for which B is bounded. If δS ≥ 12 for some S, then our current configuration does not work andwe must rescale the points to ensure that they can be shattered. Let δ = max(1, 3 maxS⊆{1,...,t} δS ).
e for any choice of c.
The example list δ · (x0 , . . . , xt ) is shattered by H

5

Adversarial VC Dimension can be larger

We have shown in the previous section that the adversarial
VC-dimension can be smaller than or equal to the standard
VC-dimension. Here, we provide explicit constructions for thecounter-intuitive case when adversarial VC-dimension can bearbitrarily larger than the VC-dimension.
Theorem 3. For any d ∈ N, there is a space X , an adversarialconstraint R ⊆ X × X , and a hypothesis class H : X → C
such that VC(H) = 1 and AVC(H, R) ≥ d.
Proof. Let X = Zd . Let H = {hx : x ∈ X }, where1
y=x
hx (y) =−1 y 6= x.

Figure 2: The examples x0 =(−1, 1) and x1 = (1, −1) aremarked with crosses. The function
h(0,1) ∈ H maps the smaller square
The VC dimension of this family is 1 because no classifier to 1 and everything else to −1.
eoutputs the labeling (1, 1) for any pair of distinct examples.
The corrupted function h̃(0,1) ∈ H
maps the larger square to ⊥ and evConsider the adversary with an `∞ budget of 1. No corerything else to −1. Observe that
rupted classifier will ever output 1, only 0 and ⊥. Taked dh̃(0,1) (x0 ) = ⊥ and h̃(0,1) (x1 ) =x = (x0 , . . . , xd−1 ) ∈ (Z ) :−1.
−1 j = i(xi )j =1
j 6= i.
7

Now consider the 2d classifiers that are the indicators for y ∈{0, 1}[d] : h̃y = κ(hy ). Observe that
−1 yi = 1h̃y (xi ) =⊥ yi = 0
because if yi = 1 then d∞ (xi , y) = 2 but if yi = 0 then d∞ (xi , y) = 1. Thus(h̃y (x0 ), . . . , h̃y (xd−1 )) contains ⊥ at each index that y contains 1. If the examples are all labeled with −1, this subset of the corrupted classifier family achieves all 2d possible error patterns.
The adversarial VC dimension is at least d.
Because `(c, −1) ≤ `(c, ⊥) for all c ∈ {−1, 1}, in the hypothesis class constructed in the proof of
Theorem 3, h1 is clearly the best hypothesis. For all (x, c) ∈ Zd × {−1, 1} and all y ∈ {0, 1}d , wehave `(c, h̃1 (x)) ≤ `(c, h̃y (x)). Thus h1 can be selected without examining any training data andthe sample complexity is mH,R (δ, ) = 0.
Theorem 3 shows that the addition of an adversary can lead to a significantly weaker upper boundon sample complexity. It does not show that the addition of an adversary can increase the sample
complexity and whether this is possible remains an open question.

6

Related work and Concluding Remarks

In this paper, we are the first to demonstrate sample complexity bounds on PAC-learning in thepresence of an evasion adversary. We now compare with related work and conclude.
6.1

Related Work

The body of work on attacks and defenses for machine learning systems is extensive as describedin Section 1 and thus we only discuss the closest related work here. We refer interested readers toextensive recent surveys [9, 50, 62] for a broader overview.
PAC-learning with poisoning adversaries: Kearns and Li [44] studied learning in the presence ofa training time adversary, extending the more benign framework of Angluin and Laird [2] whichlooked at noisy training data.
Classifier-specific results: Wang et al. [78] analyze the robustness of nearest neighbor classifiers
while Fawzi et al. [28, 29] analyze the robustness of linear and quadratic classifiers under bothadversarial and random noise. Hein and Andriushchenko [38] provide bounds on the robustness ofneural networks of up to one layer while Weng et al. [79] use extreme value theory to bound therobustness of neural networks of arbitrary depth. Both these works assume Lipschitz continuousfunctions. In contrast to our work, all these show how robust a given classifier is and do not address
the issue of learnability and sample complexity.
Distribution-specific results: Schimdt et al. [66] study the sample complexity of learning a mixtureof Gaussians as well as Bernoulli distributed data in the presence of `∞ -bounded adversaries.
√ For theformer, they show that for all classifiers, the sample complexity increases by an order of d, while
it only increases for halfspace classifiers for the latter distribution. Gilmer et al. [32] analyze therobustness of classifiers for a distribution consisting of points distributed on two concentric spheres.
In contrast to these papers, we prove our results in a distribution-agnostic setting.
Wasserstein distance-based constraint: Sinha et al. [72] consider a different adversarial constraint,
based on the Wasserstein distance between the benign and adversarial distributions. They thenstudy the sample complexity of Stochastic Gradient Descent for minimizing the relaxed Lagrangian
formulation of the learning problem with this constraint. Their constraint allows for different samples
to be perturbed with different budgets while we study a sample-wise constraint on the adversary.
Objective functions for robust classifiers: Raghunathan et al. [64] and Kolter and Wong [45] takesimilar approaches to setting up a solvable optimization problem that approximates the worst-caseadversary in order to carry out adversarial training. Their focus is not on the sample complexity
needed for learning, but rather on provable robustness achieved against `∞ -bounded adversaries bychanging the training objective.
86.2

Concluding remarks

While our results provide a useful theoretical understanding of the problem of learning with adversaries, the nature of the 0-1 loss prevents the efficient implementation of Adversarial ERM to obtainrobust classifiers. In practice, recent work on adversarial training [34, 53, 76], has sought to improve
the robustness of classifiers by directly trying to find a classifier that minimizes the Adversarial
Expected Risk, which leads to a saddle point problem [53]. A number of heuristics are used to enable
the efficient solution of this problem, such as replacing the 0-1 loss with smooth surrogates like thelogistic loss and approximating the inner maximum by a Projected Gradient Descent (PGD)-based adversary [53] or by an upper bound [64]. Our framework now allows for an analysis of the underlying
PAC learning problem for these approaches. An interesting direction is thus to find the adversarial
VC-dimension for more complex classifier families such as piece-wise linear classifiers and neuralnetworks. Another natural next step is to understand the behavior of convex learning problems in thepresence of adversaries, in particular the Regularized Loss Minimization framework.
Acknowledgments
This work was supported by the National Science Foundation under grants CNS-1553437, CIF1617286 and CNS-1409415, by Intel through the Intel Faculty Research Award and by the Office ofNaval Research through the Young Investigator Program (YIP) Award.

References[1] Mahdieh Abbasi and Christian Gagné. Robustness to adversarial examples through an ensemble ofspecialists. arXiv preprint arXiv:1702.06856, 2017.
[2] Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4):343–370, 1988.
[3] Anurag Arnab, Ondrej Miksik, and Philip H. S. Torr. On the robustness of semantic segmentation models
to adversarial attacks. In CVPR, 2018.
[4] Alexander Bagnall, Razvan Bunescu, and Gordon Stewart. Training ensembles to detect adversarial
examples. arXiv preprint arXiv:1712.04006, 2017.
[5] Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Dimensionality reduction as a defense against
evasion attacks on machine learning classifiers. arXiv preprint arXiv:1704.02654, 2017.
[6] Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Black-box attacks on deep neural networks via
gradient estimation. In ICLR Workshop, 2018.
[7] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Giorgio
Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European
Conference on Machine Learning and Knowledge Discovery in Databases, pages 387–402. Springer, 2013.
[8] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In
Proceedings of the 29th International Conference on Machine Learning (ICML-12), pages 1807–1814,
2012.
[9] Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning.
arXiv preprint arXiv:1712.03141, 2017.
[10] Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks
against black-box machine learning models. In ICLR, 2018.
[11] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top
professionals. Science, page eaao1733, 2017.
[12] Nicholas Carlini and David Wagner. Defensive distillation is not robust to adversarial examples. arXiv
preprint arXiv:1607.04311, 2016.
[13] Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection
methods. In AISec, 2017.
[14] Nicholas Carlini and David Wagner. Magnet and “efficient defenses against adversarial attacks” are notrobust to adversarial examples. arXiv preprint arXiv:1711.08478, 2017.
[15] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Security
and Privacy (SP), 2017 IEEE Symposium on, pages 39–57. IEEE, 2017.
[16] Nicholas Carlini and David Wagner. Audio adversarial examples: Targeted attacks on speech-to-text. In
DLS (IEEE SP), 2018.

9

[17] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. CoRR,
abs/1608.04644, 2016.
[18] Pin-Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deepneural networks via adversarial examples. In AAAI, 2018.
[19] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization
based black-box attacks to deep neural networks without training substitute models. In Proceedings of the10th ACM Workshop on Artificial Intelligence and Security, pages 15–26. ACM, 2017.
[20] Shang-Tse Chen, Cory Cornelius, Jason Martin, and Duen Horng Chau. Robust physical adversarial attack
on faster r-cnn object detector. arXiv preprint arXiv:1804.05810, 2018.
[21] Moustapha Cisse, Yossi Adi, Natalia Neverova, and Joseph Keshet. Houdini: Fooling deep structured
prediction models. In NIPS, 2017.
[22] Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa.
Natural language processing (almost) from scratch. Journal of Machine Learning Research, 12(Aug):2493–
2537, 2011.
[23] Nilaksh Das, Madhuri Shanbhogue, Shang-Tse Chen, Fred Hohman, Siwei Li, Li Chen, Michael E
Kounavis, and Duen Horng Chau. Shield: Fast, practical defense and vaccination for deep learning usingjpeg compression. arXiv preprint arXiv:1802.06816, 2018.
[24] Li Deng, Geoffrey Hinton, and Brian Kingsbury. New types of deep neural network learning for speech
recognition and related applications: An overview. In Acoustics, Speech and Signal Processing (ICASSP),
2013 IEEE International Conference on, pages 8599–8603. IEEE, 2013.
[25] R Dudley. Sizes of compact subsets of hilbert space and continuity of gaussian processes. J. Funct. Anal.,
1:290–330, 1967.
[26] Gintare Karolina Dziugaite, Zoubin Ghahramani, and Daniel M Roy. A study of the effect of JPG
compression on adversarial images. arXiv preprint arXiv:1608.00853, 2016.
[27] Ivan Evtimov, Kevin Eykholt, Earlence Fernandes, Tadayoshi Kohno, Bo Li, Atul Prakash, Amir Rahmati,
and Dawn Song. Robust physical-world attacks on machine learning models. In CVPR, 2018.
[28] Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Analysis of classifiers’ robustness to adversarial
perturbations. Machine Learning, 107(3):481–508, 2018.
[29] Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Robustness of classifiers: fromadversarial to random noise. In NIPS, 2016.
[30] Reuben Feinman, Ryan R Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples
from artifacts. arXiv preprint arXiv:1703.00410, 2017.
[31] Volker Fischer, Mummadi Chaithanya Kumar, Jan Hendrik Metzen, and Thomas Brox. Adversarial
examples for semantic image segmentation. In ICLR Workshop, 2017.
[32] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and
Ian Goodfellow. Adversarial spheres. In ICLR, 2018.
[33] Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku. Adversarial and clean data are not twins. arXiv preprint
arXiv:1704.04960, 2017.
[34] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples.
In International Conference on Learning Representations, 2015.
[35] Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick McDaniel. On the(statistical) detection of adversarial examples. arXiv preprint arXiv:1702.06280, 2017.
[36] Kathrin Grosse, Nicolas Papernot, Praveen Manoharan, Michael Backes, and Patrick McDaniel. Adversarial
examples for malware detection. In European Symposium on Research in Computer Security, pages 62–79.
Springer, 2017.
[37] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning
applications. Information and Computation, 100(1), 1992.
[38] Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against
adversarial manipulation. In Advances in Neural Information Processing Systems, pages 2263–2273, 2017.
[39] Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew
Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic
modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing
Magazine, 29(6):82–97, 2012.
[40] Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks onneural network policies. In ICLR, 2017.

10

[41] Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulatingmachine learning: Poisoning attacks and countermeasures for regression learning. In IEEE Security andPrivacy, 2018.
[42] Kyle D Julian, Jessica Lopez, Jeffrey S Brush, Michael P Owen, and Mykel J Kochenderfer. Policy
compression for aircraft collision avoidance systems. In Digital Avionics Systems Conference (DASC),2016 IEEE/AIAA 35th, pages 1–10. IEEE, 2016.
[43] Alex Kantchelian, JD Tygar, and Anthony D Joseph. Evasion and hardening of tree ensemble classifiers.
In Proceedings of the 33rd International Conference on Machine Learning (ICML-16), 2016.
[44] Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing,22(4):807–837, 1993.
[45] J Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer
adversarial polytope. In ICML, 2018.
[46] Jernej Kos, Ian Fischer, and Dawn Song. Adversarial examples for generative models. arXiv preprint
arXiv:1702.06832, 2017.
[47] Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. In ICLR Workshop, 2017.
[48] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional
neural networks. In Proceedings of the 25th International Conference on Neural Information Processing
Systems - Volume 1, NIPS’12, pages 1097–1105, USA, 2012. Curran Associates Inc.
[49] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv
preprint arXiv:1607.02533, 2016.
[50] Qiang Liu, Pan Li, Wentao Zhao, Wei Cai, Shui Yu, and Victor CM Leung. A survey on security threats
and defensive techniques of machine learning: A data driven view. IEEE access, 6:12103–12117, 2018.
[51] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples andblack-box attacks. In ICLR, 2017.
[52] Jiajun Lu, Hussein Sibai, and Evan Fabry. Adversarial examples that fool detectors. arXiv preprint
arXiv:1712.02494, 2017.
[53] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards
deep learning models resistant to adversarial attacks. In ICLR, 2018.
[54] Dongyu Meng and Hao Chen. Magnet: a two-pronged defense against adversarial examples. In Proceedingsof the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 135–147. ACM,
2017.
[55] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In CVPR, 2017.
[56] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate
method to fool deep neural networks. In CVPR, 2016.
[57] Matej Moravčı́k, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis,
Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence inheads-up no-limit poker. Science, 356(6337):508–513, 2017.
[58] Mehran Mozaffari-Kermani, Susmita Sur-Kolay, Anand Raghunathan, and Niraj K Jha. Systematic
poisoning attacks on and defenses for machine learning in healthcare. IEEE journal of biomedical andhealth informatics, 19(6):1893–1905, 2015.
[59] Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: fromphenomena to black-box attacks using adversarial samples. arXiv preprint arXiv:1605.07277, 2016.
[60] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami.
Practical black-box attacks against deep learning systems using adversarial examples. In Proceedings ofthe 2017 ACM Asia Conference on Computer and Communications Security, 2017.
[61] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami.
The limitations of deep learning in adversarial settings. In 2016 IEEE European Symposium on Security
and Privacy (EuroS&P), pages 372–387. IEEE, 2016.
[62] Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman. Towards the science of
security and privacy in machine learning. arXiv preprint arXiv:1611.03814, 2016.
[63] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense
to adversarial perturbations against deep neural networks. In Security and Privacy (SP), 2016 IEEE
Symposium on, pages 582–597. IEEE, 2016.
[64] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In
ICLR, 2018.

11

[65] Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph, Shing-hon Lau, Satish Rao,
Nina Taft, and JD Tygar. Stealthy poisoning attacks on pca-based anomaly detectors. ACM SIGMETRICS
Performance Evaluation Review, 37(2):73–74, 2009.
[66] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversariallyrobust generalization requires more data. arXiv preprint arXiv:1804.11285, 2018.
[67] Uri Shaham, James Garritano, Yutaro Yamada, Ethan Weinberger, Alex Cloninger, Xiuyuan Cheng, Kelly
Stanton, and Yuval Kluger. Defending against adversarial images using basis functions transformations.
arXiv preprint arXiv:1803.10840, 2018.
[68] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.
[69] Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K Reiter. Accessorize to a crime: Real andstealthy attacks on state-of-the-art face recognition. In Proceedings of the 2016 ACM SIGSAC Conference
on Computer and Communications Security, pages 1528–1540. ACM, 2016.
[70] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez,
Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without humanknowledge. Nature, 550(7676):354, 2017.
[71] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
[72] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principledadversarial training. In ICLR, 2018.
[73] Chawin Sitawarin, Arjun Nitin Bhagoji, Arsalan Mosenia, Prateek Mittal, and Mung Chiang. Rogue signs:
Deceiving traffic sign recognition with malicious ads and logos. In DLS (IEEE SP), 2018.
[74] Charles Smutz and Angelos Stavrou. When a tree falls: Using diversity in ensemble classifiers to identify
evasion in malware detectors. In NDSS, 2016.
[75] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, andRob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
[76] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. In ICLR, 2018.
[77] Qinglong Wang, Wenbo Guo, Kaixuan Zhang, Alexander G Ororbia II, Xinyu Xing, Xue Liu, and C Lee
Giles. Adversary resistant deep neural networks with an application to malware detection. In Proceedingsof the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages
1145–1153. ACM, 2017.
[78] Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors toadversarial examples. In ICML, 2018.
[79] Tsui-Wei Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca
Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In ICLR, 2018.
[80] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adversarial examples
for semantic segmentation and object detection. In International Conference on Computer Vision. IEEE,
2017.
[81] Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neuralnetworks. In NDSS, 2018.
[82] Weilin Xu, Yanjun Qi, and David Evans. Automatically evading classifiers. In Proceedings of the 2016
Network and Distributed Systems Symposium, 2016.
[83] Xuejing Yuan, Yuxuan Chen, Yue Zhao, Yunhui Long, Xiaokang Liu, Kai Chen, Shengzhi Zhang, Heqing
Huang, Xiaofeng Wang, and Carl A Gunter. Commandersong: A systematic approach for practical
adversarial voice recognition. In USENIX Security, 2018.

12