Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides theoretical studies for why encoder-decoder can be seen as a generalization of RNNs in time-inhomogenous sequence modeling. The authors put an impressive amount of effort into mathematically defining approximation properties of RNN encoder-decoders beginning from a universal approximation result. 

The authors first show the universal approximation property of RNN encoder-decoders, and subsequently, they show approximation rates of targets for RNN encoder-decoders. They introduce a notion of temporal products that can characterize the temporal relationships in the input/output pair. 
main_review: This paper studies the approximation properties of RNN encoder-decoders, in the perspective of linear and continuous time. The authors first show the universal approximation property of a linear RNN encoder-decoder, then extends to the approximation rates that can be characterized by the rank of temporal products. The authors show that the temporal product structure may be the intrinsic structure arising from the encoder-decoder architecture.

Pros: 
* Rigorous mathematical proofs that the encoder-decoder using linear RNN as the base building block is a more general form of sequence model that includes linear RNNs in its hypothesis space.
* Mathematically prove that the encoder-decoder architectures are a better fit for modeling time-inhomogenous sequence modeling problems.

Cons:
* The impact is somewhat limited by assuming linear and continuous-time for proving the approximation properties of RNN encoder-decoder, which is not the case in reality. 
* Requires high-level mathematical skills to follow the paper, which might not be a good fit for ICLR considering the main audience who usually seeks rigorous experiments that back up the claims.
summary_of_the_review: Overall, a good mathematical study is important to have in a fast-moving field that certainly lacks theoretical results. However, I find that this study might not be that helpful practically as the setting is limited in linear RNN encoder-decoder setup, which is unlikely to be considered as a main choice of architecture these days. Also, as an ML researcher, it is a bit hard to follow a paper that is written in a formal mathematical style with a very small experiment at the end.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides theoretical insight for approximation properties of RNN encoder-decoder architecture in linear setting. More specifically, they study supervised learning problem of temporal modelling where a first RNN encodes a given sequence into a coding vector and a second RNN is responsible to decode said vector to a target output sequence. Linear setting here refers to a linear and continuous-time idealization in eq 6.

Their analysis summarized as following:
1.  Universal approximation: any linear, continuous, and regular temporal relation can be approximated by RNN encoder-decoder up to arbitrary accuracy.
2.  Approximation rate for large size coding vector: beside width of encoder and decoder, this error bound depends on $\alpha$ smoothness of $\mathbf{H}$ and $\beta$ temporal decay rates of the output of constant signal under $\mathbf{H}$ where $\mathbf{H}$ is a sequence of linear, continuous, and regular functionals on inputs. Each $\mathbf{H}$ has a unique two-parameter representation $\rho(t,s)$. Target functionals that are smooth and have fast decaying memory are identified as good target of this approximation.
3.  Approximation rate for small size coding vector: the architecture and the following assumptions in the paper give rise to an intrinsic structure to this type of RNN encoder-decoders called temporal product structure which can be deconstructed into encoder and decoder parts. By relating this structure to rank of temporal relationships they show approximation rate (in small size coding vector) is additionally a function of rank structure of target relationship. This analysis enables us to see the coding vector size as a knob to control number of parameters vs approximation error.
4.  Experiments: they show that the theoretical analysis holds in their experiments.
main_review: I'd like to thanks the authors for their submission. I enjoyed reading it.

Overall, I think the paper is well-written, well-motivated, and is a good theoretical insight into one of the first types of DNN structures for sequence to sequence translation. I appreciate the fact that in a few instances (e.g. "The rank concept of temporal relationships") the paper poses a question, takes its time to explain the concepts and its generalization while trying to build intuition by explaining it in lower dimensional examples. It also does a good job of distinguishing itself from a previous closely related paper, Li et al. (2021). However, I have to say that since I am not following this line of research closely I cannot judge this work in context of existing works.

There are, however, a few concerns and questions:
1.  Authors mention "classical" or "traditional" RNN a few times. It is a bit vague to me what the opposite of that refers to? The RNN that the paper introduces here?
2.  In the related work section, it would be interesting to see what your type of analysis enables us in compare to other works.
3.  Eq. 1 and 2: any intuition as to why input space should vanish at infinity and output space should be bounded?
4.  Before eq. 4: "resulting from convolve" $\rightarrow$ "resulting from convolving"?
5.  Eq. 5 and 6 and the surrounding text is confusing. 5.1. $\sigma_E, \sigma_D, \sigma_O, \tau$ are not defined. 5.2. coding vector is introduced as $c$ which doesn't show up in equations. Again, coding vector is named $v$. 5.3. The equation for $g_t$ seems to be wrong? From reading the text I think it should be $g_t=\sigma_D(W_D g_{t-1} +b_D)$. 5.4. $h_0$ is missing.
6.  Is there any ramification for "linear and continuous-time idealization" before eq 6? A more intuitive explanation of this assumption is also appreciated.
7.  Eq. 7 and 8: the fact that one needs negative real parts in eigenvalues to ensure stability over long horizons is not explained.
8.  Authors on occasions focus on time-homogeneity and use it to distinguish their work from Li et al. (2021). In my opinion, it would be better if authors introduce this concept, its significance and motivation a bit sooner in the paper.
9.  Second paragraph in section 4.2: "where the dimension of the $N$..." $\rightarrow$ "where $N$..."
10.  Eq 11: $C^{(\alpha+1)}$ with superscript is not defined.
11.  Theorems 4.2 and 4.3 both discuss existence but not construction of these approximations. There is a section in appendix that discusses numerical illustrations. A discussion on algorithms to find these approximations and their nuances, even a short one, in the main text is appreciated.
12.  A discussion of the type of important assumptions that are used make these theoretical insights, how strong they are, and how far they are from the architectures that practitioners use today is welcomed.
summary_of_the_review: Generally a good paper that tries to theoretically explain the approximation power of RNN encoder-decoder architecture, although in linear and continuous-time setting. It provides intuition for the required characteristics of the target to ensure low approximation error and how to control number of parameters vs approximation error. A few places in the text and equations need authors' attention and better explanation of some assumptions are required.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides a theoretical analysis of both the universal approximation and the approximation rate of the RNN encoder-decoder in a linear setting. 
main_review: Overall, the paper is very well written. The summary of the theoretical results in the paper is neat, clear, and important. Detailed proof is provided for all propositions and theorems. The authors properly emphasize the difference between this work and previous related work. 

My only concern is that I think it would be helpful for the readability by providing a brief introduction of the time-homogeneous functionals, Eq. 6 - 9, besides the math definition, though readers could find more detailed information in Li et al. (2021). Also, In Equation 5, h_\tau is not clearly defined as the last hidden state.  
summary_of_the_review: This paper gives interesting notions and discoveries on the approximation properties of the recurrent encoder-decoder structure, and the statements are rigorous.
review_title: null

Meta-review: This paper presents a theoretical analysis of the approximation properties of linear recurrent encoder-decoder architectures, obtaining universal approximation results and subsequently showing approximation rates of targets for RNN encoder-decoders. It introduces a notion of "temporal products," which helps to characterize the types of temporal relationships that can be efficiently learned in this setting.

Overall, the reviewers and I all agree that this paper makes important theoretical contributions to the important problem of the approximation capabilities of encoder-decoder architectures. The main weaknesses involve the rather simplified linear problem setup, but this limitation is easily forgiven in this first-of-its-kind rigorous analysis. I recommend acceptance.
Decision: Accept (Spotlight)