Adversarial Examples in Multi-Layer Random ReLU Networks
Year: 2021

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 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.

heading: 1 Introduction and Main Result
text: Since the phenomenon of adversarial examples was first observed in deep networks [SZS+14], there has been considerable interest in 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 in certain ReLU networks—those in which each layer has vanishing width relative to the previous layer—and conjectured 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 a wide variety of network architectures—those with constant depth and polynomiallyrelated widths. The key fact underlying this phenomenon was already observed in [DS20]: a high-dimensional linear function f(x) = w>x with input x 6= 0 and random parameter vector w with a uniformly chosen direction will satisfy krf(x)k kxk |f(x)| with high probability. This implies
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the existence of a nearby adversarial example for this linear function: a perturbation of x of size |f(x)|/krf(x)k ⌧ kxk in the direction f(x)rf(x) will flip the sign of f(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 2 Rd,
|f(x + u) (f(x) + hu,rf(x)i)|  kuk sup krf(x) rf(x + v)k : v 2 Rd, kvk  kuk ,
and thus to demonstrate the existence of an adversarial example near x for a function f , it suffices to show the smoothness property:
for all v 2 Rd with kvk . |f(x)|/krf(x)k, krf(x) rf(x + v)k ⌧ krf(x)k. (1) We show that for a deep ReLU network with random parameters and a high-dimensional input vector x, 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 in 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 (1), it suffices to have krf(x) rf(x + v)k  ✏ + (kvk), for some increasing function : R+ ! R+, provided that ✏ + (kvk) ⌧ krf(x)k. We prove an inequality like this for ReLU networks, where the ✏ term decreases with width.
Consider a network with input dimension d, `+1 layers, a single real output, and complete connections between layers. Let d1, . . . , d` denote the dimensions of the layers. The network has independent random weight matrices Wi 2 Rdi⇥di 1 for i 2 [` + 1], where we set d0 = d and d`+1 = 1. For input x 2 Rd, the network output is defined as follows:
f(x) = W`+1 · (W` · (W` 1 · (· · · (W1 · x) · · · ))) where (x)i = max{xi, 0}
W`+1 ⇠ N (0, I/d`) and 8i 2 [`], (Wi)j,k i.i.ds N (0, 1/di 1). (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 ↵ > 0, (↵x) = ↵ (x)), the scaling is not important for our results; the 1/di 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 ` 2 N. There are constants c1, c2, c3 that depend on ` for which the following holds. Fix 2 (0, 1) and let f(·) be an (` + 1)-layer ReLU neural network defined by (NN-DEF) with input dimension d and intermediate layers of width {di}`i=1. Suppose that the widths satisfy
dmin c1(log dmax)c2 log 1/ where dmin = min {di}`i=1, d , dmax = max {di}`i=1, d .
Then for any fixed input x 6= 0, with probability at least 1 ,
|f(x + ⌘rf(x))| |f(x)| and sign(f(x + ⌘rf(x))) 6= f(x),
for an ⌘ satisfying k⌘rf(x)k
kxk  c3
r log 1/
d .
It suffices to choose c1 = (C1`)c2 , c2 = C2`, c3 = C`3, for some absolute constants C1, C2, C3.
This theorem concerns networks of fixed depth, and the constants in the size of the perturbation and in the requirement on the network width are larger for deeper networks. We also prove a 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 is essentially constant, which rules out the possibility of adversarial examples.
The heart of the proof of Theorem 1.1 is to show a smoothness property like (1). It exploits a decomposition of the change of gradient between two input vectors. Define Hi : Rd ! Rdi⇥di
as Hi(x)jk = 1{j = k, vi(x)j 0} with vi(x) = Wi (· · · (W1x)). For two input vectors x, y 2 Rd, we will see in Section 2.4 that we can decompose the change of gradient as
rf(x) rf(y) = `X
j=1
W`+1
j+1Y
i=`
Hi(x)Wi ! · (Hj(x) Hj(y))Wj ·
0 @ 1Y
i=j 1 Hi(y)Wi
1
A .
(Here and elsewhere, indices of products of matrices run backwards, so Q k
i=j Mi = I when j < k.) For the jth term in the decomposition, we need to control the scale of: the gradient of the mapping from the input to the output of layer j, the change in the layer j nonlinearity Hj(x) Hj(y), and the gradient from layer j 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 x and y, this dimension—the width of the bottleneck layer—dictates the size of a discretization (an ✏-net) that is a 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 x 2 Rd satisfying kxk = p d and any y in a ball around x, with high probability krf(x) rf(y)k = o(1), but |f(x)| is no more than a constant and krf(x)k is at least a constant. This implies the existence of a small (o(kxk)) perturbation of x in the direction f(x)rf(x) that flips the sign of f(x).
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 in networks with polynomial depth. Beyond this, we do not know how the sensitivity to 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 theoretical work include the recent result of Bubeck and Sellke [BS21] who, following up on Bubeck, Li and Nagaraj [BLN21], show that only mildly over-parameterized networks when trained on random data have large Lipschitz constants. While these results apply to a 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 a 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 near-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 to this phenomenon showing that local linearity arises naturally at initialization.

heading: 2 Proof of Main Theorem
text: 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 in 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, we track the scale of the ball around x as it propagates through the network. Finally, in Subsection 2.4,
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 x 2 Rd, and we assume:
dmin (C` log dmax)240` log 1/ , kxk = p d and R := p dmin
(` log dmax)80` = ⌦ (` log dmax)
40` .
Additionally, we 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 2 Rd, we let:
x0 := x, efi(x) := Wifi 1(x), (Di(y))j,k =
8 ><
>: 1 w.p 12 if j = k, yj = 0, 1 if j = k, yj > 0, 0 otherwise, fi(x) = Di( efi(x)) efi(x).
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 2 N, {di}mi=0 ⇢ Rd and Wi 2 Rdi⇥di 1 be distributed such that each entry of Wi is drawn iid from any symmetric distribution. Then, defining for x 2 Rd0 :
h0(x) = x,
ehi(x) = Wihi 1(x)
hi(x) = Di(ehi(x))ehi(x)
where (Di(y))i,j =
8 ><
>: 1, if j = k and yj > 0 1, with probability 12 if j = k, yj = 0 0, otherwise
we have the distributional equivalences for any x 6= 0 and fixed diagonal matrices B1, . . . , Bm:
Wm
1Y
j=m 1 (Dj(ehj(x)) + Bj)Wj d = Wm
1Y
j=m 1 (Dj + Bj)Wj
1Y
j=m
(Dj(ehj(x)) + Bj)Wj d =
1Y
j=m
(Dj + Bj)Wj
where (Dj)k,l = ( 1, with probability 1/2 if k = l 0, otherwise

heading: 2.1 Concentration of Function Value and Gradient at a Fixed Point
text: We first present a simple lemma that shows that the gradient at x is at least a constant and that its output value is bounded. The proof gives an illustration of how Lemma 2.1 will be used through the more involved proofs in the paper. Lemma 2.2. For some universal constant c, with probability at least 1 we have:
|f(x)|  c2` p
log 1/ and krf(x)k 1 2`+1 .
Proof. Note that
rf(x) = W`+1 1Y
i=`
Di( efi(x))Wi and f(x) = rf(x)x.
And we have from Lemma 2.1, rf(x) d= W̃`+1 Q1 i=` DiW̃i, where
(Di)j,k = ( 1 with probability 1/2 if j = k, 0 otherwise,
{Wi}`+1i=1 d = {W̃i}`+1i=1 .
Therefore, it suffices to analyze the random vector W̃`+1 Q1
i=` DiW̃i. We first condition on a favorable event for the Di. Note that we have by the union bound and an application of Hoeffding’s inequality (e.g., [BLM13, Theorem 2.8]) that:
8i 2 [`] : Tr Di di
3 with probability at least 1 /4,
since di c log(4`/ ). We now condition on the Di and note that: fW`+1 1Y
i=`
Di fWi d = W † `+1
1Y
i=`
W † i where
8i 2 {2, . . . , `} : W † i 2 RTrDi⇥TrDi 1 , W † `+1 2 R 1⇥TrD` , W †1 2 RTrD1⇥d
(W †1 )j,: s N (0, I/d), W † `+1 s N (0, I/d`), 8i 2 {2, . . . , ` + 1} : (W † i )j,: s N (0, I/di 1) .
From the above display, we obtain from Theorem C.3 and its corollary C.4, W
† `+1
1Y
i=`
W † i
1 2 · W † `+1
2Y
i=`
W † i
with probability at least 1 /(4`)
1 2`+1
with probability at least 1 /4 by induction,
since min0i` di c log(4`/ ). Through a similar argument, we obtain: W̃`+1 1Y
i=`
DiW̃i
 2 `+1 (2)
with probability at least 1 /4. We also have:
W̃`+1
1Y
i=`
DiW̃i W̃`+1 1Y
i=`
DiW̃i
= m ! d = Unif mSd 1 .
Combining this, Eq. (2) and Lemma C.6, we get that:
|f(x)|  c2` p log 1/
with probability at least 1 /2, for some absolute constant c. A union bound over all the preceeding events concludes the lemma.

heading: 2.2 A Decomposition of Local Gradient Changes
text: The following decomposition allows us to reason about deviations layer by layer:
rf(x) rf(y) = W`+1
1Y
i=`
Di( efi(x))Wi 1Y
i=`
Di( efi(y))Wi
!
= W`+1
1Y
i=`
Di( efi(x))Wi ⇣ D`( ef`(x)) + (D`( ef`(y)) D`( ef`(x))) ⌘ W` 1Y
i=` 1 Di( efi(y))Wi
!
= W`+1 D`( ef`(x))W`
1Y
i=` 1 Di( efi(x))Wi
1Y
i=` 1 Di( efi(y))Wi
!
+ (D`( ef`(x)) D`( ef`(y)))W` 1Y
i=` 1 Di( efi(y))Wi
!
= `X
j=1
W`+1
j+1Y
i=`
Di( efi(x))Wi ! · (Dj( efj(x)) Dj( efj(y)))Wj ·
0 @ 1Y
i=j 1 Di( efi(y))Wi
1
A
| {z } j
.
(GD-DECOMP)
We use this decomposition to show that the gradient is locally constant. Concretely, consider a fixed term in the above decomposition and let i⇤ = arg min
i<j di. Letting Mi⇤ = Q1 i=i⇤ Di(
efi(y))Wi, we can bound a single term, j , as follows:
k jk  W`+1
j+1Y
i=`
Di( efi(x))Wi ! (Dj( efj(x)) Dj( efj(y)))Wj
0 @ i ⇤+1Y
i=j 1 Di( efi(y))Wi
1
A
kMi⇤k.
We bound the above by bounding both of the two factors on the right-hand-side. In the above expression, the length of j 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 to the activation patterns of y. Intuitively, the first factor is expected to be small if the images of x and y at layer i⇤ are close and hence, we show that an image of a 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 a spectral norm bound on Mi⇤ in Lemma 2.6 and finally, establish a bound on k jk in 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.

heading: 2.3 Scale Preservation of Local Neighborhoods
text: In this section, we show that the image of a ball around x remains in a ball of suitable radius around the image of x projected through the various layers of the network. Here, we introduce additional notation used in the rest of the proof:
8j 2 {0} [ [` + 1] : fj,j(x) = x, 8i > j : efi,j(x) = Wifi 1,j(x), fi,j(x) = Di( efi,j(x)) efi,j(x).
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 is crucial for reducing the sizes of the ✏-nets that arise in our proofs. Intuitively, when we construct an ✏-net to prove that some property holds uniformly over a ball, it is crucial to work with the lowestdimensional image of that ball, which appears in a bottleneck layer. These bottleneck layers are denoted by indices {ij}mj=1, defined recursively from the output layer backwards with the convention that d0 = d:
i1 := arg min i` di, 8j > 1 s.t ij 1, ij+1 := arg min j<ij dj , d i min = min j<i dj . (NN-DECOMP)
Note, that im = 0, for all j 2 [m 1], dij < dij+1 and for all k 2 {ij+1, . . . , ij 1}, dk dij+1 .
The following technical lemma bounds the scaling of the images at a layer in the network of an input x and of a 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 to 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 a simple illustration of how such ideas are used through the rest of the proof.
Lemma 2.3. We have with probability at least 1 ,
8i 2 [`] : kfi(x)k 1 2i · p di,
8kx0 xk  R : k efi(x) efi(x0)k  (C log dmax)i/2 · 1 +
s di
d i
min
! · R,
8kx0 xk  R : kfi(x) fi(x0)k  (C log dmax)i/2 · 1 +
s di
d i
min
! · R.
Proof Sketch. The proof of the first claim is nearly identical to that of Lemma 2.2.
For the second claim, we use a gridding argument with some subtleties. Concretely, we construct a 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 ij in NN-DECOMP. We now establish the following claim inductively where we adopt the convention i0 = ` + 1.
Claim 2.4. Suppose for j 1 and eR  dmax · R:
8y 2 B(x, R) : kfij (x) fij (y)k  eR.
Then:
8i 2 {ij + 1, . . . , ij 1 1}, y 2 B(x, R) : k efi(x) efi(y)k  (C` log dmax)(i ij)/2 · s di
dij
· eR,
8y 2 B(x, R) : k efij 1(x) efij 1(y)k·  (C` log dmax) (ij 1 ij)/2 · eR
with probability at least 1 /8l.
Proof Sketch. We start by constructing an "-net [Ver18, Definition 4.2.1], G, of fij (B(x, R)) with " = 1/(d`max)
32. Note that we may assume |G|  (10 eR/")dij . We will prove the statement on the grid and extend to the rest of the space. For layer i + 1, defining ex = fij (x), we have 8ey 2 G:
k efi+1,ij (ex) efi+1,ij (ey)k = kWi+1(fi,ij (ex) fi,ij (ey))k
 kfi,ij (ex) fi,ij (ey)k · r di+1
di · 1 +
s log 1/ 0
di+1
!
with probability at least 1 0 as before by Theorem C.3. By setting 0 = /(16|G|`2) and noting that di dij , the conclusion holds for layer i + 1  ij on G with probability at least 1 /(16`2). By induction and the union bound, we get:
8i 2 {ij + 1, . . . , ij 1 1}, ey 2 G : k efi,ij (ey) efi,ij (ex)k  (C` log dmax)(i ij)/2 ·
s di
dij
· eR
8ey 2 G : k efij 1,ij (ey) efij 1,ij (ex)k  (C` log dmax) (ij 1 ij)/2 · eR
with probability at least 1 /(16`2). To extend to all y 2 fij (B(x, R)), we condition on the bound on kWik given by Lemma C.1 for all i  ij 1 and note that 8y 2 fij (B(x, R)), for ey = arg min
z2Gkz yk, and for ij + 1  i < ij 1, k efi,ij (ex) efi,ij (y)k  k efi,ij (ex) efi,ij (ey)k + k efi,ij (y) efi,ij (ey)k
 k efi,ij (ex) efi,ij (ey)k + ky eyk iY
k=ij+1
kWkk
 k efi,ij (ex) efi,ij (ey)k + " iY
k=ij+1
C
s dk
dk 1
!
= k efi,ij (ex) efi,ij (ey)k + "Ci ij s di
dij
,
using that di dij . Similarly, for i = ij 1, we have
k efij 1,ij (ex) efij 1,ij (y)k  k efij 1,ij (ex) efij 1,ij (ey)k + "Cij 1 ij s dij 1 1
dij
.
Our setting of " concludes the proof of the claim.
An inductive application of Claim 2.4, a union bound and the observation that: kfi(x) fi(y)k  k efi(x) efi(y)k
concludes the proof of the lemma.
The following lemma shows that few neurons have inputs of small magnitude for network input x. Lemma 2.5. With probability at least 1 , for all i 2 [`], we have:
# ⇢ j : |h(Wi+1)j , fi(x)i| ↵i
kfi(x)kp di
1 2 r 2
⇡ ↵i
! di+1.
Proof. Follows from the fact that Pr(|Z|  c)  c p
2/⇡ for Z ⇠ N(0, 1), plus a simple application of Hoeffding’s Inequality.

heading: 2.4 Proving Local Gradient Smoothness
text: In this section, we show that the gradient is locally constant, and thus complete the proof of Theorem 1.1. In our proof, we will bound each of the terms in the expansion of the gradient differences (GD-DECOMP). First, we prove a structural lemma on the spectral norm of the matrices appearing in the right-hand-side of (GD-DECOMP), allowing us to ignore the portion of the network till the last-encountered bottleneck layer. Define, for all i > j, Mi,j(y) = Q j+1 k=i Dk(
efk(y))Wk. Lemma 2.6. With probability at least 1 over the {Wk}, we have: 8ky xk  R, j 2 [m 1] : P{D1(·),...,D`(·)} n Mij ,ij+1(y)  (C · ` · log dmax)(ij ij+1)/2 o = 1,
where the probability is taken with respect to the random choices in the definition of the Dk(·).
We provide the first part of the proof in full as the simplest application of ideas that find further application in the subsequent result establishing bounds on terms in (GD-DECOMP); see Appendix A.3.
Proof Sketch. To start, consider a fixed j 2 [m] and condition on the conclusion of Lemma 2.3 up to level ij+1. Now, consider an "-net of fij+1(B(x, R)), G, with resolution " = 1/(d`max)32. As before, |G|  (Cdmax)48`dij+1 for some constant C. We additionally will consider subsets
S = n
(Sk) ij+1+1 k=ij 1 : Sk ✓ [dk], |Sk|  4dij+1
o .
Note that |G| · |S|2  (dmax)64ldij+1 . For y 2 G, S1, S2 2 S , consider the following matrix:
M ij ,ij+1
y,S1,S2 =
ij+1+1Y
k=ij
(Dk( efk,ij+1(y)))+(DS1k DS2k))Wk where (DS)i,j = ( 1, if i = j and i 2 S, 0, otherwise.
We will bound the spectral norm of M ij ,ij+1 y,S1,S2 . First, note that:
M ij ,ij+1 y,S1,S2  2 fM ij ,ij+1 y,S1,S2 where fM ij ,ij+1 y,S1,S2 := Wij
ij+1+1Y k=ij 1 (Dk( efk,ij+1(y)) + (DS1k DS2k))Wk
and observe that from Lemma 2.1:
fM ij ,ij+1 y,S1,S2 d = Wij
ij+1+1Y k=ij 1 (Dk + (DS1k DS2k))Wk) where (Dk)i,j = ( 1 w.p 12 if i = j, 0 otherwise.
To bound the spectral norm, let B be a 1/3-net of Sdij 1 and v 2 B. Applying Theorem C.3,
v>fM ij ,ij+1 y,S1,S2  v > Wij
ij+1+2Y k=ij 1 (Dk + (DS1k DS2k))Wk) · 1 +
s log 1/ 0
dij+1
!
 ij+1Y
k=ij
0
@1 +
s log 1/ 0
dk
1
A
with probability at least ` 0. But setting 0 = /(16`4 · |G| · |S|2) yields with probability at least 1 /16:
8y 2 G, S1, S2 2 S : fM ij ,ij+1
y,S1,S2
 (C · ` · log dmax)(ij ij+1)/2.
On the event in the conclusion of Lemma 2.3, we have that fi(y) 6= 0 for all i 2 [`], y 2 G and therefore, we have by a union bound over the discrete set G:
8y 2 G, k 2 {ij+1, . . . , ij} , m 2 [dk] : ( efk,ij (y))m 6= 0 proving the lemma for y 2 G as the activations are deterministic. For y /2 G, the following claim concludes the proof of the lemma. The claim is essentially a generalization of [BCGdC21, Eq. (18)] and its proof is deferred to the appendix.
Claim 2.7. With probability at least 1 0/`2 over the {Wk}, we have for all m 2 {ij+1+1, . . . , ij} and y 2 fij+1(B(x, R)):
P{Dk( efk,ij+1 (y)),Dk( efk,ij+1 (ey))} n Tr|Dm( efm,ij+1(y)) Dm( efm,ij+1(ey))|  4dij+1 o = 1
where ey = arg min z2Gkz yk, and the probability is taken with respect to the random choices in the definition of the Dk(·).
The previous claim along with our previously established bounds establish the lemma.
Our final technical result establishes the near-linearity of f in a ball around x. 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 {Wk}:
8kx yk  R, j 2 [`] : P{Dk( efk(x)),Dk( efk(y))}
⇢ krf(x) rf(y)k  ✓ C `
log` dmax
◆ = 1,
where the probability is taken with respect to the random choices in the definition of the Dk(·).
Proof Sketch. Consider a fixed term from (GD-DECOMP); that is, consider:
Di↵j(y) := W`+1
j+1Y
i=`
Di( efi(x))Wi ! · (Dj( efj(y)) Dj( efj(x)))Wj ·
0 @ 1Y
i=j 1 Di( efi(y))Wi
1
A .
We will show with high probability that Di↵j(y) is small for all y 2 B(x, R). This will then imply the lemma by a union bound and (GD-DECOMP). Let k be such that ik = arg minm<j dm. We will condition on the weights of the network up to layer ik. Specifically, we will assume the conclusions of Lemmas 2.3 and 2.6 up to layer ik. We may now focus our attention solely on the segment of the network beyond layer ik as a consequence of the following observation and Lemma 2.6:
kDi↵j(y)k  kDi↵j,k(x, y)k · kMik,0(y)k where (3)
Di↵j,k(x, y) := W`+1
j+1Y
i=`
Di( efi(x))Wi ! (Dj( efj(y)) Dj( efj(x)))Wj
0 @ ik+1Y
i=j 1 Di( efi(y))Wi
1
A
We will show for all y such that ky xk  R:
P{Dm( efm(x)),Dm( efm(y))}
⇢ kDi↵j,k(x, y)k
C `
(` log dmax)3`
= 0
with probability at least 1 /(16`2).
We have from Lemma 2.1 that the random vector H defined below is spherically symmetric and satisfies kHk  2` with probability at least 1 /(16`4):
W`+1
j+1Y
i=`
Di( efi(x))Wi d = fW`+1
j+1Y
i=`
Di fWi =: H.
As in the proof of Lemma 2.6, let G be an "-net of fik(B(x, R)) with " as in the proof of Lemma 2.6. We now break into two cases depending on how dj compares to dik and handle them separately. At this point, we have effectively reduced the multi-layer proof to the problem of analyzing deviations of activations at a fixed layer. For the remaining proof, we generalize approaches in [DS20] for the small width case and [BCGdC21] for the large width case.
Case 1: dj  dik(` log dmax)20`. 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 dj/poly(` log dmax)` between y 2 B(x, R) and x. Since, H is spherically distributed, kH(Dj( efj(x)) Dj( efj(y)))k is very small and consequently the whole term is small.
Case 2: dj dik(` log dmax)20`. This case is analogous to [BCGdC21]. The proof is technically involved and requires careful analysis of the random vector H(Dj( efj(x)) Dj( efj(y)))Wj , which is complicated in our setting due to the matrices preceeding it in (GD-DECOMP). It involves the distributional equivalence in Lemma 2.1.
A union bound and an application of the triangle inequality now imply the lemma.
Proof of Theorem 1.1. On the intersection of the events in the conclusions of Lemmas 2.2, 2.3 and 2.8, we have that rf(x) is deterministic and furthermore, we have:
krf(x)k 1 2`+1
, |f(x)|  c2` p log 1/
8y s.t ky xk  R : krf(x) rf(y)k  1 (` log dmax)` = o(1).
Assume f(x) > 0 (the alternative is similar) and let ⌘ = 2 ` log d·
p log 1/
krf(x)k2 , we have for the point x + ⌘rf(x), defining the function g(t) = f(x + t⌘rf(x)):
f(x + ⌘rf(x)) = f(x) + Z 1
0 g 0(t)dt = f(x) +
Z 1
0 (⌘rf(x))>rf(x + t⌘rf(x))dt
= f(x) (1 o(1))2` log d p log 1/  f(x).
Our lower bounds on rf(x) ensure k⌘rf(x)k  R, concluding the proof of the theorem.

heading: 3 The Impact of Depth
text: 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 an example of a sufficiently deep network for which, with high probability, the output of the network will have the same sign for all input patterns. Theorem 3.1. Fix a sufficiently large d 2 N, an ` d3 and (`d)20  k  exp( p
`), and consider the randomly initialized neural network (NN-DEF) with d1 = · · · = d` = k. There is a universal constant C such that with probability at least 0.9,
8x, y 2 Sd 1 : |f(x) f(y)||f(x)|  C r log d d .
The proof involves showing that the image of Sd 1 is bounded away from 0, and that the inner products between images of two input vectors throughout the network converge. The following lemma shows how the expected inner products evolve through the network. The lemma follows from computing a double integral; see [CS09, Eq. (6)]. The proof of Theorem 3.1 is in Appendix B.
Lemma 3.2. Let d 2 N. Fix x, y 2 Rd with x, y 6= 0. Then for g s N (0, I):
E ⇥ max g > x, 0 max g > y, 0 ⇤
p E(max {g>x, 0})2 · E(max {g>y, 0})2
= sin ✓
⇡ +
✓ 1 ✓
⇡
◆ cos ✓
where ✓ = arccos(x>y/(kxkkyk)).

heading: 4 Disclosure of Funding and Competing Interests
text: PB and YC gratefully acknowledge the support of the NSF through grants DMS-2023505 and DMS2031883, the Simons Foundation through award #814639, and Microsoft through the BAIR Open Research Commons. We declare no competing interests.

Review summaries:
EDIT: I will be keeping my (positive) score.  The 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.  The 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:  the 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 x, there is a relatively large ball around x where f satisfies this smoothness property.   The 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$.  The 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.  For 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.    

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.

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.

This paper studies some adversarial examples in random ReLu networks, where a smaller perturbation generates a negative label.  The 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.