Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors extend results regarding the application of controlled differential equations and rough paths theory, from 'feed-forward' architectures to recurrent neural networks.
The resulting analysis allows them to define an RKHS over such models, measure their capacity and bound their generalization.
main_review: I found this submission extremely interesting though quite technically challenging. 

Theorems 2 & 3 are of great relevance to the entire community, and I would like to offer some minor suggestions:
1. I cannot find a clear definition of $\sigma^{(k)}$ in the main text. Please move the definition from the appendix into the main text.
2. 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.

I have a technical questions that I would like the authors to address.
For 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. 
Does this imply that $K_f$ implicitly has such a dependence on $T$?
limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Minor comments: 
(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.
(2) Could one extend Theorem 2 to cover multi-class classification tasks?
limitations_and_societal_impact: No, in particular no mention of the potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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?

While 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.

A few additional remarks and questions:

* 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?
* 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.
* l 68: Subspace is usually used in the sense of `linear subspace' in this context. `Subset' might be a better term.
* 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.
* l 103: $M$ should be defined in the next line, where it is used (or the phrasing should be changed).
* l 144: missing subscript $[0,1]$.
* 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.
* Appendix A.2: The Picard-Lindeloeff theorem should be considered standard. It does not need to be reproved here.
* l 666: In the last equation, the equality should be $= \frac{L+1}{L-1} \leq \frac{2}{1-L}$, I believe
* l 756: Infinity norm (rather than infinite norm)
limitations_and_societal_impact: the authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

1. 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)
2. 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$)
3. 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?

---

After rebuttal:

I thank the authors for responding to my questions. I think this is an interesting paper and recommend acceptance.
limitations_and_societal_impact: Not applicable
review_title: null

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)