Year: 2019

Abstract:
This paper considers the growth in the length of one-dimensional trajectories as they are passed through deep ReLU neural networks, which, among other things, is one measure of the expressivity of deep networks. We generalise existing results, providing an alternative, simpler method for lower bounding expected trajectory growth through random networks, for a more general class of weights distributions, including sparsely connected networks. We illustrate this approach by deriving bounds for sparse-Gaussian, sparse-uniform, and sparse-discrete-valued random nets. We prove that trajectory growth can remain exponential in depth with these new distributions, including their sparse variants, with the sparsity parameter appearing in the base of the exponent.

heading: 1 INTRODUCTION
text: Deep neural networks continue to set new benchmarks for machine learning accuracy across a wide range of tasks, and are the basis for many algorithms we use routinely and on a daily basis. One fundamental set of theoretical questions concerning deep networks relates to their expressivity. There remain different approaches to understanding and quantifying neural network expressivity. Some results take a classical approximation theory approach, focusing on the relationship between the architecture of the network and the classes of functions it can accurately approximate (Lu et al. (2017); Cybenko (1992); Hornik et al. (1989)). Another more recent approach has been to apply persistent homology to characterise expressivity (Guss & Salakhutdinov (2018)), while Poole et al. (2016) focus on global curvature, and the ability of deep networks to disentangle manifolds. Other works concentrate specifically on networks with piecewise linear activation functions, using the number of linear regions (Montufar et al. (2014)) or the volume of the boundaries between linear regions (Hanin & Rolnick (2019)) in input space. In 2017, Raghu et al. (2017) proposed trajectory length as a measure of expressivity; in particular, they consider the expected change in length of a one-dimensional trajectory as it is passed through Gaussian random neural networks (see Figure 1 for an illustration). Their primary theoretical result was that, in expectation, the length of a one-dimensional trajectory which is passed through a fully-connected, Gaussian network is lower bounded by a factor that is exponential with depth, but not with width.
One-dimensional trajectories and their evolution through deep networks are also of interest in their own right because they constitute simple data manifolds. Firstly, we commonly assume that the real
data which we aim to correctly classify or predict with a deep network lie on one or more manifolds, and thus design a network to perform appropriately on such a manifold. Secondly, researchers are beginning to consider whether the output (manifolds) of generator networks could be a good model for real word data manifolds, for example, as priors for a variety of inverse problems (Manoel et al. (2017); Huang et al. (2018)). Both of these hypotheses motivate an understanding of how manifolds are acted upon by deep networks.
Our results in this paper pertain specifically to the ‘trajectory length’ measure of expressivity. We produce a simpler proof than in the pioneering work of Raghu et al. (2017), which also generalises their results, deriving similar lower bounds for a broader class of random deep neural networks.
Theoretical work of this nature is important because it allows for more straightforward transfer and adaptation of prior theoretical results to new contexts of interest. For example, there is a current surge in research around low-memory networks, training sparse networks, and network pruning. Sparsely connected networks have shown the capacity to retain very high test accuracy (Frankle & Carbin (2019); Han et al. (2015)), increased robustness (Ahmad & Scheinkman (2019); Aghasi et al. (2017)), with much smaller memory footprints, and less power consumption (Yang et al. (2019)). The approach we take in this work enables us to extend results from dense random networks to sparse ones. It also allows us to consider the other weight distributions of sparse-Gaussian, sparse-uniform and sparse-discrete networks (see Definitions 2 - 4).
More specifically we make the following contributions:
Contributions:
1. We provide an alternative, simpler method for lower bounding expected trajectory growth through random networks, for a more general class of weights distributions (Theorem 2).
2. We illustrate this approach by deriving bounds for sparse-Gaussian, sparse-uniform, and sparse-discrete random nets. We prove that trajectory growth can be exponential in depth with these distributions, with the sparsity appearing in the base of the exponential (Corollaries 1 - 3).
3. We observe that the expected length growth factor is strikingly similar across the aforementioned three distributions. This suggests a universality of the expected growth in length for iid centered distributions determined only by the variance and sparsity (Figure 3).

heading: 1.1 NOTATION
text: We consider feedforward ReLU deep neural networks. We denote a the d-th post-activation layer as z(d), and the subsequent pre-activation layer as h(d), such that
h(d) = W (d)z(d) + b(d), z(d+1) = φ(h(d)),
where φ(x) := max(x, 0) is applied elementwise. We denote x = z(0).
We use fNN (x;P,Q) to denote a random feedforward deep neural network which takes as input the vector x, and is parameterised by random weight matrices W (d) with entries sampled iid from the distribution P , and bias vectors b(d) with entries drawn iid from distribution Q. Definition 1. A random sparse network with sparsity parameter α, denoted fNN (x;α,P,Q), is a random feedforward network in which all weights are sampled from a mixture distribution of the form
wij ∼ αP + (1− α)δ, where δ is the delta distribution at 0, and P is some other distribution. In other words, weights are 0 with probability 1− α, and sampled from P with probability α. Biases are drawn iid from Q. Definition 2. A sparse-Gaussian network is a random sparse network fNN (x;α,P,Q), where P = N (0, σ2w) and Q = N (0, σ2b ). Definition 3. A sparse-uniform network is a random sparse network fNN (x;α,P,Q), where P = U(−Cw, Cw) and Q = U(−Cb, Cb). Definition 4. A sparse-discrete network is a random sparse network fNN (x;α,P,Q), where P is a uniform distribution over a finite, discrete, symmetric setW , with cardinality |W| = Nw, and Q is a uniform distribution over a finite, discrete, symmetric set B, with cardinality |B| = Nb.
For a weight matrix W in a random sparse network, with wi denoting the ith row, we define wPi as the vector containing only the P-distributed entries of wi. We define a trajectory x(t) in input space as a curve between two points, say x0 and x1, parameterized by a scalar t ∈ [0, 1], with x(0) = x0 and x(1) = x1, and we define z(d)(x(t)) = z(d)(t) to be the image of the trajectory in layer d of the network. The trajectory length l(x(t)) is given by the standard arc length, ∫
t
∣∣∣∣∣∣∣∣dx(t)dt ∣∣∣∣∣∣∣∣dt.
As in the work by Raghu et al. (2017), this paper considers trajectories with x(t+ dt) having a nontrivial component perpendicular to x(t) for all t, dt.
Finally, we say a probability density or mass function fX(x) is even if fX(−x) = fX(x) for all random vectors x in the sample space.

