EXPRESSIVE POWER OF RECURRENT NEURAL NET- WORKS
Deep neural networks are surprisingly efficient at solving practical tasks, but the theory behind this phenomenon is only starting to catch up with the practice. Numerous works show that depth is the key to this efficiency. A certain class of deep convolutional networks -namely those that correspond to the Hierarchical Tucker (HT) tensor decomposition -has been proven to have exponentially higher expressive power than shallow networks. I.e. a shallow network of exponential width is required to realize the same score function as computed by the deep architecture. In this paper, we prove the expressive power theorem (an exponential lower bound on the width of the equivalent shallow network) for a class of recurrent neural networks -ones that correspond to the Tensor Train (TT) decomposition. This means that even processing an image patch by patch with an RNN can be exponentially more efficient than a (shallow) convolutional network with one hidden layer. Using theoretical results on the relation between the tensor decompositions we compare expressive powers of the HT-and TT-Networks. We also implement the recurrent TT-Networks and provide numerical evidence of their expressivity.
In this paper, the expressive power of neural networks characterized by tensor train (TT) decomposition, a chain-type tensor decomposition, is investigated. Here, the expressive power refers to the rank of tensor decomposition, i.e., the number of latent components. The authors compare the complexity of TT-type networks with networks structured by CP decomposition, which corresponds to shallow networks. It is proved that the space of TT-type networks with rank O(r)  can be complex as the same as the space of CP-type networks with rank poly(r).
The paper is clearly written and easy to follow. 
The contribution is clear and it is distinguished from previous studies.
Though I enjoyed reading this paper, I have several concerns.
1. The authors compare the complexity of TT representation with CP representation (and HT representation). However, CP representation does not have universality (i.e., some tensors cannot be expressed by CP representation with finite rank, see [1]), this comparison may not make sense. It seems the comparison with Tucker-type representation makes much more sense because it has universality. 
2. Connecting RNN and TT representation is a bit confusing. Specifically, I found two gaps.
   (a) RNNs reuse the same parameter against all the input x_1 to x_d. This means that G_1 to G_d in Figure 1 are all the same. That's why RNNs can handle size-varying sequences. 
   (b) Standard RNNs do not use the multilinear units shown in Figure 3, but use a simple addition of an input and the output from the previous layer (i.e., h_t = f(Wx_t + Vh_{t-1}), where h_t is the t-th hidden unit, x_t is the t-th input, W and V are weights, and f is an activation function.) 
Due to the gaps, the analysis used in this paper seems not applicable to RNNs. If this is true, the story of this paper is somewhat misleading. Or, is your theory still applicable?
[1] Hackbusch, Wolfgang. Tensor spaces and numerical tensor calculus. Vol. 42. Springer Science & Business Media, 2012.