Adversarial Examples in Multi-Layer Random ReLU Networks
Authors: Peter Bartlett
Sebastien Bubeck
Yeshwanth Cherapanamjeri
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial examples
deep ReLU networks
theory

Abstract: We consider the phenomenon of adversarial examples in ReLU networks with independent Gaussian parameters.  For networks of constant depth and with a large range of widths (for instance, it suffices if the width of each layer is polynomial in that of any other layer), small perturbations of input vectors lead to large changes of outputs.  This generalizes results of Daniely and Schacham (2020) for networks of rapidly decreasing width and of Bubeck et al (2021) for two-layer networks. Our proof shows that adversarial examples arise in these networks because the functions they compute are \emph{locally} very similar to random linear functions. Bottleneck layers play a key role: the minimal width up to some point in the network determines scales and sensitivities of mappings computed up to that point.  The main result is for networks with constant depth, but we also show that some constraint on depth is necessary for a result of this kind, because there are suitably deep networks that, with constant probability, compute a function that is close to constant.

Adversarial Examples in Multi-Layer Random ReLU Networks
Peter L. Bartlett
Sébastien Bubeck
Department of Electrical Engineering and Computer Science
Microsoft Research Redmond
Department Statistics
UC Berkeley
Yeshwanth Cherapanamjeri
Department of Electrical Engineering and Computer Science UC Berkeley
Abstract
We consider the phenomenon of adversarial examples in ReLU networks with independent Gaussian parameters. For networks of constant depth and with a large range of widths (for instance, it suffices if the width of each layer is polynomial that of any other layer), small perturbations of input vectors lead to large changes of outputs. This generalizes results of Daniely and Schacham (2020) for networks of rapidly decreasing width and of Bubeck et al (2021) for two-layer networks. Our proof shows that adversarial examples arise these networks because the functions they compute are locally very similar to random linear functions. Bottleneck layers play key role: the minimal width up some point in the network determines scales and sensitivities of mappings computed up that point. The main result is for networks with constant depth, but we also show that some constraint on depth is necessary for result of this kind, because there are suitably deep networks that, with constant probability, compute a function that is close constant.
Introduction and Main Result
Since the phenomenon of adversarial examples was first observed in deep networks [SZS* 14], there has been considerable interest why this extreme sensitivity to small input perturbations arises in deep networks [GSS15, SSRD19, BLPR19, DS20, BCGdC21] and how it can be detected and avoided [CW17a, CW17b, FCSG17, MMS+ 18, QMG+19] Building on the work of Shamir et al [SSRD19], Daniely and Schacham [DS20] prove that small perturbations (measured in the Euclidean norm) can be found for any fixed input and most Gaussian parameters certain ReLU networks- those in which each layer has vanishing width relative to the previous layer- and con- jectured the same result without this strong constraint on the architecture. Bubeck, Cherapanamjeri, Gidel and Tachet des Combes [BCGdC21] prove that the same phenomenon occurs in general two-layer ReLU networks, and give experimental evidence of its presence in deeper ReLU networks.
In this paper, we prove that adversarial examples also arise in deep ReLU networks with random weights for wide variety of network architectures-thoss with constant depth and polynomially- related widths. The key fact underlying this phenomenon was already observed in [DS20]: high-dimensional linear function fx) ) = w with input * 0 and random parameter vector w with a uniformly chosen direction will satisfy [z) ||> > If(x) with high probability. This implies
35th Conference Neural Information Processing Systems (NeurIPS 2021).

---

