Year: 2019

Abstract:
It has been noted in existing literature that over-parameterization in ReLU networks generally improves performance. While there could be several factors involved behind this, we prove some desirable theoretical properties at initialization which may be enjoyed by ReLU networks. Specifically, it is known that He initialization in deep ReLU networks asymptotically preserves variance of activations in the forward pass and variance of gradients in the backward pass for infinitely wide networks, thus preserving the flow of information in both directions. Our paper goes beyond these results and shows novel properties that hold under He initialization: i) the norm of hidden activation of each layer is equal to the norm of the input, and, ii) the norm of weight gradient of each layer is equal to the product of norm of the input vector and the error at output layer. These results are derived using the PAC analysis framework, and hold true for finitely sized datasets such that the width of the ReLU network only needs to be larger than a certain finite lower bound. As we show, this lower bound depends on the depth of the network and the number of samples, and by the virtue of being a lower bound, over-parameterized ReLU networks are endowed with these desirable properties. For the aforementioned hidden activation norm property under He initialization, we further extend our theory and show that this property holds for a finite width network even when the number of data samples is infinite. Thus we overcome several limitations of existing papers, and show new properties of deep ReLU networks at initialization.

heading: 1 INTRODUCTION
text: Deep rectifier (ReLU) networks are popular in deep learning due to their ease of training and stateof-the-art generalization. This success of deep rectifier networks can be partly attributed to good initialization strategies (for example Glorot & Bengio (2010); He et al. (2015)). Essentially, good parameter initializations guarantee that there is no exploding or vanishing of information across hidden layers. These properties help gradient descent based optimization methods in navigating the complex non-linear loss landscape of deep networks by initializing them at a good starting point where training can begin. Such favorable properties promised by these initialization strategies are (in most cases) shown to hold true in asymptotic settings where the network width tends to infinity and/or under strict assumptions made about the distribution of the input data. A detailed account of these existing papers and a contrast between these papers and our work is discussed in section 2.
Our paper relaxes the aforementioned assumptions made in previous papers. Further, we show novel properties that hold for deep ReLU networks at initialization when using the He initialization scheme (He et al., 2015). Specifically, we show that deep ReLU networks obey the following properties in the forward (Eq. 1) back backward (Eq. 2) pass (see section 3 for notations),
‖hl‖2 ≈ ‖x‖2 ∀l ∈ {1, 2, · · · , L} (1)
‖∂`(fθ(x),y) ∂Wl ‖F ≈ ‖δ(x,y)‖2 · ‖x‖2 ∀l ∈ {1, 2, · · · , L} (2)
We refer to the above properties as as the the activation norm equality and the gradient norm equality property.
Further, we derive a finite lower bound on the width of the hidden layers for which the above results hold (i.e., the network needs to be sufficiently over-parameterized) in contrast to a number of previous papers that assume infinitely wide layers.
We do not make any assumption on the data distribution as done in a number of previous papers that study initialization. Further, our results hold for an infinite stream of data for the activation norm equality property and for any finite dataset in the backward pass.
Thus we have relaxed a number of assumptions made in previous research work that focus on deriving initialization strategies for deep ReLU networks. Our results showing the connection between activation norm and input norm (and similarly the property for gradients) for deep ReLU networks can be utilized in further research studies.

heading: 2 RELATION WITH EXISTING WORK
text: The seminal work of Glorot & Bengio (2010) studied for the first time a principled way to initialize deep networks to avoid exploding/vanishing gradient problem (EVGP). Their analysis however is done for deep linear networks. The analysis by He et al. (2015) follows the derivation strategy of Glorot & Bengio (2010) except they tailor their derivation for deep ReLU networks. However, both these papers make a strong assumption that the dimensions of the input are statistically independent and that the network width is infinite. Our results do not make these assumptions.
Saxe et al. (2013) introduce the notion of dynamical isometry which is achieved when all the singular values of the input-output Jacobian of the network is 1. They show that deep linear networks achieve dynamical isometry when initialized using orthogonal weights and this property allows fast learning in such networks.
Poole et al. (2016) study how the norm of hidden activations evolve when propagating an input through the network. Pennington et al. (2017; 2018) study the exploding and vanishing gradient problem in deep ReLU networks using tools from free probability theory. Under the assumption of an infinitely wide network, they show that the average squared singular value of the input-output Jacobian for deep ReLU network is 1 when initialized appropriately. Our paper on the other hand shows that deep ReLU networks are norm preserving maps at appropriate initialization. Further, we show there exists a finite lower bound on the width of the network for which the Frobenius norm of the hidden layer-output Jacobian (equivalently the sum of its squared singular values) are equal across all hidden layers.
Hanin & Rolnick (2018) show that for a fixed input, the variance of the squared norm of hidden layer activations are bounded from above and below for deep ReLU networks to be near the squared norm of the input such that the bound depends on the sum of reciprocal of layer widths of the network. Our paper shows a similar result in a PAC bound sense but as an important difference, we show that these results hold even for an infinite stream of data by making the bound depend on the dimensionality of the input.
Hanin (2018) show that sufficiently wide deep ReLU networks with appropriately initialized weights prevent EVGP in the sense that the fluctuation between the elements of the input-output Jacobian matrix of the network is small. This avoids EVGP because a large fluctuation between the elements of the input-output Jacobian implies a large variation in its singular values. Our paper shows that sufficiently wide deep ReLU networks avoid EVGP in the sense that the norm of the gradient for the weights of each layer is roughly equal to a fixed quantity that depends on the input and target.
Over-parameterization in deep networks has previously been shown to have advantages. Neyshabur et al. (2014); Arpit et al. (2017) show empirically that wider networks train faster (number of epochs) and have better generalization performance. From a theoretical view point, Neyshabur et al. (2018) derive a generalization bound for a two layer ReLU network where they show that a wider network has a lower complexity. Lee et al. (2017) show that infinitely wide deep networks act as a Gaussian process. Arora et al. (2018) show that over-parameterization in deep linear networks acts as a conditioning on the gradient leading to faster convergence, although in this case overparameterization in terms of depth is studied. Our analysis complements this line of work by showing another advantage of over-parameterization in deep ReLU networks.

heading: 3 THEORETICAL RESULTS
text: Let D = {xi,yi}Ni=1 be N training sample pairs of inputs vectors xi ∈ Rno and target vectors yKi where xi’s are sampled from a distribution with support X . Define a L layer deep ReLU network fθ(x) = h L with the lth hidden layer’s activation given by,
hl := ReLU(al)
al := Wlhl−1 + bl l ∈ {1, 2, · · ·L} (3)
where hl ∈ Rnl are the hidden activations, ho is the input to the network and can be one of the input vectors xi, Wl ∈ Rnl×nl−1 are the weight matrices, b ∈ Rnl are the bias vectors which are initialized as 0s, al are the pre-activations and θ = {(Wl,bl)}Ll=1. Define a loss on the deep network function for any given training data sample (x,y) as,
`(fθ(x),y) (4)
where `(.) is any desired loss function. For instance, `(.) can be log loss for a classification problem, in which case fθ(x) is transformed using a weight matrix to have dimensions equal to the number of classes and the softmax activation is applied to yield class probabilities (i.e., a logistic regression like model on top of fθ(x)). However for our purpose, we do not need to restrict `(.) to a specific choice, we only need it to be differentiable. We will make use of the notation,
δ(x,y) := ∂`(fθ(x),y)
∂aL (5)
We organize our theoretical results as follows. We first derive the activation norm equality property for finite datasets and then extend these results to infinite dataset setting in section 3.1. We then derive the gradient norm equality property for finite datasets in section 3.2. All formal proofs, if not shown in the main text, are available in the appendix.

