Title: ON THE EXPRESSIVE POWER OF DEEP NEURAL NET-WORKS

Abstract: 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 thisall 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. 

Length, k =32 σ 2 w =0.5 σ 2 w =1 σ 2 w =4 σ 2 w =16 σ 2 w =64 (b)

=4 k =1 k =4 k =16 k =64 k =256 (c)

k =2 k =32 k =512

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 F W 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, F W : R m → 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 d) ).

h (d) = W (d) z (d) + b (d) , z (d+1) = φ(h (

(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(F W , x) be a vector representing the activation region of every hidden neuron in the network. So for a ReLU network F W , we can take A(F W , 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 F W , we can (overloading notation slightly) take A(F W , 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 ∼ N (0, σ 2 b ). 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 F W 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 F W , 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 (σ 2 w + σ 2 b ) 1/4 • √ k σ 2 w + σ 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 F W with zero bias, we have

E l(z (d) (t)) ≥ O √ σ w k √ σ 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(σ d w ) 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 (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 F W is directly proportional to the length of the latent image of the curve, z (n) (t). 

Transitions:

Transitions vs. Length

k =8,σ 2 w =2 k =64,σ 2 w =2 k =8,σ 2 w =8 k =64,σ 2 w =8 k =512,σ 2 w =8 k =8,σ 2 w =32 k =64,σ 2 w =32 k =512,σ 2 w =32 Figure 2:

The number of transitions is linear in trajectory length. Here we compare the empirical number of sign changes to the length of the trajectory, for images of the same trajectory at different layers of a hard-tanh network. We repeat this comparison for a variety of network architectures, with different network width k and weight variance σ 2 w .

We intuit a reason for this observation as follows: note that for a network F W with n hidden layers, the linear, one dimensional, readout layer outputs a value by computing the inner product

W (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 F W 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 + σ 2 b σ 2 w   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 F W , 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 F W with with ReLU or hard-tanh activations, input space is partitioned into convex regions (polytopes), with F W 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:

-1 0 1 x0 -1 0 1 x1 Layer 0 -1 0 1 x0 -1 0 1 Layer 1 -1 0 1 x0 -1 0 1

Layer 2 Dichotomies vs. Width 

EQUATION

d r =1 d r =3 d r =5 d r =7 d r =9 d r =11 d r =13 d r =15 d r =17

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. The different lines are generated by varying the hidden layer chosen to train. All other layers are kept frozen after random initialization. We see that training lower hidden layers leads to better performance. The networks had width k = 100, weight variance σ 2 w = 2, and hard-tanh nonlinearities. Note that we only train from the second hidden layer (weights W (1) ) onwards, so that the number of parameters trained remains fixed. While the theory addresses training accuracy and not generalization accuracy, the same monotonic pattern is seen for both.

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 = {x 1 , .., x s } ⊂ R m , how many of the 2 s 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 x i ∈ S are sufficiently uncorrelated (e.g. random) class label transitions should occur independently for each x i 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 σ 2 w = 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 Interestingly, and supporting the observation on remaining depth, the first layer appears to increase trajectory length, in contrast with all later layers, suggesting it is being primarily used to fit the data. The right pane shows an identical plot but for an interpolation between random points, which also display decreasing trajectory length, but at a slower rate. Note the output layer is not plotted, due to artificial scaling of length through normalization. We see that the training process increases trajectory length, likely to increase the expressivity of the input-output map to enable greater accuracy. The right pane shows an identical plot but for an interpolation between random points, which also displays increasing trajectory length, but at a slower rate. Note the output layer is not plotted, due to artificial scaling of length through normalization. The network is initialized with σ 2 w = 3.

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.

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 W ij ∼ 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 = W V 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 W ij 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 W T ⊥ ) = E(W W T ) -E(W W T )

As any two rows of W are independent, we see from the observation that E(W W T ) is a diagonal matrix, with the ith diagonal entry just ((W (0) ) T • x) 2 . But similarly, E(W W T ) 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 ∈ R k be a random Gaussian vector, with X i 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 Y i ∼ 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 1 A is an identity matrix with non-zeros diagonal entry i iff i ∈ A ⊂ [k], and |A| > 2, then E 1 A ⊥ 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 ã = V a, by taking inner products, and square-rooting, we see that W ã = ||W a||. 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 1 A ⊥ W ⊥ = ⊥ 1 A W ⊥ . (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 view W as a random m 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 = U W V 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 by1 A ) each of variance (k -1)σ 2 ||x ⊥ || 2 .

Lemma 5. Norm and Translation Let X 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 f X (•). Then we wish to show

x ||x -µ|| f X (x)dx ≥ x ||x|| f X (x)dx

Now we can pair points x, -x, using the fact that f X (x) = f X (-x) and the triangle inequality on the integrand to get

|x| (||x -µ|| + ||-x -µ||) f X (x)dx ≥ |x| ||2x|| f X (x)dx = |x| (||x|| + ||-x||) f X (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

EQUATION

| < 1} i.e. the set of indices for which the hidden representation is not saturated. Letting W i denote the ith row of matrix W , we now claim that:

E W (d) δz (d+1) = E W (d) E W (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

E W (d) δz (d+1) = E W (d) E W (d) ⊥ φ(W (d) δz (d) )

But conditioning on W (d) in the inner expectation gives us h (d+1) and A 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:

E W (d) δz (d+1) ⊥ ≥ O √ σk √ σ + k E W (d) δz (d) ⊥

To get this, we first need to define z(d+1) = 1 A W (d) h (d+1) -the latent vector h (d+1) with all saturated units zeroed out.

We then split the column space of W (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) 1 A

(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) • 1 A -W (d) δz (d) • 1 A , ẑ(d+1) ẑ(d+1) (1)

where the • indicates a unit vector.

Similarly ⊥ W (d) δz (d) = W (d) δz (d) -W (d) δz (d) , ẑ(d+1) ẑ(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) ⊥ • 1 A = ⊥ W (d) δz (d) • 1 A

Now the claim follows easily by noting that δz

(d+1) ⊥ ≥ δz (d+1) ⊥ • 1 A .

Returning to (*), we split δz (d) = δz  and W (d) analogously), and after some cancellation, we have

EQUATION

⊥ = W (d) ⊥ + ⊥ W (d) ⊥ (

E W (d) δz (d+1) = E W (d) E W (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) (which can be done without decreasing the norm as they are perpendicular to the remaining terms) and using the above claim, have

EQUATION

E W (d) δz (d+1) ⊥ ≥ E W (d) E W (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 on W (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      ≥ E W (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

E W (d) δz (d+1) ⊥ ≥ 1 √ 2   k j=2 k j p j (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 p j (1 -p) k-j σ √ k j = - k 1 p(1 -p) k-1 σ √ k + k j=0 k j p j (1 -p) k-j σ √ k j = -σ √ kp(1 -p) k-1 + kp • σ √ k k j=1 1 √ j k -1 j -1 p j-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 p j-1 (1 -p) k-j ≥ 1 k j=1 j k-1 j-1 p j-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

E W (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

EQUATION

where the last inequality holds for σ ≥ 1 and follows by Taylor expanding e -x 2 /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-1     E δ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-1     d+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

E W (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 ≤ σ 2 w + σ 2 b (as the bias is drawn from N (0, σ 2 b )). So equation (b) becomes

P(|h (d+1) i | < 1) ≥ 1 (σ 2 w + σ 2 b ) √ 2π

This gives Theorem 1

E δz (d+1) ≥ O   σ w (σ 2 w + σ 2 b ) 1/4 • √ k σ 2 w + σ 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 + b i .

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)

EQUATION

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 . As we are in the large σ case, we assume that |z A sufficient condition for this to happen is if

|W i1 | ≥ | j =i W j1 |. But X = W i1 ∼ N (0, σ 2 /k) and j =i W j1 = 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 σ 2 1 , σ 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 is O(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 + σ 2 b /σ 2 w ), by noting that Y ∼ N (0, σ 2 w + σ 2 b ).

This results in a growth rate of form O(

√ k/ 1 + σ 2 b σ 2 w ).

C PROOFS AND ADDITIONAL RESULTS FROM SECTION 2.3

Proof of Theorem 3

Proof. We show inductively that F W 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 on R i is a linear function of the inputs j λ j x j + 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 R i (as we get a different linear function of the inputs in a different region.) So the defined hyperplane(s) either partition R i (if they intersect R i ) or the output pattern of v (d) i is also constant on R i . 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) = x 0 + t(x 1 -x 0 ) input into a neural network F W , we partition R t into intervals every time a neuron transitions. Every interval has a unique network activation pattern on F W .

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 R m (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 R m -i.e. k equations of form α 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 in H ∩ H, and does not affect any of the other regions.)

i x = β i . for α i ∈ R m , β i ∈ R.

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(k m ).

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(k 2 m). Continuing in this way for each of the n hidden layers gives the O(k m n) 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

EQUATION

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 

k =2 k =8 k =32 k =128 k =512

All dichotomies Random walk:

Figure 10 : Here we plot the number of unique dichotomies that have been observed as a function of the number of transitions the network has undergone. Each datapoint corresponds to the number of transitions and dichotomies for a hard-tanh network of a different depth, with the weights in the first layer undergoing interpolation along a great circle trajectory W (0) (t). We compare these plots to a random walk simulation, where at each transition a single class label is flipped uniformly at random. Dichotomies are measured over a dataset consisting of s = 15 random samples, and all networks had weight variance σ 2 w = 16. The blue dashed line indicates all 2 s possible dichotomies.

Sauer-Shelah lemma (Sauer, 1972) ,

EQUATION

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 d r = (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 10 6 segments. We repeated this for a grid of network widths k, weight variances σ 2 w , 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. Figure 12 : We repeat the experiment in Figure 6 for a convolutional network trained on CIFAR-10. The network has eight convolutional hidden layers, with three by three filters and 64 filters in each layer, all with ReLU activations. The final layer is a fully connected softmax, and is trained in addition to the single convolutional layer being trained. The results again support greater expressive power with remaining depth. Note the final three convolutional layers failed to effectively train, and performed at chance level.

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.

:



Figures and Tables:

Figure 1: The exponential growth of trajectory length with depth, in a random deep network with hard-tanh nonlinearities. A circular trajectory is chosen between two random vectors. The image of that trajectory is taken at each layer of the network, and its length measured. (a,b) The trajectory length vs. layer, in terms of the network width k and weight variance σ 2 w , both of which determine its growth rate. (c,d) The average ratio of a trajectory's length in layer d + 1 relative to its length in layer d. The solid line shows simulated data, while the dashed lines show upper and lower bounds (Theorem 1). Growth rate is a function of layer width k, and weight variance σ 2 w .

Figure 3: Deep networks with piecewise linear activations subdivide input space into convex polytopes. Here we plot the boundaries in input space separating unit activation and inactivation for all units in a three layer ReLU network, with four units in each layer. The left pane shows activation boundaries (corresponding to a hyperplane arrangement) in gray for the first layer only, partitioning the plane into regions. The center pane shows activation boundaries for the first two layers. Inside every first layer region, the second layer activation boundaries form a different hyperplane arrangement. The right pane shows activation boundaries for the first three layers, with different hyperplane arrangements inside all first and second layer regions. This final set of convex regions correspond to different activation patterns of the network -i.e. different linear functions.

Figure 4: The number of functions achievable in a deep hard-tanh network by sweeping a single layer's weights along a one dimensional trajectory is exponential in the remaining depth, but increases only slowly with network width. Here we plot the number of classification dichotomies over s = 15 input vectors achieved by sweeping the first layer weights in a hard-tanh network along a one-dimensional great circle trajectory. We show this (a) as a function of remaining depth for several widths, and (b) as a function of width for several remaining depths. All networks were generated with weight variance σ 2 w = 8, and bias variance σ 2 b = 0. Theorem 4. (Tight) Upper bound for Number of Activation Patterns Given a neural network F W , inputs in R m , with ReLU or hard-tanh activations, and with n hidden layers of width k, the number of activation patterns grows at most like O(k mn ) for ReLU, or O((2k) mn ) for hard-tanh.

Figure 6: Demonstration of expressive power of remaining depth on MNIST. Here we plot train and test accuracy achieved by training exactly one layer of a fully connected neural net on MNIST.The different lines are generated by varying the hidden layer chosen to train. All other layers are kept frozen after random initialization. We see that training lower hidden layers leads to better performance. The networks had width k = 100, weight variance σ 2 w = 2, and hard-tanh nonlinearities. Note that we only train from the second hidden layer (weights W (1) ) onwards, so that the number of parameters trained remains fixed. While the theory addresses training accuracy and not generalization accuracy, the same monotonic pattern is seen for both.

Figure7: We repeat a similar experiment in Figure6with a fully connected network on CIFAR-10, and mostly observe that training lower layers again leads to better performance. The networks had width k = 200, weight variance σ 2 w = 1, and hard-tanh nonlinearities. We again only train from the second hidden layer on so that the number of parameters remains fixed.

Figure8: Training acts to stabilize the input-output map by decreasing trajectory length for σ w large. The left pane plots the growth of trajectory length as a circular interpolation between two MNIST datapoints is propagated through the network, at different train steps. Red indicates the start of training, with purple the end of training. Interestingly, and supporting the observation on remaining depth, the first layer appears to increase trajectory length, in contrast with all later layers, suggesting it is being primarily used to fit the data. The right pane shows an identical plot but for an interpolation between random points, which also display decreasing trajectory length, but at a slower rate. Note the output layer is not plotted, due to artificial scaling of length through normalization. The network is initialized with σ 2 w = 16. A similar plot is observed for the number of transitions (see Appendix.)

Figure9: Training increases expressivity of input-output map for σ w small. The left pane plots the growth of trajectory length as a circular interpolation between two MNIST datapoints is propagated through the network, at different train steps. Red indicates the start of training, with purple the end of training. We see that the training process increases trajectory length, likely to increase the expressivity of the input-output map to enable greater accuracy. The right pane shows an identical plot but for an interpolation between random points, which also displays increasing trajectory length, but at a slower rate. Note the output layer is not plotted, due to artificial scaling of length through normalization. The network is initialized with σ 2 w = 3.

be the ith row of W (0) , b (0) i the bias, we have the hyperplane W (0) i x + b i = 0 for a ReLU and hyperplanes W (0) i x + b i = ±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 polytope R i . Then the activation pattern on layers ≤ d-1 is constant on R i , and so the input to v (d) i

Let the number of regions (connected open sets bounded on some sides by the hyperplanes) be r(k, m). Then r

Figure 11: An identical plot to Figure 8 but for transition count.

Expressive power depends only on remaining network depth. Here we plot the number of dichotomies achieved by sweeping the weights in different network layers through a 1-dimensional great circle trajectory, as a function of the remaining network depth. The number of achievable dichotomies does not depend on the total network depth, only on the number of layers above the layer swept. All networks had width k = 128, weight variance σ 2 w = 8, number of datapoints s = 15, and hard-tanh nonlinearities. The blue dashed line indicates all 2 s possible dichotomies for this random dataset.

Table content: <table><tr><td/><td/><td>Unique Dichotomies</td><td>10 2 10 3 10 4 10 5</td><td colspan="4">Dichotomies vs. Remaining Depth Layer swept = 1 Layer swept = 4 Layer swept = 8 Layer swept = 12 All dichotomies</td><td/></tr><tr><td/><td/><td/><td>10 1</td><td colspan="4">Remaining Depth d r 0 2 4 6 8 10 12 14 16</td><td/></tr><tr><td>0.3 0.4 0.5 0.8 0.9 1.0 Figure 5: 0 0.6 0.7 Accuracy</td><td>100</td><td colspan="3">200 Train Accuracy Against Epoch 300 400</td><td>500 0</td><td>100</td><td>200 Test Accuracy Against Epoch 300</td><td>400</td><td>500</td><td>lay 2 lay 3 lay 4 lay 5 lay 6 lay 7 lay 8 lay 9</td></tr><tr><td/><td/><td colspan="3">Epoch Number</td><td/><td/><td>Epoch Number</td><td/></tr></table>

List and location of key theoretical and experimental results.

Table content: <table/>

The network is initialized with σ 2 w = 16. A similar plot is observed for the number of transitions (see Appendix.)

Table content: <table><tr><td>10 2</td><td/><td/><td>MNIST inputs</td><td/><td colspan="3">Trajectory Length during training</td><td/><td colspan="3">Random inputs</td><td/><td/></tr><tr><td>Trajectory Length</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>10 1</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>0</td><td>2</td><td>4</td><td>6</td><td>8</td><td>10</td><td>12</td><td>0</td><td>2</td><td>4</td><td>6</td><td>8</td><td>10</td><td>12</td></tr><tr><td/><td/><td/><td>Layer number</td><td/><td/><td/><td/><td/><td/><td>Layer number</td><td/><td/><td/></tr></table>

Peer review (iclr2017):
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 ggeq 0. For expressing asymptotic lower bounds one can use the notation Omega (see https://en.wikipedia.org/wiki/Big_O_notation). - It would be helpful to mention that the expectation is being taken with respect to the network weights and that these are normally distributed with variance sigma. - Theorem 2. Here it would be good to be more specific about the kind of sign transitions. Is this about transitions at any units of the network, or about sign transitions at the scalar output of the entire network. - Theorem 3 is quite trivial. The bijection between transitions and activation patterns is not clear. Take a regular n-gon in the plane and a circle that crosses each edge twice. This makes 2n transitions but only n+1 activation patterns. - Theorem 4. Where is the proof of this statement? How does this relate to the simple fact that each activation pattern corresponds to the vector indicating the units that are `active*? MINOR COMMENTS - The names of the theorems (e.g. ``Bound on ...** in Theorem 1) could be separated more clearly from the statements, for instance using bold font, a dot, or parentheses. - On page 4, in Latex one can use gg for the `much larger* symbol. - On page 4, explain the notation delta z_orth. - On page 4, explain that ``latent image** refers to the image in the last layer. - Why are there no error bars in Figure 2? - On page 5 explain that the hyperplane is in the last hidden layer. - On page 5, ``is transitioning for any input**. This is not clearly stated, since a transition takes place at a point in a trajectory of inputs, not for a single input. - The y-axis labels in Figure 1 (c) and (d) are too small. - Why are there no error bars in Figure 1 (a) and (b)? The caption could at least mention that shown are the averages over experiments. - In Figure 4 (b) the curves are occluded by the labels. - The numbering of results is confusing. In the Appendix some numbers are repeated with the main part and some are missing. - On page 19. Theorem 6. As far as I remember Stanley also provides an elementary proof of case with hyperplanes in general position. Many other works also provide elementary proofs using the same induction arguments in what is known as the sweep hyperplane method.