Workshop track -ICLR 2018 BENEFITS OF DEPTH FOR LONG-TERM MEMORY OF RECURRENT NETWORKS
The key attribute that drives the unprecedented success of modern Recurrent Neural Networks (RNNs) on learning tasks which involve sequential data, is their ever-improving ability to model intricate long-term temporal dependencies. However, a well established measure of RNNs' long-term memory capacity is lacking, and thus formal understanding of their ability to correlate data throughout time is limited. Though depth efficiency in convolutional networks is well established by now, it does not suffice in order to account for the success of deep RNNs on inputs of varying lengths, and the need to address their 'time-series expressive power' arises.
In this paper, we analyze the effect of depth on the ability of recurrent networks to express correlations ranging over long time-scales. To meet the above need, we introduce a measure of the information flow across time that can be supported by the network, referred to as the Start-End separation rank. Essentially, this measure reflects the distance of the function realized by the recurrent network from a function that models no interaction whatsoever between the beginning and end of the input sequence. We prove that deep recurrent networks support StartEnd separation ranks which are exponentially higher than those supported by their shallow counterparts. Moreover, we show that the ability of deep recurrent networks to correlate different parts of the input sequence increases exponentially as the input sequence extends, while that of vanilla shallow recurrent networks does not adapt to the sequence length at all. Thus, we establish that depth brings forth an overwhelming advantage in the ability of recurrent networks to model long-term dependencies, and provide an exemplar of quantifying this key attribute which may be readily extended to other RNN architectures of interest, e.g. variants of LSTM networks. We obtain our results by considering a class of recurrent networks referred to as Recurrent Arithmetic Circuits (RACs), which merge the hidden state with the input via the Multiplicative Integration operation.
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.