The Recurrent Neural Tangent Kernel
Authors: Sina Alemohammad
Zichao Wang
Randall Balestriero
Richard Baraniuk
Venue: ICLR 2021 Poster (2021)
Keywords: Neural Tangent Kernel
Recurrent Neural Network
Gaussian Process
Overparameterization

Abstract: The study of deep neural networks (DNNs) in the infinite-width limit, via the so-called neural tangent kernel (NTK) approach, has provided new insights into the dynamics of learning, generalization, and the impact of initialization. One key DNN architecture remains to be kernelized, namely, the recurrent neural network (RNN).  In this paper we introduce and study the Recurrent Neural Tangent Kernel (RNTK), which provides new insights into the behavior of  overparametrized RNNs. A key property of the RNTK should greatly benefit practitioners is its ability to compare inputs of different length. To this end, we characterize how the RNTK weights different time steps to form its output under different initialization parameters and nonlinearity choices. A synthetic and 56 real-world data experiments demonstrate that the RNTK offers significant performance gains over other kernels, including standard NTKs, across a wide array of data sets. 

Published as a conference paper at ICLR 2021
THE RECURRENT NEURAL TANGENT KERNEL
Sina Alemohammad, Zichao Wang, Randall Balestriero, Richard G. Baraniuk Department of Electrical and Computer Engineering Rice University
[sa86, zw16 6, rb42, richb baaabbrrriic @rice.
ABSTRACT
The study of deep neural networks (DNNs) in the widhh limit, via the so-called neural tangent kernel (NTK) approach, has provided new insights into the dynamics of learning, generalization, and the impact of initialization. One key DNN architecture remains to be kernelized, namely, the recurrent neural network (RNN). In this paper we introduce and study the Recurrent Neural Tangent Kernel (RNTK), which provides new insights into the behavior of overparametrizeed RNNss A key property of the RNTK should greatly benefit practitioners is its ability to compare inputs of different length. To this end, characterize how the RNTK weights different time steps to form its output under different initialization parameters and nonlinearity choices. A synthetic and 56 real-world data experiments demonstrate that the RNTK offers significant performance gains over other kernels, including standard NTKs, across a wide array of data sets.
INTRODUCTION
The overparameterizztion of modern deep neural networks (DNNs) has resulted in not only remarkably
good generalization performance on unseen data (Novak al. 2018 Neyshabur et 2019 Belkin
ct al. 2019) but also guarantees that gradient descent learning can find the global minimum of
their highly nonconvex loss functions (Du al. 2019b Allen
al. 2019b a Zou al. 2018
Arora et al., 2019b). From these successes, a natural question arises: W What happens when we take
overparameterization to the limit by allowing the width of DNN's hidden layers to go infinity?
Surprisingly, the analysis of such (impractical) DNN becomes analytically tractable. Indeed, recent work has shown that the training dynamics of finfinitewwidt) DNNs under gradient flow captured by constant kernel called the Neural Tangent Kernel (NTK) that evolves according to linear ordinary differential equation (ODE) (Jacot et al. 2018 Lee et al. 2019 Arora et al. 2019a).
Every DNN architecture and parameter initialization produces distinct NTK. The original NTK was derived from the Multilayer Perceptron (MLP) (Jacot et al., (2018) and was soon followed by kernels derived from Convolutional Neural Networks (CNTK) (Arora et al., 2019a| Yang 2019a). Residual DNNs (Huang et al., 2020), and Graph Convolutional Neural Networks (GNTK) (Du et al. 2019a). In Yang 2020a), general strategy obtain the NTK of any architecture provided.
In this paper, we extend the NTK concept to the important class of overparametrized Recurrent Neural Networks (RNNs), a fundamental DNN architecture for processing sequential data. We show that RNN in its infinite-width limit converges to a kernel that we dub the Recurrent Neural Tangent Kernel (RNTK). The RNTK provides high performance for various machine learning tasks, and an analysis of the properties of the kernel provides useful insights into the behavior of RNNs in the following overparametrized regime. In particular, we derive and study the RNTK to answer the following theoretical questions:
Q: Can the RNTK extract long-term dependencies between two data sequences? RNNs are known to underperform at learning long- long-term dependencies due to the gradient vanishing or exploding
(Bengio et al., 1994). Attempted ameliorations have included orthogonal weights (Arjovsky et al., 2016:Jing et 2017 Henaff et al. 2016) and gating such as in Long Short-Term Memory (LSTM) (Hochreiter & Schmidhuber 1997) and Gated Recurrent Unit (GRU) (Cho et al. 2014) RNNs. We demonstrate that the RNTK can detect long-ten dependencies with proper initialization of the hyperparameters, and moreover, we show how the dependencies are extracted through time via different hyperparameter choices.

---

