Title: TRAJECTORY GROWTH LOWER BOUNDS FOR RANDOM SPARSE DEEP RELU NETWORKS

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.

1. INTRODUCTION:

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

1.1. NOTATION:

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 f N N (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 f N N (x; α, P, Q), is a random feedforward network in which all weights are sampled from a mixture distribution of the form

w ij ∼ α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 f N N (x; α, P, Q), where

P = N (0, σ 2 w ) and Q = N (0, σ 2 b ). Definition 3. A sparse-uniform network is a random sparse network f N N (x; α, P, Q), where P = U(-C w , C w ) and Q = U(-C b , C b ).

Definition 4. A sparse-discrete network is a random sparse network f N N (x; α, P, Q), where P is a uniform distribution over a finite, discrete, symmetric set W, with cardinality |W| = N w , and Q is a uniform distribution over a finite, discrete, symmetric set B, with cardinality |B| = N b .

For a weight matrix W in a random sparse network, with w i denoting the i th row, we define w Pi as the vector containing only the P-distributed entries of w i .

We define a trajectory x(t) in input space as a curve between two points, say x 0 and x 1 , parameterized by a scalar t ∈ [0, 1], with x(0) = x 0 and x(1) = x 1 , 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

f X (x) is even if f X (-x) = f X (x)

for all random vectors x in the sample space.

2 EXPECTED TRAJECTORY GROWTH THROUGH RANDOM NETWORKS 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 f N N (x; N (0, σ 2 w /k), N (0, σ 2 b )) 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 f N N (x; α, N (0, σ 2 w ), N (0, σ 2 b )) be a sparse-Gaussian, feedforward ReLU network as defined in Section 1.1, with layers of width k. Then

EQUATION

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/ √ k in + k out , 6/ √ k in + k out ) -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 f N N (x; α, U(-C w , C w ), U(-C b , C b )) be a sparse-Uniform, feedforward ReLU network as defined in Section 1.1, with layers of width k. Then

EQUATION

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 f N N (x; α, P, Q) be a sparse-discrete random feedforward ReLU network as defined in Section 1.1, and layers of width k. Then