the existence of a nearby adversarial example for this linear function: perturbation of z of size [+=))| < ||=]]| in the direction - Vx) (f)) will flip the sign of [(x). This observation
can be extended to nonlinear functions that are locally almost linear. Indeed, it is easy to show that for all x, u E Rdd
[f(z + +) (f(z) (u, vf())))] | sup f()) - vf(2 + +)ll v R., ||||| - |uul]
and thus to demonstrate the existence of an adversarial example near for function f, it suffices to show the smoothness property:
for all R² with ||a|| & ((=))//V(()
[Vf(2) vf(x+
[Vf(()]]
(1)
We show that for deep ReLU network with random parameters and high-dimensional input vector I, there is a relatively large ball around x where the function computed by the network is very likely to satisfy this smoothness property. Thus, adversarial examples arise in deep ReLU networks with random weights because the functions that they compute are very close to linear this sense.
It is important to notice that ReLU networks are not smooth in a classical sense, because the nondifferentiability of the ReLU nonlinearity implies that the gradient can change abruptly. But for the smoothness condition (I), suffices to have f(z) - Vf( + u)ll S E + o[[[=]), [), for some increasing function Ø R2+ > R.. provided that c ((le])) < [Vf(())]. We prove an inequality like this for ReLU networks, where the term decreases with width.
Consider a network with input dimension d, {+1 layers, single real output, and complete connections between layers. Let .i,...,dd de denote the dimensions of the layers. The network has independent random weight matrices W; Rd:x4d 1 for i [e + 1]. where we set dg d and de+1 For input x: E Rdd, the network output is defined as follows:
f(x) We+1 oWe oWW-11 a(. (W1 x) ..)))))) })) where a(x); max (z; 0}
We+1 ~ (O, 1/de) and Vi E [4], (W)),. idd 1/00,//d-11)
(NN-DEF)
Note that the scale of the parameters is chosen so that all the real-valued signals that appear throughout the network have roughly the same scale. This is only for convenience: because the ReLU is positively homogeneous (that is, for a > 0, a (az) = oz (x)), the scaling is not important for our results; the 1/d,-1 in (NN-DEF) could be replaced by any constant without affecting the ratio between the norm of an input vector and that of a perturbation required to change the sign of the corresponding output.
The following theorem is the main result of the paper.
Theorem 1.1. Fix & E N. There are constants C1, C22 03 that depend on E for which the following holds. Fix (0, 1) and let f()) be an (f+ 1)-layer ReLU neural network defined by (NN-DEF) with input dimension d and intermediate layers of width {d,), Suppose that the widths satisfy
dmin 2 ci (log dmax)* 2 ) log 1/6 where d.ni min (d. d} dmax max ([d))==1,
Then for any fixed input x + O, with probability at least - 5,
If(x + f(()) 2 (f()) and sign(f(x vV # f(x),
for n satisfying
log 1/8 [n)](>)]
S c3
|
d
It suffices to choose e1 = (Cif)²,, 02 C2l, -: Ct., for some absolute constants Cz C2, C3.
This theorem concerns networks of fixed depth, and the constants the size of the perturbation and in the requirement on the network width are larger for deeper networks. We also prove converse result that illustrates the need for some constraint on the depth. Theorem 3.1 shows that when the depth is allowed to grow polynomially in the input dimension d, the function computed by a random ReLU network essentially constant, which rules out the possibility of adversarial examples.
The heart of the proof of Theorem 1.1 is to show smoothness property like (1). It exploits decomposition of the change of gradient between two input vectors. Define H, g xdd xd,

---

as fx(x))( = _{j = k, (z)5 2 0} with v1(x) = (W1z)) For two input vectors
3, E IRd we will see in Section 2.4 that we can decompose the change of gradient as
H+1 [.))))))))))
- -
Σ Wett
-
II (=)-1
H.(
==1 i==
(Here and elsewhere, indices of products of matrices run backwards, so Il. M₁ = when j < k.) For the jth term the decomposition, we need to control the scale of: the gradient of the mapping from the input the output of layer j. the change in the layer nonlinearity (z)x) H,(y), and the gradient from layer to the output. It turns out that controlling these quantities depends crucially on the width of the narrowest layer before layer j-we call this the bottleneck layer for layer j. This width determines the dimension of the image at layer j of a ball in the input space. In proving bounds on gradients and function values that hold uniformly over pairs of nearby vectors æ and y. this dimension- the width of the bottleneck layer-dictates the size of a discretization (an e-nel) that is crucial ingredient in the proof of these uniform properties. Our analysis involves working separately with the segments between these bottleneck layers. We show that for an input E IR satisfying ||=||| || = Vd and any in a ball around z, with high probability Vf(x)) V [()]]l = o(1), but [ is no more than a constant and [ is at least a constant. This implies the existence
of a small (o(1I= (D) perturbation of x in the direction fz) that flips the sign of f(z).
These results suggest several interesting directions for future work. First, our results show that for high-dimensional inputs, adversarial examples are inevitable in random ReLU networks with constant depth, and unlikely networks with polynomial depth. Beyond this, we do not know how the sensitivity input perturbations decreases with depth. Similarly, both results are restricted to networks with subexponential width, and it is not clear what happens for very wide networks. Finally, we show that networks with random weights suffer from adversarial examples because their behavior is very similar to that of random linear functions. It would be worthwhile to determine whether randomly initialized trained networks retain this nearly linear behavior, and hence suffer from adversarial examples for the same reason.
Related Work: Related thcoretical work include the recent result of Bubeck and Sellke [BS21] who, following up Bubeck, Li and Nagaraj [BLN21], show that only mildly over- wee-paarmeteriieed networks when trained on random data have large Lipschitz constants. While these results apply to broader class of networks including those potentially trained on data, this weaker property on its own does not suffice to explain the prevalence of adversarial examples and computational ease of finding them. Indeed, establishing this fact requires understanding the behavior of the local landscape of the function computed by the network which these approaches do not capture.
Closely related empirical works include work by Madry, Makelov, Schmidt, Tsipras and Vladu [MMS+ 18] and by Qin, Martens, Gowal, Krishnan, Dvijotham, Fawzi, De, Stanforth and Kohli [QMG+ + 19]. We note that both these works emphasize the importance of the interplay between the local behavior of the function and the existence of adversarial perturbations. [MMS+ 18] identify local
near-linearity as cause of adversarial examples and propose a robust training procedure attempting to eliminate this property. On the other hand, [QMG+ 19] suggest an alternative robust training procedure that retains local lear-linearity but eliminates adversarial examples by ensuring that the learnt network (despite being locally linear) is robust to single-step perturbations. Our work lends theoretical grounding this phenomenon showing that local linearity arises naturally initialization.
2 Proof of Main Theorem
In this section, we provide an outline of the proof of Theorem 1.1. As described above, we will prove our result first by showing that the gradient at x has large norm and changes negligibly in a large ball around x. The first condition is established Subsection 2.1. The second step is more intricate. First, we prove the decomposition of the gradient differences in Subsection 2.2. Then, in Subsection 2.3, track the scale of the ball around x propagates through the network. Finally, in Subsection 2.4,
3

---

we use this result to bound the terms in the decomposition of the gradient differences to show that our network is locally linear. For the rest of the proof, unless otherwise stated, we consider a fixed I E 12d and we assume:
Vamin
dminn 2 d log 1/6, ||>||| vd and (flog )
52 ((e log dmax) )
Additionally, randomize the activations of neurons whenever they receive an input of 0. This does not change the behavior of the neural network in terms of its output or the images of the input through the layers of the network but greatly simplifies our proof. For x E IRd, we let:
To = = f((=== = - (D.(0))sx = {
w.p 2 if k. Vj 0, j = k. > O, f((x) (())=))(())))()))) otherwise,
Our first key observation is that the randomization in the activation units allows us the following distributional equivalences, proved in Appendix A.1.
Lemma 2.1. Let m E N, {de] C Id and W, E Rd:xd, 1 be distributed such that each entry of We is drawn üd from any symmetric distribution. Then, defining for x E dR:do:
ho (x) = I, Th (x) = (1)--1 where (Di(v)lss has ha(x)) = (x)
1, i = k and >> 0
1, with probability 1 if Yj
0, otherwise
we have the distributional equivalences for any x + 0 and fixed diagonal matrices B Bm
B,)W, II (,,(,( & j=m-1
Wm
II (D, + B,)W, j=m-1
( i (0,0+( B,W,
d II (D, + B,)W,
{1
with probability 1/2 if =
where (Dz)a.
(0.
otherwise
2.1 Concentration of Function Value and Gradient at a Fixed Point
We first present simple lemma that shows that the gradient at x at least constant and that its output value is bounded. The proof gives illustration of how Lemma 2.1 will be used through the more involved proofs in the paper.
Lemma 2.2. For some universal constant with probability at least - 5 we have:
1
If(x)) < et Vlog 1/5 and [[
2-+1
Proof. Note that
vf(x)= = We+1 II D.(f(x))) and f(x) = vf(r)x. i= And we have from Lemma 2.1, ff(x) - Wet I D.W, where = (Di)ak = {
with probability 1/2 k, (Wi & (W)
otherwise,
Therefore, it suffices to analyze the random vector We+1 I W.W. We first condition on favorable event for the D,. Note that we have by the union bound and an application of Hoeffding's inequality (e.g.. [BLM13, Theorem 2.8l) that:
Tr Dr 2 di with probability at least 8/4,
Vi [
3

---

since dp 2 clog(4e/0). We now condition on the D; and note that:
We+1
II
D,W,
W
w
where
i=f
i=
Vi E (2,.... f W. E TY DIXT W (WT),, MO, r/d), W (O T/de), vi (2. -.......-... E+ (W.)s ~ N (0, (0.1/d
IR
TRIXTD De W E Dr
From the above display, we obtain from Theorem C.3 and its corollary C.4,
W
W
W1
W i=
with probability at least 1 - 6/(4e)
2
i=(
with probability at least - 6/4 4 by induction,
2++1
since minogige d: 2 clog(40/0) Through similar argument, we obtain:
Wenn I 2
(2)
i=!
with probability at least - 8/4. We also have:
Wen1 II D.W, ==
We+1 II D.W; t=
d Unif (msd-1).
Combining this, Eq. (2) and Lemma C.6, we get that:
[f(z) S c2' /log 1/5
with probability at least 1 - 8/2, for some absolute constant c. A union bound over all the preceeding events concludes the lemma.
2.2 A Decomposition of Local Gradient Changes
The following decomposition allows us to reason about deviations layer by layer:
We+1 ii D. II D.C.Co))).
f)(x) (f()
i [I - + De(F((o))) we II p.(.)).
Wet1
li=E
1=6-1
Weii
De((((>)))e
[I D.(,())))W II D.(.WO)).) 1=--1
1=--1
+ (Di(T((e)) - D.(..O) II D.(.O))
1-8-1
Σ Wen
II D.(())))) i=!
-
I i=j-1
D.C.(o)))
(GD-DECOMP)
We use this decomposition to show that the gradient is locally constant. Concretely, consider fixed term in the above decomposition and let i" arg min;ej d,. Letting M,. = - D.(f(w))., we can bound single term, Aj. as follows:
j+1
++1
p.(. )
|IAZ.
||ر < W
II I...()))) -OCE(G))-((CEE))))
II
5

---

We bound the above by bounding both of the two factors on the right- right-hand-side. In the above expression, the length of A is bounded by a product of the length of the corresponding factor in a truncated network starting at the output of layer i" and a product of masked weight matrices up to layer i" corresponding the actívation patterns of y. Intuitively, the first factor is expected to be small if the images of and y layer i' close and hence, show that an image of suitably small ball around x: remains close to the image of x: through all the layers of the network (Lemma 2.3). We then prove spectral norm bound on Mi- in Lemma 2.6 and finally, establish a bound on || || Lemma 2.8 where we crucially rely on the scale preservation guarantees provided by Lemma 2.3. Finally, combining these results with those of Subsection 2.1 completes the proof of Theorem 1.1.
2.3 Scale Preservation of Local Neighborhoods
In this section, we show that the image of a ball around x remains in ball of suitable radius around the image of z projected through the various layers of the network. Here, we introduce additional notation used in the rest of the proof:
Vj {0) ue 1]: (z)(z) z, vi f(,((z) Wife-1)()). -.,,) f()()=
We now describe the decomposition of the neural network into segments, which are bounded by what we call bottleneck layers, and our analysis works separately with these segments. This decomposition crucial for reducing the sizes of the c-nets that arise in our proofs. Intuitively, when we construct an e-net prove that some property holds uniformly over ball, it is crucial work with the lowest- dimensional image of that ball, which appears in a bottleneck layer. These bottleneck layers are denoted by indices {i, }/ defined recursively from the output layer backwards with the convention that do = d:
i == arg min dis
Vj > 1 s 2 1, 2 == arg min jei
Eiiin
min dj. JZt
(NN-DECOMP)
ise
- 1]. de, < diyz and for all & fiy41...... ., 13, d2 diyzs- Note, that im 0, for all j E [m [m-
The following technical lemma bounds the scaling of the images at a layer in the network of an input r and of ball around x. The crucial properties we will exploit are that these images avoid the origin, and that the radius of the image of the ball is not too large. The full proof is deferred Appendix A.2. In the proof sketch, we carry out the section of the proof where we transition between bottleneck layers in full as it is simple illustration of how such ideas are used through the rest of the proof.
Lemma 2.3. We have with probability least 1 5,
vi E 10 : [1f((()1
2 Vdl.
M||> x1| S R: (17(()) F((')11 (Clog d )1/2
1+
R.
P'uin
d;
VII - x1| < R: [x(()) - f((x')l < (Clog d 1/2
1
R..
d'ain
Proof Sketch. The proof of the first claim is nearly identical to that of Lemma 2.2.
For the second claim, we use gridding argument with some subtleties. Concretely, we construct new grid over the image of B(x, R) whenever the number of units in a hidden layer drops below all the previous layers in the network starting from the input layer. These layers are precisely defined by the indices i, in NN-DECOMP, We now establish the following claim inductively where we adopt the convention in = l
Claim 2.4. Suppose for j 2 1 and R < dmax R:
Vy E B[I, R): flfa (x) f(,( < R.

---

Then:
vie E2 1......... 11,
((,, R) (f((z) )- - F((U)l & (CElog dmax)) (6-1/))2
dj R di,
V
Vy E [a,, R) [1 ( - (w)l < (Og (mnx)) with probability at least - 6/81.
Proof Sketch. We start by constructing an e-net [Ver18, Definition 4.2.1], g, of fú, (B(r, R)) with )82 Note that we may assume |g] I (10R/e)(,, We will prove the statement on the grid and extend to the rest of the space. For layer i + 1, defining T = fú, (T), we have vÿ G:
[1 (z) - Je+1a, (7) = [ [i,,, r
J1,5, (7))
di-1 d;
(1
log 1/8'
< 115 Jea, (1)
1
d
with probability at least 1 - 8' as before by Theorem C.3. By setting 8'= that d; 2 di,. the conclusion holds for layer + 1 S ij on with probability at least 8/(16.). By induction and the union bound, we get:
(16]])) and noting
di R V dip
Vi E Li + 1, - E G 1Fi,, Fu, (3) (CElog dmaxx) (i-i))/2
Vfe 9: I| 1 (0) - Jrg 15, (3) S (CElog (0-1
with probability at least 1 8/(16)). To extend to all y fi, (B(r, R)), condition the bound ||Wil| given by Lemma C.1 for all < i--1 and note that Vy E Sú, (B(x,, for y = arg min segl= - yll. and for + S 1j-1,
[1f (T) (w)ll = (T),, f.,,(0)) (7)I lff (v) Fua, (0)
< 11F F.., (i)) Øl
|
k
dp
s - +E II
C
dx-1
K=
dl
11f,,,()) Fr,, (1) -
V
clip"
using that d; 2 di,- Similarly, for i = 1--1. we have
d
[h, 2nl (7) - Jr, 1 (v) S [| 1 1.,(()) (z) - Je, 1nly (7)
+ -
di
Our setting of & concludes the proof of the claim.
An inductive application of Claim 2.4, a union bound and the observation that:
lx)()) - f(())l s (l F((y))
concludes the proof of the lemma.
The following lemma shows that few neurons have inputs of small magnitude for network input Lemma 2.5. With probability at least for all [e]. we have:
# H15 5 ((W f(()) a Vd, }
[1((())]1 }
2
> 1 2
4 dit1-
Proof. Follows from the fact that of Hoeffding's Inequality.
cv 2 for Z NOO, 1), plus simple application
D
7

---

2.4 Proving Local Gradient Smoothness
In this section, we show that the gradient is locally constant, and thus complete the proof of Theo- rem 1.1. our proof, we will bound each of the terms in the expansion of the gradient differences (GD-DECOMP), First, we prove structural lemma on the spectral norm of the matrices appearing in the right-hand-side of (GD-DECOMP), allowing us ignore the portion of the network till the last-encountered bottleneck layer. Define, for all i j. Myy(y) -I PR(fe(v))Wa.
Lemma 2.6. With probability at least 1 over the {Wk}, have:
Vly-=l1 & R.j E [m-1): P(DI().... D4O3 (1 (v) S (C- e. log dmnax) (54)))
where the probability is taken with respect to the random choices in the definition of the Dx(()-
We provide the first part of the proof in full as the simplest application of ideas that find further appli- cation in the subsequent result establishing bounds on terms in (GD-DECOMP); see Appendix A.3.
Proof Sketch. To start, consider fixed j E [m]] and condition on the conclusion of Lemma 2.3 up to level i5+1. Now, consider an E-net of f1 (B(r R)), ) 9, with resolution 1/(dmax) As before,
| < (Cdmax)
) 481 for some constant C. We additionally will consider subsets
S (Sw) Sy S [d&], S S 4d.
Note that |g] 1112 < (dmax)
6ildi,+1, For E g, S S E S. consider the following matrix:
1511+1
1, i = j and E S,
Mhide
II
(DelFrees (D))) W where (Ds)ss
U.81 ,
0. otherwise.
Army
We will bound the spectral norm M g.st s2.
First, note that:
441+1
Missaa U.St..s
M
1 8. _2
where M M u. = W,, II
(Du(fres- + (Dsg Dsz))
k=
and observe that from Lemma 2.1:
fy-1+1
M
Wi,
(Dx -Dss,,Dss))WWa where (Da)i. = k=
II
w.p i otherwise.
y.st D.S"
To bound the spectral norm, let be a 1/3-net of gd, -1 and E B. Applying Theorem C.3,
1 2441
S
W
+11+2 +2
II
(Dx + (Dst Deg))Wee)
(1+
1+
log 1/8' d:yt:
9,5t
k=f;-1
15+1
log 1/8'
1+
d+
Amm
with probability at least 6o'. But setting 8' = 5/(16E2 191 |S|²) yields with probability at least
1 8/16: Vy G. S, S2 e S;
M S. S (C log dmax (00-50011110 111)/2
On the event in the conclusion of Lemma 2.3, have that f((y) + 0 for all [Ω.y and therefore, we have by union bound over the discrete set G:
Vy G, k E (ist1...., is} E [d+] (Fr., (w)) #0
proving the lemma for y E G as the activations are deterministic. For y & G. the following claim concludes the proof of the lemma. The claim is essentially generalization of [BCGdC21, Eq. (18) and its proof is deferred to the appendix.

---

Claim 2.7. With probability at least 1 1 /// over the [W&), we have for all m E f8z+1 + 1...,,...., and E (B) R)):
(B(z,
[Delōrages (v)) De (1)) (Tr)D (v)) Dm (fmmmy (1)) S )
where ÿ arg mi || yll, and the probability is taken with respect to the random choices in the definition of the (-).
The previous claim along with our previously established bounds establish the lemma.
Our final technical result establishes the near-linearity of f in ball around The full proof is deferred to Appendix A.4 but in our proof sketch we identify sections which involve considerations unique to this lemma.
Lemma 2.8. For some absolute constant C, with probability at least 1 - over the {W*}: Oe
V|| wll s R [4] 110::P(piCeee (P.(fatt)) [V (Vf(c)-Vf(o)) (11g
(Tog' Songdduax dumax
where the probability is taken with respect to the random choices in the definition of the DE(-).
Proof Sketch. Consider a fixed term from (GD-DECOMP); that is, consider:
H+1
I 1-j-1
Diff, = We+1
i=!
We will show with high probability that ;iff; is small for all y E Bar,, This will then imply the lemma by union bound and (GD-DECOMP). Let & be such that is. = arg minmay dm We will condition on the weights of the network up to layer ig. Specifically, we will assume the conclusions of Lemmas 2.3 and 2.6 up to layer ig. We may now focus our attention solely on the segment the network beyond layer ig as a consequence of the following observation and Lemma 2.6:
( s |Diff (z, 3)ll MI ov))l where
(3)
++1 II
i++1
Diff ( = We+1
I..(((()))) (D)(F(()) (D)( -D,(,(,))), i=
II D.CKCO))W
We will show for all y such that lyy x|| s R:
{ [IDiffy a)ll 2
C
P (o)
= 0
(e log dmax )
with probability at least 5/(1662).
We have from Lemma 2.1 that the random vector H defined below is spherically symmetric and satisfies || < 2 with probability at least 1 8/(16)*):
j+1
j+1
We+1 II D.(F())) & Wet1 II D.W. = H. ==
i=
As in the proof of Lemma 2.6, let G be e-net of fi, (B(sr, R)) with in the proof of Lemma 2.6. We now break into two cases depending on how d, compares to d, and handle them separately. At this point, we have effectively reduced the multi-layer proof to the problem of analyzing deviations of activations at fixed layer. For the remaining proof, we generalize approaches [DS20] for the small width case and [BCGdC21] for the large width case.
Case 1: dj S di, (1 log )20e In this case, the key observation already made in [DS20] is that under Lemma 2.3, the number of neurons that may actually differ at layer j is at most d, /olyol log dmax)) between E B(x, R) and x. Since, H is spherically distributed, (=)) - (x))( is very small and consequently the whole term is small.

---

Case 2: d, 2 dig (6 log dmax))a0. This case is analogous to [BCGdC21]. The proof is technically involved and requires careful analysis of the random vector H (D,, (f)(()) - (f which is complicated in our setting due to the matrices preceeding it in (GD-DECOMP) It involves the distributional equivalence in Lemma 2.1.
union bound and an application of the triangle inequality now imply the lemma.
Proof of Theorem I.I. On the intersection of the events in the conclusions of Lemmas 2.2, 2.3 and 2.8, we have that (x)) deterministic and furthermore, we have:
[V(())] 2 2441
[[(x) S c2 v Vlg 1/0
Ay s.t lly x1| R: (x) v (Elog dmax) o(1).
Assume f(x) > (the alternative is similar) and let 2' log 1/g (x)), defining the function g()) = f(xx f()):
we have for the point
[V5(x]]
f(x ((++V/(²)) = f(x) + / g g()d)tt f(x) + L.
f(xx - (1-o(1))2 log logd/log11 1/8 < - fzz).
Our lower bounds on f((x) ensure |/ f())] - R, concluding the proof of the theorem.
The Impact of Depth
Theorem 1.1 relies on the depth being constant. In this section, we show that some constraint on the depth is necessary in order to ensure the existence of adversarial examples. In particular, the following result gives example of sufficiently deep network for which, with high prohability, the output of the network will have the same sign for all input patterns.
Theorem 3.1. Fix a sufficiently large d E N, & 2 de and (ed)20 S k S exp(yV), and consider the randomly initialized neural network (NN-DEF) with d1 constant C such that with probability at least 0.9,
de k. There is universal
[f(x) f(vil S CV log d
Vx, y EESES Ed-11
[f(x))
The proof involves showing that the image of gd-1 bounded away from 0 and that the inner products between images of input vectors throughout the network converge. The following lemma shows how the expected inner products evolve through the network. The lemma follows from computing double integral; see [CS09, Eq. (6)]. The proof of Theorem 3.1 is in Appendix B. Lemma 3.2. Let d N. Fix x, y Idd with x, y # O. Then for g I):
E max {g x, 0} max (g T v.
sin 0
(
1 0 7
cos 0
/ E[(max {g xr 03)² E(max {g y, 0})²
π
where 0 arccos(x //((/= (1le))).
4 Disclosure of Funding and Competing Interests
PB and YC gratefully acknowledge the support of the NSF through grants DMSS2023505 and DMS- 2031883, the Simons Foundation through award #81 1639, and Microsoft through the BAIR Open Research Commons. We declare competing interests.
10

---

References
[BCGdC21] Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, and Rémi Tachet des Combes. A single gradient step finds adversarial examples on random two-layers neural networks. arXiv, 2104.03863, 2021. 1, 8, 9, 10
[BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities. Oxford University Press, Oxford, 2013. 4, 27
[BLN21] Sébastien Bubeck, Yuanzhi Li, and Dheeraj M. Nagaraj. A law of robustness for two- layers neural networks. In Mikhail Belkin and Samory Kpotufe, editorss, Conference Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 804-820, PMLR, 2021. 3
[BLPR19] Sebastien Bubeck, Yin Tat Lee, Eric Price, and llya Razenshteyn, Adversarial examples from computational constraints. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, vol- ume 97 of Proceedings of Machine Learning Research, pages 831-840. PMLR, 2019.
[BS21] Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. CoRR, abs/2105. 12806, 2021. 3
[CS09] Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Bengio,
D. Schuurmans, Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009, 10
[CW17a] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pages 39-57, 2017.
[CW17b] Nicholas Carlini and David A. Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. Bhavani M. Thuraisingham, Battista Biggio, David Mandell Freeman, Brad Miller, and Arunesh Sinha, editors, Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, AlSec CCS 2017, Dallas, TX, USA, November 3, 2017, pages 3-14. ACM, 2017.
[DS20] Amit Daniely and Hadas Shacham. Most ReLU networks suffer from l adversarial perturbations. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6629- 6636. Curran Associates, Inc., 2020. 1.9
[FCSG17] Reuben Feinman, Ryan R. Curtin, Saurabh Shintre, and Andrew Gardner. Detecting adversarial samples from artifacts. arXiv, 1703.00410, 2017. 1
[GSS15] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. 1
[MMS 18] 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. 1,3
[QMG 19] 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 Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. 1,3
11

---

[SSRDI9] Adi Shamir, Itay Safran, Eyal Ronen, and OIT Dunkelman. A simple explanation for the existence of adversarial examples with small hamming distance. arXiv, 1901.10861.
2019. 1
[SZS 14] Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[Ver18] Roman Vershynin. High-dimensional probability, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018. 7, 14, 22
12


Reviews:
[{"review_id": "t2hlXalauov", "reviewer": "Reviewer_2Ydc", "summary": "This paper studies how adversarial examples arise in constant depth ReLU networks with independent Gaussian parameters. The main results of the paper is Theorem 1.1 which determines how the width of different network layers affect the probability of the existence of adversarial examples. Overall, the most important takeaway is that smoothness (or the absence of adversarial examples) requires networks that are polynomially (in the number of input dimensions) deeper and/or wider.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 mathematically heavy. While the math seems to work out (I haven't thoroughly gone through every equation), I found no discussion about the proposed theorem.\n\n1) The abstract is unclear. Aside from stating that \"adversarial examples arise in these [ReLU] networks [with independent Gaussian parameters] because the functions that they compute are very close to linear\", it is difficult to understand what the main theorem implies.\n\n2) The rest of the paper is just as uninformative. I understand what the proof states and that it is a generalization of the results from Daniely and Schacham (2020) and Bubeck et al. (2020), but it is unclear what it implies. A thorough discussion on the implications of the theorem would be welcome (beyond the single paragraph listed after the proof).\n\n3) The related work is missing. Some of it is sprinkled through the paper, but it is again quite difficult to judge the significance of this work without a dedicated section. How does this work relate to empirical work like [MMS+18] or [QMG+19]? How does it relate to over-parametrization and generalization?\n\n4) Finally, for my own understanding, Theorem 3.1. roughtly states that one needs a depth of at least d^3 while Bubeck and Selke (2021) state that \"smooth interpolation requires d times more parameters\" (where d is the number of inputs dimensions). Can the authors comment on the difference and complementary of the results?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I haven't found any discussion about the limitations and/or societal impact. Maybe the authors can highlight some of those in the rebuttal.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "puIwRwXh-hg", "reviewer": "Reviewer_ZKWX", "summary": "EDIT: I will be keeping my (positive) score.\n\nThe paper studies robustness properties of ReLU networks that have random weights. The main finding is that random ReLU nets of constant depth are susceptible to adversarial examples for every input vector. The main theorem relies on some conditions about the widths in the networks' layers. To complement this result, the authors show that in the large depth regime, such a result cannot hold.\n\nThe paper builds on prior work and  their main result generalizes results of Daniely and Schacham (2020) for networks with rapidly decreasing width and results of Bubeck et al (2021) for two-layer networks. Some ideas and intuition come actually from prior works: \nthe main goal is to demonstrate the existence of an adversarial example near input x,  and to do this for a function f, it turns out that it suffices to show the smoothness property: see (1) . This \"smoothness\" property is not in the common sense of the word \"smooth\" function, but basically says that for a deep ReLU network with random parameters and a high-dimensional input vector\nx, there is a relatively large ball around x where f satisfies this smoothness property. \n\nThe main result is Theorem 1.1 that proves how taking a small step away from a point x in the direction of the gradient can flip the sign of the evaluated function f at x thus corresponding to an adversarial example. The most interesting condition is that the min depth of the net $d_\\min \\ge c_1(\\log d_\\max)^{c_2} \\log 1/\\delta$.\n\nThe authors also prove a converse result to justify why their results could only be true in the constant depth regime. This complementary result is given in Theorem 3.1 which shows that when depth grows polynomially in the input dimension d, the function computed by a random ReLU network can essentially be constant, which rules out the possibility of adversarial examples.\n\nFor theorem 1, an important aspect of the architecture of the network that allows for adversarial examples or not, depends crucially on the width of the narrowest layer before layer j—that  is \"the bottleneck layer\" for layer j as the authors call it. This width determines the dimension of the image at layer j of a ball in the input space. In proving bounds on gradients and function values that hold uniformly over pairs of nearby vectors x and y, this dimension—the width of the bottleneck layer—dictates the size of a discretization that is a crucial ingredient in their proof.\n\n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "TL;DR: interesting paper with very nice result on adversarial examples for constant depth ReLU nets\n\nThe reviewer finds the paper both technically and conceptually very interesting. It provides a plausible explanation for the abundance of adversarial examples in modern neural nets by giving theory on how such examples would arise. They state a simple property on the gradients that would be sufficient for the existence of attacks and then the authors try to understand how this property would appear in NN. The main result is on constant depth neural nets but the authors complement this by saying the once we allow depth to increase, there can be cases where NN compute functions close to constant hence they don't suffer from adv. examples.\n\nI think the paper is very well-motivated given the lack of understanding for adv. examples and provides a nice set of ideas that will likely be used in future works.\n\n\nTYPO IN THEOREM 1: sign of f(x) -- I think the authors meant to put sign in front of f\n\nQUESTION to the authors: One might have expected that when the depth is allowed to grow more, then this would lead to even more adversarial examples?  Maybe a naive rationale for this has to do with the lipschitzness of the network that could potentially map x+dx far away from x. My understanding is that because of the randomness in the network, one can avoid adversarial examples as the authors show. But one question that comes to mind is why is it that deep networks in practice tend to suffer from attacks? Is there some difference in the way the initialization or optimization procedures are done?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KHLJgYSTk4c", "reviewer": "Reviewer_zVxB", "summary": "This paper studies some adversarial examples in random ReLu networks, where a smaller perturbation generates a negative label.\n\nThe main result of the paper is some theorems. and the main technique used in the paper is mostly some inequality manipulation and concentration. I cannot check all the derivations, but the main results, i.e. the constants are convincible to me.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "My major concern comes from the applicability of the property it studies. A network with random weights can hardly be associated with any machine learning applications. I can get the point that due to technical difficulty. It is hard to analyze in general, but I think the paper should mention the difference between the random network and a trained network, e.g. if the network is trained, the constants in theorem 1.1. will increase or decrease?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experients are ignored in the paper. I get it as common in this field. But still, at least the paper improves upon previous theoretical papers, e.g. it claims that \" the minimal width up to some point in the network determines scales and sensitivities of mappings computed up to that point\", the authors are encouraged to design an experiment to verify, even without verifying the magnitudes of constants in the theorem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "BOEfVkACmq", "reviewer": "Reviewer_BmM8", "summary": "This paper analyzes multi-layer random ReLU networks, and shows theoretical evidence that for constant depth networks with a variety of widths, adversarial examples must necessarily exist. They prove this result based on the key idea that such random networks are nearly linear, and that establishing smoothness accounts for the network’s nonlinearity. Further, they show that adversarial examples will not exist if the depth grows too large.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "Overall, this paper appears original, has a significantly improved result compared to prior work (extending from 2-layer networks to general constant-depth networks), and is presented in a very clear fashion. The intuition behind each step of the proof is carefully presented in the introductory section, and various proof techniques, such as analyzing the bottleneck layer, are discussed. The proof itself, as well as the key intuitions behind each step of the proof, are also presented in a clear and understandable fashion (there are a lot of important details in the proofs too, which I did not go over carefully). All in all, I would recommend an accept.\n\nI have some suggestions and questions for the authors.\n1) Spelling/Grammar - gaussian and euclidean should be capitalized. Heoffding should be Hoeffding.\n2) Does the proof still hold when the output dimension is not a single real output? What if it’s a k-dimensional output (e.g. if there are k logits)?\n3) This is not necessary, as I believe that the theory presented is an important contribution by itself, but what future experiments (L90) would you suggest to determine if randomly initialized trained networks retain this nearly linear behavior? For example, Lemma 2.2 relies on the gradient being bounded away from 0, but this would probably not be true for a trained neural network, right?\n\n\nUPDATE: After reading the author response, I will keep my score of Accept, as I still feel that this is an interesting paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. With that said, it is a purely theoretical paper, so I do not believe there is too much for the authors to discuss here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies adversarial examples in ReLU networks with independent gaussian parameters. Reviewers were generally happy with the results of the paper. In particular, authors' responses in the rebuttal period helped clarify some concerns. Overall, I think the paper is above the accept threshold. 
Decision: Accept (Poster)