Adversarial examples from computational constraints

authors propose a simple classification task, namely distinguishing between samples on the unit

sphere in high dimension and samples on a sphere of radius R bounded away from 1. They show

experimentally that even in such a simple setup, state-of-the-art neural networks have adversarial

examples at most points. We note however that this example only applies to specific classifiers,

2

since it is easy to construct an efficient robust classifier for the given example (e.g., just use a linear

model on the norm of the features); thus the “hardness” here only appears for a given network

structure.

Supporting hypothesis 2 is the work of Schmidt et al. [16]. Here the authors consider a mixture

of two separated Gaussians (isotropic, with means at distance Θ(

d)). With such a separation a

single sample is sufficient to learn non-robustly; but to learn a classifier that is robust to O(1)-size

perturbations in (cid:96)∞-norm one needs Ω(

d) samples. This polynomial separation suggests that

avoiding adversarial examples in high dimension requires a lot more samples than mere learning—

d samples. In fact, since their hard instance is essentially a set of 2d possible

but only up to

distributions, our secondary result gives a black-box algorithm that would produce a robust classifier

with O(d) samples.

√

√

√

Finally the large body of work on “adversarial defense” can be viewed as investigating hypothesis

4. We note that, at the time of writing, the state of the art defense Madry et al. [14] (according

to [1]) is still far from being robust. Indeed on the CIFAR-10 dataset its accuracy is below 50%

even with very small perturbations (of order 10−2 in (cid:96)∞-norm), while state of the art non-robust

accuracy is higher than 95%.

1.2 The SQ model

Proving computational hardness is a notoriously difficult problem. To circumvent this difficulty

one usually either (i) reduces the problem at hand to a well-established computational hardness

conjecture (e.g., proving NP-hardness), or (ii) proves an unconditional hardness within a limited

computational framework (such as the oracle lower bounds in convex optimization, [15]). Our task

here is further complicated by the average-case nature of the problem (the datasets are i.i.d. from

some fixed distribution). Fortunately there is a growing set of results on computational hardness

in learning theory that we can leverage. The statistical query (SQ) model of computation from

Kearns [12] is a particularly successful instance of approach (ii) for learning theory: (a) most known

learning algorithms fall in the framework, including in particular logistic regression, SVM, stochastic

gradient descent, etc; and (b) SQ-hardness has been proved for many interesting problems that are

believed to be computationally hard, such as learning parity with noise [12], learning intersection

of halfspaces [13], the planted clique problem [8], robust estimation of high-dimensional Gaussians

[4], or learning a function computable by a small neural network [17]. Thus we naturally use this

model to prove our main result on the computational hardness of robust learning. We now recall

the definition of the SQ model and state informally our main result.

As Kearns put it in his original paper, the SQ model considers “learning algorithms that con-

struct a hypothesis based on statistical properties of large samples rather than on the idiosyncrasies

of a particular sample”. More precisely, rather than having access to a data set (Xi, f (Xi)), in the

SQ model one must make queries to a τ -SQ oracle which operates as follows: given a [0, 1]-valued

function ψ defined on input/output pairs, the SQ oracle returns a value EX∼D ψ(X, f (X))+ξ where

|ξ| ≤ τ . We refer to τ as the precision of the oracle. Obviously, an algorithm using T queries to an

oracle with precision τ can be simulated using a data set of size roughly T /τ 2. In our main result

we consider an oracle with exponential precision. More concretely we take τ of order exp(−Cdc)

where d is the dimension of the problem and c, C > 0 are some numerical constants. Observe

that such a high precision oracle cannot be simulated with a polynomial (in d) number of samples.

Yet we show that even with such a high precision one needs an exponential number of queries to

achieve robust learning for a certain task which on the other hand is easy to learn, and information

theoretically learnable robustly:

Theorem 1.1 (informal). For any M, ε > 0, there exists a classification task in Rd which is

3

• learnable in poly(d) time and poly(d) samples;

• robustly learnable in poly(d) samples with (cid:96)2-robustness parameter M (while with high prob-

√

ability all samples have (cid:96)2-norm O(

d));

• not efficiently and robustly learnable in the statistical query model, in the sense that even

with an exponential (in d) precision statistical query oracle one needs an exponential (in d)

number of queries in order to robustly learn with robustness parameter ε.

√

d log d).