heading: 3.1 ACTIVATION NORM EQUALITY
text: Consider an L layer deep ReLU network and data x ∈ X . We show in this section that the norm of hidden layer activation of any layer is roughly equal to the norm of the input at initialization for all x ∈ X if the network weights are initialized appropriately and the network width is sufficiently large but finite. Specifically we show ∀l ∈ [L] and x ∈ X ,
‖hl‖2 ≈ ‖x‖2 (6)
To achieve this goal, we start with a very simple result– in expectation, ReLU transformation in each layer preserves the norm of its corresponding input if the weights are sampled appropriately. Evaluating this expectation also helps determining the scale of the random initialization that leads to norm preservation.
Lemma 1 Let v = ReLU (Ru), where u ∈ Rn, R ∈ Rm×n. If Rij i.i.d.∼ N (0, 2m ), then for any fixed vector u, E[‖v‖2] = ‖u‖2.
The proof for the above lemma involves simply computing the expectation analytically by exploting the fact that each dimension of the vector u is a weighted sum of Gaussian random variables. The above result thus shows that for each layer, initializing its weights from an i.i.d. Gaussian distribution with 0 mean and 2/fan-out variance (viz. He initialization (He et al., 2015)) preserves the norm of its input in expectation. We now derive a lower bound on the width of a ReLU layer so that it can preserve the norm of the input for a single fixed input with error margin.
Lemma 2 Let v = ReLU (Ru), where u ∈ Rn, R ∈ Rm×n. If Rij i.i.d.∼ N (0, 2m ), and ∈ [0, 1), then for any fixed vector u,
Pr ( |‖v‖2 − ‖u‖2| ≤ ‖u‖2 ) ≥ 1− 2 exp ( −m (
4 + log
2
1 + √ 1 +
)) (7)
The proof of this lemma involves a direct application of the Chernoff bounding technique. Now we use the above lemma to show that the norm of hidden activations equal the norm of inputs within a specified margin and for a finite size dataset for a deep ReLU network.
Theorem 1 Let D be a fixed dataset with N samples and define a L layer ReLU network fθ(.) as shown in Eq. 3 such that each weight matrix Wl ∈ Rnl×nl−1 has its elements sampled as W lij i.i.d.∼ N (0, 2nl ) and biases b l are set to zeros. Then for any sample (x,y) ∈ D and ∈ [0, 1), we have that,
Pr ( (1− )L‖x‖2 ≤ ‖fθ(x)‖2 ≤ (1 + )L‖x‖2 ) ≥ 1−
L∑ l′=1 2N exp ( −nl′ ( 4 + log
2
1 + √ 1 +
)) (8)
While the statement of the above theorem only talks about the norm of the final output of the network, it equally applies to any hidden layer l as well since the theorem can be applied equivalently to a l layer network.
Having proved the activation norm equality property in the finite dataset setting above, we now turn our attention to the case of infinite dataset case. To do so, we first prove a non-trivial result where we use lemma 2 to show how a lower bound on the width of an individual ReLU layer can be computed such that this layer preserves the norm of an infinite stream of inputs.
Lemma 3 Let X be a d ≤ n dimensional subspace of Rn and R ∈ Rm×n. If Rij i.i.d.∼ N (0, 2m ),
∈ [0, 1), and,
m ≥ 1 /12− log(0.5(1 + √ 1 + /3))
· ( d log 2
∆ + log
4
δ
) (9)
then with probability at least 1− δ,
(1− )‖u‖2 ≤ ‖ReLU(Ru)‖2 ≤ (1 + )‖u‖2 ∀u ∈ X (10)
where ∆ := min{ 3 √ d , √ √ 3d }.
Proof Sketch: The core idea behind the proof is inspired by lemma 10 of Sarlos (2006). Without any loss of generality, we will show the norm preserving property for any unit vector u in the d dimensional subspace X of Rn. This is because for any arbitrary length vector u, ‖ReLU(Ru)‖ = ‖u‖ · ‖ReLU(Rû)‖. The idea then is to define a grid of finite points over X on [−1, 1]d with interval size depending on , such that every unit vector û in X is close enough to one of the grid points. Then, if we choose the width of the layer to be large enough to approximately preserve the length of the finite number of grid points, we can guarantee that the length of any arbitrary unit vector approximately remains preserved as well within the derived margin of error. The formal proof can be found in the appendix.
We now extend the above lemma to a deep ReLU network and show our main result for the forward pass that the norm of hidden activations equal the norm of input within some distortion margin, for an infinite stream of input data for a sufficiently large (but finite) width deep ReLU network.
Theorem 2 Define a L layer ReLU network fθ(.) as shown in Eq. 3 such that each weight matrix Wl ∈ Rnl×nl−1 has its elements sampled as W lij i.i.d.∼ N (0, 2nl ) and biases b l are set to zeros. Let X be a d ≤ n dimensional subspace of Rn. If W lij i.i.d.∼ N (0, 2nl ), ∈ [0, 1), and,
nl ≥ 1 /12− log(0.5(1 + √ 1 + /3)) · ( d log 2 ∆ + log 4L δ ) ∀l ∈ [L] (11)
then with probability at least 1− δ,
(1− )l‖x‖2 ≤ ‖hl‖2 ≤ (1 + )l‖x‖2 ∀x ∈ X ∀l ∈ [L] (12)
Proof: Since the input lies on a d dimensional subspace of Rn, we apply theorem 3 to the first layer and get the guarantee that the norm of all inputs on the d dimensional subspace are preserved by this layer. Next, we show that since each layer is a linear transform followed by pointwise ReLU non-linearity, and the input takes values in a set defined by the d dimensional subspace of Rn, the output of the first layer will take values in a set that is strictly a subset of a d dimensional subspace. To see this, let B ∈ Rn×d denote a matrix with orthonormal columns describing the basis of the subspace X on which the input lies, and let z ∈ Rd. Then we have that,
x ∈ {Bz|z ∈ Rd} (13)
The first layer transforms any input x as h1 = ReLU(W0x) (14)
= ReLU(W0Bz) (15) Denote B′ = W0B. Then note that rank(B′) ≤ d. Let S1 denote the set of values that h1 can take. Then we have that,
S1 = {B′z|z ∈ Rd} ∩ Rn + 1 (16)
where Rn+ denote the subset of Rn where all dimensions take non-negative values. This shows that h1 takes values in a set that is strictly a subset of a d dimensional subspace of Rn1 .
Having proved this for first layer, we can recursively apply this strategy to all higher layers since the output of each layer lies on a subset of a subspace. Notice that while doing so, the lower bound on the width of each layer depends only on the subspace dimensionality d. Applying union bound over the result of theorem 3 for L layers proves the claim.
We note that the lower bound on width derived above depends on two quantities– the depth of the network L, and the dimensionality of the subspace d on which the input lies. Specifically, the lower bound on the width becomes larger for larger input dimensionality d and larger network depth L irrespective of the number of data samples, meaning that a wider network is needed as the depth of the network and/or the intrinsic input dimensionality increases.

