Understanding Generalization in Recurrent Neural Networks
Authors: Zhuozhuo Tu
Fengxiang He
Dacheng Tao
Venue:  (2020)
Keywords: generalization
recurrent neural networks
learning theory

Abstract: In this work, we develop the theory for analyzing the generalization performance of recurrent neural networks. We first present a new generalization bound for recurrent neural networks based on matrix 1-norm and Fisher-Rao norm. The definition of Fisher-Rao norm relies on a structural lemma about the gradient of RNNs. This new generalization bound assumes that the covariance matrix of the input data is positive definite, which might limit its use in practice. To address this issue, we propose to add random noise to the input data and prove a generalization bound for training with random noise, which is an extension of the former one. Compared with existing results, our generalization bounds have no explicit dependency on the size of networks. We also discover that Fisher-Rao norm for RNNs can be interpreted as a measure of gradient, and incorporating this gradient measure not only can tighten the bound, but allows us to build a relationship between generalization and trainability. Based on the bound, we theoretically analyze the effect of covariance of features on generalization of RNNs and discuss how weight decay and gradient clipping in the training can help improve generalization. 

Published as a conference paper at ICLR 2020
UNDERSTANDING GENERALIZATION IN RECURRENT NEURAL NETWORKS
Zhuozhuo Tu, Fengxiang He, Dacheng Tao
UBTECH Sydney Al Centre, School of Computer Science, Faculty of Engineering The University of Sydney Darlington, NSW 2008, Australia zhtu3055@uni sydney. edu.au, au, (fengxiang he, dacheng. wawheng..aaoeesydneeeee..ee taoddsyy
edu, au
ABSTRACT
In this work, we develop the theory for analyzing the generalization performance of recurrent neural networks. We first present new generalization bound for recurrent neural networks based on matrix I-norm and Fisher-Rao norm. The definition of Fisher-Rao norm relies RNNs. This new generalization bound assumes that the covariance matrix of the input data is positive definite, which might limit its use in practice. To address this issue, we propose to add random noise to the input data and prove a generalization bound for training with random noise, which is an extension of the former one. Compared with existing results, our generalization bounds have no explicit depen- dency on the size of networks. We also discover that Fisher-Raa norm for RNNs can be interpreted sure not only can tighten the bound, but allows us build relationship between generalization and trainability. Based on the bound, we theoretically analyze the effect covariance of features on generalization of RNNS and discuss how weight decay and gradient clipping in the training can help improve generalization.
structural lemma about the gradient of
measure of gradient, and incorporating this gradient mea-
INTRODUCTION
The Recurrent Neural network (RNN) is a neural sequence model that has achieved the state-of- the-art performance on numerous tasks, including natural language processing (Yang et al. 2018 Mikolov & Zweig 2012), speech recognition (Chiu et al.) 2018 Graves 2013) and machine transla- tion (Wu et al. 2016 Kalchbrenner & Blunsom 2013). Unlike feedforward neural networks, RNNs allow connections among hidden units associated with time delay. Through these connections, RNNs can maintain a "memory" that summarizes the past sequence of inputs, enabling it to capture correlations between temporally distant events in the data.
RNNs are very powerful, and empirical studies have shown that they have a very good generaliza- tion property. For example, Graves (203)) showed that deep LSTM RNNs achieved test error of 17.7% on TIMT phoneme recognition benchmark after training with only 462 speech samples. Despite of the popularity of RNNs in practice, their theory is still not well understood. A number of recent works have sought to shed light on the effective representational properties of recurrent networks trained in practice. For example, Oymak (018)) studied the state equation of recurrent neural networks and showed that SGD can efficiently learn the unknown dynamics from few obser- vations under proper assumptions. Miller & Hardt (0119) tried to explain why feed-forward neural networks are competitive with recurrent networks in practice. They identified stability as necessary condition and proved that stable recurrent neural networks are well approximated by ferd-forward networks for the purpose of both inference and training by gradient descent. Despite of the impres- sive progress understanding the training behavior of RNNs, there no generalization guarantee in these works.
Understanding the generalization performance in machine learning has been a central problem for many years and revived in recent years with the advent of deep learning. One classical approach to proving generalization bound is via notions of complexity. For deep neural networks, numer- complexity measures have been proposed to capture the generalization behavior such VC

---

Published as a conference paper at ICLR 2020
dimension (Harvey al. 2017) and norm- based capacity including spectral norm (Bartlett al.
2017 Neyshabur et al. 2019), Frobenius norm (Neyshabur et al. 20155 a: 2018) and 1y- norm (Neyshauur et al. 2015b; Bartlett & Mendelson 2002; Golowich al. 2018). These existing norm- based complexity measures depend on the number of hidden units of the network explicitly and thus can not explain why neural networks generalize well in practice, despite that they operate in an overparametrized setting (Zhang et al., (017). Neyshabur et al. (2019) proved generalization bounds for two layer ReLU feedforward networks, which decreased with the increasing number of hidden unit in the network. However their results only applied to two layer ReLU networks and some specific experiments. More recently, new generalization bound based on Fisher- Rao norm was proposed (Liang et al. (017)) This notion of Fisher-Rao norm is motivated by information geometry and has good invariance properties. But they proved the bound only for linear deep neural networks. There are also some works about the generalization of recurrent neural networks (Zhang) ctt al., 2018; Chen et al. 2019; Allen-Zhu & Li, 2019). However these bounds also depend on the size of networks, which makes them vacuous for very large neural networks.
Our main contributions are summarized as follows.
We define the Fisher-Rao norm for RNNs based on its gradient structure and derive new Rademacher complexity bound and generalization bound for recurrent neural networks based on Fisher- norm and matrix 1-norm. contrast to existing results such as spec- tral norm-based bounds, our bound has no explicit dependence on the size of networks.
We prove a generalization bound for RNNs when training with random noises. Our bound applies to general types of noises and can potentially explain the effect of noise training on generalization of recurrent neural networks as demonstrated by our empirical results.
We propose new technique to decompose RNNs with ReL. activation into a sum of linear network and difference terms. As a result, each term in the decomposition can be treated independently and easily when estimating the Rademacher complexity. This decomposi- tion technique can potentially be applied other neural networks architectures such as convolutional neural networks, which might be of independent interest.
The remainder of this paper is structured as follows. We define the problem and notations in Sec- tion[2 The notion of Fisher-Rao norm for RNNs introduced in Section We prove the general- ization bound for RNNs in Section 3.2, and the generalization bound for training with random noise derived in Section 3.3 Section 3.4 gives detailed analysis of our generalization bound. Finally we conclude and discuss future directions.
2 PRELIMINARIES
We focus on the vanilla RNNs with ReLU activation. Let U E Rmxd V E Rkxm and W E Rmxm be the weight matrices. Given the input sequence x = (I1, ,,,)) E Rid where each 2; Rd and L is the input sequence length, the vanilla RNNs can be described as follows.
gt Ux. + Wht-1,
ht p(g:). Vt = Vh+
where St and hy E 1tth represents the input and output of hidden layer at step 1, p(-) is the ReLU function and yt E R2* denotes the output value at step L.
For simplicity, in this paper, we only consider the final output yz. We assume that data (x, v) is drawn d. from some unknown distribution over RLd x y where y represents the label space 21, ... .J. The RNNs above define mapping yı (x) from RLd - R& where k is the number of classes We convert yr (x) to a classifier by selecting the output coordinate with the largest magnitude, meaning
x - (rrmax((yr..))).
where I:1e represents the i-th element of a vector. This naturally leads to the definition of margin Myr (I. y) of the output y7 labeled example (x,y):
Myn (s., v) [wz. (2))l max(vz(<)])
2