The same result holds using the (cid:96)∞ norm instead of (cid:96)2, except with diameter O(

Of course, a number of natural machine learning algorithms such as nearest neighbor are not

based on statistical queries. Although we cannot prove it, we believe that our input distributions

are computationally hard in general. For the case of nearest neighbor, the distance to points of each

class have very similar distributions—indeed, the two distributions match on polynomially many

moments. This suggests that exponentially many samples are necessary for nearest neighbor. For

more information about nearest neighbor classifiers in the context of adversarial examples, see [20].

Moreover, there are very few problems in any domain with exponential SQ hardness for which

polynomial time algorithms are known; in fact, the only such problems involve solving systems of

linear equations over finite fields [7]. Since Theorem 1.1 involves a real-valued problem, finding a

polynomial time algorithm that avoids the SQ lower bound would be a remarkable breakthrough

in SQ theory.

1.3 Overview of proofs

Our secondary result, on the information theoretic achievability of robustness, is proved via simple

arguments reminiscent of PAC-learning theory. Namely, if a classifier is not good enough for a

given pair of distributions, we can rule it out with high confidence by looking at not too many

samples. Then, we use a union bound to claim the result for a family of pairs that is either at most

exponentially large, or is at least covered by a net of at most exponential size (the only subtlety is

in the proper definition of a net in this robust context).

Our primarily result, on the hardness of robustness, is technically much more challenging. The

central object in the proof is a natural high-dimensional generalization of a construction from Di-

akonikolas et al. [4]. Roughly speaking, a hard pair of distributions is obtained by taking a stan-

dard multivariate Gaussian, choosing a random k-dimensional subspace and planting there two

well-separated distributions that match many moments of a Gaussian (in [4] only the case k = 1 is

considered). To show an SQ lower bound, we use – as in [4] – the framework of [2, 8] to reduce the

question to computing a certain non-standard notion of correlation between the distributions. To

bound said correlation, we deviate from [4] significantly, since their argument is tailored crucially

to the case k = 1. Our argument is less precise, but allows k (cid:29) 1 which is necessary to obtain a

large separation between the distributions (which in turn controls the parameter M in Theorem

1.1).

2 Definitions

Throughout we restrict ourselves to binary classifiers, Rd-feature space, as well as to balanced

classes. We fix some norm (cid:107) · (cid:107) in Rd, and we denote B(ε) = {z ∈ Rd : (cid:107)z(cid:107) ≤ ε}.

Definition 2.1. The ε-robust zero-one loss (with respect to (cid:107) · (cid:107)) is defined as follows, for f : Rd →

{0, 1} and (x, i) ∈ Rd × {0, 1},

(cid:96)ε(f, x, i) = 1{∃ z ∈ B(ε) : f (x + z) (cid:54)= i} .

4

Definition 2.2. A binary classifier f : Rd → {0, 1} is (ε, δ)-robust for a pair of distributions

(D0, D1) on X if for any i ∈ {0, 1},

E

X∼Di

[(cid:96)ε(f, X, i)] ≤ δ .

Definition 2.3. A (binary) classification task is given by a family D of pairs of distributions

D = (D0, D1) over a domain X . A classification algorithm receives datasets X 0, X 1 consisting of

n i.i.d. samples from D0 and D1 respectively, and outputs a classifier f : Rd → {0, 1}.

We say that D is (ε, δ)-robustly learnable with n samples if there is a classification algorithm

such that, for every D ∈ D, with probability at least 2/3 over X 0 and X 1, the algorithm produces

a classifier f that is (ε, δ)-robust for D.

Remark 2.4. The success probability 2/3 is an arbitrary constant larger than 1/2. It is easy to see

that, for any η > 0, by using O(n log(1/η)) samples one can obtain a success probability of 1 − η.

We also note that the classical (ε(cid:48), δ(cid:48))-PAC learning scenario, with δ(cid:48) = 1/3, corresponds to our

definition of (ε, δ)-robust classification with parameters ε = 0 and δ = ε(cid:48). Slightly more precisely, a

concept class F ⊂ {0, 1}Rd for PAC-learning corresponds to the family D of all pairs of distribution

supported respectively on f −1(0) and f −1(1) for some f ∈ F.

Definition 2.5. We say that D is (ε, δ)-robustly feasible if every D ∈ D admits an (ε, δ)-robust

classifier. When it exists we denote fD for such a classifier (chosen arbitrarily among all robust

classifiers for D), and FD = {fD, D ∈ D}.

3 Robust learning with few samples

Obviously robust feasibility is a necessary condition for robust learnability. We show that it is

in fact sufficient, even for sample efficient robust learnability. We first do so when a finite set of

classifiers FD suffices for robust feasibility.

3.1 Robust empirical risk minimization

Theorem 3.1. Assume that D is (ε, δ)-robustly feasible. Then it is (ε, δ + δ(cid:48))-robustly learnable

with n = Ω

(cid:16) δ+δ(cid:48)

.

(cid:17)

δ(cid:48)2 log(|FD|)

(cid:80)n

Proof. Let ˆDi = 1

j=1 δX i(j) be the empirical measure corresponding to the dataset X i. We

n

will show that ERM on the ε-robust loss gives the claimed sample complexity. More precisely we

consider the classification algorithm that outputs:

ˆf = arg min

f ∈FD

max

i∈{0,1}

E

X∼ ˆDi

(cid:96)ε(f, X, i) .

For shorthand notation we write pf = maxi∈{0,1} EX∼Di (cid:96)ε(f, X, i) and ˆpf = maxi∈{0,1} E

In particular we simply want to prove that p ˆf ≤ δ +δ(cid:48). Note that by definition pfD ≤ δ. A standard

Chernoff bound gives that, with probability at least 2/3, one has for every f ∈ FD,

X∼ ˆDi

(cid:96)ε(f, X, i).

|pf − ˆpf | = O(

pf log(|FD|)/n) .

(cid:113)

Now observe that for n ≥ 4 δ+δ(cid:48)

δ(cid:48)2 log(|FD|)

obtain with n = Ω

(cid:16) δ+δ(cid:48)

(cid:17)

δ(cid:48)2 log(|FD|) one can has (cid:112)pfD log(|FD|)/n ≤ δ(cid:48)/2 , and thus we

p ˆf −

,

δ(cid:48)

2

(cid:114) p ˆf

δ + δ(cid:48) ≤ ˆp ˆf ≤ ˆpfD ≤ δ + δ(cid:48) .

5

It now suffices to observe that s ≥ δ + δ(cid:48) implies s − δ(cid:48)

2

(cid:113) s

δ+δ(cid:48) > δ + δ(cid:48)

2 .

3.2 Robust covering number

In many natural situations the classification task is specified by a continuous set of distributions.

For example one might have a set of the form D = {(g0(w0), g1(w1)), (w0, w1) ∈ Ω} where g0 and

g1 are Lipschitz functions and Ω is some compact subset of Rd(cid:48). In this case Theorem 3.1 does not

apply, although one would like to say that “essentially” D is of log-size roughly d(cid:48). The classical

solution to this difficulty is with covering numbers:

Definition 3.2. For a metric space (X , dist) we write

(cid:40)

Ndist(X , ε) = inf

|X| s.t. X ⊂ X and X ⊂

{y : dist(x, y) ≤ ε}

.

(cid:41)

(cid:91)

x∈X

With a slight abuse of notation we also extend the distance to the Cartesian product X × X by

dist((x, x(cid:48)), (y, y(cid:48))) = max(dist(x, x(cid:48)), dist(y, y(cid:48))).

With the above definitions one can obtain the following result as a straightforward corollary of

Theorem 3.1 and the definition of total variation distance.

Theorem 3.3. Assume that D is (ε, δ)-robustly feasible. Then D is (ε, δ + 2δ(cid:48))-robustly learnable

with n = Ω

(cid:17)

δ(cid:48)2 log(NTV(D, δ(cid:48)))

(cid:16) δ+δ(cid:48)

.

In fact, if one is willing to lose a little bit of robustness, one can use a significantly weaker

notion of “distance” than total variation. Indeed we can consider a broader class of modifications

to a distribution that preserves the robustness of a classifier:

in Theorem 3.3 we used that we

can move arbitrarily a small amount of mass, but in fact we can also move a little an arbitrary

amount of mass. While the former type of movement corresponds to total variation distance, the

latter corresponds to the (infinity) Wasserstein distance. We denote W∞(D, D(cid:48)) for the infimum of

sup(x,x(cid:48))∈supp(µ) (cid:107)x − x(cid:48)(cid:107) over all measures µ(x, x(cid:48)) with marginal over x (respectively x(cid:48)) equal to

D (respectively D(cid:48)). Next we introduce a slightly non-standard notion of covering with respect to

a pair of distances

Definition 3.4. For a metric space X equipped with two distances dist and dist(cid:48) we define an (ε, δ)

neighborhood by2:

Uε,δ(x) = (cid:8)y : ∃z s.t. dist(cid:48)(x, z) ≤ δ and dist(z, y) ≤ ε(cid:9) .

The corresponding covering number is:

Ndist,dist(cid:48)(X , ε, δ) = inf

|X| s.t. X ⊂ X and X ⊂

(cid:40)

(cid:41)

Uε,δ(x)

.

(cid:91)

x∈X

It is now easy to prove the following strengthening of Theorem 3.3:

2The choice of first moving with dist(cid:48) and then with dist will fit our application.

In general a more natural

definition would be:

Uε,δ(x) = {y : ∃x = z1, z(cid:48)

1, . . . , zn, z(cid:48)

n = y s.t.

dist(zi, z(cid:48)

i) ≤ ε and

n−1

(cid:88)

i=1

dist(cid:48)(z(cid:48)

i, zi+1) ≤ δ} .

n

(cid:88)

i=1

6

Theorem 3.5. Assume that D is (ε, δ)-robustly feasible. Then D is (ε−ε(cid:48), δ+2δ(cid:48))-robustly learnable

with n = Ω

(cid:17)

δ(cid:48)2 log(NW∞,TV(D, ε(cid:48), δ(cid:48)))

(cid:16) δ+δ(cid:48)

.

Proof. Let A be the set realizing the infimum in the definition of NW∞,TV(D, ε(cid:48), δ(cid:48)). Observe that

D is (ε − ε(cid:48), δ + δ(cid:48))-robustly feasible with classifiers from FA, and apply Theorem 3.1.

3.3 Covering number bound from generative models

We now show that distributions approximated by generative models have bounded covering numbers

(in terms of Definition 3.4), so Theorem 3.5 gives a good sample complexity for such distributions.

The proof is deferred to Appendix C in the supplementary material.

Definition 3.6. A generative model gw : Rk → Rd is a neural network indexed by weights w ∈ Rm.

The generated distribution D(gw) is the distribution given by gw(x) for x ∼ N (0, Ik).

Lemma 3.7. Let gw be an (cid:96)-layer neural network architecture with at most d activations in each

layer and Lipschitz nonlinearities such as ReLUs. Consider any family of distribution pairs D such

that for each D ∈ D, and each i ∈ {0, 1}, there exists some w ∈ [−B, B]m with W∞(Di, D(gw)) ≤ ε.

Then

log (NW∞,TV(D, ε + δ, δ)) ≤ O(m(cid:96) log(dB/δ)).

4 Lower bound for the SQ model

Let D0 and D1 be two distributions over a set X , for which we would like to solve a (binary)

classification task. The SQ model, introduced in [12], is defined as follows. An algorithm is allowed

to access D0 and D1 through queries of the following kind. A query is specified by a function

h : X → [0, 1], and the response is two numbers u, v ∈ R such that u ∈ Ex∼D0[h(x)] ± τ and

v ∈ Ex∼D1[h(x)] ± τ . Here τ > 0 is a positive parameter called precision. After asking a number

of such queries, the algorithm must output a required (robust or non-robust) classifier for D0 and

D1.

Our main result is as follows:

Theorem 4.1. For every sufficiently small ρ, γ > 0 the following holds. There exists a family of

2dO(1) pairs of distributions ( (cid:101)D0, (cid:101)D1) over Rd such that:

√

• Almost all the mass of (cid:101)D0 and (cid:101)D1 is supported in an (cid:96)2-ball of radius O(

• The distributions (cid:101)D0 and (cid:101)D1 admits a (Ω((cid:112)1/γ), 2−dΩ(γ))-robust classifier; moreover, a

Ω((cid:112)1/γ), 0.01)-robust classifier can be learned from O(d) samples from D0 and D1;

d);