EQUATION

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) = φ(h d (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 f N N (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 ŵPi |] ≥ M u for any constant vector u, for all i, then

EQUATION

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 α j M j k j 2 • l(x(t))

Moreover, the bounds from Theorem 2 and Corollaries 1 -3 hold true in the 0 bias case as well.

3. PROOF OF THEOREM 2:

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,

EQUATION

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) and b (d) , then P (h

(d) j is either 0 or 1. When z (d) is fixed independently of W (

(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) to be the set of 'active nodes' in layer d; specifically,

(d) j = 0 when h (d) j < 0. We define A (

A (d) := {j : h (d) j > 0},

and I A (d) ∈ R k×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 d) .

dz (d+1) = I A (d) (h (d) (t + dt) -h (d) (t)) = I A (d) W (d) dz (

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,

EQUATION

where Ŵ ∈ R |A|×k is the matrix comprised of the rows of W indexed by A, and we denote the i-th row of Ŵ as ŵi , and the i-th entry of b as bi . Equation 6follows since the elements of W dz (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 I A (d) is equivalent to considering Ŵ dz (d) instead of I A W dz (d) together with conditioning on the fact that every element in the vector Ŵ z (d) + b is positive.

This gives us

EQUATION

where ( 7) follows from the analysis above and the independence of each ŵi , ( 8) is trivial, and (9) follows from iteratively applying Jensen's inequality, after noting that f

(x) = √ x 2 + C is convex for x, C ≥ 0.

Now let J i denote the (random) index set of the P-distributed entries of ŵi , and let w Ji , dz

(d) Ji , z (d) Ji

denote the restrictions to the indices in J i of ŵi , dz (d) and z (d) respectively. Then

ŵ i z (d) = w Ji z (d)

Ji , and

ŵ i dz (d) = w Ji dz (d)

Ji , such that, after conditioning on J i , we have that

E[ Ŵ p | ŵ i z (d) + bi > 0 ∀i, |A|] ≥ E       |A| i=1 ( * * ) E Ji E w J i [|w Ji dz (d) Ji | |w Ji z (d) Ji + bi > 0, J i ] ( * ) 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 J i , we can define X = w Ji dz

(d) Ji and Y = w Ji z (d)

Ji + bi , such that lower bounding ( * ) means lower bounding

EQUATION

By assumption the joint distribution over G = [w Ji,1 , . . . , w Ji,k , bi ] is even. The vector H = [X, Y, w Ji,3 . . . , w Ji,k , bi ] 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

EQUATION

again by assumption.

Having bounded ( * ), we average over J i 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

EQUATION

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) , d) .

EQUATION

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 and Q: 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 w i ∼ 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

[-C w , C w ] or [-C b , C b ],

and thus is even.

Next, to bound E[|U |], we apply the Marcinkiewicz-Zygmund inequality with p = 1, using the optimal A 1 from Lemmas 8 and 9, to get that

E[|U |] ≥ C w 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| √ 2N w u .

4. NUMERICAL SIMULATIONS:

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 from N (0, σ 2 w /k), and biases from N (0, 0.01 2 ). In the sparse-Uniform networks, non-zero weights are sampled from 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 Figure 3 : Expected growth factor, that is, the expected ratio of the length of any very small line segment in layer d + 1 to its length in layer d. Figure 3a shows the dependence on the variance of the weights' distribution, and Figure 3b shows the dependence on sparsity. 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 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.

U(-C/ √ k, C/ √ k),

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.

5. CONCLUSION:

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.

A SUPPORTING LEMMAS:

Lemma 1. Let f X (x) be an even joint probability density function over random vector X ∈ R k . Let A ∈ R k×k be an invertable linear transformation such that Y = AX. Then the joint density f Y (y) is also even.

Proof. Wlog we assume f X is defined on R k . To calculate the density over Y ∈ R k we make a change of variables such that

EQUATION

)

Since A is one-to-one, we have that f X (x) = f X (A -1 y) for some y, and f X is even, so y )) for all y. Putting this together completes the proof,

f X (A -1 y) = f X (-(A -1 y)) = f X (A -1 (-

EQUATION

)

Lemma 2. Let f X (x) be an even joint probability mass function over random vector X ∈ R k . Let A ∈ R k×k be an invertable linear transformation such that Y = AX. Then the joint mass function f Y (y) is also even.

Proof. f X 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

EQUATION

)

Since A is one-to-one, we have that f X (x) = f X (A -1 y) for some y, and f X is even, so y )) for all y. Putting this together completes the proof,

