Title: UNDERSTANDING GENERALIZATION IN RECURRENT NEURAL NETWORKS

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.

1. INTRODUCTION:

The Recurrent Neural network (RNN) is a neural sequence model that has achieved the state-ofthe-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 translation (Wu et al., 2016; Kalchbrenner & Blunsom, 2013) . Unlike feedforward neural networks, RNNs allow connections among hidden units associated with a 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 generalization property. For example, Graves (2013) showed that deep LSTM RNNs achieved a 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 (2018) studied the state equation of recurrent neural networks and showed that SGD can efficiently learn the unknown dynamics from few observations under proper assumptions. Miller & Hardt (2019) tried to explain why feed-forward neural networks are competitive with recurrent networks in practice. They identified stability as a necessary condition and proved that stable recurrent neural networks are well approximated by feed-forward networks for the purpose of both inference and training by gradient descent. Despite of the impressive progress in understanding the training behavior of RNNs, there is 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, numerous complexity measures have been proposed to capture the generalization behavior such as VC dimension (Harvey et al., 2017) and norm-based capacity including spectral norm (Bartlett et al., 2017; Neyshabur et al., 2019) , Frobenius norm (Neyshabur et al., 2015b; a; 2018) and l p -path norm (Neyshabur et al., 2015b; Bartlett & Mendelson, 2002; Golowich et al., 2018) . These existing normbased complexity measures depend on the number of hidden units of the network explicitly and thus can not explain why neural networks generalize so well in practice, despite that they operate in an overparametrized setting (Zhang et al., 2017) . 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, a new generalization bound based on Fisher-Rao norm was proposed (Liang et al., 2017) . 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 et 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-Rao norm and matrix 1-norm. In contrast to existing results such as spectral norm-based bounds, our bound has no explicit dependence on the size of networks. The remainder of this paper is structured as follows. We define the problem and notations in Section 2. The notion of Fisher-Rao norm for RNNs is introduced in Section 3.1. We prove the generalization bound for RNNs in Section 3.2, and the generalization bound for training with random noise is derived in Section 3.3. Section 3.4 gives a 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 ∈ R m×d , V ∈ R k×m and W ∈ R m×m be the weight matrices. Given the input sequence

x = (x 1 , x 2 , • • • , x L ) ∈ R Ld where each x i ∈ R d

and L is the input sequence length, the vanilla RNNs can be described as follows.

EQUATION

where g t and h t ∈ R m represents the input and output of hidden layer at step t, ρ(•) is the ReLU function and y t ∈ R k denotes the output value at step t.

For simplicity, in this paper, we only consider the final output y L . We assume that data (x, y) is drawn i.i.d. from some unknown distribution D over R Ld × Y where Y represents the label space {1, 2, • • • , k}. The RNNs above define a mapping y L (x) from R Ld → R k , where k is the number of classes. We convert y L (x) to a classifier by selecting the output coordinate with the largest magnitude, meaning

x → argmax i [y L (x)] i ,

where [•] i represents the i-th element of a vector. This naturally leads to the definition of margin M y L (x, y) of the output y L at a labeled example (x, y):

M y L (x, y) = [y L (x)] y -max y =y [y L (x)] y .

Thus, y L misclassifies (x, y) if and only if M y L (x, y) ≤ 0. The quality of the prediction made by y L is measured by the expected risk defined as

E (x,y)∼D [1 My L (x,y)≤0 ].

Since the underlying distribution D is unknown to us, we instead consider the empirical error on sample data given by 1 n n i=1

(1 My L (xi,yi)≤α ).

The generalization error is then the difference between expected risk and empirical risk, defined as

E (x,y)∼D [1 My L (x,y)≤0 ] - 1 n n i=1

(1 My L (xi,yi)≤α ).

Our goal in this paper is to study the generalization error for RNNs theoretically.

To establish the generalization bound, a little bit of notations are necessary. T ). The smallest eigenvalue of a matrix A is given by λ min (A). The activation function ρ and its derivative ρ are entrywise, i.e., ρ(

A) = (ρ(a ij )) ij and ρ (v) = (ρ (v i )) i . We denote c = (L + 1, L, • • • , 2) T , η(θ) = [V diag(ρ (g L ))...W diag(ρ (g 1 ))U x 1 , V diag(ρ (g L ))...W diag(ρ (g 2 ))U x 2 , • • • , V diag(ρ (g L )) U x L ] ∈ R k×L and τ (θ) = (V W L-1 U x 1 , V W L-2 U x 2 , • • • , V U x L )

where θ = (U, W, V ) and diag converts a vector into a diagonal matrix.

3. 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-Rao norm for RNNs.

3.1. FISHER-RAO 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 = (x 1 , x 2 , • • • , x L ), consider the recurrent neural network in (1), we have the identity

a,b ∂y L ∂v ab v ab + i,j ∂y L ∂w ij w ij + p,q ∂y L ∂u pq u pq = η(θ)c.

The notion of Fisher-Rao norm is motivated by Fisher-Rao metric of information geometry and is defined as follows.

Definition 1 ( (Liang et al., 2017) , Definition 2). The Fisher-Rao norm for a parameter θ is defined as ||θ|| 2 f r :=< θ, I(θ)θ >, where I(θ) = E(∇l(y Lθ (x), y) ⊗ ∇l(y Lθ (x), y)) and l(., .) is the loss function.