• For (cid:102)D0 and (cid:102)D1, there exists a linear (non-robust) classifier, which can be learned in polynomial

time;

• For every ε > ρ, in order to learn a (ε, 0.01)-robust classifier for (cid:101)D0 and (cid:101)D1, one needs at

least 2dΩ(1) statistical queries with accuracy as good as 2−dΩ(γ).

For instance, if γ is a small constant we get the existence of a C-robust classifier, where C is

a large constant. One could push C as high as Ω(log1/2−ε d) at a cost of the lower bound being

against SQ queries with somewhat worse accuracy (2−2logΩ(ε) d instead of 2−dΩ(1)).

We first show a family of pairs (D0, D1) that admit a robust classifier, yet it is hard (in the SQ

model) to learn any (non-robust) classifier. Later, in Section 4.3, we show a simple modification of

this family to obtain the main result.

7

Figure 1: The distributions in Lemma 4.2 are similar to discretized Gaussians, with careful dis-

cretization and weighting from Gauss-Hermite quadrature.

4.1 Hard family of distributions

Here we define a hard family of pairs of distributions (D0, D1) as discussed above. This section

contains the definition and key properties of the family; proofs of those properties appear in Ap-

pendix A. This family can be seen to be a high-dimensional generalization and modification of a

family considered in [4]. The family depends on three parameters: integers 1 ≤ k ≤ d, m ≥ 1 and

