Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors of this paper first present a class of networks inspired by various tensor decomposition models. Then they focus on one particular decompostion known as the tensor train decomposition and points out an analogy between tensor train networks and recurrent neural networks. Finally the authors show that almost all tensor train networks (exluding a set of measure zero) require exponentially large width to represent in CP networks, which is analogous to shallow networks.

While I enjoyed reading the gentle introduction, nice overview of past work, and the theoretical analysis that relates the rank of tensor train networks to that of CP netowkrs, I wasn't sure how to translate the finding into the corresponding neural network models, namely, recurrent neural networks and shallow MLPs.

For example, 
 * How does the "bad" example (low TT-rank but exponentially large CP-rank) translate into a recurrent neural network?
 * For both TT-networks and CP-networks, there are multilinear interaction of the inputs/previous hidden states. How precise is the analogy? Can we somehow restrict the interactions to additive ones so that we can exactly recover MLPs or RNNs?

I also did not find the experiments illuminating. First of all the authors need to provide more details about how CP or TT networks are applies to MNIST and CIFAR-10 datasets. For example, the number of input patches and the number of hidden units, etc. In addition, I would like to see the performance of RNNs and MLPs with the same number of units/rank in order to validate the analogy between these networks. Finally I think it makes sense to try some sequence datasets for which RNNs are typically used.

Minor comments:
 * In p7 it would help readers to point out that B^{(s,t)} is an algebraic subset because it is an intersection of M_r and the set of matrices of rank at most q^{d/2} - 1, which is known to be algebraic.
review_title: Some gap between theory and practice

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper investigates an expressive power of the tensor train decomposition relative to the CP-decomposition. The result of this paper is interesting and also important from a viewpoint on analysis for the tensor train decomposition.

However, I think there is some room for improvement on this paper. Comments are as follow.

C1.
Could you describe more details about the importance of an irreducible algebraic variety? Especially, it will be nice if authors provide practical examples of tensors in $\mathcal{M}_r$ and tensors not in $\mathcal{M}_r$. The present description about $\mathcal{M}_r$ is too simple and thus I cannot judge whether the restriction on $\mathcal{M}_r$ is critical or not.

C2. 
I wonder that the experiment for comparing TT-decomposition and CP-decomposition is fair, since CP-decomposition does not have the universal approximation property. Is it possible to conduct numerical experiments for comparing the ranks directly? For example, given a tensor with known CP-rank, could you measure the TT-rank of the tensor? Such experiments will improve persuasiveness of the main result presented in this paper.
review_title: Important result, but some room for improvement.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.
review_title: An interesting theoretical paper

Meta-review: This paper offers a theoretical and empirical analysis of the expressivity of RNNs, in particular in comparison to TT decomposition. The reviewers argued the results was interesting and important, although there were issues with clarity of some of the explanations. More critical reviewers argued the comparison basis with CP networks was not "fair" in that their shallowness restricted their expressivity w.r.t. TT. The experiments could be strengthened by making the explanations surrounding the set up clearer. This paper is borderline acceptable, and would have benefited from a more active discussion between the reviewers and the author. From reading the reviews and the author responses, I am leaning towards recommending acceptance to the main conference rather than the workshop track, as it is important to have theoretical work of this nature discussed at ICLR.
Decision: Accept (Poster)