The following lemma gives the explicit formula of Fisher-Rao norm in RNNs. We can see that the notion of Fisher-Rao norm relies mainly on the gradient structure of RNNs.

Lemma 2. Assume that the loss function l(., .) is smooth in the first argument. Then the following identity holds for the RNN in (1),

||θ|| 2 f r = E η(θ)c, ∂l(y Lθ (x), y) ∂y Lθ 2 .

Remark 1. We observe that each term V diag(ρ (g L ))...W diag(ρ (g i ))U x i in η(θ) is actually the gradient component in Backpropagation through time (BPTT). Therefore, the Fisher-Rao norm can be regarded as a measure of gradient. As will be shown later, we can build a relationship between generalization and trainability in RNNs via Fisher-Rao norm.

For the linear activation function and margin loss l(y Lθ (x), y) = Φ α (M y L (x, y)) where α > 0 is the margin parameter, one might upper bound the Fisher-Rao norm in Lemma 2 by

||θ|| 2 f r ≤ 4 α 2 E max i [(τ (θ)c) i ] 2 , since τ (θ)c, ∂l(y Lθ (x), y) ∂y Lθ 2 ≤ 4 α 2 max i [(τ (θ)c) i ]

2 by definition of M y L (x, y) and lipschitz property of Φ α (•). We define this upper bound as

EQUATION

and still call it "Fisher-Rao 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 || • || f s 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 it is very challenging to bound the Radermacher complexity of ReLU networks directly in terms of the Fisher-Rao norm, we consider decomposing the ReLU network into the sum of a linear network and a difference term, i.e., y L = ψ(θ)x + (y L -ψ(θ)x). For the linear network part ψ(θ)x, the Rademacher complexity can be bounded directly by Fisher-Rao norm. For the difference term (y L -ψ(θ)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.

Lemma 3. Define F r := {x → [ψ(θ)x] y : ||θ|| f s ≤ r, y ∈ Y} where x ∈ R Ld and ψ(θ) := (V W L-1 U, V W L-2 U, • • • , V U ).

For any data x 1 , x 2 , • • • , x n drawn i.i.d from the distribution D, collect them as columns of a matrix X ∈ R Ld×n . Then we have

Rn (F r ) ≤ r||X|| F 2n 1 λ min (E(xx T ))

,

assuming that E(xx T ) is positive definite. Remark 2. If E(x) = 0, E(xx T ) is the covariance matrix of random variable x.

Remark 3. We should mention that our assumption that E(xx T ) is positive definite is not so restrictive and usually holds in practice. For example, for the case that x is continuous random variable, we can prove that E(xx T ) is positive definite as follows. Suppose that x is a continuous random variable in the n-dimensional subspace X ⊂ R n . If there exists u ∈ R n such that u T E(xx T )u = 0, then for any x ∈ X we have u T x = 0, i.e., u ⊥ X. Since X is n-dimensional, the only u that satisfies is that u = 0. Therefore, by definition, E(xx T ) is positive definite. As we will show in 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 y L -ψ(θ)x. With a slight abuse of notations, given input data

x 1 , x 2 , • • • , x n ∈ R Ld , the corresponding g 1 , g 2 , • • • , g n ∈ R Lm and h 1 , h 2 , • • • , h n ∈ R Lm are calculated by (1)

. We collect all input data as a matrix denoted by X, all input data at time t as a matrix denoted by X t , all input of the hidden layer at time t as a matrix denoted by G t and all output of hidden layer at time t denoted by H t , where

X ∈ R Ld×n , X t ∈ R d×n , G t ∈ R m×n , H t ∈ R m×n and t = 1, • • • , L.

The difference term can be decomposed by the following lemma. Lemma 4. Define H t := H t -G t . Then the following equality holds

V H L -ψ(θ)X = L i=1 V W L-i H i .

To bound the Rademacher complexity of each term in the above decomposition, we need a technical lemma given as follows.

Lemma 5. For any p ≥ 1,

||H t || p ≤ m 1 p (1-1 p ) n 1 p (1-1 p ) ||G t || p .

As we will see, the operator norm in Lemma 5 will be instantiated for the case of p = 1. The use of || • || 1 helps avoid the appearance of the dimension m when upper bounding the Rademacher complexity. Also it guarantees that Rademacher complexity has a convergence rate O(1/n). The upper bound for the Rademacher complexity of these individual term is given by the following lemma. Lemma 6.

Let

Ω := {θ = (U, W, V ) : ||V T || 1 ≤ β V , ||W T || 1 ≤ β W , ||U T || 1 ≤ β U }. Then for any i = 1, • • • , L, we have E σ sup θ∈Ω,y∈Y 1 n [V W L-i H i ] y, σ ≤ 1 n β V β U i j=1 β L-j W ||X j T || 1 , where σ = (σ 1 , σ 2 , • • • , σ n ) T is Rademacher random variable and [•]

y, represents the y-th row of the matrix.

We are now ready to put the ingredients together to prove our first theorem.

Theorem 1 (Rademacher complexity of RNNs).

Let

Ω := {θ = (U, W, V ) : ||V T || 1 ≤ β V , ||W T || 1 ≤ β W , ||U T || 1 ≤ β U , ||θ|| f s ≤ r}.

Then, the empirical Rademacher complexity of RNNs with ReLU can be bounded as follows