a positive real ε > 0.

Fix an integer m ≥ 1. We introduce two auxiliary distributions over R that we will use later as

building blocks.

Lemma 4.2. There exist two distributions DA and DB over R with everywhere positive p.d.f.’s

A(t) and B(t) respectively such that:

• DA and DB match N (0, 1) in the first m moments;

• There exist two subsets SA, SB ⊂ R such that the distance between SA and SB is at least

Ω(1/

m), Px∼DA[x ∈ SA] ≥ 1 − e−Ω(m), and Px∼DB [x ∈ SB] ≥ 1 − e−Ω(m);

√

• A, B ∈ C∞, and for every 0 ≤ l ≤ m + 1 and t, one has: | dl

dtl

(See Figure 1 for the illustration.)

A(t)

G(t) |, | dl

dtl

B(t)

G(t) | ≤ mO(l+1).

Next let us fix parameters 1 ≤ k ≤ d and ε > 0. Let U = {Ui} be a family of k-dimensional

subspaces of Rd with fixed orthonormal bases such that for every i (cid:54)= j and u ∈ Ui, one has:

(cid:107)projUj u(cid:107)2 ≤ ε · (cid:107)u(cid:107)2. Informally speaking, subspaces from U are pairwise near-orthogonal.

Lemma 4.3. For every k ≤ dΩ(1), there exists such a family U with ε ≤ d−0.49 and |U| = 2dΘ(1).

