On the approximation properties of recurrent encoder-decoder architectures
Authors: Zhong Li
Haotian Jiang
Qianxiao Li
Venue: ICLR 2022 Spotlight (2022)
Keywords: encoder-decoder
recurrent neural networks
approximation
temporal product

Abstract: Encoder-decoder architectures have recently gained popularity in sequence to sequence modelling, featuring in state-of-the-art models such as transformers. However, a mathematical understanding of their working principles still remains limited. In this paper, we study the approximation properties of recurrent encoder-decoder architectures. Prior work established theoretical results for RNNs in the linear setting, where approximation capabilities can be related to smoothness and memory of target temporal relationships. Here, we uncover that the encoder and decoder together form a particular “temporal product structure” which determines the approximation efficiency. Moreover, the encoder-decoder architecture generalises RNNs with the capability to learn time-inhomogeneous relationships. Our results provide the theoretical understanding of approximation properties of the recurrent encoder-decoder architecture, which precisely characterises, in the considered setting, the types of temporal relationships that can be efficiently learned.

Published as a conference paper at ICLR 2022
ON THE APPROXIMATION PROPERTIES OF RECUR- RENT ENCODER-DECODEN ARCHITECTURES
Zhong Li'
Haotian Jiang"
School of Mathematical Sciences Peking University 1i zhongopuuueduuuu cn
Department of Mathematics National University of Singapore e00126638u. nus. edu
Qianxiao Lit
Department of Matherntiics National University of Singapore gianxiao@nus. edu.
ABSTRACT
Encoder-decoder architectures have recently gained popularity in sequence to sequence modelling, featuring in state-of-the-art models such as trans- formers. However, mathematical understanding of their working princi- ples still remains limited. In this paper, we study the approximation prop- erties of recurrent encoder-decoder architectures. Prior work established theoretical results for R.NSs in the linear setting, where approximation capabilitics can be related to smoothness and memory of target temporal relationships. Here, we uncover that the encoder and decoder together form partieular "temporal product structure" which determines the approxi- mation efficiency. Moreover, the encoder-decoder architecture generalises RNNs with the capability to learn inmniionooogeeouuus relationships. Our results provide the theoretical understanding of approximation properties of the recurrent encoder-decoder architecture, which precisely characterises, in the considered sctting, the types of temporal relationships that can be efficiently learned.
INTRODUCTION
Encoder-decoder is an increasingly popular architecture for sequence to sequence modelling problems (Sutskever et al.) 2014 Chiu al.] 2018 Venugopalan et al. 2015). The core of this architecture is to first encode the imput sequence into a vector using the encoder and then map the vector into the output sequence through the decoder. In particular, such architecture forms the main component in the transformer network (Vaswani et al. 2017), which has become a powerful method for modelling sequence to soquence relationships Parmar el al. 2018 Bellagy et al. 2020 Li et al. 2019).
The encoder-decoder family of structures differ significantly from direct application of recur- 19900)) and its generalisations (Hochreiter & Schmid huber 1997 Cho et al. 2014b) for processing sequences. However, both architectures can be considered modelling mappings between sequences, albeit with different underlying structures. Hence, a natural but unresolved question is: how are these approaches funda- mentally different? Answering this question is not only of theoretical importance but also of practical interest. Currently, architectural selection for different time series modelling lasks is predominantly empirical. Thus, is desirable to develop a concrete mathemati- cal framework to understand the key differences between separate architect ures in order to guide practitioners in principled way.
rent. neural networks (RNNs, Elman
"quual contribution
1 "Corresponding author

---

Published as a conference paper at ICLR 2022
In this paper, we investigate the approximation properties of encoder-decodee architectures. Approximation is one of the most basic and important problems for supervised learning. It considers to what extent the model can fit target. In particular, prove general approx- imation result. in the linear setting, which characterises the types of temporal input-output relationships that be efficiently approximated by encoder-decoder architectures. These results reveal that such architectures essentially generalise RNNs by lifting the requirement of sime-homogeneity (see Remark 3.2) in the target relationships. Hence, it can be used to tackle broader class of sequence to sequence problems. Furthermore, of particular in- terest is the identification of a "temporal product structure" a precise property of the larget temporal relationship that highlights another intrinsic difference between recurrent encoder-decoders and RNNs.
Our main contributions can be summarised as follows.
1. We prove a universal approximation result for recurrent encoder-decoder architec- tures in the linear setting, including the approximation rates.
2. We show that in the considered setting, the recurrent encoder-decoder generalises the RNNs and can approximate time-inhomogencous relationships, which further adapt to additional temporal product structures in the target relationship. This answers prociscly how encoder-decoders are different from RNNs, at least in the considered setting.
Organisation. In Section 2 we review the related work on encoder-decoder architectures and general approximation theories of sequence modelling. The approximation problem is formulated in Section 3 Our main results, their consequences and numerical illustrations
are presented in Section 4 All the proofs and numerical details included in appendices.
Notations. For consistency, we adhere to the following notations. Boldfaced letters are reserved for sequences or paths, which can be understood as functions of time. Lower case letters can mean vectors or scalars. Matrices are denoted by capital letters. For a E N, C denotes the space of functions with continuous derivatives up to order-a.
2 RELATED WORK
We first review some previous works on sequence to sequence modelling. The encoder- decoder architecture first appeared in Kalchbrenner Blunsom (2013), where they map the input sequence into a vector using convolutional neural networks (CNNs), and then using a recurrent structure to map the vector to the output sequence. With the flexibility of manipulating the underlying structure of encoder and decoder, numerous models based this architecture have come out thereafter. For instance, Cho et al. (2014b) used gated RNNs as both the encoder and decoder, while in the later work {Cho et al. 2014a they proposed a CNN- based decoder. In /Susskever et al. (2014), ; they proposed a deep LSTM for both the encoder and decoder. [Badaanau al. (2015) first introduced the attention mechanism, which was further developed in the well-known transformer networks (Vaswani et al. (017)). However, most of the research on eucoder-decoder architectures focused on applications. A theoretical understanding is helpful for its further improvement and development.
From the theoretical point of view, Ye & Sung (2019) studied several theoretical properties of CNN encoder-decoders; including expressiveness, generalisation capability and optimisation landscape. Of particular relevance the current work is expressiveness, which considers the relationships that can be generated from the architecture. However, this is not approx- imation. Yun al. (020)) proved the universal approximation property of transformers for certain classes of functions, for example, permutation equivariant functions, but they did not consider the actual dynamical properties of target relationships that affect approximation. Dynamical proprieties such memory, smoothness and low rank structures because they can preciscly characterise different temporal relationships and affect the ap- proximation capabilities of models. Assuming the target generated from a hidden dynamical system is one approach, which is widely applied [Masss et al. 2007 Schäfer & Zimmermann 2007 Doya 1993 Funahashi & Nakamura, 1993) In contrast, functional- approach is
essential,
2

---

Published as a conference paper at ICLR 2022
recently introduced, where the target temporal relationships are generated from functionals satisfying specific properties such as linearity, contimuity, regularity and himeenomoyyyeity (Li et al, 2021]. In Li et al. (2021), the approximation properties of linear RNN models are studied, and the results therein show that the approximation efficiency is related to the memory structure. Tn Jiang al. (2021), similar formulations are applied to investigate convolutional architectures, where the results suggest that targets with certain spectrum regularity can be well approximated by dilated CNNs. Under this framework, the target temporal relationship that can be efficiently approximated is characterised by properties such as memory, smoothness and sparsity. This enables us make precise mathemati- cal comparisons between different architectures. Our results in this work reveal that the encoder-decoders have a special temporal product structure which is intrinsically different. from other sequence modelling architectures.
3 PROBLEM FORMULATION
In this section, we precisely define the input space, output space, concept space and hy- pothesis space, respectively.
Functional formulation of temporal modelling. First, we define the input and output space precisely. A temporal sequence can be viewed as a function of time t. The input space defined by X' = Co((=oo, Ik.. This is the space of continuous functions from (-oo, 0] to Rd vanishing at infinity, where d N4 is the dimension. Denote the element in X' by x = {xz E Rd t S 0}, we equip X with the supremum norm ||>||x := supiço || We take the outputs space as y = C,O, oo), R), the space of bounded continuous functions from [0, 20) to R. We consider real-valued outputs, since each dimension can be handled individually for vector-valued outputs.
The mapping between imput and output sequences can be formulated as sequence of functionals, i.e. y/2 = (x), t 2 0. The output y at the time step depends on the input sequence The ground truth relation between inputs and outputs is formulated by the sequence of functionals H = (H, :t 0}.
We provide example to illustrate the above formulation. Given input æ, the output is a smoothed version of æ, resulting from convolving æ with the Gaussian kernel g(s)
exp(- This relation can be formulated ye Hz(x) 0 g(t + sds V2x
The RNN encoder-decoder model. For the supervised learning problem, our goal is to use a model to learn the target relationship H. First, we define the model. Among all different variants of the encoder-decoder architectures, the RNN encoder-decoder introduced in Cho et al. (2014b) can be considered as the most simple and representative model, where the encoder and decoder are both RNNs. We study this particular model as we try to eliminate other factors and only focus the encoder-decoder architecture itself.
Under our setting, the simplified model of Cho al. (014b) with RNNs as both encoder and decoder can be formulated as
he ( Upa, + bE),
hr
= oD (W
(1)
Ot Wos. bo,
where he, It are hidden states of the encoder and decoder respectively. Recurrent activation functions are denoted by og and dp. Here, 7 denotes the terminating time step of the encoder, and the summary of the input sequence, which is called as the coding vector. The model prediction is denoted as R. All the other notations are model parameters. Equation [I describes the following model dynamics. First, the encoder reads the entire input æ, and then summarises the input into fixed size coding vector v, which is also the last hidden state of the encoder. Next, the coding vector is passed into the decoder as the initial state, and then the decoder produces output at each time step. Note that the encoder has a terminating time, and the decoder has a starting time. This is the reason why we take the input and output semi-infinite sequences.
3

---

Published as a conference paper at ICLR 2022
We study linear, residual and contimuous-tin idcalisation of the model dynamics
h Wh, Un
Qho,
G: = Vgt,
90 Pu;
(2)
= c gt:
f 2 0,
where W R.MEEME, U Rmxxd Q E RNNME, V E Rm P E R and e R are parameters. me and my denote the width of encoder and decoder, respectively. The coding vector has dimension N, where we apply linear transformations to control it. We assume h- = 0, which is the usual choice for the initial condition of RNN hidden states.
Since our goal is to investigate approximation problems over large time horizons, we are supposed to consider the stable RNN encoder-decoders, where
W E Wmn == (W E ME eigenvalues of W have negative real parts), (3)
V Vn == {V E R=DXND eigenvalues of have negative real parts}. (4)
The hypothesis space of RNN encoder-decoder models with arbitrary widths and coding vector dimension defined as H Ume. Hmg.mo,N, where
Qe Ux_,xs, with Hmg..D.N = { A (A: [ (A: 2 03 1.(x)) = =cee [0
(5)
(W. U, Q.V. E Wmn x Rmxxd xd x Nxmm x Vmn x R x RD
The widths mg, mp and the coding vector dimension N together control the capac- ity / /complexity of the hypothesis space. Note that the assumptions eigenvalues of W and V ensure that the parameterized lincar functionals are contimous.
Due to the mathematical form (5), not all functionals can be reprosented by RNN encoder- decoders. To achieve a good approximation, the larget functionals must possess certain structures. We introduce the following definitions to clarify these structures.
Definition 3.1. Let H [1f: 0} be sequence of functionals.
1. For any 2 O, the functional H, is linear and continuous if for any Å A2 E R and ,2 E X, we have He(Ai >2ar2) A Ha.)) >2H2(()2), and ||H|| sup=ex 11 [H((z)] < oc, where ||Hll denotes the induced functional norm.
22
2. For any 2 0, the functional H, is regular if for any sequence (x) C X such that limm (! 0 for almost every s S 0 (Lebesgue measure), we have lim (x()
/ ||H.Ildd.
For sequence of functionals H, we define its norm by |
Remark 3.1. The definitions of linear and continuous functionals are standard. One can view regular functionals as those not determined by imputs on arbitrurily small time intervals, e.g. an insonilely thin spike (i.e. 8-funclions).
Given the above definitions, we immediately have the following observation.
Proposition 3.1. Let Ā E A be sequence of functionals in the RNN encoder-decoder
bypothesis space (see 5 ()). Then for any t 2 0, H, E H is linear, continuous and regular function oft.
functional. Furthermore, ||H||| decays exponentiolly
The proof is found in Appendix A This proposition characterises properties of the encoder- decoder hypothesis space. In particular, it is different from the RNN hypothesis space discussed in Li et al. (2021) since the encoder-decoder is not necessarily time-homogeneous
Remark 3.2. sequence of functionals H is homooeoomoeeeouus if for any t, 2 0, H,(x) = H+++(x(7)) with x(r), - for all E Th. That is, if the input is shifted to the right by
4

---

Published as a conference paper at ICLR 2022
T, the output is also shifted by Temporal convolution is czample of time-homogeneous operation (recall the Gaussian convolution discussed in Section S An ezample of time- inhomogeneous relationship is video coptioning: shifts in the sequence of input video frames do not necessarily lead to corresponding shifts in the coption text sequence.
Relation with RNNs. Here, emphasisc the differences between the encoder-docoder hypothesis space and the RNN hypothesis space discussed in Li et al. (2021), where (( (a) Jo c ( structure involving two temporal parameters & and 8, while the RNN only has one depend- ing on + s, due to the time-homogeneity. Owing this difference and the fact that H(RNN) c: H, the encoder-decode hypothesis space (5) more general, with the extra ca- pability to learn time-inhonne hine-inhomogeneous relationships. Furthermore, e and e eWs adapt to temporal product structure, which an intrinsic difference between encodersdecoders and other architectures. We will discuss this in detail in the next section.
A key difference is that the encoder-decoder has
4 APPROXIMATION RESULTS
One of the most fundamental problems for supervised learning the approximation prob- lem. It basically concerns the capacity of the hypothesis space to fit the concept space. In general, there are two levels of approximation problems that can be discussed. The first is known as the universal approximation, which considers the density of the hypothesis space in the concepl, space. The second is the approximation rale, which aims to characterise quantitatively the approximation accuracy concerning the capacity/cone /complexity of the hy- pothesis space (e.g. the number of trainable parameters). In this section, both of them are developed for RNN encoder-decoders
4.1 UNIVERSAL APPROXIMATION
We first present the most basic density result, which states that any linear, continuous, and regular temporal relationship can be approximated by RNN encoder-decoders up to arbitrary accuracy. The proof is found in Appendix B
Theorem 4.1. Lel H be a sequence of lineor, continuous and regulaar functionals defined on X, and satisfy H < co. Then for any >> 0, there enists H E H. such that
H-
|He H.lldt <
First, one can show that each sequence of functionals H E can be associated with unique two- parameter "representation" p(t, such that Hz(x) (x)== =
Here, we highlight two important observations while deriving Theorem 4.1
p x st, s)ds. Recall the model form A.(x) J II,f(t, s)ds, where (tt, s) == (c v PQe " denotes the correspond- ing representation. The functional approximation is then reduced to function approximation in the sense of representations, i.e. H All < (1p--(ll-((0.00))) It turns out that p directly affects the rate of approximation and gives rise to intrinsic properties. We will discuss this 4.3 In addition, we again emphasise the differences between the present work and Li et al. (2021). In Li et al. (2021), the target relationships are assumed to be time- homo-eooogg with the representation H.( = Jo p(t+ s)x= which only depends on & However, the setting here does not assume hono-eoongg,nily,, hence implies more general representation depending on the two temporal directions and simultaneously.
in detail in Section
4.2 GENERAL APPROXIMATION RATES
While the density result (Theorem 4.1 ensures the universal approximation property of the RNN encoder-decoder, it does not identify targets that can be efficiently approximated. To achieve this, focus approximation rates next. We characterise the temporal structure of a target relationship by observing its responses to "constant" imput signals. Here, we consider the approximation rates for the model with "large size" coding vector, where the
5

---

Published as a conference paper at ICLR 2022
dimension N 2 m mp) This is the scenario where we fix the widths but take an oversized coding vector.
Theorem 4.2. Let H be a sequence of linear, continuous and regular functionals defined
on X, and satisfy |H] < 20. Consider the oulput of piece-wise constant signals vf(t,))
(o)-))- 1 2 0, i == 1.2...... where {e:]i=1 denotes the standard basis of IR. Assume that there exist N+, B > such that for any i 11,
Df E ECa+1(00, )0)
(7)
gktl
(((+s)) ae (t, 8) = o(1) as [[(t, + co, (x,,) ++1sa+1.
(8)
Then for any me, mDD N E N+, there crists H E Amggmm.N such that
C(a)nd
.+11) m
H A
(9)
g2
E
where C 0 are both universal constants with dependence only and (a, respeclively, and o == max max sup (((+))
gh+t os of (f, < co. Here,
iEBt.isd K.EN k+1a+11 1,s20
the number of trainable parameters is dN dN + mD) with N N m.
The proof is found in Appendix C First, note that the error bound does not depend on the coding vector size N, long N m. This because further increasing N beyond m only increases the number of trainable parameters, but does not increase the model capacity (see Remark C.2). Only the model widths mg. mD affect the approximation capabilities.
Next, we focus on the classes of target relationships that can be well approximated. Here, characterises the smoothness of H, and characterises the temporal decay rates of the output responding to constant signal under H. This is notion of memory in the target relationship. The error bound (9) indicates that a sequence of target functionals can be elficiently approximated by the encoder-decoder if it is smooth (large a), and has fast decayed memory (large B).
The characterisation in smoothness and memory decay also appears in the approxima- tion results of RNNs (Li ct al. 2021), where the upper bound is C(and However, our 9m results for encoder-decoders suggest extra structures, where the bound involves two (in- stead of one) temporal parameters together with smoothness and decay memories in both. The two-parameter temporal dependence allows the encoder-decoder to approximate time- inhomogeneous relationships, which generalises the RNN. This two- two-parameter structure further leads to adaptation to a specific low rank type of target relationships, resulting in finer approximation rates we discuss next.
4.3 APPROXIMATION RATES VIA TEMPORAL PRODUCT STRUCTURE
Motivation of temporal product structure. In contrast with Theorem 4.2 we next consider the model with N m min(mg, mD). In this situation, the model has fewer paramoters, and we aim to characterise the target relationships by further exploiting the structure of the two-parameter representation p(l, s). This leads to finer approximation rate by considering me, mp, logether.
We first motivate how the "temporal product structure" arises, and how it relates to the approximation. Detailed discussions and proofs are found in Appendix For the illustration purpose, we set the input dimension d 1. Recall Q R Xmmg, P x then the representation á of the encoder-decoder functional can be rewritten as
p(t, s) cT vpp Qe u
Σ
Σ fJ=1
my
c Pnn [e
) me
Σ
u4Qni [ewa]
(t)
(10)

---

Published as a conference paper at ICLR 2022
This is a tensor product structure over the (t, s) time domain (determined by the encoder {dn] and decoder {Pr] successively). We call it the temporal product structure. As is shown later, this structure significantly affects approximation rales. When {Φx} and {&n} are selected as the "bases" along 8, direction, respectively, N is considered as the rank of the temporal product. We also define N as the rank the model, which is understood as the maximum rank of temporal products that the encoder-decoder model can represent.
The rank concept of temporal relationships. Recall that the given number of train- able parameters is dN + mp)) Hence, a low rank model may achieve fewer trainable parameters. When investigating relationships that can be well approximated by low rank models, a natural conjecture would be "low rank" " targets.
What is the meaning of "low rank" for temporal relationship? It is well-known that in linear algebra, an operator low rank means that its range space is low-dimensional. This idea can be also applied to temporal relationships. For "low rank" temporal relationship, the output sequence is more "regular", meaning that the output sequences (viewed as functions) in low-dimensional function space. We provide inluitive numerical illustration for better understanding.
1.5
1.0
30
0.6
DC
1.0
1.5
-10
10 15
75 200
(a) high rank relationship
(b) low rank relationship
Figure 1: We construct a high rank and a low rank target from the temporal product. For both (Ia] and [bb, we plot the inputs H, together with the corresponding outputs (x)..
Detailed settings are found in Appendix E.1
Figure [ shows the outputs of a high rank (a) and a low rank (b) target relationship on the same set of random input sequences. Different colours refer to different instances of inputs. In the first case (high rank), the temporal structure of the outputs is very complex and depends scnsitively on the inputs. However, in the sccond case (low rank), the output sequences are much more regular, and only macroscopic structures (c.g. scale/offset) appear.
Remark 4.1. In the research of approzimation theories for temporal sequences, prior works also related a nolion of rank to approzimation properlies of the dilated convolutional structure Jiang el al., 2021). Here, we emphusise that the nolion of rank considered in our work is very different from that in Jiang et al. (2021), which mainly concerns the tensorisation of discrete time sequence according to the width of convolution filters.
POD an analogue of SVD. Now, we characterise low rank and high rank temporal relationships in a mathematical way. We will introduce the concepts informally, and rigorous definitions and arguments can be found in Appendix D
For a matrix, we can assess its rank by performing the singular value decomposition (SVD). This method can be extended to the temporal relationships using proper orthogo- nal decomposition (POD; Liang et al. (2002). Berkooz et al.) (1993). Chatterjec (2000)) ) The basic insight is that the function P can be decomposed into the following form: p(t, s) NN
No (t)xx(t) where No S oc, {ppx} and {ør} are orthonormal bases, and Ti 2 02 2 ... 2 0 denote the singular values. This procedure can be viewed as apply- ing SVD to an infinitoddimensional space (when N, = oo). An analogue of Eckart-Young thcorem (Eckart & Young. 1936). which characterises the best low rank approximation, also holds for POD. It roughly states that inf (ank()))) Áll32 E of That is,

---

Published as a conference paper at ICLR 2022
any target p has rank-N best approximation, with error equalling to the tail sum of the squared singular values. In other words, a target with fast decayed On (low "effective rank") has smaller approximation errors. This forms the basis of our next result, which states that if the target relationship possesses an effective low rank structure in terms of the decay of singular values, then one achieve efficient. approximation using encoder-decoder structures by limiting the size of coding vectors. Detailed definitions for {an} and proofs are found in Appendix D
Theorem 4.3. Assume the same conditions as in Theorem 4.2 N+ with N < m, there exists H- Hmmg. such that
Then for any m, N
C(and) H H S B
{
m
1/2
(1+Vm
-
+
o
mp
m
N+1
1/2
(11)
x/2
xx/
n=
mE
MDD
D
where S hides universal positive constants, and m = min MD}. Here, the number of trainable parameters is dN(mg mp) with N S m.
This is finer approximation rate compared to Theorem 4.2 where both the widths me, mp and the coding vector size N affect the model capacity for approximation. Besides the smoothness and memory decay, we have the additional rank structure of the target rela- tionship, which is characterised by its singular values {an) We again focus on the class of functionals that can be well approximated. Smoothness and decay rate is the same as Theorem 4.2 The difference lies in the rank structure indicated by {an]: the error bound is small if fan) has a small tail E N==N+1 oh It suggests that a target with fast decayed far, } or low "effective rank" can be well approximated by the RNN encoder-docoder with fewer parameters. Due to the Eckart Young-like low rank approximation, select N based on the decay rate of singular values.
can appropriately
Here, we emphasise that the temporal product is an intrinsic structure arising from the encoder-decoder architecture. Recall the dynamics of the encoder-decoder: first encodes the input sequence into coding vector, and then decodes an entire output sequence from it. In this sense, the coding vector is the only interaction between the input and output. Thus, the coding vector size N is an essential mcasure of the model capacity concerning the dependence of outputs on inputs. Here, we show that this concept can be formalised as notion of rank, which can pinpoint the precise types of input-oulpul relationships that encoder-decoder archilectures are well adapted to.
Numerical illustrations. Here, we utilise numerical examples to illustrate the above discussions. We observe how the decay rate of singular values, the rank No of the target relationships, and the model rank N affect the approximation error | Hll However, it is not always possible to construct the best approximation. Instead, we perform some training steps achieve an upper bound of the approximation error, which is consistent with our theoretical results.
In Figure 2 we train linear encoder-decoder models to learn three relationships of different ranks determined by various decay patterns of singular values, given in (a), (b) and (c). Different colours denote targets with different ranks. From Figure 2 we have the following observations consistent with previous discussions. First, observe that increasing the model rank N makes approximation errors smaller, as expected. Morcover, note that when increas- ing N, the speeds of error decrements are different. If the singular values decay fast, the approximation errors also decay fast. This implies that a target with fast decayed singular values can be approximated efficiently with fewer parameters (smaller N). In addition, for each experiment, we are able to achieve low approximation errors by choosing N & m. The errors will remain unchanged or decrease much more slowly when further increasing N. This suggests that in practice, one can choose N such that it covers the major singular values of the target in order to improve the approximation efficiency.
8

---

Published as a conference paper at ICLR 2022
1.1
Target
2.8
Ng
Ng
1.0
No m oc
0.9
2.3
Xg
Error
0.7
1.8
0.6
0.5
1.3
0.4
0.3
0.8
0.0
0.0
2
6
8
10
2
4
6
10
10
20
30
N
N
(a) on
n1
n S No
(b)
n No
(c) 0n = n
0, > No
0,
No
Figure 2: In (a), (b), (c) consider target relationships with different singular values indicated the respective caption. For (a); (b) we also consider targets with different rank, where No 6, We models with fixed width me mp 128 and coding
vector size N. Detailed settings are found in Appendix E.2
In Figure 3 we perform experiments on the forced Lorentz 96 system (Lorenz) 1996), which parameterises a high-dimennsooal and nonlinear relationship between input Torcing and model states. The parameters J. the Lorenz 96 system control the overall complexity of the target (see Appendix E.3 for details). We use the RNN encoder-decoder with tanh activations to learn this target. Although our theories are developed in the linear regime, the low rank approximation phenomenon also appears in this nonlincar sctting. The crror decrements saturate when increasing the coding vector size N beyond a threshold, suggest- ing the existence of some implicit notion of "rank" of the target nonlinear functional. This "rank" increases with the larget complexity (mainly K).
x10
x10
Targst
Taget Parameters R K-5J==
R J-0
-
10,
Error
21,
Error
K 5, 100
0
10
10
20
30
N
N
Figure 3: J, J are the parameters of the Lorenz 96 system. They describe the number of independent and coupled variables in the system, which can be viewed complexity measure. Detailed settings are found in Appendix E.3
CONCLUSION
We theoretically study the approximation properties of the RNN encoder-decoder a lin- setting. We prove universal approximation result for linear temporal relationships utilising encodor-decodor architectures, and show that they generalise R.NNs to the time- inhomogencous setting. Moreover, discover important temporal product structure that characterises the types of input-output relationships especially suited for the efficient approximation using encoder-decoders. This elucidates the key differences between these novel architectures and classical methods for temporal modelling, and forms a basic step towards understanding the intricacies of modern deep learning.

---

Published as a conference paper at ICLR 2022
Reproducibility statements. Detailed proofs for theoretical results, and complete set- tings mumerical examples are found in the appendix. The source code for numerical tests can be made available upon request.
Here is a quick reference:
Proposition
Properties of RNN encoder-decoder functionals
Appendix
Theorem
Universal approximation theorem
Appendix
B
Theorem
General approximation rates
Appendix
Theorem
Approximation rates concerning temporal product structure
Appendix
Figure
Illustration of high/low rank temporal relationships
Appendix
Figure
Numerical examples singular values
Appendix
Figure
Numerical examples on Lorenz 96 systems
Appendix
ACKNOWLEDGEMENTS
ZL is supported by Peking Universily under BICMR mathematical scholarship. HJ is sup- ported by National University Singapore under PGF scholarship. QL supported by the National Research Foundation, Singapore, under the NRF fellowship (NRF-NRFFL 1I-FF11--221 0005).
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Damitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Repre- sentations, pp. 1 15, 2015.
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long- oon-document trans- former. Xivi preprint arXiv:2004.051 2020.
G. Berkooz, P. Holmes, and J. L. Lumley. The proper orthogonal decomposition in the analysis of turbulent flows. Annual Review of Fluid Mechamics, 25(1):539 555555555 1993. doi: 10.1146 annurev fl. 25.001193..002554.... URL attps://doiis wtt.//....r//11.111///.a..a.// f1. 25. 010193111111 002543
Vladimir I. Bogachev. Measure theory, volume 1. Springer Science & Business Media, 2007.
Ching- Hua Chang and Chung- Wei Ha. On eigenvalues of differentiable positive definite kernels. Integral Equations and Operalor Theory, 33:1-7, 1999. doi: 10.1007/BF0120300
Anindya Chatterjee. An introduction to the proper orthogonal decomposition. Current Science, 78(7):808 817, 2000. ISSN 00113891. URL http:://ww.jjstt jstor org/stable/ 24103957
Chung-Cheng Chiu, Tara N. Sainath, Yonghui Wu, Rohit Prabhavalkar, Patrick Nguyen, Z. Chen, Anjuli Kannan, Ron J. Weiss, Kanishka Rao, Katya Gonina, Navdeep Jaitly, Bo Li, Jan Chorowski, and Michiel Bacchiani. State-of-the-art speech recognition with sequence-to-seqqeeee models. In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 4774 4778, 2018.
Kyunghyun Cho, Bart van Merriënboer, Damitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder decoder approaches. In Eighth Workshop on Syntar, Semantics and Structure in Statistical Translation, 103 111. Association for Computational Linguistics, 2014a. doi: 10.3115/v1W1444012 URL https:///claathoooogy org//14--012221
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Damitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. Conference on Empirical Meth- ods in Natural Language Processing, pp. 1724 1734, 2014b. doi: 10.3115/v1/d14-111
Kenji Doya. Universality of fully-connected recurrent neural networks. IEEE Transactions on Neural Networks, 1993.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 13))211-2 1936.
Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):179-2)) 211, 1990.
Ken-ichi Funahashi and Yuichi Nakamura. Approxination of dynamical systems by con- timuous time recurrent neural networks. Newral Networks, 6(6):801 806, 1993. ISSN 0893-6080.
Sepp Hochreiter and Jürgen Schmidluber. Long short-term memory. Neural computation, (18):1735-1784) 1997.
Haotian Jiang, Zhong Li, and Qianxiao Li. Approximation theory of convolutional archi- lectures for time series modelling. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4961- 4970. PMLR, 2021. URL httpt::// https://prrocedding. mmr.mmmrr....
http:///vv9/j/aangnn html
Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. In Confer- ence on Empirical Methods in Natural Language Processing, pp. 1700-1709, 2013. ISBN 9781937284978.
11

---

Published as a conference paper at ICLR 2022
Peter D. Lax. Functional Analysis. John Wiley & Sons, Inc., 2002.
Naihan Li, Shujic Liu, Yanqing Liu, Sheng Zhao, and Ming Liu. Neural speech synthesis with transformer network. In AAAI Conference on Artificial Intelligence, volume 33, pp. 6706 6713, 2019.
Zhong Li, Jiequn Han, Weinan E, and Qianxiao Li. On the curse of memory recurrent neu- ral networks: Approximation and optimization analysis. In International Conference on Learning Representations, 2021. URL htttp:://openrevieee http://www..eeeooroooo/o/////a//
Y. C. Liang, H. P. Lee, S. P. Lim, W. Z. Lin, K. H. Lee, and C. G. Wu. Proper orthogonal decomposition and its applications Part I: Theory. Journal of Sound and Vibration, 252 (3):527-544, 2002. ISSN 0022-460X. doi:
Parti
pww.://0/0////.001...... 4041. URL
G. G. Lorentz. Approzimation of Functions, AMS Chelsea Publishing Series. Holt, Rinehart and Winston, 2005. ISBN 9780821840504.
URL https::/books..ceeeeet google. com. com.s//books?
1d=BW4r0mTKSe0C
Edward N. Lorenz Predictability: A problem partly solved. dictability, volume 1, pp. 40 58, 1996.
Proc. Seminar on Pre-
Wolfgang Maass, Prashant Joshi, and Eduardo D. Sontag. Computational aspects of feed- back in neural circuits. PLOS Computational Biology, 3(1 3(1),16,,, 2007.
Charles Bradfield Morrey, Multiple Integrals in the Calculus of Variations. Springer-Verlae Verlag, 1966.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexan- der Ku, and Dustin Tran. Image transformer. In International Conference Machine Learning, pp. 4055 4064. PMLR, 2018.
Walter Rudin. Real and Compler Analysis. Higher Mathematics Series. McGraw-Hill Edu- cation, 1987. ISBN 9780070542341. URL https::/bboks...ttt/o google. com wtw..//ggg....ooo/////o/oooaaa/a FuAAAAMAAJ
Anton Maximilian Schäfer and Hans-Georg Zimmermann. Recurrent neural networks are universal approximators. International Journal of Neural Systems, 17(4):253-22) 223, 2007.
Martin H. Schultz. m.--mulivariate approximation theory. STAM Journal on Numerical Analysis, 1(2):161-183, 1969. doi: 10.1137/0706017. URL attps://ddt 1tr.iioorg1....11331 0706017
Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence to sequence learning with neural networks. In Advances in Newral Information Processing Systems, volume 4, pp. 3104- 3112, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5999-69 6009,009, 2017.
Subhashini Venugopalan, Marcus Rohrbach, Jeffrey Donahue, Raymond Mooney, Trevor Darrell, and Kate Sacnko. Sequence to sequence-video to text. In Proceedings of the IEEE International Conference on Compuler Vision, pp.
2015.
Jong Chul Ye and Woon Kyoung Sung. Understanding geometry of encoder-decoder CNNs. In International Conference on Machine Learning, pp. 12245-12254, 2019. ISBN 9781510886988.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequuence-tossqquenee functions? In Interna- tional Conference on Learning Representations, 2020. URL
net/
forum/iddByaNNoNtvv
12

---

Published as a conference paper at ICLR 2022
A PROPERTIES OF MODEL FUNCTIONALS
In this section, we prove observations of the hypothesis space reported in Proposition
Proof of Proposition 3.1 Recall that
Hi (x 0) -- Mee
(12)
Fix any 0= (W, V,U, The linearity obvious. Since both W Wm and V E Vmp have eigenvalues with negative real parts, there exist e1, c2, cie and o1o S de for any 4,8 2 0, hence
,2, c, > 0, such that ||e 110e S
let Ce S ||e|| dellllee*Mee Mee"eeeeUss
S ||c|lalle "1 || seel ||اا
S c - ||>=||>>,
(13)
where X hides universal positive constants depending on parameters 0. Therefore [z; 0) 2 e <<| = [[+((:0)1 S caal
(14)
That is, the functional (=:00) is bounded (i.e. continuous) with an exponentially-decayel norm (as function of t). Finally, by (13) and Lebesgue's dominated convergence theorem, the functional (+(:;0) also regular. The proof completed.
B UNIVERSAL APPROXIMATION
In this section, we provide the proof of Theorem 4.1 i.e. the universal approxination property of RNN encoder-decoders. As is stated in the main text, the key step is it the classical representation theorem, which helps to reduce the approximation problem of functionals to functions.
B.1 PRELIMINARIES
First, we list the background definitions and notations used in the following theorems. Let (X, A) be a measure space (with A as the o-algebra of subsets of X).
The space X is called locally compuct if for any I E X, has compact neighbour- hood.
X is Hausdorff space if all distinct points in X are pair-wisely separable by neigh- bourhoods. That is, for any x, E X, there exists a neighbourhood A, of x and a neighbourhood Ay of y, such that n Ø.
The measure is called finile measure, if it satisfies v(X) co. The measure v is called a o-finile measure, if can be covered with at most countably many measurable sets with finite measure. That is, there are measurable sets [ C A with v(A)) < oo for all n N4, such that U An = X. Obviously, a finite measure is also o-finite.
Let X = (-o,, 0]. For a measure on the measure space ((-00, 0J, i absolutely continuous with respect to the Lebesgue measure v, if for every measurable set A, v(A) = 0 implies ((A) = 0, which is written as μ < v.
Denote by (X) the linear space of continuous functions defined on X vanishing infinity. We have the following classical representation theorem.
representation theorem). Let X be a locally com- pact Hausdorff space. For any continuous lânear functional tú on Co(X), there is unique, rogular, countably additive and signed measure i on X, such that
Theorem B.1 Maw-MMarrko--attee
$( v(n= = f(z)dp(z), Vf Co()),
(15)
13

---

Published as a conference paper at ICLR 2022
with || = (x). Here, |pl(X) denotes the total variation of (the signed measure) μ. which defined as lul == supp Ei= lu(A,),, where P Ui=1 A, portition over X with A, E A for all i = 1,2, k
Proof. Well-known, see e.g.
Bogachev
2007 (CH 7.10.4).
Remark B.1. It is straightforward to verify that [xl(X) = sup (e)((p(A) + ln(A))). |v(A)))) Fur- thermore, if p. has a density dp/dv with respect to a countably additive, nonnegative measure v, then have [p](X) = [idp/dv/lzzu d//l
To handle signed measures, the following Jordan docomposition theorem is necessary.
[Bogachev 2007
Theorem B.2. Lel p. be signed measure on the measure space (X, Then, there are two mulually singular (non-negative) mensures pt and μr on (X,A), such that μr = fxt 1t Moreover, such pair (n*,²²) is unique.
Based on this, have the following proposition to characterise absolutely continuous signed measures.
Proposition B.1. If and v are signed measures, then we have < v + ut < v and J K..
We also need the following Radon-Nikodym theorem (Bogachev 2007
Thcorem B.3. Let (X,A.v) be o-finite measure space, and let be o-finite signed measure, such that & V. Then there erists a unique measurable function f, such that ((A)= SA I'd for every measurable set A.
B.2 PROOFS
Before we prove the universal approximation theorem (Theorem 4.1 we need some lemmas. Lemma B.1. Let {H, 2 0} be a family of linear, continuous and regular functionals defined on X. Then there exists integrable function p: [0, oc) Rd i.e.
d
ll [P]la=((0.0)))) = Σ
I I < 00,
(16)
such that
He(x)) = - ( x IIIp(I, 8)ds, Vo E
(17)
In particular, have [ -000 |H, ||000==(00.002))
Proof. Obviously, (-o0,0 a locally compact Hausdorff space. For any 2 0, since H, is linear continuous, according to the Kiesz-Markov-Kakulaaa representation theorem (Theorem B.1b, there exists a unique, regular, countably additive and signed measure Pes such that
H((x) l x._ dT]d)((), Vo E X,
(18)
with Σd [pe, ((-o,(()) |[t|].- We show that for any 2 0, = 1,2,. .d, Mr is absolutely continuous with respect to (the Lebesgue measure), i.e. Me,i < v. According to Theorem B.2 and Proposition B.1 one can assume Pe, to be non-negative without loss of generality. Take measurable set A C (-o0,0) 0] with v(A)
0, the aim is to show (A)(A) = 0. Let A' (-oc, A. Since both A and A' are measurable, there exist K, C A. K' C A' with K,, K2 closed, such that (A.(A') K,) < 1/n, mas(A' K)) < 1/n
14

---

Published as a conference paper at ICLR 2022
and v(A') K2)) I 1/n for any of imput signals {x(*) J==1
N4. Fix any i E (1,,,...,df) ,d,, construct the sequence
s 5 0, j + i,
0,
8 E Kn j = i,
j= 1= d.
(19)
1, 8 SE Kn, j= i,
which can then be continuously extended to (-oc, 0] by defining =!! d(
d(e,K.)
[0, 1]. g
We deduce that lim ". for vaaee s S In fact, let = {s 00
0: lim 2
0): we have K2 C S since for any Kn =!7 Hence, (-x0, \ S AU (A' K,), which gives v((-00,0 0 (5) S v(A)+ K,, I 1/n 0 as > oc. Due to the regularity
of He, we get lim Hz(x())) = By 18 and 19). we have
= Σ 10
Fn. (8) = L Fos (s)
Hz(x("))
j=1
= =sh Kn +
+ + JAYKs 2 dues(s)) = (e,)(Kn) + I1, + I2.n: JAYKn
(20)
where (e,(Kn) Mt,(A) (A \ Kn) E (m,((A) 1/n, (A,(),),,,, and [1 + |/2ml I JAYK. + [.r,,, ldp = Me,((A Kn) + (e,((A' (2) S 2/n, which gives lim (x())))) = (A). Therefore, (A) =0.
Notice that |me=((-00,,0) 0J) S | 0)) S ||ell < 0o for a.e. 0 (since ||| 1 He 00), we get that ((-00, (0, A,,,)) is a finite measure space, and hence o-finite. o-finite measure space. According to the Radon-Nikodym theorem (Theorem B.3) there exists unique measurable function Pt.z (-o0, 0] + R, such that (A) SA (t,i(5) (s) for every measurable set A. Hence, we have
Obviously, ((-oc, 0) A.v)) v)
Hi(x) [ 0
III S II.p(t,))ds Vo X,
(21)
with p((,8) pc(-s)- In addition, by Remark B.1 have |1,,1(((00,, 0J)
So (s),ds) which gives
H = / ||H
Σ / (p,,:(((-0c,)))) =
Σ ll (e = [1.00))00.0))))) (22)
The proof completed.
Based on this representation theorem, the problem of functional approximation is reduced as function approximation. That is,
|| Helldt / sup ||
H A
[H((z) - : 0)
xI,(p(t,)) -(l,, s))s
sup |1
sup
|k0=ol - p(l, dlsdd
||
d
[ (t)(t,)) - Pa(t, s))dsdt
$
(23)
1=1
Here, d(s, B) == inf([s al : a E B} the distance between point and set B.
15

---

Published as a conference paper at ICLR 2022
i..
Il p-- )1.,)(00000))) Σ pl )1..2:
(24)
Lemma B.2. Let p(t, 10,00)2- R with || [|]1))((0,0))))) < oc.
Then for any 0, there
crists a polynomial p(u, v) Lj=11 caude, such that
Jo (o(t,s) p(e "dddd <e.
(25)
Proof. Fix any c 0. Consider the following transformation
R(u, v) 1 p In u, In v), u, E (0, 1], uv = 0.
(26)
10,
This transformation preserves the norm with || = (
First, according the density of continuous functions L space (Rudin 1987 Theorem 3.14), there exists R E C([0,1]3) such that ||- Rl. < e/2. Next, by the density of polynomials in the space of continuous functions (Lorentz)
2005 Theorem 6), there exists
polynomial q(u,v) Lj. c such that || g 1 ([0.1]3) e/2. Finally, let p(u, uvg(u, v), we have
(0((,8) - ple e " = 0 [-] L. R(u, 0) un
- dudc
||R (1111(00.133
I || R R|( + +II 9 -11x0(00013))
< 6/2 + c/2 =6,
(27)
which completes the proof.
Now we are ready to prove the universal approximation theorem.
Proof of Theorem 4.1 According the representation thcorem (Lemma B.1 we have
H₂(x)= = / xI.p(t, s)ds, Vo X,
(28)
where (10,02)(00,000))) = ||| < x. Therefore, by Lemina B.2 there exists pe(u, v)
(1) urr i= 1,2.... d, where m is the maximal degrec of {p. such that EjAles Cjt
Σ 10- lni(t, s) pi(e ee" <
(29)
Let
c u 1m V W - diag (1,2, 1.2,....7 .......77 ..)..
m),
W = diag (W, W, ..... .W) E dmd dm = diag(u, u, u...., ..) E Rdmxd
(30)
M PQ (M, Ma) mmddm [Miljt (i)
Cjk
we get
)(,,s)
c. CeVe Ve
Ve M,,,...... Ma) diagle We e W. ... . Wo) diag(u, u... .u)
= (c -cTTo VeM C ( di We u, wen, Wou) TeVt
(c Won," T Wo u, ... .c Wo.)
(31)
16

---

Published as a conference paper at ICLR 2022
with
(,(1, - c e = ,67,, i= 1,
(32)
Therefore, by 24 and [29
we have
H H
lpp Pellx:(0.2003)
Σ
d
| 30 pi(t,s)- - pe(e-t,e=0)) <c,
pi(tss)
(33)
1=1
which completes the proof.
C GENERAL APPROXIMATION RATES
In this section, the proof of Theorem 4.2 is given. Again, by 224. the aim is to investigate the function approximation
pll- Since one can handle each spatial dimension
separately (similarly with (30) and (31] , firstly derive the estimates by assuming d 1, and then extend the obtained results to the case of multi- multi-dimensional inputs (for general d E N)).
Conditions on representation. To characterise the accuracy of using the model eee "u (with M == PQ) to approximate the target p(l, the first stuff is to trans- late the conditions on the output (of piece-wise constant signals) to the representation. Recall that (t, = Hz(1(-oo__s), 8 2 O, we get p(t, assumptions on yf in Theorem 4.2 equivalent to the following smoothness and exponential decay conditions on That is, there exist E N4, 3 >> 0 such that
de H2/HH111--0) (H((((- Hence, the
E C² +xx)) ((++s)
(34)
gh+t
a p(t, 8) o(1) as (I(1,))] + co,
(35)
Note that the last decay condition implics
gk+l
sup g-(k+) ((++s)
((t,g)((t,))) ST. k, k+lsa
(36)
4,200
for some > 0.
C.1 BASICS
Let Ωe Rd be bounded set. Define the spaces (I) {f C()): D'f C(i) for all | S a), a a, Ca) = [f e (0) 1 f(x) fz)()) < K| - v for some K 0, for all x, Ω and |i| = a).
(37)
(38)
and the "norm"
D'f(()) D'f(y)) | - vI
fla, sup sup = zyynn
Wf E CO),
(39)
with the shorthand || lla lo,0,
Thcorem C.1 (Multivariate Jackson's 's theorem (Schultz 1969
Thcorem 4.10). Let Ω Rd be regular, ? bounded and open set, and f E C.))(S) for some E N, μ [0, 1). Then for any n N,, we have
C(a, p))
inf |f plla <
n |
(40)
PEP4
2It is proved that every bounded, open and convex set is regular. See Morrey 1966 3.4.1).
(Lemma
17

---

Published as a conference paper at ICLR 2022
where Pd denotes the set of all polynomials with the degree of no more than in each variable, (t), > 0 is universal constant only depending on a, μ and Q.
A commonly used case is when μ 0. That is, for f (EC(()), get
110,001 S 2 max
(D)() < oc.
(41)
=
For any z, 2, E 22 let p(x) = p(x) + f(0o) p(zo), and ē(x) == f(x) - p(x)) Then p P and
If(z) - p(x) = |ē( + (((x) - أ(x))
I sup (ē(x) ē(y) = (ēb,,,0 = IIf -Pla. e E f2.
(42)
z.en
This gives the following convenient corollary.
Corollary C.I. Let Ω E TRd be regular, bounded and open sel, and I E (a for some E N. Then for any n E N4, there erists p E pPd such that
Ca max || |12> |l - pl S
(43)
n =d
where Pd denotes the set of all polynomials with the degree of no more than n in each variable, C. > is universal conslant only depending on a and Ω
C.2 PROOPS
Now we are ready to present the proof.
Proof of Theorem 4.2 Step 1: domain transform. Consider the transform from the infinite
domain [0, 00)2 to the compact one [0, 1]2:
R(u,v) = { pl cc co luu, -co v)), u E (0, 1], 0,
(44)
uv 0,
where co : (a) 0 is a fixed constant. A straightforward computation by induction shows that, for any k E N, k +1 S a, and any u,u (0,
gb+l Ou R(u, v)
(-1)ttl b
gits ((,)))()
aia p(-co ln, -colan (45)
++tlf11 i=
where C(k, i), ((,j) are some integer constants, and (t, s) = loo ln is one-
to-one mapping between (0, 1]2 and [0, 00)2. By 36 we get
gktl
0iti
Out R(u,o)
S
Σ Σ
at pl ( In -co
x+
1
II
im =
gk+l
R(e 7 -0,6 2
(-1))
(+11)
C ((),)))((
T1 ((1,))
Jiti
Or
giti
C(k, (14 g-(t) )(+t))
ar p(l,
1=0 j=
(46)
1= 0
18

---

Published as a conference paper at ICLR 2022
where C(a)
0 is universal constant only depending
According to the decay
condition 35
we get
80
P - co In u, -co In
[++ll (+0 Oits Ot do
lim (0,0)
lim
p(1, 8)
1
(t,s) -00
alto) 0i+s
lim (+0c,-)))
Öt P(t, s)
0,
(47)
and similarly for uo, v0 E (0, 1],
gits Be p( C-o In -c0 ln
(++1) (+1)) ji+s
lim (1,0) (ag.0)
lim
0s p(1,8)
1
(- +20)
a(++) Oits
St d=a)
lim
e
as p(t, 8)
[((+a)]] +
0,
(48)
85+s 3r
p( ( c0 In co Inv)
lim (0.v)
0.
(49)
This gives
gk+l Ou Ov!
R(u, v) =0; (u, [0, [0] (0) [0,1].
(50)
and
gh+l R(u, u) I c(aa)
Mg ==
max kJINN, &+iSa (1
max
Ou
(51)
by
46 and 50
Hence, R(u, v) E Ca ([0, with bounded derivatives.
Step 2: polynomial approrimation. According to Corollary C.1 and 51 obtain that there exists Rn P?, such that
Ca n" KIINN k+1==
gktl Ou R(u, 8)
R - R R S
max
(00.1)))))
Cla)r, na
VNEN+.
(52)
where C(a) > 0 is universal constant only related to a. Furthermore, let (u, Rn(u, R,,u, 0) (0, (0, 0), get Rn E P with (,, 0) (0, v) 0 for
any u, U, E [0, By 50 we have R(u, u) = for any (u, E [0, (0) (0) 0, 1). then
R R ((.1))2) S R R 1~ ((011p) + RR (nl1z=((0.11)))
| 2 (10 + R (u. 0) - R(u, 0)
+ RR, (0, R(0 v000,))l==0000000 (0.1)) + [, (0. 0) R(0, 00 (001)))
$ || R,.llx
(53)
ie. we can further require the approximator satisfying the zero half-boundary condition (i.e. vanishing on (u,v) E [0, 1] x {0) U [0) 1]) without effecting the approximation accuracy. Let m = (mi,,,,, mp), we get
R R 1=),1)))) s C(a)y
< O(ah (1 m
(54)
ma
mB
where
m m
:: Rm E P2.
R(u, =
Pogul v.
(55)
j=1
19

---

Published as a conference paper at ICLR 2022
Let
1m/
u = 1ms
M Fiyl E _mxm
(56)
diag((2 (2,,, ....... + 1)/c0,
W 3, 1)/00:
(57)
then by 24 and 54], we have
H H || s 110 أ0 (10,200)
(58)
||((1,)) c.e.tMee M (1000000)) [
p((t.s) (((t,s--e - t0 Riee : t0
[1000000)
c || - ('(1111))
(59)
c(a)7 82m
C(a) g2
(1
1
1 o R R (0.1p))
+
(60)
mm
mß
That is, one can achieve an approximation accuracy scaling like (1/m)o with m² parameters. The proof is completed.
Remark C.1. The extension to multi-diimensional inputs (general d E N+) is found in the lost paragraph of Appendir D.2.
Remark C.2. Recall M PQ m with P RR Q E Nxme, we only need to investigate the case of N
mp} = m, since rank(M) m.
D APPROXIMATION RATES VIA TEMPORAL PRODUCT STRUCTURE
In this section, the proof of Theorem is provided.
D.1 PROPER ORTHOGONAL DECOMPOSITION
Proper orthogonal decomposition (POD; (Liang et al. 2002 Berkooz et al. 1993 Chat
terjec 2000b) is a method for model reduction, which commonly applied to numerical PDEs and fluids mechanics. It can be viewed as an extension of singular value decomposi- tion (SVD) and principal component analysis (PCA) infinite-dimensionaal spaces.
Fix any R 1 ((0 11.)
Define the POD operator
c: @(v) ~ f ( R(u, v)d(u)do R(u, v)du, Φ(v) E I I,2 1].
(61)
Proposition D.1. The operator K. is linear, bounded, compact, self adjoiit and non- negative.
Proof. (i) The linearity is obvious.
(ii) Let
R: 6(v) /' u(u,d)o(o)de, d(v) L 1].
(62)
then
(KC))()= - R(u, (R))( Φ(v) E _= 1].
(63)
By the Cauchy-Schwarde inequality, we get
|| & ||F]_1=9(001))]||))]=)0000
(64)
'ere, the notation as 44 since the function defined there also bounded.
20

---

Published as a conference paper at ICLR 2022
which gives
[[ S [|8]]1200013)))))0le & (o.))lll.
(65)
Note that R(u, u) E ([0, 113) c ([0, 113), hence both and R are bounded operator from [² 1] to itself.
(iii) It is well-known that the Hilbert-Schmidt integral operator
(Cv)(u)= = 1." R(u, v)b(u)du, vb()) E L 1]
(66)
compact operator from L2 itself. Therefore
K CRØ, @ L2 1].
(67)
which gives K. CR. Since R. bounded and C is compact, we get also compact. (iv) By Fubini's thcorem, it is straightforward to verify that
(Ko, 10)11 S.' J. A(u, w) (L R(u, v))(v)do) du (w))d
[ J L'' R(u, ())(v) dodduww
('" S' R(u,v) (L H(u, ((,, (W)(()))))))) (a du ølu)de
(0, (G)K))))
0 E 17
(68)
(v) By Fubini's theorem, is straightforward to verify that
S/¹ S. (Ro)(1) w)du bw)dw l'/ S' (Ro)(u) w))(w)dudd (RØ)(W) (f, R(u, w)((w)dw)) du
(Ko, ()
(Ro) 20, áe 1].
(69)
The proof completed.
Combining (i)- and applying Silbert-Schmidee expansion thcorem, obtain that [² 1] has an orthonormal basis (onIneN U(Vee such that
Kdn Andn; An of O for n N, and Kate 0 for & E, where M is a finite or countable set. I is not finite, we have lim An 0;
For any v E L0, 1], we have
(w + (w, (eh neN
(70)
EE3
where the second summation has at most countable non-zero terms, and
Krb
Enni
AniV, @n L2001
(71)
aEN
Here, all the scries converge under the norm || |11300011- Without loss of generality, N {1, 21 ... ,oo for No E N., or No to (i.e. N = N4). By (69, get
0 < (Kon, on) = An on 2 = An. Vn E NV
(72)
21

---

Published as a conference paper at ICLR 2022
Le. all the cigenvalues of IC are non-negative, and An # 0 for E N implies An > 0, vn ... In addition, lim Xn = 0 implies that one can index all the eigenvalues in 2 An 2 ... 0.
non-increasing sequence: X 2 X2
Then, we can present the POD estimate.
Theorem D.1. For any R E ([0, 1}3), we have
N L.' R(u,w) E(R(u, v), dn (n(()) (0000))10000100)(
No Σ n=N+1
du
Xns
NA
E.
(73)
nm1
1210.1]
Proof. Combining
69
and 72
gives
An (Kon, 0n) 0n) = I (R) Vn E.
(74)
Similarly,
L (R)) ((Ci))duuuKK(b,eeelee bel - (n =0, E
(75)
NEN
which gives
(Rvb)(()= = L/ R(u, ()),()) 0, a.e. u [0,
(76)
Notice that (v) == R(u,v) C=(0, 1] c 13|0,11 1] for any [0. By gel
70 and 76
|| R. [2111
(Bas Qn) 1n) + Σ neN
Σ
Bux ())) ((
EE
Σ BEN
(Rus 2m) 1310.100 + Σ
(Rus VE) 1g)
EEE
L=(0.11
Σ (Bus 2n) ) (3 + Σ
(Bes Vie VE) (.
nEN
$E5
Σ (Ron)(())
a.e. u [0.
(77)
Hence for any N E N, we have
N
2
N Σ
Ru
Σ
Ras Φn) Ln)
R 1R
(Ra on 2n)
(78)
1.|0.11
n=1
N
Σ (Ron) (1) -
Σ (2
nEN
n=1
No Σ (1))
(79)
n=N+1
where the summation is zero by convention if the subscript is larger than the superscript. This by 74h implics
N [((u,)- (R(u, v), (). (.l0,,,),,
du
An-
(80)
LP
Here, the equality holds as a consequence Beppo Levi's monotone convergence lemma and Lebesgue's i dominated convergence theorem, and has ΣnEN Xn +oc. In fact, for
22

---

Published as a conference paper at ICLR 2022
No to, let S Σx= k== Aes we get Sn increasing (since X 2 0 for all & M). By 74
and 78 we have
S Σ % (Rés) (u)du = //" Σ Bun o& )z) 1o 2 L. [R [Rullli = || ((0).))))
(81)
which gives that Sn converges as n 00. The proof is completed.
cc. Remark D.1. Let Pn(u)) == (R(u, v), On (n())) then we have the POD estimate R(u, v) = En (n()))(()), where the error is characterised by the tail of eigenvalues of the POD operator.
Recall the POD operator defined in 661 We similarly define
C: (()) - I'' L.' R(u, v))(u)do Me, v)du, Φ(v) E 1,300.1), 1],
(82)
where R is defined as 55 i.e. the approximator constructed in the general approximation theorem before. Obviously, as polynomial, R ( 1J²). Hence, by Proposition D.1 K. is also linear, bounded, compact, self-adjoint and non-negative. In addition, according to Theorem D.I. we have the following POD estimate
L.' M((,,) v) (f(uu, v), on (v)) [2(0.1) da(w)
N
No
du =
Xn
(83)
1.210.1]
n=N+1
where {Am 2 are eigenvalues of R satisfying λ₁ 2 do 2 .... 2 An 2 ... 2 0, and (on J No C
L 1] are the corresponding orthonormal eigenfunctions, i.e. Røn = An Anon. An > 0 for n E .No
Lemma D.1. K is a fonile-rank operator. That is, No S m min(me, mD} <0.
Proof. Let (n(u)= = (R(u, v), ēn(()) Lo We first show that both (u( and (v( are polynomials. In fact, since A(u,v) v) Σ im
m
Ej Fiju' o we have
gt Ouk A(,,))
u
(i k)!
i= j=1
m m
i!
P (kk,,))
k= 1,2,,....
(84)
k))
1
with the convention that the summation is zero the subscript is larger than the superscript, Le. Ci(k, m) = 0 for any k > m. Let (m) = max R 100 (0. 1]0, max C₁ (k, m))
then we have
gh Ruu o0) (m)m))) 1 1] c 10, k=
(85)
bu
According to Lebesgue's dominated convergence theorem, we get by induction that
du (n(()) = du S( R(u, u))n - S/' gh Similarly, we get
d² d²
Ouk R(u, ())n( k 0, 1....
(86)
gh Dok Blu,v)
m
m
j!
u
(j- k)!
m7
m7
j!
Fig
A C2(,,
k= 1,2, ....,
(87)
[j - k)!
1=1 j=k
23

---

Published as a conference paper at ICLR 2022
and C2(k, m) 0 for any k > m. Let C2(m) xax ((o,)))) max C2(k,
then for = 0,1,- we have
R(u,)) /." A(u, (() S C2(m) =0 Ock
0h
(m) Cm c L 1].
(88)
According to Lebesgue's dominated convergence theorem, we get by induction that
dt dok ),(0) dz))) = An (' Ie 1
Ouk R(u,v) v) / R(u,, ())
k = 0, 00,1....
(89)
That is, Pn, on E C0 1] for any n = 1,2,... No. Since R(u, 0) = R(O,0) 0 for de
u [0. 1], we get Pn (0) = Furthermore, we have du Pn(u)) dut (n)
d
for m, hence pn; on Pm. Since 1 [2 1] are orthonormal, we must have No m <0. The proof completed.
D.2 APPROXIMATION RATES
Perturbation of eigenvalues. First, we need to bound the gap between the eigenvalues
(Am Ne and ) (corresponding to the function R defined in 44)). The following theorem is necessary.
Theorem D.2 (Courant Fischer Weyl min-max principle; Lax 2002) (Chapter 28, The- orem 4)). Let B be compact, self-adjoint operator Hillert space H. whose positive eigenvalues are listed in a decreasing order μ1 2 122 2 ... pk 2 > 0. Then
min S SES x|=||==
(Bx, a)H Mh:
(90)
where S₁ C H is any k-dimensional linear subspace.
Based on it, we have the following lemma to characterise the perturbation of singular values. Lemma D.2. For any R1, R2 - ([0, 1]2), we have the estimate
A
Ri
R2
RR R2lle3(0.1)))
(91)
Proof. According to Theorem
D.2 and by
69 have
X max Ss
min
(RRo, )) L=(o,1]
max
min Sa des,, 11
|
(92)
Note that Rr. RR, RR, Rs and by 64 we have
V A
max
min Sy dESt. 10
|RR capo1
< max Sz deS., 10
min
(II(RR, RR, 231001 + |R +11
< max
min Sy dESt 2po
Rnll + 1
< max
min
|R
[R R2 Rellc2(0.113)
Sy dESt. =
Ra
R1 Rellx2((0.133)
(93)
'In fact, for any p E Pm with p(0) 0, we have p E span(u, v..... " Through a standard Sohmidd-othogoonllzaatioo,, we can get (v) Pa, k = 1,2.-... m, such that (e,, e,) = ky and p span(e: (v), (x)) (m)()). That is, if (p, 2) p(0) 0, ?(0) 0, then their coordinates under the basis {er 1m orthogonal. Hence, the No orthogonal m--dimensional coordinates here leads at m non-zeros.
for some p, q E Pm with
24

---

Published as a conference paper at ICLR 2022
and similarly,
V A/
max
min Sy deSt, 2p11
[R c2.1011
max
min
(I(RR,, Ra, RR, + RR olle)(..1)
Ss dESt, 21.11
S max
min Sy dESt p=
(11RR,- R. + RR. 1
max
min Ss dES., P
[RRR 1 + 1 Ri R(ll22(10117)
& + 1| - Relle>(1o1)))
(94)
which completes the proof.
Proofs. Now we are ready to derive the final estimate.
Proof of Theorem
By Lemma
D.2 and
54
get
C(a)7
Vx+
AM
R R 2(0.11))))))) S IR (2110~(00117) I
(95)
m
Combining
54
83
and
95
gives that
N
1
ptt,s)
30 pn -
n=1
((((000))
N
R(u,v)
Bn (1)
==
< [((u,,) R(u, -(u,,))l2((0019))))
R(u,v) - Σ (1))
n=
T.(((0113))
< [(u,v) R(,, ( + i((u,o) Σ
(1()nn)
n=l
1.2((0.13)
No
C(a)r m
C(a)) ma
An 5
Iin Ao
Σ An
n=N+1
n=N+1
n=N-1
C(a)r m
No An
Σ
Fm
Am
v Am + Vnn
n=
N==+1
C(a)y ma
No
2
+
An
Σ
Am
V An
+ V2,
An
V
An
Am
n=N+1
++
n==+1
(1+ No N
1 m
sC(a)r
+
An
Ax
(96)
ma/2
-==++1
n=N+1
where S hides universal positive constants.
For the corrosponding parameters, recall that Pn, En E Pm with Fn. = 2o.(0) = 0, we can write
m
(u) = Σ
Pun u
(x(2) =
Σ
Q Unjit
(97)
j=1
25

---

Published as a conference paper at ICLR 2022
for any 1,2, ,No Let
c == m
" = mm
(98)
V diag(2 3, ,m + 1)/co,
W 3,.
m + ,
1)/co:
(99)
M PQ with P [Pin] _axN
Q [Qnyl E RNxx
(100)
then we have
m
e W uu ==== == c.p.
Qe
Σ
L+1
Ps
nze
50 (n 20).e ia (
(101)
n=1
Plugging this into 96 gives
H AI s lle )
(102)
s) TC''Me" (I (((o)))))))
c(a)) No - -N)
(1+
No An
No
x B2
+
+
m
m2
n=N+1
n=N+1
(103)
and the number of trainable parameters is 2.m. Together with Lemma D.1 the proof is completed.
Extension to multi-dimennionall inputs.
The above results can be naturally extended to the general case where a d-dimensional input is given (Vd E N.). In fact, let
[t e, W' ""/l=lllll "ull= Se, i = 1,2, ,d,
(104)
for some 0 < 6 < 1, then we take
M (M,, M2, Ma) E pm
(105)
W diag(W, w,,, W.... W) ddnxdm
U= =ddagg( ,,..,,,,, u) E Rddadd (106)
and have
Te Wsu =c ee M2, .Ma diagle"s Ws e Ws ...., e.o) diag(u, u, u.... .u)
= (c Tet T Te M2,... "e. Vt Ma) diagle" W. u, e eW W
= (c u,,"" cT ee M'M2eW., ",,....... TT Mae W))). u))
(107)
the form PQ(=M is required, it is sufficient to take Mj = P.Qs, i == 1,2, .d, and
P= (P, P2, ... Pa) E RxddN Q = diagi(aa Q1, Q2. .Q) E dddm
(108)
Therefore, we obtain
Elee((,s) ( (1ll
(1 S de,
(109)
with the number of parameters increased by d-times compared to the corresponding one- dimensional sctting.
D.3 CASE ANALYSIS
Bounds under different cases. Now we make the comparison between 102 and 58
Recall that {An) Noo is positive decreased sequence (with lim X, 0 and D An
20
[| by 81 if No +00), and No S m, we have the following cases.
26

---

Published as a conference paper at ICLR 2022
if No o(m), set N = NN in (102) and get the same bound as number of parameters is only ((Nom) o(m²);
58
but the
if No O(),, then 1002 implies that
|| - cte v M W*
((0,00))))
c(ah)
I+ [+vm (1+Vm-N) N)
+
Σ
An +
An
8
m
ma/2
n=
N==++ +1
C(ahy
m
An +
An
(110)
g2
m71
a
x=
n=
ma/a
We are supposed to require that
max
Any
An
m
ma/2
N+1
n=N+1
1
Σ
V
1
(111)
20 2211-
ma-1"
n== N+1
R=N+1
We give the following typical examples to illustrate sufficient conditions to guarantce
111
If An O(= with r> > 2a + 2 (ar E N+), since
1
Σ
x dd
1- Nr-1 m
(112)
N=
we get by
111 that
m
Σ
An
+ N ~
بي
(113)
Nr-1
m
R=M+1
R=N+1
A
S
Σ n
m
(114)
N
ma-
R=N+1
Assume that N ~ m with 8 E (0, then by
113 and 114
we require
8 2 max ( 20-1 i.e.
2xx
a ---++ -
2a 8
r 2 max
1, 2
+ 1.
(115)
8
Meanwhile, the POD-estimate [100 achieves an accuracy scaling like (1/m)a-3
a-
with (m!++) parameters, while under the same capacity, the accuracy of m(1+5)
a(1+8) 1/a, 115 becomes r a-1 That is to say, r" = 2a can be viewed as an upper bound of the critical point where the two estimates are compa- rable. When > r", the POD-estimate outperforms the non-POD-et,imate, In fact. when r > r", we take N = m P > m F-F (hence satisfying (113) and 114 which gives an ((1/m)a-H) approximation error with O( estimate, while 2 =) trainable parameters are needed to achiove the same 1 we get that the POD-estimate outperforms the non-POD-estimate When r" + too, the num- ber of trainable parameters for the POD-estimate is O(m), much better than the non-POD-estimate
58
scales like (1/m) 2 The former beats the latter if a
1/a (a > 2). When g = max 2a--1 2(a + 1)) = 2a²-1 a-1
d
and this effect gets more notable with increasing.
20-1
parameters for the POD-
accuracy using the non-PODDestimate. Since 2a-1
r-1
27

---

Published as a conference paper at ICLR 2022
Remark D.2. Let
K(v, = ! R(u, u)l(,, w, E [0,
(116)
we get
(KT)(w)) = L:¹ K(v, ((v,w))bo)dde & E 1,2 1).
(117)
Recall that R E CO (00, 113) 1 (10, 112), we get K I ((0, [[, 113),
and hence K can be also viewed as Hilbert-See -chhentt integral operator with the kernel K, where K is obviously symmetric as K(u, K(w, v), and positive definile since I (Ko,
& E 12(0,11 1] () L2 = -oo So ((u, ())())
by (69). Since the derivatives of R (up to a-order) are continuous on [0, 1]2 (hence bounded and integrable), we get K E Ca [0, 1]2) (a- (a-differentiable for both arguments). According to Chang & Ha (999) (Theorem 1), we have
SN VNEN, = An = On (at1)),)) + co. (118)
N
That is to say, this general setting (only assume smoothness of the kernel) can not guarantee the sufficient condition provided here (An = =(n=)) with r اا²ي i.e. the point that the POD-estimate outperforms the non-POD- estimate requires a faster decay of the eigenvalues.
If An (e))
with w > 0, we get by
111 that
wn e eN+(N+
m 20-1
Σ
N
In
1,
e-
2a
a=1+1
N+1
(119)
8
n (N++1)
2
ma-1
Σ
VAn
+
N
In
1 m-
1 - e
n=N+1
n=N+1
(120)
That is to say, for any a E N+, w > 0, we have N ~ (2a - 1) In m. This implies an (((1/m)==) approximation error with O(m In m) parameters for the POD-estimate, while ((m2-t) parameters needed to achieve the same accuracy using the non-POD-es
If No < +oo (i.e. IC is a finite rank operator by one can just take N = No and get by 1100p ((1 ((11m))=3 2) approximation error. For m E N sufficiently large such that m ~ No for some x >> 1, the number of trainable parameters for the POD-estimate is O(Nm) = O(Nx+1), while O (No (2)))))) paramoters are needed to achieve the same accuracy using the non-POD-estimatee Obviously, +
if a 2 2, we get x(2 - 1) iv
Eigenvalue approximation. One can apply 91 in Lemma D.2 to estimate the eigen- values Na where R = R and R2 is taken as some approximator of R, say R. Let ā = R2 we recall 91 as
VtL
S R R I=(().13))
(121)
We provide a naive method here. That is, can take Å as a piece-wise constant ap- proximation of R. Fix any n E N4. Let To = {0}, I₁ = (ان [] for = 1,2, ... n,, then (I, xI, is the uniform partition over [0, 1). Let R((u, v) = Eiz=o R(g 1))l,,, Iz, (u.
28

---

Published as a conference paper at ICLR 2022
Then for any @ L2 1], if w E Ik. k 0,1, n, have
(K)o)(w)= {/¹ / R(u, (v))d R(u,w))
1'
L. 1z, (u, v)o(o)du 17p x (u, w)du
R
R
n
j
i
k
Sa.l. Jo, 1z,x,, (u, () 1I,II, (u, w)du
R
R
n
j=0
i
k
R
R
Izz ((u)do.
(122)
which is constant only related to k. That is, KnO is piece-wise constant func- tion, i.e. KgΦ E span (1I, o== range(K(p) span {1z, Je=o Obviously, {1I, / an orthogonal set, which implies that the operator Kg is of finite rank at most + 1. Let. Raj == [ 2=,,, i,j 1.2, n + 1, {oR)R= be the singular value of A [Ryy] E R(a+1)x(x+1)) and V [(x++))(*++)) with columns as the corresponding right singular vectors. Set [21, ,,,,1))) = [1 ". 1r,,] V, then by (122), we gel for 1 1,2. +1,
1 n
(Kgee)(w) =
R
R
n2
11
1=0 1=0
n+1 n+1n+) m+1
Ray R
k+
Vjs
A RVV.
(123)
k+1
which gives
Kger- = Σ
R RV
1z, = of Σ
Vi+1.1 = ofer,
(124)
k=0 k+1
k=
Le. the set [ collects the all the eigenvalues of Kg which can be obtained by the SVD of ft.
For the error estimate, it is straightforward to have
R(u,v) v) f((uvv) 1.((0)))3)
R(u, v) - R ( [ -
1 n1) ) dudv
7 max (u,,)_(0,11'
|/ u1 will |1
i
2 dudu
n
2 cc
n dudv 4C²
(125)
n²
i=1
hence by 121
| o < 20(h2 for any E N4.
E NUMERICAL SETTINGS
According to Lemma B.1 the target input-output temporal relationship has Riesz repre- sentation form. Under the discrete-time regime, we are supposed to set
T
H((x) =
Σ p(t, S)X.
(126)
==1
where T E N4 is the path length.
29

---

Published as a conference paper at ICLR 2022
E.1 SETTINGS OF FIGURE
For the imput, we generate 6 sequences using Gaussian i.i.d. random variables with the path length = 30. Hence, the output (target) is H²(x:) = Ex p(t, 8 8)
The high rank target has the representation
[oos((), 1= 8, 0,
hish (t,
(127)
t + 5,
while the low rank larget has the representation
99
jon (1,
= Σ
(os() cos(nTs)).
(128)
n
E.2 SETTINGS OF FIGURE
Consider the target with the following representation
p(t,s) 8) = e - = R(e _0,e
(129)
where
R(u, v) = Σ nn an (u)@n(()) n=1
(130)
with both {pk) and } as orthonormal bases. In this way, we construct target with singular values {ox). Under the discrete-time setting, we are supposed to use the following linear, width-m RNN encoder-decoder
A.(x) = Σ c C -V 8),
(131)
where P E R Q E Nxm with mD mp.
Recall that the approximation error is derived as
H मll || R S || R(|1=((0.11))
(132)
where o) = E (:( E Ph with En, Hn E P In the numerical experiments, first construct R(u, v), and then fit it with the polynomial A(u, v) using the method of least squares. The norm || (())1=) is used to evaluate the approximation error.
In the particular example reported in Figure 2 we set m 128, pp (2sin(nuu)) n < No.
and on (v) = /2sin(nTo). The singular values are taken as: (a) on = n
10,
No
n n n No. (c) on = 2 with No 2, 4, 6, 8. As an infinite sum, R is (b) on 0, n No
constructed under a finite truncation with the first 50 terms.
E.3 SETTINGS OF FIGURE
We perform experiments nonlinear targets show that the insight of low rank approxi- mation also holds the nonlinear case.
Nonlincar target.
We consider the forced Lorenz 96 system Lorenz 1996. which is important example of reduced order modelling for convection dynamics, with applications in weather forecasting.
Mathenatically, the system has K output variables {ye} and JK hidden variables { with k = 1,2...., K and j 1,2,...,. The parameters K.J control the number of
30

---

Published as a conference paper at ICLR 2022
variables in the system, and can be viewed complexity measure. The imput {øE} is external temporal forcing. The system satisfies the following dynamics
dys yk- 1 Ml++1) - yk + 3k J ==1
J
jjkk
(133)
dt
dzj,k dt -2j41,6(2jt22, 2z-1 2j. + yk.
(134)
with cyclic indices yk+K yke 2j,+ 2j,k and 2j+J,k kj,k- Here, we take { as randomly generaled input sequences with the path length 64. We have tested for several
cases with different parameters: i) J with K 1,5, 10, 20; ii) K = 5 with J 5, 15, 25, 100.
Note that the forced Lorenz 96 system parameterizes a highly nonlinear functional.
Nonlinear model. ear activations, i.e.
We learn the above system using RNN encoder-decoders with nonlin-
he o + UET, bb),
aQQ,, + +b), 90 = (Pv bb),
9t +(W
(135)
Wos + bo,
where a is the element-wise tanh activation. Let = 128 be the hidden dimension, N 1,2,..., 32 be the size of the coding vector v, we have 2.s ot. bo E RRKK hg bg, bp, by I WE. WD Rmxm b, E RRN, Wo E Rm=x, Q E R=xN, P IR Nxm_ Note that we construct the model with a fixed hidden dimension m but different N, thus only sizes of Q, P. b b2 are varying, while sizes of other parameters remain unchanged.
Training and initialisation. We denote the model with the coding vector size as EncDee(M), We utilise the Adam optimiser and train from EncDec(1) to EncDee(32) For (ncDee()), we use a normal random initialisation, and train for 3000 epoches until a stable error. For (nc with N 1, use the parameters trained from EncDec the initialisation. For the parameters Q, P. b2, we pad them to match the size of EncDee(N) with normal distributions as initialisations.
It is shown that the low rank approximation phenomena discovered in the linear setting also appears in this nonlinear case.
31


Reviews:
[{"review_id": "sBP2Mn9WJLH", "reviewer": "Reviewer_e39c", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nPros: \n* 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.\n* Mathematically prove that the encoder-decoder architectures are a better fit for modeling time-inhomogenous sequence modeling problems.\n\nCons:\n* 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. \n* 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_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. \n\nThe 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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qqGsjoLKLg", "reviewer": "Reviewer_WtE5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nMy 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_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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "d6aG3k-rO1Q", "reviewer": "Reviewer_Qn54", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'd like to thanks the authors for their submission. I enjoyed reading it.\n\nOverall, 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.\n\nThere are, however, a few concerns and questions:\n1.  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?\n2.  In the related work section, it would be interesting to see what your type of analysis enables us in compare to other works.\n3.  Eq. 1 and 2: any intuition as to why input space should vanish at infinity and output space should be bounded?\n4.  Before eq. 4: \"resulting from convolve\" $\\rightarrow$ \"resulting from convolving\"?\n5.  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.\n6.  Is there any ramification for \"linear and continuous-time idealization\" before eq 6? A more intuitive explanation of this assumption is also appreciated.\n7.  Eq. 7 and 8: the fact that one needs negative real parts in eigenvalues to ensure stability over long horizons is not explained.\n8.  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.\n9.  Second paragraph in section 4.2: \"where the dimension of the $N$...\" $\\rightarrow$ \"where $N$...\"\n10.  Eq 11: $C^{(\\alpha+1)}$ with superscript is not defined.\n11.  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.\n12.  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_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.\n\nTheir analysis summarized as following:\n1.  Universal approximation: any linear, continuous, and regular temporal relation can be approximated by RNN encoder-decoder up to arbitrary accuracy.\n2.  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.\n3.  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.\n4.  Experiments: they show that the theoretical analysis holds in their experiments.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)