Published as a conference paper at ICLR 2021
Q: Do the recurrent weights of the RNTK reduce its representation power compared to other NTKs? An attractive property of an RNN that is shared by the RNTK is that it can deal with sequences of different lengths via weight sharing through time. This enables the reduction of the number of learnable parameters and thus more stable training at the cost of reduced representation power. We prove the surprising fact that employing tied vs. untied weights in RNN does not impact the analytical form of the RNTK.
Q: Does the RNTK generalize well? A recent study has revealed that the use of an SVM classifier with the NTK, CNTK, and GNTK kernels outperforms other classical kernel-based classifiers and trained finite DNNs on small data sets (typically fewer than 5000 training samples) (Lee et al.. 2020, Arora et al. 22119]] 2020; Du et al.) 2019a). We extend these results to RNTKs to demonstrate that the RNTK outperforms variety of classic kernels, NTKs and finite RNNs for time series data sets in both classification and regression tasks. Carefully designed experiments with data of varying lengths demonstrate that the RNTK's performance accelerates beyond other techniques as the difference in lengths increases. Those results extend the empirical observations from (Arora et al. 2019a 2020 Du ct al. 2019a Lee et al. 2020) into finite DNNs, NTK, CNTK, and GNTK comparisons by observing that their performance- wise ranking depends the employed DNN architecture.
We summarize our contributions as follows:
[C1] We derive the analytical form for the RNTK of an overparametrized RNN at initialization using rectified linear unit (ReLU) and error function (erf) nonlincarities for arbitrary data lengths and number of layers (Section B.1).
[C2] We prove that the RNTK remains constant during (overparametrizze)) RNN training and that the dynamics of training are simplified to set of ordinary differential equations (ODEs) (Section
[C3] When the imput data sequences are of equal length, we show that the RNTKs of weight-tied and weight-untied RNNs converge the same RNTK (Section 3.3).
[C4] Leveraging our analytical formulation of the RNTK, we empirically demonstrate how correla- tions between data at different times weighted by the function learned by RNN for different sets of hyperparameters. We also offer practical suggestions for choosing the RNN hyperparameters for deep information propagation through time (Section 3.4
[C5] We demonstrate that the RNTK is eminently practical by showing its superiority over classical kernels, NTKs, and finite RNNs exhaustive experiments on time-series classification and regression with both synthetic and 56 real-world data sets (Section 4).
2 BACKGROUND AND RELATED WORK
Notation. We denote [n] = (1.....n) and Ia the identity matrix of size d. [A]i, represents the (i, j)th entry of a matrix, and similarly [a]: represents the i-th entry of vector. We use x(-) R - IR to represent the activation function that acts coordinate wise on vector and d' to denote its derivative. We will often use the rectified linear unit (ReLU) d(x) = max(0, x) and error function (erf) p(z)= = VF fo e =² dz activation functions. (H, Σ) represents the multidimensional Gaussian distribution with the mean vector μ and the covariance matrix Σ.
Recurrent Neural Networks (RNNs). Given an input sequence data æ = (x1 )T of length T with data at time t, De E RT simple RNN (Elman 1990) performs the following recursive computation at each layer and each time step &
g (1)0 ((0 (C- (0)))))))))))))))))))))))))))( + U (8- (.)) + b(0
h (.000))) = @b (g(ttt)))
where (()) E Raxn ((8) E R= for E E [L]. U(1) E Ruxm and U - pux" for 2 2 are the RNN parameters. (E.1) is the pre-activation vector at layer l and time step t, and h (e.0) (æ) is the after-activation (hidden state). For the input layer & = O, we define h (z)))))) == xt. (2.0) (z) as the initial hidden state at layer l that must be initialized to start the RNN recursive computation.
The output of an L-hidden layer RNN with linear read out layer is achieved via
fa(x) = Vh (L.T) (x),
where V E Rdxx, Figure visualizes an RNN unrolled through time.
2

---

Published as a conference paper at ICLR 2021
Figure 1: Visualization of a simple RNN that high- lights a cell (purple), layer (red) and the initial hidden state each layer (green). (Best viewed in color.)
W
W
(an)
(a)))
A (m)
W(O)
(1(
(x))
N (ar)
A0 (m)
((
Neural Tangent Kernel (NTK). Let (a:) Rdd be the output of DNN with parameters 0. For two input data sequences a and x', the NTK is defined as (Jacot et al. 2018)
(x, oV (x), V fo. (x')).
where Sa, and Og are the network output and parameters during training at time Let X' and ) be the set of training inputs and targets, ((, v) Rd R R+ be the loss function, and
C X E(a,))xx ((fo. (x), y) be the the empirical loss. The evolution of the parameters 9g and output of the network fo, on a test input using gradient descent with infinitesimal step size (a.k.a gradient flow) with learning rate 1) given by
00:
V Vo fo. (2) (x)
(1)
Ōs
0, (x: fo, (x) V fo, v = -
fo, (2)
(2)
Ös
Generally, + (x. x²). hereafter referred the empirical NTK, changes over time during training, making the analysis of the training dynamics difficult. When fe, corresponds to an infinite-widih MLP, (Jacot et al. 2018) showed that (z, converges to limiting kernel at initialization and stays constant during training, i.e..
lim (2,xx²)= lim 0o(2, x') = O(x, x') Vs, n-+00
11+000
which is equivalent to replacing the outputs of the DNN by their first-order Taylor expansion in the parameter space (Lee et al.) 2019). With mean-square error (MSE) loss function, the training dynamics in (1) and (2) simplify to set of linear ODEs, which coincides with the training dynamics of kernel ridge regression with respect to the NTK when the ridge term goes to zero. A nonzero ridge
regularization can be conjured up by adding regularization term 1² |1, - 0ol1 to the empirical loss
(Hu al. 2020
THE RECURRENT NEURAL TANGENT KERNEL
We are now ready to derive the RNTK. We first prove the convergence of an RNN at initialization the RNTK in the infinite-width limit and discuss various insights it provides. We then derive the convergence of an RNN after training to the RNTK. Finally, we analyze the effects of various hyperparameter choices on the RNTK. Proofs of all of our results are provided in the Appendices.
RNTK FOR AN INFINITE- WIDTI RNN AT INITIALIZATION
First we specify the following parameter initialization scheme that follows previous work on NTKs Ja cot et al. 2018), which is crucial to our convergence results:
( of ((), D(E af
of ((222,), U0=
UO, V m
V= V, vn
80)
(3)
Vn
where
W Jejs 11g,
Mig,
(4)
We will refer to (3) and 4 as the NTK initialization. The choices of the hyperparameters ow Fa- o, and のr can significantly impact RNN performance, and we discuss them in detail in Section
We denote time here, since is used to index the time steps of the RNN inputs.
3

---

Published as a conference paper at ICLR 2021
For the initial (at time t 0) hidden state at each layer L, we set (x() to i..d. copy of [00, on)) (Wang et al. 2018 For convenience, we collect all of the learnable parameters of the RNN into = vect {{
3.4
U(9, 1/ V]].
The derivation of the RNTK at initialization is based on the correspondence between Gaussian initialized, infinite-width DNNs and Gaussian Processes (GPs), known as the DNN-GP. In this setting every coordinate of the DNN output tends to GP as the number of units/neurons in the hidden layer (its width) goes to infinity. The corresponding DNN-GP kernel is computed as
x'x = E [[fo(=)), [fo()))) Vi [d]
(5)
B~N
First introduced for lingle-layer, fully-connected neural network by (Neal
1995
recent works on
NTKs have extended the results for various DNN architectures (Lee et al. 2018 Duvenaud et al. 2014 Novak et al., 2019) Garriga-A Alonso al. 2019 Yang 20T9b), where in addition to the output, all pre-activation layers of the DNN tends to GPs in the infinite-width limit. In the case of RNNs, each coordinate of the RNN pre-activation g (f++))
(x) converges to a centered GP depending on the
inputs with kernel
glen' x²)
[ (2.6) (x));: [g (e (x An~
E.
Vi E [n]]
(6)
As per Yang 2019a). the gradients of random iidtnite-width DNNs computed during backpropagation
also Gaussian distributed. In the case of RNNs, every coordinate of the vector 8 (x)
vn( V (o) converges to GP with kernel
[[)())))))) (x))) Vi E [n]-
0~N
Both convergences occur independently of the coordinate index i and for inputs of possibly different lengths, i.e., * T'. With (6) and we now prove that an infinite- width RNN at initialization converges to the limiting RNTK.
Theorem Let and x' be two data sequences of potentially different lengths T and respectively, Without loss of generality, assume that T < T", and let T := T' - T. Let n be the number of units in the hidden layers, the empirical RNTK for an L-layer RNN with NTK initialization converges the following limiting kernel as n + 00
lim 0o( x') Oxx, (L,,T,T)) (x, @ Ia. n-+00
(8)
where
L ΣΣ tm1
((1.1))) (x0 + K(xxx²),
(9)
with K(x,x'), x"), E(tiatt) (x, x'), and (I(G),)))) (x, x²) defined in
Remarks. Theorem I holds generally for any two data sequences, including different lengths ones. This highlights the RNTK's ability produce similarity measure O(x, x²) even if the inputs are of different lengths, without resorting to heuristics such as zero padding the inputs to the to the max length of both sequences. Dealing with data of different length is in sharp contrast to common kernels such as the classical radial basis functions, polynomial kernels, and current NTKs. We showcase this capability below in Section 4
To visualize Theorem I we plot in the left plot in Figure 2 the convergence of single layer, sufficiently wide RNN to its RNTK with the two simple inputs æ = (1, (1,11,1) 1} of length 3 and x' {cos((a), sin(a)) } of length 2, where
[0, 2T.. For an RNN with sufficiently large hidden state (n = 1000), we see clearly that it converges to the RNTK (n = oo).
RNTK Example for Single-Layer RNN. We present concrete example of Theorem by showing how to recursively compute the RNTK for a single-layer RNN; thus we drop the layer index for notational simplicity. We compute and display the RNTK for the general case of multi- layer RNN in Appendix B.3 To compute the RNTK (T,T")
(ar, x. ), need to compute the GP
4

---

Published as a conference paper at ICLR 2021
11
1000
Weight-mntied Weight
(2t 27)
1.5
11 0c
log 6
-1.2
-1.4
0-
-1.6
-18
log(n) (n)
Ch
Figure 2: Empirical demonstration of wide, single-layer RNN converging its limiting RNTK. Left: convergence for a pair of üifferent-lenghe inputs æ = -1.1) and x' {cos(a), sin(a)) with varying a= 2m. The vertical axis corresponds to the RNTK values for different values of a. Right: convergence of weight-tied and weight-untied single layer RNN to the same limiting RNTK with increasing width (horizontal axis). The vertical axis corresponds the average of the normalzzll error between the empirical RNTK computed using finite RNNs and the RNTK for 50 Gaussian normal signals of length T 5.
kemels (x æ²) and ( x'). We first define the operator Vol [ that depends on the nonlinearity 66-) and positive semi-definite matrix K E R222
Vel [ B[(((z) ((22)),
72) N(00 K).
(10)
Following Yang 2019 9a), we obtain the analytical recursive formula for the GP kernel ((+tt) x')
for single layer RNN as
ga.1) 2')
- oh 1 (m==')
m (1) + +oz
(11)
(2t, a1) + oh 02
1>1
(12)
m
ga.1) (x.x') (x)1 a/ra) + o
1>1
(13)
+ 0²
E(0 x') ou V K (112)) (x, x²)]
(z,, xx), +o²
1,1'1
(14)
m
K(xxx0) x') = VoVo Φ K (T (T+1 1.7 11 (xx xt)) xt)],
(15)
where
-(-111-1) 1) (.)
111- (xr, x¹)
K(t (((,))(),, (x,
(16)
-(--1,1-11 (x.
111- (x', x¹)
Similarly, we obtain the analytical recursive formula for the GP kernel (1(,,t+)) x') as
(ITTT") (z, x²) = og V. / K [KT+,,++++))
(x, x')]
(17)
11(,)-) x') = au V or (++1err-)) (x) (x, x')) (((,,=")(((ttttt+tt) (x, x')
EE [T' - 1]
(18)
(14.0) (xx, = 0
t' - t +
(19)
For ReL. and x erf. provide analytical expressions for V K and V [ in Appendix
B.5
These yield an explicit formula for the RNTK that enables fast and point-wise kernel evaluations.
For other activation functions, one can apply the Monte Carlo approximation to obtain V [
and
Ver []]
Novak et al. 2019).
3.2
RNTK FOR AN INFINITE- WIDTH RNN DURING TRAINING
We prove that an infinitely-win RNN, not only at initialization but also during gradient descent training, converges to the limiting RNTK at initialization.
Theorem Let n be the number of units of each RNN's layer. Assume that ( X) is positive
definite on X such that Amin (0(X, > O. Let ny" : 2((miu ((),in(((X x²)) + Amax ( (0 X ) For an T-laaee RNN with NTK initialization as in 3 trained under gradient flow (recall ( and
(2) with 7) < n",, we have with high probability
sup 10 00ll2
( (
OXX) x)
0
Vn
5

---

Published as a conference paper at ICLR 2021
+(0
0.0
-v 0.0IG
-7a
-0
0
0.05
0.1
11:0K (
-7
1
1
Per time step & (horizontal axis) sensitivity analysis (vertical axis) the RNTK for the ReLU (top row) and erf (bottom row) activation functions for various weight noise hyperparameters. We also experiment with different RNTK hyperparameters in each of the subplots, given by the subplot internal legend. Clearly, the ReLU (top-row) provides through time). On the other hand, erf (hottom row) sees more erratic behavior either focusing entirely early time-steps or on the latter ones.
Figure 3:
stable kernel across time steps (highlighted by the constant sensitivity
Remarks. Theorem 2 states that the training dynamics of an RNN in the Sefnite-widtt limit as in [I (2) are governed by the RNTK derived from the RNN at its initialization. Intuitively, this is due to the NTK initialization 33, 4 which positions the parameters near a local minima, thus minimizing the amount of update that needs to be applied to the weights to obtain the final parameters.
3.3 RNTK FOR AN INFINITE WIDTH RNN WITHOUT WEIGHT SHARING
We prove that, in the width limit, an RNN without weight sharing (untied weights), i.e., using independent new weights ((e,)) U(L,)) and ((.,)) at each time step f, converges to the same RNTK as an RNN with weight sharing (tied weights). First, recall that it is a common practice to use weight-tied RNNs, i.e., in layer é, the weights ((),, U and (( are the same across all time steps This practice conserves memory and reduces the number of learnable parameters. We demonstrate that, when using untied-weight the RNTK formula remains unchanged.
Theorem 3 For inputs of the same length, an RNN with untied weights converges the same RNTK as an RNN with tied weights in the infinite-width (n - oo) regime.
Remarks. Theorem 3 implies that weight-tied and weight-untied RNNs have similar behaviors in the infinite-widthh limit. It also suggests that existing results on the simpler, weight-unties RNN setting may be applicable for the more general, weight-tied RNN. The plot the right side of Figure empirically demonstrates the convergence of both the weight-tied and weight-untied RNNs to the RNTK with increasing hidden layer size n; moreover, the convergence rates are similar.
3.4 INSIGHTS INTO THE ROLES OF THE RNTK's S HYPERPARAMETERS
Our analytical form for the RNTK is fully determined by a small number of hyperparameters, which contains the various weight variances collected into S = (a.. ou, Tb, function
ob } and the activation 2 In standard supervised-lcamning settings, one often performs cross-validation to select the hyperparameters. However, since kernel methods become computationally intractable for large datasets, we seek a more computationally friendly alternative to cross- validaaion.... Here we conduct novel exploratory analysis that provides new insights into the impact of the RNTK hyperparameters on the RNTK output and suggests simple method to select them priori in a deliberate manner.
To visualize the role of the RNTK hyperparameters, we introduce the sensitivity s(1) of the RNTK of two input sequences and x'' with respect to the input a; at time f.
s(t)
V æ, (xx, x'
(20)
From
18 emphasize that a. merely scales the RNTK and does change its overall hehavior.

---

Published as a conference paper at ICLR 2021
Table 1: Summary of time series classification results on 56 real-world data sets. The RNTK outperforms classical kernels, the NTK, and trained RNNs across all metrics. See Appendix A for detailed description of the metrics.
RNTK
Polynomisl
Ganssian RNN
Ideaniiy
GRU 09.301 #: 22.07
Acc. mens
MIL1SY: =: 15.99%5
77.34% # 16.61%
78.15%
16.59%
77.09%
16.40%
55.WWE #: 26,42%
63.8%% di 19:12
190
92.86%
85.71%
87.60%
82. 14%
28, 57%
42 3..6%%
60.71%
P9ST
$0.36%
66.07%
75.00%
67 5666
17.56%
2144%%
46.4358
PMA
97.23%
90.30%
98.86%
94,23%
67.06%
78.22%
84.31%
Priddman Kank
2,38
3,00
2,89
3,46
5.86
5.21
4.21
Here, s(I) indicates how sensitive the RNTK is to the data at time I, i.e. Lt, in presence of another data sequence æ'. Intuitively, large/small s(t) indicates that the RNTK relatively sensitive/nneesstive to the input 2y at time t.
The sensitivity is crucial to understanding to which extent the RNTK prediction is impacted by the input at each time step. In the case where some time indices have a small sensitivity, then any input variation in those corresponding times will not alter the RNTK output and thus will produce a metric that is invariant to those changes. This situation can be beneficial or detrimental based on the task at hand, Ideally, and in the absence of prior knowledge on the data, one should aim to have a roughly constant sensitivity across time in order to treat all time steps equally in the RNTK input comparison.
Figure plots the normalized sensitivity s(t) /a//max/ssss = 100, with s(t) computed numerically for æt, ot ~ NO, 1). We repeated the experiments 10000 times; the mean of the sensitivity is shown in Figure 3 Each of the plots shows the changes of parameters SRALU = {v2, 0, for e ReLU and Serf = 0.01, 0.05, 0} for e = erf.
for two data sequences of the same length
3 we first observe that both ReLU and erf show similar per time step sensitivity measure s(t) behavior around the hyperparameters SReLU and Sart. one varies any of the weight variance parameters, the sensitivity exhibits wide range of behavior, and in particular with erf. We observe that ow has a major influence on st)). For RcLU, a small decrease/increase in ow can lead to over-sensitivity of the RNTK to data the last/first times steps, whereas for crf, any changes in ow leads to over-sensitivity to the last time steps.
From Figure
Another notable observation is the importance of one which is usually set to zero for RNNs. (Wang eet al.) 2018) showed that a non-zero d acts as a regularization that improves the performance of RNNS with the ReLU nonlinearity. From the sensitivity perspective, non-zero σn results in reducing the importance of the first time steps of the input. We also see the same behavior in erf, but with stronger changes as o, increases. Hence whenever one aims reinforcing the input pairwise comparisons, such parameters should be favored.
This sensitivity analysis provides a practical tool for RNTK hyperparameter tuning. In the absence of knowledge about the data, hyperparameters should be chosen to produce the least time varying sensitivity. If given priori knowledge, hyperparameters can be selected that direct the RNTK the desired time-steps.
EXPERIMENTS
We now empirically validate the performance of the RNTK compared to classic kernels, NTKs, and trained RNNs on both classification and regression tasks using large number of time series data sets. Of particular interest the capability of the RNTK offer high performance even on inputs of different lengths.
Time Series Classification. The first set of experiments considers time series inputs of the same lengths from 56 datasets in the UCR time-series classification data repository (Dau et al. 2019). We restrict ourselves to selected data sets with fewer than 1000 training samples and fewer than 1000 time steps (T) as kernel methods become rapidly intractable for larger datasets. We compare the RNTK with a variety of other kernels, including the Radial Basis Kernel (RBF), polynomial kernel, and NTK (Jacot al.) 2018), well as finite RNNs with Gaussian, identity (Le et al. 2015) initialization, and GRU (Cho et al. 2014]. We use = ReLU for both the RNTKs and NTKs. For each kernel, train a C-SVM Chang & Lin 2011 classifier, and for each finite RNN we gradient descent training. For model hyperparameter tuning, we use 10-fold cross- validation.. Details on the data sets and experimental setup available in Appendix A.T
7

---

Published as a conference paper at ICLR 2021
(a) Sinusoidal signal
(b) Sinusoidal signal
(c) Google stock value
(d) Google stock value
RNTK
SNR
NTK RDF
Polynomla
x-
Tvar
T
13
Ntrain
Figure 4: Performance of the RNTK on the synthetic sinusoid and real-world Google stock price data sets compared to three other kernels. We vary the input lengths (a,c), the input noise level (b), and training size (d). We compute the average SNR by repeating each experiment 1000 times. The RNTK clearly oulperforms all of the other kemels under consideration. Figure 4b suggests that the RNTK performs better when input noise level is low demonstrating one case where time recurrence from RNTK might be sub-optimal as it collects and accumulate the high noise from each time step as opposed to other kernels treating each independently.
We summarize the classification results over all 56 datasets Table detailed results on each data set is available in Appendix A.2 We see that the RNTK outperforms not only the classical kernels but also the NTK and trained RNNs in all metries. The results demonstrate the ability of RNTK to provide increased performances compare to various other methods (kernels and RNNs). The superior performance of RNTK compared to other kernels, including NTK, can be explained by the internal recurrent mechanism present in RNTK, allowing time-series adapted sample comparison. In addition, RNTK also outperforms RNN and GRU. As the datasets we consider are relative small in size, finite RNNs and GRUs that typically require large amount of data to succeed do not perform well in our setting, An interesting future direction would be to compare RNTK to RNN/GRU on larger datasets.
Time Series Regression. We now validate the performance of the RNTK time series inputs of different lengths on both synthetic data and real data. For both scenarios, the target is to predict the next time-step observation of the randomly extracted windows of different length using kernel ridge regression.
We compare the RNTK to other kernels, the RBF and polynomial kernels and the NTK. We also compare our results with a data independent predictor that requires no training, that is simply to predict the next time step with previous time step (PTS).
For the synthetic data experiment, we simulate 1000 samples of one period of a sinusoid and add white Gaussian noise with default o, = 0.05. From this fixed data, we extract training set size Nurain = 20 segments of uniform random lengths in the range of [Tixed Tixed + Tvar] with Tixed = 10. We use standard kernel ridge regression for this task. The test set is comprised of Neest 5000 obtained from other randomly extracted segments, again of varying lengths. For the real data, we use 975 days of the Google stock value in the years 2014-2018, As in the simulated signal setup above, we extract Nursin segments of different lengths from the first 700 days and test the Neest segments from days 701 to 975. Details of the experiment are available in Appendix A.2
We report the predicted signal-to-noise ratio (SNR) for both datasets in Figures 4a and 4c for various values of Tar- We vary the noise level and training set size for fixed Tvar = TO in Figures (4b and 4d. As we see from Figures 4a| and 4cc the RNTK offers substantial performance gains compared to the other kernels, due to its ability to naturally deal with variable length inputs. Moreover, the performance gap increases with the amount of length variation of the inputs Ter- Figure 4d demonstrates that, unlike the other methods, the RNTK maintains its performance even when the training set small. Finally, Figure 4c demonstrates that the impact of noise in the data on the regression performance is roughly the same for all models but becomes more important for RNTK with a large an this might be attributed to the recurrent structure of the model allowing for a time propagation and amplification of the noise for very low SNR. These experiments demonstrate the distinctive advantages of the RNTK over classical kernels, and NTKs for input data sequences of varying lengths.
In the case of PTS, we expect the predictor to outperform kernel methods when learning from the training samples is hard, due to noise in the data small training size which can lead to over fitting. In Figure 4a RNTK and Polynomial kernels outperforms PTS for all values of T Terr but for larger T Tear, NTK and RBF under perform PTS due the increasing detrimental effect of zero padding.
8

---

Published as a conference paper at ICLR 2021
For the Google stock value, methods due to the nature of those data heavily relying on close past data. However, RNTK is able to reduce the effect of over-fitting, and provide the closest results to PTS among all kernel methods employed, with increasing performance as the number of training samples increase.
superior performance of PTS with respect all other kernel
5 CONCLUSIONS
In this paper, we have derived the RNTK based on the architecture a simple RNN. We have proved that, at initialization, after training, and without weight sharing, any simple RNN converges the same RNTK. This convergence provides new insights into the behavior of infinite-width RNNs, including how they process different-length imputs, their training dynamics, and the sensitivity of their output at every time step to different nonlinearities and initializations. We have highlighted the RNTK's practical utility by demonstrating its superior performance on time series classification and regression compared to a range of classical kernels, the NTK, and trained RNNs. There are many avenues for future research, including developing RNTKs for gated RNNs such as the LSTM (Hochreiter & Schmidhuber 1997) and investigating which of our theoretical insights extend to finite RNNs.
ACKNOWLEDGMENTS
This work supported by NSF grants CCF-1911094, IIS-1838177, and IIS-1730574; ONR grants N00014-18- 12571, N00014-20-1-2781 and N00014-20-1-2554; AFOSR grant FA9550-18-1-044 and Vannevar Bush Faculty Fellowship. ONR grant N00014-18-1-2047.
REFERENCES
Zeyuan Allen-Zhre Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In In Advances in Neural Information Processing Systems, pp- 6155-6166, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In Advances in Neural Information Processing Systems, pp. 6676-6688, 2019b.
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks, In International Conference on Machine Learning, pp. 120-1128, 2016.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8141-8150. 2019a.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019b.
Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Confer- ence on Learning Representations, 2020. URL httpp::/openrevieew forett/formmmio
rk18sJBYvH
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learin practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116632):15899-15855 2019. URLhttts.. //www. ppass org/ cotte/ntt/1////e//1/12
Yoshua. Bengio, Patrice. Simard, and Paolo. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Trans. Neural Networks, 5(2):157-166, 1994.
Erwin Bolthausen. An iterative construction of solutions of the tap equations for the sherrington- kirkpatrick model. Communications Mathematical Physics, 325(1):333-366, 2014.
Chih- Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:22 2011. Software available at
http: /tt:://www.... www. cs ntu. edu. wtt.ttt/wlliiio

---

Published as a conference paper at ICLR 2021
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using mn encoder-decoder for statistical machine translation. arXiv preprint arXiv: 1406. 100.1078, 2014.
Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, pp. 342-350 2009.
Hoang Anh Dau, Eamonn Keogh, Kaveh Kamgar, Chin-Chia Michael Yeh, Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, Yanping Chen, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, Gustavo Batista, and MI. Hexagon. The UCR time series classifica- tion archive, 2019. /tt.ttpss: www. CS UCr wwwpedddooo///eeeeeeeeee wttpentttiimmeetett http:/tttmmssereiseeeeeeeeee _atta________
2018/]
Simon S. Du, Kangcheng Hou, Russ R Salakhutdinov, Barnahas Poezos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 5724-5734, 2019a.
Simon S. Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019b.
David Duvenaud, Oren Rippel, Ryan Adams, and Zoubin Ghahramani. Avoiding pathologies in very deep networks. In Artificial Intelligence and Statistics, pp. 202-210, 2014.
Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):19-211,, 1990. URL https / www. /wwww. www.scciinediire.. rect rect. com/ /ct.e//c/..rrrccee/////////222/0
M. Femmández-Delgado, M.S. Sirsat, E. Cernadas, Alawadi, S. Barro, and M. Febrero-Bande. An extensive experimental survey of regression methods. Neural Networks, 111:11 34, 2019.
Adrià Garriga-Nlonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks as shallow gaussian processes. In International Conference on Learning Representations, 2019. httttttt////peeette
net/
Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long-memor, tasks. In International Conference on Machine Learning, pp. 2034 2042. PMLR, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1780, 1997.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference on Learning Representations, 2020. /tts:: httpeeewwwwwwwweeeeeeeeeeeeeeeee
n wwt.://orrummii--iekkyyy....
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks generalize better than deep feedforward networks?-a neural tangent kernll perspective. arXiv preprint arXiv:2002.06262. 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in neural information processing systems, pp. 8571 1580, 2018
Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačić. Tunable efficient unitary neural networks (eunn) and their application to mns. In International Conference on Machine Learning, pp. 1741, 2017.
Quoc V Le, Navdeep Jaitly, and Geoffrey E Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv:1504.009411 2015.
Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. In International Conference on Learn- ing Representations, 2018. URL httphhttpps//ooeeeeiiieeee oetererreeee..eeeoooooooooossass 07.
10

---

Published as a conference paper at ICLR 2021
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, pp. 8572-8583, 2019.
Jaehoon Lee, Samuel S Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. arXiv preprint arXiv:2007.15800 2020.
Radford M Neal. Bayesian Learning for Neural Networks. PhD thesis, University of Toronto, 1995.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations, 2019.
Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization in neural networks: an empirical study. In International Confer- ence on Learning Representations, 2018. URL https::/
net/ forum?ii
HJC2SZ2CA
Roman Novak, Lechao Xiao, Yasaman Bahri, Jachoon Lee, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many channels gaussian processes. In International Conference Learning Representations, 2019. URL
https::/cppeneviees net.
Zichao Wang, Randall Balestriero, and Richard Baraniuk. A max-affine spline perspective of
recurrent neural networks. In International Conference on Learning Representations, 2018. URL
net forum httpss:/opeerevvilt 2 (oopoeeeemdddBJeeeeeeeee
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1rX1::1902.04760, 2019a.
Greg Yang. Tensor programs I: Wide feedforward recurrent neural networks of any architecture are gaussian processes. arXiv preprint urXiv:/9100 12478, 2019b.
Greg Yang. Tensor programs II: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006.14544 2020a.
Greg Yang. Tensor programs III: Neural matrix laws. arXiv preprint arXiv:2009.10683 2020b.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arXiv preprint arXiv: 1,08888 2018.

---

Published as a conference paper at ICLR 2021
A EXPERIMENT DETAILS
A.1 TIME SERIES CLASSIFICATION
Kernel methods settings. We used RNTK, RBE, polynomial and NTK (acot al. 2018). For data pre-processing, we normalized the norm of each æ to 1. For training we used C-S in LIBSVM library (Chang Lin 201T) and for hyperparameter selection we performed 10-fold validation for splitting the training data into 90% training set and 10% validation test. We then choose the best performing set of hyperparameters on all the validation sets, retrain the models with the best set of hyperparameters on the entire training data and finally report the performance on the unseen test data. The performance all kernels on each data set is shown table
For C-SVM we chose the cost function value
C {0.01, 0.1, 1, 10, 100}
and for each kernel we used the following hyperparameter sets
RNTK: We only used single layer RNTK, we ReLU and the following hyperparameter sets for the variances:
{1.34, 1.35, 1.36, 1.37, 1.38, 1.39, 1.40, 1.41, 1.42, 22, 1.43, 1.44, 1.45, 1.46, 1.47)
Tx =1
on E {0, 0.00 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.,,0.., On E (0, 0,,,0.11,.11..5.11
NTK: The formula for NTK of L-layer MLP (Jacot et al. 2018) for æ, x e R is:
(11 0
(x, x.'
+ +0²
E00 x²) o V (T(t) (I, x²)] of
E [T.
(0 (x, x') od V a IK (e+ (x, (x,
i E
|)- (x)x) (x,
K (x, (x,xx) E((-1) xx)
K(x,, x') V (++1) (L+)+ (2,
L
L
KNTK Σ
g (z, x') II (1x)')))
+ x')
#=
and we used the following hyperparamters
LE [10]
Tw (0.5, 12,,,,,,, E 0.00 01,,0,01,,,,,,,000.1111,
RBF:
KRBE - a e {0.01, 0.05, 0.1, |0000000000000000000000000011111 1,,,,, 10, 20, 30, 30,3004400 40, 100)
Polynomial:
Kpolynomial (2, (2,x') (r + (x,
dE [5]
(0, (0,0.1,0.2, 0.5,
12

---

Published as a conference paper at ICLR 2021
Table Test accuracy of each model on 56 time series data set from UCR time-series classification data repository (Dau et al. 2019).
Dataset
RNTK
NTK
RBF
POLY
Gaussian RNN
Identity RNNN
GRU
Strawberry
98.38
97.57
97.03
96.76
94.32
75.4
91.62
ProxiallPhannxOOtineeCrrrrr
89
87.97
87.29
86.94
82.81
74.57
86.94
PowerCons
97.22
97.22
96.67
91.67
96.11
99.44
Ham
70.48
71.63
66.67
71.43
53.33
60
60.95
SmallKiichenApplianncs
67. .47
38.4
40.27
37.87
60.22
76
71.46
Screen'yppe
41.6
43.2
43.47
38.4
40
41.06
36.26
MiddieePallanxCCuiinCCooom
57.14
57.14
48.7
64.29
76.28
57.04
74.57
RefrigerationDeviies
46,93
37.07
36.53
41.07
50.93
46.66
Yoga
84.93
84.63
84.63
84.87
46.43
76.66
61.83
Computers
59.2
S5.2
58.8
56.4
53.2
$5.2
58.8
ECG5000
93.76
94.04
93.69
93.96
88.4
93.15
93.26
Fish
90.29
84
85.71
88
28
38.28
UWaveGestureLibraay
79.59
78.7
78.48
65.83
55.97
75.34
73.64
UWaveGestureL.ibrat Y
71.56
70.63
70.35
70.32
44.5
65.18
65.38
UWaveGesturel.
73.95
73.87
72.89
71.94
43.29
67.81
70.32
StarLLighCCurves
95.94
96.19
94.62
94.44
82.13
86.81
96.15
CricketX
60.51
59.49
62.05
62.56
8.46
63.58
26.41
CricketY
63.85
58.97
60.51
59.74
15.89
59.23
36.15
CricketZ
60.26
59.23
62.05
59.23
8.46
57.94
41.28
DisalPhalanxOuutieCCCrre
77.54
77.54
75.36
73.91
69.92
69.56
75
Worms
57.14
50.65
55.84
50.65
35.06
49.35
41.55
SynthetieControl
98.67
96.67
97.67
92.66
97.66
Herring
56.65
59.38
59.38
59.38
23.28
59.37
59.38
Medicallmages
74.47
73.29
75.26
74.61
48.15
64.86
69.07
SwedishLeaf
90.56
91.04
91.36
90.72
59.2
45.92
91.04
ChlorineConccnnrraiion
90.76
77.27
86.35
91.54
65.99
55.75
61.14
SmoothSubspace
96
87.33
92
86.67
94
95.33
92.66
TwoPatterns
94.25
90.45
91.25
93.88
99.7
99.9
100
Faceall
74.14
83.33
83.25
82.43
53.66
70.53
70.65
DistalPhalanx TW
66.19
69.78
66.91
67.37
67.62
64.74
69.06
MiddiePhalanxTTV
57.79
61.04
59.74
60.39
58.44
58.44
59.09
FCcesUCR
81.66
80.2
80.34
82.98
53.21
75.26
79.46
OliveOil
90
86.67
86.67
83.33
66.66
40
40
UMD
91.67
92.36
97.22
90.97
44.44
71.52
100
nseelEPGRegular
99.6
99.2
99.6
96.79
100
98.39
Meat
93.33
93.33
93.33
93.33
0.55
33.33
Lightning2
78.69
73.77
70.49
68.85
45.9
70.49
67.21
Lightning7
61.64
60.27
63.01
60.27
23.28
69.86
76.71
Car
83.33
78.83
80
80
23.33
$8.33
26.66
GunPoint
95.33
95.33
94
74.66
80.66
Arrowhead
80.57
83.43
80.57
74.86
48
56
37.71
Coffee
100
100
92.86
92.86
100
42.85
57.14
Trace
96
81
76
76
70
71
100
ECG200
89
86
plane
98.1
96.19
97.14
97.14
96.19
84.76
96.19
Verrso Young
98.73
97.46
98.73
94.6
53.96
52,38
98.41
GumPPinntMlleVersusee Versue
99.05
99.68
99.37
99.68
68.67
52.53
99.68
AunpointAgeepan
96.52
94.62
95.89
93.99
47.78
47.78
95.56
FreezerRegular Train
97.44
94.35
96.46
96.84
76.07
7.5
86.59
84.22
85.33
86.14
86.67
20
36.66
89.11
Worms TwoClass
62.34
62.34
61.04
59.74
51.94
46.75
57.14
Earthquakes
74,82
74,82
74.82
74.82
65.46
76.97
76.97
Fifty
68.57
68.57
69.67
68.79
34.28
60.21
65.27
Beef
73.33
83.33
93.33
26.67
46.67
36.67
Adiac
76.63
71.87
73.40
77.75
51.4
16.88
60.61
WordSynonyms
57.99
58.46
61.13
62.07
17.71
45.77
53.76
Fintte-width RNN settings. We used 3 different RNNs.
The first is a ReLU RNN with Gaussian
initialization with the same NTK initialization scheme, where parameter variances dw o, v2,
13

---

Published as a conference paper at ICLR 2021
Ju and da 0. The second is ReLU RNN with identity initialization following (Le et al. 2013). The third is a GRU (Cho et al. 2014) with uniform initialization. All models are trained with RMSProp algorithm for 200 epochs. Early stopping is implemented when the validation set accuracy does not improve for 5 consecutive epochs.
We perform standard 5-fold cross validation. For each RNN architecture used hyperparamters of number layer, number hidden units and learning rate as
L {1,2]
T. E {50, 100, 500) 7 E {0.01, 0.001, 0.0001, 0.00001}
Metries descriptions First, only in this paragraph, let i {1,2, N} index total of N datasets and j E MM. index a total of M classifiers. Let V/j be the accuracy of the j-th classifer on the i-th dataset. We reported results on 4 metrics: average accuracy (Acc. mean), P90, P95, PMA and Friedman Rank. P90 and P95 is the fraction of datasets that the classifier achieves at least 90% and 95% of the maximum achievable accuracy for each dataset, i.e.,
P90, = N Σ 1y1s 2 (09(maxyy:)
(21)
PMA the accuracy of the classifier on a dataset divided by the maximum achievable accuracy on that dataset, averaged over all datasets:
1 Σ
Vij
PMA,
(22)
N
max ykj
Friedman Rank (Fernández--eele Delgado et al., 2019) first ranks the accuracy of each classifier on each dataset and then takes the average of the ranks for each classifier over all datasets, i.e..
FR, Σ Tij
1 N
(23)
where riy is the ranking of the j-th classifier on the i-th dataset.
Note that better classifier achieves lower Friedman Rank, Higher P/90 and PMA.
Remark. In order to provide insight into the performance of RNTK in long time steps setting, we picked two datasets with more that 1000 times steps: SemgHHanSSuhjeath22 (T 1024) and StarLightCurves (T = 1024).
A.2 TIME SERIES REGRESSION
For time series regression, we used the 5-fold validation of training set and same hyperparamter sets for all kernels. For training we kernel ridge regression with ridge term chosen form
À E {0, 0.00. 0.1,0,0,,22,33330,,,,,, 0.5, 0.6, 0.7, 0.8, 0.8, 1, 3, 5,6, 6, 7,7,8, 10, 100}
B PROOFS FOR THEOREMS AND 3: RNTK CONVERGENCE AT INITIALIZATION
B. PRELIMINARY: NETSOR PROGRAMS
Calculation of NTK in any architecture relies on finding the GP kernels that correspond to each pre-activation and gradient layers at initialization. For feedforward neural networks with ......, 7z number of neurons (channels CNNs) at each layer the form of this GP kernels can be calculated via taking the limit of n1. ... ny sequentially one by one. The proof is given by induction, where by conditioning on the previous layers, each entry the current layer is sum infinite i.i Gaussian random variables, and based Central Limit Theorem (CLT)) it becomes Gaussian process with
14

---

Published as a conference paper at ICLR 2021
kernel calculated based on the previous layers. Since the first layer is affine transformation of input with Gaussian weights, it is a Gaussian process and the proof is completed. See (Lee et al.) 1018:Duvenaue al. 2014 NNvak al. 2019 Garriga-Alonso et al. 2019) for formal treatment. However, due to weight-sharing sequential limit is not possible and condoning on previous layers does not result in i.i.d. weights. Hence the aforementioned arguments break. To deal with it, in (Yang) 2019a) a proof using Gaussian conditioning trick (Bolthausen, 2014) is presented which allows use of recurrent weights in a network. More precisely, has been demonstrated than neural networks (without batch normalization) can be expressed and series of matrix multiplication and (piece wise) nonlinearity application, generally referred as Netsor programs. has been shown that any architecture that can be expressed as Netsor programs that converge to GPs as width goes to infinity in the same rate, which a general rule to obtain the GP kernels. For completeness of this paper, we briefly restate the results from (Yngg 2019a) which we will use later for calculation derivation of RNTK.
There are 3 types of variables in Netsor programs; A-vars, G-vars and H-vars. A-vars are matrices and vectors with i.i.d Gaussian entries, G-vars are vectors introduced by multiplication a vector by an A-var and H -ars are vectors after coordinate wise nonlinearities is applied to G-vars. Generally, G-vars can be thought of as pre-activation layers which are asymptotically treated as a Gaussian distributed vectors, H-vars after-activation layers and A-vars are the weights. Since in neural networks inputs are immediately multiplied by a weight matrix, it can be thought of as an G-var, namely Isn- Generally Netsor programs supports G-vars with different dimension, however the asymptotic behavior of neural networks described by Netsor programs does not change under this degree of freedom, as long as they go to infinity the same rate. For simplicity, let the G-vars and H-vars have the same dimension n since the network of interest is RNN and all pre-activation layers have the same dimension. We introduce the Netsor programs under this simplification. To produce the output of a neural network, Netsor programs receive a set of G-vars and A-vars as input, and new variables are produced sequentially using the three following operators:
Matmul multiplication of an A-var: A with an H-var: h, which produce a new G-var, g-
Ah
(24)
Lincomp: Linear combination of G-vars, g', 1 S i S k. with coefficients a² E R 1 S S k which produce of new G-var:
a g
(25)
Nonlin: creating new H-var, h, by using nonlinear function o : R that act coordinate wise on a set of G-vars, g', < i
= x ........,"
(26)
Any output of the neural network E R should be expressed as inner product of a new A-var which has not been used anywhere else in previous computations and an H-var:
y/ h
Any other output can be produced by another o' and h' (possibility the same h or v).
It is assumed that each entry of any A-var: : A E R in the netsor programs computations is drawn from (O, # and the input G-vars are Gaussian distributed. The collection of a specific entry of all G-vars of in the netsor program converges in probability to a Gaussian vector ([g")..... [g]] ~
N(,, Σ) for all E
[n] as n goes infinity.
Let p(g) == E [g]e] be the mean of a G-var and E(g.g') E [g]] [g']:] be the covariance between any two G-vars. The general rule for p(g) is given by the following equations:
(g)
if g is input
n(g)=
d'((gg)
ifg
Σ n'g'
(27)
otherwise
15

---

Published as a conference paper at ICLR 2021
For g and g', let G {g'.... .g'.....'" ' with distribution N Eg), where Eg | ( containing the pairwise covariances between the G-vars. (g g') is calculated via the following rules:
be the set of G-vars that has been introduced before g and g'
(g.g')
if and g are inputs
a d'E(g',g)
if g a
"gg.g')
k
& if g Σ d'g'
(28)
d'E(g.g)
E (n
[z)z)((z)]
if = Ah and g' = Ah'
otherwise
.....""".."" .g") Where h "..g'......"" different nonlinearities. This set of rules presents a recursive method for calculating the GP kernels in network where the recursive formula starts from data dependent quantities El and μ which are given.
and h' "'g'..... g")) are functions of G-vars in G from possibly
All the above results holds when the nonlinearities are bounded uniformly by c for some and when their derivatives exist.
The common practice (which netsor programs uses) is to initialize DNNs weights [A]., with (00 ) (known as standard initialization) where generally n is the number of units in the previous layer. In this paper we have used a different parameterization scheme as used in (Jacot al.) (018)) and we factor the standard deviation shown and initialize weights with standard standard Gaussian. This approach does not change the the forward computation of DNN, but normalizes the backward computation (when computing the gradients) by factor 1. otherwise RNTK will be scales by n. However this problem can be solved by scaling the step size by and there no difference between NTK and standard initialization (Lee al. 2019).
Standard vs. NTK initialization.
B.2 PROOF FOR THEOREM SINGLE LAYER CASE
We first derive the RNTK in simpler setting, i.e., a single layer and single output RNN. We then generalize the results to multi-layer and multi-output RNNs. We drop the layer index & to simplify notation. From 3 and 4 the forward pass for computing the output under NTK initialization for each
input x = {0 is given by:
g (z)
(x)
ow Wh (t-11) (x) + Ou Uz, + oa
(29)
Vm
Vn
(x)) (x))
(30)
fo(x) = Tv T (2)) (x))
(31)
30 and 31 use all the introduced operators introduced in 24 25 and 26 given input variables W. (Ux, T b. and h (0) (z))
Note that 29
First, we compute the kernels of forward pass (tt()) (æ, x') and backward pass (It.')) (x. x') intro- duced in (6) and ( for two input æ and æ'. Note that based (27) the mean of all variables is zero since the inputs are all zero mean. the forward pass for the intermediate layers we have:
E(G'') (z, x') E(g (0) (x), g (xx))
=
(h + Vm
Uz + obb,
on Wh(t'-1)
+ Ou Ux' + oab)
Vn
Vn
m
=
Th Ta wh (z-1)
wh (1 + Ein
Uni,
Un'p Enn (obb,aab).
vn
m
v m
16

---

Published as a conference paper at ICLR 2021
We have used the second and third rule in (28 to expand the formula, We have also used the first and fifth rule to set the cross term to zero, i.e,
Σ
Wh
(x);
Un 0
vn
Σ
Wh (t-1) (x), o&b 0
Vn
Σ
Uni,
Ou vn
Wh (t' (ar) 0
mm
Σ
Tbb,
w
Wh (t' (x') 0
vn
nin
Ou vm
Uni, ob
0
Ein
ogb,
Uni
= 0.
vm
For the non-zero terms we have
m (abb, obb) = ob
0- (ær, x.,))
yin
On m
Uwi
Ou Ux'y Vm
m
which can be achieved by straight forward computation. If t * 1 and t' o 1, by using the forth rule in (28) we have
ow Wh (t-1)))) Ow Wh (C' (2')) Vn
[o(z))((22] = V (K(h)) (xx x')
5
E
With K(lit" x²) defined in 16). Otherwise, it will be zero by the fifth rule (if t or oor==1l 1). introduced
Here the
G-vars is (x)), Un ) (g (a'), Ux 11 (x))))))). (())))))) (x')). but the dependency is only the last layer G-vars, plgg g E G)) = (t-1)) @(((g g G))) = leading the calculation to the operator defined (TO). As result
of previously
o (I) x/) + of
Σ (x. x') 2 V K
(x, x')
m
To complete the recursive formula, using the same procedure for the first layers we have
y (1.1) (x, x²) ot (a==²) +
(0), oz.
m
02
((1' (x, x') (2,
(1), xx)²) + o
m
2
(tt1))) x²) =
(1 a1) + of.
m
The output GP kernel is calculated via
K(æ,, x') = of Vo (T++T+++ +1) (x,,
The calculation of the gradient vectors (z())x)) = VT(( (ol(zr) in the backward pass is given by
(()) = 0. T e (0)) (x) = ow W
@ (z)
t T - 1]
vn
To calculate the backward pass kernels, we rely on the following Corollary from Yang 2020b)
17

---

Published as a conference paper at ICLR 2021
Corollary In infinitely wide neural networks weights used in calculation of back propagation gradients (W ) is an i..d copy of weights used in forward propagation (W) as long as the last layer weight (v) is sampled independently from other parameters and has mean 0.
The immediate result Corollary is that g (ar) and (a)) are two independent Gaussian vector their covariance is zero based on the fifth rule in 28 Using this result, we have:
IT(C.)) (2, x²) = 5 (x)) (x))
10 (x))
18 (x')):
La ( (x))l 10 (x)); (6'( (x'))) 18 (xx (z')ls)
= =
E s.N(0.K
(d((z) 0 (zz)) E [z)+ 10l1' (x')),
(m,er))
Vo ((+,) +1)
(x, x') (z,
T - t' = T t, then the the formula will lead to
11 (TT (xx x²) E [0 (z'))
of [b]:
[b], 1d "" (2'))) (a))))
[ (g
E [[)] [m]]]
= V [ ( (x. (x.x')]
Otherwise it will end to either of two cases for some < or and by the fifth rule in 28 we
have:
Σ ((())) (ar). 8 (()) =
T (t
WT
8lr ()())))) o' (T))
Vn
Σ
((()) (x), 8(t") (z))
E
1 o (z)):
w (f'(g"")
8th +1) 0.
vn
Without loss of generality, from now on assume T < T and T - T = r, the final formula for computing the backward gradients becomes:
(xx, (x) N(TT++)
VfV K ((T+1I+++1) (x, (,,
(1 (2,x²) = oa Ve
K (1++11+++)
(x, x') (241)
t T -
I('l (2,x)) =
t' t
Now we have derived the single layer RNTK. Recall that Vect[(We U, w}} contains all of the network's learnable parameters. As result, we have:
Vefe(z) = Vect { Oz((z) (f) (z)
(.)
dv }
dW 0U Øb
As result
Of((x) 0fa(x')
0f((z)
0fe
Of((z)
0fo(x')
(Vofo(z), Vofo(x)))
dw aw OU
0U
Ōb
@f((z)
0fo(x')
Ov dv
18

---

Published as a conference paper at ICLR 2021
Where the gradients of output with respect to weights can be formulated as the following compact
form:
0f((z)
Σ
(x))
(x))))()))
OW
vn
(=1
0f((z)
8(1)
(2)
(vm" Dt
ou
2U
vn
0f((z)
Σ
Tb
(())
(())))) (z))
0b
vn
ff((z)
0
(z)).
Ov
As result we have:
0S((z)
(so(
(x)), 800) (00)))
( (x), 1/ (00))
n
OW
dW
t=
0f((z)
afo(z') OU
T
(x). (x).
(21))
o. xbv) a'p))
(I
OU
t=1
@f((w)) 0l0(dd)
(2t), 500) 8(2 of (80) (ot),
Ub Ub
0S((z²) o n (T) (x)), (x), (TTT
dv
dv
Remember that for any two G-var E [[]] [g'ss]] is independent of index i. Therefore,
13 ((')))
V (z,
t>1
h 0 (x),
h
oh
Hence, by summing the above terms in the widtt limit we get
T
(4.0 (2, (x') x²)) + x').
(Vofolx), Vofolz)) vofo(a²))
+
(32)
Since 11(.00 x') = 0 for 1' - T is simplified to
T
(Vafo(z), Vofo(z)) = Σ 11t++)(( x')
silhet (a', xd)) + x')
Multi-dimensional output. For fa(x) E Rd the i-th output for i [d] is obtained via
[fo(x)],
Vn u h (x))
where vi is independent of vy for # j. As result, for The RNTK O( x²) e IRdd for multi- dimensional output we have
( x )k = (f([))),, , Vo Vo (fo('')),
For = j. the kernel is the same as computed in 332 and we denote as
(Vo [fo(=)); Vo (f(() (2))))))) (T,T") (z. (x, x').
19

---

Published as a conference paper at ICLR 2021
For * j, since vs is independent of vy. II (x, x') and all the backward pass gradients become zero, so
Vo [fa())), Ve [Fo(2')), 0 ifj
which gives us the following formula
( x²) (T.T) (a. x') @ la.
This concludes the proof for Theorem 1 for single-layer case.
B.3 PROOF FOR THEOREM 1: MULTI-LAYER CASE
Now we drive the RNTK for multi-layer RNTK. We will only study single output case and the generalization multi-dimensional case is identical the single layer case. The set of equations for calculation of the output of a L-layer RNN for œ = (xx )
are
of U xz + t
g (.0 (x)
(x)
t=1
vn
vm
d'
(x) + of
g
1.0 (x)
w(0 (c.-11))
110 (z) + ob
{> 1
Vn
h (1.0 (x) = o (x)
so(x)) = ou
vn
The forward pass kernels for the first layer is the same as calculated B.2 For E 2 we have:
(2, x') E(g E(g(t (2). (1,t)) (x)))
(x). w (0 (C.'
= Σ
+ Σ
U h
U
+ W (()+()))))(a))))
of
vn
( K (((l),)))) (r., x')]
(o 2 ( (x(- (ax, x''} + (ot)
where
(x, D( (2,
K (((,,))) (x, x²) = ((0.--),'-))(x E - (xt x¹)
and Inn defined in B.2 For the first first time step we have:
E(41))) (2, x') ( oo (a=x)) + VV K (1.222)
(x, x') + (ot))
((G.))) (z, x') = (o [ (x(4441)) (x.
(o/)
(a. 1.611.))
= vV (K(2222(+1) (x,, x')] + (af)²
And the output layer
K(x,, x²) = [ ( (x, x a')]
Note that because using new weights at each layer we get
(2.0 (x)
(x)) =
l l E'
Now we calculate the backward pass kernels in multi-layer RNTK. The gradients at the last layer is calculated via
8(L.3) (x) = v o 8' l'(g" (L.T) (x))))))))))
In the last hidden layer for different time steps we have
of vn (wil)) T (d'(g(..0 @ (())+11(2))
(z).
t [T -1
20

---

Published as a conference paper at ICLR 2021
In the last time step for different hidden layers we have
ou f+1 (DietT)) (d'()()(())) @ (())) (()
8 (
(z)
lE -1] 1]
Vnn
At the end for the other layers we have
vn (z) (wie))
of
(d(g(((0())) (())+1)()))
+ o+t1 Vn (ui-n)) (o'gg (x)) (z))
& EE 11, -1]
The recursive formula for the IT (xx, x²) is the same as the single layer, and it is non-zero for - - = т. As a result we have
11 (x, 2') = V. [ [K (x, x')
I xx, = Vv [K (x. x') 11 (1(A (x,x²)=
x') E [T- - 1]
t' t (33)
Similarly by using the same course of arguments used in the single layer setting, for the last time step have (1 (a, x') = (o or [K
[K(1+11++))]]] x') ((
(x, (x) l [
For the other layers we have
( x²) (V [K (1 x²) (( (ax, x')
+ (oft1) a K ((x4t144++) (x, x')
11(+1+++++ (z, x').
For 1' - 1 + T the recursion continues until reaches ITL.TT")) xx, I TT) (x, x'),"" 1" <T and as a result based on (33 we get
T" or
(T (ar, x²)
(34)
For L' - 1= r it leads to (TL,TT)) (ær, .²) and has non-zero value.
Now we derive RNTK for multi-layer:
0fo(z) 0fo(z')
ff((z) 0fo(z')
(Vofo(x), Vofo(z')) Σ
OW ow()
aU 200
(f((z)
0f((z))
@f((w)
0fe(z')
ab
ab0 Ov
Ov
E=1
where 0f((z) 0se(x')
T T
(x).))(x))) (x)))
(o (n (e1-1))
OW()) Ow
n
0.(())
0so(a')
T"
(((.)) (z). (d)))
(ot))
26)
1=1
(0
m
T
0f((z) 0fo(z')
8 ((11)) (z)) (
(ot))
(11.))))))) (--)))))))
t>1
n
0f((z) 0f((z')
T
(2). (of)
ab() abC)
(z)(z) 0.(((²)) o (1)
On
Ov
n
21

---

Published as a conference paper at ICLR 2021
Summing up all the terms and replacing the inner product of vectors with their expectations we get
= = (L,T,TT)
ΣΣΣ I1 1 - (x) (x, + K(<x, x²).
By 34 we can simplify
(LLTTT)
y(tu4 m ( (2..t))))(ttt)) (2) (((xx
For multi-dimmensioal output it becomes
(ax, æ²) (1.T.T)) (axx') x²) & la.
This concludes the proof for Theorem 1 for the multi-layer case.
B.4 PROOF FOR THEOREM 3: WEIGHT-UNTIED RNTK
The architecture of weight-untied single layer RNN is
(x) Vm
h + Tu
U( + ozb
vn
h 00 (a:) & (g
fo(x)) = vn"
h (x))
Where we use new weights at each time step and we index it by time. Like previous sections, we first derive the forward pass kernels for two same length data æ {xt) {x )7
(( (x, x') = ou.. V [K (1.) (a, x')] + on (xx x²) + oz.
=
ELt (x, (x,
#
Since using same weight at the same time step. (t.0 x') can be written function of the previous kernel, which is exactly as the weight-tied RNN. However for different length, it becomes zero consequence of using different weights, unlike weight-tied which has non-zero value. The kernel of the first time step and output is also the same as weight-tied RNN, For the gradients we have:
((T) 0 G' (g (x))
80 (x)
ow (w(++))T (0(() ( ( (x)) LE [T -1]
For t' we have:
ob. Voy K (1+++++1) (x, x x'))11(441)44) xx) (1t.00 (z, x²)
(1(0)0 (x,x') V.V K (T-+1,4++
Due to using different weights for t + t', we can immediately conclude that [[(t,,'( x²) = This of calculation is exactly the same the weight-tied case when 7 T T 0.
Finally, with 0 Vect [((W()) U ((t) w}] we have
T
Of((z) 0fo(z')
T
0fo(x) 0fo(z')
(Vofo(x), vofo(x') = Σ
Ow owa)
OU
0f((z) 0fo(x')
Of((z) 0fo(m')
(b Ab( dv
dv
22

---

Published as a conference paper at ICLR 2021
with
(f((a)
Ofo(a')
1
(0
(x).
8(0(('))
860)
OW OW
71
n
(fo()) 0fo(a")
800 (2)).
(1 x/))
0000 000
(f((a) ff((a)
(00)
(2))
0b() @b(0)
n
ff((a) f
h (T (x)), (z)))
dv dv
As result we obtain
(Vofo(z). Vefo(z')) = (t-0)) (x,
x') (x, (f', ,0)) + Ni x'),
same as the weight-tied RNN when 0. This concludes the proof for Theorem 3.
B.5 ANALYTICAL FORMULA FOR Vo[K]
Ki
K3
For any positive definite matrix K
we have:
K3
K2
Φ ReLU (Cho Saul
2009)
VolK]
[c(TT - arccos(c)) + v1- VkiK2.
2m
1
V K
(x arccos(c)).
2x
where Ka/ KgKg
erf Neal 1995)
2
2Kg
V K
arcsin
π
((1 + 2K (1 + 2Kg)
V K
I (1 + 2K2)(1 + 2K2)
4Kg
C PROOF FOR THEOREM 2: RNTK CONVERGENCE AFTER TRAINING
To prove theorem 2 lipschitzness of the network Jacobian J(6, X) Vofo(x) E R. [ initialization.
the strategy used in (Lee al. 2019) which relies the the local
Definition The Jacobian of a neural network is local lipschitz at NTK initialization (6g ~ (O,
there is constant K > 0 foror every C such that
[|] < K [[](8,x) -(0 x))1F K[10 -81 Ø1'
V 0,0 B(0o. R)
where
B30 R) = 10: 110 01 R}.
Theorem Assume that the network Jacobian is local lipschitz with high probability and the empirical NTK of the network converges in probability at initialization and it is positive definite over the input set. For e O, there exists such that for n > N when applying gradient flow with
1) < 2 (Amin (0 X)) ) + Amax (0(X, (0) with probability at least (1 e) we have:
sup |10 Ball2
sup θ (X (o(X 0
Vn
Vn
Proof: See (Lee al. 2019
23

---

Published as a conference paper at ICLR 2021
Theorem holds for any network architecture and any cost function and it was used in (Lee et al. 2019) to show the stability of NTK for MLP during training.
Here extend the results for RNTK by proving that the Jacobian of a multi-layer RNN under NTK initialization local lipschitz with high probability.
To prove it, first, we prove that for any two points 8, 0 E B(U,, R) there exists constant K such that
|| (2))
18 (a) |2 S Kivn
(a))
(35)
(1.) (x) g (5. (2, || (x) - (( (x) = ||0 `1 - Kivn - Ø||
(36)
To prove (35) and 36 we use the following lemmas
Let A E m be random matrix whose entries are independent standard normal random variables. Then for everyt 2 O, with probability at least - cl-ett) for some constant have:
Lemma
|| I m + vn +t.
Lemma 2
Let E Rn be a random vector whose entries are independent standard normal random variables. Then for every 2 0, with probability at least 1 - e(-ctt) for some constant we have:
||l|| S Vt.
Setting / = v for any 0 E R(0o: R). With high probability, get:
|| 12, | s syn,
| S 2yn, || (2((2) S 20, nn
We also assume that there exists some finite constant C such that
(xxx)] < C|ac,, 16(x) <(a') < C| - - [d'(x)) < CC 110(x)) - 2 (z') < Cl a'|-
The proof is obtained by induction. From now on assume that all inequalitics (35) and (36) holds with some l for the previous layers. We have
lgg (6.1) (2) = || of Vn
(x) + of U(() h (x)) + (1
(( (61- (((-1)
Vn
| (t) 1211 1211o (x)) ll2 + of 
ا (0)) lla + (
x (30 Ck 30 Ck + 20,) Vñ.
And the proof for 35 and
36 is completed by showing that the first layer is bounded
(x) lla
سي w (1.00
(
of 1/2
Vn
Vm
30
< (30 on +
| |l + 20.).n.
Vm
For the gradient of first layer we have
| (x) = 11 2 0 (T))
S o 00l1o||211o' (g (L,T) (x))l
= 2v.
And similarly we have
(18(()0) (x)) C3. 3k,, Vn.
See math. uci http:///...aaaaaa/////////////// proofs
24

---

Published as a conference paper at ICLR 2021
For 8,0 E B(Ob, R) we have
(x)) (a)11 -/ (W()
( (xx) o
(w (1.00
vn
Vm
3
1 30 30 +
| 12/ 110 01l2vn.
m
(x)) ||a|| ou (wl)) - Wl)
1g (zx) (x))l2
oh
w
12110( (x)) (x)))
+ |
(U 0(9)]
o1 ( lello( - (.
+
1.0) (x))ll
+ - 1
s (kot + -30 Ck + ko 30 + ob) 0ll2VT.
For gradients we have
(x) - (24.1) S 0..lo'(g((433)) (1 l1 6)112 (=.11)lbllo(()))+)))) 5'(g(4.T)xx))
S (a,C O 0llavn.
And similarly using same techniques have
(180))()) - g(e-:) (x)lla S (owC + Ck Ch)ll - 0ll2vn.
As result, there exists K₁ that function of ow o., Tb, L, T and the norm of the inputs. Now we prove the local Lipchitzness of the Jacobian
1 (x) (o (((h(ct-)(())))
[0 )) F 5
2= 1=1
8 (ax)) (21
1 /
(((,1) (a)) (m))
vn
1 (())))))) (2)))
72
F
|
(o.xx)
8(1.0) 811.0 (x) 0z [1)1 .b + on (x))))
+ vil
Fr
T
(K9Co' + K2CoL+offk
1=1
K1od
(RGCO +
vm | Ki) + coCKi)
25

---

Published as a conference paper at ICLR 2021
And for 0,0 0 E B(0u, R) we have
- (1)) (x)) -8)))())) (d(
[)(, 2(0 -
2=
(te:0
(
(x) (0(7())-11((0))
+
1
1
(o) (--)) (x) (a))
811.01
72
[011,t11( (o - (() (o)
8(2.00 (z) .of (()) (z)) (m) odoll ب (201)100)00) (2)) - 12 (4.30
(x=)l (x))lr
Vn
(Ki + 4KGCO + ok)
(=2
Ki0 vm
+
> CoK +
| - of k1) + o,CK, 110 - 8112-
The above proof can be generalized the entire dataset by straightforward application of the union bound. This concludes the proof for Theorem 2.
26


Reviews:
[{"review_id": "DHh3gCEavs5", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the NTK of RNNs in the infinite-width limit, and shows a number of interesting features of such networks, that are somehow surprising knowing the problems of exploding gradients, or knowing the need for independence of parameters in proofs involving the NTK (for the tied weights giving the same as the untied case). While the techniques are not particularly new (they are relying on the applciation of techniques appearing in earlier papers), and the idea to look at RNNs is fairly straightforward, I think this is an interesting and useful paper, with nontrivial estimates (that look correct, although I may need a bit more time to check). The quality of the writing is extremely high, the notations are optimal, and it is overall a pleasure to read, and this paper will serve as an excellent basis for future investigations.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6V1l0pBZjUD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends NTK to RNN to explain behavior of RNNs in overparametrized case. It’s a good extension study and interesting to see RNN with infinite-width limit converges to a kernel. The paper proves the same RNTK formula when the weights are shared and not shared. The proposed sensitivity for computationally friendly RNTK hyperparameter tuning is also insightful.\n\nWeakness:\n\nIn the experimental part, the paper claims they restrict the data with shorter and fewer samples. This may be a downside of the proposed method as the goal of RNNs is to handle various length of data samples. Also, it seems that the proposed RNTK cannot outperform other SOA methods. Any reason? Why are GRU and identity RNNs chosen? Please highlight the best number for each experiment for an easier comparison. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4OkzS-X4Flk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the neural tangent kernel for RNNs is derived. It is emphasized how this results in a proper kernel that can handle samples of different lengths.\n\nThe  theoretical derivations are correct to the best of my knowledge and help to complete the picture of deep architectures for which the NTK has been derived. This is a valuable contribution.\n\nMy main concern is on the empirical side. Since the sinusoid regression is a toy problem I'll focus on the other two:\n\n- Google stock price regression: Appendix A2 doesn't provide much insight into the experiment setup, but it seems that the objective is to predict the stock price of the next day based on the previous ones. I would assume that a strong baseline for this task will be to simply predict the stock price to be the same as the previous day. This is a trivial predictor that requires a training set size of zero. So if you were to plot its performance on Figs 4c and 4d, which (constant) SNR would it yield? I'd be surprised if it is beaten (and that would be a very interesting result), but also I'd be surprised if it's not matched (seems a simple enough predictor to discover if there is no overfitting). However, those graphs show a big spread between different predictors, which is not intuitive given the previous sentences. Can you pleaser report the SNR of \"my\" trivial predictor and explain the apparent discrepancy?\n\n- The 53 UCR classification datasets: Why those 53? The database contains 128, and your paper states that you took \"data sets with fewer than 1000 training samples and fewer than 1000 time steps\". But datasets \"Adiac\" and \"Beef\" fulfill those requirements and were not taken. On the other hand, \"StarLightCurves\" doesn't seem to fulfill them (1024 steps) and yet you took it. Can you clearly state how you chose those 53 datasets out of the 128 available?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agreed on the value of theoretical contribution, especially the surprising conclusion that the weight-tied and untied RNTK are identical. The empirical results were updated in response to reviewer's suggestion. I believe this would be of interest to ICLR audience.
Decision: Accept (Poster)