Now we are ready to define our family of hard pairs (D0, D1) of distributions over Rd. The

family is parameterized by a k-dimensional subspace U ∈ U together with an orthonormal basis

u1, u2, . . . , uk ∈ U , where U is the family of subspaces guaranteed by Lemma 4.3. Let us extend

the above basis to a basis for the whole Rd: u1, u2, . . . , ud. Now we define a pair of distributions

8

6420246Well-separated distributions matching on 19 momentsABN(0,1) rescaledDU,A and DU,B via their p.d.f.’s AU (x) and BU (x) respectively as follows:

AU (x) =

k

(cid:89)

i=1

A((cid:104)x, ui(cid:105)) ·

d

(cid:89)

i=k+1

G((cid:104)x, ui(cid:105))

and

BU (x) =

k

(cid:89)

i=1

B((cid:104)x, ui(cid:105)) ·

d

(cid:89)

i=k+1

G((cid:104)x, ui(cid:105)),

where A(·) and B(·) are densities of distributions DA and DB from Lemma 4.2, and G(t) =

· e−t2/2 is the p.d.f. of the standard Gaussian distribution N (0, 1). Now we simply take D0 to

1√

be DU,A and D1 to be DU,B.

2π

Lemma 4.4. There exist two sets SU,A, SU,B ⊂ Rd such that the distance between SU,A and SU,B is

Ω((cid:112)k/m), and for which Px∼DU,A[x ∈ SU,A] ≥ 1 − e−Ω(km) and Px∼DU,B [x ∈ SU,B] ≥ 1 − e−Ω(km).

As a result, the pair (D0, D1) admits a (Ω((cid:112)k/m), e−kmΩ(1))-robust classifier. Moreover, since

log |U| ≤ O(d) (which follows from standard bounds on the number of pairwise near-orthogonal unit

vectors in Rd), it follows from Theorem 3.1 that one can learn a (Ω((cid:112)k/m), 0.01)-robust classifier

from merely O(d) samples.