heading: 2 EXPECTED TRAJECTORY GROWTH THROUGH RANDOM NETWORKS
text: Raghu et al. (2017) considered ReLU and hard-tanh Gaussian networks with the standard deviation scaled by 1/ √ k. Their result with respect to ReLU networks is captured in the following theorem.
Theorem 1 (Raghu et al. (2017)). Let fNN (x;N (0, σ2w/k),N (0, σ2b )) be a random Gaussian deep ReLU neural network with layers of width k, then
E[l(z(d)(t))] ≥ O ( σw √ k√
k + 1
)d · l(x(t)),
for x(t) a 1-dimensional trajectory in input space.
There are, however, other network weight distributions which may be of interest. For example, the expressivity and generative power of sparse networks are of particular interest in the current moment, given the current interest in low-memory and low-energy networks, training sparse networks, and network pruning (Frankle & Carbin (2019); Han et al. (2015); Yang et al. (2019)). We prove that even for sparse random networks, trajectory growth can remain exponential in depth given sufficiently large initialisation scale σw. Scaling σw by 1/ √ k can yield a width-independent lower bound on this growth. Moreover, a sufficiently high sparsity fraction (1 − α) results in a lower bound which, instead of growing exponentially, shrinks exponentially to zero. This is captured by the following result.
Corollary 1 (Trajectory growth in deep sparse-Gaussian random networks). Let fNN (x;α,N (0, σ2w),N (0, σ2b )) be a sparse-Gaussian, feedforward ReLU network as defined in Section 1.1, with layers of width k. Then
E[l(z(d)(t))] ≥ ( ασw √ k√
2π
)d · l(x(t)), (1)
for x(t) a 1-dimensional trajectory in input space.
Corollary 1 with α = 1 and σw replaced by σw/ √ k recovers a bound which is very similar to the prior bound by Raghu et al. (2017) in Theorem 1.
Beyond Gaussian weights, we consider other distributions commonly used for initialising and analysing deep networks. Uniform distributions, for example, still constitute the default initialisations of linear network layers in both Pytorch and Tensorflow (uniform according to U(−1/ √ k, 1/ √ k) in the case of Pytorch, and uniform according to U(−6/ √ kin + kout, 6/ √ kin + kout) – a.k.a the Glorot/Xavier uniform initialization (Glorot & Bengio (2010)) – in the case of Tensorflow). We prove an analogous lower bound for uniformly distributed weights.
Corollary 2 (Trajectory growth in deep sparse-uniform random networks). Let fNN (x;α,U(−Cw, Cw),U(−Cb, Cb)) be a sparse-Uniform, feedforward ReLU network as defined in Section 1.1, with layers of width k. Then
E[l(z(d)(t))] ≥ ( αCw √ k
4 √ 2
)d · l(x(t)), (2)
for x(t) a 1-dimensional trajectory in input space.
Another research direction which has gathered some momentum in recent years are quantized or discrete-valued deep neural networks (Li et al. (2017); Hubara et al. (2016; 2017)), including recent work using integer valued weights (Wu et al. (2018)). This motivates consideration of discrete weight distributions, in addition to continuous ones. As an example of such, we prove a similar lower bound for networks with weights and biases uniformly sampled from finite, symmetric, discrete sets. Corollary 3 (Trajectory growth in deep sparse-discrete random networks). Let fNN (x;α,P,Q) be a sparse-discrete random feedforward ReLU network as defined in Section 1.1, and layers of width k. Then
E[l(z(d)(t))] ≥ ( α √ k
2 √ 2 · ∑ w∈W |w| Nw )d · l(x(t)) (3)
for x(t) a 1-dimensional trajectory in input space.
In all cases these lower bounds show how to choose the combination of σw and α to guarantee (or not) exponential growth in trajectory length in expectation at initialisation.
The main idea behind the derivation of these results is to consider how the length of a small piece of a trajectory (some ‖dz(d)‖) grows from one layer to the next (‖dz(d+1)‖ = ‖φ(hd(t + dt)) − φ(h(d)(t)‖). In the context of random feedforward networks, we can consider piecewise linear activation functions as restrictions of dh(d) to a particular support set which is statistically dependent on h(d). This approach was developed by Raghu et al. (2017). The key to our proof is providing a more direct and more generally applicable way of accounting for this dependence than originally provided by Raghu et al. (2017). Specifically, our approach lets us derive the following, more general result, from which Corollaries 1, 2, and 3 follow easily. Theorem 2 (Trajectory growth in deep random sparse networks). Let fNN (x;α,P,Q) be a random sparse network as defined in Section 1.1, with layers of width k. Let P and Q be such that the joint distribution over a vector of independent elements from both distributions is even. If E[|u>ŵPi |] ≥M‖u‖ for any constant vector u, for all i, then
E[l(z(d)(t))] ≥ ( αM √ k
2
)d · l(x(t)) (4)
for x(t) a 1-dimensional trajectory in input space. Remark. It is trivial to amend this result for networks where the width, distribution, and sparsity varies layer by layer, in which case the lower bound (4) is replaced by
d∏ j=i
( αjMj √ kj
2
) · l(x(t))
Moreover, the bounds from Theorem 2 and Corollaries 1 - 3 hold true in the 0 bias case as well.

heading: 3 PROOF OF THEOREM 2
text: We prove Theorem 2 in three stages: i) We turn the problem into one of bounding from below the change in the length of an infinitesimal line segment; ii) we account simply and explicitly for the dependence generated by the ReLU activation; and iii) we break this dependence by taking advantage of the symmetry characterising this class of distributions. Supporting lemmas can be found in Appendix A.
Proof. Stage 1:
For the first stage of proof, we will closely follow Raghu et al. (2017). We are interested in deriving a lower bound of the form,
E [∫
t
∣∣∣∣∣∣∣∣dz(d)(t)dt ∣∣∣∣∣∣∣∣dt] ≥ C · ∫
t
∣∣∣∣∣∣∣∣dx(t)dt ∣∣∣∣∣∣∣∣dt, (5)
for some constant C. As noted by Raghu et al. (2017), it suffices to instead derive a bound of the form
E [ ‖dz(d)(t)‖ ] ≥ C‖dx(t)‖,
since integrating over t yields the desired form. Our approach will be to derive a recurrence relation between ‖dz(d+1)‖ and ‖dz(d)‖, where we refrain from explicitly including the dependence of dz on t, for notational clarity.
Next, like Raghu et al. (2017), our proof relies on the observation that
dz(d+1) = φ(W (d)z(d)(t+ δt) + b(d))− φ(W (d)z(d)(t) + b(d)) = φ(d)(t+ δt)− φ(d)(t) = dφ(d),
and that since φ is the ReLU operator, dφ dh
(d) j
is either 0 or 1. When z(d) is fixed independently of
W (d) and b(d), then P (h(d)j = 0) = 0 (see the preamble to Lemma 6 for more detail on this), and thus we need only note that dφ(d)j = dh (d) j when h (d) j > 0, and dφ (d) j = 0 when h (d) j < 0. We define A(d) to be the set of ‘active nodes’ in layer d; specifically,
A(d) := {j : h(d)j > 0},
and IA(d) ∈ Rk×k is defined as the matrix with ones on the diagonal entries indexed by set A(d), and 0 everywhere else. We can then write
‖dz(d+1)‖ = ‖IA(d)(h(d)(t+ dt)− h(d)(t))‖ = ‖IA(d)W (d)dz(d)‖.
From here we will drop the weight index (d) to minimise clutter in the exposition.
It is at this point where we depart from the proof strategy used by Raghu et al. (2017). The next steps in their proof depend heavily on the weight matrices in the network being Gaussian. For example, they require that a weight matrix after rotation has the same, i.i.d. distribution as the matrix before rotation. Instead, our proof can tackle a number of other, non-rotationally-invariant distributions, as well as sparse networks.
Stage 2:
The next stage of the proof begins by noting that after conditioning on size of the set A,
E[‖IAWdz(d)‖ | |A|] = E[‖Ŵdz(d)‖ | ŵ>i z(d) + b̂i > 0 ∀i, |A|], (6)
where Ŵ ∈ R|A|×k is the matrix comprised of the rows of W indexed by A, and we denote the i-th row of Ŵ as ŵi, and the i-th entry of b̂ as b̂i. Equation 6 follows since the elements of Wdz(d) are i.i.d., and A(d) selects all entries whose corresponding entries in h(d) have positive values. Thus, in expectation, pre-multiplying by the matrix IA(d) is equivalent to considering Ŵdz(d) instead of IAWdz
(d) together with conditioning on the fact that every element in the vector Ŵz(d) + b̂ is positive.
This gives us
E[‖IAWdz(d)‖ ] = E  Ê w1 Ê w2 · · · E ŵ|A|  √√√√ |A|∑
i=1
(ŵ>i dz (d))2 ∣∣∣∣ ŵ>i z(d) + b̂i > 0 ∀i, |A|   (7)
= E  Ê w1 Ê w2 · · · E ŵ|A|  √√√√ |A|∑
i=1
|ŵ>i dz(d)|2 ∣∣∣∣ ŵ>i z(d) + b̂i > 0 ∀i, |A|   (8)
≥ E  √√√√ |A|∑
i=1
Ê wi [|ŵ>i dz(d)| |ŵ>i z(d) + b̂i > 0]2  , (9) where (7) follows from the analysis above and the independence of each ŵi, (8) is trivial, and (9) follows from iteratively applying Jensen’s inequality, after noting that f(x) = √ x2 + C is convex for x,C ≥ 0.
Now let Ji denote the (random) index set of the P-distributed entries of ŵi, and let wJi , dz(d)Ji , z (d) Ji denote the restrictions to the indices in Ji of ŵi, dz(d) and z(d) respectively. Then ŵ>i z (d) = w>Jiz (d) Ji , and ŵ>i dz (d) = w>Jidz (d) Ji , such that, after conditioning on Ji, we have that
E[‖Ŵp‖ | ŵ>i z(d) + b̂i > 0 ∀i, |A|] ≥ E  √√√√√√√√ |A|∑ i=1 (∗∗)︷ ︸︸ ︷ E Ji [ E wJi [|w>Jidz (d) Ji | |w>Jiz (d) Ji
+ b̂i > 0, Ji]︸ ︷︷ ︸ (∗)
] 2  ︸ ︷︷ ︸
(∗∗∗)
.
(10)
Stage 3:
The third stage of the proof is to work our way from the inside out, lower bounding (∗) first, then (∗∗), and finally (∗ ∗ ∗).
Consider the expectation in (∗). Having conditioned on Ji, we can define X = w>Jidz (d) Ji and Y = w>Jiz (d) Ji + b̂i, such that lower bounding (∗) means lower bounding
E[|X| |Y > 0]. (11)
By assumption the joint distribution over G = [wJi,1, . . . , wJi,k, b̂i] > is even. The vector H = [X,Y,wJi,3 . . . , wJi,k, b̂i] > is obtained by a linear transformation of G (which is invertible since ‖z(d)‖ is not parallel to ‖dz(d)‖). Thus by Lemma 1 (continuous) or Lemma 2 (discrete) this joint distribution over H is also even, and by Lemma 3 (continuous) or Lemma 4 (discrete), the joint distribution of [X,Y ]> is even too. We can therefore apply Lemma 5 (continuous) or Lemma 6 (discrete) and need only consider E[|X|], which is bounded as
E[|X|] ≥M‖dz(d)Ji ‖, (12)
again by assumption.
Having bounded (∗), we average over Ji to get (∗∗), for which we can apply Lemma 7 to get
E Ji [M‖dz(d)Ji ‖] ≥ αM‖dz (d)‖. (13)
Finally, we can bound (∗ ∗ ∗) as follows
E[‖IAWdz(d)‖] ≥ E |A|
 √√√√ |A|∑