f X (A -1 y) = f X (-(A -1 y)) = f X (A -1 (-

EQUATION

Lemma 3. Let f X1,...,X k (x 1 , . . . , x k ) be an even probability density function.

Then f X1,...,X k-1 (x 1 , . . . , x k-1 ) = ∞ -∞ f X1,...,X k (x 1 , . . . , x k )dx k is also even. Proof. f X1,...,X k-1 (x 1 , . . . , x k-1 ) = ∞ -∞ f X1,...,X k (x 1 , . . . , x k )dx k = ∞ -∞ f X1,...,X k (-x 1 , . . . , -x k )dx k = ∞ -∞ f X1,...,X k (-x 1 , . . . , -x k-1 , x k )dx k = f X1,...,X k-1 (-x 1 , . . . , -x k-1 )

The first and last equalities follow from the definition of marginalisation of random variables. The second equality follows from the assumption that f X1,...,X k is even, and the third equality follows from the change of variables: -x k -→ x k .

Lemma 4. Let X 1 , . . . , X k be discrete random variables with symmetric support sets X 1 , . . . , X k respectively, i.e. x i ∈ X j ⇐⇒ -x i ∈ X j . Let P (X 1 = x 1 , . . . , X k = x k ) be an even probability mass function such that P (X

EQUATION

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 -x k is equivalent to summing over x k .

Lemma 5. Let X and Y be random variables with an even joint probability density function

f XY (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 f ZY (z, y), which works out to be

f ZY (z, y) = f XY (z, y) + f XY (-z, y)

for z ≥ 0 and y ∈ R. Then we have that

E[Z|Y > 0] = ∞ 0 z • f Z|Y >0 (z|y > 0)dz = ∞ 0 z • f Z,Y >0 (z, y > 0) ∞ 0 f Y (y)dy dz = 2 ∞ 0 z • f Z,Y >0 (z, y > 0)dz = 2 ∞ 0 z ∞ 0 f ZY (z, y)dydz = 2 ∞ 0 z ∞ 0 (f XY (z, y) + f XY (-z, y))dydz.

One the other hand, we have that

E[Z] = ∞ 0 z • f Z (z)dz = ∞ 0 z • (f X (z) + f X (-z))dz = 2 ∞ 0 z • f X (z)dz = 2 ∞ 0 z • ∞ -∞ f XY (z, y)dydz = 2 ∞ 0 z • 0 -∞ f XY (z, y)dy + ∞ 0 f XY (z, y)dy dz

Comparing the expressions for E[Z|Y > 0] and E[Z], we can see that they are equal if

0 -∞ f XY (z, y)dy = ∞ 0 f XY (-z, y)dy.

A change of variables on the left hand side from y to -y yields

0 -∞ f XY (z, y)dy = ∞ 0 f XY (z, -y)dy.

and by assumption, we know that f XY (z, -y) = f XY (-z, y) since f XY is even, which completes the proof.

Lemma 5 implicitly makes use of the fact that P (Y = 0) = 0, which follows from w J i and bi being continuous random variables, and Y = w Ji z Ji + bi , with z Ji being fixed independent of w Ji . 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 := [w Ji , bi ], the concatenation of w Ji and bi , and ẑ := [z Ji , 1], the concatenation of z Ji and 1, such that Y = v ẑ. Associated with the discrete distribution over v there are N |Ji| w N b possible discrete random vectors in R |Ji|+1 . The set of vectors ẑ ∈ R |Ji|+1 orthogonal to such a discrete set is measure zero, and as such for ẑ fixed independent of the choice of the discrete measure v we have P (v ẑ = 0) = 0. If however ẑ were selected with knowledge of the discrete distribution v then one of two cases will occur; either v ẑ = 0, or ẑ is selected to be from the measure zero set of vectors orthogonal to any of the N |Ji| w N b 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 N b vectors generated by v to which that particular ẑ 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 f XY (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 f ZY (z, y), which works out to be f ZY (z, y) = f XY (z, y) + f XY (-z, y) for (z, y) where z ∈ X + and y ∈ Y f XY (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

EQUATION

= 2

EQUATION

On the other hand, we have Lemma 8 (Marcinkiewicz-Zygmund Inequality (Ferger (2014) )). Let X 1 , . . . , X n 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 A p and B p depending only on p such that

EQUATION

Lemma 9 (Optimal constants for Marcinkiewicz-Zygmund Inequality (Ferger (2014) )). Let Γ denote the Gamma function and let p 0 be the solution of the equation Γ( p+1 2 ) = √ π/2 in the interval

(1, 2), i.e. p 0 ≈ 1.84742. Then for every p > 0 it holds:

EQUATION

and

B p,opt = 1 0 < p ≤ 2 2 p/2 • Γ( p+1 2 ) √ π , 2 < p < ∞ (42) Lemma 10. Let X = i α i w i , where w i ∼ U(-C, C) Then E[|X|] ≥ C 2 √ 2 α

Proof. Defining X i = α i w i , we can then apply the Marcinkiewicz-Zygmund inequality with p = 1, using the optimal A 1 from Lemma 9 to get that

E[|X|] = E k i=1 X i ≥ 1 √ 2 E   k i=1 X 2 i  

Next we use the same tricks as early in the proof of the Gaussian case:

1 √ 2 E   k i=1 X 2 i   = 1 √ 2 E   k i=1 |X i | 2   ≥ 1 √ 2 k i=1 E[|X i |] 2 ,

where the first equality is trivial and the second follows from a repeated application of Jensen's inequality.

To calculate

EQUATION

E[|X i |] = C|α i | 2 and so E[|X|] ≥ 1 √ 2 k i=1 E[|X i |] 2 = 1 √ 2 C 2 4 k i=1 |α i | 2 = C 2 √ 2 α

Lemma 11. Let X = i α i w i , where w i are uniformly sampled from some discrete symmetric sample space W. Then

E[|X|] ≥ w∈W |w| √ 2N w α

Proof. Defining X i = α i w i , 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[|X i |] 2 .

To calculate E[|X i |] we note that X i = α i w i is uniformly sampled from α i W and thus

E[|X i |] = |α i | w∈W |w| N w

and so

E[|X|] ≥ 1 √ 2 k i=1 E[|X i |] 2 = 1 √ 2 ( w∈W |w|) 2 N 2 w k i=1 |α i | 2 = w∈W |w| √ 2N w α

Lemma 12. Let W, X ⊂ R k be discrete sets with finite cardinality, and g : W -→ X be a oneto-one transformation. Then if P (W = w) = P (W 1 = w 1 , . . . , W k = w k ) = 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

EQUATION

used in (13) in Stage 3 of the proof of Theorem2. It is straightforward to derive an upper bound for this same quantity, as

EQUATION

first using Jensen's inequality to get that E Ji [ dz Ji 2 ] ≤ E[ dz Ji 2 ], and then using the strategy from the proof of Lemma 7 to get E[ dz Ji 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 ∈ R k , and average over subvectors dz Ji . Specifically, we calculated the expected value of a subvector dz Ji containing only the entries of dz indexed by J i , where J i ⊆ {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 Figure 4 : The dependence on α and k of expected value of a subvector dz Ji . In Figure 4a , dz is a realisation of the uniform distribution over the unit sphere. In Figure 4b , dz has the first entry equal to 1, and the rest zeros.

tight, by letting dz have only a single non-zero entry, which case E[ u J ] = α 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 . Figure 5 : Expected growth factor for trajectories joining randomly chosen (normalised) points in R 500 . Figure 5a and Figure 5c show the dependence on the standard deviation of the weights' distribution for a straight and curved trajectory respectively, and Figure 5b and Figure 5d show the dependence on sparsity with a straight and curved trajectory respectively. In this experiment we have chosen as the curved trajectory a straight line which has been modified to be a semi-circular arc in 100 randomly chosen hyperplanes.

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) ), l 0 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. 

:

In this experiment we chose the 101 st and 1001 st points from the MNIST test set, but the choice of points does not qualitatively change the results.

Figures and Tables:

Figure 1: A circular trajectory, passed through a ReLU network with σ w = 2. The plots show the pre-activation trajectory at different layers projected down onto 2 dimensions.

Figure 2: Expected length of a line connecting two MNIST data points as it passes through a sparse-Gaussian deep network, plotted at each layer d.

Further work on quantifying the probabilistic concentration of E[ u J ] close to √ α u would be an interesting extension of this research.

Figure 6: Expected growth factor for trajectories passed through trained feedforward ReLU networks trained on MNIST.

Peer review (iclr2020):
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. I give an initial rating of weak accept because (1) the paper is well written and well-organized. (2) the numerical simulation results support the claims and proofs. (3) the investigation on sparsely connected networks seems timely. However, I*m not an expert in this area. It also seems that most derivation and insights are from previous literature Raghu 2017, which makes the contribution of this submission limited. I have a question which may be invalid. For Figure 3, the observed expectation matches perfectly with the the lower bound for all three distributions. This seems amazing, have the authors try with other dataset or other settings to do this experiment? Did it always match perfectly?