4.2 SQ lower bound for learning a classifier for DU,A and DU,B

The heart of the matter is to show that it requires 2dΩ(1) statistical queries with precision τ = 2−dΘ(γ)

to learn a classifier for DU,A and DU,B provided that all the parameters m, k, ε are set correctly.

The argument is fairly involved and uses the framework of [8] to reduce the question to that of

upper bounding χ-correlation between the distributions. Due to space limitations, we show the

argument in Appendix B of the supplementary material.

4.3 Making the distribution easy to learn non-robustly

Let us now show a family of pairs distributions ( (cid:101)D0, (cid:101)D1) over Rd+1 such that it is easy to learn a

(non-robust) classifier, but hard to learn a robust one. The construction is very simple: we take

distributions (D0, D1) over Rd as defined above and define x ∼ (cid:101)D0 to be x = (0, y1, y2, . . . , yd),

where y ∼ D0, and, similarly, x ∼ (cid:101)D1 to be x = (ρ, y1, y2, . . . , yd), where y ∼ D1 and ρ > 0. These

distributions admit a trivial (non-robust) classifier based on the first coordinate. Moreover, since

(cid:101)D0 and (cid:101)D1 are linearly separable, they can be classified using linear SVM or logistic regression.

Information-theoretically, one can learn a ((cid:112)1/γ, 0.1)-robust classifier using O(d) samples by ig-

noring the first coordinate and applying Theorem 3.1. However, for every ε > ρ, one needs 2dΩ(1)

SQ queries with accuracy 2−dΘ(γ) to learn an (ε, 0.1)-robust separator. This can be shown exactly

the same way as for D0 and D1 (see Appendix B in the supplementary material).

The above distributions are hard to learn robustly with respect to the (cid:96)2 norm. We can switch to

d = (cid:107)x−y(cid:107)2,

d log d).

(cid:96)∞ by replacing x by its Hadamard transform Hx. Since (cid:107)Hx−Hy(cid:107)∞ ≥ (cid:107)H(x−y)(cid:107)2/