i=1
α2M2‖dz(d)‖2  (14) = E |A| [√ |A| · α2M2‖dz(d)‖2 ] (15)
≥ E |A|
[ 1√
kαM‖dz(d)‖ · |A| · α2M2‖dz(d)‖2
] (16)
= αM‖dz(d)‖√
k · E[|A|]. (17)
where (14) is obtained by substituting the bound for (∗∗) into the inequality in (10), (15) follows since there is no dependence on i in the summed terms, and (16) follows since for any 0 ≤ γ ≤ max(γ), √ γ ≥ 1√
max(γ) γ, and |A| is at most k.
The proof is concluded by calculating E[|A|]. Since |A| is the number of entries in the vector h(d) which are positive, and each entry in that vector is an independent, centred random variable, |A| has a binomial distribution with probability 1/2, and therefore an expected value of k/2. Plugging this in yields the final recursive relation between ‖dz(d+1)‖ and ‖dz(d)‖,
E[‖dz(d+1)‖] ≥ αM √ k
2 ‖dz(d)‖.
Iterative application of this result starting at the first layer yields the final result.
Let us illustrate the ease with which Corollaries 1, 2 and 3 are obtained. In the case of each distribution, we need to do two things. First, we must verify that the necessary assumption holds in the case of those distributions P andQ: that the joint distribution over a vector of independent elements from both distributions is even. Second, we must derive a bound of the form E[|u>w|] ≥ M‖u‖, where wi ∼ P , and substitute M into Theorem 2. When P and Q are centred Gaussians, the joint distribution over elements from one or both distributions is a multivariate Gaussian, with an even joint probability density function. Moreover, for U = u>w, E[|U |] has a closed form solution,
E[|U |] = √
2σw√ π ‖u‖
When P and Q are centred uniform distributions, the joint distribution is uniform over the polygon bounded in each dimension by the symmetric bounds [−Cw, Cw] or [−Cb, Cb], and thus is even. Next, to bound E[|U |], we apply the Marcinkiewicz-Zygmund inequality with p = 1, using the optimal A1 from Lemmas 8 and 9, to get that
E[|U |] ≥ Cw 2 √ 2 ‖u‖;
for details of this derivation, see Lemma 10.
Likewise, when P and Q are uniform distributions over discrete, symmetric, finite sets W and B respectively, we make a discrete analogue of the argument made in the continuous uniform case to confirm the necessary assumption holds. Bounding E[|U |] in this case also follows from a very similar argument to that made in the continuous case, detailed in full in Lemma 11, yielding
E[|U |] ≥ ∑ w∈W |w|√
2Nw ‖u‖.