E σ sup θ∈Ω,y∈Y 1 n n i=1 [y Lθ (x i )] y σ i ≤ r||X|| F 2n 1 λ min (E(xx T )) + 1 n β V β U ||X T || 1 Λ , where Λ := 1 1-β W 1 -β L W 1 -β W -Lβ L W if β W = 1 and Λ := L+L 2 2 for β W = 1.

To establish the generalization bound for RNNs, we need the following classical results for multiclass margin bounds. Lemma 7 ( (Kuznetsov et al., 2015) , Theorem 2). Let H ⊆ R X ×Y be a hypothesis set with Y = {1, 2, • • • , k}. Fix α > 0. Then, for any δ > 0, with probability at least 1 -δ, the following multi-class classification generalization bound holds for all h ∈ H:

R(h) ≤ 1 n n i=1 Φ α (M h (x i , y i )) + 4k α Rn (Π 1 (H)) + 3 log 2 δ 2n ,

where

Π 1 (H) = {x → h(x, y) : y ∈ Y, h ∈ H}.

The generalization bound for RNNs follows from combining Theorem 1 and Lemma 7. Theorem 2. Fix margin parameter α, then for any δ > 0, with probability at least 1 -δ, the following holds for every RNN whose weight matrices θ = (U, W, V ) satisfy

||V T || 1 ≤ β V , ||W T || 1 ≤ β W , ||U T || 1 ≤ β U and ||θ|| f s ≤ r: E[1 My L (x,y)≤0 ] ≤ 1 n 1 My L (xi,yi)≤a + 4k α r||X|| F 2n 1 λ min (E(xx T )) + 1 n β V β U ||X T || 1 Λ + 3 log 2 δ 2n

.

(3)

Comparison with existing results. We compare our result with the existing generalization bounds (Zhang et al., 2018; Chen et al., 2019) . In comparison with the bound in Zhang et al. (2018) , which

is of the order Õ( max{d, m, k}L 2 ||U || 2 ||V || 2 max{1, ||W || L 2 } √ nα

), there is no explicit appearance of the network size parameters d and m in our bound. As we have mentioned before, the reason that we can avoid these dimensional factors is that we use matrix 1-norm instead of spectral norm to upper bound the Rademacher complexity of the network. Moreover, there is always a L 2 factor in their bound, whereas the L 2 term only occurs in our bound when ||W T || 1 = 1. For the case that ||W T || > 1, our bound has only a linear dependence on L, and for the case that ||W T || 1 < 1, by simple calculation, we can show that Λ ≤ 1 (1-β W ) 2 and the dependence on L would vanish. Both of our bounds have an exponential term ||W || L , which would make the bounds become vacuous for ||W || > 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 is also an additional bonus of our proof technique. In the next section, we will use this proof technique to derive a 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(xx T ) to be positive definite and would become very poor when the smallest eigenvalue is close to 0, 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 σ 2 , the term E(xx T ) in the bound becomes E((x + )(x + ) T ) and the smallest eigenvalue of E((x + )(x + ) T ) is (λ min (E(xx T )) + σ 2 ), which is greater than σ 2 . 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 et al., 2014; 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 σ 2 . Let i denotes the d-dimensional gaussian noise generated at step i and = ( 1 , 2 , • • • , L ) ∈ R Ld . We collect all noise data as a matrix 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 (1) with weight matrices θ

= (U, W, V ), y L is Lipschitz with respect to || • || ∞ , i.e., ||y L (x) -y L (x )|| ∞ ≤ i ||V T || 1 ||U T || 1 ||W T || L-i 1 ||x i -x i || ∞ for any x = (x 1 , x 2 , • • • , x L ), x = (x 1 , x 2 , • • • , x L ) ∈ R Ld .

The generalization bound for training with random noise is described as follows. Theorem 3. Fix margin parameter α, then for any δ > 0, with probability at least 1 -δ over a sample ((x 1 , 1 , y 1 ), (x 2 , 2 , y 2 ), • • • , (x n , n , y n )), the following holds for every RNN whose weight matrices

θ = (U, W, V ) satisfy ||V T || 1 ≤ β V , ||W T || 1 ≤ β W , ||U T || 1 ≤ β U and ||θ|| f s ≤ r: E[1 My L (x,y)≤0 ] ≤ 1 n Φ α (M y L (x i + i , y i )) + 2 α i β V β U β L-i W σ 2 log(2d) + 3 log 2 δ 2n + 4k α r||X + X || F 2n 1 λ min (E(xx T )) + σ 2 + 1 n β V β U ||X T + X T || 1 Λ .

Remark 4. The above bound can be easily extended to other kinds of noises by replacing σ 2 log(2d) by

E || i || ∞ .

Remark 5. The bound in Theorem 3 is an extension of that in Theorem 2 and can be applied even when the smallest eigenvalue of E(xx T ) is very close to 0. For example, when λ min (E(xx T )) = 1 × 10 -6 , applying Theorem 2 directly might lead to a vacuous bound. But if using Theorem 3 by choosing a small noise with mean 0 and variance 0.01, we might obtain a better bound since the term 1 λmin(E((xx T )))+σ 2 ≤ 10. Notice that adding noise can not always guarantee an improved generalization especially when λ min (E(xx T )) is not so small as it incurs an additional linear term

