Exponential expressivity in deep neural networks through transient chaos
We combine Riemannian geometry with the mean field theory of high dimensional chaos to study the nature of signal propagation in generic, deep neural networks with random weights. Our results reveal an order-to-chaos expressivity phase transition, with networks in the chaotic phase computing nonlinear functions whose global curvature grows exponentially with depth but not width. We prove this generic class of deep random functions cannot be efficiently computed by any shallow network, going beyond prior work restricted to the analysis of single functions. Moreover, we formalize and quantitatively demonstrate the long conjectured idea that deep networks can disentangle highly curved manifolds in input space into flat manifolds in hidden space. Our theoretical analysis of the expressive power of deep networks broadly applies to arbitrary nonlinearities, and provides a quantitative underpinning for previously abstract notions about the geometry of deep functions.
The main results in this paper: 1) Deep neural networks are expressive. Specifically, an L-deep network will typically (with the right scaling of the weights) map any 1D curve in its input to a curve which has non-vanishing curvature and euclidian length exponentially increasing in L.  2) Shallow neural networks are not expressive. Specifically, for any given 1D curve in the input, a bound is derived on the elucidation length of the curve at the hidden layer.  Thus, deep networks are more expressive then shallow networks.
This is a very interesting work. However, I have a few major concerns:   1) I believe Theorem 1 is wrong, as can be seen from the counterexample at the bottom of this review. As can be observed from this counterexample, the main problem in the proof is the inaccurate sentence on lines 110-112 in the supplementary material. I'll wait to author's feedback before deciding if this a fatal flaw.  2) I believe the statement that h_i^l are uncorrelated random variables (line 69 in paper + line 22 in supplementary material) is wrong for l > 1 (i.e., second hidden layer, or deeper). In this case, h_i^l are all composed of different linear sums of the same random vector x^{l-1}, and are therefore dependent. I agree this dependency should vanish in the limit of large N and random W, but this should be clearly stated and quantified (to prevent potential issues when applying similar calculations for trained networks).  3) The authors should explain the novelty of their results in comparison to those in the recent ICML paper “Convolutional Rectifier Networks as Generalized Tensor Decompositions” by Cohen et al.  Minor comments:  4) Section 1 is very similar to section G in the supplementary material of “Exact solutions to the nonlinear dynamics of learning in deep linear neural networks” by Saxe et al. I feel this similarity should be stated and discussed. For example, Saxe et al. suggested that it is good to initialize near the transition to Chaos. It would be nice if the authors can clarify if this is related to the results in the current paper.  5) It would be nice if the authors could clarify how one should to use eq. (9) for non-differentiable activation functions (e.g., the popular ReLU).   6) Most of the paper is written very clearly, except Section 5, which feels a bit rushed. I think it should be improved or removed.  7) There are a few typos. For example, in the caption of fig. 3:  “5 and 10” -> “5,10 and 15” “ 6 “ -> “ (6)”  (in two places).  *** Counterexample *** x^0(t) = ( -2t , 2t+sin(t) ) which is a curve over some range 0 < t < 2*pi*M, where M is an positive integer (and we replaced \theta from the paper with t). Taking the derivative: d x^0(t) / dt = ( -2 , 2+cos(t) ) we see that s=0. Choosing N1=1,W=(1,1), b=0 and activation function  \phi(h) = min(1,max(-1,h)) (so R=2) we get  d x^1(t)  / dt  = d h^1(t)  / dt = cos(t) Therefore, the total Euclidian length is L^E=int _ 0 ^ {2*pi*M} |cos(t)| dt = 4*M , which is larger than the bound in Theorem 1:  N1*(1+s)*R = 1*1*2 = 2.   %% After Rebuttal %% 1) Correction of Theorem 1 looks good. I hoped this would be possible. 2) Yes, I was wrong here. Sorry for the confusion. 3) Sure, I understand your method is more true for more general activation functions. Still it would be very helpful to the reader if the authors place their results within the right context. For example, if you restrict yourself to the setting (ReLU+MaxPooling) in Cohen&Shashua 2016, can you get different/better results?  Thanks for this nice paper!