ON THE EXPRESSIVE POWER OF DEEP NEURAL NET- WORKS
We study the expressive power of deep neural networks before and after training. Considering neural nets after random initialization, we show that three natural measures of expressivity all display an exponential dependence on the depth of the network. We prove, theoretically and experimentally, that all of these measures are in fact related to a fourth quantity, trajectory length. This quantity grows exponentially in the depth of the network, and is responsible for the depth sensitivity observed. These results translate to consequences for networks during and after training. They suggest that parameters earlier in a network have greater influence on its expressive power – in particular, given a layer, its influence on expressivity is determined by the remaining depth of the network after that layer. This is verified with experiments on MNIST and CIFAR-10. We also explore the effect of training on the input-output map, and find that it trades off between the stability and expressivity of the input-output map.
1 INTRODUCTION
Neural network architectures have proven “unreasonably effective” (LeCun, 2014; Karpathy, 2015) on many tasks, including image classification (Krizhevsky et al., 2012), identifying particles in high energy physics (Baldi et al., 2014), playing Go (Silver et al., 2016), and modeling human student learning (Piech et al., 2015). Despite their power, we have limited knowledge of how and why neural networks work, and much of this understanding is qualitative and heuristic.
To aim for a more precise understanding, we must disentangle factors influencing their effectiveness, trainability, or how well they can be fit to data; generalizability, or how well they perform on novel examples; and expressivity, or the set of functions they can compute.
All three of these properties are crucial for understanding the performance of neural networks. Indeed, for success at a particular task, neural nets must first be effectively trained on a dataset, which has prompted investigation into properties of objective function landscapes (Dauphin et al., 2014; Goodfellow et al., 2014; Choromanska et al., 2014), and the design of optimization procedures specifically suited to neural networks (Martens and Grosse, 2015). Trained networks must also be capable of generalizing to unseen data, and understanding generalization in neural networks is also an active line of research: (Hardt et al., 2015) bounds generalization error in terms of stochastic gradient descent steps, (Sontag, 1998; Bartlett and Maass, 2003; Bartlett et al., 1998) study generalization error through VC dimension, and (Hinton et al., 2015) looks at developing smaller models with better generalization.
In this paper, we focus on the third of these properties, expressivity — the capability of neural networks to accurately represent different kinds of functions. As the class of functions achievable by a neural network is dependent on properties of its architecture, e.g. depth, width, fully connected, convolutional, etc; a better understanding of expressivity may greatly inform architectural choice and inspire more tailored training methods.
Prior work on expressivity has yielded many fascinating results by directly examining the achievable functions of a particular architecture. Through this, neural networks have been shown to be
universal approximators (Hornik et al., 1989; Cybenko, 1989), and connections between boolean and threshold networks and ReLU networks developed in (Maass et al., 1994; Pan and Srikumar, 2015). The inherent expressivity due to increased depth has also been studied in (Eldan and Shamir, 2015; Telgarsky, 2015; Martens et al., 2013; Bianchini and Scarselli, 2014), and (Pascanu et al., 2013; Montufar et al., 2014), with the latter introducing the number of linear regions as a measure of expressivity.
These results, while compelling, also highlight limitations of much of the existing work on expressivity. Much of the work examining achievable functions relies on unrealistic architectural assumptions, such as layers being exponentially wide (in the universal approximation theorem). Furthermore, architectures are often compared via ‘hardcoded’ weight values – a specific function that can be represented efficiently by one architecture is shown to only be inefficiently approximated by another.
Comparing architectures in such a fashion limits the generality of the conclusions, and does not entirely address the goal of understanding expressivity — to provide characteristic properties of a typical set of networks arising from a particular architecture, and extrapolate to practical consequences.
Random networks To address this, we begin our analysis of network expressivity on a family of networks arising in practice — the behaviour of networks after random initialization. As random initialization is the starting point to most training methods, results on random networks provide natural baselines to compare trained networks with, and are also useful in highlighting properties of trained networks (see Section 3). The expressivity of these random networks is largely unexplored. In previous work (Poole et al., 2016) we studied the propagation of Riemannian curvature through random networks by developing a mean field theory approach, which quantitatively supports the conjecture that deep networks can disentangle curved manifolds in input space. Here, we take a more direct approach, exactly relating the architectural properties of the network to measures of expressivity and exploring the consequences for trained networks.
Measures of Expressivity In particular, we examine the effect of the depth and width of a network architecture on three different natural measures of functional richness: number of transitions, activation patterns, and number of dichotomies.
Transitions: Counting neuron transitions is introduced indirectly via linear regions in (Pascanu et al., 2013), and provides a tractable method to estimate the degree of non-linearity of the computed function.
Activation Patterns: Transitions of a single neuron can be extended to the outputs of all neurons in all layers, leading to the (global) definition of a network activation pattern, also a measure of nonlinearity. Network activation patterns directly show how the network partitions input space (into convex polytopes), through connections to the theory of hyperplane arrangements.
Dichotomies: We also measure the heterogeneity of a generic class of functions from a particular architecture by counting dichotomies, ‘statistically dual’ to sweeping input in some cases. This measure reveals the importance of remaining depth in expressivity, in both simulation and practice.
Connection to Trajectory Length All three measures display an exponential increase with depth, but not width (most strikingly in Figure 4). We discover and prove the underlying reason for this – all three measures are directly proportional to a fourth quantity, trajectory length. In Theorem 1) we show that trajectory length grows exponentially with depth (also supported by experiments, Figure 1) which explains the depth sensitivity of the other three measures.
Consequences for Trained Networks Our empirical and theoretical results connecting transitions and dichotomies to trajectory length also suggest that parameters earlier in the network should have exponentially greater influence on parameters later in the network. In other words, the influence on expressivity of parameters, and thus layers, is directly related to the remaining depth of the network after that layer. Experiments on MNIST and CIFAR-10 support this hypothesis — training only earlier layers leads to higher accuracy than training only later layers. We also find, with experiments on MNIST, that the training process trades off between the stability of the input-output map and its expressivity.
2 GROWTH OF TRAJECTORY LENGTH AND MEASURES OF EXPRESSIVITY
In this section we examine random networks, proving and empirically verifing the exponential growth of trajectory length with depth. We then relate trajectory length to transitions, activation patterns and dichotomies, and show their exponential increase with depth.
2.1 NOTATION AND DEFINITIONS
Let FW denote a neural network. In this section, we consider architectures with input dimension m, n hidden layers all of width k, and (for convenience) a scalar readout layer. (So, FW : Rm → R.) Our results mostly examine the cases where φ is a hard-tanh (Collobert and Bengio, 2004) or ReLU nonlinearity. All hard-tanh results carry over to tanh with additional technical steps.
We use v(d)i to denote the i th neuron in hidden layer d. We also let x = z(0) be an input, h(d) be the hidden representation at layer d, and φ the non-linearity. The weights and bias are called W (d) and b(d) respectively. So we have the relations
h(d) = W (d)z(d) + b(d), z(d+1) = φ(h(d)). (1)
Definitions Say a neuron transitions when it switches linear region in its activation function (i.e. for ReLU, switching between zero and linear regimes, for hard-tanh, switching between negative saturation, unsaturated and positive saturation). For hard-tanh, we refer to a sign transition as the neuron switching sign, and a saturation transition as switching from being saturated between ±1. The Activation Pattern of the entire network is defined by the output regions of every neuron. More precisely, given an input x, we let A(FW , x) be a vector representing the activation region of every hidden neuron in the network. So for a ReLU network FW , we can take A(FW , x) ∈ {−1, 1}nk with −1 meaning the neuron is in the zero regime, and 1 meaning it is in the linear regime. For
hard-tanh network FW , we can (overloading notation slightly) take A(FW , x) ∈ {−1, 0, 1}nk. The use of this notation will be clear by context. Given a set of inputs S, we say a dichotomy over S is a labeling of each point in S as ±1. We assume the weights of our neural networks are initialized as random Gaussians, with appropriate variance scaling to account for width, i.e. W (d)ij ∼ N (0, σ2w/k), and biases b (d) i ∼ N (0, σ2b ). In the analysis below, we sweep through a one dimensional input trajectory x(t). The results hold for almost any such smooth x(t), provided that at any point x(t), the trajectory direction has some non-zero magnitude perpendicular to x(t).
2.2 TRAJECTORY LENGTH AND NEURON TRANSITIONS
We first prove how the trajectory length grows, and relate it to neuron transitions.
2.2.1 BOUND ON TRAJECTORY LENGTH GROWTH
We prove (with a more exact lower bound in the Appendix):
Theorem 1. Bound on Growth of Trajectory Length Let FW be a hard tanh random neural network and x(t) a one dimensional trajectory in input space. Define z(d)(x(t)) = z(d)(t) to be the image
of the trajectory in layer d of FW , and let l(z(d)(t)) = ∫ t ∣∣∣∣∣∣dz(d)(t)dt ∣∣∣∣∣∣ dt be the arc length of z(d)(t).
Then
E [ l(z(d)(t)) ] ≥ O   σw
(σ2w + σ 2 b )
1/4 · √ k√√
σ2w + σ 2 b + k
d  l(x(t))
This bound is tight in the limits of large σw and k. An immediate Corollary for σb = 0, i.e. no bias, is
Corollary 1. Bound on Growth of Trajectory Length Without Bias For FW with zero bias, we have
E [ l(z(d)(t)) ] ≥ O (( √ σwk√ σw + k )d) l(x(t))
The theorem shows that the image of a trajectory in layer d has grown exponentially in d, with the scaling σw and width of the network k determining the base. We additionally state and prove a simple O(σdw) growth upper bound in the Appendix. Figure 1 demonstrates this behavior in simulation, and compares against the bounds. Note also that if the variance of the bias is comparatively too large i.e. σb >> σw, then we no longer see exponential growth. This corresponds to the phase transition described in (Poole et al., 2016).
The proof can be found in the Appendix. A rough outline is as follows: we look at the expected growth of the difference between a point z(d)(t) on the curve and a small perturbation z(d)(t+ dt), from layer d to layer d + 1. Denoting this quantity ∣∣∣∣δz(d)(t)∣∣∣∣, we derive a recurrence relating∣∣∣∣δz(d+1)(t)∣∣∣∣ and ∣∣∣∣δz(d)(t)∣∣∣∣ which can be composed to give the desired growth rate. The analysis is complicated by the statistical dependence on the image of the input z(d+1)(t). So we instead form a recursion by looking at the component of the difference perpendicular to the image of the input in that layer, i.e.
∣∣∣∣∣∣δz(d+1)⊥ (t)∣∣∣∣∣∣. For a typical trajectory, the perpendicular component preserves a fraction √ k−1 k of the total trajectory length, and our derived growth rate thus provides a close lower bound, as demonstrated in Figure 1(c,d).
2.2.2 RELATION TO NUMBER OF TRANSITIONS
Further experiments (Figure 2) show:
Observation 1. The number of sign transitions in a network FW is directly proportional to the length of the latent image of the curve, z(n)(t).
We intuit a reason for this observation as follows: note that for a network FW with n hidden layers, the linear, one dimensional, readout layer outputs a value by computing the inner productW (n)z(n). The sign of the output is then determined by whether this quantity is ≥ 0 or not. In particular, the decision boundary is a hyperplane, with equation W (n)z(n) = 0. So, the number of transitions the output neuron makes as x(t) is traced is exactly the number of times z(n)(t) crosses the decision boundary. As FW is a random neural network, with signs of weight entries split purely randomly between ±1, it would suggest that points far enough away from each other would have independent signs, i.e. a direct proportionality between the length of z(n)(t) and the number of times it crosses the decision boundary.
We can also prove this in the special case when σw is very large. Note that by Theorem 1, very large σw results in a trajectory growth rate of
g(k, σw, σb, n) = O  √k√ 1 +
σ2b σ2w n Large σw also means that for any input (bounded away from zero), almost all neurons are saturated. Furthermore, any neuron transitioning from 1 to −1 (or vice versa) does so almost instantaneously. In particular, at most one neuron within a layer is transitioning for any input. We can then show that in the large σw limit the number of transitions matches the trajectory length (proof in the Appendix, via a reduction to magnitudes of independent Gaussians):
Theorem 2. Number of transitions in large weight limit Given FW , in the very large σw regime, the number of sign transitions of the network as an input x(t) is swept is of the order of g(k, σw, σb, n).
2.3 TRANSITIONS AND ACTIVATION PATTERNS
We can generalize the ’local’ notion of expressivity of a neuron‘s sign transitions to a ’global’ measure of activation patterns over the entire network. We can formally relate network activation patterns to specific hyperplane arrangements, which allows proof of three exciting results.
First, we can precisely state the effect of a neural network on input space, also visualized in Figure 3
Theorem 3. Regions in Input Space Given a network FW with with ReLU or hard-tanh activations, input space is partitioned into convex regions (polytopes), with FW corresponding to a different linear function on each region.
This results in a bijection between transitions and activation patterns for ‘well-behaved’ trajectories, see the proof of Theorem 3 and Corollary 2 in Appendix.
Finally, returning to the goal of understanding expressivity, we can upper bound the expressive power of a particular architecture according to the activation patterns measure:
Theorem 4. (Tight) Upper bound for Number of Activation Patterns Given a neural network FW , inputs in Rm, with ReLU or hard-tanh activations, and with n hidden layers of width k, the number of activation patterns grows at most like O(kmn) for ReLU, or O((2k)mn) for hard-tanh.
2.4 DICHOTOMIES: A NATURAL DUAL
So far, we have looked at the effects of depth and width on the expressiveness (measured through transitions and activations) of a generic function computed by that network architecture. These measures are directly related to trajectory length, which is the underlying reason for exponential depth dependence.
A natural extension is to study a class of functions that might arise from a particular architecture. One such class of functions is formed by sweeping the weights of a network instead of the input. More formally, we pick random matrices, W,W ′, and consider the weight interpolation W cos(t) + W ′ sin(t), each choice of weights giving a different function. When this process is applied to just the first layer, we have a statistical duality with sweeping a circular input.
Given this class of functions, one useful measure of expressivity is determining how heterogeneous this class is. Inspired by classification tasks we formalize it as: given a set of inputs, S = {x1, .., xs} ⊂ Rm, how many of the 2s possible dichotomies does this function class produce on S?
For non-random inputs and non-random functions, this is a well known question upper bounded by the Sauer-Shelah lemma (Sauer, 1972). We discuss this further in Appendix D.1. In the random setting, the statistical duality of weight sweeping and input sweeping suggests a direct proportion to transitions and trajectory length for a fixed input. Furthermore, if the xi ∈ S are sufficiently uncorrelated (e.g. random) class label transitions should occur independently for each xi Indeed, we show this in Figure 4 (more figures, e.g. dichotomies vs transitions and observations, are included in the Appendix).
Observation 2. Depth and Expressivity in a Function Class. Given the function class F as above, the number of dichotomies expressible by F over a set of random inputs S by sweeping the first layer weights along a one dimensional trajectory W (0)(t) is exponential in the network depth n.
3 TRAINED NETWORKS
Remaining Depth The results from Section 2, particularly those linking dichotomies to trajectory length, suggest that earlier layers in the network might have more expressive power. In particular, the remaining depth of the network beyond the layer might directly influence its expressive power. We see that this holds in the random network case (Figure 5), and also for networks trained on MNIST and CIFAR-10. In Figures 6, 7 we randomly initialized a neural network, and froze all the layers except for one, which we trained.
Training trades off between input-output map stability and expressivity We also look at the effect of training on measures of expressivity by plotting the change in trajectory length and number of transitions (see Appendix) during the training process. We find that for a network initialized with large σw, the training process appears to stabilize the input-output map – monotonically decreasing trajectory length (Figure 8) except for the final few steps. Interestingly, this happens at a faster rate in the vicinity of the data than for random inputs, and is accomplished without reducing weight magnitudes.
For a network closer to the boundary of the exponential regime σ2w = 3, where trajectory length growth is still exponential but with a much smaller base, the training process increases the trajectory length, enabiling greater expressivity in the resulting input-output map, Figure 9
4 CONCLUSION
In this paper, we studied the expressivity of neural networks through three measures, neuron transitions, activation patterns and dichotomies, and explained the observed exponential dependence on depth of all three measures by demonstrating the underlying link to latent trajectory length. Having explored these results in the context of random networks, we then looked at the consequences for trained networks (see Table 1). We find that the remaining depth above a network layer influences its expressive power, which might inspire new pre-training or initialization schemes. Furthermore, we see that training interpolates between expressive power and better generalization. This relation between initial and final parameters might inform early stopping and warm starting rules.
ACKNOWLEDGEMENTS
We thank Samy Bengio, Ian Goodfellow, Laurent Dinh, and Quoc Le for extremely helpful discussion.
Appendix
Here we include the full proofs from sections in the paper.
A PROOFS AND ADDITIONAL RESULTS FROM SECTION 2.2
Proof of Theorem 1 We prove this result for FW with zero bias for technical simplicity. The result also translates over to FW with bias with a couple of technical modifications.
A.1 NOTATION AND PRELIMINARY RESULTS
Difference of points on trajectory Given x(t) = x, x(t+ dt) = x+ δx in the trajectory, let δz(d) = z(d)(x+ δx)− z(d)(x) Parallel and Perpendicular Components: Given vectors x, y, we can write y = y⊥ + y‖ where y⊥ is the component of y perpendicular to x, and y‖ is the component parallel to x. (Strictly speaking, these components should also have a subscript x, but we suppress it as the direction with respect to which parallel and perpendicular components are being taken will be explicitly stated.)
This notation can also be used with a matrix W , see Lemma 1.
Before stating and proving the main theorem, we need a few preliminary results.
Lemma 1. Matrix Decomposition Let x, y ∈ Rk be fixed non-zero vectors, and let W be a (full rank) matrix. Then, we can write
W = ‖W‖ + ‖W⊥ + ⊥W‖ + ⊥W⊥
such that ‖W⊥x = 0
⊥W⊥x = 0
yT⊥W‖ = 0 y T⊥W⊥ = 0
i.e. the row space of W is decomposed to perpendicular and parallel components with respect to x (subscript on right), and the column space is decomposed to perpendicular and parallel components of y (superscript on left).
Proof. Let V,U be rotations such that V x = (||x|| , 0..., 0)T and Uy = (||y|| , 0...0)T . Now let W̃ = UWV T , and let W̃ = ‖W̃‖ + ‖W̃⊥ + ⊥W̃‖ + ⊥W̃⊥, with ‖W̃‖ having non-zero term exactly W̃11, ‖W̃⊥ having non-zero entries exactly W̃1i for 2 ≤ i ≤ k. Finally, we let ⊥W̃‖ have non-zero entries exactly W̃i1, with 2 ≤ i ≤ k and ⊥W̃⊥ have the remaining entries non-zero. If we define x̃ = V x and ỹ = Uy, then we see that
‖W̃⊥x̃ = 0 ⊥W̃⊥x̃ = 0
ỹT⊥W̃‖ = 0 ỹ T⊥W̃⊥ = 0
as x̃, ỹ have only one non-zero term, which does not correspond to a non-zero term in the components of W̃ in the equations.
Then, defining ‖W‖ = UT ‖W̃‖V , and the other components analogously, we get equations of the form
‖W⊥x = U T ‖W̃⊥V x = U T ‖W̃⊥x̃ = 0
Observation 3. Given W,x as before, and considering W‖, W⊥ with respect to x (wlog a unit vector) we can express them directly in terms of W as follows: Letting W (i) be the ith row of W , we have
W‖ = ((W (0))T · x)x
... ((W (k))T · x)x  i.e. the projection of each row in the direction of x. And of course
W⊥ = W −W‖
The motivation to consider such a decomposition of W is for the resulting independence between different components, as shown in the following lemma.
Lemma 2. Independence of Projections Let x be a given vector (wlog of unit norm.) If W is a random matrix with Wij ∼ N (0, σ2), then W‖ and W⊥ with respect to x are independent random variables.
Proof. There are two possible proof methods:
(a) We use the rotational invariance of random Gaussian matrices, i.e. if W is a Gaussian matrix, iid entries N (0, σ2), and R is a rotation, then RW is also iid Gaussian, entries N (0, σ2). (This follows easily from affine transformation rules for multivariate Gaussians.)
Let V be a rotation as in Lemma 1. Then W̃ = WV T is also iid Gaussian, and furthermore, W̃‖ and W̃⊥ partition the entries of W̃ , so are evidently independent. But then W‖ = W̃‖V T and W⊥ = W̃⊥V T are also independent.
(b) From the observation note that W‖ and W⊥ have a centered multivariate joint Gaussian distribution (both consist of linear combinations of the entries Wij in W .) So it suffices to show that W‖ and W⊥ have covariance 0. Because both are centered Gaussians, this is equivalent to showing E(< W‖,W⊥ >) = 0. We have that
E(< W‖,W⊥ >) = E(W‖WT⊥ ) = E(W‖WT )− E(W‖WT‖ )
As any two rows of W are independent, we see from the observation that E(W‖WT ) is a diagonal matrix, with the ith diagonal entry just ((W (0))T · x)2. But similarly, E(W‖WT‖ ) is also a diagonal matrix, with the same diagonal entries - so the claim follows.
In the following two lemmas, we use the rotational invariance of Gaussians as well as the chi distribution to prove results about the expected norm of a random Gaussian vector.
Lemma 3. Norm of a Gaussian vector Let X ∈ Rk be a random Gaussian vector, with Xi iid, ∼ N (0, σ2). Then
E [||X||] = σ √ 2 Γ((k + 1)/2)
Γ(k/2)
Proof. We use the fact that if Y is a random Gaussian, and Yi ∼ N (0, 1) then ||Y || follows a chi distribution. This means that E(||X/σ||) = √ 2Γ((k+ 1)/2)/Γ(k/2), the mean of a chi distribution with k degrees of freedom, and the result follows by noting that the expectation in the lemma is σ multiplied by the above expectation.
We will find it useful to bound ratios of the Gamma function (as appear in Lemma 3) and so introduce the following inequality, from (Kershaw, 1983) that provides an extension of Gautschi’s Inequality.
Theorem 5. An Extension of Gautschi’s Inequality For 0 < s < 1, we have
( x+ s
2
)1−s ≤ Γ(x+ 1)
Γ(x+ s) ≤
( x− 1
2 +
( s+ 1
4
) 1 2 )1−s
We now show: Lemma 4. Norm of Projections Let W be a k by k random Gaussian matrix with iid entries ∼ N (0, σ2), and x, y two given vectors. Partition W into components as in Lemma 1 and let x⊥ be a nonzero vector perpendicular to x. Then
(a)
E [∣∣∣∣⊥W⊥x⊥∣∣∣∣] = ||x⊥||σ√2 Γ(k/2)
Γ((k − 1)/2 ≥ ||x⊥||σ
√ 2
( k
2 − 3 4 )1/2 (b) If 1A is an identity matrix with non-zeros diagonal entry i iff i ∈ A ⊂ [k], and |A| > 2,
then
E [∣∣∣∣1A⊥W⊥x⊥∣∣∣∣] ≥ ||x⊥||σ√2 Γ(|A|/2)
Γ((|A| − 1)/2) ≥ ||x⊥||σ
√ 2 ( |A| 2 − 3 4 )1/2 Proof. (a) Let U, V, W̃ be as in Lemma 1. As U, V are rotations, W̃ is also iid Gaussian.
Furthermore for any fixed W , with ã = V a, by taking inner products, and square-rooting, we see that ∣∣∣∣∣∣W̃ ã∣∣∣∣∣∣ = ||Wa||. So in particular E [∣∣∣∣⊥W⊥x⊥∣∣∣∣] = E [∣∣∣∣∣∣⊥W̃⊥x̃⊥∣∣∣∣∣∣]
But from the definition of non-zero entries of ⊥W̃⊥, and the form of x̃⊥ (a zero entry in the first coordinate), it follows that ⊥W̃⊥x̃⊥ has exactly k−1 non zero entries, each a centered Gaussian with variance (k − 1)σ2 ||x⊥||2. By Lemma 3, the expected norm is as in the statement. We then apply Theorem 5 to get the lower bound.
(b) First note we can view 1A⊥W⊥ = ⊥1AW⊥. (Projecting down to a random (as W is random) subspace of fixed size |A| = m and then making perpendicular commutes with making perpendicular and then projecting everything down to the subspace.)
So we can viewW as a randomm by k matrix, and for x, y as in Lemma 1 (with y projected down onto m dimensions), we can again define U, V as k by k and m by m rotation matrices respectively, and W̃ = UWV T , with analogous properties to Lemma 1. Now we can finish as in part (a), except that ⊥W̃⊥x̃ may have only m − 1 entries, (depending on whether y is annihilated by projecting down by1A) each of variance (k − 1)σ2 ||x⊥||2.
Lemma 5. Norm and Translation LetX be a centered multivariate Gaussian, with diagonal covariance matrix, and µ a constant vector.
E(||X − µ||) ≥ E(||X||)
Proof. The inequality can be seen intuitively geometrically: as X has diagonal covariance matrix, the contours of the pdf of ||X|| are circular centered at 0, decreasing radially. However, the contours of the pdf of ||X − µ|| are shifted to be centered around ||µ||, and so shifting back µ to 0 reduces the norm.
A more formal proof can be seen as follows: let the pdf of X be fX(·). Then we wish to show∫ x ||x− µ|| fX(x)dx ≥ ∫ x ||x|| fX(x)dx
Now we can pair points x,−x, using the fact that fX(x) = fX(−x) and the triangle inequality on the integrand to get∫
|x| (||x− µ||+ ||−x− µ||) fX(x)dx ≥ ∫ |x| ||2x|| fX(x)dx = ∫ |x| (||x||+ ||−x||) fX(x)dx
A.2 PROOF OF THEOREM
Proof. We first prove the zero bias case, Theorem 1. To do so, it is sufficient to prove that
E [∣∣∣∣∣∣δz(d+1)(t)∣∣∣∣∣∣] ≥ O ( √σk√ σ + k )d+1∣∣∣∣∣∣δz(0)(t)∣∣∣∣∣∣ (**) as integrating over t gives us the statement of the theorem.
For ease of notation, we will suppress the t in z(d)(t).
We first write W (d) = W
(d) ⊥ +W (d) ‖
where the division is done with respect to z(d). Note that this means h(d+1) = W (d)‖ z (d) as the other component annihilates (maps to 0) z(d).
We can also define A W (d) ‖ = {i : i ∈ [k], |h(d+1)i | < 1} i.e. the set of indices for which the hidden representation is not saturated. Letting Wi denote the ith row of matrix W , we now claim that:
EW (d) [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] = EW (d)‖ EW (d)⊥   ∑ i∈A
W (d) ‖
((W (d) ⊥ )iδz (d) + (W (d) ‖ )iδz (d))2  1/2  (*)
Indeed, by Lemma 2 we first split the expectation over W (d) into a tower of expectations over the two independent parts of W to get
EW (d) [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] = EW (d)‖ EW (d)⊥ [∣∣∣∣∣∣φ(W (d)δz(d))∣∣∣∣∣∣]
But conditioning onW (d)‖ in the inner expectation gives us h (d+1) andA W (d)
‖ , allowing us to replace
the norm over φ(W (d)δz(d)) with the sum in the term on the right hand side of the claim.
Till now, we have mostly focused on partitioning the matrix W (d). But we can also set δz(d) = δz
(d) ‖ + δz (d) ⊥ where the perpendicular and parallel are with respect to z (d). In fact, to get the expression in (**), we derive a recurrence as below:
EW (d) [∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣] ≥ O ( √ σk√ σ + k ) EW (d) [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣] To get this, we first need to define z̃(d+1) = 1A
W (d) ‖
h(d+1) - the latent vector h(d+1) with all
saturated units zeroed out.
We then split the column space ofW (d) = ⊥W (d)+‖W (d), where the split is with respect to z̃(d+1). Letting δz(d+1)⊥ be the part perpendicular to z
(d+1), and A the set of units that are unsaturated, we have an important relation: Claim ∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣ ≥ ∣∣∣∣∣∣⊥W (d)δz(d)1A∣∣∣∣∣∣ (where the indicator in the right hand side zeros out coordinates not in the active set.)
To see this, first note, by definition,
δz (d+1) ⊥ = W (d)δz(d) · 1A − 〈W (d)δz(d) · 1A, ẑ(d+1)〉ẑ(d+1) (1)
where the ·̂ indicates a unit vector.
Similarly ⊥W (d)δz(d) = W (d)δz(d) − 〈W (d)δz(d), ˆ̃z(d+1)〉ˆ̃z(d+1) (2)
Now note that for any index i ∈ A, the right hand sides of (1) and (2) are identical, and so the vectors on the left hand side agree for all i ∈ A. In particular,
δz (d+1) ⊥ · 1A = ⊥W (d)δz(d) · 1A Now the claim follows easily by noting that ∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣ ≥ ∣∣∣∣∣∣δz(d+1)⊥ · 1A∣∣∣∣∣∣.
Returning to (*), we split δz(d) = δz(d)⊥ + δz (d) ‖ , W (d) ⊥ = ‖W (d) ⊥ + ⊥W (d) ⊥ (and W (d) ‖ analogously), and after some cancellation, we have
EW (d) [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] = EW (d)‖ EW (d)⊥   ∑ i∈A
W (d) ‖
( (⊥W
(d) ⊥ + ‖W (d) ⊥ )iδz (d) ⊥ + ( ⊥W (d) ‖ + ‖W (d) ‖ )iδz (d) ‖ )2 1/2 
We would like a recurrence in terms of only perpendicular components however, so we first drop the ‖W (d)⊥ , ‖W (d) ‖ (which can be done without decreasing the norm as they are perpendicular to the remaining terms) and using the above claim, have
EW (d) [∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣] ≥ EW (d)‖ EW (d)⊥   ∑ i∈A
W (d) ‖
( (⊥W
(d) ⊥ )iδz (d) ⊥ + ( ⊥W (d) ‖ )iδz (d) ‖ )2 1/2 
But in the inner expectation, the term ⊥W (d)‖ δz (d) ‖ is just a constant, as we are conditioning onW (d) ‖ . So using Lemma 5 we have
E W
(d) ⊥   ∑ i∈A
W (d) ‖
( (⊥W
(d) ⊥ )iδz (d) ⊥ + ( ⊥W (d) ‖ )iδz (d) ‖ )2 1/2  ≥ EW (d)⊥   ∑ i∈A
W (d) ‖
( (⊥W
(d) ⊥ )iδz (d) ⊥ )2 1/2 
We can then apply Lemma 4 to get
E W
(d) ⊥   ∑ i∈A
W (d) ‖
( (⊥W
(d) ⊥ )iδz (d) ⊥ )2 1/2  ≥ σ√k√2 √ 2|A W (d) ‖ | − 3 2 E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣]
The outer expectation on the right hand side only affects the term in the expectation through the size of the non-saturated set of units. Letting p = P(|h(d+1)i | < 1), and noting that we get a non-zero norm only if |A
W (d) ‖ | ≥ 2 (else we cannot project down a dimension), and for |A W (d) ‖ | ≥ 2,
√ 2
√ 2|A
W (d) ‖ | − 3
2 ≥ 1√
2
√ |A
W (d) ‖ |
we get
EW (d) [∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣] ≥ 1√2  k∑ j=2 ( k j ) pj(1− p)k−j σ√ k √ j E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣]
We use the fact that we have the probability mass function for an (k, p) binomial random variable to bound the √ j term: k∑ j=2 ( k j ) pj(1− p)k−j σ√ k √ j = − ( k 1 ) p(1− p)k−1 σ√ k + k∑ j=0 ( k j ) pj(1− p)k−j σ√ k √ j
= −σ √ kp(1− p)k−1 + kp · σ√
k k∑ j=1 1√ j ( k − 1 j − 1 ) pj−1(1− p)k−j
But by using Jensen’s inequality with 1/ √ x, we get
k∑ j=1 1√ j ( k − 1 j − 1 ) pj−1(1− p)k−j ≥ 1√∑k j=1 j ( k−1 j−1 ) pj−1(1− p)k−j = 1√ (k − 1)p+ 1
where the last equality follows by recognising the expectation of a binomial(k − 1, p) random variable. So putting together, we get
EW (d) [∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣] ≥ 1√2 ( −σ √ kp(1− p)k−1 + σ · √ kp√ 1 + (k − 1)p ) E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣] (a)
To lower bound p, we first note that as h(d+1)i is a normal random variable with variance ≤ σ2, if A ∼ N (0, σ2)
P(|h(d+1)i | < 1) ≥ P(|A| < 1) ≥ 1
σ √ 2π (b)
where the last inequality holds for σ ≥ 1 and follows by Taylor expanding e−x2/2 around 0. Similarly, we can also show that p ≤ 1σ . So this becomes
E [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] ≥  1√ 2  1 (2π)1/4 √ σk√
σ √ 2π + (k − 1) − √ k
( 1− 1
σ
)k−1E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣]
= O ( √ σk√ σ + k ) E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣]
Finally, we can compose this, to get
E [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] ≥  1√ 2  1 (2π)1/4 √ σk√
σ √ 2π + (k − 1) − √ k
( 1− 1
σ )k−1d+1 c · ||δx(t)|| with the constant c being the ratio of ||δx(t)⊥|| to ||δx(t)||. So if our trajectory direction is almost orthogonal to x(t) (which will be the case for e.g. random circular arcs, c can be seen to be ≈ 1 by splitting into components as in Lemma 1, and using Lemmas 3, 4.)
Result for non-zero bias In fact, we can easily extend the above result to the case of non-zero bias. The insight is to note that because δz(d+1) involves taking a difference between z(d+1)(t+ dt) and z(d+1)(t), the bias term does not enter at all into the expression for δz(d+1). So the computations above hold, and equation (a) becomes
EW (d) [∣∣∣∣∣∣δz(d+1)⊥ ∣∣∣∣∣∣] ≥ 1√2 ( −σw √ kp(1− p)k−1 + σw · √ kp√ 1 + (k − 1)p ) E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣]
We also now have that h(d+1)i is a normal random variable with variance ≤ σ2w + σ2b (as the bias is drawn from N (0, σ2b )). So equation (b) becomes
P(|h(d+1)i | < 1) ≥ 1√
(σ2w + σ 2 b ) √ 2π
This gives Theorem 1
E [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] ≥ O  σw (σ2w + σ 2 b ) 1/4 · √ k√√
σ2w + σ 2 b + k
E [∣∣∣∣∣∣δz(d)⊥ ∣∣∣∣∣∣]
Statement and Proof of Upper Bound for Trajectory Growth Replace hard-tanh with a linear coordinate-wise identity map, h(d+1)i = (W
(d)z(d))i + bi. This provides an upper bound on the norm. We also then recover a chi distribution with k terms, each with standard deviation σw
k 1 2
,
E [∣∣∣∣∣∣δz(d+1)∣∣∣∣∣∣] ≤ √2Γ ((k + 1)/2)
Γ (k/2)
σw k 1 2 ∣∣∣∣∣∣δz(d)∣∣∣∣∣∣ (2) ≤ σw ( k + 1
k
) 1 2 ∣∣∣∣∣∣δz(d)∣∣∣∣∣∣ , (3)
where the second step follows from (Laforgia and Natalini, 2013), and holds for k > 1.
B PROOFS AND ADDITIONAL RESULTS FROM SECTION 2.2.2
Proof of Theorem 2
Proof. For σb = 0: For hidden layer d < n, consider neuron v(d)1 . This has as input ∑k i=1W (d−1) i1 z (d−1) i . As we are in the large σ case, we assume that |z(d−1)i | = 1. Furthermore, as signs for z (d−1) i andW (d−1) i1 are both completely random, we can also assume wlog that z(d−1)i = 1. For a particular input, we can define v (d) 1 as sensitive to v (d−1) i if v (d−1) i transitioning (to wlog −1) will induce a transition in node v (d) 1 .
A sufficient condition for this to happen is if |Wi1| ≥ | ∑ j 6=iWj1|. But X = Wi1 ∼ N (0, σ2/k)
and ∑ j 6=iWj1 = Y
′ ∼ N (0, (k − 1)σ2/k). So we want to compute P(|X| > |Y ′|). For ease of computation, we instead look at P(|X| > |Y |), where Y ∼ N (0, σ2). But this is the same as computing P(|X|/|Y | > 1) = P(X/Y < −1) + P(X/Y > 1). But the ratio of two centered independent normals with variances σ21 , σ 2 2 follows a Cauchy distribution,
with parameter σ1/σ2, which in this case is 1/ √ k. Substituting this in to the cdf of the Cauchy distribution, we get that
P ( |X| |Y | > 1 ) = 1− 2 π arctan( √ k)
Finally, using the identity arctan(x) + arctan(1/x) and the Laurent series for arctan(1/x), we can evaluate the right hand side to be O(1/ √ k). In particular
P ( |X| |Y | > 1 ) ≥ O ( 1√ k ) (c)
This means that in expectation, any neuron in layer d will be sensitive to the transitions of √ k neurons in the layer below. Using this, and the fact the while v(d−1)i might flip very quickly from say −1 to 1, the gradation in the transition ensures that neurons in layer d sensitive to v(d−1)i will transition at distinct times, we get the desired growth rate in expectation as follows:
Let T (d) be a random variable denoting the number of transitions in layer d. And let T (d)i be a random variable denoting the number of transitions of neuron i in layer d. Note that by linearity of expectation and symmetry, E [ T (d) ] = ∑ i E [ T (d) i ] = kE [ T (d) 1 ]
Now, E [ T
(d+1) 1
] ≥ E [∑ i 1(1,i)T (d) i ] = kE [ 1(1,1)T (d) 1 ] where 1(1,i) is the indicator function of
neuron 1 in layer d+ 1 being sensitive to neuron i in layer d. But by the independence of these two events, E [ 1(1,1)T (d) 1 ] = E [ 1(1,1) ] · E [ T (d) 1 ] . But the firt time on the right hand side isO(1/ √ k) by (c), so putting it all together, E [ T
(d+1) 1
] ≥ √ kE [ T
(d) 1
] .
Written in terms of the entire layer, we have E [ T (d+1) ] ≥ √ kE [ T (d) ] as desired.
For σb > 0: We replace √ k with √ k(1 + σ2b/σ 2 w), by noting that Y ∼ N (0, σ2w + σ2b ). This results in a growth
rate of form O( √ k/ √
1 + σ2b σ2w ).
C PROOFS AND ADDITIONAL RESULTS FROM SECTION 2.3
Proof of Theorem 3
Proof. We show inductively that FW partitions the input space into convex polytopes via hyperplanes. Consider the image of the input space under the first hidden layer. Each neuron v(1)i defines hyperplane(s) on the input space: letting W (0)i be the ith row of W
(0), b(0)i the bias, we have the hyperplane W (0)i x + bi = 0 for a ReLU and hyperplanes W (0) i x + bi = ±1 for a hard-tanh. Considering all such hyperplanes over neurons in the first layer, we get a hyperplane arrangement in the input space, each polytope corresponding to a specific activation pattern in the first hidden layer.
Now, assume we have partitioned our input space into convex polytopes with hyperplanes from layers≤ d−1. Consider v(d)i and a specific polytopeRi. Then the activation pattern on layers≤ d−1 is constant on Ri, and so the input to v (d) i on Ri is a linear function of the inputs ∑ j λjxj + b and some constant term, comprising of the bias and the output of saturated units. Setting this expression to zero (for ReLUs) or to ±1 (for hard-tanh) again gives a hyperplane equation, but this time, the equation is only valid in Ri (as we get a different linear function of the inputs in a different region.) So the defined hyperplane(s) either partition Ri (if they intersect Ri) or the output pattern of v (d) i is also constant on Ri. The theorem then follows.
This implies that any one dimensional trajectory x(t), that does not ‘double back’ on itself (i.e. reenter a polytope it has previously passed through), will not repeat activation patterns. In particular, after seeing a transition (crossing a hyperplane to a different region in input space) we will never return to the region we left. A simple example of such a trajectory is a straight line: Corollary 2. Transitions and Output Patterns in an Affine Trajectory For any affine one dimensional trajectory x(t) = x0 + t(x1−x0) input into a neural network FW , we partition R 3 t into intervals every time a neuron transitions. Every interval has a unique network activation pattern on FW .
Generalizing from a one dimensional trajectory, we can ask how many regions are achieved over the entire input – i.e. how many distinct activation patterns are seen? We first prove a bound on the number of regions formed by k hyperplanes in Rm (in a purely elementary fashion, unlike the proof presented in (Stanley, 2011)) Theorem 6. Upper Bound on Regions in a Hyperplane Arrangement Suppose we have k hyperplanes in Rm - i.e. k equations of form αix = βi. for αi ∈ Rm, βi ∈ R. Let the number of regions (connected open sets bounded on some sides by the hyperplanes) be r(k,m). Then
r(k,m) ≤ m∑ i=0 ( k i )
Proof of Theorem 6
Proof. Let the hyperplane arrangement be denoted H, and let H ∈ H be one specific hyperplane. Then the number of regions in H is precisely the number of regions in H −H plus the number of
regions in H ∩H . (This follows from the fact that H subdivides into two regions exactly all of the regions inH ∩H , and does not affect any of the other regions.) In particular, we have the recursive formula
r(k,m) = r(k − 1,m) + r(k − 1,m− 1)
We now induct on k+m to assert the claim. The base cases of r(1, 0) = r(0, 1) = 1 are trivial, and assuming the claim for ≤ k +m− 1 as the induction hypothesis, we have
r(k − 1,m) + r(k − 1,m− 1) ≤ m∑ i=0 ( k − 1 i ) + m−1∑ i=0 ( k − 1 i )
≤ ( k − 1
0
) + d−1∑ i=0 ( k − 1 i ) + ( k − 1 i+ 1 )
≤ ( k
0
) + m−1∑ i=0 ( k i+ 1 ) where the last equality follows by the well known identity(
a
b
) + ( a
b+ 1
) = ( a+ 1
b+ 1 ) This concludes the proof.
With this result, we can easily prove Theorem 4 as follows:
Proof. First consider the ReLU case. Each neuron has one hyperplane associated with it, and so by Theorem 6, the first hidden layer divides up the inputs space into r(k,m) regions, with r(k,m) ≤ O(km).
Now consider the second hidden layer. For every region in the first hidden layer, there is a different activation pattern in the first layer, and so (as described in the proof of Theorem 3) a different hyperplane arrangement of k hyperplanes in an m dimensional space, contributing at most r(k,m) regions.
In particular, the total number of regions in input space as a result of the first and second hidden layers is ≤ r(k,m) ∗ r(k,m) ≤ O(k2m). Continuing in this way for each of the n hidden layers gives the O(kmn) bound.
A very similar method works for hard tanh, but here each neuron produces two hyperplanes, resulting in a bound of O((2k)mn).
D PROOFS AND ADDITIONAL RESULTS FROM SECTION 2.4
D.1 UPPER BOUND FOR DICHOTOMIES
The Vapnik-Chervonenkis (VC) dimension of a function class is the cardinality of the largest set of points that it can shatter. The VC dimension provides an upper (worst case) bound on the generalization error for a function class (Vapnik and Vapnik, 1998). Motivated by generalization error, VC dimension has been studied for neural networks (Sontag, 1998; Bartlett and Maass, 2003). In (Bartlett et al., 1998) an upper bound on the VC dimension v of a neural network with piecewise polynomial activation function and binary output is derived. For hard-tanh units, this bound is
v = 2 |W |n log (4e |W |nk) + 2 |W |n2 log 2 + 2n, (4)
where |W | is the total number of weights, n is the depth, and k is the width of the network. The VC dimension provides an upper bound on the number of achievable dichotomies |F| by way of the
Sauer–Shelah lemma (Sauer, 1972),
|F| ≤ ( e|S| v )v . (5)
By combining Equations 4 and 5 an upper bound on the number of dichotomies is found, with a growth rate which is exponential in a low order polynomial of the network size.
Our results further suggest the following conjectures: Conjecture 1. As network width k increases, the exploration of the space of dichotomies increasingly resembles a simple random walk on a hypercube with dimension equal to the number of inputs |S|.
This conjecture is supported by Figure 10, which compares the number of unique dichotomies achieved by networks of various widths to the number of unique dichotomies achieved by a random walk. This is further supported by an exponential decrease in autocorrelation length in function space, derived in our prior work (Poole et al., 2016).
Conjecture 2. The expressive power of a single weight W (d)ij at layer d in a random network F , and for a set of random inputs S, is exponential in the remaining network depth dr = (n− d). Here expressive power is the number of dichotomies achievable by adjusting only that weight.
That is, the expressive power of weights in early layers in a deep hard-tanh network is exponentially greater than the expressive power of weights in later layers. This is supported by the invariance to layer number in the recurrence relations used in all proofs directly involving depth. It is also directly supported by simulation, as illustrated in Figure 5, and by experiments on MNIST and CIFAR10 as illustrated in Figures 6, 7.
E FURTHER RESULTS AND IMPLEMENTATION DETAILS FROM SECTION 3
We implemented the random network architecture described in Section 2.1. In separate experiments we then swept an input vector along a great circle trajectory (a rotation) for fixed weights, and swept weights along a great circle trajectory for a fixed set of inputs, as described in Section 2.4. In both cases, the trajectory was subdivided into 106 segments. We repeated this for a grid of network widths k, weight variances σ2w, and number of inputs s. Unless otherwise noted, σb = 0 for all experiments. We repeated each experiment 10 times and averaged over the results. The simulation results are discussed and plotted throughout the text.
The networks trained on MNIST and CIFAR-10 were implemented using Keras and Tensorflow, and trained for a fixed number of epochs with the ADAM optimizer.
Transitions Count during Training
We also have preliminary experimental results on Convolutional Networks. To try and make the comparisons fair, we implemented a fully convolutional network (no fully connected layers except for the last layer).
We also include the plot showing the effect of training on number of transitions for interpolated MNIST and interpolated random points.
SUMMARY 
This paper studies the expressive power of deep neural networks under various related measures of expressivity. 
It discusses how these measures relate to the `trajectory length', which is shown to depend exponentially on the depth of the network, in expectation (at least experimentally, at an intuitive level, or theoretically under certain assumptions). 
The paper also emphasises the importance of the weights in the earlier layers of the network, as these have a larger influence on the represented classes of functions, and demonstrates this in an experimental setting. 
PROS 
The paper further advances on topics related to the expressive power of feedforward neural networks with piecewise linear activation functions, in particular elaborating on the relations between various points of view. 
CONS 
The paper further advances and elaborates on interesting topics, but to my appraisal it does not contribute significantly new aspects to the discussion. 
COMMENTS
- The paper is a bit long (especially the appendix) and seems to have been written a bit in a rush. 
Overall the main points are presented clearly, but the results and conclusions could be clearer about the assumptions / experimental vs theoretical nature. 
The connection to previous works could also be clearer. 
- On page 2 one finds the statement ``Furthermore, architectures are often compared via ‘hardcoded’ weight values -- a specific function that can be represented efficiently by one architecture is shown to only be inefficiently approximated by another.'' 
This is partially true, but it neglects important parts of the discussion conducted in the cited papers. 
In particular, the paper [Montufar, Pascanu, Cho, Bengio 2014] discusses not one hard coded function, but classes of functions with a given number of linear regions. 
That paper shows that deep networks generically* produce functions with at least a given number of linear regions, while shallow networks never do. 
* Generically meaning that, after fixing the number of parameters, any function represented by the network, for parameter values form an open, positive -measure, neighbourhood, belongs to the class of functions which have at least a certain number of linear regions. 
In particular, such statements can be directly interpreted in terms of networks with random weights. 
- One of the measures for expressivity discussed in the present paper is the number of Dichotomies. In statistical learning theory, this notion is used to define the VC-dimension. In that context, a high value is associated with a high statistical complexity, meaning that picking a good hypothesis requires more data. 
- On page 2 one finds the statement ``We discover and prove the underlying reason for this – all three measures are directly proportional to a fourth quantity, trajectory length.'' 
The expected trajectory length increasing exponentially with depth can be interpreted as the increase (or decrease) in the scale by a composition of the form a*...*a x, which scales the inputs by a^d. Such a scaling by itself certainly is not an underlying cause for an increase in the number of dichotomies or activation patterns or transitions. Here it seems that at least the assumptions on the considered types of trajectories also play an important role. 
This is probably related to another observation from page 4: ``if the variance of the bias is comparatively too large... then we no longer see exponential growth.''
OTHER SPECIFIC COMMENTS 
In Theorem 1 
- Here it would be good to be more specific about ``random neural network'', i.e., fixed connectivity structure with random weights, and also about the kind of one-dimensional trajectory, i.e., finite in length, closed, differentiable almost everywhere, etc. 
- The notation ``g \geq O(f)'' used in the theorem reads literally as |g| \geq \leq k |f| for some k>0, for large enough arguments. It could also be read as g being not smaller than some function that is bounded above by f, which holds for instance whenever g\geq 0. 
For expressing asymptotic lower bounds one can use the notation \Omega (see