heading: 3.2 GRADIENT NORM EQUALITY
text: Consider any given loss function `(.) and a data sample (x,y), we show in this section that the norm of gradient for the parameter Wl of the lth layer depends only on the input and output. Specifically, for a wide enough network, the following holds at initialization for all l ∈ {1, 2, . . . , L} and ∀x ∈ D,
‖∂`(fθ(x),y) ∂Wl ‖F ≈ ‖δ(x,y)‖2 · ‖x‖2 ∀l (17)
As a first step, we note that the gradient for a parameter Wl for a sample (x,y) is given, ∂`(fθ(x),y)
∂Wl = diag
( ∂`(fθ(x),y)
∂al
) · Mnl(hl−1) (18)
whereMnl(hl−1) is a matrix of size nl × nl−1 such that each row is the vector hl−1. Therefore, a simple algebraic manipulation shows that,
‖∂`(fθ(x),y) ∂Wl ‖F = ‖ ∂`(fθ(x),y) ∂al ‖2 · ‖hl−1‖2 (19)
In the previous section, we showed that for a sufficiently wide network, ‖hl‖2 ≈ ‖x‖2 ∀l with high probability. To show that gradient norms of parameters are preserved in the sense shown in Eq. (17), we essentially show that ‖∂`(fθ(x),y)
∂al ‖2 ≈ ‖δ(x,y)‖2 ∀l with high probability for sufficiently wide
networks.
Note that ‖∂`(fθ(x),y) ∂aL ‖2 = ‖δ(x,y)‖2 by definition. To show the norm is preserved for all layers, we begin by noting that,
∂`(fθ(x),y) ∂al = ∂hl ∂al
( ∂al+1
∂hl
T ∂`(fθ(x),y)
∂al+1
)
= 1(al) ( Wl+1 T ∂`(fθ(x),y)
∂al+1
) (20)
where is the point-wise product (or Hadamard product) and 1(.) is the heaviside step function. The following proposition shows that 1(.) follows a Bernoulli distribution w.r.t. the weights given any fixed input at the previous layer.
Proposition 1 If network weights are sampled i.i.d. from a Gaussian distribution with mean 0 and biases are 0 at initialization, then conditioned on hl−1, each dimension of 1(al) follows an i.i.d. Bernoulli distribution with probability 0.5 at initialization.
Given this property of 1(al), we show below that the transformation of type shown in Eq. (20) is norm preserving in expectation.
Lemma 4 Let v = (Ru) z, where u ∈ Rn, R ∈ Rm×n and z ∈ Rm. If Rij i.i.d.∼ N (0, 1pm ) and zi i.i.d.∼ Bernoulli(p), then for any fixed vector u, E[‖v‖2] = ‖u‖2.
The proof of this lemma involves analytically computing the expectation of the vector norm by exploiting the fact that each dimension of v is a sum of Gaussian random variables multiplied to an independent Bernoulli random variable. This lemma reveals the variance of the 0 mean Gaussian distribution from which the weights must be sampled in order for the vector norm to be preserved in expectation. Since 1(al) is sampled from a 0.5 probability Bernoulli, we have that the weights must be sampled from a Gaussian with variance 2/m. We now show this property holds for a finite width network.
Lemma 5 Let v = (Ru) z, where u ∈ Rn, z ∈ Rm, and R ∈ Rm×n. If Rij i.i.d.∼ N (0, 10.5m ), zi i.i.d.∼ Bernoulli(0.5) and ∈ [0, 1), then for any fixed vector u,
Pr ( |‖v‖2 − ‖u‖2| ≤ ‖u‖2 ) ≥ 1− 2 exp ( −m (
4 + log
2
1 + √ 1 +
)) (21)
The proof of this lemma involves a direct application of the Chernoff bounding technique. Having shown that a finite width ReLU layer can preserve gradient norm, we now note that we need to apply this result to Eq. (20). In this case, we must substitute the matrix R in the above lemma with the network’s weight matrix Wl+1 T
. In the previous subsection, we showed that each element of the matrix Wl+1 must be sampled from N (0, 2/nl+1) in order for the norm of the input vector to be preserved. However, in order for the Jacobian norm to be preserved, we require Wl+1 to be sampled from N (0, 2/nl) as per the above lemma. This suggests that if we want the norms to be preserved in the forward and backward pass for a single layer simultaneously, it is beneficial for the width of the network to be close to uniform. The reason we want them to simultaneously hold is because as shown in Eq. (19), in order for the parameter gradient norm to be same for all layers, we need the norm of both the Jacobian ‖∂`(fθ(x),y)
∂al ‖2 as well as the hidden activation ‖hl−1‖2 to be preserved throughout
the hidden layers. Therefore, assuming the network has a uniform width, we now prove that in deep ReLU networks with He initialization, the norm of weight gradient for each layer is simply a product of norm of the input and norm of the error at output.
Theorem 3 1 Let D be a fixed dataset with N samples and define a L layer ReLU network as shown in Eq. 3 such that each weight matrix Wl ∈ Rn×n has its elements sampled asW lij
i.i.d.∼ N (0, 2n ) and biases bl are set to zeros. Then for any sample (x,y) ∈ D, ∈ [0, 1), and for all l ∈ {1, 2, . . . , L} with probability at least,
1− 4NL exp ( −n (
4 + log
2
1 + √ 1 +
)) (22)
the following hold true,
(1− )L‖x‖2 · ‖δ(x,y)‖2 ≤ ‖∂`(fθ(x),y) ∂Wl ‖2
≤ (1 + )L‖x‖2 · ‖δ(x,y)‖2 (23) 1Similar to He et al. (2016), we have assumed that ∂`(fθ(x),y)
∂al+1 in independent from 1(al) and Wl+1 at
initialization.
and
(1− )l‖x‖2 ≤ ‖hl‖2 ≤ (1 + )l‖x‖2 (24)
We note that even though the theorem relies on the specified independence assumption similar to He et al. (2016), we show that our predictions hold in practice in the next section.

heading: 4 EMPIRICAL VERIFICATION

heading: 4.1 NORM PRESERVATION OF ACTIVATION AND GRADIENTS
text: In this section, we verify the hidden activations have the same norm as input norm ‖h i‖2 ‖x‖2 ≈ 1 (Eq. 6), and the parameter gradient norm approximately equal the product of input norm and output error norm ‖ ∂`(fθ(x),y) ∂Wi ‖F
‖δ(x,y)‖2·‖x‖2 ≈ 1 (Eq. 17) for all layer indices i for sufficiently wide deep ReLU networks. For this experiment we choose a 10 layer network with 2000 randomly generated input samples in R500 and randomly generated target labels in R20 and cross-entropy loss. We add a linear layer along with softmax activation to the ReLU network’s outputs to make the final output in R20. We use network width from the set {100, 500, 2000, 4060}. We show results for both He initialization (He et al., 2015) which we theoretically show is optimal, as well as Glorot initialization (Glorot & Bengio, 2010) which is not optimal for deep ReLU nets. As can be seen in figure 1 (left), the mean ratio of hidden activation norm to the input norm over the dataset is roughly 1 with a small standard deviation for He initializaiton. This approximation becomes better with larger width. On the other hand, Glorot initialization fails at preserving activation norm for deep ReLU nets. A similar result can be seen for parameter gradients norms (figure 1 (right)). In the figure we denote ∂`(fθ(x),y)∂Wi by ∂Wi. Here we find for He initialization that the norm of weight gradient for each layer is roughly equal to the product of norm of input and norm of error at output, and this approximation becomes stronger for wider networks. Once again Glorot initialization does not have this property.

heading: 4.2 TIGHTNESS OF BOUND
text: In the following experiment we verify the tightness of the bound in lemma 2 (for forward pass) and lemma 5 (for backward pass). To do so, we vary the network width of a one hidden layer ReLU transformation from 500 to 4000, and feed 2000 randomly sampled inputs x through it. For each sample we measure the distortion defined as,
:= ∣∣∣∣1− ‖h‖‖x‖ ∣∣∣∣ (25)
for the forward pass, and,
:= ∣∣∣∣1− ‖∂`(fθ(x),y)∂Wi ‖F‖δ(x,y)‖2 · ‖x‖2 ∣∣∣∣ (26)
for the backward pass. Here h is the output of the one hidden layer ReLU transformation. We compute the mean value of for the 2000 examples and plot them against the network width used. We call this the empirical estimate. We simultaneously plot the values of predicted by lemma 2 and lemma 5 for failure probability δ = 0.05. We call this the theoretical value. The plot for the forward pass is shown in figure 2 (left). As can be seen, our lower bound on width is an over-estimation but becomes tighter for smaller values of . A similar result can be seen for lemma 5 in figure 2 (right). Thus our proposed bounds can be improved and we leave that as future work.

heading: 4.3 EFFECT OF NON-UNIFORMITY OF WIDTH ON GRADIENT NORM EQUALITY
text: As discussed in section 3.2, gradient norm equality property holds more accurately when deep networks have a more uniform width throughout the layers. To verify this, we construct a 20 layer deep ReLU network such that the width of each layer is determined by independently sampling uniformly between 1000− v and 1000 + v, where v denotes the amount of width variation chosen for a particular experiment. Once the network architecture is fixed, we initialize the weights with He initialization. We then generate 1000 pairs of input samples and output error similar to the process described in section 4.1 and compute the ratio ‖ ∂`(fθ(x),y) ∂Wi ‖F
‖δ(x,y)‖2·‖x‖2 . The mean and standard deviation of this value across samples are shown in figure 3 for v ∈ {1, 200, 500}. It can be seen that the ratio is closer to 1 with smaller variance when width variation v is small, thus verifying our theoretical prediction.

heading: 5 CONCLUSION
text: We derived novel properties that are possessed by deep ReLU networks initialized with He initialization. Specifically, we show that the norm of hidden activations and the norm of weight gradients are a function of the norm of input data and error at output. While deriving these properties, we relaxed most of the assumptions (such as those on input distribution and width of network) made by previous work that study weight initialization in deep ReLU networks. Thus our work establishes that He initialization optimally preserves the flow of information in the forward and backward directions in a stronger setting, and uncovers novel properties.

heading: A PROOFS
text: A.1 PROOFS FOR FORWARD PASS
Lemma 1 Let v = ReLU (Ru), where u ∈ Rn and R ∈ Rm×n. If Rij i.i.d.∼ N (0, 2m ), then for any fixed vector u, E[‖v‖2] = ‖u‖2. Proof: Define ai = RTi u, where Ri denotes the ith row of R. Since each element Rij is an independent sample from Gaussian distribution, each ai is essentially a weighted sum of these independent random variables. Thus, each ai ∼ N ( 0, 2m‖u‖ 2 )
and independent from one another. Thus each element vi = ReLU(ai) ∼ NR ( 0, 2m‖u‖ 2 )
where NR denotes the rectified Normal distribution. Our goal is to compute,
E[‖v‖2] = E[ m∑ i=1 v2i ] (27)
= mE[v2i ] (28)
From the definition of vi,
E[vi] = 1 2 · 0 + 1 2 E[Z] (29)
where Z follows a half-Normal distribution corresponding to the Normal distributionN ( 0, 2m‖u‖ 2 ) .
Thus E[Z] = √
2‖u‖2 m · √ 2 π = 2 √ ‖u‖2 mπ . Similarly,
E[v2i ] = 0.5E[Z2] (30) = 0.5(var(Z) + E[Z]2) (31)
Since var(Z) = 2m‖u‖ 2(1− 2π ), we get,
E[v2i ] = 0.5
( 2
m ‖u‖2(1− 2 π ) + (2 √ ‖u‖2 mπ )2 ) (32)
= ‖u‖2
m (33)
Thus,
mE[v2i ] = ‖u‖2 (34)
which proves the claim.
Lemma 2 Let v = ReLU (Ru), where u ∈ Rn, R ∈ Rm×n. If Rij i.i.d.∼ N (0, 2m ), and ∈ [0, 1), then for any fixed vector u,
Pr ( |‖v‖2 − ‖u‖2| ≤ ‖u‖2 ) ≥ 1− 2 exp ( −m (
4 + log
2
1 + √ 1 +
)) (35)
Proof: Define ṽ = √
0.5m ‖u‖ v. Then we have that each element ṽi ∼ N R (0, 1) and independent from one another since vi = ReLU(ai) ∼ NR ( 0, 2m‖u‖ 2 )
where NR denotes the rectified Normal distribution. Thus to bound the probability of failure for the R.H.S.,
Pr ( ‖v‖2 ≥ (1 + )‖u‖2 ) = Pr
( ‖u‖2
0.5m ‖ṽ‖2 ≥ (1 + )‖u‖2
) (36)
= Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) (37)
Using Chernoff’s bound, we get for any λ > 0, Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) = Pr ( exp(λ‖ṽ‖2) ≥ exp(λ0.5m(1 + )) ) (38)
≤ E[exp(λ‖ṽ‖ 2)]
exp(0.5mλ(1 + )) (39)
= E[exp(
∑m i=1 λṽi 2)]
exp(0.5mλ(1 + )) (40)
= Πmi=1E[exp(λṽi 2)]
exp(0.5mλ(1 + )) (41)
=
( E[exp(λṽi2)]
exp(0.5λ(1 + ))
)m (42)
Denote p(ṽi) as the probability distribution of the rectified Normal random variable ṽi. Then, E[exp(λṽi2)] = ∫ ∞ −∞ exp(λṽi 2)p(ṽi) (43)
We know that the mass at vi = 0 is 0.5 and the density between vi = 0 and vi = ∞ follows the Normal distribution. Thus,
E[exp(λṽi2)] = 0.5 exp(0) + 1√ 2π ∫ ∞ 0 exp(λṽi 2 − ṽi2/2) (44)
= 0.5 + 1 2 √ (1− 2λ) √ 2√ π/(1− 2λ) ∫ ∞ 0 exp(− ṽi 2 2 (1− 2λ)) (45)
Note that ∫∞
0
√ 2√
π/(1−2λ)
∫∞ 0 exp(− ṽi 2
2 (1− 2λ)) is the integral of a half Normal distribution corresponding to the Normal distribution N (0, 1/(1− 2λ)). Thus,
E[exp(λṽi2)] = 0.5 + 1 2 √ (1− 2λ) (46)
Hence, we get,
Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) ≤ ( 0.5 ( 1 +
1√ (1− 2λ)
) exp(−0.5λ(1 + )) )m (47)
The above failure probability can be bounded to be smaller by finding an appropriate value of λ. We find that λ ≈ 0.5 1+ approximately minimizes the above bound. Substituting this value of λ above, we get,
Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) ≤ ( 0.5 ( 1 + √ 1 + )
exp(− 4
) )m
(48)
= exp ( −m (
4 + log
2
1 + √ 1 +
)) (49)
Thus,
Pr ( ‖v‖2 ≤ (1 + )‖u‖2 ) ≥ 1− exp ( −m (
4 + log
2
1 + √ 1 +
)) (50)
Similarly, to prove the L.H.S. by bounding the probability of failure from the other side, Pr ( ‖v‖2 ≤ (1− )‖u‖2 ) = Pr ( −‖v‖2 ≥ −(1− )‖u‖2 ) (51)
= Pr ( −‖u‖ 2
0.5m ‖ṽ‖2 ≥ −(1− )‖u‖2
) (52)
= Pr ( −‖ṽ‖2 ≥ −0.5m(1− ) ) (53)
Using Chernoff’s bound, we get for any λ > 0, Pr ( −‖ṽ‖2 ≥ −0.5m(1− ) ) = Pr ( exp(−λ‖ṽ‖2) ≥ exp(−λ0.5m(1− )) ) (54)
≤ E[exp(−λ‖ṽ‖ 2)]
exp(−0.5mλ(1− )) (55)
= E[exp(−
∑m i=1 λṽi 2)]
exp(−0.5mλ(1− )) (56)
= Πmi=1E[exp(−λṽi2)] exp(−0.5mλ(1− ))
(57)
=
( E[exp(−λṽi2)]
exp(−0.5λ(1− ))
)m (58)
Performing computations similar to those above to compute the expectation term, we get,
E[exp(−λṽi2)] = 0.5 + 1 2 √ (1 + 2λ) (59)
Hence, we get,
Pr ( ‖ṽ‖2 ≤ 0.5m(1− ) ) ≤ ( 0.5 ( 1 +
1√ (1 + 2λ)
) exp(0.5λ(1− )) )m (60)
Similar to the R.H.S. case, we find that λ ≈ 0.5 1− approximately minimizes the failure probability,
Pr ( ‖ṽ‖2 ≤ 0.5m(1− ) ) ≤ ( 0.5 ( 1 + √ 1− ) exp( 4 ) )m
(61)
= exp ( m (
4 − log 2 1 + √ 1−
)) (62)
It can be shown that,
exp ( m (
4 − log 2 1 + √ 1−
)) ≤ exp ( −m (
4 + log
2
1 + √ 1 +
)) (63)
Thus,
Pr ( ‖v‖2 ≥ (1− )‖u‖2 ) ≥ 1− exp ( −m (
4 + log
2
1 + √ 1 +
)) (64)
Using union bound, Eq. (50) and (64) hold together with probability,
Pr ( (1− )‖u‖2 ≤ ‖v‖2 ≤ (1 + )‖u‖2 ) ≥ 1− 2 exp ( −m (
4 + log
2
1 + √ 1 +
)) (65)
This proves the claim.
Theorem 1 LetD be a fixed dataset with N samples and define a L layer ReLU network as shown in Eq. 3 such that each weight matrix Wl ∈ Rnl×nl−1 has its elements sampled as W lij
i.i.d.∼ N (0, 2nl ) and biases bl are set to zeros. Then for any sample (x,y) ∈ D and ∈ [0, 1), we have that, Pr ( (1− )L‖x‖2 ≤ ‖fθ(x)‖2 ≤ (1 + )L‖x‖2 ) ≥ 1−
L∑ l′=1 2N exp ( −nl′ ( 4 + log
2
1 + √ 1 + )) (66)
Proof: When feed-forwarding a fixed input through the layers of a deep ReLU network, each hidden layer’s activation corresponding to the given input is also fixed because the network is
deterministic. Thus applying lemma 2, on each layer’s transformation, the following holds true for each l ∈ {1, 2, · · ·L},
Pr ( (1− )‖hl−1‖2 ≤ ‖hl‖2 ≤ (1 + )‖hl−1‖2 ) ≥ 1− 2 exp ( −nl (
4 + log
2
1 + √ 1 + )) (67)
Thus, using union bound, we have the lengths of all the layers until layer l are simultaneously preserved with probability at least,
1− l∑
l′=1
2 exp ( −nl′ (
4 + log
2
1 + √ 1 +
)) (68)
Applying union bound again, all the lengths until layer l are preserved simultaneously for N inputs with probability,
1− l∑
l′=1
2N exp ( −nl′ (
4 + log
2
1 + √ 1 +
)) (69)
Finally, we note that the following hold true with the above probability,
(1− )‖x‖2 ≤ ‖h1‖2 ≤ (1 + )‖x‖2 (70) (1− )‖h1‖2 ≤ ‖h2‖2 ≤ (1 + )‖h1‖2 (71)
Substituting ‖h1‖2 ≤ (1 + )‖x‖2 in the R.H.S. of the last equation, and (1− )‖x‖2 ≤ ‖h1‖2 in the L.H.S. of the last equation, we get,
(1− )2‖x‖2 ≤ ‖h2‖2 ≤ (1 + )2‖x‖2 (72)
Performing substitutions for higher layers similarly yields the claim.
Lemma 3 Let X be a d ≤ n dimensional subspace of Rn and R ∈ Rm×n. If Rij i.i.d.∼ N (0, 2m ),
∈ [0, 1), and,
m ≥ 1 /12− log(0.5(1 + √ 1 + /3))
· ( d log 2
∆ + log
4
δ
) (73)
then for all vectors u ∈ X , with probability at least 1− δ,∣∣∣‖ReLU(Ru)‖ − ‖u‖∣∣∣ ≤ ‖u‖ (74) where ∆ := min{
3 √ d , √ √ 3d }.
Proof: The core idea behind the proof is inspired by lemma 10 of Sarlos (2006). Without any loss of generality, we will show the norm preserving property for any unit vector u in the d dimensional subspace X of Rn. This is because for any arbitrary length vector u, ‖ReLU(Ru)‖ = ‖u‖ · ‖ReLU(Rû)‖. The idea then is to define a grid of finite points over X such that every unit vector û in X is close enough to one of the grid points. Then, if we choose the width of the layer to be large enough to approximately preserve the length of the finite number of grid points, we essentially guarantee that the length of any arbitrary vector approximately remains preserved. To this end, we define a grid G on [−1, 1]d with interval of size ∆ := min{ / √ d, √ /d}. Note the
number of points on this grid is (
2 ∆
)d . Also, let column vectors of B ∈ Rn×d be the orthonormal
basis of X . We now prove the R.H.S. of the bound in the claim. If we consider any unit vector û in X , we can find a point g on the grid G such that ‖g‖ ≤ 1, and it is closest to û in `2 norm, and define r′ := û− g. Thus the vector û can essentially be decomposed as,
û = g + r′ (75)
Also note that since r′ lies in the span of X , we can represent r′ := Br for some vector r.
Now consider the norm of the vector û after the ReLU transformation give by ‖ReLU(Rû)‖. Then we have,
‖ReLU(Rû)‖ = ‖ReLU(R(g + r′))‖ (76) ≤ ‖ReLU(Rg) +ReLU(Rr′))‖ (77) ≤ ‖ReLU(Rg)‖+ ‖ReLU(Rr′))‖ (78) ≤ ‖ReLU(Rg)‖+ ‖Rr′‖ (79)
Similarly, we have,
‖ReLU(Rg)‖ = ‖ReLU(R(g + û− û))‖ (80) ≤ ‖ReLU(Rû) +ReLU(R(g − û)))‖ (81) ≤ ‖ReLU(Rû)‖+ ‖ReLU(−Rr′))‖ (82) ≤ ‖ReLU(Rû)‖+ ‖Rr′‖ (83)
Therefore,
‖ReLU(Rg)‖ − ‖Rr′‖ ≤ ‖ReLU(Rû)‖ ≤ ‖ReLU(Rg)‖+ ‖Rr′‖ (84)
Applying union bound on all the points in G, from lemma 2, we know that with probability at least 1− ( 2 ∆ )d exp ( −m ( 4 + log 2 1+ √ 1+ )) ,
‖ReLU(Rg)‖2 ≤ (1 + )‖g‖2
≤ 1 + (85) ≤ (1 + )2 (86)
This can be substituted in the R.H.S. of Eq. (84). Now we only need to upper bound ‖Rr′‖. To this end, we rewrite ‖Rr′‖ = ‖RBr‖. Then,
‖RBr‖2 = d∑ i=1 d∑ j=1 < RBiri,RBjrj > (87)
≤ 2 d∑ i=1 d∑ j=1 |ri| · |rj |· < 1√ 2 RBi, 1√ 2 RBj > (88)
Note that 1√ 2 R is a matrix whose entries are sampled from N (0, 1). Invoking lemma 6 on the d2 terms in the above sum, we have that with probability at least 1− 2d2 exp ( −m4 ( 2 − 3 )) ,
2 d∑ i=1 d∑ j=1 |ri| · |rj |· < 1√ 2 RBi, 1√ 2 RBj > ≤ 2 d∑ i=1 d∑ j=1 |ri| · |rj | · (< Bi,Bj > + ) (89)
= 2 d∑ i=1 r2i ‖Bi‖2 + 2 d∑ i=1 d∑ j=1 |ri| · |rj | · (90)
= 2‖r‖2 + 2 ‖r‖21 (91)
Since r′, and hence r is a point inside one of the grid cells containing the origin, its length can be at most the length of the main diagonal of the grid cell. Formally, ‖r‖ ≤ √ d∆ ≤ , and ‖r‖1 ≤ d∆ ≤ √ . Subsituting these inequalities in the above equations, we get,
‖RBr‖2 ≤ 4 2 (92)
Looking back at the R.H.S. of Eq. (84), we have that with probability at least 1 −( 2 ∆ )d exp ( −m ( 4 + log 2 1+ √ 1+ )) − 2d2 exp ( −m4 ( 2 − 3 )) ,
‖ReLU(Rû)‖ ≤ 1 + + 2 (93) = 1 + 3 (94)
To prove the L.H.S. of the claimed bound, we can similarly find a point g on the grid G such that ‖g‖ ≥ 1, and it is closest to û in `2 norm, and define r′ := û− g. Then invoking lemma 2, we know that with probability at least 1− ( 2 ∆ )d exp ( −m ( 4 + log 2 1+ √ 1+ )) ,
‖ReLU(Rg)‖2 ≥ (1− )‖g‖2
≥ 1− (95) ≥ (1− )2 (96)
This can be substituted in the L.H.S. of Eq. (84). We then substitute the previously computed upper bound of ‖RBr‖2 once again and have that with probability at least 1 − 2 (
2 ∆
)d exp ( −m ( 4 + log 2 1+ √ 1+ )) − 2d2 exp ( −m4 ( 2 − 3 )) ,
1− 3 ≤ ‖ReLU(Rû)‖ ≤ 1 + 3 (97)
Scaling û arbitrarily, we equivalently have,
(1− 3 )‖u‖ ≤ ‖ReLU(Ru)‖ ≤ (1 + 3 )‖u‖ (98)
Finally, since,( 2
∆
)d exp ( −m (
4 + log
2
1 + √ 1 +
)) ≥ d2 exp ( −m
4
( 2 − 3 )) (99)
We can further lower bound the success probability of Eq. (98) for mathematical ease as,
1− 4 ( 2
∆
)d exp ( −m (
4 + log
2
1 + √ 1 +
)) (100)
Therefore to guarantee a success probability of at least 1− δ, we bound,
1− 4 ( 2
∆
)d exp ( −m (
4 + log
2
1 + √ 1 +
)) ≥ 1− δ (101)
Rearranging the terms in the equality to get a lower bound on m and rescaling proves the claim.
A.2 PROOFS FOR BACKWARD PASS
Proposition 1 If network weights are sampled i.i.d. from a Gaussian distribution with mean 0 and biases are 0 at initialization, then conditioned on hl−1, each dimension of 1(al) follows an i.i.d. Bernoulli distribution with probability 0.5 at initialization.
Proof: Note that al := Wlhl−1 at initialization (biases are 0) and Wl are sampled i.i.d. from a random distribution with mean 0. Therefore, each dimension ali is simply a weighted sum of i.i.d. zero mean Gaussian, which is also a 0 mean Gaussian random variable.
To prove the claim, note that the indicator operator applied on a random variable with 0 mean and symmetric distribution will have equal probability mass on both sides of 0, which is the same as a Bernoulli distributed random variable with probability 0.5. Finally, each dimension of al is i.i.d. simply because all the elements of Wl are sampled i.i.d., and hence each dimension of al is a weighted sum of a different set of i.i.d. random variables.
Lemma 4 Let v = (Ru) z, where u ∈ Rn, R ∈ Rm×n and z ∈ Rm. If Rij i.i.d.∼ N (0, 1pm ) and zi i.i.d.∼ Bernoulli(p), then for any fixed vector u, E[‖v‖2] = ‖u‖2.
Proof: Define ai = RTi u, where Ri denotes the ith row of R. Since each element Rij is an independent sample from Gaussian distribution, each ai is essentially a weighted sum of these independent random variables. Thus, each ai ∼ N ( 0, 1pm‖u‖ 2 ) and independent from one another.
Our goal is to compute,
E[‖v‖2] = m∑ i=1 E[(aizi)2] (102)
= m∑ i=1 E[a2i ]E[z2i ] (103)
= mE[a2i ]E[z2i ] (104) = mp(var(ai) + E[ai]2) (105) = ‖u‖2 (106)
which proves the claim.
Lemma 5 Let v = (Ru) z, where u ∈ Rn, z ∈ Rm, and R ∈ Rm×n. If Rij i.i.d.∼ N (0, 10.5m ), zi i.i.d.∼ Bernoulli(0.5) and ∈ [0, 1), then for any fixed vector u,
Pr ( |‖v‖2 − ‖u‖2| ≤ ‖u‖2 ) ≥ 1− 2 exp ( −m (
4 + log
2
1 + √ 1 +
)) (107)
Proof: Define ai = RTi u, where Ri denotes the ith row of R. Then, each ai ∼ N ( 0, 10.5m‖u‖ 2 ) and independent from one another. Define ã = √
0.5m ‖u‖ a. Then we have that each element ãi ∼ N (0, 1).
Define ṽ such that ṽi = ãizi. Thus to bound the probability of failure for the R.H.S., Pr ( ‖v‖2 ≥ (1 + )‖u‖2 ) = Pr
( ‖u‖2
0.5m ‖ṽ‖2 ≥ (1 + )‖u‖2
) (108)
= Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) (109)
Using Chernoff’s bound, we get for any λ > 0, Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) = Pr ( exp(λ‖ṽ‖2) ≥ exp(λ0.5m(1 + )) ) (110)
≤ E[exp(λ‖ṽ‖ 2)]
exp(0.5mλ(1 + )) (111)
= E[exp(
∑m i=1 λṽi 2)]
exp(0.5mλ(1 + )) (112)
= Πmi=1E[exp(λṽi 2)]
exp(0.5mλ(1 + )) (113)
=
( E[exp(λṽi2)]
exp(0.5λ(1 + ))
)m (114)
Denote p(ãi) and p(zi) as the probability distribution of the random variables ãi and zi respectively. Then,
E[exp(λṽi2)] = ∑ zi p(zi) ∫ ãi p(ãi) exp(λãi 2z2i ) (115)
Substituting p(ãi) with a standard Normal distribution, we get, E[exp(λṽi2)] = ∑ zi p(zi) ∫ ãi 1√ 2π exp(λãi 2z2i − ãi 2 2 ) (116)
= ∑ zi p(zi) ∫ ãi 1√ 2π exp(− ãi 2 2 (1− 2λz2i )) (117)
= ∑ zi p(zi) ∫ ãi 1√ 2π · √ 1− 2λz2i√ 1− 2λz2i exp(− ãi 2 2 (1− 2λz2i )) (118)
= ∑ zi p(zi) · 1√ 1− 2λz2i (119)
where the last equality holds because the integral of a Gaussian distribution over its domain is 1. Finally, summing over the Bernoulli random variable zi, we get,
E[exp(λṽi2)] = (1− 0.5) + 1√
1− 2λ (120)
Hence, we get,
Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) ≤ ( 0.5 ( 1 +
0.5√ (1− 2λ)
) exp(−0.5λ(1 + )) )m (121)
≤ ( 0.5 ( 1 +
1√ (1− 2λ)
) exp(−0.5λ(1 + )) )m (122)
We find that the above inequality is identical to that in Eq. (47). Thus λ ≈ 0.5 1+ approximately minimizes the above bound as before. Substituting this value of λ above, we get,
Pr ( ‖ṽ‖2 ≥ 0.5m(1 + ) ) ≤ ( 0.5 ( 1 + √ 1 + )
exp(− 4
) )m
(123)
= exp ( −m (
4 + log
2
1 + √ 1 +
)) (124)
Thus,
Pr ( ‖v‖2 ≤ (1 + )‖u‖2 ) ≥ 1− exp ( −m (
4 + log
2
1 + √ 1 +
)) (125)
Similarly, to prove the L.H.S. by bounding the probability of failure from the other side, Pr ( ‖v‖2 ≤ (1− )‖u‖2 ) = Pr ( −‖v‖2 ≥ −(1− )‖u‖2 ) (126)
= Pr ( −‖u‖ 2
0.5m ‖ṽ‖2 ≥ −(1− )‖u‖2
) (127)
= Pr ( −‖ṽ‖2 ≥ −0.5m(1− ) ) (128)
Using Chernoff’s bound, we get for any λ > 0, Pr ( −‖ṽ‖2 ≥ −0.5m(1− ) ) = Pr ( exp(−λ‖ṽ‖2) ≥ exp(−λ0.5m(1− )) ) (129)
≤ E[exp(−λ‖ṽ‖ 2)]
exp(−0.5mλ(1− )) (130)
= E[exp(−
∑m i=1 λṽi 2)]
exp(−0.5mλ(1− )) (131)
= Πmi=1E[exp(−λṽi2)] exp(−0.5mλ(1− ))
(132)
=
( E[exp(−λṽi2)]
exp(−0.5λ(1− ))
)m (133)
Performing computations similar to those above to compute the expectation term, we get,
E[exp(−λṽi2)] = 0.5 + 1√
(1 + 2λ) (134)
Hence, we get,
Pr ( ‖ṽ‖2 ≤ 0.5m(1− ) ) ≤ ( 0.5 ( 1 +
0.5√ (1 + 2λ)
) exp(0.5λ(1− )) )m (135)
≤ ( 0.5 ( 1 +
1√ (1 + 2λ)
) exp(0.5λ(1− )) )m (136)
Similar to the R.H.S. case, we find that λ ≈ 0.5 1− approximately minimizes the failure probability,
Pr ( ‖ṽ‖2 ≤ 0.5m(1− ) ) ≤ ( 0.5 ( 1 + √ 1− ) exp( 4 ) )m
(137)
= exp ( m (
4 − log 2 1 + √ 1−
)) (138)
It can be shown that,
exp ( m (
4 − log 2 1 + √ 1−
)) ≤ exp ( −m (
4 + log
2
1 + √ 1 +
)) (139)
Thus,
Pr ( ‖v‖2 ≥ (1− )‖u‖2 ) ≥ 1− exp ( −m (
4 + log
2
1 + √ 1 +
)) (140)
Using union bound, Eq. (125) and (140) hold together with probability,
Pr ( (1− )‖u‖2 ≤ ‖v‖2 ≤ (1 + )‖u‖2 ) ≥ 1− 2 exp ( −m (
4 + log
2
1 + √ 1 +
)) (141)
This proves the claim.
Theorem 2 LetD be a fixed dataset with N samples and define a L layer ReLU network as shown in Eq. 3 such that each weight matrix Wl ∈ Rn×n has its elements sampled as W lij
i.i.d.∼ N (0, 2n ) and biases bl are set to zeros. Then for any sample (x,y) ∈ D, ∈ [0, 1), and for all l ∈ {1, 2, . . . , L} with probability at least,
1− 4NL exp ( −n (
4 + log
2
1 + √ 1 +
)) (142)
the following hold true,
(1− )L‖x‖2 · ‖δ(x,y)‖2 ≤ ‖∂`(fθ(x),y) ∂Wl ‖2 ≤ (1 + )L‖x‖2 · ‖δ(x,y)‖2 (143)
and
(1− )l‖x‖2 ≤ ‖hl‖2 ≤ (1 + )l‖x‖2 (144)
Proof: From theorem 1, we know that the following holds for all l,
Pr ( (1− )l‖x‖2 ≤ ‖hl‖2 ≤ (1 + )l‖x‖2 ) ≥ 1− 2NL exp ( −n (
4 + log
2
1 + √ 1 + )) (145)
On the other hand, we have that,
∂`(fθ(x),y)
∂aL−1 = 1(aL−1)
( WL T δ(x,y) )
(146)
From proposition 1, we know that each element of 1(aL−1) follows a Bernoulli distribution with probability 0.5. Thus applying lemma 5 to the above equation (under the assumption that δ(x,y) and 1(al) are statistically independent), the following holds for a fixed data sample (x,y),
Pr ( (1− )‖δ(x,y)‖2 ≤ ‖∂`(fθ(x),y)
∂aL−1 ‖2 ≤ (1 + )‖δ(x,y)‖2
) ≥ 1− 2 exp ( −n (
4 + log
2
1 + √ 1 + )) (147)
Applying union bound on N fixed samples, the following holds for all N samples,
Pr ( (1− )‖δ(x,y)‖2 ≤ ‖∂`(fθ(x),y)
∂aL−1 ‖2 ≤ (1 + )‖δ(x,y)‖2
) ≥ 1− 2N exp ( −n (
4 + log
2
1 + √ 1 + )) (148)
Similarly,
Pr ( (1− )‖∂`(fθ(x),y)
∂aL−1 ‖2 ≤ ‖∂`(fθ(x),y) ∂aL−2 ‖2 ≤ (1 + )‖∂`(fθ(x),y) ∂aL−1 ‖2 ) ≥ 1− 2N exp ( −n ( 4 + log
2
1 + √ 1 + )) (149)
Combining the the above two results and applying union bound, we get,
Pr ( (1− )2‖δ(x,y)‖2 ≤ ‖∂`(fθ(x),y)
∂aL−2 ‖2 ≤ (1 + )2‖δ(x,y)‖2
) ≥ 1− 4N exp ( −n (
4 + log
2
1 + √ 1 + )) (150)
Extending this to all L layers, we have for all l that,
Pr ( (1− )L−l‖δ(x,y)‖2 ≤ ‖∂`(fθ(x),y)
∂al ‖2 ≤ (1 + )L−l‖δ(x,y)‖2
) ≥ 1− 2NL exp ( −n (
4 + log
2
1 + √ 1 + )) (151)
Combining the above result with Eq. (145) using union bound, we get for all l,
Pr ( (1− )L−1‖δ(x,y)‖2‖x‖2 ≤ ‖∂`(fθ(x),y)
∂al ‖2‖hl−1‖2 ≤ (1 + )L−1‖δ(x,y)‖2‖x‖2 ) ≥ 1− 4NL exp ( −n (
4 + log
2
1 + √ 1 + )) (152)
Since,
‖∂`(fθ(x),y) ∂Wl ‖2 = ‖ ∂`(fθ(x),y) ∂al ‖2 · ‖hl−1‖2 ∀l (153)
we have proved the claim.
Lemma 6 (Corollary 2.1 of Kakade & Shakhnarovich (2009)) Let u1,u2 ∈ Rn be any two fixed vectors such that ‖u1‖ ≤ 1 and ‖u2‖ ≤ 1, R ∈ Rm×n be a projection matrix where each element of R is drawn i.i.d. from a standard Gaussian distribution, Rij ∼ N (0, 1m ) and any ∈ (0, 1/2)
Pr (| < Ru1,Ru2 > − < u1,u2 > | ≤ ) ≥ 1− 4 exp ( −m
4
( 2 − 3 )) (154)
Lemma 7 Let v1 = (Ru1) z and v2 = (Ru2) z, where u1,u2 ∈ Rn, z ∈ Rm, and R ∈ Rm×n. If Rij i.i.d.∼ N (0, 10.5m ), zi i.i.d.∼ Bernoulli(0.5) and ∈ [0, 1), then for any fixed vectors u1 and u2 s.t. ‖u1‖ ≤ 1 and ‖u2‖ ≤ 1,
Pr (| < v1,v2 > − < u1,u2 > | ≤ ) ≥ 1− 4 exp ( −m (
4 + log
2
1 + √ 1 +
)) (155)
Proof: Applying lemma 5 to vectors u1 + u2 and u1 − u2, we have with probability at least 1− 4 exp ( −m ( 4 + log 2 1+ √ 1+ )) ,
(1− ) · ‖u1 + u2‖2 ≤ ‖z Ru1 + z Ru2‖2 ≤ (1 + ) · ‖u1 + u2‖2 (156) (1− ) · ‖u1 − u2‖2 ≤ ‖z Ru1 − z Ru2‖2 ≤ (1 + ) · ‖u1 − u2‖2 (157)
Then notice, 4 < v1,v2 > = 4 < z Ru1, z Ru2 > (158)
= ‖z Ru1 + z Ru2‖2 − ‖z Ru1 − z Ru2‖2 (159) ≥ (1− ) · ‖u1 + u2‖2 − (1 + ) · ‖u1 − u2‖2 (160) = 4· < u1,u2 > −2 · (‖u1‖2 + ‖u2‖2) (161) ≥ 4· < u1,u2 > −4 (162)
Equivalently, · < u1,u2 > − < v1,v2 >≤ (163)
The other side of the claim can be proved similarly.

Review summaries:
This paper studies initialization techniques for deep ReLU networks from a theoretical standpoint and derives finite layer width concentration bounds to show that with the He initialization scheme, deep ReLU networks preserve the norm of the input sample during a forward pass and the norm of the gradient with respect to the output during a backward pass. The concentration bounds also suggest lower bounds on the width of the ReLU layers. The authors verify their theory with experiments on synthetic data.

This work considers random parameter initialization in neural networks (In particular the initialization presented in He et al.) and develops non-asymptotic bounds for the norms and gradients of neural networks during initialization. The authors show that the norms of the outputs and gradients (for gradients, under a different assumption on the dimension of the matrix) remain constant through the different layers. The results presented differ from previous work in that they give nice concentration bounds for such output and gradient norms. In addition the authors prove results in the case of infinite samples under the assumption that they arise from a finite dimensional space.