Trajectory growth through random deep ReLU networks
Authors: Ilan Price
Jared Tanner
Venue:  (2020)
Keywords: Deep networks
expressivity
trajectory growth
sparse neural 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.

Under review as a conference paper at ICLR 2020
TRAJECTORY GROWTH LOWER BOUNDS FOR RANDOM SPARSE DEEP RELU NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper considers the growth in the length of one- me--iimensional 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 re- sults, providing an alternative, simpler method for lower bounding expected tra- jectory growth through random networks, for more general class of weights dis- tributions, including sparsely connected networks. We illustrate this approach by deriving bounds for sparse- Gaussian, sparse-uniform, and cearss-ddsceet--valuus random nets. We prove that trajectory growth can remain exponential in depth with these new distributions, including their sparse variants, with the sparsity pa- rameter appearing in the base of the exponent.
INTRODUCTION
Deep neural networks continue range of tasks, and are the basis for many algorithms we use routinely and on a daily basis. One fun- damental set of theoretical questions concerning deep networks relates their expressivity. There remain different approaches to understanding and quantifying neural network expressivity. Some results take classical approximation theory approach, focusing the relationship between the chitecture of the network and the classes of functions it can accurately approximate (Lu et al. (2017);
benchmarks for machine learning accuracy across wide
Cybenko 1992); Hornik 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 disentangle manifolds. Other works concentrate specifically on networks with piecewise linear activation functions, using the number of linear regions (Montufar al. (2014) or the volume of the boundaries between linear regions (Hanin) & Rolnick (219)) input space. In 2017, Raghu al. (017)) proposed trajectory length mea- one-dimensional trajectory as it passed through Gaussian random neural networks (see Figure for illustration). Their primary theoretical result was that, expectation, the length of a one-dimensional trajectory which is passed through fully-connected, Gaussian network is lower bounded by factor that is exponential with depth, but not with width.
sure of expressivity; in particular, they consider the expected change in length
122
-10
-12
-1--
411
-1.
-22
-30
-05
(a) Input
(b) Layer
(c) Layer
Figure 1: A circular trajectory, passed through ReLU network with ow 2. The plots show the pre-activation trajectory at different layers projected down onto dimensions.
One-dimensional trajectories and their evolution through deep networks are also interest in their right because they constitute simple data manifolds. Firstly, commonly assume that the real

---