2 α i β V β U β L-i W σ 2 log(2d

) and might also increase other parameters in the bound such as ||X + X || F . Therefore we suggest adding noise only when the smallest eigenvalue of E(xx T ) is very small. For this case, a small noise such as σ = 0.1 not only can greatly improve the term

1 λ min (E(xx T ))

but also ensure that the extra cost σ 2 log(2d) and

||X + X || F /n be small enough since ||X + X || F /n ≤ ||X|| F /n + ||X || F /n and ||X || F /n

would be small when n is large.

Remark 6. If we remove the constraint condition ||θ|| f s ≤ r, which means that we do not have any knowledge about the gradients, the generalization bound in Theorem 2 and Theorem 3 still holds by substituting r with

β V β U B( 1 (1-β W ) 2 + 1 1-β W ) for β W < 1.

But with this extra gradient measure, the bound can become much tighter, especially when λ min (E(xx T ) is small. Please refer to the detailed analysis in the next section. Experiments. We now study the effect of random noise on generalization of RNNs empirically. For simplicity, we consider the IMDB dataset, a collection of 50K movie reviews for binary sentiment classification. We use GloVe word embedding to map each word to a 50dimensional vector. We train vanilla RNNs with ReLU activation function for sequence length L = 100. The corresponding smallest eigenvalue of E(xx T ) is approximated by using the total training data, which is 4 × 10 -4 . We add Gaussian noise to the input data in the training process with σ = 0.1, 0.2, 0.3 and 0.4. The generalization error which is the gap between test error without noise and training error with noise for L = 100 and different values of σ is shown in Figure 1 (results for other values of L in Appendix D). We observe that as we start injecting noise, the generalization error 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.

3.4. ANALYSIS OF GENERALIZATION BOUND:

Our theoretical results have a 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 T ):

According to our results, the generalization performance in RNNs is influenced by the smallest eigenvalue of E(xx T ). 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 in RNNs. The exact answer for this problem may be complicated. Here we only make an initial attempt and claim that weaker correlation would help improve the generalization, and a non-rigorous proof is given as follows. Denote the covariance matrix E(xx T ) by Ξ where each element ξ ij in Ξ represents the covariance between feature i and j. Suppose that ||Ξ -I|| 1 ≤ ζ with ζ < 1. By definition of || • || 1 matrix norm, we immediately get |ξ ii -1| + j =i |ξ ij | ≤ ζ for any i. Then by simple derivation, we obtain ξ iij =i |ξ ij | ≥ 1 -ζ for any i. Applying Gershgorin circle theorem, we have that the smallest eigenvalue must be greater or equal than 1 -ζ. Since the element ξ ij with i = j represents the covariance between feature i and j, a weaker correlation between feature i and j means a smaller value of |ξ ij | and we need a smaller ξ to upper bound ||Ξ -I|| 1 , which gives us a bigger lower bound on the smallest eigenvalue. Therefore the generalization bound becomes better.

3.4.2. GENERALIZATION AND TRAINABILITY:

The generalization of RNNs also depends on parameters β U , β V , β W and r, where β U , β V and β W control the weight matrices and r represents the gradient measure. It has a natural relationship with the training process. The normal procedure in training RNNs is to use weight decay for regularization and gradient clipping to avoid the exploding gradients problems (Bengio et al., 1994; Pascanu et al., 2013) . From the perspective of generalization, these strategies can decrease the value of these parameters β U , β V , β W and r and thus improves the generalization. For example, if

β W ≤ 1, we have Λ ≤ 1 (1-β W ) 2

, and the second term

1 n β V β U ||X T || 1 Λ

in the generalization bound would be small when β W is not so close to 1. Similarly, if λ min (E(xx T )) is very small, by setting the gradient clipping value in the training procedure, we can achieve a 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 we only have the weights, i.e., the parameters β U , β W and β V and the gradient measure parameterized by r is unknown to us. To apply our bound, a natural idea is to infer the gradient measure parameter r based on the known weight parameters. An upper bound for r in terms of β U , β W and β V is given as follows. Under the same conditions as Theorem 2, if we further assume that the data x be given with ||x T || 1 ≤ B, by the definition of || • || f s in (2), for any y ∈ Y, we have