heading: 4 NUMERICAL SIMULATIONS
text: In this section we demonstrate, through numerical simulations, how the relationships between the the network’s distributional and architectural properties observed in practice compare with those described in the lower bounds of Corollaries 1 - 3. To this end, we use as our trajectory a straight line between two (normalised) MNIST datapoints1, discretized into 10000 pieces. For each combination of distribution and parameters, we pass the aforementioned line through 100 different deep neural networks of width 784, and average the results. Specifically, we consider three different networks types, sparse-Gaussian, sparse-uniform, and sparse-discrete networks, from Definitions 2 - 4 respectively. For each distribution we consider different values of network fractional density α ranging from 0.1 to 1. In the sparse-Gaussian networks, non-zero weights are sampled fromN (0, σ2w/k), and biases from N (0, 0.012). In the sparse-Uniform networks, non-zero weights are sampled from U(−C/ √ k,C/ √ k), and biases from U(−0.01, 0.01). In the sparse-discrete networks, non-zero weights are uniformly sampled fromW := (1/ √ k) {−C,−(C + 1), . . . , C − 1, C}, and biases from B := {−0.01, 0.01}. We do this for a variety of σw and C values. The results are shown in Figures 2 and 3.
Figure 2 plots the average length of the trajectory at layer d of a sparse-Gaussian network, with σw = 6 and for different choices of sparsity ranging from 0.1 to 0.9. We see exponential increase of expected length with depth even in sparse networks, with smaller slopes for smaller α (higher sparsity). In Figures 3a and 3b we plot the growth ratio of a small piece of the trajectory from one
layer to the next, averaged over all pieces, at all layers, and across all 100 networks for a given distribution. This E[‖dz(d+1)‖/‖dz(d)‖] corresponds to the base of the exponential in our lower bound. The solid lines reflect the observed averages of this ratio, while the dashed lines reflect
1In this experiment we chose the 101st and 1001st points from the MNIST test set, but the choice of points does not qualitatively change the results.
the lower bound from Corollaries 1, 2, and 3. Figure 3a illustrates the dependence on the standard deviation of the respective distributions (before scaling by 1/ √ k), with α fixed at α = 0.5. We observe both that the lower bounds clearly hold, and that the dependence on σw is linear in practice, exactly as we expect from our lower bounds. Figure 3b shows the dependence of this ratio on the sparsity parameter α, where we have fixed σw = 2 for all distributions. Once again, the lower bounds hold, but in this case there is a slight curve in the observed values, not a strictly linear relationship. The reason for this is that the linear bound we provide is necessary in order to account for the more pathological cases of dz. This is discussed in more depth in Appendix B.
One striking observation in Figures 3a and 3b is that for a given σw, the observed E[‖dz(d+1)‖/‖dz(d)‖] matches perfectly across all three distributions, for different values of σw and different α. This remains true when we repeat the experiments with different datapoints, and with points chosen uniformly at random in a high-dimensional space, both when the trajectory considered is a straight line and when it is not (e.g. arcs in two or more dimensions.) See Appendix C.1 for these figures. Another implication of these experiments is that they give some guidance for how to trade off weight scale against sparsity depending on the desired network properties. For example, Figure 3b considers the initialisation scheme with σw = 2/ √ k. We see that the empirically observed growth factor from one layer to the next is approximately 1.5 when the matrices are dense (α = 1), while the growth factor is 1 with α ≈ 0.5, and less than one as α decreases further. In Appendix C.2 we present some preliminary numerical experiments looking at the extent to which the results proved and verified for random networks apply to trained networks as well. Our results indicate that indeed some of the results appear to carry over: trained networks appear to retain the exponential trajectory growth with depth, and that the trajectory growth factor retains a roughly linear dependence on σw. However, this expected growth factor is not the same size in random nets as it is in trained nets with the same σw, nor is the expected growth factor trajectory independent in trained networks, as it is for random networks.

