Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: After reading the authors's rebuttal I increased my score from a 7 to a 6.  I do think the paper would benefit from experimental results, but agree with the authors that the theoretical results are non-trivial and interesting on their own merit.

------------------------
The paper presents a theoretical analysis of depth in RNNs (technically a variant called RACs) i.e. stacking RNNs on top of one another, so that h_t^l (i.e. hidden state at time t and layer l is a function of h_t^{l-1} and h_{t-1}^{l})

The work is inspired by previous results for feed forward nets and CNNs. However, what is unique to RNNs is their ability to model long term dependencies across time. 

To analyze this specific property, the authors propose a concept called "start-end rank" that essentially models the richness of the dependency between two disjoint subsets of inputs. Specifically, let S = {1, . . . , T/2} and E === {T/2 + 1, . . . , T}. sep_{S,E}(y) models the dependence between these two sets of time points. Specifically sep_{S,E}(y) = K means there exists g_s^k and g_e^k for k=1...K such that y(x) = \sum_{k} g_s^k(x_S) g_e^k(x_E).

Therefore sep_{S,E}(y) is the rank of a particular matricization of y (with respect to the partition S,E). If sep_{S,E}=1 then it is rank 1 (and would correspond to independence if y(x) was a probability distribution). A higher rank would correspond to more dependence across time. 

(Comment: I believe if I understood the above correctly, it would be easier to explain tensors/matricization first and then introduce separation rank, since I think it much makes it clearer to explain. Right now the authors explain separation rank first and then discuss tensors / matricization).

Using this concept, the authors prove that deep recurrent networks can express functions that have exponentially higher start/end ranks than shallow RNNs.

I overall like the paper's theoretical results, but I have the following complaints:

(1)  I have the same question as the other reviewer. Why is Theorem 1 not a function of L?  Do the papers that prove similar theorems about ConvNets able to handle general L? What makes this more challenging? I feel if comparing L=2 vs L=3 is hard, the authors should be more up front about that in the introduction/abstract.

(2) I think it would have been stronger if the authors would have provided some empirical results validating their claims. 


review_title: Interesting theory, could benefit from some experiments

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes to use the start-end rank to measure the long-term dependency in RNNs. It shows that deep RNN is signficantly better than shallow one in this metric. 

The theory part seems to be technical enough and interesting, though I haven't checked all the details. The main concern with the paper is that I am not sure whether the RAC studied by the paper is realistic enough for practice. Certain gating in RNN is very useful but I don't know whether one can train any reasonable RNN with all multiplicative gates. The paper will be much stronger if it has some experiments along this line. 
review_title: review 

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper investigates an effect of time dependencies in a specific type of RNN.

The idea is important and this paper seems sound. However, I am not sure that the main result (Theorem 1) explains an effect of depth sufficiently.

--Main comment
About the deep network case in Theorem 1, how $L$ affects the bound on ranks? In the current statement, the result seems independent to $L$ when $L \geq 2$. I think that this paper should quantify the effect of an increase of $L$.

--Sub comment
Numerical experiments for calculating the separation rank is necessary to provide evidence of the main result. Only a simple example will make this paper more convincing.
review_title: An effect of increase of $L$ should be evaluated.

Meta-review: This paper attempts a theoretical treatment of the influence of depth in RNNs on their ability to capture dependencies in the data. All reviewers found the theoretical contribution of the paper interesting, and while there were problems raised regarding formalisation, they appear to have been adequately addressed in the revisions to the paper. The main concern in all three reviews surrounds the evaluation, and weakness thereof. The overarching point of contention seems to be that the theory relates to a particular formulation of RNNs (RAC), causing doubts that the results lift to other architectural variants which are used to obtain state-of-the-art results on tasks such as language modelling. It seems that the paper could be significantly improved by the provision of stronger empirical results to support the theory, or a more convincing argument as to why the results should transfer from, say, RAC to LSTMs. The authors point to two papers on the matter in their response, but it is not clear this is a substitute for experimental validation. I find the paper a bit borderline because of this, and recommend redirection to the workshop.
Decision: Invite to Workshop Track