Under review as a conference paper at ICLR 2020
data which we aim to correctly classify predict with deep network lie more manifolds, and thus design a network to perform appropriately on such a manifold. Secondly, researchers are beginning consider whether the output (manifolds) of generator networks could be good model for real word data manifolds, for example, as priors for a variety of inverse problems (Manoel et al.) (2017): (Huang al. (201)). Both of these hypotheses motivate understanding of how manifolds are acted upon by deep networks.
Our results in this paper pertain specifically the 'trajectory length' measure of expressivity. We produce 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 new contexts of interest. For example, there 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 (211)): 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 extend results from dense random networks to sparse ones. It also allows us to consider the other weight distributions of and sparse-discrete networks (see Definitions 2
sparse- sparse-uniform
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 (Corol- laries
3. We observe that the expected length growth factor is strikingly similar across the aforemen- tioned 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 the d-th post-activation layer as z(d), and the subsequent pre-activation layer ((d), such that
(d) = (d) + b(69, (d++)) = (h((2))
where (xx) == max(x, 0) is applied elementwise. We denote 20)
We use [N P, Q) to denote random feedforward deep neural network which takes as input the vector x, and parameterised by random weight matrices (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 o, denoted JNN( a; 2), is a random feedforward network in which all weights are sampled from a mixture distribution of the form
Wij ~ aP + (1
where 8 the delta distribution O, and P is some other distribution. In other words, weights are O with probability 1 a, and sampled from P with probability a. Biases are drawn iid from Q.
Definition 2. sparse-Gaussian network is a random sparse network fNN( Q), where
P = N(0,, oz)) and Q =N
Definition 3. A sparse-uniform network is random sparse network fNN Q), where P u( Cw., Cw)) and Q (d(-Cs,Caa Cb)-
Definition 4. A sparse-discrete network is random sparse network (x: a., P. Q). where P. is
a uniform distribution over a finite, discrete, symmetric set W. with cardinality W N and Q
uniform distribution a finite, discrete, symmetric set B, with cardinality [B] Nb-
2

---

Under review as a conference paper at ICLR 2020
For weight matrix W in random sparse network, with w; denoting the 1th row, define wp, as the vector containing only the P-distributed entries wi
We define trajectory x(t) in imput space curve between two points, say and ø1, parameter- ized by scalar E [0, 1], with z00) zo and æ=1) 21, and define (x(()) 2(4) to be the image of the trajectory in layer d of the network. The trajectory length (xx(t) is given by the standard are length,
.. (x((t)
dt.
dt
As in the work by Raghu al. (2017), this paper considers trajectories with z0 + dt) having non- trivial component perpendicular to (() for all 1, dt.
Finally, say probability density mass function fx (3)) is even if fx(-x) fx(x) for all random vectors x in the sample space.
EXPECTED TRAJECTORY GROWTH THROUGH RANDOM NETWORKS
Raghu et al. (2017) considered ReLU and hard-tanh Gaussian networks with the standard deviation scaled by 1/Vk. Their result with respect to ReLU networks captured in the following theorem.
Theorem (Raghu et al. (001))). Let (x; NO0, oa./////))))))) NO), of)) be a random Gaussian deep ReLU neural network with layers of width then
ow OwVk
E[(( (4) (t)) (+))
20
-(x(tt),
+I+
for r:() a I-dimensional trajectory in input space.
There are, however, other network weight distributions which may be of interest. For example, the expressivity and generative power sparse networks are particular interest the current mo- ment, 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 al. (2019)). We prove that even for sparse random networks, trajectory growth ficiently large initialisation scale dw- Scaling a by 1/vī can yield width-independent lower bound on this growth. Moreover, a sufficiently high sparsity fraction (1 a) results in a lower bound which, instead of growing exponentially, shrinks exponentially zero. This is captured by the following result.
remain exponential depth given suf-
Corollary (Trajectory growth in deep sparse-Gaussian random networks). Let fN a. (O, of NNO, af)) be a sparse-Gaussian, feedforward ReLU network as defined in Section 1.1 with layers of width k. Then
a0 V
BI((2 (+))
-((((t),
(I)
/2T
for x(() a I-dimensional trujectory input space.
Corollary with a and aw replaced by aw / V recovers bound which is very similar to the prior bound by |Rahuu et (2017) in Theorem
Beyond Gaussian weights, ing and analysing deep networks. Uniform distributions, for example, still constitute the default initialisations, of linear network layers in both Pytorch and Tensorflow (uni- form according to U(-1/VR, in the case of Pytorch, and uniform according to u(-6/vk. kout, 6/ B/v + kout) a.k.a the Glorot/Xavier uniform initialization (Glorot & [Beniio (2010)) the case of Tensorflow). We prove an analogous lower bound for uniformly distributed weights.
consider other distributions commonly used for initialis-

---

Under review as a conference paper at ICLR 2020
Corollary 2 (Trajectory growth in deep sparse-uniform random networks). Let fNN( a, C Cb)) be a sparse-Unifora Uniform, feedforward ReLU network as defined in Section 1.1 with layers of width k. Then
(aCw vk d 4v2
BL( (1))
((((1)),
for xr() a 1-dimensional trajectory in input space.
Another research direction which has gathered some momentum in recent years are quantized or sicrete-valued deep neural networks (Li et al. (2 Hubara et al. (2016) 2017h), including recent work using integer valued weights (Wu al. (2018). This motivates consideration of discrete weight distributions, in addition to continuous ones. As an example of such, we prove 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( a, P)Q) be a sparse-discrete random feedforward ReLU network as defined in Sec- tion 1.1 and layers width k. Then
avk 2V2
Evew |u]| 1
EI(( ( (1))
((x(t))
No
for xrf) a 1- 1-dimensional trajectory in input space.
In all cases these lower bounds show how to choose the combination of aw and a to guarantee (or not) exponential growth in trajectory length in expectation at initialisation.
The main idea behind the derivation of these results is consider how the length of a small piece of trajectory (some [|d=(<) ()) grows from layer the (]d22(41)] [1 d()) ((h(") (t)l)- In the context of random feedforward networks, activation functions restrictions of d to partieular support set which is statistically dependent on (d), This approach a more direct and more generally applicable way of accounting for this dependence than originally provided by Raghu al. (2017) Specifically, our approach lets derive the following, more general result, from which Corollaries 1
consider piecewise linear
developed by Raghu et al. (2017). The key to proof is providing
easily.
Theorem 2 (Trajectory growth in deep random sparse networks). Let NNN a, P, Q) be random sparse network as defined in Section 1.7 with layers of width k. Let P and Q be such that the joint distribution over vector of independent elements from both distributions even. If Ellu up, 2 MM]uu| for any constant vector u, for all i, then
(aMVk d
(1)
((x((()
for x(() a I-dimensional trajectory in input space.
Remark. It is trivial amend this result for networks where the width, distribution, and sparsity varies layer by layer, in which case the lower bound (4p is replaced by
aa kg
II
I[((())
2
j=i
Moreover, the bounds from Theorem and Corollaries -
hold true in the bias case as well.
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) break this dependence by taking advantage of the symmetry characterising this class distributions. Supporting lemmas can be found in Appendix A.

---

where W. IR Alik is the matrix comprised of the rows of W indexed by A, and we denote the i-th row of W as wi and the i-th entry as b,. E i...d,, and A(d) selects all entries whose corresponding entries in k(d) have positive values. Thus, expectation, pre-multiplying by the matrix Lats is equivalent to considering W (dz(d) instead of Under review as a conference paper at ICLR 2020
Proof. Stage 1:
For the first stage of proof, we will closely follow Raghu et al. 2017 ). We are interested in deriving lower bound of the form,
de dz(a)
f.
dx((t)
E
dt
2 C.
dt,
(5)
dt
dt
for some constant C. As noted by Raghu et (2017). suffices to instead derive a bound of the form
[Ide (t)ll 2 Cl]dx(ttll,
E
since integrating over yields the desired form. Our approach will be derive a recurrence relation between ||dz(+1]]]| and |dz]/)]], where refrain from explicitly including the dependence of dz on t, for notational clarity.
Next, like Raghu et (2017) our proof relies on the observation that dz (d+1) = =(W(1)) (d)) (t+ 8t) + b()) - (1)
ald)(t + ōt) - x(00((
and that since the ReLU operator,
de either or When 2 (d) is fixed independently of di
W(d) and 6649, then p(h (d) = 0) = 0 (see the preamble to Lemma 6 for more detail on this), and
thus we need only note that d (d) dh (d) when n/ 0, and dØp 0 when hg < 0. We
define (d) be the set of 'active nodes' in layer specifically,
A bi : n 0}:
and LAt E B is defined the matrix with ones the diagonal entries indexed by set A(d) and 0 everywhere else. We can then write
(d+)()+1]] A (1 dt) - h (4) (t)II
A ((d) de (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 weight matrix after rotation has the same, i.i.d. distribution as the matrix before rotation. Instead, our proof can tackle number of other, conn-rtatiioally-invaal distributions, as well as sparse networks.
Stage 2:
The next stage of the proof begins by noting that after conditioning size of the set A,
Ell Ld [A]] = E[]l (d) w. (d) + b, > 0 vi, [A]]
(6)
since the elements of W (d) are
I (d) together with conditioning on the fact that every element in the vector (2)d) positive.
5

---

Under review as a conference paper at ICLR 2020
This gives us
LA d2
E
(ú, dz(d))2
8 (d) b. 14
(7)
101 10g
E 10g
18
Σ k d2(0)/
10 2(1) + > 1400 AA
(8)
LA]
2
E
100 2(10 + > 0/2 E [1 dz(0)
(9)
where 77) follows from the analysis above and the independence of each wùt (8) is trivial, and ( follows from iteratively applying Jensen's 's inequality, after noting that f(z) x2 C is convex for x. C 2 O.
Now let Jj denote the (random) index set of the P-distributed entries of w; and let W., dzy, 2J, denote the restrictions the indices in Jr of vi (z(d) and z(d) respectively. Then vi 2(d)
(d)
T (d) J, *J, and úi dz(d) = w dzyz
(d) such that, after conditioning on Ji we have that
LAI 2
B||[Wp|| 2(4) + b. OV,,
2
[[
d= (2)
|wo =J, by > 0, Jil
(d)
(+)
(****
(10)
Stage 3:
The third stage of the proof to work our way from the inside out, lower bounding (+) first, then (x+), and finally (* +).
Consider the expectation in (+). Having conditioned on J, we can define = w., dz and
w (d) J. + b, such that lower bounding (*) means lower bounding
E E| Y 00.
(11)
By assumption the joint distribution over G [W] WJ,kk, b.] is even. The vector H [X, Y, WJ., ... k. 6.]T is obtained by linear transformation of G (which is invertible since || is not parallel to []) Thus by Lemma ] (continuous) or Lemma 2 (discrete) this joint distribution over is also even, and by Lemma (continuous) or Lemma (discrete), the joint distribution of [X, T is even too. We can therefore apply Lemma (continuous) or Lemma (discrete) and need only consider E[[ X]]. which is bounded as
E X 2 M(|dz),) (d) II.
(12)
again by assumption.
Having bounded (*), we average over to get (**), for which we can apply Lemma to get
|[M||d2 ||| 2 aM (1)
(13)

---

Under review as a conference paper at ICLR 2020
Finally, can bound (* +) follows
E|ll We
(d)
E [A
Σ a Q2M22 M2
(14)
VIAI a2M22 (2
E
(15)
[
E [A] v VkaM |2(0) 1laMad
|Al aAl-a" a 12
(16)
aM aM (2 B[[AA]]
(17)
where (14) is obtained by substituting the bound for (**) into the inequality in 10 15 follows since there is no dependence i in the summed terms, and (16) follows since for any 0 s < Vmaztr) 7/5 and [A]] is at most k.
max(7): /7 2
The proof concluded by calculating [[[A]]- Since |A| is the number of entries in the vector / (d) which are positive, and each entry in that vector is 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 [d and [|dz(d]].
aMVk |d
El|ld2 (1+))
2
Iterative application of this result starting at the first layer yields the final result.
Let us illustrate the ease with which Corollaries and are obtained. In the case of each distri- bution, 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 independent elements from both distributions is even. Second, must derive bound of the form El|u w|) > M|[u||, where w. ~ P, and substitute M into Theorem
When P and Q centred Gaussians, the joint distribution elements from or both distri- butions is a multivariate Gaussian, with an even joint probability density function. Moreover, for U ur [B[ has closed form solution,
20 a
B||
|u|l
TT
When P and Q are centred uniform distributions, the joint distribution uniform over the polygon bounded in each dimension by the symmetric bounds [-Ows Cw] or [-C,, Co). and thus is even. Next, to bound E[[U']]. we apply the prrrinkkewiee-Zyygmae inequality with p 1. using the optimal A₁ from Lemmas BaanmasSSan and to get that
C 2
B[JU
>
|u]|:
for details of this derivation, Lemma 10
Likewise, when P and Q are uniform distributions over discrete, symmetric, finite sets W and respectively, make discrete analogue of the argument made in the continuous uniform to confirm the necessary assumption holds. Bounding E[[ in this case also follows from a very similar argument that made in the continuous case, detailed in full in Lemma yielding
E|U Enew |w0
|u|].
V2N

---

Under review as a conference paper at ICLR 2020
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 D-P To this end, we use as our trajectory a straight line between two (normalised) MNIST datapoints discretized into 10000 pieces. For each combi- nation 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 net- works types, sparse- Gansss-, sparse-uniform, and sparse-discrete networks, from Definitions 2 respectively. For each distribution we consider different values of network fractional density a rang- ing from 0.1 to 1. In the sparse-Gaussin Gaussian networks, non-zero weights sampled from from.N(0. (O, o k), and biases from (0, 0.01²). ). In the sparse- Uniform networks, non-zero weights are sampled from U(-C/Vk, C/vk), and biases from (0.0.1 0.01). In the sparse-discrete discrete networks, non-zero weights are uniformly sampled from W := (1/vk) @ (-C, -CC 1)..... C - 1, C), and biases from B 0.00,, We do this for a variety of aw and C' values. The results are shown in Figures and
0.9
0.3
10
10
Figure 2: Expected length of line connecting two MNIST data points as it passes through sparse- Gaussian deep network, plotted at each layer d.
Figure 2 plots the average length of the trajectory at layer d of sparse-Gaussian Gaussian network, with 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 a (higher sparsity). In Figures 3a and
3b we plot the growth ratio of small piece of the trajectory from one
12.5
2.0
Sparse Gaussim
S Spazse Gaussiau Spazse uniform
10.0
Sparse unidoru
1.5
Sparse discrete
Sparso disemit
1.0
5.0
2.5
0.5
0.0
0.0
5
10 16
20
0.2
0.4
0.6
0.8
1.0
(a)
(b)
Figure 3: Expected growth factor, that is, the expected ratio of the length of any very small line segment in layer d 1 its length layer d. Figure [3 shows the dependence the variance of the weights' distribution, and Figure shows the dependence on sparsity.
layer to the next, averaged over all pieces, at all layers, and across all 100 networks for given distribution. This ([]]d(((+))]]]] bound. The solid lines reflect the observed averages of this ratio, while the dashed lines reflect
corresponds to the base of the exponential in our lower
In this experiment chose the 101 and 1001 points from the MNIST test set, but the choice of points does qualitatively change the results.
8

---

Under review as a conference paper at ICLR 2020
the lower bound from Corollaries and Figure 3a illustrates the dependence on the standard deviation of the respective distributions (before scaling by 1/vk), with fixed at 0.5. We observe both that the lower bounds clearly hold, and that the dependence on ow is linear in practice, exactly as expect from our lower bounds. Figure 33b shows the dependence of this ratio the sparsity parameter a, where we have fixed o = 2 for all distributions. Once again, the lower bounds hold, but in this case there is 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 discussed in more depth Appendix B
One striking observation in Figures 3a and 3b is that for a given |[]ld=/4+D1///]d [|] matches perfectly across all three distributions, for different values of ow and different a. This remains true when repeat the experiments with different datapoints, and with points chosen uniformly at random in a high-dimensional space, both when the trajectory con- sidered is straight line and when is not (e.g.
the observed
in two or more dimensions.) See Appendix C.I 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 ex- ample, Figure 3b considers the initialisation scheme with dw 2/V We see that the empirically observed growth factor from one layer to the next is approximately 1.5 when the matrices are dense (a- = 1), while the growth factor is with a Rs 0.5, and less than one as a 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 roughly linear dependence dw- However, this expected growth factor is not the same size in random nets as it is in trained nets with the same ow, nor is the expected growth factor trajectory independent in trained networks, as it is for random networks.
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.
REFERENCES
Alireza Aghasi, Afshin Abdi, Nam Nguyen, and Justin Romberg. Net-trim: Convex pruning of deep neural networks with performance guarantee. Advances in Neural Information Processing Systems, pp. 3177-3186, 2017.
Subutai Ahmad and Luiz Scheinkman. How can we be so dense? the benefits of using highly sparse representations. arXiv preprint 1rX3. 2019.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con- trol, Signals, and Systems (MCSS), 5(4): 1992.
Dietmar Ferger. Optimal constants in the marcinkiewicz-zygmnnd inequalities. Statistics & Prob- ability Letters, 84:96-101, 2014.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:// openreview net
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, 249-256, 2010.
William H Guss and Ruslan Salakhutdinov. On characterizing the capacity of neural networks using algebraic topology. arXiv preprint arXiv: 1802v 04443, 2018.

---

Under review as a conference paper at ICLR 2020
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learning, pp. 2596-2604, 2019.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359 366, 1989.
Wen Huang, Paul Hand, Reinhard Heckel, and Vladislav Voroninski. A provably convergent scheme scheme for compressive sensing under random generative priors. arXiv preprint arXiv: /8/2.04/76 2018.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in neural information processing systems, pp. 4107-4115, 2016.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- El-Yaniv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Jour- nal of Muchine Learning Research, 18(1 18(1):686-6888, 2017.
Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. In Advances in Neural Information Processing Systems, pp. 11815811881 2017.
Christos Louizos, Karen Ulirich, and Max Welling. Bayesian compression for deep learning. In Advances in Neural Information Processing Systems, pp. 3288-3298, 2017.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In Advances in neural information processing systems, pp. 6231-6239, 2017.
Andre Manoel, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Multi-layer generalized linear estimation. In 2017 IEEE International Symposium on Information Theory (ISIT), pp- 2098-2100 IEEE, 2017.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 2498-2507. JMLR. org, 2017.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp. 2924-2932, 2014.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Diekstein, and Surya Ganguli. Expo- nential expressivity in deep neural networks through transient chaos. In Advances in Neural Information Processing Systems 29, pp. 3360-3368. 2016.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 2847-2854. JMLR.org, 2017.
Shuang Wu, Guoqi Li, Feng Chen, and Luping Shi. Training and inference with integers in deep neural networks. International Conference on Learning Representations, 2018. ht d=HJGXzmapb
//openreview.net.o.
Haichuan Yang. Yuhao Zhu, and Liu. Energy-constrained compression for deep neural networks via weighted sparse projection and layer input masking. In International Conference on Learning Representations, 2019. URL https://///cm....t. wttpr//ewweeeeeeeeeeeeeeeeeeeaaa
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv: 2017.
10

---

Under review as a conference paper at ICLR 2020
A SUPPORTING LEMMAS
Lemma 1. Let fx(x) be an even joint probability density function over random vector X E R Let A E B an invertable linear transformation such that Y =AX. Then the joint density fyl is also even.
Proof. Wlog we assume /x is defined on R To calculate the density over Y E R we make a change of variables such that
fr(y) = (())==x(A->>1AA1
(18)
Since A is one-to-one, we have that (x) fx fx(A- for some y, and fx is even, so [x y)) = fx (x(-(A-))) - -x (- for all y. Putting this together completes the proof,
fr(y)
/x(4 (x fr(-x)
(19)
L
Lemma 2. Let fx( be even joint probability mass function over random vector X E Rt Let E & be an invertable linear transformation such that Y AX. Then the joint mass function (y) is also even.
Proof. fx is defined on some discrete, finite, symmetric set X. To calculate the density over Y e y := {Ap: p E X) we make a change of variables such that
fr
Σ fx(x).
(20)
x6 (Ax=a)
Since A is one-to-one we have that fx (x)) fx(A-1y) for some y, and fx is even, so
fx(A = fx (-(-- (A (-y) for all y. Putting this together completes the proof,
fr(y)= = Σ Sx(A
Σ (-))
(21)
mE w)
#E (
Lemma 3. Lel ( be an even probability density function. (0l....;d)dda 2x) is also even.
Then
Nn- fx....X--
( (k-11) - Xx (2,....,
Proof.
fximiI (
(II,..., = fxim., Xx Xe (1
fximi.ee (- - xx ddrk
fximn (-I1, 0k Iok dx
-00
fx..... (-I1, -I--1)
The first and last equalities follow from the definition of marginalisation of random variables. The second equality follows from the assumption that fxi...,x is even, and the third equality follows from the change of variables: -xn - Ik.
Lemma 4. Let XI...., Xx be discrete random variables with symmetric support sets Xi...., X respectively, i.e. I; E X2 = -D; E X,. Let P Zi...., X, 2x) be an probability mass function such that P(Xi = -I...., X = 2x) P(Xi = - -I,,..., X -xx).
Then P(X1 21.... X =K--)) is also even.

---

Under review as a conference paper at ICLR 2020
Proof.
P(Xi
XR-1 = xk-1) = Σ
P(Xi I1,
Xx = =kk)
(22)
Σ
P(X1 -1,
Xx -Ik)
(23)
myEN
Σ
P(X1 -111 .,.....," = Ik)
(24)
Σ
P(X1 -1 xk Ik)
(25)
= P(X - Xx-1 -xb-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 -2 equivalent to summing over 2i.
Lemma Let X and Y be random variables with an even joint probability density function fxy v). Then
B[|x|| Y > 0] = [[
Proof. Letting X = Z, we can make a straightforward change of variables to calculate the joint distribution /2y y). which works out to be
fzr (2, fxy fxr (-2,g)
for 2 2 and y E R. Then we have that
E 0J =
2 fzirso > 0)dz
Izv>o(z,y) > 0) dz
So fy fy(ddy
2
2 fzy > 0)dz
0
2
2
y)dydz
x
2
2
(fxy(2.)) v) + fxr 22
One the other hand, we have that
Z
2 fz(2)dz
(fx(2) fx(-2))dz
2
fx(2)dz
2. [ fxv (xy(2)))dyds
( [xr(2, 1 (xr(e.u)dy) dz
2
12

---

Under review as a conference paper at ICLR 2020
Comparing the expressions for E > 0] and E[Z], that they equal if
f (xy( J. fxy((2,y)dy.
A change of variables on the left hand side from y to yields
S fxr = Io fxr(2, v))d..
and by assumption, we know that (2, -y) - fxr(-zz since /xY is even, which completes the proof.
Lemma 5 limlicitly makes use of the fact that P(Y 0) 0, which follows from w', and 6, being continuous random variables, and Y w], zJ, b;, with zJ, being fixed independent of w.,, We similarly make use of the fact that P(Y 0) = 0 in the application of Lemma O though that this true is less immediately apparent in the discrete case. For clarity, let us define e [w,,, b.]. the concatenation of wJ, and 6, and == [a,,, 1], the concatenation of Z., and 1, such that Y 2. Associated with the discrete distribution over there are N No possible discrete random vectors in R M++++ The set of vectors & E R|4H+ orthogonal to such discrete set is measure zero, and as such for é fixed independent of the choice of the discrete measure we have P(n 2 = 0) 0. If however & were selected with knowledge of the discrete distribution v then one of two cases will occur; either T * 0, or is selected to be from the measure zero set of vectors orthogonal to any of the N.. 3:l N& vectors generated by In the latter case, the assumptions in Lemma 6 of y excluding would not be satisfied. In such an adversarial case there would be a discrepancy between X|| Y OJ and [|[ which would shrink as the proportion of the !.l N₂ vectors generated by 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 & V, and an even joint probability mass function fxY (x. y) such that P(X x. v) P(X =,,Y= -y). Then
B Y > 0] = [[]
Proof. Letting |X| Z, we can make change of variables obtain the joint mass function fzy (2,8), which works out to be
fx + fxr(-2,)) for (2,8) where E X and E y (2xy(2,))
fzr(z,
for (2,z) where 2 = 0 and e y
where X is the of all positive elements of X.
Next, we have that
BIZY > =
Σ =P(Z 2 0)
=EX+
P(Z = 122
Σ
(27)
P(Y > 0)
2 Σ = =
(28)
ZEXl
= 2 Σ Σ
=P(Z =
ZEXt WEy+
2 Σ
Σ
(fxy(z, + fxr(-2,9)
(29)
+ y
On the other hand, we have
13

---

Under review as a conference paper at ICLR 2020
E
Σ =P(Z = 2)
(30)
Σ (fx(2) + fx(-2))
(31)
=EX'
Σ 2fx(z)
(32)
SEX+
Σ
Σ
2fxy(2,1)
(33)
ZEX+ wEy
=2 Σ
Σ WEY!
2fxr(z,U)+ + Σ =(
(34)
seX!
NEY
Next, we not that
Σ =fxr(2,8) Σ =ʃxv(z, -y)
VEY
NEY
= Σ
xfxx(-2.2)
VE)*
Thus the expressions 29 and 34 are equal, which completes the proof.
Lemma 7 (Expected norm of a random sub-vector). Let u E R be a fixed vector and let J S .k, be random index set, where the probability of any index from to k appearing in any given sample is independent and equal to a. Then, defining to be the vector comprised only of the elements of indexed by J, we can lower bound the expectation of the norm of this subvector by
Ey[[| ||ll 2 ai||all
(35)
Proof. First, bound the expectation of the norm in terms of the expectation of the squared norm as follows:
B u.
EE
(36)
jEU
2
(37)
|
jEJ
This follows because for any 0 S 7 S max (7), VT 2
Vmaa(>)) 7-
Next we note that ΣSE, u is exactly equivalent to Ek= u B,, a weighted sum of iid Bernoulli random variables B, with p = and so
E JEJ
2 ا
E
(38)
1=1
|||| a.
(39)
Substituting this into inequality 37 completes the proof,
E
u
||]
2
a [u|
Lemmas 8 and 9 are taken from Ferger (014), and are restated here for completeness.
14

---

Under review as a conference paper at ICLR 2020
Lemma 8 (Mariinkewwccz-Zyymmml Inequality (Ferger (2014 Let X1...., X,, be N in- dependent and centered real random variables defined on some probability space (2, P) with [||X]]]] < for every i {1,..., n and some 0. Then for every p 2 1 there exist positive constants Ap and Bp depending only on such that
2/2
P/2
A
X?
Σ
X
S B
x?
(40)
Lemma 9 (Optimal constants for Barrinkiewiez-Zygmmmn Inequality (Ferger (001 Let I de-
note the Gamma function and let po be the solution of the equation I (2:1 (1, 2), i.e. xe 1.84742. Then, for every p > it holds:
/2 the interval
2P/2 1
0 0<pSp p0
Ap. p.opl
2p/2
Pu <
(41)
VT
1
2 2 <
and
1
0 0<p52
Bp.opt
I( 211
(42)
22/2
2 <<p<<0
V
Lemma 10. Let X = Ee a,w, where wi ~ uu C(-CCC) Then
C
B|X
||||
2V2
Proof. Defining X; = 0ky,0 we can then apply the Marcinkiewicz-Zygmund inequality with p 1,
using the optimal A from Lemma 9 get that
X| = X
Σ
X?
2
Next we use the same tricks early in the proof of the Gaussian case:
E
x?
E
X
1
B|I
2
where the first equality is trivial and the second follows from repeated application of Jensen's inequality.
To calculate [[[[X[]] we note that X, a,w, is uniformly distributed X; U(-la,/C, (aaaCC, and thus
C Clas
E X
2
and
k M
X >
E
1
2
C
k
|as12
V2
4
i=1
||||
2v2
15

---

Under review as a conference paper at ICLR 2020
Lemma 11. Let X Σ, ay where wi uniformly sampled from some discrete symmetric
sample space W. Then
Ewew |wi
E||
2
||||
V2N
Proof. Defining X; a,w, we follow exactly the same steps as in the first part of the proof of Lemma 10 to get that
&
X|
2
Σ
EI
V2
To calculate [[[ we note that X; W is uniformly sampled from a; W and thus
|as Enew |wl
B[|
N
and
X|
2
E x111
2
NEW |2cl)2
|ag12
2
N2
Σvew [
|||||
V2N
Lemma 12. Let W.X C & be discrete sets with finite condinality, and g W - X a one- to-one transformation. Then if P(W w) P(W, W1.... W4 wk) C for all e W, where C is constant, then P(X = x) = C for all X
Proof.
P(X x)
Σ we(o(w)=x}
P(W = w)
(43)
(44)
Equation is is a change of variables, and 44 follows from the fact the there is only ever one term in the sum, since g one-to-one.
B NON-LINEAR DEPENDENCE ON a IN THE TYPICAL CASE
One interesting observation which merits further detail is that the observed dependence of the growth factor on a in practice, shown in Figure 3b is not exactly linear, but rather the shape of that depen- dence looks closer Va. The likely source of this qualitative discrepancy is the of Lemma to lower bound
E,, ||| dz, [I]
al a||da/||
(45)
used in 13) in Stage 3 of the proof of Theoren this same quantity,
It is straightforward to derive an upper bound for
E,, [ |I| < Val|dz||,
(46)
first using Jensen's inequality get that E,, (v [æ,,, | < E1,, 2]. and then using the strat- egy from the proof of Lemma 7 to get E |2,, [| a |dz||2
16

---

Under review as a conference paper at ICLR 2020
To explore this discrepancy between the observed growth ratio and the lower and upper bounds from (43) and (46). we consider different fixed vectors dæ E RR, and average over subvectors day,- Specifically, we calculated the expected value of subvector dz containing only the entries of da indexed by J, where Jj S 2........ } 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 Figure44ashhows 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 /a||dz||. not a/| However, is also possible to construct an example where the lower bound is
Bounda
10
Baund
01.5
0.4
0.3
6.4
0.6
988
(a)
(b)
The dependence and ie of expected value of a subvector dz In Figure 4a de is realisation of the uniform distribution over the unit sphere. In Figure 4b dz has the first entry equal I, and the zeros.
Figure 4:
tight, by letting dz have only single non-zero entry, which case E[[ II] ai rull (see Figure 4b While the former case, with entries dz mostly of the same order, 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 [||ll|]] close to /all|u] would be an interesting extension of this research.
17

---

Under review as a conference paper at ICLR 2020
C ADDITIONAL NUMERICAL EXPERIMENTS
C.I
OTHER DATAPOINTS AND TRAJECTORIES WITH RANDOM NETWORKS
12.5
2.0
Sparse Gausiin
Sparso Ganseian
Eljldb B /11i=4000
10.0
Sparse uniãorm
1.5
Sparse uniform
Sparse diserete
Spurse discrete
7.5
1.0
5.0
0.5
2.5
0.0
5
230
0.8
(a)
(b)
12.5
Sperse Gaussian.
Spazse Gauasion
Sperse wilform
Sparso uniform
Sparse discrete
S Spazee disccete
7.5
2.5
5
15
20
0.2
0.1
0.6
0.8
1.0
(C)
(d)
Figure 5: Expected growth factor for trajectories joining randomly chosen (normalised) points in R5000 Figure 5a and Figure 5e show the dependence on the standard deviation the weights' distribution for straight and curved trajectory respectively. and Figure 5bland and Figure Sdl show the dependence on sparsity with a straight and curved trajectory respectively. In this experiment we have chosen the curved trajectory straight line which has been modified to be semi-circular are 100 randomly chosen hyperplanes.
show
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 different values of initill Gw, 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 aw 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 trajectories we pass through the trained networks (each pass through the 20 trained networks for each own and the growth factor averaged over all these networks). Each trajectory was then also passed through 20 random Gaussian networks of the same architecture order to compare the outcomes.
The results are shown Figure 6
Two key observations from Figure 6 consistent with Corollaries are that: there remains roughly linear dependence of a 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 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
18

---

Under review as a conference paper at ICLR 2020
joining points within the same class. However, trajectory growth can remain exponential in depth in both cases.
Figure 6bb shows individual results for individual lines passed through the 20 trained networks per initialization value o addition to the average behaviour shown in Figure 6a we observe that each path shows the same aforementioned key observations of path length having dependence proportional to ow- 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 post- training ow and trajectory growth factor over twenty trained networks, each curve in Figure 6b thus corresponds to one trajectory, for varying values of ow. The variance, over the 20 trained networks, of both computed values ppost-training ou 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 statistically significant difference between the expected growth factors for different trajectories. The consistency across different trained networks for each given trajectory is remark- able given the different random initializations of the networks. Moreover, however, the gaps between the plots for different trajectories illustrates key different between trained and untrained networks: in trained networks, the growth factor is seneectory-deeeddeet 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 consis- tency across the many hyperparameters involved in such experiments; for example, which sample pairs of points used, what trajectory shape, what regularisation is used during training. Sim- ilarly, potential experiments on trained sparse networks may be influenced by the choice of method for imposing sparsity the trained network (e.g variational dropout (Molchanov al. (2017)), lo regularization (Louizos et al. (2017), or magnitude pruning (Zhu & Gupta (2017)). Such an ex- pansive numerical investigation is beyond the scope of the focus of this paper, but may serve as an interesting alternative direction of inquiry.
Poan from tame daseee Poans from ffteent thoue
1.30
3.35
Points from diflerur classus
Points from class 1.0
Points from clsss 2.0
Points from cass 4.0
1.05
Points from
from
14
18
1's
206
19
12
14
1.
1.8
20
d
(a)
(b)
Figure 6: Expected growth factor for trajectories passed through trained feedforward ReLU net- works trained on MNIST.
19


Reviews:
[{"review_id": "rJen4nfhqB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: 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.\n\nStrengths: The paper is well-written and the proofs are clearly explained. I’m grateful that the authors specifically mentioned where their proof deviates from the original and they clearly delineate how their proof method extends Raghu (2017)\n\nWeaknesses: This is an interesting direction, but I do not believe there are enough results to constitute an accept. If the authors are following Raghu (2017), then I would have also liked to see analysis on trained networks as done in Raghu (2017) for example. I also think the title of the paper is too general for the specific results contained in the paper, namely sparsity should at least be mentioned in the title.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "r1xMfg2LKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nI 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. \n\nI 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? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HkxWMcyQtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, how the length of the trajectory in the input space is amplified by a ReLU neural network is analyzed. Specifically, the paper studied the case when the weights and biases are sparse random matrices. Some theoretical lower bounds are derived and are also empirically checked. \n\nThough the results are interesting, I am slightly lean to the rejection side. The main reason is that the motivation is not strong enough and it makes the entire work somehow incremental.\n\nAs described in the paper, the analysis of the trajectory length of NN has been initiated by Raghu et al. (2017). Although Raghu et al. considered the case of densely connected NNs, this work extended the notion to the sparsely connected NNs. I feel the extension is reasonable but it is not a big \"jump\" from the original work, and the originality is less significant. A good point of the derived results is that they are simple and easy to understand the dependency of the variance of the weights and the sparsity level. However, I am not so excited about these results because I cannot find a practical value from them. For example, (the current form of) Corollary 1 does not tell us how to control the sparsity level \\alpha to maintain some accuracy-sparsity tradeoff. \n\nFrom the technical side, it is nice the proof is written in line by line. However, it looks everything is done in a normal manner and nothing special happens. Also, the condition of Theorem 2 is unclear. What does the \"restriction\" of \\hat{w}_i mean? Does the condition E[] >= M ||u|| hold for any u and M? \n\nFinally, I have a simple question about the relationship between the scale of the output and the trajectory length. Let W be a weight and x be an input. When the smallest singular value of W is m, x is amplified at least by m, i.e., ||Wx|| >= m||x|| for any x. This means that (a part of) the trajectory growth is explained by the smallest singular value of the sparse random matrix W. Can you clarify the difference?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article studies the length of one-dimensional trajectories as they are mapped through the layers of a ReLU network, simplifying proof methods and generalising previous results on networks with random weights to cover different classes of weight distributions including sparse ones. It is observed that the behaviour is similar for different distributions, suggesting a type of universality. The reviewers found that the paper is well written and appreciated the clear description of the places where the proofs deviate from previous works. However, they found that the results, although adding interesting observations in the sparse setting, are qualitatively very close to previous works and possibly not substantial enough for publication in ICLR. The revision includes some experiments with trained networks and updates the title to better reflect the contribution. However, the reviewers did not find this convincing enough. The article would benefit from a deeper theory clarifying the observations that have been made so far, and more extensive experiments connecting to practice. 
Decision: Reject