Framing RNN as a kernel method: A neural ODE approach
Authors: Adeline Fermanian
Pierre Marion
Jean-Philippe Vert
Gérard Biau
Venue: NeurIPS 2021 Oral (2021)
Keywords: recurrent neural networks
neural ODE
kernel method
theory of deep learning
generalization bounds

Abstract: Building on the interpretation of a recurrent neural network (RNN) as a continuous-time neural differential equation, we show, under appropriate conditions, that the solution of a RNN can be viewed as a linear function of a specific feature set of the input sequence, known as the signature. This connection allows us to frame a RNN as a kernel method in a suitable reproducing kernel Hilbert space. As a consequence, we obtain theoretical guarantees on generalization and stability for a large class of recurrent networks. Our results are illustrated on simulated datasets.

Framing RNN as a kernel method: A neural ODE approach
Adeline Fermanian
Pierre Marion
Jean-Philippe Vert?
Gérard Biau'
Sorbonne Université, CNRS,
Laboratoire de Probabilités, Statistique et Modélisation, LPSM, F-75005 Paris, France
Radeline.h cedelinne.frraniinn fermanian, eierre.marion gerard. bian/@aorbonn--uiverssttt Google Research, Brain team,
Paris, France
jpvert@google.com com
Abstract
Building the interpretation of a recurrent neural network (RNN) continuous- time neural differential equation, we show, under appropriate conditions, that the solution of RNN be viewed the input sequence, known as the signature. This connection allows us to frame RNN kernel method in suitable reproducing kernel Hilbert space. As consequence, we obtain theoretical guarantees on generalization and stability for a large class of recurrent networks. Our results are illustrated simulated datasets.
linear function of specific feature set of
Introduction
Recurrent neural networks (RNN) among the most successful methods for modeling sequential data. They have achieved state-of- of-the-art results in difficult problems such as natural language processing (e.g., Mikolov al., 2010; Collobert al., 2011) speech recognition (e.g., Hinton et al., 2012; Graves et al., 2013). This class of neural networks has a natural interpretation in terms of (discretization of) ordinary differential equations (ODE), which casts them in the field of neural ODE (Chen et al., 2018). This observation has led to the development of continuous-depth models for handling preguuaaly-sampple time-series data, including the ODE-RNN model (Rubanova et al., 2019), GRU-ODE-Baye
(De Brouwer et al., 2019), or neural CDE models (Kidger et al., 2020; Morrill et al., 2020a). In addition, the tine-contiuuuus interpretation of RNN allows to leverage the rich theory of differential equations to develop new recurrent architectures (Chang et al., 2019; Herrera al., 2020: Erichson al., 2021), which are better at learning long-term dependencies.
On the other hand, the development of kernel methods for deep learning offers theoretical insights on the functions learned by the networks (Cho and Saul, 2009; Belkin et al., 2018; Jacot al., 201 8). Here, the general principle consists in defining a reproducing kernel Hilbert space (RKHS) is, a function class x- which is rich enough to describe the architectures of networks. good example is the construction of Bietti and Mairal (2017, 2019), who exhibit an RKHS for convolutional neural networks. This kernel perspective has several advantages. First, by separating the representation of the data from the learning process, it allows to study invariances of the representations learned by the network. Next, by reducing the learning problem to linear one in H. generalization bounds can be more easily obtained. Finally, the Hilbert structure of H provides a natural metric on neural networks, which can be used for example for regularization (Bietti et al., 2019).
"Equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Contributions. By taking advantage of the neural ODE paradigm for RNN, we show that RNN are, in the continuous-time limit, linear predictors over specific space associated with the signature of the input sequence (Levin et al., 2013). The signature transform, first defined by Chen (1958) and central in rough path theory (Lyons et al., 2007; Friz and Victoir, 2010), summarizes sequential inputs by graded feature set of their iterated integrals. Its natural environment is tensor space that can be endowed with an RKHS structure (Király and Oberhauser, 2019). We exhibit general conditions under which classical recurrent architectures such as feedforward RNN, Gated Recurrent Units (GRU, Cho et al., 2014), or Long Short-Term Memory networks (LSTM, Hochreiter and Schmidhuber, 1997), can be framed bounds for RNN as well as stability guarantees via regularization. The theory is illustrated with some experimental results.
kernel method in this RKHS. This enables to provide generalization
Related works. The neural ODE paradigm was first formulated by Chen et al. (2018) for residual neural networks. It was then extended to RNN in several articles, with focus on handling irregularly sampled data (Rubanova et al., 2019; Kidger et al., 2020) and learning long-term dependencies (Chang et al., 2019). The signature transform has recently received the attention of the machine learning community (Levin et al., 2013; Kidger et al., 2019; Liao et al., 2019; Toth and Oberhauser, 2020; Fermanian, 2021) and, combined with deep neural networks, has achieved state-of-the-ard performance for several applications (Yang et al., 2016, 2017; Perez. Arribas, 2018; Wang et al., 2019; Morrill et al., 2020b). Király and Oberhauser (2019) use the signature transform to define kernels for sequential data and develop fast computational methods. The connection between continuous- RNN and signatures has been pointed out by Lim (2021) for a specific model of stochastic RNN. Deriving generalization bounds for RNN is an active research area (Zhang et al., 2018; Akpinar et al., 2019; Tu et al., 2019). By leveraging the theory of differential equations, our approach encompasses a large class of RNN models, ranging from feedforward RNN to LSTM. This is in contrast with most existing generalization bounds, which are architecture dependden.... Close to our point of view the work of Bietti and Mairal (2017) for convolutional neural networks.
Mathematical context. We place ourselves in a supervised learning setting. The input data is a sample of n. i.i.d. vector-valued sequences (x(1)....,xx }. where x(() = {x] ,T E (Rd)T. T 2 1. The outputs of the learning problem can be either labels (classification setting) or sequences (sequence-t---eqqeeee setting). Even if we only observe discrete sequences, each x(9) is mathematically considered as a regular discretization of continuous-time process X ([0, 1], Rd). where (Vo 1), Rd) is the space of continuous functions from [0, 1] to Rd of finite total variation. Informally, the total variation of process corresponds its length. Formally, for any [s, t] C [o, 1), the total variation of a process X E (V 1), Red) on [s, t] is defined by
(6)
|| 121vss..
sup (o......))D.....
Σ
IX - -l.
j=1
where Da,t denotes the set of all finite partitions of [s. f] and ||. the Euclidean norm. We therefore have that z) (6) x-( 1 S < T, where x == (t). We make two assumptions on the 1/7- processes (t) First, they all begin at zero, and second, their lengths are bounded by L E (0, 1). These assumptions are not too restrictive, since they amount to data translation and normalization, common in practice. Accordingly, we denote by 2 the subset of BV 1), Rd) defined by
T= fx E BV
(10, 11, R") X. = 0 and || $ L
(() are i.i.d. according some X E 2. The norm on all spaces RT, m 2 1, is always the Euclidean one. Observe that assuming that X E 2 implies that, for any 1 [0, 1]. XX,] = [X, Xoll S [|X]|rv:00.1] S L.
and assume therefore that (1),
Recurrent neural networks. Classical RNN are defined by a sequence of hidden states fi...., ho E 12, where, for x (21....,TT) IT) generic data sample,
hu 0 and hy+1 = fh,, 2z+1) for 0 <jST-1 1
At each time step S S T, the output of the network is z, = (hy), where yb is a linear function. In the present article, we rather consider the following residual version, which is a natural adaptation

