A single gradient step finds adversarial examples on random two-layers neural networks
Authors: Sebastien Bubeck
Yeshwanth Cherapanamjeri
Gauthier Gidel
Remi Tachet des Combes
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: adversarial examples
random neural networks
deep-learning theory

Abstract: Daniely and Schacham recently showed that gradient descent finds adversarial examples on random undercomplete two-layers ReLU neural networks. The term “undercomplete” refers to the fact that their proof only holds when the number of neurons is a vanishing fraction of the ambient dimension. We extend their result to the overcomplete case, where the number of neurons is larger than the dimension (yet also subexponential in the dimension). In fact we prove that a single step of gradient descent suffices. We also show this result for any subexponential width random neural network with smooth activation function.

A single gradient step finds adversarial examples on random two-layers neural networks
Sébastien Bubeck Microsoft Research
Yeshwanth Cherapanamjeri
Gauthier Gidel" Mila, Université de Montréal
UC Berkeley
Rémi Tachet des Combes Microsoft Research
Abstract
Daniely and Schacham [2020] recently showed that gradient descent finds adver- sarial examples random undercomplete two-layers ReLU neural networks. The term "undercomplete" refers to the fact that their proof only holds when the number of neurons is vanishing fraction of the ambient dimension. We extend their result to the overcomplete case, where the number of neurons is larger than the dimension (yet also subexponential in the dimension). gradient descent suffices. We also show this result for any subexponential width random neural network with smooth activation function.
fact prove that single step of
Introduction
We study the random two-layers neural network model, ʃ Rd defined by k
f(x)
(wp x),
(1)
where 1/ IR - fixed non-linearity, the weight vectors wy E Rd are i.i.d. from a Gaussian A/ (0, &la) (so they are roughly unit norm vectors), and the coefficients ag E Il are independent from the weight vectors and i.idd uniformly distributed in +-1,+1}. With this parametrization, the central limit theorem says that, for E vd. gd-1 (so that Wy x ~ (O, 1)) and large width k, the distribution f(x) is approximately a centered Gaussian with variance E (tt
Our goal is to study the concept of adversarial examples in this random model. We say that 5 Bd is an adversarial perturbation at z E Rd if ||ō]| < ||>||| and sign (f()) ) & sign(f(a + 5)). In this case, we call 8 an adversarial example. Our main result is that, while [f(x)) (11) with high probability, single gradient step on (i.e., perturbation of the form ó = fz)) for some E R) suffices find such adversarial examples, with roughly [|o|| |zl 1. Note, here that gradients are taken with respect to the input to the network as opposed to the weights the network. We prove this statement for networks of subexponential width (c.g.. A < exp(o(d))) with both smooth and ReLU activation functions. theorem.
Va
first state our result for smooth activation functions in the following
Theorem 1. Let E (0, 1) and vi be non-constant, Lipschitz and with Lipschitz derivative. There exists constants C₁ Cz Cz Ca depending on vi such that the following holds true. Assume k 2
"Canada CIFAR Al Chair
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

vlog(1/7)
Ci logo" and d 2 C2 (2)og(k/>) log(1/7), and let nJ I. such that |n] = C3 [()ل) and
sign(n) sign( Then, with probability at least " one has:
si)n(f(x)) + si + fVx))))
Moreover have [ S Coy/oo(11/)
Note that our proof of Theorem in Section 2 easily gives explicit values for C1, C2 Cs, Ca- Also note that by re-arranging the constraint d in Theorem 1 and setting 7 1/poly(d), the subexponential width condition is of the form & & exp(old)).
Our second main result establishes similar behavior for the non-smooth ReLU activation unit.
Theorem 2. Let E (0. 1) and v(t) = max(0, t). There exist constants C1 C2, C3, Ca, C3 such that the following holds true. Assume
C2 log (d) log(1/1 s k; C2 (d) log(1/)) dd C3 Ozlog" log(1/7) S log(d)
and let 1j E R. such that (y/ CA /log(1/7) and sign(n) = sign(f(x)) Then, with probability at [
least 1 - 7/ one has:
sign(f()) (x)) + sign( VV()))
Moreover, we have [n)]( S Csy/log(1/7).
As before, note that the subexponential condition on the width in the above Theorem is of the form I < cx2()).24) In fact by modifying a bit the proof we can get condition of the form < cxp(d") for any o < 1/2, but for the sake of clarity we only prove the weaker version stated above. The proof for the ReLU activation is broken into two separate cases focusing on the overlapping regimes:
Case 1: k 2 d d and Case log (d) 1og(1/7) S & S d
as the proofs for the two settings use distinct arguments. The proof for the first regime is similar to the proof for Theorem while the second uses a refinement of an argument by Daniely and Schacham [2020]. These arguments corresponding proofs are extendible to the setting where ag are drawn from a normal distribution with minor modifications. We include the simpler setting with Bernoulli activations in the last layer for the sake of conceptual clarity. Intuitively, the strong concentration (and nati-concentration properties of the normal distribution coupled with a conditioning argument the magnitudes of the weights in the final layer yield similar results for gaussian setting as well. Additionally, due to the scale invariance of the ReLU activation function, our results also hold true for any distribution over long as
carried out in Section 3. We would like to note that results and
P (x 0} = 0 and for smooth activations when TP |||||| = @(va) = 1. Finally, our results also hold when a bias unit is introduced: in this setting, we simply project our perturbation å onto the ((d - -iddmennioo subspace of perturbations which leave the bias unit unchanged.
1.1 Related works
The existence of adversarial examples in neural network architectures was first evidenced in the seminal paper of Szegedy et al. [2014], where the authors found adversarial examples by using I.-BFGS optimization procedure. Shortly after this work, was hypothesized in Goodfellow et al. [2015] that the existence of adversarial examples stems from excessive "linearity" of neural network models. This hypothesis was experimentally confirmed by showing that a single step of gradient descent suffices to find adversarial perturbations (the so-called fast gradient sign method -FGSM). Our theorems can be thought of as a theoretical confirmation of the hypothesis Goodfellow et al. [2015]. In fact, as explained in Section 1.2, our proofs proceed exactly by showing that "most" two-layers neural networks behave "mostly" linearly over "vast" regions of input space.
We note that not all networks are susceptible to one-step gradient attacks to find adversarial examples. Indeed, Goodfellow et [2015], it was shown that adversarial training can be used to build networks that are somewhat robust to one-step gradient attacks. Interestingly, Madry et al. [2018] showed that such models remain susceptible multi-steps gradient attacks, and empirically demon- strated that better robustness can be achieved with adversarial training using multi-steps gradient

---

attacks. Understanding this phenomenon theoretically remains challenge, see for example Allen- Zhu and Li [2020] for a proposed approach, and Moosavi-Dezfooli et al. [2019]. Qin et al. [2019] for discussion/llgoritmiie consequences of the relation with the phenomenon of gradient obfuscation (Papernot et al. [2017], Athalye et al. (2018]).
Our work is direct follow-up of Daniely and Schacham [2020] (which itself follows Shamir et al. (2019]). Daniely and Schacham prove that multi-steps gradient descent finds adversarial examples for ReLU random networks of the form (I), as long as the number of neurons is much smaller than the dimension (i.e., (d)). They explicitly conjecture that this condition not necessary. and indeed we exponentially improve it in Theorem 2 (see below for a discussion of & exponential in the dimension). We note that Daniely and Schacham went beyond two-layers neural networks, and conjectured (and proved for shrinking layers) that gradient descent finds adversarial examples on random multi-layers neural networks. We give some experimental confirmation of this multi-layer conjecture in Section 4.
The ultra-wide case k = exp())(d) remains open. This exponential size case seems of a different nature than the polynomial size we tackle here, at least for the ReLU activation function. In particular, it is likely that the behavior with exponential width would be closely tied to the actual limit case k +00, where the random model (1) yields a Gaussian process. Namely, for k = to0, f is Gaussian process indexed by the sphere (say if we restrict to inputs I E Vd -d-53 gd-1), with For example if the activation function is Hermite polynomial of degree p. then f would be spherical p-spin glass model. This polynomial case is particularly well-understood, and in fact the landscape we describe below in Section 1.2 was already described in this case by Ben Arous et al. [2020] (in particular Corollary 59) indicating that adversarial examples would likely continue to persist in the ultra-wide setting. It would be interesting to see if the y-spin glass landscape literature can be extended to non-polynomia activation functions, and to a finite (but possibly exponential d) k. A step in this latter direction was recently taken in Eldan et al. [2021], where convergence rates to the Gaussian process limit where given both for polynomial activations and for the ReLU. Finally note that for smooth activation it might be that there is a more direct argument to remove the subexponential width condition in Theorem (in technical terms, the proof of Proposition could leverage better argument than our naive upper bound on Lip(
fz) ((, [ (X)]) and [[) = -I. (X))
Finally, we note that, in practice, it has been found that there exists "universal" adversarial perturba- tions that generalize across both inputs and neural networks, (losavi-Dezfood et al. [2017]. For the case of ReLU activation (Theorem 2), we could in fact prove our result by replacing the gradient step with a step in the direction Σi= agW,, which is indeed a direction independent of the input v, thus proving the existence of "universal" perturbations (generalizing across inputs) for model.
1.2 The landscape of random two-layers neural networks
For a smooth non-linearity vi, we have
&
f(x)
aewey' (we- r) and
v²f(x)
Σ
aewew? (we x)
Vi
VK
t=1
We already claimed in the introduction that, with high probability the value of f(x) was bounded:
Upper-Bounded Value: [)()]] = 0(1).
(2)
We alluded to the CLT for this claim, but also easy to guess it intuitively by noting that:
k
1
E[f(z) = E
Σ F-P=1
aaaerblue x)b(wee - x) = (xxx(o,))
K
as [[aaaar] = ={ The formal proof of (2) (and all other claims we make here) will eventually be simple application of the classical Bernstein concentration incquality. Similarly, it is easy to see that (noticing that E = ( [V/ (X)?). with high probability, the norm of the gradient of ((x:) bounded below (note that we can also show that it bounded above).
Lower Bower-Bounded Gradient
[+ = 2(1).
(3)
3

---

A slightly more difficult calculation, although classical too, is that
VV2 f(x))lop 000 ( (
Upper-Bounded Hessian
(4)
Vdl
Indeed one can simply note that, for any E S ( Σら ar(wz- ( x) is approximately distributed as a centered Gaussian with variance (through heuristic application of the asymptotic central limit theorem):
Ew,z N0.. vi
(z)2
so that with probability at least - y one can expect u T V2 f(x) to be of order V (lo(11/)) by taking union bound over a discretization of the sphere gd-1, one can show inequality (4). In fact, interestingly, one can even hope that (4) holds true for an entire ball around x: with appropriate smoothness over v (say C smoothness), this could be obtained by another union bound over second discretization of d-dimensional ball. In other words, we can expect with high probability:
d and thus
Vz E gd ||^||| (d), one has f Ō ( V
(5)
Equations (2), (3), and (5) paint a rather clear geometric picture. There are essentially two scales around a fixed x E Vd- The macroscopic scale, where one considers perturbation æ + with ||ō|| = (VV),, and the mesoscopic scale where ||]|| = o(vd) (we use this term because for the ReLU network there will also be microscopic scale, with ||o|| (()). At the macroscopic scale the landscape of f might be very complicated, but our crucial observation is that the picture at the mesoscopic scale is dramatically simpler. Namely, at the mesoscopic scale, the function is essentially linear, since one has (thanks to (3) and (5))
Approximate Linearity:
[V(() vf(z + 8)l1 = f())) 4A ||8|| =
o(Vd). =
(6)
Moreover, since the height of the function is most a constant (by (2)) and the norm of the gradient constant, it suffices to step at constant distance in the direction of the gradient (or negative gradient)
to change the sign f. Assuming without any loss of generality that fxx > O, we combine (2), (3), and (6) using a standard descent lemma (Lemma 3):
f(x f(x)) <
f(x)
V f(=))
-
sup [Vf(() Vf(x +0]1 (7)
MV Sn
b(1)by
2(1 by
by
o(1) (4)
<C - < (for C,/C2 <
where C1, C2 and C3 constants that do not depend k and d. In words: single step of gradient descent (or ascent) with a ((1) step-size suffices to find an adversarial example, and morcover the adversarial perturbation satisfies ||0|| = O(1) = ((1=l//VV)
1.3
Proof strategy
The starting point of the proof for both the smooth and ReLU case is show (2) and (3), which we essentially do below in Section 1.4. In the smooth case, one could then prove formally (4) and conclude as indicated in the last paragraph of Section 1.2. Of course, (4) is simply ill-defined for the ReLU case, so one has to take a different route. Instead, we propose to directly prove (6), that is we study the difference of gradients the mesoscopic scale. Using that ||A]| supuesa-1 h, thus need to control (for some o(Vd)):
&
sup SERR:
sup vE
Σ
arlwe - () (we- -x - www (x+
VI
(9)

---

We execute this strategy first for the smooth case in Section 2. We then prove the ReLU case in Section 3, where we face an extraneous difficulty since the gradient not Lipschitz very small scale, which introduces third scale (the microscopic scale) that has to be dealt with differently. Technically, this issue appears when we try to move from the discretization over e and 6 in (9) the whole space (a so-called e-net argument).
1.4 Scaling of value and gradient
Here we show how to prove (2) and (3) (in fact, for our purpose, we only need the one-sided inequality | [2))ll = (21)) under very mild conditions on 10 which will be satisfied for both ReL.U and smooth activations. We will repeatedly use Bernstein's 's inequality which we restate here for convenience (see e.g., Theorem 2.10 in Boucheron et al. [2013]):
Theorem (Bernstein's 's inequality). Let (Xe) be i..d centered random variables such that for all integers q 2 2, [ < - for fixed > O. Then, with probability at least 1 7;
Σ X / 20 log(1/1) + clog(1/7).
(10)
We will also repeatedly that Ex~~V [| - (q 1)!! I 2. as well as the following concentration of x² random variables (see e.g., (2.19) in Wainwright [2019]): let X1,..., y X be i.idd standard Gaussians, then with probability at least 1 one has:
Σ t=1
X
k < 44Kklog(2/)).
(1I)
We can now proceed to our various results.
Lemma 1 (Bounded Value). Assume that there exists C. >> O such that for all integers 2 2,
< 2o²c0-2 [x-xx]..)]l+((]]]]]
2hen Then with probability at least - q one has
[f(x)] S 20 log(l/7) + clog(1/7)
Vk
Proof sketch. Since 1
Vk Ek_ arb(w: I), we use Bernstein's inequality on X₂ arb(wz ..)...).... x).
Lemma (Lower-Bounded Gradient). Let vp be differentiable almost everywhere, and assume that there exists ,','' ,,'' > O such that for all integers q 2 2, (x. S 29922 Then with probability at least 1
[Vf(2)]1 (x= (v 20 2002lo((/>)) log(2/7)
d' <log(2/7))
))
log(4/>)
1 (1-5/ 5/
+
d
Proof sketch. Let P We have [=)()) 2 fIPV + Ei Paewey' (we =)] where a, Pww is independent of we and is distributed as / (0. 1o1))). We conclude by conditioning the values (we x))c(M] and using the concentration results (10) and (11).
zx' be the projection on the orthogonal complement of the span of x.
d
2 Smooth Non-Linearity (Theorem 1)
In this section, we consider a 1-Lipschitz and L-smooth activation function, that for 8, / E R, (s) ((t) < and (v'(s) v'(1) s Lis - t/.
(12)
We also assume (0) 0 and denote og E Ex~N (()))(((()))))) which we assume to be non-zero (that is zb is not constant function).
5

---

Proposition 1 (Upper-Bound) Bounded Value and one has with probability at least
Gradient). Under the above assumptions,
7
2 log
[f(x)] & V 2og
+
1/2
2 log
1
log
log
5 7
and |[/(()] 2 E
1- 5
Particularly, there exists C > 0 such that for k 2 C' Cloog(2/)) and d 2 C' C'log(8/7) we have
If(x)) - 2//og(1/>)
and
[V(()] 2 c²/2.
(13)
Proof. With (12) we have (x)] - [X| and thus in Lemma we can take o = c which yields the first claimed equation. For the second equation use that [x)( < 1 (since &b is 1-Lipschitz) and thus, in Lemma 2, we can also take = d' = yielding the second claimed equation.
Next, we need to control (9) where we use erucially the smoothness of the activation function. Proposition 2 (Bounded Variations).
Let R 2 With probability least - - one has
[V(()) V/(x + +) s 20RL (V
log(Rk/n)
log(1/7)
sup BERT: |
Vh:
Particularly, for any > there exists C1 C2 such that if 2 CgR9tog and d z C²R² Rog( Rk/h)) then
sup [Vf(z) v f(z + 8)11 sc.
(14)
SER:: |
Proof sketch. Our plan is to use the fact that |h|]| = supweg" v h. Thus, we first show, by using Bernstein's 's inequality on X, = % (w, ()(//(w, .²) - v (w; (x + 5)), that if we fix 5 E Idd such that || < R and gd-1, then with probability at least 1 y one has:
L
Xi < 4RL d Vlog(1/7)
log(1/7)
(0 (z) Vf(x +((++0),,)
(1
[2 (v. : ||a||| 1, || S R) and N be an e-net over Ω with 1/k. By union bound N₂ (whose size is most R10kR)2d [Vershynin, 2018, Corollary 4.2.13]), obtain with probability at least 1 7:
sup (v, < sup (u,d)en
0(v,0)+ +
sup (v.8). ('))) w0 16-8
$ 5) (
(v,5)EN,
4RL
2d log Rk)) + log(1/7)
Lip(0)
< d
V (dlog((k) + lo/()
1+
k
Then show that the variations of & be upper-bounded by RL times x2 random variable and use (11) to show that with probability at least - 7,
log 1og(1/7)
Lip($)= < RL Vkk+4 4
Finally can turn the proof of Theorem 1. Let us first recall this theorem.

---

Theorem 1. Let y E (0, and & be non-constant, Lipschitz and with Lipschtiz derivative. There exists constants C₁ C2 C3. Cs depending on such that the following holds true. As- sume k 2 C (L/7)l (1/7) and d Z C2 (oog((//))log1////1) and let d E R such that [m] and sig)(n) -fign((())) Then with probability at least 1 7 one
(sy/log(1/>)llVf
hus:
sign([(>:) + sign (f vV(())))
Moreover we have [,)](())] & (lg(1))
Proof. We make the following claims which hold with probability at least 7. Without any loss of generality we can assume that (x) > O, we will use a standard descent lemma (Lemma 3) and the previous propositions get that,
((=-)V\(z>) <
((x)
|
sup 161
V +611). (15)
Sn
O(1) (13)
200 (13)
2(1) by (13)
o(1) by (14)
Formally, let us set V V log(1 1/2), R 1og(1/7), 2 C1 R2 log log (1/7) and d 2
32
R2R log( (Rk/7) where C1 and C2 are large enough such that (13) and (14) are valid with c c By Proposition we have that [x)]l 2 c2/2 and n) //)f((=)l _/ /lo((1/>)
4.
2 d de f(x)..
Moreover, Proposition 2 shows that for all 5 such that |o|| S [n]]V s f 11/(1//)= R, we thus have [v) - fx 5)ll S c 4 Consequently,
f(x - fz)) S f(x) -nnnnl/V// [[(iil (2) - (v) S f(x) n 2 +4)=
-
(16)
4
8
Thus, with single gradient step of size at most R = 64 /lo((111) switched the sign of f.
3 ReLU Non-Linearity (Theorem 2)
In this section, we consider the ReLU non-linearity (t) = max(0, t). We start by showing that (x) is upper bounded and that |/V f (x)]] || is lower-bounded.
Proposition 3 Bounded Value and Lower-Bouee Bounded Gradient). With probability at least 1 1-77
log(2/7)
1f(x) S (2log(2/7)
1+
1
2log(4/7)
(1+)
log(1/7)
) 1/2
(1
1-55
log(4/7)
and [Vf(()]]
2
k
k
d
Particularly, there exists C > O such that for l 2 C'log(1/7) and d 2 C'log(4/7) we have
If(z)) < 2 log(2/>) and [[Vf()) 2 4
(17)
Proof. In Lemma and Lemma 2, we can take c o' d' = 1 (since [x(X) |X| and (x)) < 1), which concludes the proof.
Now we split the control of the gradient variation into two cases: the large width case (Cd d d$ k) and the small width case (log" (d) log(1/7) S k S log" d).
Proposition 4. (Bounded Variations Large Width Case) Let S R Vd/2, > log(1/7). Then, with probability least 7, one has
vk 2 52 and
1/4
log d d
d
sup SER4: |
[V[(z) - v5(x + +J1l 20 Blogg((kk))
+ 400
T
log Itk)
7

---

Particularly, for any > 0, there exists C1. C2 such that Cl (Rk) S k and C2 (Rk) then we have, log(d)
(Rk)
d
sup 8ER*: ||
[V)(2) (x(x+ c.
(18)
Proof sketch. In the smooth case (Proposition 2) we did so by using crucially the smoothness of the activation function. Here, instead of smoothness, we will use that only few activations can change when you make microscopic move (i.c., between æ + 8 and x + d' with || - 8'1l = o(1)) The key observation that for any such that ||o|| R.
log(d) d
P(sign we x) + sign( (e (x + 5))) - RV
(19)
We can then use this result to bound the variation of V f(r) along fixed direction. If we fix d E R
such that |||| v R (with R 2 1) and v E E8-11, then with probability at least 7 one has:
5), ( ((c, (( = (Vf<))>>>>>>>>>>>)))> f( +
1 1 = Vk
log(t)
(2R
log(d)
+ log(
This inequality is proven via Bernstein's 's inequality on X == ar(wo (/ - -) (wo (x+ +))) where we use (19) to prove
| S v E we 1 2224] x P(sign(ws x) # sign(wr (x + 8))) S g! a- 0², (20)
2
1/4
with Va 22 log(d)
and c Vd
Then, similarly as in the proof of Proposition 2, we use a covering argument (but this time with an
8-Net of size = R-- 12-1/33-1 to show that,
sup (cc < sup (v
2 5) +
sup (v.8).(".8)))0)) 11- 88188-8--
((v, 8) ( (')
(v,
1/4
10dlog Rkk) + 1og(2/7) d
log(d) |
10d (Rk) + log (2/7)
s 2
d
sup (v.8).(mt (1 11-
(uu, 6) { 88)1_
(21)
By using x concentration, it is easy to see that with probability at least 1 - y:
(log(k/>>)
(5, r) (6, v')l s ||u [|ll-/lll o'lly k 4/0V
(22)
d
By using (19) are able show that with probability 1 5 for any (v, 5) N₂ there is most 4d different activated neurons between (vv, d) and ((v, and thus by applying a concentration result of Lipschitz function of Gaussians get,
log 4k + 8/7 (66 -80' & 18
d
(23)
d
Combining (21), (22), and (23), we get
log 1/4
+ 40 d log Rk).
sup SERd: |
[v)(2)
fz(z + 5)1l < 20
Rlog (Rk)
d
k
Proposition 5 (Bounded Variations Small Width Case). Let 20 log d log 1/7 k < dlog d and d > 20 log d log 1/7. Then, with probability at least 1 7, we have;
60
sup
[V[(x) V 8)11 <
log d
8ER*, [ log
8

---

Proof sketch. In the small width regime we assume 20 log d log 1/8 S k S dlog' d. The idea of the proof is to control the operator norm of W (where f(x Vk w(WTx)) x)) as well as the number of neurons with too small activation. With high probability, we show that we have,
1+ 10(k log 1/8)
{
k
|| 3
i: (i:
d
log d
log d sgnnngg (w;, x) + sgn(ws, y)} is
Thus, uniformly on { | vll S uppper-hounded:
} the cardinal of T. = {i sgn log d
vE
TTl S 300k/ log" d= B.
(24)
We can conclude the proof by using an union bound and a concentration inequality on Gaussians.
[V =
1
Σ
S
sup AC
1
Σ
arwe
S
B V
1
log & + log d
Vk
d
CET
IET
J
We now prove our final result.
Theorem 2. Let y E (0. 1) and (t) max(0.t). t). There exist constants C1, C2, C3, C4, Ci such that the following holds true. Assume
d
Ci log (d) log(1/7) k,
C2 C2log log(1/)) s d, C3 Czlog (k) log(1/7) < log(d)
/lo(11/))
and let 17 E R such that |n|
C1
and sign(n) sign(f(x)). Then with probability at [f]())
least 1 - 7y one has:
sign(f(z)) + sign(f(= +
Moreover we have [[)]l < Cs Covlog(1/h))
Proof. The proof is the same as for Theorem 1 using Proposition 3 instead of Proposition 1 and Proposition 4 or Proposition replacing Proposition
4 Experiments
Setting. To verify our theoretical findings, we run some experiments to measure empirically the probability of finding adversarial example in the direction ff(x). More precisely, take random point x of norm vd and initialize network using the procedure described in Section 12, We then find the smallest such that a gradient step v/V / (xx) changes the sign of the function. 7) is of the opposite sign of (xx) and we limit k. as well as deeper networks with L = 1 through L = 6 hidden layers. All hidden layers are of width k. For our experiments, we used ReLU activation units and the standard deviations reported in Figure are computed over 100 random network initializations for each choice of architecture and 100 random input points for each such initialization.
search to |n] < 20. We explore various values of d and
Figure 2a shows the average of the smallest 7 required to switch the sign the function. We note that the average only includes cases where an r indeed found. Figure 2b shows the gradient norm in æ (all cases included). As we see, both the smallest and the gradient norm approximately constant both in d and in k. This finding also holds for deeper networks (see Appendix D). In Figure 1, we show the fraction of examples (out 10, 000 samples) whose sign is switched. We see that with L switched. This confirms our theoretical results. Once again, we observe the same statement holds for deeper networks. The values of d and l: at which 100% switching is reached appears to grow with L3. Additionally, we track the value of the smallest required to switch the sign of the function, and the gradient norm w.r.t æ. Both are approximately constant in d and in k. This finding also holds for deeper networks (see Appendix D for the curves).
Results.
and values of d and larger than 50, 100% of samples
We also conducted experiments with a gaussian initialization for the last layer place of Bernoulli initialization from Section and obtained qualitatively similar results.
Due GPU memory limitations, l could not reach 1,000,000 for deeper networks.

---

exmmete
Freetton of switched Fracttin swichee exemlles
Number of hidten neurons
Number of Nideen neurons
Number Nidden neurons
L
L=5
Frectton swieched
Figure 1: Fraction of inputs with an adversarial example found after a single gradient step, for various input dimensions d, hidden layer widths & and number of hidden layers L. For each pair (k, L). report the average 100 network initializations and 100 values of per initialization. The colored represents standard deviation.
Acknowledgment
We thank Mark Sellke for pointing us the reference Ben Arous et al. [2020], and Peter Bartlett for several discussions on this problem.
5 Disclosure of Funding and Competing Interests
GG research supported by the Canada CIFAR Al Chair Program and an IVADO grant. YC gratefully acknowledges the support of the NSF through grants the Simons Foundation through award #8 #814639, and Microsoft through the BAIR Open Research Commons. We declare competing interests.
and DMS-2031888
References
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005. 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses adversarial examples. In International Conference on Machine Learning, 2018.
Gérard Ben Arous, Eliran Subag, and Ofer Zeitouni. Geometry and temperature chaos in mixed spherical spin glasses at low temperature: the perturbative regime. Communications on Pure and Applied Mathematics, 2020.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Amit Daniely and Hadas Schacham. Most ReLU networks suffer from & adversarial perturbations. In Advances in Neural Information Processing Systems, 2020.
Ronen Eldan, Dan Mikulincer, and Tselil Schramm. Non-asymptotic approximations of neural networks by gaussian processes. arXiv preprint arXiv:2102.08666 2021.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference Learning Representations, 2015.
10

---

Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE conference computer vision and pattern recognition, 2017.
Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- ness via curvature regularization, and vice versa. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference computer and communications security, 2017.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhussein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. In Advances in Neural Information Processing Systems, 2019.
Adi Shamir, Itay Safran, Eyal Ronen, and Orr Dunkelman. A simple explanation for the existence of adversarial examples with small hamming distance. arXiv preprint urXiv:I900 10861, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representutions, 2014.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing: Theory and Practice. Cambridge University Prteess, 2012.
Roman Vershynin. High-dimensional probability. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018.
Martin J Wainwright. High-dimensional statisties; A non-asymptotic viewpoint. Cambridge University
Press, 2019.


Reviews:
[{"review_id": "r5JNwbwhhc", "reviewer": "Reviewer_aYEM", "summary": "The authors prove that two-layer neural networks can be perturbed adversarially at a fixed data point and at random initialization (with high probability), i.e.\\ for a neural network $f$ with randomly initialized parameters and a data point $x$, there exists a small perturbation $\\delta = O(1)$ such that $|f(x)| = \\Omega(1)$, but $f(x+\\delta)\\cdot f(x) < 0$. The result holds for a wide range of widths and activation functions. They present numerical evidence for their theoretical claims.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results seem to be generally correct and are backed up by proofs and simulations. Personally, I find the observation that untrained shallow neural networks which are initialized randomly can easily be perturbed adversarially by a white box attack not that interesting. However, I believe that the results presented here are a significant improvement on e.g.\\ Daniely and Schacham (2020), which was selected for NeurIPS 2020. Following precedent, I lean towards accepting the present work.\n\n{\\bf General comments:}\n\n* The authors consider data $x$ in the sphere $\\sqrt d \\cdot S^{d-1}$, but construct adversarial examples in the ambient space $\\R^d$. Is it possible to adapt the mechanics to adversarial examples on the data manifold? This could strengthen the authors' statement, but I am concerned that the hairy ball theorem may necessitate radial perturbations in high dimension. Can this be avoided (with high probability)?\n\n* As is convention, the authors absorbed the bias $b$ in $\\sigma(w\\cdot x+b)$ into the weight vector $w$ by implicitly replacing a data point $x$ with a data point $(x,1)$. As they modify $x$ in the direction of the negative gradient, there is no reason for the last coordinate to be fixed, effectively changing the weights of the neural network rather than the data points. Could the authors address this discrepancy (either by more clearly stating the limitations of their result or by outlining a strategy to avoid this conflict). I believe that this could easily be avoided, for example by stepping in the direction of the partial gradient which does not take the last dimension into account. \n\n* The authors name random variables $X, Y$ in the situation that $x$ is only used as a projection and the randomness stems from $w$ or $a$. I find this naming convention confusing and poorly chosen.\n\n* The proofs are written with little detail, so that the reader has to reconstruct the argument. This makes a timely review different in a time-frame as short as NeurIPS, as it takes additional time to assess whether the details are correect. I would ask the authors to see if they can flesh out the details of the proofs in the appendix a little more.\n\n\n{\\bf Specific comments:}\n\n* l 18: $|f(x)| \\approx 1$ signals that $|f(x)| = 1 + o(1)$. I believe the authors mean that $|f(x)| \\geq c>0$ for a constant which depends on $\\psi$. Maybe $|f(x)| = \\Omega(1)$ would be more appropriate.\n* l 24: Typo 'Lipschtiz'\n* l 37: Could the authors briefly explain the constraint $k\\ll \\exp(d^{0.24})$ and comment on the constant $0.24$? I do not follow exactly.\n* l 67: The authors claim above that their main results hold for $\\exp(d^\\rho)$ with $\\rho<1$, which is not the same as $\\exp(o(d))$ (compare e.g.\\ $\\exp(d/\\log d)$. A qualifier like 'almost', 'roughly' or 'essentially' might be appropriate. In the introduction (l 22) the same could be claimed, although there I do not see quite as large a problem.\n* l 77: Does a continuous Gaussian process of this form admit adversarial examples?\n* l 103: What does the term 'approximately distributed like' mean? Please be more precise.\n* l 103: If $X, Y\\sim N(0,1)$, then $\\E[XY] \\leq \\sqrt{\\E [X^2]\\,\\E[Y^2]} = 1$, but $\\E[XY] = x\\cdot u$ can be as large as $\\Omega (\\sqrt d)$. Please correct. \n* l 103: The random variable $X$ is not related to the term in the previous line which contains the data point $x$ and induces the random variable $Y$. This notation is unfortunate and confusing. \n* l 107: I assume that this would be $C^{2,1}$-smoothness, but please be more specific. \n* eq (5): This claim is almost certainly wrong. It is much stronger than Lemma 5 in the appendix since an $\\eps$-covering of the sphere $\\sqrt d\\cdot S^{d-1}$ requires $\\sim (\\eps^{-1} \\sqrt d)^d$ elements. If $\\|x\\|$ is allowed to be polynomial in $d$, I do not believe this could be recovered. Please check this claim and provide a proof or find a different heuristic.\n* l 116: A scalar-valued function which has constant height is automatically constant. Additionally, you are trying to argue that the function changes sign. This sentence is contradictory, and should be rewritten. \n* l 148: Delete comma.\n* l 163: Since the proof of Proposition 1 is given in the main text, it does not need to be listed in Appendix B.\n* l 171: Typo 'Berstein'\t\n* l 174: Where does the constant 10 come from? Also line 380.\n* l 178: If the authors need more space for explanation, I believe the repetition of Theorem 1 is not necessary.\n* l 248: The figures presented above suggest that $100,000$ was not reached, either.  \n* l 360: A few additional lines might make the proof easier to read (remark e.g.\\ that $\\delta$ is replaced by $\\delta/2$, be clear about which variables Bernstein's inequality is used on, etc.)\n* l 375: The Gaussians have variance $1/d$ and $\\|\\delta\\|/d$ respectively, so the two factors should not appear with the same homogeneity (I believe the correct scaling would be $\\|\\delta\\|^{q/2}$). Please double-check how this affects other results in the article.\n* l 380: 'a union bound' (since English is weird). This also is not a union bound, but a tail inequality.\n* eq (29): This looks vaguely correct, but I am slightly confused at the explicit expression for the first term. Could the authors explain more precisely which tail bound they are using? I would have expected $\\log(1/\\gamma)$ to be outside the square root in the first term.\n* l 390: Since this was proven in the main text, it does not have to be repeated here. \n* l 404: Please give more detail. Is there a factor 2 missing due to the absolute values?\n* l 408: How does (11) enter? Please give more details. \n* l 409: Typo 'crucial' \n* l 417, 418: It looks like text versions do not line up\n* l 420: The authors need to bound oscillations at an infinitesimal scale as well, but only {\\em in terms of $\\eps$}. This is different from estimating the Lipschitz-constant at scale $\\eps$, which sounds more like taking $\\sup_{\\|x-y\\|=\\eps}\\frac{\\Phi(x) - \\Phi(y)}{\\eps}$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ZibLvA78oE4", "reviewer": "Reviewer_ATH6", "summary": "The paper studies adversarial examples in random depth-2 ReLU networks.  They consider depth-2 networks, where the first layer is drawn from a normal distribution such that the norms of the weights vectors are roughly 1, and the second layer is drawn from the uniform distribution on {-1/\\sqrt{k},1/\\sqrt{k}} where k is the width of the network. They assume that k is at most sub-exponential in the input dimension, and is bounded below by some polylogarithmic expression. For an input x on the sphere of radius \\sqrt{d} the output of the network is w.h.p. O(1) (the input x is fixed, and the probability is over the choice of the network). The authors show that there is w.h.p. \\delta with ||\\delta||=O(1) such that sign(f(x)) \\neq sign(f(x+\\delta)). Moreover, such \\delta can be found with a single gradient step. Thus, although the inputs are of size \\sqrt{d}, there is w.h.p. a perturbation of size O(1) that changes the sign of the output. They prove the result for both smooth and ReLU activations.\nFinally, they validate the results empirically, and also demonstrate that ש similar phenomenon occurs in deeper networks.\n\nDaniely and Schacham [2020] showed that such a property holds in ReLU networks where the sizes d_1,…,d_t  of the layers (where d_1 is the input dimension) are such that for every j we have d_{j+1} = o(d_j) and d_t = \\omega(1). For the special case of depth-2 networks it required width k=o(d). Thus, the improvement here w.r.t. k is exponential.\n\nThe proofs roughly follow the following steps. First, they show an O(1) upper bound on f(x) and an \\Omega(1) lower bound on ||\\nabla f(x)||. Then, they bound the variation of the gradient near x. Finally, they use standard arguments to bound f(x-\\eta \\nabla f(x)) for an appropriate \\eta. The proofs of these steps for the case of the ReLU activation is different from the case of smooth activations, and the proofs for the ReLU activation with small k is different from the case of large k.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and the main ideas of the proofs are clearly explained in the first 9 pages. Since real-world trained networks are highly non-random, then I think that the nature of adversarial examples in random networks might be very different than in the case of trained networks. Still, I find the mathematical formulation of the problem on random networks natural, and I think that by understanding adversarial examples in random networks we may gain useful insights. Thus, the setting of random networks is a first step towards more realistic settings. The improvement w.r.t. the results of Daniely and Schacham is significant, since their assumption of k=o(d) is very strong.\n\nThe random networks in this paper are such that the second layer is drawn from the uniform distribution on {-1/\\sqrt{k},1/\\sqrt{k}}. This weights distribution is less standard. I think that a result for the case where all weights are drawn from a normal distribution would be interesting. Can your results be extended to this setting? Anyway, I think that a discussion on this issue is appropriate. Also, in Daniely and Schacham all weights are drawn from a normal distribution, and hence in this sense the results here are not strictly stronger even for depth-2 networks. \nI am also not sure what is the initialization scheme in the experiments on deep networks. I guess that all layers are drawn from a normal distribution, except maybe for the final layer. I think that a more detailed description on this setting is required.\n\nA minor comment: In the last equation in page 8, in the expression after the first inequality the sum should be over A.\n\nOverall, I think that the paper gives significant results on a natural problem, and I recommend acceptance.\n\n**post rebuttal update**\nThank you for your response. I maintain my recommendation for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "J_J0KFsXPIt", "reviewer": "Reviewer_ogDp", "summary": "The paper studies the phenomenon of adversarial examples for random two-layer networks with ReLU or smooth activations. It is shown that one step of gradient descent yields adversarial examples (i.e., a switching of the sign of the network output) with high probability, under a much milder condition on the number of neurons compared to previous work, i.e. sub-exponential in the dimension instead of sub-linear for Daniely and Schacham [2020].\nThe proof is based on characterizing the landscape of the network function at different scales, showing that at relatively small \"mesoscopic\" scale of perturbations (o(sqrt(d)),  but still O(1)), the gradient is close to constant while being Omega(1), making it easy to find an adversarial example with a single gradient step.\nSome experiments are provided to illustrate the theory, and to illustrate how the phenomenon extends to multiple layers.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main result appears to significantly improve our understanding of adversarial examples for networks at random initialization, which have been crucial objects in the understanding of deep learning in recent years. The improvement compared to Daniely and Schacham seems significant, the paper is well written and the results seem novel, thus I recommend acceptance.\n\nHere are a couple of minor comments:\n* would the results easily extend to Gaussian initialization of a_l instead of +/- 1, which is perhaps more standard in practice?\n* some comments on how these results could persist after initialization would be helpful (e.g. perhaps such lack of robustness could remain valid (only?) in the NTK regime?). Some experiments illustrating this on practical networks at various stages of training would also be welcome.\n\n\n\n===== post-rebuttal update ======\n\nThank you for your response! Please do include your comments on Gaussian weights in the final version of the paper. I maintain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "G_S4qgYOTqh", "reviewer": "Reviewer_2AAQ", "summary": "The authors consider the existence of adversarial examples in neural networks trained by gradient descent.  They demonstrate that for two layer networks, one gradient update following random initialization can find adversarial examples.  Their results extend previous work by Daniely and Schacham to more general settings (for two layer networks) and rely upon a different suite of techniques.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I quite like this paper.  They clearly explained the problem of interest, accurately described previous work and their limitations, and then proposed a solution to overcome the limitations of previous work.  The practice of finding adversarial examples using one-step attacks is common but had previously never been shown; this work thus provides a concrete theoretical explanation for this previously unexplained phenomenon.  I was unable to find any obvious drawbacks to the paper's results.\n\nThe exposition in the main section was particularly clear and nice to read.  In particular, the proof sketch was clear and intelligible, and the discussion in lines 72-87 about extensions to the width = exp(d) case was insightful.  \n\nThe experiments could use some more details. e.g., which activation function is used? For Fig. 1, are the colored areas representing standard deviations over random initializations (if so how many)? \n\nIt may be helpful to emphasize in the introduction that the gradient is with respect to x rather than w (although this is implicit given your notation). \n\nIs there any understanding of whether or not the results hold for more general distributions over x?  Some comments on this would be nice.\n\n\n** Post rebuttal updates **\nI've read the other reviewers' comments and the author response and am maintaining my strong recommendation for acceptance.  Thanks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers find the paper to be clearly written, with a clear exposition of the problem and offering a novel analysis with a significant degree of novelty. I strongly recommend acceptance.
Decision: Accept (Spotlight)