the robustness parameters in the theorem are unchanged while the diameter becomes O(

√

√

5 Conclusion and future directions

In this paper we put forward the thesis that adversarial examples might be an unavoidable con-

sequence of computational constraints for learning algorithms. Our main piece of evidence is a

classification task, for which there essentially exists a classifier robust to Euclidean perturbations

of size log1/2−ε d (while with high probability any sample has norm O(

d)), yet finding any non-

trivial robust classifier (even for arbitrarily small perturbations, and with probability of correctness

√

9

only slightly better than chance) is hard in the statistical query model (in the sense that one needs

an exponential number of queries, even with a very high precision statistical query oracle). We

identify several directions in which this result could be strengthened to give stronger evidence for

our thesis.

1. The most important question for the validity of our thesis is whether one could prove a similar

hardness result for natural distributions. This is a particularly challenging open problem as

the concept of a natural distribution is fuzzy (for instance there is no consensus on what a

natural distribution for images should look like).

2. We believe that our proposed classification task is really computationally hard in any sense,

not only in the statistical query model. As we discussed SQ is natural for learning theory

hardness, but there have been lots of works leveraging other types of hardness assumption

(e.g., cryptographic). It would be interesting to explore further the position of robust learning

in the hardness landscape.

3. Finally one might wonder whether the perturbation size log1/2−ε d is optimal (for distributions

essentially supported in a ball of size

d). A concrete open question could be phrased as

follows: consider a classification task that is (Ψ(d), 0)-robustly feasible, how fast does Ψ need

to grow in order to ensure that one can find in polynomial time a (1, 1/3)-robust classifier?

√

10

References

[1] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense

of security: Circumventing defenses to adversarial examples. In Proceedings of the 35th Inter-

national Conference on Machine Learning, ICML ’18, 2018. URL https://arxiv.org/abs/

1802.00420.

[2] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven

Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis.

In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC

’94, pages 253–262. ACM, 1994.

[3] Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial clas-

sification. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge

Discovery and Data Mining, KDD ’04, pages 99–108. ACM, 2004.

[4] Ilias Diakonikolas, Daniel Kane, and Alistair Stewart. Statistical query lower bounds for

robust estimation of high-dimensional gaussians and gaussian mixtures. In Proceedings of the

fifty-eighth Annual Symposium on Foundations of Computer Science, FOCS ’17, 2017. URL

https://arxiv.org/pdf/1611.03473.pdf.

[5] Gamaleldin F Elsayed, Shreya Shankar, Brian Cheung, Nicolas Papernot, Alex Kurakin, Ian

Goodfellow, and Jascha Sohl-Dickstein. Adversarial examples that fool both human and com-

puter vision. arXiv preprint arXiv:1802.08195, 2018.

[6] Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier,

2018. URL https://arxiv.org/pdf/arXiv:1802.08686.pdf.

[7] Vitaly Feldman. A general characterization of the statistical query complexity. Proceedings of

Machine Learning Research vol, 65:1–46, 2017.

[8] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. Statistical

algorithms and a lower bound for detecting planted cliques. In Proceedings of the forty-fifth

annual ACM symposium on Theory of computing, STOC ’13, pages 655–664. ACM, 2013.

[9] Amparo Gil, Javier Segura, and Nico M Temme. Asymptotic approximations to the nodes and

weights of gauss–hermite and gauss–laguerre quadratures. Studies in Applied Mathematics,

140(3):298–332, 2018.

[10] Justin Gilmer, Luke Metz, Fartash Faghri, Sam Schoenholz, Maithra Raghu, Martin Wat-

tenberg, and Ian Goodfellow. Adversarial spheres. In International Conference on Learning

Representations Workshop, 2018. URL https://arxiv.org/pdf/1801.02774.pdf.

[11] Amir Globerson and Sam Roweis. Nightmare at test time: Robust learning by feature deletion.

In Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, pages

353–360. ACM, 2006.

[12] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM

(JACM), 45(6):983–1006, 1998.

[13] Adam R. Klivans and Alexander A. Sherstov. Unconditional lower bounds for learning inter-

sections of halfspaces. Machine Learning, 69(2):97–114, 2007.

11

[14] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.

Towards deep learning models resistant to adversarial attacks. In International Conference on

Learning Representations, 2018. URL https://arxiv.org/pdf/1706.06083.pdf.

[15] Y. Nesterov. Introductory lectures on convex optimization: A basic course. Kluwer Academic

Publishers, 2004.

[16] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.

Adversarially robust generalization requires more data, 2018. URL https://arxiv.org/pdf/

arXiv:1804.11285.pdf.

[17] Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural

networks. In Advances in Neural Information Processing Systems, pages 5520–5528, 2017.

[18] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good-

fellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference

on Learning Representations, 2013. URL https://arxiv.org/pdf/1312.6199.pdf.

[19] Gabor Szego. Orthogonal polynomials, volume 23. American Mathematical Soc., 1939.

[20] Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest

neighbors to adversarial examples. arXiv preprint arXiv:1706.03922, 2017.

12

A Proofs of properties of the SQ hard distribution

We start with the following lemma on Hermite polynomials:

Lemma A.1. For every k > 1, the distance between any roots of Hk−1(t) and Hk(t) is at least

Ω(1/

k).

√

Proof. It is known that extrema of Hk are exactly zeros of Hk−1, which follows from H (cid:48)

and a lack of double roots. Thus, it is enough to show that extrema and zeros of Hk are Ω(1/

separated.

k = 2kHk−1

k)-

√

Consider the case where 0 ≤ u < v < w are such that Hk(u) = Hk(w) = 0, Hk is positive

between u and w, and H (cid:48)

k(v) = 0. Let us show how to lower bound v − u. Denote Fk(t) =

e−t2/2Hk(t). Clearly, Fk(u) = Fk(w) = 0 and Fk is positive between u and w with a unique local

maximum on [u, w], which we denote by v(cid:48).

It is not hard to check that v(cid:48) ≤ v. Thus, it is

enough to lower bound v(cid:48) − u. It is known (see, e.g., [19, Section 5.5] that Fk satisfies the ODE

Z(cid:48)(cid:48) + (2k + 1 − t2)Z = 0. By comparing with Z(cid:48)(cid:48) + (2k + 1)Z = 0, we can get that lower bound

v − u ≥ v(cid:48) − u ≥

= Ω(1/

k).

√

√

Now let us lower bound w − v. It is known [19, Section 5.5] that Hk satisfies the ODE Z(cid:48)(cid:48) −

2tZ(cid:48) + 2kZ = 0. By comparing this ODE with Z(cid:48)(cid:48) − 2wZ(cid:48) + 2kZ = 0, we get that w − v ≥

...