((τ (θ)c) y 2 = ((L + 1)[V ] y, W L-1 U x 1 + L[V ] y, W L-2 U x 2 + • • • + 2[V ] y, U x L ) 2 ≤ (|(L + 1)[V ] y, W L-1 U x 1 | + |L[V ] y, W L-2 U x 2 | + • • • + |2[V ] y, U x L |) 2 ≤ ((L + 1)β V β U Bβ L-1 W + Lβ V β U Bβ L-2 W + 2β V β U B) 2 = (β V β U B( β W -β L W (1-β W ) 2 + 2-(L+1)β L W 1-β W )) 2 ≤ (β V β U B( 1 (1-β W ) 2 + 1 1-β W )) 2 , for β W < 1, and ((τ (θ)c) y 2 ≤ (β V β U B 3L+L 2 2

) 2 for β W = 1. The above inequality holds for any x and y. So we can get

||θ|| f s = E max i [(τ (θ)c) i ] 2 1/2 ≤ β V β U B( 1 (1-β W ) 2 + 1 1-β W ) for β W < 1. By replacing r with β V β U B( 1 (1-β W ) 2 + 1 1-β W )

, the generalization bound (3) also holds. But notice that this bound is obtained without any knowledge about the gradients. If we happen to know that the parameter r is much smaller than

β V β U B( 1 (1-β W ) 2 + 1 1-β W )

, 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 eigenvalue of E(xx T ) is small. Therefore the introduction of Fisher-Rao norm can help eliminate the negative effect of λ min (E(xx T )) and thus improve the generalization bound.

4. CONCLUSION:

In this paper, we propose a new generalization bound for RNNs in terms of matrix 1-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 T || 1 > 1. It is of interest to get a tighter bound which can avoid this exponential dependence. Moreover, our 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 an interesting topic for future research.

A PROOFS IN SECTION 3.1 A.1 PROOF OF LEMMA 1:

Proof. To begin with, by equation (1), we have y L = V h L . Then the derivative of y L with respect to v ab can be calculated as

∂y L ∂v ab = (0, 0, • • • , [h L ] b , • • • , 0) T ,

i.e., a k-dimensional vector with a-th element [h L ] b and all other elements zero. Multiplying both sides by v ab and summing them up, we get

a,b ∂y L ∂v ab v ab = V h L = y L .

The derivative of y L with respect to W and U can be derived by using chain rule in the similar way as follows.

∂y L ∂w ij = V ∂h L ∂w ij ∂h L ∂w ij = diag(ρ (g L ))(0, • • • , [h L-1 ] j , • • • , 0) T + diag(ρ (g L ))W ∂h L-1 ∂w ij and ∂y L ∂u pq = V ∂h L ∂u pq ∂h L ∂u pq = diag(ρ (g L ))(0, • • • , [x L ] q , • • • , 0) T + diag(ρ (g L ))W ∂h L-1 ∂u pq ,

where we use the property of ReLU activation function that ρ(z) = ρ (z)z. Summing up these terms immediately gives us the following equality.

i,j ∂h L ∂w ij w ij + p,q ∂h L ∂u pq u pq = diag(ρ (g L ))( i,j (0, • • • , [h L-1 ] j , • • • , 0) T w ij + p,q (0, • • • , [x L ] q , • • • , 0) T u pq ) + diag(ρ (g L )) W ( i,j ∂h L-1 ∂w ij w ij + p,q ∂h L-1 ∂u pq u pq ) = diag(ρ (g L ))(W h L-1 + U x L ) + diag(ρ (g L ))W ( i,j ∂h L-1 ∂w ij w ij + p,q ∂h L-1 ∂u pq u pq ) = h L + diag(ρ (g L ))W ( i,j ∂h L-1 ∂w ij w ij + p,q ∂h L-1 ∂u pq u pq ).

For ease of exposition, define

f L := i,j ∂h L ∂w ij w ij + p,q

∂h L ∂u pq u pq . Then the above equality can be rewritten as

f L = h L + diag(ρ (g L ))W f L-1 . By induction, we have f L = h L + diag(ρ (g L ))W h L-1 + diag(ρ (g L ))W diag(ρ (g L-1 ))W h L-2 + diag(ρ (g L ))W diag(ρ (g L-1 ))...W diag(ρ (g 2 ))W h 1 .

Multiplying both sides by V and using some basic calculation, we can show that

V f L = Ly L - η(θ)(0, 1, • • • , L -1) T . Therefore, a,b ∂y L ∂v ab v ab + i,j ∂y L ∂w ij w ij + p,q ∂y L ∂u pq u pq = y L + V f L = (L + 1)y L -η(θ)(0, 1, • • • , L -1) T . Substituting y L = η(θ)(1, 1, • • • , 1) T into the above equality leads to the desired result a,b ∂y L ∂v ab v ab + i,j ∂y L ∂w ij w ij + p,q

∂y L ∂u pq u pq = η(θ)c .

A.2 PROOF OF LEMMA 2:

Proof. Using the definition of Fisher-Rao norm,

||θ|| 2 f r = E(< θ, ∇l(y Lθ , y) > 2 ) = E(< θ, ∇y Lθ (x) ∂l(y Lθ , y) ∂y Lθ > 2 ) = E((θ T ∇y Lθ (x) ∂l(y Lθ , y) ∂y Lθ ) 2 ) = E(< ∇y Lθ (x) T θ, ∂l(y Lθ , y) ∂y Lθ > 2 )

.

By Lemma 1, we have ∇y Lθ (x) T θ = η(θ)c. Substituting it into the above equality gives us

||θ|| 2 f r = E η(θ)c, ∂l(y Lθ (x), y) ∂y Lθ 2 . B PROOFS IN SECTION 3.2 B.1 PROOF OF LEMMA 3

The proof of Lemma 3 relies on the following result in Saniuk & Rhodes (1987) . Proposition 1. Let X, Y∈ R n×n with Y symmetric and nonnegative definite. Then, trace(XY

) ≤ ||X|| 2 • trace(Y ).

Now we are ready to prove Lemma 3.

Proof. Denote A := E(((L + 1)x T 1 , Lx T 2 , • • • , 2x T L ) T ((L + 1)x T 1 , Lx T 2 , • • • , 2x T L ))

. By the definition of ||θ|| f s , for any y ∈ Y, we have

||[ψ(θ)] y, T || 2 A = [ψ(θ)] y, E(((L + 1)x T 1 , Lx T 2 , • • • , 2x T L ) T ((L + 1)x T 1 , Lx T 2 , • • • , 2x T L ))[ψ(θ)] y, T = E([ψ(θ)] y, ((L + 1)x T 1 , Lx T 2 , • • • , 2x T L ) T ((L + 1)x T 1 , Lx T 2 , • • • , 2x T L )[ψ(θ)] y, T ) = E([(τ (θ)c) y ] 2 ) ≤ ||θ|| 2 f s

, where [ψ(θ)] y, represents the y-th row of ψ(θ). On the other hand, from the definition of Rademacher complexities,

Rn (F r ) = E σ ( sup f ∈Fr 1 n n i=1 f (x i )σ i ) = E σ (sup θ,y 1 n n i=1 [ψ(θ)x i ] y σ i ) = E σ (sup θ,y 1 n n i=1 [ψ(θ)] y, x i σ i ) = E σ (sup θ,y < 1 n n i=1 x i σ i , [ψ(θ)] y, T >) ≤ E σ (sup θ,y (|| 1 n n i=1 x i σ i || A -1 ||[ψ(θ)] y, T || A )) ≤ rE σ (|| 1 n n i=1 x i σ i || A -1 ) = rE σ < ( 1 n n i=1 x i σ i )( 1 n n i=1 x T i σ i ), A -1 > ≤ r E σ < ( 1 n n i=1 x i σ i )( 1 n n i=1 x T i σ i ), A -1 > = r 1 n 2 < n i=1 x i x T i , A -1 > = r n < XX T , A -1 > = r n < XX T , (CE(xx T )C) -1 > = r n trace(XX T C -1 (E(xx T )) -1 C -1 )

, where the first inequality uses Cauchy-Schwarz inequality and

C := diag((L+1)I d , LI d , • • • , 2I d ).

Since C -1 and E(xx T ) are positive definite, we have trace(

XX T C -1 (E(xx T )) -1 C -1 ) = trace(C -1 (E(xx T )) -1 C -1 XX T ) ≤ ||C -1 (E(xx T )) -1 C -1 || 2 trace(XX T ) ≤ ||C -1 || 2 ||(E(xx T )) -1 || 2 ||C -1 || 2 trace(XX T ) = 1 4 ||(E(xx T )) -1 || 2 ||X|| 2 F ≤ 1 4 ||X|| 2 F λ min (E(xx T ))

,

where the first inequality is by Proposition 1 and the last inequality uses trace(XX T ) = ||X|| 2 F . Therefore,

Rn (F r ) ≤ r||X|| F 2n 1 λ min (E(xx T ))

.

B.2 PROOF OF LEMMA 4:

Proof. Denote H t := U X t + W H t-1 and H 1 := U X 1 . By the definition of H L , we have

H L -H L = ρ(U X L + W H L-1 ) -U X L -W H L-1 = ρ(U X L + W H L-1 ) -U X L -W H L-1 + W (H L-1 -H L-1 ) = H L + W (H L-1 -H L-1 ) ,

which by induction gives

H L -H L = H L + W H L-1 + • • • + W L-1 (H 1 -H 1 ) = L i=1 W L-i H i .

So the difference term can be rewritten as

V H L -ψ(θ)X = V H L -V H L = L i=1 V W L-i H i ,

where the second equality uses ψ(θ)X = V H L .

B.3 PROOF OF LEMMA 5:

Proof. Using Riesz-Thorin Theorem, we have

||H t || p ≤ ||H t || 1/p 1 ||H t || 1-1/p ∞

. And since H t = ρ(G t ) -G t , by the definition of the induced L 1 and L ∞ matrix norm, we know

||H t || 1 ≤ ||G t || 1 and ||H t || ∞ ≤ ||G t || ∞ . Therefore, ||H t || p ≤ ||H t || 1/p 1 ||H t || 1-1/p ∞ ≤ ||G t || 1/p 1 ||G t || 1-1/p ∞ ≤ m 1 p (1-1 p ) n 1 p (1-1 p ) ||G t || p ,

where the last inequality uses some basic facts about matrix norm that

||G t || 1 ≤ m 1-1/p ||G t || p and ||G t || ∞ ≤ n 1/p ||G t || p .

B.4 PROOF OF LEMMA 6:

Proof. For any y ∈ Y, by Hölder's inequality, for any p, q ≥ 1 with 1 p + 1 q = 1,

1 n [V W L-i H i ] y, σ = 1 n [V ] y, W L-i H i σ ≤ 1 n ||H i T W T L-i [V ] y, T || p ||σ|| q = ||[V ] y, T || p ||W T || L-i p ||H i T || p n 1/q-1 ≤ ||[V ] y, T || p ||W T || L-i p m 1 p (1-1 p ) n -1 p 2 ||G i T || p .

In order to eliminate the dimension dependency on m and simultaneously enjoy a faster convergence rate with respect to n, we choose p = 1. Then the above inequality reduces to

1 n [V W L-i H i ] y, σ ≤ ||[V ] y, T || 1 ||W T || L-i 1 n -1 ||G i T || 1 ≤ β V β L-i W n -1 ||G i T || 1 ≤ β V β L-i W n -1 (β U ||X i T || 1 + β W ||H i-1 T || 1 ). For ||H i-1 T || 1 , we have ||H i-1 T || 1 = ||ρ(X i-1 T U T + H i-1 T W T )|| 1 ≤ ||X i-1 T U T + H i-2 T W T || 1 ≤ β U ||X i-1 T || 1 + β W ||H i-2 T || 1 ,

which by induction gives

||H i-1 T || 1 ≤ β U i-1 j=1 β i-1-j W ||X j T || 1 .

Therefore,

E σ sup θ∈Ω,y∈Y 1 n [V W L-i H i ] y, σ ≤ 1 n β V β U i j=1 β L-j W ||X j T || 1 .

B.5 PROOF OF THEOREM 1:

Proof. Using the notations that we have introduced earlier, the empirical Rademacher complexity can be rewritten as

E σ sup θ∈Ω,y∈Y 1 n n i=1 [y Lθ (x i )] y σ i = E σ sup θ∈Ω,y∈Y 1 n [V H L ] y, σ = E σ sup θ∈Ω,y∈Y 1 n [ L i=1 V W L-i H i + ψ(θ)X] y, σ ≤ L i=1 E σ sup θ∈Ω,y∈Y 1 n [V W L-i H i ] y, σ + E σ sup θ∈Ω,y∈Y 1 n [ψ(θ)X] y, σ ≤ L i=1 E σ sup θ∈Ω,y∈Y 1 n [V W L-i H i ] y, σ + E σ sup ||θ|| f s ≤r,y∈Y 1 n [ψ(θ)X] y, σ

, where the second equality uses Lemma 4 and the last inequality is due to the fact that Ω ⊆ Ω and Ω ⊆ {θ : ||θ|| f s ≤ r}.

For the last term, by Lemma 3, we have

E σ sup ||θ|| f s ≤r,y∈Y 1 n [ψ(θ)X] y, σ ≤ r||X|| F 2n 1 λ min (E(xx T ))

.

The other terms can be handled by Lemma 6 in the following way. Collecting all terms, we establish

L i=1 E σ sup θ∈Ω,y∈Y 1 n [V W L-i H i ] y, σ ≤ L i=1 1 n β V β U i j=1 β L-j W ||X j T || 1 ≤ L i=1 1 n β V β U i j=1 β L-j W ||X T || 1 = 1 n β V β U ||X T || 1 1 -β W 1 -β L W 1 -β W -Lβ L W for β W = 1, and L i=1 E σ sup θ∈Ω,y∈Y 1 n [V W L-i H i ] y σ ≤ 1 n β V β U B 2 L+L 2 2 for β W = 1,

E σ sup θ∈Ω,y∈Y 1 n n i=1 [y Lθ (x i )] y σ i ≤ r||X|| F 2n 1 λ min (E(xx T )) + 1 n β V β U ||X T || 1 Λ.

C PROOFS IN SECTION 3.3:

This section includes the full proofs of the generalization bound for training with random noise.

C.1 LIPSCHITZ PROPERTIES OF RELU NONLINEARITIES AND MARGIN OPERATOR:

We first establish the Lipschitz properties of the ReLU activation function and margin operator M(y L (x), y) := M y L (x, y). Lemma 9. Let ρ : R n → R n be the coordinate-wise ReLU function, then it is 1-Lipschitz according to || • || p for any p ≥ 1.

Proof. For any

x, x ∈ R n , ||ρ(x) -ρ(x )|| p = |ρ(x) i -ρ(x ) i | p 1/p ≤ |x i -x i | p 1/p = ||x -x || p .

Lemma 10. For every j and every p

≥ 1, M(•, j) is 2-Lipschitz wrt || • || p .

Proof. Let y, y , j be given, and suppose that M(y, j) ≤ M(y , j) without loss of generality. Select coordinate i = j so that M(y, j) = y j -y i . Then M(y , j) -M(y, j) = y j -max

l =j y l -y j + y i ≤ (y j -y j ) + (y i -y i ) ≤ 2||y -y|| ∞ ≤ 2||y -y || p .

C.2 PROOF OF LEMMA 8

Proof. We prove this Lemma by induction. Let

x = (x 1 , x 2 , • • • , x L ) and x = (x 1 , x 2 , • • • , x L ). Denote g t := U x t + W h t-1 , h t := ρ(g t ) and y t := V h t . Then we have ||h t -h t || ∞ = ||ρ(g t ) -ρ(g t )|| ∞ ≤ ||g t -g t || ∞ = ||U x t + W h t-1 -U x t -W h t-1 || ∞ ≤ ||U T || 1 ||x t -x t || ∞ + ||W T || 1 ||h t-1 -h t-1 || ∞ ,

where the first inequality uses Lemma 9 and the second inequality uses basic properties of || • || ∞ . By induction, we get

||h L -h L || ∞ ≤ i ||U T || 1 ||W T || L-i 1 ||x i -x i || ∞ .

Therefore,

||y L -y L || ∞ = ||V h L -V h L || ∞ ≤ ||V || ∞ ||h L -h L || ∞ ≤ i ||V T || 1 ||U T || 1 ||W T || L-i 1 ||x i -x i || ∞ .

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 (1) with weight matrices θ = (U, W, V ), the following inequality holds for any x = (x 1 , x 2 , • • • , x L ) and y.

|E [Φ α (M y L (x, y)) -Φ α (M y L (x + , y))]| ≤ 2 α i ||V T || 1 ||U T || 1 ||W T || L-i 1 (E || i || ∞ ).

Proof. For any fixed x and y,

|E [Φ α (M y L (x, y)) -Φ α (M y L (x + , y))]| ≤ E |Φ α (M y L (x, y)) -Φ α (M y L (x + , y))| ≤ 2 α E ||y L (x) -y L (x + )|| ∞ ≤ 2 α E ( i ||V T || 1 ||U T || 1 ||W T || L-i 1 || i || ∞ ) = 2 α i ||V T || 1 ||U T || 1 ||W T || L-i 1 (E || i || ∞ )

, where the first inequality uses Jensen's inequality, the second inequality follows from the 1 α -Lipschitz property of Φ α (•) and Lemma 10 and the last inequality is by Lemma 8. E(e t| i| ) = 2dΦ(σ 2 t)e σ 2 t 2 /2 ≤ 2de σ 2 t 2 /2 , where the second inequality uses the definition of normal distribution and Φ is the cumulative distribution function of the standard normal distribution. Taking logs on both sides and dividing by t, we get

E(Z) ≤ log(2d) t + σ 2 t 2 .

Choosing t = 2log(2d) σ leads to the desired result, E(Z) ≤ σ 2 log(2d).

We now return to the proof of Theorem 3. 

α i β V β U β L-i W (E || i || ∞ )

,

where the first equality is due to the fact that the input x and noise are independent, the first inequality uses Jensen's inequality and the last inequality follows from Lemma 11. The inequality above can be rewritten as follows.

E x,y [Φ α (M y L (x, y))] ≤ E x, ,y [Φ α (M y L (x + , y))

+ 2 α i β V β U β L-i W (E || i || ∞ ) .

For the first term in the right hand side of the above inequality, by Theorem 2, with probability at least 1 -δ, the following holds:

E x, ,y [Φ α (M y L (x + , y)) ≤ 4k α r||X + X || F 2n 1 λ min (E((x + )(x + ) T )) + 1 n β V β U ||X T + X T || 1 Λ + 3 log 2 δ 2n + 1 n Φ α (M y L (x i + i , y i )) = 4k α r||X + X || F 2n 1 λ min (E(xx T ) + E( T )) + 1 n β V β U ||X T + X T || 1 Λ + 3 log 2 δ 2n + 1 n Φ α (M y L (x i + i , y i )) = 4k α r||X + X || F 2n 1 λ min (E(xx T ) + σ 2 I) + 1 n β V β U ||X T + X T || 1 Λ + 3 log 2 δ 2n + 1 n Φ α (M y L (x i + i , y i )) = 4k α r||X + X || F 2n 1 λ min (E(xx T )) + σ 2 + 1 n β V β U ||X T + X T || 1 Λ + 3 log 2 δ 2n + 1 n Φ α (M y L (x i + i , y i ))

.

Combining the above two inequalities together leads to

E[1 My L (x,y)≤0 ] ≤ E x,y [Φ α (M y L (x, y))] ≤ 1 n Φ α (M y L (x i + i , y i )) + 2 α i β V β U β L-i W (E || i || ∞ )+ 4k α r||X + X || F 2n 1 λ min (E(xx T )) + σ 2 + 1 n β V β U ||X T + X T || 1 Λ + 3 log 2 δ 2n

, where the first inequality makes use of the fact that 1 u ≤ Φ α (u). Therefore, the desired result can be immediately obtained by substituting E || i || ∞ with σ 2 log(2d) according to Lemma 12.

D SUPPLEMENTARY FIGURES:

Figure 2 shows the behavior of generalization error for RNNs as the standard derivation of noise σ varies for the sequence length L = 200 and 300 trained on IMDB dataset. As in the body, increasing σ will first improve the generalization error and then, after a certain point, harm the performance of RNNs. ) and L = 300 (smallest eigenvalue: 2.5 × 10 -5 ) respectively.

:



Figures and Tables:

Figure 1: Generalization error for training with noise (mean ± standard error averaged on 5 runs).

where the second inequality uses the definition of matrix norm || • || 1 .

Let { i } d i=1 be an i.i.d sequence of N (0, σ 2 ) variables, then E[max i | i |] ≤ σ 2 log(2d). Proof. Define Z = [max i | i |].For any t > 0, by Jensen' inequality, we have e tE(Z) ≤ E(e tZ ) = E(max i e t| i| ) ≤ i

For any RNNs with weight matrices θ = (U, W, V ) satisfying||V T || 1 ≤ β V , ||W T || 1 ≤ β W , ||U T || 1 ≤ β U , we have |E x,y [Φ α (M y L (x, y))] -E x, ,y [Φ α (M y L (x + , y))| = |E x,y (Φ α (M y L (x, y)) -E [Φ α (M y L (x + , y))])| ≤ E x,y |Φ α (M y L (x, y)) -E [Φ α (M y L (x + , y))]| ≤ 2

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: 1 × 10 -4 ) and L = 300 (smallest eigenvalue: 2.5 × 10 -5 ) respectively.

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.

Table content: <table/>

For a vector, we denote the l p norm by ||v|| p = ( |v i | p ) 1/p and the l ∞ norm by ||v|| ∞ = max |v i |. For a matrix, we denote the matrix p-norm as ||A|| p = max ||x||p=1 ||Ax|| p , the matrix 1-norm by ||A|| 1 = max j { i |a ij |} and the Frobenius norm by ||A|| 2 F = trace(AA

Table content: <table/>

Peer review (iclr2020):
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. This work has the potential to be of interest for the learning theory community on theoretical properties of recurrent neural networks. One 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?