heading: 5 CONCLUSION
text: Our proof strategy and results generalise and extend previous work by Raghu et al. (2017) to develop theoretical guarantees lower bounding expected trajectory growth through deep neural networks for a broader class of network weight distributions and the setting of sparse networks. We illustrate this approach with Gaussian, uniform, and discrete valued random weight matrices with any sparsity level.

heading: A SUPPORTING LEMMAS
text: Lemma 1. Let fX(x) be an even joint probability density function over random vector X ∈ Rk. Let A ∈ Rk×k be an invertable linear transformation such that Y = AX . Then the joint density fY (y) is also even.
Proof. Wlog we assume fX is defined on Rk. To calculate the density over Y ∈ Rk we make a change of variables such that
fY (y) = fX(A −1y)|A−1|. (18)
Since A is one-to-one, we have that fX(x) = fX(A−1y) for some y, and fX is even, so fX(A −1y) = fX(−(A−1y)) = fX(A−1(−y)) for all y. Putting this together completes the proof,
fY (y) = fX(A −1y)|A−1| = fX(A−1(−y))|A−1| = fY (−y) (19)
Lemma 2. Let fX(x) be an even joint probability mass function over random vector X ∈ Rk. Let A ∈ Rk×k be an invertable linear transformation such that Y = AX . Then the joint mass function fY (y) is also even.
Proof. fX is defined on some discrete, finite, symmetric set X . To calculate the density over Y ∈ Y := {Ap : p ∈ X} we make a change of variables such that
fY (y) = ∑
x∈{Ax=y}
fX(x). (20)
Since A is one-to-one, we have that fX(x) = fX(A−1y) for some y, and fX is even, so fX(A −1y) = fX(−(A−1y)) = fX(A−1(−y)) for all y. Putting this together completes the proof,
fY (y) = ∑
x∈{Ax=y}
fX(A −1y) = ∑ x∈{Ax=y} fX(A −1(−y)) = fY (−y) (21)
Lemma 3. Let fX1,...,Xk(x1, . . . , xk) be an even probability density function. Then fX1,...,Xk−1(x1, . . . , xk−1) = ∫∞ −∞ fX1,...,Xk(x1, . . . , xk)dxk is also even.
Proof.
fX1,...,Xk−1(x1, . . . , xk−1) = ∫ ∞ −∞ fX1,...,Xk(x1, . . . , xk)dxk
= ∫ ∞ −∞ fX1,...,Xk(−x1, . . . ,−xk)dxk
= ∫ ∞ −∞ fX1,...,Xk(−x1, . . . ,−xk−1, xk)dxk
= fX1,...,Xk−1(−x1, . . . ,−xk−1) The first and last equalities follow from the definition of marginalisation of random variables. The second equality follows from the assumption that fX1,...,Xk is even, and the third equality follows from the change of variables: −xk −→ xk.
Lemma 4. Let X1, . . . , Xk be discrete random variables with symmetric support sets X1, . . . ,Xk respectively, i.e. xi ∈ Xj ⇐⇒ −xi ∈ Xj . Let P (X1 = x1, . . . , Xk = xk) be an even probability mass function such that P (X1 = x1, . . . , Xk = xk) = P (X1 = −x1, . . . , Xk = −xk) . Then P (X1 = x1, . . . , Xk−1 = xk−1) is also even.
Proof.
P (X1 = x1, . . . , Xk−1 = xk−1) = ∑ xk∈Xk P (X1 = x1, . . . , Xk = xk) (22)
= ∑ xk∈Xk P (X1 = −x1, . . . , Xk = −xk) (23)
= ∑
−xk∈Xk
P (X1 = −x1, . . . , Xk = xk) (24)
= ∑ xk∈Xk P (X1 = −x1, . . . , Xk = xk) (25)
= P (X1 = −x1, . . . , Xk−1 = −xk−1) (26) Lines 22 and 26 follow from the definition of marginal distributions, (23) follows by assumption, (24) follows fro a change of variables, and (25) follows since summing over −xk is equivalent to summing over xk.
Lemma 5. Let X and Y be random variables with an even joint probability density function fXY (x, y). Then
E[|X| | Y > 0] = E[|X|]
Proof. Letting |X| = Z, we can make a straightforward change of variables to calculate the joint distribution fZY (z, y), which works out to be
fZY (z, y) = fXY (z, y) + fXY (−z, y) for z ≥ 0 and y ∈ R. Then we have that
E[Z|Y > 0] = ∫ ∞
0
z · fZ|Y >0(z|y > 0)dz
= ∫ ∞ 0 z · fZ,Y >0(z, y > 0)∫∞ 0 fY (y)dy dz
= 2 ∫ ∞ 0 z · fZ,Y >0(z, y > 0)dz
= 2 ∫ ∞ 0 z ∫ ∞ 0 fZY (z, y)dydz
= 2 ∫ ∞ 0 z ∫ ∞ 0 (fXY (z, y) + fXY (−z, y))dydz.
One the other hand, we have that E[Z] = ∫ ∞
0
z · fZ(z)dz
= ∫ ∞ 0 z · (fX(z) + fX(−z))dz
= 2 ∫ ∞ 0 z · fX(z)dz
= 2 ∫ ∞ 0 z · ∫ ∞ −∞ fXY (z, y)dydz
= 2 ∫ ∞ 0 z · (∫ 0 −∞ fXY (z, y)dy + ∫ ∞ 0 fXY (z, y)dy ) dz
Comparing the expressions for E[Z|Y > 0] and E[Z], we can see that they are equal if∫ 0 −∞ fXY (z, y)dy = ∫ ∞ 0 fXY (−z, y)dy.
A change of variables on the left hand side from y to −y yields∫ 0 −∞ fXY (z, y)dy = ∫ ∞ 0 fXY (z,−y)dy.
and by assumption, we know that fXY (z,−y) = fXY (−z, y) since fXY is even, which completes the proof.
Lemma 5 implicitly makes use of the fact that P (Y = 0) = 0, which follows from w Ji and b̂i being continuous random variables, and Y = w>JizJi + b̂i, with zJi being fixed independent of wJi . We similarly make use of the fact that P (Y = 0) = 0 in the application of Lemma 6, though that this is true is less immediately apparent in the discrete case. For clarity, let us define v := [wJi , b̂i], the concatenation of wJi and b̂i, and ẑ := [zJi , 1], the concatenation of zJi and 1, such that Y = v
>ẑ. Associated with the discrete distribution over v there are N |Ji|w Nb possible discrete random vectors in R|Ji|+1. The set of vectors ẑ ∈ R|Ji|+1 orthogonal to such a discrete set is measure zero, and as such for ẑ fixed independent of the choice of the discrete measure v we have P (v>ẑ = 0) = 0. If however ẑ were selected with knowledge of the discrete distribution v then one of two cases will occur; either v>ẑ 6= 0, or ẑ is selected to be from the measure zero set of vectors orthogonal to any of the N |Ji|w Nb vectors generated by v. In the latter case, the assumptions in Lemma 6 of Y excluding 0 would not be satisfied. In such an adversarial case there would be a discrepancy between E[|X| | Y > 0] and E[|X|] which would shrink as the proportion of the N |Ji|w Nb vectors generated by v to which that particular ẑ is orthogonal. Lemma 6. Let X and Y be discrete random variables with finite, symmetric support sets X and Y respectively, where 0 /∈ Y , and an even joint probability mass function fXY (x, y) such that P (X = x, Y = y) = P (X = −x, Y = −y). Then
E[|X| | Y > 0] = E[|X|]
Proof. Letting |X| = Z, we can make a change of variables to obtain the joint mass function fZY (z, y), which works out to be
fZY (z, y) = { fXY (z, y) + fXY (−z, y) for (z, y) where z ∈ X+ and y ∈ Y fXY (z, y) for (z, y) where z = 0 and ∈ Y
where X+ is the set of all positive elements of X . Next, we have that
E[Z|Y > 0] = ∑ z∈X+ zP (Z = z|Y > 0)
= ∑ z∈X+ z P (Z = z ∩ Y > 0) P (Y > 0) (27)
= 2 ∑ z∈X+ zP (Z = z ∩ Y > 0) (28)
= 2 ∑ z∈X+ ∑ y∈Y+ zP (Z = z ∩ Y = y)
= 2 ∑ z∈X+ ∑ y∈Y+ z (fXY (z, y) + fXY (−z, y)) (29)
On the other hand, we have
E[Z] = ∑ z∈X+ zP (Z = z) (30)
= ∑ z∈X+ z (fX(z) + fX(−z)) (31)
= 2 ∑ z∈X+ zfX(z) (32)
= 2 ∑ z∈X+ ∑ y∈Y zfXY (z, y) (33) = 2 ∑ z∈X+ ∑ y∈Y+ zfXY (z, y) + ∑ y∈Y− zfXY (z, y)
 (34) Next, we not that ∑
y∈Y− zfXY (z, y) = ∑ y∈Y+ zfXY (z,−y)
= ∑ y∈Y+ zfXY (−z, y)
Thus the expressions in 29 and 34 are equal, which completes the proof.
Lemma 7 (Expected norm of a random sub-vector). Let u ∈ Rk be a fixed vector and let J ⊆ {1, 2, . . . , k} be a random index set, where the probability of any index from 1 to k appearing in any given sample is independent and equal to α. Then, defining uJ to be the vector comprised only of the elements of u indexed by J , we can lower bound the expectation of the norm of this subvector by
EJ [‖uJ‖] ≥ α‖u‖ (35)
Proof. First, we bound the expectation of the norm in terms of the expectation of the squared norm as follows:
E[‖uJ‖] = E[ √∑ j∈J u2J,j ] (36)
≥ 1‖u‖E[ ∑ j∈J u2J,j ] (37)
This follows because for any 0 ≤ γ ≤ max(γ),√γ ≥ 1√ max(γ) γ.
Next we note that ∑ j∈J u 2 J,j is exactly equivalent to ∑k i=1 u 2 iBi, a weighted sum of k iid Bernoulli random variables Bi with p = α, and so
E[ ∑ j∈J u2J,j ] = k∑ i=1 u2i · E[B] (38)
= ‖u‖2 · α. (39) Substituting this into inequality 37 completes the proof,
E[‖uJ‖] ≥ α‖u‖
Lemmas 8 and 9 are taken from Ferger (2014), and are restated here for completeness.
Lemma 8 (Marcinkiewicz-Zygmund Inequality (Ferger (2014))). Let X1, . . . , Xn be n ∈ N independent and centered real random variables defined on some probability space (Ω, A, P ) with E[|Xi|p] <∞ for every i ∈ {1, ..., n} and for some p > 0. Then for every p ≥ 1 there exist positive constants Ap and Bp depending only on p such that
ApE ( n∑ i=1 X2i )p/2 ≤ E[∣∣∣∣ n∑ i=1 Xi ∣∣∣∣p ] ≤ BpE ( n∑ i=1 X2i )p/2 (40) Lemma 9 (Optimal constants for Marcinkiewicz-Zygmund Inequality (Ferger (2014))). Let Γ denote the Gamma function and let p0 be the solution of the equation Γ(p+12 ) = √ π/2 in the interval (1, 2), i.e. p0 ≈ 1.84742. Then for every p > 0 it holds:
Ap,opt =  2p/2−1, 0 < p ≤ p0 2p/2 · Γ( p+1 2 )√ π , p0 < p < 2
1 2 ≤ p <∞ (41)
and
Bp,opt = { 1 0 < p ≤ 2 2p/2 · Γ(
p+1 2 )√ π , 2 < p <∞ (42)
Lemma 10. Let X = ∑ i αiwi, where wi ∼ U(−C,C) Then
E[|X|] ≥ C 2 √ 2 ‖α‖
Proof. DefiningXi = αiwi, we can then apply the Marcinkiewicz-Zygmund inequality with p = 1, using the optimal A1 from Lemma 9 to get that
E[|X|] = E [∣∣∣∣ k∑
i=1
Xi ∣∣∣∣ ] ≥ 1√
2 E
 √√√√ k∑
i=1
X2i  Next we use the same tricks as early in the proof of the Gaussian case:
1√ 2 E
 √√√√ k∑
i=1
X2i  = 1√ 2 E  √√√√ k∑
i=1
|Xi|2 
≥ 1√ 2 √√√√ k∑ i=1 E[|Xi|]2,
where the first equality is trivial and the second follows from a repeated application of Jensen’s inequality.
To calculate E[|Xi|] we note that Xi = αiwi is uniformly distributed Xi ∼ U(−|αi|C, |αi|C), and thus
E[|Xi|] = C|αi|
2 and so
E[|X|] ≥ 1√ 2 √√√√ k∑ i=1 E[|Xi|]2
= 1√ 2 √√√√C2 4 k∑ i=1 |αi|2
= C
2 √ 2 ‖α‖
Lemma 11. Let X = ∑ i αiwi, where wi are uniformly sampled from some discrete symmetric sample spaceW . Then
E[|X|] ≥ ∑ w∈W |w|√
2Nw ‖α‖
Proof. Defining Xi = αiwi, we follow exactly the same steps as in the first part of the proof of Lemma 10, to get that
E[|X|] ≥ 1√ 2 √√√√ k∑ i=1 E[|Xi|]2.
To calculate E[|Xi|] we note that Xi = αiwi is uniformly sampled from αiW and thus
E[|Xi|] = |αi| ∑ w∈W |w| Nw
and so
E[|X|] ≥ 1√ 2 √√√√ k∑ i=1 E[|Xi|]2
= 1√ 2 √√√√ (∑w∈W |w|)2 N2w k∑ i=1 |αi|2
= ∑ w∈W |w|√
2Nw ‖α‖
Lemma 12. Let W,X ⊂ Rk be discrete sets with finite cardinality, and g : W −→ X be a oneto-one transformation. Then if P (W = w) = P (W1 = w1, . . . ,Wk = wk) = C for all w ∈ W , where C is constant, then P (X = x) = C for all x ∈ X
Proof.
P (X = x) = ∑
w∈{g(w)=x}
P (W = w) (43)
= C (44)
Equation 43 is a change of variables, and (44) follows from the fact the there is only ever one term in the sum, since g is one-to-one.
B NON-LINEAR DEPENDENCE ON α IN THE TYPICAL CASE
One interesting observation which merits further detail is that the observed dependence of the growth factor on α in practice, shown in Figure 3b, is not exactly linear, but rather the shape of that dependence looks closer to √ α. The likely source of this qualitative discrepancy is the use of Lemma 7, to lower bound
EJi [‖dzJi‖] ≥ α‖dz‖, (45) used in (13) in Stage 3 of the proof of Theorem2. It is straightforward to derive an upper bound for this same quantity, as
EJi [‖dzJi‖] ≤ √ α‖dz‖, (46)
first using Jensen’s inequality to get that EJi [ √ ‖dzJi‖2] ≤ √ E[‖dzJi‖2], and then using the strategy from the proof of Lemma 7 to get E[‖dzJi‖2] = α‖dz‖2.
To explore this discrepancy between the observed growth ratio and the lower and upper bounds from (45) and (46), we consider different fixed vectors dz ∈ Rk, and average over subvectors dzJi . Specifically, we calculated the expected value of a subvector dzJi containing only the entries of dz indexed by Ji, where Ji ⊆ {1, 2, . . . , k} is a random index set, where the probability of any index from 1 to k appearing in any given sample is independent and equal to α. Figure 4a shows the results when dz a realisation of the uniform distribution over the unit sphere, with different dimensions k.
For even moderately large k, and vectors dz where most entries are roughly this same magnitude, this upper bound is very tight, such that the expected norm of the subvector generally behaves like√ α‖dz‖, not α‖dz‖. However, it is also possible to construct an example where the lower bound is
tight, by letting dz have only a single non-zero entry, which case E[‖uJ‖] = α‖u‖ (see Figure 4b). While the former case, with entries of dz mostly of the same order, is typical, especially past the first few layers of the network, the bound cannot be improved without further assumptions on ‖dz‖. Further work on quantifying the probabilistic concentration of E[‖uJ‖] close to √ α‖u‖ would be an interesting extension of this research.

heading: C ADDITIONAL NUMERICAL EXPERIMENTS
text: C.1 OTHER DATAPOINTS AND TRAJECTORIES WITH RANDOM NETWORKS
C.2 TRAINED NETWORKS
One might consider the extent to which the results proved and numerically verified for random networks carry over to the context of trained networks.
Here we present a preliminary investigation into trajectory growth through trained networks. For 5 different values of initial σw, we train 20 different randomly initialised dense Gaussian deep ReLU networks (10 layers, hidden layers of width 32) on MNIST to test accuracy of greater than 95%. After training we calculate the new, post-training σw of each net. We then sample pairs of data points of the same class, and of different classes, and connect them with straight lines. These are the trajectories we pass through the trained networks (each is pass through the 20 trained networks for each σw, and the growth factor averaged over all these networks). Each trajectory was then also passed through 20 random Gaussian networks of the same architecture in order to compare the outcomes.
The results are shown in Figure 6. Two key observations from Figure 6, consistent with Corollaries 1 - 3, are that: there remains a roughly linear dependence of σw in the base of the growth factor and 2) that the expected trajectory growth remains exponential with depth.
Figure 6a illustrates this for paths between data points within and between classes, which is one of the potential factors that would impact the behaviour of a trained, rather than random, network; we observe that the average growth factor for trajectories between classes is larger than for trajectories
joining points within the same class. However, trajectory growth can remain exponential in depth in both cases.
Figure 6b shows individual results for individual lines passed through the 20 trained networks per initialization value σw. In addition to the average behaviour shown in Figure 6a, we observe that each path shows the same two aforementioned key observations of path length having dependence proportional to σw. The black curves in Figure 6b are the result of the same procedure, but with random networks pre-training. Individual data points in Figure 6b come from averaging the posttraining σw and trajectory growth factor over twenty trained networks, each curve in Figure 6b thus corresponds to one trajectory, for varying values of σw. The variance, over the 20 trained networks, of both computed values (post-training σw and growth factor), is displayed in the figures, but is typically smaller than the dot used by the plotting software. Consequently visual gaps between data points indicate a statistically significant difference between the expected growth factors for different trajectories. The consistency across different trained networks for each given trajectory is remarkable given the different random initializations of the networks. Moreover, however, the gaps between the plots for different trajectories illustrates a key different between trained and untrained networks: in trained networks, the growth factor is trajectory-dependent, while (as shown in Figure 5), this is not the case for random networks.
A further numerical exploration of these preliminary results would be necessary to confirm consistency across the many hyperparameters involved in such experiments; for example, which sample pairs of points are used, what trajectory shape, or what regularisation is used during training. Similarly, potential experiments on trained sparse networks may be influenced by the choice of method for imposing sparsity on the trained network (e.g variational dropout (Molchanov et al. (2017)), l0 regularization (Louizos et al. (2017)), or magnitude pruning (Zhu & Gupta (2017))). Such an expansive numerical investigation is beyond the scope of the focus of this paper, but may serve as an interesting alternative direction of inquiry.

Review summaries:
This submission proposes an alternative way to lower bound the trajectory growth through random networks. It generalizes to a variety of weights distributions. For example, the authors showcase their approach on sparse-Gaussian, sparse-uniform, and sparse-discrete-valued random nets and prove that trajectory growth can be exponential in depth with these distributions, with the sparsity appearing in the base of the exponential. 

The authors examine trajectory growth of deep ReLU neural networks whose weights come from a (random) “sparse-Gaussian”, “sparse-uniform”, and “sparse-discrete” distribution. They give definitions of these distributions in the paper. They do this by extending the proof of Raghu (2017) so that it can handle more general distributions than the standard Gaussian. They also provide some numerical experiments verifying their theories.