---

R be the of classical RNN in the neural ODE framework (see, e.g., Yue et al.. 2018):
hg and hy+1 = hi + T [(hg) for SSiST-
(1)
The simplest choice for the function f the feedforward model, say SRNN, defined by
JRNN [RN .)) o oUh Vx
where a is an activation function, U Rexe and V E Rexd are weight matrices, and E R the bias. The function SRNN. equipped with smooth activation (such as the logistic or hyperbolic tangent functions), will our leading example throughout the paper. However, the GRU and LSTM models can also be rewritten under the form (1), as shown in Appendix A.1. Thus, model (1) is flexible enough to encompass most recurrent networks used in practice.
Overview. Section 2 is devoted to framing RNN as linear functions in a suitable RKHS. We start by embedding iteration (1) into continuous-time model, which takes the form of a controlled differential equation (CDE). This allows, after introducing the signature transform, to define the appropriate RKHS, and, in turn, to show that model (1) boils down, in the continuous caatiuuuus-tmee limit, to a linear problem the signature. This framework is used in Section 3 to derive generalization bounds and stability guarantees. We provide some experiments Section before discussing our results in Section 5. All proofs are postponed the supplementary material.
2 Framing RNN kernel method
Roadmap. First, we quantify the difference between the discrete recurrent network (1) and its continuous-time counterpart (Proposition 1). Then, we rewrite the corresponding ODE as CDE (Proposition 2). Under appropriate conditions, Proposition 4 shows that the solution of this equation a linear function of the signature of the driving process. Importantly, these assumptions are valid for feedforward RNN, stated by Proposition 5. We conclude in Theorem 1.
2.1 From discrete to continuous time
Recall that ho...., hr denote the hidden states of the RNN (I), and let И [0, 1] solution of the ODE
dH, [H,, dt),,, Ho ho-
(3)
By bounding the difference between H./r and hy, the following proposition shows how to pass from discrete to continuous time, provided / satisfies the following assumption:
(A1) The function f is Lipschitz continuous in and æ, with Lipschitz constants K₁, and Kg. We let K2 max(Kn, Kz).
Proposition 1. Assume that (A1) is verified. Then there exists unique solution H to (3) and, for any 0 S
|/,/ h5ll S Ci T sup z)(eek) and M
where 01 Ks (L+ for any 1 E E 10, |H+||| S M.
[f Moreover, ||||S
sup
[
Then, following Kidger et al. (2020), we show that the ODE (3) can be rewritten under the form of a CDE. At the cost of increasing the dimension of the hidden state from to + d, this allows to reframe model (3) as a linear model in dXX, in the sense that X has been moved 'outside' of f.
Proposition 2. Assume that (Ai) is verified. Let H [0, 1] - Te. be the solution of (3), and let X [0, 1] -> dRd+1 be the tine-augmented process X, (X 1-1t) Then there exists tensor field F R + gexd
axdde = e d, = d+ 1, such that if H [0, 1] + R is the solution of the CDE
d.H. = (H.)dXX, Ho (Ho X then its first coordinates equal to H.
(4)
3

---

Equation (4) can be better understood by the following equivalent integral equation:
H, Ho= + /. F(H.)dX..
where the integral should be understood as Riemann-Stieljes integral (Friz and Victoir, 2010, Sec- tion 1.2). Thus, the output of the RNN can be approximated by the solution of the CDE (4), and, according to Proposition 1, the approximation error is ((/T).
Example 1, Consider JRNN as in (2). Iʃa Lipschitz. confinuous with constant Ka, then, for any h1,h2 h2 E R,, I1, E ERA,
[| - (R2 F1 )11 |la(Uh + Vx1 + b) - oUU2 + Vxy + b)ll
S KoKKl |I lop |// h2ll,
where || - lop denotes the operator norm-see Appendix A.3. Similarly, (I1 - f(h +2)ه < KoI|V V llopl x2l|. Thus, assumption (A1) is satisfied. The tensor field FRNN of Proposition corresponding to this network is defined for any h RR by
0axx
o (W)+b))
0dx1 0 b.),
FRNN (h)
where = (U V) E
(5)
Laxd
2.2 The signature
An essential ingredient towards our construction the signature of continuous- process, which we briefly present here. We refer to Chevyrev and Kormilitzin (2016) for gentle introduction and to Lyons al. (2007); Levin et al. (2013) for details.
Tensor Hilbert spaces. We denote by (R the kth tensor power of R with itself, which is Hilbert space of dimension d The key space to define the signature and, in turn, our RKHS, consists in infinite square- summaale sequences of tensors of increasing order:
g = a= (ag. (ao...., akk .k....) |as E (R
fa-=
Σ R=0
lax loele < co).
(6)
Endowed with the scalar product (a, 6) = Ex= (ak, bR) (ROjON, I is Hilbert space, as shown in Appendix A.4.
Definition 1. Let X E BV
00, 10, Rd). For any E [0, 1}, the signature of X on [0, t) is defined by -.. where, for each k 2 1,
(X) (1,
X 1.4
yk
rk [0,1
kd
dX., 2 dX E (R2)
O541 Cu
Although this definition is technical, the signature should simply be thought of as a feature map that embeds a bounded variation process into an infnite-dimensionall tensor space. The signature has several good properties that make it relevant tool for machine learning (e.g., Levin et al., 2013; Chevyrev and Kormilitzin, 2016 6; Fermanian, 2021). In particular, under certain assumptions, S(X) characterizes X up to translations and reparameteriizations, and has good approximation properties. We also highlight that fast libraries exist for computing the signature (Reizenstein and Graham, 2020; Kidger and Lyons, 2021).
The expert reader is warned that this definition differs from the usual one by the normalization of X 0..
by kl, which is more adapted to our context. In the sequel. for any index (i....., .44 C {l..... d)h s (X) denotes the term associated with the coordinates (i1,..., ix) of x When the signature is taken on the whole interval [o, 1], we simply write S(X), S(1 (X), and X
[..]]
Example 2. Let be the d-dimensional linear path defined by X, = (a1 + byt,..., Od + bat)T, a,, b, E R. Then ((1....))((x) = b,, ...b, and x 188
The next proposition, which ensures that (X) E T, is an important step. Proposition 3. Let X E E and X, = (X,, 1_( as in Proposition 2. Then, for any t E [0. 1]. (1))o.(())1 2(1 -1

---

The signature kernel. By taking advantage of the structure of Hilbert space of I, it is natural to introduce the following kernel:
K + (X (S(X),
which is well defined according to Proposition 3. We refer to Király and Oberhauser (2019) for general presentation of kernel methods with signatures and to Cass al. (2020) for kernel trick. The RKHS associated with K is the space of functions
H = {Ea 2 + E. (X) (a, ((x)) 9].
with scalar product (5arE)). Es) = (),,3) (see, e.g., Schölkopf and Smola, 2002).
2.3 From the CDE to the signature kernel
An important property of signatures is that the solution of the CDE (4) can be written, under certain assumptions, linear function of the signature of the driving process X. This operation can be thought of as Taylor expansion for CDE. More precisely, let us rewrite (4) as
dH; = F(H,)XX Σ F'(H,)dx;
(8)
where X, (X, X R Rexd and F : Re are the columns of F-to avoid heavy notation, we momentarily write d, H. and X instead of ē, d. H. and X. Throughout, the bold notation is used to distinguish tensor fields and vector fields. We recall that vector field F: + Re or a tensor field F: Re + Rexd are said to be smooth if each of their coordinates is 6000
Definition 2. Let F,G: ::GKK R - TR! be smooth vector fields and denote by J(.) the Jacobian matrix. Their differential product is the smooth vector field F G: Re Rs defined, for any RR, by
8G Dh (b) JGG)())F)))
(F * G)(b
Σ
In differential geometry, F G is simply denoted by FG. Since the operation is not associative, we take the convention that it evaluated from right left, i.e., F1 F2 F8 F (F² * F3).
Taylor expansion. Let H be the solution of (8), where F is assumed to be smooth. We now show that H can be written linear function of the signature X, which is the crucial step embed the RNN in the RKHS H. The step-N Taylor expansion of H (Friz and Victoir, 2008) is defined by
H Ho + Σ k!
Σ 1dh
(61..... sk) (X)F's .... Fix (Ho()
[..1]
Throughout, we let
(F)
sup [M Sh
| x........ FiR (h)ll-
Example 3. Let F FRNN defined by (5) with an identity activation. Then, for any h E R.
1 < < d + 1, (h) = Whh + bi, where by is the (i+ d'th vector of the canonical basis of R.. and
T- W.
2
W = Ozxes
W4+1
and ba+1
1-
Oxxx
0.
The vector fields FiSN are then affine, ((F = W,, and the iterated star products have a simple expression: for any 1 1 .1....,44 S d, FRNN * (f) = WW2 ...
b;,). WW, (W,, ..
The next proposition shows that the step-N Taylor expansion H is good approximation of H. Proposition 4. Assume that the tensor field F is smooth. Then, for any E [0. 1), 2
N++1
H4 11 < (N 11! (F).
(9)
5

---

Thus, provided that A (F) is not too large, the right-hand side of (9) converges to zero, hence
He = Ho
Σ
s [0.4]
(X) *... F (Ho).
(10)
We conclude from the above representation that the solution H of (8) is in fact linear function of the signature of X. A natural concern is to know whether the upper bound Proposition vanishes with N for standard architectures. This property is encapsulated in the following more general assumption:
2 < DO.
(A2) The tensor field F is smooth and
AR
(F)
Ad!
Clearly, if (Ag) is verified, then the right-hand side of (9) converges to O. The next proposition states formally the conditions under which (Ag) is verified for FRNN. It is further illustrated in Figure which shows that the convergence is fast with two common activation functions. We let ||o = V2 and (|o(()]]] M.lII (U
Vvllins &.Mll=ls
where
((k) is the derivative of order k of
Proposition 5. Let F RNN be defined by (5). Isa is the identity function, then (Ag) is satisfied. In the general case, (A2) holds if smooth and there exists such that, for any k 2
-
(|005 110 Sa and
[|W]|
(11)
8a2d
where || ||| the Frobenius norm. Moreover, for any N
Sa² [| F N-1
(F I V2a
N!.
1 1-L L
The proof of Proposition 5, based on the manipulation of higher-order derivatives of tensor fields, is highly non-trivial. We highlight that the conditions on are mild and verified for common smooth activations. For example, they are verified for the logistic function (with a 2) and for the hyperbolic tangent function (with a = 4) see Appendix A.5. The second inequality of (11) puts constraint on the norm of the weights, and can be regarded as radius of convergence for the Taylor expansion.
Putting everything together. We now have all the elements at hand to embed the RNN into the RKHS H To fix the idea, we assume in this paragraph that we are in a +1 classification setting. In other words, given an input sequence x, we are interested in the final output 27 = ((rr) R. where hr is the solution of (I). The predicted class is 2 1(2 >> 0) 1.
By Propositions and 2, 27 is approximated by the first e coordinates of the solution of the CDE (4), which outputs Retuue process H. According to Proposition 4, H is linear function of the signature of the augmeneddd process X. Thus, on top of H, it remains to successively apply the projection Proj on the first coordinates followed by the linear function & to obtain an element of the RKHS H. This mechanism is summarized in the following theorem.
Theorem Assume that (A1) and (Az) are verified. Then there exists a function &ar H such that
C
12T Ex(X)) S || T
(12)
where (x) = (a, S(X)) of and X, = (XT, TT We have a = (ax)) where each ag E (RR))k is defined by
N1
sh o Proj (Fr * *..* Fix (Ho))-
Moreover, ||a|13 S |1 Σ AT AA())) 2
We conclude that in the continuous-ting time limit, the output of the network can be interpreted as scalar product between the signature of the augmentg)) process X and an element of .. This interpretation is important for at least two reasons: (i) it facilitates the analysis of generalization of RNN by leveraging the theory of kernel methods, and (Mi) provides new insights on regularization strategies to make RNN more robust. These points will be explored in the next section. Finally, we stress that the approach works for large class RNN, such as GRU and LSTM. The derivation of conditions (A₂) and (A2) beyond the feedforward RNN is left for future work.

---

3 Generalization and regularization
3.1 Generalization bounds
Learning procedure. A first consequence of framing a RNN as a kernel method is that it gives natural generalization bounds under mild assumptions. In the learning setup, are given an i..d. sample Dn, of random pairs of observations (x(), (,yy))))))))))))))
(RT)) x L. where x(i)
(xf") "ci"....,at ( We distinguish the binary classification problem, where y {-1,1}, from the sequential prediction problem, where y (R²) and andy() (v) ..... VT The RNN is assumed to be parameterized by 9 E @ C R", where θ is a compact set. To clarify the notation, we use a subscript whenever quantity depends on 0 (e.g., for etc.). In line with Section 2, it is assumed that the tensor field Fg associated with fo satisfies (A1) and (A2), keeping in mind that Proposition 5 guarantees that these requirements are fulfilled by feedforward recurrent network with smooth activation function.
Let go (R4)²* - y/ denote the output of the recurrent network. The parameter 0 is fitted by empirical risk minimization using a loss function f: y x + R+ The theoretical and empirical risks respectively defined, for any 0 E O by
n
( ([((y,go(x)) and (0) =
(y
. go (x))).
where the expectation E is evaluated with respect the distribution of the generic random pair (x, y)- We let 0n E argmin (.) and aim at upper bounding P(yge, (x) - 0j2,) in the classification regime (Theorem 2) and (p,))) in the sequential regime (Theorem 3). To reach this goal, our strategy is to approximate the RNN by its continuous version and then use the RKHS machinery of Section 2.
Binary classification. In this context, the network outputs real number go (x) = (bhr) R and the predicted class is 2 1 (go(x) > 0) 1. The loss & (-1, } x IR + IR+ is assumed to satisfy the assumptions of Bartlett and Mendelson (2002, Theorem 7), that is, for any y E [-1,1], = R, E(y, 2) (1z2), where o(u) 2 1(u < 0), and & is Lipschitz-continuuv
with constant Kg. For example, the logistic loss satisfies such assumptions. We let Eag H be the function of Theorem 1 that approximates the RNN with parameter 0. Thus, 2T R Eao = ((x))(X)) )) 5, up to a (1/T))
term.
Theorem 2. Assume that for all O E O, (A1) and (A2) are verified. Assume, in addition, that there exists a constant B O such that for any 0 + 11Eap sse I B. Then with probability least 1 5,
P(yga, (x) 5 0 < (O.) + C2 + (1- -.V.
8BKe
2BKr
log(1/)
(13)
T
1 T.
2n.
where = Kysups (Iwillop K (L + lI II ((oelloe((o))
Close to our result are the bounds obtained by Zhang et al. (2018), Tu et al. (2019), and Chen et al. (2020). The main difference is that the term in 1/T does not usually appear, since comes from the Fuler discretization error, whereas the speed in 1/vn is the same. For instance, Chen et al. (2020) show that, under some assumptions, the excess risk is of order / + eh1 " Ken-1/2, We refer to Section for further discussion on the dependency of the different bounds to the parameter T. The home message is that the detour by continuous time neural ODE provides a theoretical framework adapted to RNN, at the modest price of an additional ((1rr) term. Moreover, we note that the bound (13) is 'simple' and holds under mild conditions for a large class of RNN. More precisely, for any recurrent network of the form (1), provided ( (A,) and (A2) are satisfied, then (13) is valid with constants 02 and B depending on the architecture. Such constants example of a feedforward RNN. We stress that Theorem 2 can be extended without significant effort the multi-class classification task, with an appropriate choice of loss function.
given below in the
Example 4. Take a feedforward RNN with logistic activation, and θ = {(W, b, x)) [[[[[] S Kw < (1 - /2d,, [|b]| S KG, || S Kg). Then, Proposition 5 states that (Az) is satisfied and, with Theorem 1, ensures that
v2 L) = B, Kj. = max([[U]]pp: |Vllo)), and ll = sup/| happlSaulll Laullee S 1- L -32dKw 8eB
7

---

Sequence-to-sequeen learning. We conclude by showing how to extend both the RKHS embed- ding of Theorem and the generalization bound of Theorem the setting of eqquence-t--sqquenne learning. In this case, the output of the network is a sequence
go (x) = (21 (21,...,27) 2r) E (Rº)".
An immediate extension of Theorem ensures that there exist p elements 01,0, ................................ ap.0 E T such that, for any S j S T.
| - ((01,0,
100.00. S10.//] (X)) '1 S I
C1
(14)
The properties of the signature guarantee that S/0.:/r) (X) S( where Xby is the process equal to X on [0, s/T] and then constant on //r, 1 see Appendix A.6. With this trick, we have, for any 1 < p. (ave Sto.5/7 (X)) 5 (ar,s, (() 5. that are back in Ht. Observe that the only difference with (12) is that we consider vector-valued sequential outputs, which requires to introduce the process [)) but that the rationale is exactly the same.
We let & (RP)T x (129T + R be the L2 distance, that is, for any y (y1...., .yt.....yy.,.... y' (V....., 3/), y = + Σ Ilu; - 1/
2 It is assumed that y takes its values in compact subset of TR9, i.e., there exists K2 0 such that ||ui|| S Ky-
Theorem 3. Assume that for all 0 6, (A1) and (A2) are verified. Assume, in addition, that there exists a constant B > 0 such that for any 1 S S p. θ, 11Sac ee S B. Then with probability at least 1 1-6, 8,
4pca B(1 - L)-
2cs log(
((,)) S Rn (0n)
+
(15)
T
Vn
where sup(c1,o +
+ 2/TB(11 -) + 2K = B(1 -))- + Ky and
Cs 3::=4pB(111)) 4p +
3.2 Regularization and stability
In addition to providing sound theoretical framework, framing deep learning in an RKHS provides a natural norm, which can be used for regularization, as shown for example the context of convo- lutional neural networks by Bietti et al. (2019). This regularization ensures stability of predictions, which crucial particular in a small sample regime or in the presence of adversarial examples (Gao et al., 2018; Ko et al., 2019). In our binary classification setting, for any inputs x, x' (#d)T, by the Cauchy- Schhaat- incquality, we have
T C + 115a (X) - Ear (X'II S 211p/1lop T (100)) - S(8')... e| 2 < 2/| 1lppl
If x and x' are close, so are their associated continuous processes X and X' (which can be approx- imated for example by taking piecewise linear interpolation), and so their signatures. The ]| & is therefore small (Friz and Victoir, 2010, Proposition 7.66). Therefore, when T is large, we see that the magnitude of [[E.. Ila determines how close the predictions natural training strategy to ensure stable predictions, for the types of networks covered in the
term [X) 5(X')
present article, is then to penalize the problem by minimizing the loss (0) + A||E..o 113x. From computational point of view, Taylor expansion, which we know by Proposition 4 to be reasonable. It remains that computing this norm is non-trivial task, and implementing smart surrogates is an interesting problem for the future. Note however that computing the signature of the data is not necessary for this regularization strategy.
possible to compute the norm in H. up to a truncation at N of the
4 Numerical illustrations
This section here for illustration purposes. Our objective not to achieve competitive performance, but rather to illustrate the theoretical results. We refer to Appendix D for implementation details.
8

---

Accrouiio
eqpazedd
++ Exn's
10
12:0e
1015
10-7
10
Step
Probeniza momu the weightt
(a) Error on a logarithmic scale as function of N
(b) Error as a function of the norm of the weights
Figure Approximation of the RNN ODE by the step-N Taylor expansion
Convergence of the Taylor expansion towards the solution of the ODE. We illustrate Proposition 4 on toy example. The process X is a 2-dimensional spiral, and we take feedforward RNN with hidden units. Repeating this procedure with 10a uniform random weight initializations, we observe in Figure la that the signature approximation converges exponentially fast in N. As seen in Figure lb, the rate of convergence depends in particular Proposition 5. However, condition (11) seems to be over-restrictive, since convergence happens even for weights with norm larger than the bound (we have 1/(8a² ~ 0.01 here).
the norm of the weight matrices, predicted by
Ponuliad
2.5
Advenrral
0.7
0.6
06
0.4
Figure 2: Adversarial accuracy as function of the adversarial perturbation
Adversarial robustness. We illustrate the penalization proposed in Section 3.2 on a toy task that consists in classifying the rotation direction of 2-dimensional spirals. We take a feedforward RNN with 32 hidden units and hyperbolic tangent activation. It is trained on 50 examples, with and without penalization, for 200 epochs. Once trained, the RNN is tested on adversarial examples, generated with the projected gradient descent algorithm with Frobenius norm (Madry et al., 2018), which modifies test examples to maximize the error while staying in a ball of radius e. We observe in Figure 2 that adding the penalization seems make the network more stable.
Comparison of the trained networks. The evolution of the Frobenius norm of the weights [[W]| and the RKHS norm [L Il during training is shown in Figure 3. This points out that the penalization, which forces the RNN to keep a small norm in H, leads indeed to learning different weights than the non-penalized RNN. The results also suggest that the Frobenius and RKHS norms are decoupled, since both networks have Frobenius norms of similar magnitude but very different RKHS norms. The figures show one random run, but we observe similar qualitative behavior on others.
5 Discussion and conclusion
Role of the discretization procedure. The starting point of the paper was motivated by the fact that the classical residual RNN formulation coincides with an Euler discretization of the ODE (3).

---

RNN
10-1
BNNS
Perslaed R2S
Fosaboni BAN
76
16G Epoch
150
123
200
Epech
Figure 3: Evolution of the Frobenius norm of the weights and of the RKHS norm during training
This choice of discretization translates into a 1/T term in Theorems and 3. However, we could have considered higher-order discretization schemes, such Runge-Kutta schemes, for which the discretization error decreases as 1/T", Such schemes correspond to alternative architectures, which were already proposed by Wang and Lin (1998), among others. At the limit, we could also consider directly the continuous model (3), as proposed by Chen et al. (2018). in which case the discretization error term vanishes. Of course, such an option requires to be able sample the continuous-timi data at arbitrary times.
Long-term stability. RNN are known to be poor at learning long-ten term dependencies (Bengio et al., 1993; Hochreiter and Schmidhuber, 1997). This is reflected in the literature by performance bounds increasing in T. which is not the case of our results (13) and (15), seemingly indicating that we fail to capture this phenomenon. This apparent paradox related to our assumption that the total variation of X is bounded. Indeed, if a time series is observed for long time, then its total variation may become large. this case, it is no longer valid to assume that ||||]V bounded by L. In other words, in our context, the parameter encapsulating the notion of "long-term" is not 7 but the regularity
measured by its total variation. Note that the choice of defining on [0. 1] and not another interval [0, U'] is arbitrary and does not carry any meaning the problem of learning long-term dependencies. A thorough analysis these questions is an interesting research direction for future work.
Radius of convergence. The assumptions ||X |rv < L < 1 and |[W]| < Kw < (1-1)/32d can be seen as radii of convergence of the Taylor expansion (10). They allow using the Taylor opproximation-whiie is of local nature-to prove global result, the RKHS embedding. In return, the condition on the Frobenius norm of the weights puts restrictions on the admissible parameters of the neural network. However, this bound can be improved, in particular by considering more exotic norms, which we did not explicit for clarity purposes.
Conclusion. By bringing together the theory of neural ODE, the signature transform, and kernel methods, we have shown that recurrent network can be framed in the continuous-time limit linear function in a well-chosen RKHS. In addition to giving theoretical insights on the function learned by the network and providing generalization guarantees, this framing suggests regularization strategies to obtain more robust RNN. We have only scratched the surface of the potentialities of leveraging this theory to practical applications, which a subject of its own and will be tackled in future work.
Acknowledgements
Authors thank T. Lévy for his inputs on the Picard-Lindelää theorem and N. Doumèche for fruitful discussion. A. Fermanian has been supported by grant from Région île-de-Fram France and Marion by stipend from Corps des Mines.
10

---

References
N.-J. Akpinar, B. Kratzwald, and S. Feuerriegel. Sample complexity bounds for recurrent neural networks with application combinatorial graph problems. arXiv: 2019.
P. I.. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
M. Belkin, S. Ma, and S. Mandal. To understand deep learning we need to understand kernel learning. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 541-549. PMLR, 2018.
Y. Bengio, P. Frasconi, and P. Simard. The problem of learning long-term dependencies in recurrent networks. In 1993 IEEE International Conference on Neural Networks, pages 1 1183-1188, 1993.
A. Bietti and J. Mairal. Invariance and stability of deep convolutional representations. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett, editors, Ad- vances in Neural Information Processing Systems, volume 30, pages 2210-6220. Curran Associates, Inc., 2017.
A. Bietti and Mairal. Group invariance, stability to deformations, and complexity of deep convolu- tional representations. Journal of Machine Learning Research, 20:1-49, 2019.
A. Bietti, G. Mialon, D. Chen, and J. Mairal. A kernel perspective for regularizing deep neural networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97, pages 664-674. PMLR, 2019.
Cass, T. Lyons, C. Salvi, and W. Yang. Computing the untruncated signature kernel as the solution of a Goursat problem. arXiv:2006. 14794, 2020.
B. Chang, M. Chen, E. Haber, and E. H. Chi. AntisymmetricRNNN: A dynamical system view on recurrent neural networks. In International Conference on Learning Representations, 2019.
K.-T. Chen. Integration of paths-a faithful representation of paths by non-commutative formal power series. Transactions of the American Mathematical Society, 89:395-407, 1958.
M. Chen, X. Li, and T. Zhao. On generalization bounds of a family of recurrent neural networks. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pages 1233-1243. 2020.
R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud. Neural ordinary differential equations, In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 6572-6583. Curran Associates, Inc., 2018.
I. Chevyrev and A. Kormilitzin. A primer on the signature method in machine learning. 1131v:1603.03788, 2016.
K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using RNN encoder-decodes for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pages 1724 1734. Association for Computational Linguistics, 2014.
Y. Cho and L. Saul. Kernel methods for deep learning. In Y. Bengio, D. Schuurmans, J. Laf- ferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22, pages 342-350. Curran Associates, Inc., 2009.
R. Collobert, J. Weston, L. Bottou, M. Karlen, K. Kavukcuoglu, and P. Kuksa. Natural language processing (almost) from scratch. Journal of Machine Learning Research, 12:2493-2537, 201 I.
E. De Brouwer, J. Simm, A. Arany, and Moreau. GRU-ODE-Bayer Continuous modeling of sporadically time series. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 7379-7390 Curran Associates, Inc., 2019.

---

N. B. Erichson, O. Azencot, A. Queiruga, L. Hodgkinson, and M. W. Mahoney. Lipschitz recurrent neural networks. International Conference on Learning Representations, 2021.
A. Fermanian. Embedding and learning with signatures. Computational Statistics & Data Analysis, 157:107148, 2021.
Friz and N. Victoir. Euler estimates for rough differential equations. Journal of Differential Equations, 244:388-412, 2008
K. Friz and N. B. Victoir. Multidimensional Stochastic Processes as Rough Paths: Theory and Applications, volume 120 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010.
J. Gao, J. Lanchantin, M. L. Soffa, and Y. Qi. Black-box generation adversarial text sequences to evade deep learning classifiers. In 2018 IEEE Security and Privacy Workshops, pages 50-56, 2018.
A. Graves, A.- Mohamed, and G. Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 6645- 6649, 2013.
C. Herrera, F. Krach, and Teichmann. Theoretical guarantees for learning conditional expectation using controlled ODE-RNN, arXiv:2006. 047277, 2020.
G. Hinton, L. Deng, D. Yu, G. E. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. N. Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 29:82-97, 2012.
S. Hochreiter and J. Schmidhuber, Long short-term memory. Neural Computation, 9:1735-1780, 1997.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 8580-8589. Curran Associates, Inc., 2018.
Kelly, Bettencourt, M. Johnson, and D. K. Duvenaud. Learning differential equations that are easy to solve. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4370-4380. Curran Associates, Inc., 2020.
Kidger and Lyons. Signatory: Differentiable computations of the signature and logsignature transforms, on both CPU and GPU. In International Conference on Learning Representations, 2021.
Kidger, P. Bonnier, I. Perez Arribas, C. Salvi, and T. Lyons. Deep signature transforms. In H. Wal- lach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 3099-3109. Curran Associates, Inc., 2019.
Kidger, J. Morrill, J. Foster, and T. Lyons. Neural controlled differennial equations for irregular time series. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6696-6707. Curran Associates, Inc., 2020.
D. Kingma and Ba. Adam: A Method for Stochastic Optimization. Proceedings of the 3rd International Conference on Learning Representations 2015.
2015.
F. J. Király and H. Oberhauser. Kernels for sequentially ordered data. Journal of Machine Learning Research, 20:1-45, 2019.
Klaus Greff, Aaron Klein, Martin Chovanec, Frank Hutter, and Jürgen Schmidhuber: The Sacred Infrastructure for Computational Research. Katy Huff, David Lippa, Dillon Niederhut, and M. Pacer, editors, Proceedings of the 16th Python in Science Conference, pages 49 56, 2017.
12

---

C.-Y. Ko. Z. Lyu, L. Weng, L. Daniel, N. Wong, and D. Lin. POPQORN: Quantifying robustness of recurrent neural networks. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97, pages 3468-3477. PMLR, 2019.
D. Levin, T. Lyons, and H. Ni. Learning from the past, predicting the statistics for the future, learning an evolving system. 1r09:: 0260, 2013.
Liao, T. Lyons, W. Yang. and H. Ni. Learning stochastic differential equations using RNN with log signature features. arXiv: 190.00826, 2019.
S. H. Lim. Understanding recurrent neural networks using nonequilibrium response theory. Journal of Machine Learning Research, 22:1-48, 2021.
T. Lyons. Rough paths, signatures and the modelling of functions on streams. arXiv:1405.4537, 2014.
T. J. Lyons, M. J. Caruana, and T. Lévy. Differential Equations Driven by Rough Paths, volume 1908 of Lecture Notes in Mathematics. Springer, Berlin, 2007.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
T. Mikolov, M. Karafiát, L. Burget, J. Čemockýý, and S. Khudanpur. Recurrent neural network based language model. In Proceedings of the 11th Annual Conference of the International Speech Communication Association, volume 2, pages 1045- 2010.
A. A. Minai and R. D. Williams. On the derivatives of the sigmoid. Neural Networks, 6:845-853, 1993.
Morrill, C. Salvi, Kidger. J. Foster, and T. Lyons. Neural rough differential equations for long time series. htti:20090082955 2020a.
J. H. Morrill, A. Kormilitzin, A. J. Nevado-Holgado, S. Swaminathan, S. D. Howison, and T. J. Lyons Utilization of the signature method to identify the early onset of sepsis from multivariate physiological time series in critical care monitoring. Critical Care Medicine, 48:c976-c981, 2020b.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf. E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style. High-Performn Perforrrfrr Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bou Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 8024 8035. Curran Associates, Inc., 2019.
I. Perez Arribas. Derivatives pricing using signature payoffs. arXiv: 1XX9vv8809009460 2018
Reizenstein and B. Graham, Algorithm 1004: The iisignature library: Efficient calculation of iterated-integral signatures and log signatures. ACM Transactions Mathematical Software, 46: article 8, 2020.
J. Riordan. An Introduction to Combinatorial Analysis. John Wiley & Sons, New York, 1958.
Y. Rubanova, R. T. Q. Chen, and D. K. Duvenaud. Latent ordinary differential equations for erregularly-samples time series. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 5320 5330. Curran Associates, Inc., 2019.
B. Schölkopf and A. J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, Cambridge, Massachusetts, 2002.
C. Toth and H. Oberhauser. Bayesian learning from sequential data using Gaussian processes with signature covariances. In H. Daumé III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 9548-9560, 2020.
7. Tu, F. He, and D. Tao. Understanding generalization in recurrent neural networks. International Conference Learning Representations, 2019.
13

---

P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski,
P. Peterson, W. Weekesser, J. Bright, S. van der Walt. M. Brett, Wilson, K. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, i. Polat, Y. Feng. E. W. Moore, J. VanderPlas, D. Laxalde, Perktold, R. Cimrman, I. Henriksen,
A. Quintero, Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors.
SciPy 1.0; Fundamental Algorithms for Scientific Computing Python. Nature Methods, 17:
261-272, 2020.
B. Wang, M. Liakata, H. Ni. T. Lyons, A. J. Nevado- Hovado-Holgado, and K. Saunders. A path signature approach for speech emotion recognition. Proceedings of Interspeech 2019, pages 1661-1665, 2019.
Y.J. Wang and C.-T. Lin. Runge-Kutta neural network for identification of dynamical systems in high accuracy. IEEE Transactions on Neural Networks, 9:294-307, 1998.
W. Yang, L. Jin, and M. Liu. DeepWriterID: An end-to-end online text- text-independent writer identifica- tion system. IEEE Intelligent Systems, 31 :45-53, 2016.
W. Yang. T. Lyons, H. Ni, C. Schmid, and L. Jin. Developing the path signature methodology and its application to landmark-based human action recognition. arXiv: 2017.
B. Yue, Fu, and J. Liang. Residual recurrent neural networks for learning sequential representations. Information, 9:56, 2018.
J. Zhang, Q. Lei, and I. Dhillon. Stabilizing gradients for deep neural networks via efficient SVD parameterization. In Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 5806-58 14. PMLR, 2018.
14


Reviews:
[{"review_id": "r1ofD0tFF-", "reviewer": "Reviewer_jQAU", "summary": "The authors extend results regarding the application of controlled differential equations and rough paths theory, from 'feed-forward' architectures to recurrent neural networks.\nThe resulting analysis allows them to define an RKHS over such models, measure their capacity and bound their generalization.", "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 found this submission extremely interesting though quite technically challenging. \n\nTheorems 2 & 3 are of great relevance to the entire community, and I would like to offer some minor suggestions:\n1. I cannot find a clear definition of $\\sigma^{(k)}$ in the main text. Please move the definition from the appendix into the main text.\n2. An explicit comparison with existing generalization bounds for RNNs would make the submission more accessible. Moreover, though this is not imperative, it would be interesting to see an empirical comparison of the derived bounds with those found in the cited references.\n\nI have a technical questions that I would like the authors to address.\nFor an ordinary differential equation rescaling $t \\in \\[0, T\\]$ to $\\tilde t \\in \\[0, 1\\]$ requires rescaling appropriately the right hands side of the differential equation. \nDoes this imply that $K_f$ implicitly has such a dependence on $T$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "qRY3gtEjMc", "reviewer": "Reviewer_aWgR", "summary": "This paper presents an approach to interpret RNN (in the continuous-time setting) as a kernel method. The main idea is to write the RNN ODE as a controlled differential equation, and through a signature transform of the (time-augmented) input process it is shown that the RNN output can be viewed as a linear function of the signature. Hence, RNN viewed this way is now amenable to classical analysis from Kernel methods. In particular, a generalization bound is proved in which the complexity measure is based on the defined RKHS norm of the target. Moreover, the approach inspires some regularization strategies for RNNs and the paper explores some of this via toy examples.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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 is very well written and studies an interesting topic of embedding RNN as a linear function(al) in an RKHS. I think this forms a nice connection between time series methods and functional analysis / kernel methods, and as far as I am aware this is novel. More broadly, this may be an interesting mathematical framework to study RNNs and variants. While the main generalization bound here follows from classical kernel methods analysis, I think the value of the paper lies in identification of RNN as a linear (but infinite dimensional) map, thus allowing one to bring in these tools. Thus, I tend to vote for acceptance of this paper. Below, I list some questions the authors may wish to address.\n\n1. As I understand, the $1/T$ term in various error/generalization bounds come from the time-discretization. If this is indeed the case, then I think it is of value to write this error separately (as in Prop 1) and then simply bound the rest of the errors in continuous time. In this way, it is more clear that the continous-time representation of the RNN as a linear map is exact, not approximate, as it currently reads in Theorem 1 (Eq 11)\n2. Can you discuss some computational limitations of the signature? To me, there appears to be a huge curse of dimensionality (with respect to both dimension $d$ and “time points” $k$)\n3. Here all results seems to be considered on a fixed temporal interval (with $T$ being the number of discretization points of this fixed interval). However, most RNN issues arise when time interval is expanded. Can you discuss the scaling of these results (e.g. the generalization bound in Theorem 2) respect to the time horizon under consideration?\n\n---\n\nAfter rebuttal:\n\nI thank the authors for responding to my questions. I think this is an interesting paper and recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HgzdMbrbR9u", "reviewer": "Reviewer_jy69", "summary": "The authors consider a continuous data/neural ode model for recurrent neural networks. They prove convergence of the discrete model to the continuum model as the length of input sequences increases (assuming that sequences are obtained by finer and finer discretizations of the same process). They then show that the neural ODE can be represented alternatively as a controlled ODE, and that a solution of the controlled ODE can be expressed in terms of the signature of the input process. This allows the authors to equate the RNN to a kernel method for a specific kernel. Finally, they use Rademacher complexity bounds for the RKHS to estimate the generalization properties of RNNs in terms of the length of the input sequence/fineness of discretization. They use the continuum model to design a penalty term which improves stability as seen in numerical experiments.", "questions": "", "limitations": "", "rating": 7, "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": "The work presented is undeniably technically demanding and bridges diverse fields in an interesting way. I am not an expert, but I believe the underlying mathematics to be correct. The applicability of the results, however, appears to be quite limited at this stage. The coefficient bound in equation (10) is fairly severe for high-dimensional inputs. I am not sure how many interesting functions can be represented with such small weights - could the authors comment on the requirement?\n\nWhile the article has definite merit, I believe that it presently falls short of inclusion in NeurIPS. Given the technical complexity and unsatisfying results, a more mathematically minded audience might appreciate this work more. It is undeniably an interesting direction of research, and I believe that a more mature contribution in this direction could be a valuable contribution in the future.\n\nA few additional remarks and questions:\n\n* The total variation of the process $X_t$ is bounded by $L<1$. Sequence data usually passes through several unit vectors. Could the authors comment more clearly on how the results scale with different upper bounds?\n* l 61: Functions in $BV([0,1])$ are not generally continuous. Please adapt the notation e.g.\\ $BV^c$ or similar (or relax the continuity requirement). I do believe that continuous functions form a closed subspace of $BV$, though.\n* l 68: Subspace is usually used in the sense of `linear subspace' in this context. `Subset' might be a better term.\n* l77/eq (2):  This is a very special case. If $\\sigma$ is the logistic function (as suggested below), then $h$ is automatically monotone increasing coordinatewise since $\\sigma>0$. A two-layer network needs an outer layer weight (at least for signed activation functions). This could easily be fixed by including a diagonal matrix of varying signs, for example, which does not change the norm bounds and does not require major changes.\n* l 103: $M$ should be defined in the next line, where it is used (or the phrasing should be changed).\n* l 144: missing subscript $[0,1]$.\n* eq (10): The condition $\\|W\\|_F < \\frac{Const}d$ is fairly severe when the input dimension $d$ is high, as the matrix becomes very large and the Frobenius norm sums over all coefficients. It is violated for any common initialization scheme. Could the authors discuss the bound and whether a weaker norm might suffice, or whether the tiny `radius of convergence' is in fact to be expected? The numerical results seem to suggest broader applicability.\n* Appendix A.2: The Picard-Lindeloeff theorem should be considered standard. It does not need to be reproved here.\n* l 666: In the last equation, the equality should be $= \\frac{L+1}{L-1} \\leq \\frac{2}{1-L}$, I believe\n* l 756: Infinity norm (rather than infinite norm)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "AxWphGQAn21", "reviewer": "Reviewer_8hpD", "summary": "This paper provides a rigorous framework to connect learning with RNNs and kernel methods, exploiting the idea that the output of a RNN can be viewed as a linear function of the signature of the input sequence in the continuous-time setting. Working within the framework (embedding the RNN into a RKHS), generalization bounds and stability guarantees are provided. Experiments are also provided to support the theory.", "questions": "", "limitations": "", "rating": 7, "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": "The main strength of the paper lies in the rigorous analysis of the connection between RNNs and kernel methods in the continuous-time setting, which itself constitute a valuable contribution. The paper is easy to read and the results seem to be technically correct. While improvements in some areas (particularly, the experimental parts) could be made, overall it is a good paper and I am inclined to accept.\n\nMinor comments: \n(1) It seems like the embedding of the input sequence into a continuous path for use in the framework could play quite an important role. More comments/results on the effects of the embedding procedures (in terms of the discretization error incurred when discretizing a continuous-time input process) would strengthen the paper.\n(2) Could one extend Theorem 2 to cover multi-class classification tasks?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, in particular no mention of the potential negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper establishes rigorous connection between (continuous time) RNNs and kernel methods. This paper brings a novel theoretical tool to the theoretical analysis of RNNs driven by a finite duration input. They also provide generalization properties and design a penalty term which improves stability as seen in numerical experiments. For the final version, please make sure to take into account all discussions from the rebuttal process.
Decision: Accept (Oral)