---

The generalization error then the difference between expected risk and empirical risk, defined as Published as a conference paper at ICLR 2020
Thus, yr misclassifies (z, y) if and only if Myr br. (a, y) - 0. The quality of the prediction made by yz is measured by the expected risk defined as
E (aa)) May (mw)sal-
Since the underlying distribution D is unknown to us, we instead consider the empirical error on sample data given by
Σ [1 Ma (m.)))a))
B(z.g)>DlLM, (2.)) (1 (n.v)aa)
Our goal in this paper is study the generalization error for RNNs theoretically.
To establish the generalization bound, a little bit of notations are necessary. For a vector, we denote Ip norm by ||||p (E /o//)///p and the Loo norm by ||o||so = max Juil- For matrix, we denote the matrix p-norm as ||Al|p = = Axllpp the matrix 1-norm by (rrae(AA")) The smallest eigen-
||A||] max, {Ei |ayy] and the Frobenius norm by ||- value of matrix A is given by Amin(A) The actívation function and its derivative of are entry- wise, i.e., p(A) = (p(a,))), )sg and p'(o) (p' (v;)), We denote c c= (L+ 1, L.... 2)T n(() (1L))("(9L)))...) (..))..WWer. Wid.g....ig//.... (iag(()(g2)))zz)) ... VVdaag (gL)) Uni] E R and (0) (VWL-UUn, VW V VUxr.) where = (U, W, V) and
[V [Vdiag(p' ((l(p((g))))..11
di [=),) Cioi,,Viinn Vdiag(p'
diag converts vector into diagonal matrix.
MAIN RESULT
In this section, we prove a generalization bound for RNNs with ReLU activation. Our new bound is based on Fisher-Rao norm and matrix 1-norm. We first define the Fisher-Re Rao norm for RNNs.
3.1 FISHER-RAC NORM FOR RNNS
We adapt the notion of Fisher Rao norm to recurrent neural networks. To begin with, we establish the following structural result for RNNs.
Lemma 1. Given an input x have the identity
(æ F2 ... IL), consider the recurrent neural network in 7 we
OyL
dyL
duL Jupg
Wij Dwsj
Upg 1)(c).
Dvab
a.b
The notion of Fisher-Ras Rao norm is motivated by Fisher Rao metric of information geometry and is defined as follows.
Definition ((Liang et al. 2017). Definition 2). The Fisher-Rao norm for a parameter is defined as
||0|,, :<< 0, T(0)0 >,
where I(0) = EVV((yy) & VI(gLo(z). y)) and ((...) is the loss function.
The following lemma gives the explicit formula of Fisher-Rau norm in RNNs. We can see that the notion of Fisher-Ran Rao norm relies mainly on the gradient structure of RNNs.
Lemma 2. Assume that the loss function ((.,.) .) is smooth in the first argument. Then the following identity holds for the RNN in I
|1013, E((n(0),, AVyLo(z).
dULO

---

Published as a conference paper at ICLR 2020
in 17(0) is actually the gradient component in Backpropagation through time (BPTT). Therefore, the Fisher-Rac Rao norm can be regarded as measure of gradient. As will be shown later, build relationship between generalization and trainability in RNNs via Fisher-Rao norm.
Remark 1. We observe that each term Vdiag(p' ((LL))(((g))))....
For the linear activation function and margin loss (()Lo()), y) (a (s, v)) where a: 0 is the margin parameter, one might upper bound the Fisher- Rao norm in Lemma by
4 110 Pr I a
E( B(max((+(())))))
since (T(0)c, ())) )²
* max; ((T)cc) by definition of My (2, and lipschitz
OyLs
property of (-). We define this upper bound as
|1013 := E (max((((0)))))))
(2)
and still call it "Fisher-Rae norm" in the paper by slightly abusing the terminology as they are equivalent for k = 1. In the rest of the paper, we will use this Fisher-Rao norm Ilfs to derive generalization bound for RNNs.
3.2 GENERALIZATION BOUND FOR RNNS
We use matrix 1-norm and Fish-Rao norm together to derive a generalization bound for RNNs. Since is very challenging to bound the Radermacher complexity of ReLU networks directly in terms of the Fisher-Rao norm, consider decomposing the ReLU network into the sum of linear network and a difference term, i.e., YL (f())z + (yz - (f))x)) For the linear network part (6)xz, the Rademacher complexity can be bounded directly by Fisher-Rao norm. For the difference term (y1, - (0)x)), we further decompose it into a sum of simpler terms and then upper bound the Rademacher complexity of these simpler terms by matrix 1-norm. We first give the results for the linear network part.
r, E V} where E RLLd and (0) (VWL-IU, VWL-2U,... VU). For any data æ1, ,2, .2. Fn drawn i.dd from the distribution DD collect them as columns of a matrix E RLaxn, Then we have
Lemma 3. Define F, fo + [+(0)=]y 110
1||
R (F.)
2n
V
AAmin (B(xx"
assuming that B(xx") positive definite.
Remark 2. If E(x) 0, E(az²) is the covariance matrix of random variable x.
Remark We should mention that our assumption that E(xz") is positive definite is not so restric- tive and usually holds in practice. For example, for the case that x is continuous random variable, can prove that E(zx") is positive definite as follows. Suppose that æ is continuous random variable in the n-dimensional subspace X C R". If there exists E R" such that u" E(xx") O, then for any E X we have uT 0, i.e., 1 X. Since is n-dimensional. the only that satisfies is that u = 0. Therefore, by definition, E(xa²") is positive definite. As will show Section 3.3 this assumption can be removed, and a more general generalization bound will be presented.
Now we bound the Rademacher complexity of the difference term yr - (f)x.. With a slight abuse of notations, given input data 22, , F. R!dd, the corresponding 91. ... Ih E RLm and h1, h2, ... hn E Rlmm are calculated by (1}. We collect all input data as a matrix denoted by matrix denoted by Xt, all input of the hidden layer at time
X, all input data at time matrix denoted by G, and all output of hidden layer at time & denoted by H. where X e Rldxx.
X. Rdxn G, E Ruxx H. E Ruxn and I..... L. The difference term can be decomposed by the following lemma.
Lemma 4. Define H" = H. Gr. Then the following equality holds
VH, (0)x = Σ VWL-
1=1
4

---

Published as a conference paper at ICLR 2020
To bound the Rademacher complexity of each term in the above decomposition, need technical lemma given as follows.
Lemma 5. For any p || Ip m (o----111c Geell
As we will see, the operator norm in Lemma 5 will be instantiated for the case of 1. The use of || II helps avoid the appearance of the dimension m when upper bounding the Rademacher complexity. Also it guarantees that Rademacher complexity has a convergence rate (1)nn). The upper bound for the Rademacher complexity of these individual term is given by the following lemma.
Lemma 6. Let Q == {0 (U,W,V) || s Bv, 11, S 3w, 100110 S Br Then for any 1. L, we have
Eg sup BELLEENn
1 n -V ", S By
Σ 2 1l1.
j=1
where a (0), "2 ,n))² is Rademacher random variable and Fly, represents the y-th row of the matrix.
We now ready put the ingredients together to prove our first theorem.
Theorem 1 (Rademacher complexity of RNNs). Let Ω 10 (U.W.V)
|[V S
3v, [ S Sw, ||0*||| S Br, ||0] fs S r]. Then, the empirical Rademacher complexity of RNNs with ReLU can be bounded as follows
1
x11
E. sup oEflyyy
(ULI
2n V Amin (((xT)) + Br Br
- Blv Bw
where A 1-Bw
LBW) if Bw and A L+L" for Bw =
To establish the generalization bound for RNNs, we need the following classical results for multi- class margin bounds.
Lemma 7 (uzneetsov al. 2015). Theorem 2). Let H C RXXY be hypothesis set with ) 21, ,k.. Fix a > O. Then, for any > O, with probability at least the following multi-class classification generalization bound holds for all h H:
4k R. (H)) + +31
logg
o La (M R(h)= < Σ
2n
1=1
where I1, {x ((x v) y V, H}.
The generalization bound for RNNs follows from combining Theorem and Lemma
Theorem 2. Fix margin parameter a, then for any 8 > 0, with probability least the follow- ing holds for every RNN whose weight matrices 0 = (U, W, V) satisfy [|VT|| I Sy. || $ Bw. wwT. & By and |0l|ss Sr:
1
4k
E M,, (a.))so S
Σ 1l My, (ana)aa +
(
+ - 3 (1 n
n
a 2n
V Ammin(E(xx
logg
31
2n
Comparison with existing results. We compare our result with the existing generalization bounds /Zhang et al. 2018 Chen al. 2019). In comparison with the bound in Zhang al. (2018). which
is of the order Ō max d, m, k I |12|||V max (1, [[W]))), ), there is explicit appearance of Vna
the network size parameters and m in our bound. As we have mentioned before, the reason that avoid these dimensional factors is that matrix 1 1-norm instead of spectral norm to
5

---

Published as a conference paper at ICLR 2020
upper bound the Rademacher complexity of the network. Moreover, there is always L factor in their bound, whereas the L term only occurs in our bound when || = 1. For the case that ||""|| > 1, our bound has only linear dependence simple calculation, we can show that A S (I-Pw>² and the dependence on I. would vanish. Both
L, and for the case that || < 1, by
of our bounds have an exponential term |[W]]", which would make the bounds become vacuous for || > 1. It should also be pointed out that our bound scales linearly with the number of classes since we handle multiclass on each coordinate of a k-tuple of functions and pay a factor of k. Chen et al.] (2019) also derived generalization bound for RNNs in terms of spectral norm and the total number of parameters of the network by using covering number analysis. Since their work assumed that the activation function in the hidden layers was bounded rather than the ReLU activation function considered in our paper, their bound is not directly comparable to ours, and we do not make a comparison here due to the page limit. We should emphasis that our proof technique is totally different from the PAC-Bayes approach (Zhang et al. 2018) and covering number analysis (Chen et al.] 2019). In particular, we work on the Rademacher complexity of RNNs directly with no invocation of complicated tools such as covering number, which makes our analysis conceptually much simpler. There also an additional bonus of our proof technique. In the next section, we will use this proof technique to derive generalization bound for RNNs when training with random noise.
3.3 GENERALIZATION BOUND FOR TRAINING WITH RANDOM NOISE
The generalization bound in Theorem 2 requires the input covariance matrix E(az²) to be positive definite and would become very poor when the smallest eigenvalue is close to O, which greatly limits the power of our bound. To address this issue, we consider adding random noise to the input data. We notice that after adding random noise with mean 0 and variance o², the term E(xx") in the bound becomes B((x + c)(2 + c)") and the smallest eigenvalue of B((x c)(x + e) is (Amin (B(x=²") )) + )²),, which is greater than o² Therefore, our bound is still applicable even when the covariance matrix of original input data is rank-deficient. Involving noise variables has been widely used in recurrent neural networks as a regularization technique (Bayer et al. 2013 Zaremba cet al., 20144] Dieng et al.) 2018 Gal & Ghahramani] 2016).. For example.| (Bayer et al. (2013 claimed that conventional dropout did not work well with RNNs because the recurrence amplified noise, which in turn hurt learning. To fix this problem, Zaremba et al. (2014) proposed to inject noise only to the input and output of RNNs. Although their method greatly reduced overfitting on a variety of tasks, the generalization guarantee was not provided. In this section, we present a generalization bound for RNNs with noise training. For simplicity, we assume that the noise is drawn i.i.d. from a Gaussian distribution with zero mean and variance o². Let e, denotes the d-dimensional gaussian (21, ,LL E RR.d. We collect all noise data as matrix
noise generated at step i and denoted by X,, To prove the generalization bound, we need to use the Lipschitz property of RNNs given by the following lemma.
Lemma 8. For every RNN in 7 with weight matrices 0- = (U, W, V), UL is Lipschitz with respect to || oloor i.e.
(1))(x) - yr vr((')) S C1I |1 =1/1000
for any x == (z1, 02, ,LL) = (41, 26, ,x1)) E R
The generalization bound for training with random noise is described as follows.
Theorem 3. Fix margin parameter a, then for any 8 > O. with probability at least 8 over sample ((x1, c,. V1). (I2, <2, V2). .......... (Z.,,..,, Eni vn)). the followinn holds for every RNN whose weight
matrices 0- = (U, W, V) satisfy |T S By, ||WT 1|1 S 33w, 1w.11UT111 S 3r and [|0||s rr:
1 Σ
Da yy (zi + ei, ei) + 2 E, By Br B / log((d) + +31
log
E Mag (o)
2n
4k
X
+ XellF
1
Bv xT + X?
2n
Xmin (B(xx²)) + o?
Remark 4. The above bound can be easily extended to other kinds of noises by replacing G. 2.v2 (og(2d) by E, leilloo.

---

Published as a conference paper at ICLR 2020
Remark 5. The bound in Theorem is extension of that in Theorem 2 and can be ap- plied even when the smallest eigenvalue of E(zr") is very close to O. For example, when Amia (Bixx"(
10 applying Theorem 2 directly might lead to vacuous bound. But using Theorem 3 by choosing small noise with mean and variance 0.01, we might obtain a better bound since the term Amiin M++?? S 10. Notice that adding noise can not always guarantee an improved generalization especially when Amin (B((x=") not so small as it incurs aL o. 2lgg(22 and might also increase other parameters
an additional linear term 2 Σ; By Pw
in the bound such as || + XellF. Therefore we suggest adding noise only when the smallest eigenvalue of [xxx"" very small. For this case, a small noise such as o. = 0.1 not only can
Amin (E(xx")) but also ensure that the extra cost or /2lgg(()) and ||X X.lle/n n be small enough since ||X Xelle/n I ||X||=/n ||XellF/n and ||xell=/N would be small when n is large.
greatly improve the term
Remark 6. If remove the constraint condition ||0||s < r, which means that do not have any knowledge about the gradients, the generalization bound in Theorem and Theorem
still holds by substituting with By 1. But with this extra gradient measure, the bound can become much tighter, especially when Amin (B(xx") is small. Please refer to the detailed analysis in the next section. Experiments. We now study the effect of ran- dom noise generalization of RNNs empir- ically. For simplicity, we consider the IMDB dataset, collection of 50K movie reviews for binary sentiment classification. We use GloVe word embedding to map each word a 50-
+ I-3 for Bw
generaiteelion error
dimensional vector. We train vanilla RNNs
with ReLU activation function for sequence length L = 100. The corresponding smallest eigenvalue of BB(x=") is approximated by us- ing the total training data, which is 4 x 10-1
2.40%
1.20%
We add Gaussian noise to the input data in the training process with σe 0.1, 0.2, 0.3 and 0.4. The generalization error which is the gap between test error with noise for L = 100 and different val- of a, shown in Figure (results for other values of L in Appendix D We observe that as we start injecting noise, the generalization eтror becomes better. But when the deviation of noise keeps growing, the generalization error shows an increasing tendency. This behavior is consistent with the prediction made by our bound.
1.00%
0.2
0.2 deviation
without noise and training
Figure Generalization error for training with noise (mean + standard error averaged on 5 runs).
3.4 ANALYSIS OF GENERALIZATION BOUND
Our theoretical results have number of implications for the generalization performance in RNNs, and some of them have been observed in empirical studies. We summarize these implications as follows.
3.4.1 GENERALIZATION AND SMALLEST EIGENVALUE OF E(xx")
According to our results, the generalization performance in RNNs is influenced by the smallest eigenvalue of E(zz"). Since the smaller eigenvalues may contribute to high frequency components of the input signal, our bound suggests that high frequency information is potentially more difficult to generalize, which is consistent with intuition. There are many factors that impact on the smallest eigenvalue and therefore the generalization performance in RNNs. In particular, we study the effect of the correlation between features on the generalization RNNs. The exact answer for this problem may be complicated. Here we only make initial attempt and claim that weaker correlation would

---

Published as a conference paper at ICLR 2020
help improve the generalization, and non-rigorous proof is given follows. Denote the covariance matrix E(xx") by E where each element Eıj in E represents the covariance between feature and j. Suppose that || - 1| < with Ç < 1. By definition of || 1h matrix norm, we immediately get Kan [aa-11 1| + Σ jæ Exy S ( for any i. Then by simple derivation, we obtain Çi Σnzt |Siy 2 for any i. Applying Gershgorin circle theorem, we have that the smallest eigenvalue must be greater equal than -- Since the element Eúj with * j represents the covariance between feature i and j. a weaker correlation between feature and j means a smaller value of [Styl and we need a smaller ç to upper bound | /I1, which gives us a bigger lower bound the smallest eigenvalue. Therefore the generalization bound becomes better.
3.4.2 GENERALIZATION AND TRAINABILITY
The generalization of RNNs also depends on parameters Bu, Bv, .w and r, where fy, By and Sw control the weight matrices and represents the gradient measure. It has natural relationship with the training process. The normal procedure in training RNNs is to use weight decay for regulariza- tion and gradient clipping to avoid the exploding gradients problems (Bengio et al.. [994] Pascanu it al. 2013). From the perspective of generalization, these strategies can decrease the value of these parameters Bv, Bw and and thus improves the generalization. For example, if 3w S 1, we
1 have S (I- and the second term - - = in the generalization bound would be 71
small when Bw is not so close to 1. Similarly, if Amin (B(x=")) is very small, by setting the gra- dient clipping value in the training procedure, we can achieve smaller value of r and thus good generalization. Therefore our bound partially explains why training RNNs in this way can achieve good performance in practice.
3.4.3 GENERALIZATION AND GRADIENT MEASURE
We are interested in how the gradient measure contributes to generalization. Suppose now that only have the weights, i.e., the parameters By, Bw and By and the gradient measure parameterized by is unknown us. To apply our bound, natural idea is to infer the gradient measure parameter r based on the known weight parameters. An upper bound for r in terms of By, Bw and By is given as follows. Under the same conditions as Theorem 2. if we further assume that the data r be given with ||="|| S. B, by the definition of || ر/ in (2) for any y E V, we have
((T(0)))))
L. WL-2U/2 + +... 2V,), U22 S (I(L+ 1)[ b, 1L-1Uxi + LVV WL-2Uxg + +.... + [2[V]. Ju. 1x
((I. VV[V, y. WL-
((L+ By B + LBv By B 31;
(B B - + 2- ))² < (8v B [[- + 1- ))²
(I-Dw)
for 3w < L, and ((T(O))),)² S (3 B.,BBBaLLL )2 for Bw 1. The above inequality holds for any x and y. So we can get ||0l|,- E( E(max, (T (T))c). 1/2 S 3r BB B( + for 3w 1. By replacing with 3y B(TTkw + 1-9w)) the generalization bound (3) also holds. But notice that this bound is obtained without any knowledge about the gradients. we happen to know that the parameter r is much smaller than By 3y B B + T-Bw ). for example, by setting gradient clipping value to be small in training process, this extra gradient measure can provide us with a better generalization bound, especially when the smallest cigenvalue of ((xx"") is small. Therefore the introduction of Fisher-Rao norm can help eliminate the negative effect of Amin (E (ExxT) )) and thus improve the generalization bound.
Bw
4 CONCLUSION
In this paper, we propose a new generalization bound for RNNs in terms of matrix I-norm and Fisher-Rao norm, which has no explicit dependence on the size of networks. Based on the bound, we analyze the influence of covariance of features on generalization of RNNs and discuss how weight decay and gradient clipping in the training can help improve generalization. While our bound is useful for analyzing generalization performance of RNNs, it would become vacuous because of an exponential term when |W 1. It is of interest to get a tighter bound which can avoid this
8

---

Published as a conference paper at ICLR 2020
exponential dependence. Moreover, bound only applies to vanilla RNNs with ReLU activation, and extending the results to tangent and sigmoid activation functions or other variants of RNNs like LSTM and MGU might be interesting topic for future research.
ACKNOWLEDGMENTS
This work was supported by Australian Research Council Project FL.-17010017, 17. We would like to thank Gemeng Zhang from Tulane University for helpful discussions and all the reviewers for their constructive comments.
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in neural networks. arXiv preprint arXiv: 170.03677 2017.
Zeyuan Allen-Zhu and Yuanzhi Li. Can sgd learn recurrent neural networks with provable general- ization? arXiv preprint 1902.0108, 2019.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov)4463-48) 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalizee margin bounds for neural networks. Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Justin Bayer, Christian Osendorfer, Daniela Korhammer, Nutan Chen, Sebastian Urban, and Patrick van der Smagt. On fast dropout and its applicability recurrent networks. arXiv preprint arXiv:1311.001,, 2013.
Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
Minshuo Chen, Xingguo Li, Tuo Zhao. generalization bounds family of recurrent neural networks, 2019. URL
Chung-Cheng Chiu, Tara N Sainath, Yonghui Wu, Rohit Prabhavalkar, Patrick Nguyen, Zhifeng Chen, Anjuli Kannan, Ron Weiss, Kanishka Rao, Ekaterina Gonina, et al. Statc-of-the-at speech recognition with sequence-to-sequenee models. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4774 IEEE, 2018.
Adji Bousso Dieng, Rajesh Ranganath, Jaan Altosaar, and David Blei. Noisin: Unbiased regu- larization for recurrent neural networks. In International Conference on Machine Learning, pp- 1251-1260, 2018.
Yarin Gal and Zoubin Ghahramani. A theoretically grounded application of dropout in recurrent neural networks. Advances in neural information processing systems, pp- 1019-1027, 2016.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of
neural networks. In Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 297-299. PMLR, 2018
Alex Graves.
Generating sequences with recurrent neural networks.
arXiv preprint
10Xiv:1308.088 0850, 2013.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension bounds for piece- wise linear neural networks. In Conference on Learning Theory, pp. 1064-1068 2017.
Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. In Proceedings of the 2013 Conference on Empirical Methods Natural Language Processing, pp. 1700-1709, 2013.
Vitaly Kuznetsov, Mehryar Mohri, and U Syed. Rademacher complexity margin bounds for learning with a large number of classes. In ICML Workshop on Extreme Classification: Learning with a Very Large Number of Labels, 2015.

---

Published as a conference paper at ICLR 2020
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geome- try, and complexity of neural networks. arXiv preprint arX1v:111.01130, 2017.
Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur: Distribution of eigenvalues for some sets of random matrices. Mutematicheskii Sbornik, 114(4):507-536, 1967.
Tomas Mikolov and Geoffrey Zweig. Context dependent recurrent neural network language model. In 2012 IEEE Spoken Language Technology Workshop (SL7), pp. 234-239. IEEE, 2012.
John Miller and Moritz Hardt. Stable recurrent models. In International Conference on Learning Representations, 2019. URL /tRLlatttp////ppeeeeee..ert net/ forttt/foummmiem htt.::/wwwe....oi.ooooggo///eeee
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized opti- mization in deep neural networks. In Advances in Neural Information Processing Systems, pp- 2422-2430, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015b.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally margin bounds for neural networks. In International Conference Learn- ing Representations, 2018. URL
net/ http://ormmmmmmmmmm WfbC2
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 Learn- ing Representations, 2019. URL httttttts///pneeee
nwwttorummmeeeee net forum Byd-BggfggAcXXX
Samet Oymak. Stochastic gradient descent learns state equations with nonlinear activations. arXiv preprint 180i .00099, 2018.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference Machine Learning, pp. 1310-1318, 2013.
J Saniuk and Rhodes. A matrix inequality associated with bounds solutions of algebraic riccati and Iyapunov equations. IEEE Transactions on Automatic Control, 32(8):739-740, 1987.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint arXiv: 00..160900..10 08144, 2016.
Zhilin Yang. Zihang Dai, Ruslan Salakhutdinov, and William W. Cohen. Breaking the softmax bottleneck: A high-rank RNN language model. In International Conference Learning Repre- sentations, 2018. URL
net /iet/fore http:/ooommmmddk//o.eae CZ
Wojciech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. arXiv preprint 1409:2409.2329 2014.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 2017. URL httpss//arxiv.orr//a/
Jiong Zhang, Lei, and Inderjit Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In International Conference Machine Learning, pp. 5801-5809, 2018.
10

---

Published as a conference paper at ICLR 2020
A PROOFS IN SECTION 3.1
A.1 PROOF OF LEMMA 1
Proof. To begin with, by equation I we have yL Vhg. Then the derivative of yr with respect to Vob can be calculated as
dyL (0, 0, ... [hr]6, 0)²,
Jcab
i.e., a k-dimensional vector with a-th element [hz]b and all other elements zero. Multiplying both sides by lab and summing them up, we get
dyL
Σ
Vab Vhg yr.
Juah
a,b
The derivative of yL with respect to W and U can be derived by using chain rule in the similar way as follows.
Oyr. V
dh.
Dwyy
Owis
Th (ong(d())))(0... [he-1li," ... ,0) diag(p' (gL)) Thg-1
Dwis
Owij
and
OyL
Thg
aupa OhL
Dupa
[azlg. ... "0)" + diag(p' (9 0hL-1
Oum
Sum
where we use the property of ReLU activation function that p(z) = p' (z(2).. Summing up these terms immediately gives us the following equality.
Σ ThL
Wij + + OhL
1,3 Owij
p.g Dupg Upg
-diag (()g))(()))) (0, ... [hL- .. 1)0 wi, + (0,,. [Fil. ... _0)
,0) Upg) ) + diag(p (gL))
@hL-1 Wij + Σ @hL-1 Upg)
W
b. Owij
Oupn
OhL-1 Owi
wij + Σ Uh
=
diag(p' (oo(((((g))((W->>1)))) hL-1 + UXL) +
Upg)
Orpp
2.
p.q
ThL-1 Wij + Σ Th
= h + diag(p (g
Upg).
b. Owis
Srkp
For ease of exposition, define fL = Σ Th Wij
Thu Dupg
Σ
Upg.
Then the above equality can be
in Owis
p.q
rewritten as
ft = hy + diag(p' (gt)) ft-1-
By induction, we have
fg = hi + diag(p' ( diag(p (oL) W (9-)(((l diaglp' (gL)) diag(p' ('L ( (g2))
Multiplying both sides by V and using some basic calculation, we can show that V = Ly (0)(0,
1)= Therefore,
Σ TyL a. Drab
Uab + Σ OyL wij + +E TyL Upa yr. + VJr. = (I 1)yr. - (0) 1, I. - p.a Oupp
1, Owij
Substituting yı.
1)TT
into the above equality leads the desired result
dyL Ovab
dyL wis
OyL Upy (7)0cc
Σ
Vab
Σ
Σ
Owij
Sutp
2.j
p.g
11

---

Published as a conference paper at ICLR 2020
A.2 PROOF OF LEMMA 2
Proof. Using the definition of Fisher-Rao norm,
ol ( v)
|01| B(< 8, Vi(yLO v) > E(< 8 VyLo(z)
>)
dyLo
= -y((O))yLL(T) ayy.oo E( VVLa VVLa(x)7
al y)
>2)
dyLo
dyLo
By Lemma 1, we have VyLo(z)* :)(0)c. Substituting it into the above equality gives us
|011 ((((0)), ((yLo(z))
Oyr.
B PROOFS IN SECTION 3.2
B. PROOF OF LEMMA 3
The proof of Lemma 3 relies on the following result Saniuk Rhodes (1987). Proposition 1. Let X, YE R=xa with Y symmetric and nonnegative definite. Then, trace(XY) S |||||2 trace(Y).
Now we are ready to prove Lemma 3.
Proof. Denote == [R(([. + 1)æf Lay,". ... , (.))) 1)a9 Ia?. ... 2x()). By the defini- tion of [101] for any y E V. we have
[[))))),m "Ila
[[>(()),, 1) Lay 22 ,ag ",,,""""",,"""""""" 20
-B((v(0)),, ((L 1)x Lxz ",,"",,,)))))))) ( Lrg, ... 2x (+)))
= =B(((((0))) < ||0|;
where [v)(0),, represents the y-th row of (0)). On the other hand, from the definition of Rademacher complexities,
R, (F+) = E. sup E ((x)),)) (sup Σn (0)x (sup Σn 1==1(=(0),,,pp IEF,"
T1
0,9 "
0.v n
EE (sup f,y
Eie D404, (x())), T ">) S Eo (sup(1)
Ei aolill =1lx(()),, (()(())((ll)))) *1la))
7
AN
n
1
S rE (11
Ln (.oo)ll-.) rB Em I,0;){
1
S Vv E. < - En 20,)) E 1 o.), A-1 = 1
< En Ia A-11
n²
XX",
1 A
XXX, (C((xr))C)
traceeeaeeXX (X (-(((C(=
where the first inequality uses Cauchy-Schwarz Schwarz inequality and C == diag Lla.... -21a).
Since 0-1 and E(xa²') ) are positive definite, we have
trace XXTC-II (E( () -IC- trace (C-'(B(xxT]) -
<||C-|(B(xx (B(xx D)) C- 112trace (xxxaceeeXX)) < ||0 I| ([I(xx")))~[ll(((""> ([000(||laaccexX"))
|[X
=+1((E(xa))) -122 4 Amii (E(xx²))
where the first inequality is by Proposition and the last inequality uses trace ttace(XXX) ||
Therefore,
-||X||F
Hi (F.) 5
2n
Amin (E(xx
12

---

Published as a conference paper at ICLR 2020
B.2 PROOF OF LEMMA 4
Proof. Denote Hi UX, W W and Hi == U.X1. By the definition of Hr, we have
H₁ H2 p + W -1) UX, - -W -UU W W U WH W Hy + (
which by induction gives
HL
-.. H - W
So the difference term can be rewritten as
VHL (00) = VHz Vill Ei VWL
where the second equality uses (² =VH
B.3 PROOF OF LEMMA 5
Proof. Using Riesz- Thorin Theorem, we have || S || 1/p HH' 11 1-1/p_ And since H
p(G.) Gt, by the definition of the induced Ln and Leo matrix norm, we know || S ||G]]] and 1o $ ||G]|]oo- Therefore,
|| S " 1 s <I
s m 1) 2 }) ||Gellp
where the last inequality uses some basic facts about matrix norm that |Go|| I m m/////||Gel/ and ||Gr|l
<n>/P|/Grll
B.4 PROOF OF LEMMA 6
Proof. For any y. by Hölder's inequality, for any p.q 2 1 with + 1,
1 :. ![VWL-'H HH y = [ WL- < | WTL [V T "|ll|ll|
= =1[(Vy,. T IT H 1 10-1 < [[[],, T "Ip [T -1- -n-b ||G, - l|r
In order to eliminate the dimension dependency convergence rate with respect to n, we choose = 1. Then the above inequality re- duces to HWWWL'H,'T,. S [[[V], lg. [ [- "n" I B II s 8y By n [Bul|x, 711 Bw ||H 1111). For |H TI we have
and simultaneously enjoy faster
| 7111 | TUT + H.-JTTT
< ||X;- TUT + H H
Bal| 1- 111
+ Bwl 11:
which by induction gives
|H T11 S Bu Σ
- 1 ||x ||x 112.
B
j=1
Therefore,
1 VWL HH," H, < - By Br Σ
1
E, ( sup TE
B/ "11,, T T11..
j=l
13

---

Published as a conference paper at ICLR 2020
B.5 PROOF OF THEOREM 1
Proof. Using the notations that we have introduced earlier, the empirical Rademacher complexity be rewritten
B sup DEIL.Ey n
Σ E
E. sup
(VH.ly.
oetlyey
-E,( sup
E VW + +00))
Betlyyy
-i=1 B.
sup oetlyyy
"WWh-H, + E.r sup - (1) BEfl.Ey
1 (0)x
E.
sup BELLEyn
+ E.r
sup i
where the second equality uses Lemma and the last inequality is due to the fact that 52 C and Ω S {0:
5 Sr).
For the last term, by Lemma 3, we have
Eg sup
(0) -
|10 STazE
2n
Amin (E(xx²))
The other terms can be handled by Lemma 6 in the following way.
E ( sup VWL-iHH I Ele C13v Bu Ej=1 BW 1
dEL,EYN
8
$ D Si=1 Bv BU Σ PW
||**111) 1 1- Bw
L(3())
Bw
for 3w # 1, and Σ F.
WWLLHH s 3r Br B₂ 1.t.? for Bw = 1, where the 2
sup
oEflyEym
second inequality uses the definition of matrix norm 1|.
Collecting all terms, we establish
E sup 1 E PEñ.EEY" n
1||
1 - Bu
2n
Amin (a(n(EE))))))
n
C PROOFS IN SECTION 3.3
This section includes the full proofs of the generalization bound for training with random noise.
C.I LIPSCHITZ PROPERTIES RELU NONLINEARITIES AND MARGIN OPERATOR
We first establish the Lipschitz properties of the ReLU activation function and margin operator M(U (1) y) == Myz (x, y).
Lemma 9. Let p: R R" be the coordinate-wise Ren then it 1-Lipschitz according to || for any 2 1.
Proof. For any x, x' E R
1 - ,(x'(()))))) - C (p(x), -(('))))) < Σ 1s - x(P)) 1/9 = =||r x'llz-
14

---

Published as a conference paper at ICLR 2020
Lemma 10. For every j and every p 2 1, M(:5) is L-pischhit wrr I1-1pp-
Proof. Let y,y', y' be given, and suppose that MMy. j) S MMy', without loss of generality, Select
coordinate + j so that j)y = yJ Vı. Then
M()' -M) = f/ max ví y, +u - (t/ Uj + (3+ vl) = 211e' - -vloo - 211y - ~
141
C.2 PROOF OF LEMMA 8
Proof. We prove this Lemma by induction. Let r (Iz, -2. ,T) and x' = (2) 222 x2).
Denote g Uz + Whl hi := p(g() and V/2 Vhi. Then we have
1/4 W11l (l((g)) p(g - 11.. g.1l= 1| Why Un! Wh 11100 < 11 | It, => + [[W]||||/
14-11
where the first inequality uses Lemma 9 and the second inequality uses basic properties of 1ax By induction, we get
|| - 11y S Σ 11107111l |1 - 1//lo0.
Therefore,
1uz->/lle IVhh-Vitllee $ 1o hh -ic $ "| -|,
C.3 PROOF OF THEOREM 3
We begin by establishing two auxiliary lemmas that we will need for the subsequent theorem.
Lemma 11. For every RNNs in 7 with weight matrices 0 (U, W, V,,), the following inequality holds for any x (#1. "2."" ,LL) and y.
E. Pa (x, Pa (M, (a +,,00))) S
Σ | | (B.
Proof. For any fixed and y.
|R D. (My (xr v)) & (MM (o + e, S E. (M, D (My (x (x +e,g)))
② E. (x) (1 + +) < EE || "|/ -/llll)))))))))
En |
|| W WIT (E, ||<]]
a
where the first inequality uses Jensen's inequality, the second inequality follows from the Lipschitz property of (+) and Lemma 10 and the last inequality is by Lemma 8.
Lemma 12. Lel {ei]d be an iid sequence of NO, variables, then Elmax; leil] S log(2)).
Proof. Define Z = [max, |es]]. For any 0, by Jensen' inequality, we have
(F < ) E(max (1ll) < Σ B(etki)) (2 < 22
where the second inequality uses the definition of normal distribution and the cumulative dis- tribution function of the standard normal distribution. Taking logs both sides and dividing by we get
log (2d)
02t
E Z)
<
t
2
15

---

Published as a conference paper at ICLR 2020
Choosing f (2log(2d) leads to the desired result,
B(Z) - ov log(dd..
We now return the proof of Theorem 3.
Proof. For any RNNs with weight matrices 0 = (U, W. V) satisfying || S 8v, s Bw, Dwv.lUT1l $ Be, we have
Ezyl L (Myr yr (a, y)]] Exe.y &
(x (2
R ta (Mor v)) Re Da (o 6,
Exy ta (M v)) [. (x+ 2 E, By ((.lllll)))))))
where the first equality is due to the fact that the input and noise independent, the first inequality uses Jensen's inequality and the last inequality follows from Lemma 11. The inequality above can be rewritten follows.
L (z, v))l < Be, (a + +), + Σ, By
( (E.llesllo)
For the first term in the right hand side of the above inequality, by Theorem 2, with probability at least 1 5, the following holds:
B (M (Ic + v,
4h
x||X + Xelle
+ +X!IlA) - +
+ +31
log 2n
8
2
a
2n
Amin(B((e + ex + +))²))
Σ
aa (MMM (I; + (.)
4h:
r||x Xelle
logg
V (mii(E(xxT)) B(ccT)) + By + x?()iA) + 3/
a
2n
2n
Σ 2 (MM (I; + vi)
4k
x||Xx + +Xlll
log
T
+ - -v + x((1 + 3/
a
2n
V Amin ABix(((xx") + ot!)
2n
Σ
aa
(MM (I: + ci,
4k
r||X + +elle
1log
a
2n
V Amin (B(x((((xT)) o?
+ - BB Br + x(()1A) + 3/
2n
+
Σ aa (Myz (o; + e..
Combining the above two inequalities together leads to
E Maz. (o.)) I E vr. (x. y))l
2
< Σ $ (Myn (I: + Ess v.)
+ Σg By 34 (Belle))bo0++
n
a
4k X + IF
log 2
+ By ByBullX + + + 3/
a
2n
Amin (E(xx")) + o?
2n
where the first inequality makes use of the fact that 1, S $ (u). Therefore, the desired result can be immediately obtained by substituting Belleill looloo with v log (2d) according to Lemma 12.
D SUPPLEMENTARY FIGURES
Figure shows the behavior of generalization error for RNNs as the standard derivation of noise de varies for the sequence length L 200 and 300 trained on IMDB dataset. As in the body, increasing o, will first improve the generalization error and then, after a certain point, harm the performance of RNNs.
16

---

Published as a conference paper at ICLR 2020
1.50%
1.40%
geneel petton 6172
1.30%
3.70%
1.2%
1.00%
110%
1.00%
1004
0.0%
0.00%
0.0
0.1
0.2
633
0.4
0.0
0.1
0.2 noise deviat on
0.5
04
nain devistion
Figure 2: Generalization error for training with noise (mean standard error averaged on 5 runs). The left and right panel are for L = 200 (smallest eigenvalue: x 10-4) and L 300 (smallest eigenvalue: 2.5 x 10-5) respectively.
17


Reviews:
[{"review_id": "rJxdMvq3KB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 proposes a new generalization bound for vanilla RNN with ReLU activation in terms of matrix-1 norm and Fisher-Rao norm. This bound has no explicit dependence on the size of networks.\n\nI am actually not familiar with the generalization theorem on RNN. Nevertheless, according to the demonstration of the authors, I can understand the results of the theorems in this paper. I think the analysis on the property of the covariance matrix of the input data are valuable. However, I still have some concerns as follows.\n\n1.\tIt is interesting if the bound can be independent on the size of networks. However, according to the bounds, I find that the bounds still depend on the size of the network but implicitly. Thus, I understand why the authors claim that the bound they provide has no “explicit” dependence on the size of networks. Then what is the value of this contribution?\n2.\tIn Section 3.4.1, the authors state that “Since the smaller eigenvalues usually contribute to high frequency components of the input signal, our bound suggests that high frequency information is often more difficult to generalize, which is consistent with intuition.”. Can the authors provide more explanations on this since I do not understand why smaller eigenvalues usually contribute to high frequency components of the input signal and what the frequency components of the input signal is. What is the formulation of the high frequency components of the input signal?\n3.\tIt seems that ReLU activation is not widely used in RNN. Instead, tangent and sigmoid function are more prevalent. The authors mention in Conclusion that the extending the results to other variants of RNNs like LSTM and MGU might be an interesting topic for future research. I think the first extending work is to study the generalization bound of vanilla RNN with tangent or sigmoid activation. \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJeKFZ8aFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 authors investigate the topic of theoretical generalizability in recurrent networks. Specifically, they extend a generalization bound using matrix 1-norm and the Fisher-Rao norm, proving the effectiveness of adding noise to input data for generalizability. These bounds have no dependence on the size of networks being investigated. The authors also propose a technique for representing RNNs as a decomposition into a sum of linear networks with a difference term, which allows for easier estimation of Rademacher complexity. The authors claim this is a representation that can be extended to other neural network architectures such as convolutional networks. \n\nThis work has the potential to be of interest for the learning theory community on theoretical properties of recurrent neural networks.\n\nOne question I have for the authors: in the experiments on the IMDB dataset, the authors claim that the generalization error is worst at \\sigma_{\\epsilon} = 0, but it appears that the error is actually larger for \\sigma_{\\epsilon} = 0.4? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "H1lnk5Sp5H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 is an interesting and very well-written paper. I read the paper carefully but I don’t have sufficient expertise to determine whether all the proof steps are correct.\n\nThis paper builds on recent works giving generalization bounds on RNNs.\n\nThe primary contribution is that they are able to bound the generalization error for RNNs without a dependence on the network size parameters d and m.\n\nTheir proof is roughly as follows:\n1. They decompose the RNN + ReLU activation into the sum of a linear network and difference terms. This step is key because it lets you treat each term independently when estimating the Rademacher complexity.\n2. The linear network term can be bounded directly with their Fisher-Rao norm.\n3. They make a second decomposition: the difference term can be written as a sum of simpler terms\n4. For the simpler terms, their Rademacher complexity can be bounded independently using matrix-1 norm. Using the matrix-1 norm instead of the spectral norm means their bounds won’t depend on the network size parameters.\n5. Then they combine these bounds to give the Rademacher complexity bounds for RNNs.\n6. Lastly, they combine the Rademacher complexity bound with Kuznetsov et al 2015’s multiclass margin bound to give the generalization bound.\n\nThe downside to their generalization bound is that it requires the covariance matrix of the input data must be positive definitive, and it explodes when the smallest eigenvalue is close to zero.\n\nTheir second contribution attempts to address these downsides. They prove another generalization bound for RNNs when training with random noise, which has the effect of increasing the term containing the smallest eigenvalue of the input covariance matrix.\n\nThey remark on several empirical phenomena that are consistent with their results:\n- Correlation of features in the input data makes it harder for RNNs to generalize\n- Weight decay could help by decreasing the relevant gradient terms in their bounds\n- Gradient clipping could help when the smallest eigenvalue of the input covariance is very small\n\nTheir third contribution is a single experiment. This contribution is fairly weak and the practical value of their theoretical work would be much more convincing if they were to put more effort into this section.\n- They use IMDB data set (50k movie reviews + binary sentiment classification task)\n- They add Gaussian noise to the input data with four different values.\n- They plot the generalization error, which is the difference between the test error without noise and the training error with noise\n\nSpecific comments to improve their experiment section:\n- I’m confused by the following sentence: “generalization errors … for different combinations of L and \\sigma_epsilon are shown in Figure 1.” However, in Figure 1 I only see different values of sigma. I don’t see anything about using various values for L. This should be clarified.\n- Figure 1 draws linear interpolation between data points - there’s no evidence for those interpolations. It should be reported as a scatter plot, preferably with error bars.\n- If space limitations prevent reporting the experiment results more rigorously, I would prefer to see the experiment results reported in an appendix, with a brief comment on their significance in the main paper.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a generalization bound for RNNs based on matrix-1 norm and Fisher-Rao norm. As the initial bound relies on non-signularity of input covariance, which may not always hold in practice, the authors present additional analysis by noise injection to ensure covariance is positive definite. Through the resulted bound, the paper discusses how weight decay and gradient clipping in the training can help generalization. There were some concerns raised by reviewers, including  rigorous report of the experiment results,  claims on generalization in IMDB experiment,  claims of no explicit dependence on the size of networks, and the relationship of small eigenvalues in input covariance to high frequency features. The authors responded to these and also revised their draft to address most of these concerns (in particular, authors added a new section in the appendix that includes additional experimental results). Reviewers were mainly satisfied with the responses and the revision, and they all recommend accept.

Decision: Accept (Poster)