UNDERSTANDING GENERALIZATION IN RECURRENT NEURAL NETWORKS
Year: 2020

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.

heading: 1 INTRODUCTION
text: 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 lp-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.
• 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 a new technique to decompose RNNs with ReLU 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 decomposition technique can potentially be applied to 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 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.

heading: 2 PRELIMINARIES
text: We focus on the vanilla RNNs with ReLU activation. Let U ∈ Rm×d, V ∈ Rk×m and W ∈ Rm×m be the weight matrices. Given the input sequence x = (x1, x2, · · · , xL) ∈ RLd where each xi ∈ Rd and L is the input sequence length, the vanilla RNNs can be described as follows.
gt = Uxt +Wht−1, ht = ρ(gt), yt = V ht,
(1)
where gt and ht ∈ Rm represents the input and output of hidden layer at step t, ρ(·) is the ReLU function and yt ∈ Rk denotes the output value at step t. For simplicity, in this paper, we only consider the final output yL. We assume that data (x, y) is drawn i.i.d. from some unknown distribution D over RLd × Y where Y represents the label space {1, 2, · · · , k}. The RNNs above define a mapping yL(x) from RLd → Rk, where k is the number of classes. We convert yL(x) to a classifier by selecting the output coordinate with the largest magnitude, meaning x→ argmaxi[yL(x)]i, where [·]i represents the i-th element of a vector. This naturally leads to the definition of margin MyL(x, y) of the output yL at a labeled example (x, y):
MyL(x, y) = [yL(x)]y −max y′ 6=y [yL(x)]y′ .
Thus, yL misclassifies (x, y) if and only ifMyL(x, y) ≤ 0. The quality of the prediction made by yL is measured by the expected risk defined as
E(x,y)∼D[1MyL (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 (1MyL (xi,yi)≤α).
The generalization error is then the difference between expected risk and empirical risk, defined as
E(x,y)∼D[1MyL (x,y)≤0]− 1
n n∑ i=1 (1MyL (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. For a vector, we denote the lp norm by ||v||p = ( ∑ |vi|p)1/p and the l∞ norm by ||v||∞ = max |vi|. 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 = maxj{ ∑ i |aij |} and the Frobenius norm by ||A||2F = trace(AAT ). The smallest eigenvalue of a matrix A is given by λmin(A). The activation function ρ and its derivative ρ′ are entrywise, i.e., ρ(A) = (ρ(aij))ij and ρ′(v) = (ρ′(vi))i. We denote c = (L + 1, L, · · · , 2)T , η(θ) = [V diag(ρ′(gL))...Wdiag(ρ ′(g1))Ux1, V diag(ρ ′(gL))...Wdiag(ρ
′(g2))Ux2, · · · , V diag(ρ′(gL)) UxL] ∈ Rk×L and τ(θ) = (VWL−1Ux1, V WL−2Ux2, · · · , V UxL) where θ = (U,W, V ) and diag converts a vector into a diagonal matrix.

heading: 3 MAIN RESULT
text: 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.

heading: 3.1 FISHER-RAO NORM FOR RNNS
text: 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 = (x1, x2, · · · , xL), consider the recurrent neural network in (1), we have the identity ∑
a,b
∂yL ∂vab vab + ∑ i,j ∂yL ∂wij wij + ∑ p,q ∂yL ∂upq upq = η(θ)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
||θ||2fr :=< θ, I(θ)θ >,
where I(θ) = E(∇l(yLθ(x), y)⊗∇l(yLθ(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),
||θ||2fr = E (〈 η(θ)c, ∂l(yLθ(x), y)
∂yLθ
〉2) .
Remark 1. We observe that each term V diag(ρ′(gL))...Wdiag(ρ′(gi))Uxi 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(yLθ(x), y) = Φα(MyL(x, y)) where α > 0 is the margin parameter, one might upper bound the Fisher-Rao norm in Lemma 2 by
||θ||2fr ≤ 4 α2 E ( max i [(τ(θ)c)i] 2 ) ,
since 〈 τ(θ)c, ∂l(yLθ(x), y)
∂yLθ 〉2 ≤ 4α2 maxi[(τ(θ)c)i]2 by definition of MyL(x, y) and lipschitz property of Φα(·). We define this upper bound as
||θ||2fs := E (
max i
[(τ(θ)c)i] 2 ) , (2)
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 || · ||fs to derive generalization bound for RNNs.

heading: 3.2 GENERALIZATION BOUND FOR RNNS
text: 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., yL = ψ(θ)x + (yL − ψ(θ)x). For the linear network part ψ(θ)x, the Rademacher complexity can be bounded directly by Fisher-Rao norm. For the difference term (yL − ψ(θ)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 Fr := {x → [ψ(θ)x]y : ||θ||fs ≤ r, y ∈ Y} where x ∈ RLd and ψ(θ) := (VWL−1U, V WL−2U, · · · , V U). For any data x1, x2, · · · , xn drawn i.i.d from the distribution D, collect them as columns of a matrix X ∈ RLd×n. Then we have
R̂n(Fr) ≤ r||X||F
2n
√ 1
λmin(E(xxT )) ,
assuming that E(xxT ) is positive definite.
Remark 2. If E(x) = 0, E(xxT ) is the covariance matrix of random variable x.
Remark 3. We should mention that our assumption that E(xxT ) 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(xxT ) is positive definite as follows. Suppose that x is a continuous random variable in the n-dimensional subspaceX ⊂ Rn. If there exists u ∈ Rn such that uTE(xxT )u = 0, then for any x ∈ X we have uTx = 0, i.e., u ⊥ X . Since X is n-dimensional, the only u that satisfies is that u = 0. Therefore, by definition, E(xxT ) 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 yL − ψ(θ)x. With a slight abuse of notations, given input data x1, x2, · · · , xn ∈ RLd, the corresponding g1, g2, · · · , gn ∈ RLm and h1, h2, · · · , hn ∈ RLm 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 Xt, all input of the hidden layer at time t as a matrix denoted by Gt and all output of hidden layer at time t denoted by Ht, where X ∈ RLd×n, Xt ∈ Rd×n, Gt ∈ Rm×n, Ht ∈ Rm×n and t = 1, · · · , L. The difference term can be decomposed by the following lemma. Lemma 4. Define H ′′t := Ht −Gt. Then the following equality holds
V HL − ψ(θ)X = L∑ i=1 VWL−iH ′′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 )||Gt||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 , ||WT ||1 ≤ βW , ||UT ||1 ≤ βU}. Then for any i = 1, · · · , L, we have
Eσ (
sup θ∈Ω,y∈Y
1 n [VWL−iH ′′i ]y,σ ) ≤ 1 n βV βU i∑ j=1 βL−jW ||Xj 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 , ||WT ||1 ≤ βW , ||UT ||1 ≤ βU , ||θ||fs ≤ r}. Then, the empirical Rademacher complexity of RNNs with ReLU can be bounded as follows
Eσ (
sup θ∈Ω,y∈Y
1
n
∑n i=1[yLθ(xi)]yσi ) ≤ r||X||F
2n
√ 1
λmin(E(xxT )) +
1 n βV βU ||XT ||1Λ ,
where Λ := 11−βW (1− βLW
1− βW − LβLW
) if βW 6= 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 ⊆ RX×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 Φα(Mh(xi, yi)) + 4k α R̂n(Π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 , ||WT ||1 ≤ βW , ||UT ||1 ≤ βU and ||θ||fs ≤ r:
E[1MyL (x,y)≤0] ≤ 1
n
∑ 1MyL (xi,yi)≤a + 4k
α (r||X||F 2n
√ 1
λmin(E(xxT )) +
1 n βV βU ||XT ||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 Õ(max{d,m, k}L 2||U ||2||V ||2 max{1, ||W ||L2 }√
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 L2 factor in their bound, whereas the L2 term only occurs in our bound when ||WT ||1 = 1. For the case that ||WT || > 1, our bound has only a linear dependence on L, and for the case that ||WT ||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.

heading: 3.3 GENERALIZATION BOUND FOR TRAINING WITH RANDOM NOISE
text: The generalization bound in Theorem 2 requires the input covariance matrix E(xxT ) 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(xxT ) in the bound becomes E((x + )(x + )T ) and the smallest eigenvalue of E((x + )(x + )T ) is (λmin(E(xxT )) + σ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) ∈ RLd. 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 ), yL is Lipschitz with respect to || · ||∞, i.e.,
||yL(x)− yL(x′)||∞ ≤ ∑ i ||V T ||1||UT ||1||WT ||L−i1 ||xi − x′i||∞
for any x = (x1, x2, · · · , xL), x′ = (x′1, x′2, · · · , x′L) ∈ RLd.
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 ((x1, 1, y1), (x2, 2, y2), · · · , (xn, n, yn)), the following holds for every RNN whose weight matrices θ = (U,W, V ) satisfy ||V T ||1 ≤ βV , ||WT ||1 ≤ βW , ||UT ||1 ≤ βU and ||θ||fs ≤ r:
E[1MyL (x,y)≤0] ≤ 1
n
∑ Φα(MyL(xi + i, yi)) + 2
α
∑ i βV βUβ L−i W σ √ 2 log(2d) + 3 √ log 2δ 2n +
4k
α (r||X +X ||F 2n
√ 1
λmin(E(xxT )) + σ2 +
1 n βV βU ||XT +XT ||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(xxT ) is very close to 0. For example, when λmin(E(xxT )) = 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((xxT )))+σ2 ≤ 10. Notice that adding noise can not always
guarantee an improved generalization especially when λmin(E(xxT )) 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(xxT ) is very small. For this case, a small noise such as σ = 0.1 not only can greatly improve the term √ 1
λmin(E(xxT )) 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 ||θ||fs ≤ 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 βUB( 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(xxT ) 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 50- dimensional vector. We train vanilla RNNs with ReLU activation function for sequence length L = 100. The corresponding smallest eigenvalue of E(xxT ) 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.

heading: 3.4 ANALYSIS OF GENERALIZATION BOUND
text: 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(xxT )
According to our results, the generalization performance in RNNs is influenced by the smallest eigenvalue of E(xxT ). 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(xxT ) 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 6=i |ξij | ≤ ζ for any i. Then by simple derivation, we obtain ξii − ∑ j 6=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 6= 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.

heading: 3.4.2 GENERALIZATION AND TRAINABILITY
text: 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 ||XT ||1Λ in the generalization bound would be small when βW is not so close to 1. Similarly, if λmin(E(xxT )) 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.

heading: 3.4.3 GENERALIZATION AND GRADIENT MEASURE
text: 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 ||xT ||1 ≤ B, by the definition of || · ||fs in (2), for any y ∈ Y , we have
((τ(θ)c)y )2 = ((L+ 1)[V ]y,W L−1Ux1 + L[V ]y,W
L−2Ux2 + · · ·+ 2[V ]y,UxL)2 ≤ (|(L+ 1)[V ]y,WL−1Ux1|+ |L[V ]y,WL−2Ux2|+ · · ·+ |2[V ]y,UxL|)2 ≤ ((L+ 1)βV βUBβL−1W + LβV βUBβ L−2 W + 2βV βUB) 2 = (βV βUB( βW−βLW (1−βW )2 + 2−(L+1)βLW 1−βW )) 2 ≤ (βV βUB( 1(1−βW )2 + 1 1−βW )) 2 ,
for βW < 1, and ((τ(θ)c)y )2 ≤ (βV βUB 3L+L22 )2 for βW = 1. The above inequality holds
for any x and y. So we can get ||θ||fs = E ( maxi[(τ(θ)c)i] 2 )1/2 ≤ βV βUB( 1(1−βW )2 + 11−βW ) for βW < 1. By replacing r with βV βUB( 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 βUB( 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(xxT ) is small. Therefore the introduction of Fisher-Rao norm can help eliminate the negative effect of λmin(E(xxT )) and thus improve the generalization bound.

heading: 4 CONCLUSION
text: 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 ||WT ||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.

heading: ACKNOWLEDGMENTS
text: This work was supported by Australian Research Council Project FL-170100117. We would like to thank Gemeng Zhang from Tulane University for helpful discussions and all the reviewers for their constructive comments.

heading: A PROOFS IN SECTION 3.1

heading: A.1 PROOF OF LEMMA 1
text: Proof. To begin with, by equation (1), we have yL = V hL. Then the derivative of yL with respect to vab can be calculated as
∂yL ∂vab = (0, 0, · · · , [hL]b, · · · , 0)T ,
i.e., a k-dimensional vector with a-th element [hL]b and all other elements zero. Multiplying both sides by vab and summing them up, we get∑
a,b
∂yL ∂vab vab = V hL = yL.
The derivative of yL with respect to W and U can be derived by using chain rule in the similar way as follows.
∂yL ∂wij = V ∂hL ∂wij ∂hL ∂wij = diag(ρ′(gL))(0, · · · , [hL−1]j , · · · , 0)T + diag(ρ′(gL))W ∂hL−1 ∂wij
and ∂yL ∂upq = V ∂hL ∂upq
∂hL ∂upq = diag(ρ′(gL))(0, · · · , [xL]q, · · · , 0)T + diag(ρ′(gL))W ∂hL−1 ∂upq
,
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 ∂hL ∂wij wij + ∑ p,q ∂hL ∂upq upq
= diag(ρ′(gL))( ∑ i,j (0, · · · , [hL−1]j , · · · , 0)Twij + ∑ p,q (0, · · · , [xL]q, · · · , 0)Tupq) + diag(ρ′(gL))
W ( ∑ i,j ∂hL−1 ∂wij wij + ∑ p,q ∂hL−1 ∂upq upq)
= diag(ρ′(gL))(WhL−1 + UxL) + diag(ρ ′(gL))W ( ∑ i,j ∂hL−1 ∂wij wij + ∑ p,q ∂hL−1 ∂upq upq)
= hL + diag(ρ ′(gL))W ( ∑ i,j ∂hL−1 ∂wij wij + ∑ p,q ∂hL−1 ∂upq upq).
For ease of exposition, define fL := ∑ i,j ∂hL ∂wij wij + ∑ p,q ∂hL ∂upq upq . Then the above equality can be rewritten as fL = hL + diag(ρ ′(gL))WfL−1.
By induction, we have
fL = hL + diag(ρ ′(gL))WhL−1 + diag(ρ ′(gL))Wdiag(ρ ′(gL−1))WhL−2+
diag(ρ′(gL))Wdiag(ρ ′(gL−1))...Wdiag(ρ ′(g2))Wh1 .
Multiplying both sides by V and using some basic calculation, we can show that V fL = LyL − η(θ)(0, 1, · · · , L− 1)T . Therefore,∑ a,b ∂yL ∂vab vab + ∑ i,j ∂yL ∂wij wij + ∑ p,q ∂yL ∂upq upq = yL + V fL = (L+ 1)yL − η(θ)(0, 1, · · · , L− 1)T .
Substituting yL = η(θ)(1, 1, · · · , 1)T into the above equality leads to the desired result∑ a,b ∂yL ∂vab vab + ∑ i,j ∂yL ∂wij wij + ∑ p,q ∂yL ∂upq upq = η(θ)c .

heading: A.2 PROOF OF LEMMA 2
text: Proof. Using the definition of Fisher-Rao norm,
||θ||2fr = E(< θ,∇l(yLθ, y) >2) = E(< θ,∇yLθ(x) ∂l(yLθ, y)
∂yLθ >2)
= E((θT∇yLθ(x) ∂l(yLθ, y)
∂yLθ )2) = E(< ∇yLθ(x)T θ,
∂l(yLθ, y)
∂yLθ >2)
.
By Lemma 1, we have∇yLθ(x)T θ = η(θ)c. Substituting it into the above equality gives us ||θ||2fr = E (〈 η(θ)c, ∂l(yLθ(x), y)
∂yLθ
〉2) .

heading: B PROOFS IN SECTION 3.2

heading: B.1 PROOF OF LEMMA 3
text: The proof of Lemma 3 relies on the following result in Saniuk & Rhodes (1987). Proposition 1. Let X, Y∈ Rn×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)xT1 , LxT2 , · · · , 2xTL)T ((L+ 1)xT1 , LxT2 , · · · , 2xTL)). By the definition of ||θ||fs, for any y ∈ Y , we have
||[ψ(θ)]y,T ||2A = [ψ(θ)]y,E(((L+ 1)xT1 , LxT2 , · · · , 2xTL)T ((L+ 1)xT1 , LxT2 , · · · , 2xTL))[ψ(θ)]y, T = E([ψ(θ)]y,((L+ 1)xT1 , LxT2 , · · · , 2xTL)T ((L+ 1)xT1 , LxT2 , · · · , 2xTL)[ψ(θ)]y, T
) = E([(τ(θ)c)y]2) ≤ ||θ||2fs
,
where [ψ(θ)]y, represents the y-th row of ψ(θ). On the other hand, from the definition of Rademacher complexities,
R̂n(Fr) = Eσ( sup f∈Fr
1
n
∑n i=1 f(xi)σi) = Eσ(sup
θ,y
1
n
∑n i=1[ψ(θ)xi]yσi) = Eσ(sup
θ,y
1
n
∑n i=1[ψ(θ)]y,xiσi)
= Eσ(sup θ,y
< 1
n
∑n i=1 xiσi, [ψ(θ)]y, T >) ≤ Eσ(sup
θ,y (|| 1 n
∑n i=1 xiσi||A−1 ||[ψ(θ)]y, T ||A))
≤ rEσ(|| 1
n
∑n i=1 xiσi||A−1) = rEσ √ < ( 1
n
∑n i=1 xiσi)( 1
n
∑n i=1 x T i σi), A −1 >
≤ r √ Eσ < ( 1
n
∑n i=1 xiσi)( 1
n
∑n i=1 x T i σi), A −1 > = r
√ 1
n2 < ∑n i=1 xix T i , A −1 >
= r
n
√ < XXT , A−1 > = r
n
√ < XXT , (CE(xxT )C)−1 > = r
n
√ trace(XXTC−1(E(xxT ))−1C−1)
,
where the first inequality uses Cauchy-Schwarz inequality andC := diag((L+1)Id, LId, · · · , 2Id). Since C−1 and E(xxT ) are positive definite, we have trace(XXTC−1(E(xxT ))−1C−1) = trace(C−1(E(xxT ))−1C−1XXT ) ≤ ||C−1(E(xxT ))−1C−1||2trace(XXT ) ≤ ||C−1||2||(E(xxT ))−1||2||C−1||2trace(XXT )
= 14 ||(E(xx T ))−1||2||X||2F ≤
1
4 ||X||2F λmin(E(xxT ))
,
where the first inequality is by Proposition 1 and the last inequality uses trace(XXT ) = ||X||2F . Therefore,
R̂n(Fr) ≤ r||X||F
2n
√ 1
λmin(E(xxT )) .

heading: B.2 PROOF OF LEMMA 4
text: Proof. Denote H ′t := UXt +WH ′ t−1 and H ′ 1 := UX1. By the definition of HL, we have
HL −H ′L = ρ(UXL +WHL−1)− UXL −WH ′L−1 = ρ(UXL +WHL−1)− UXL −WHL−1 +W (HL−1 −H ′L−1) = H ′′L +W (HL−1 −H ′L−1) ,
which by induction gives
HL −H ′L = H ′′L +WH ′′L−1 + · · ·+WL−1(H1 −H ′1) = ∑L i=1W L−iH ′′i .
So the difference term can be rewritten as
V HL − ψ(θ)X = V HL − V H ′L = ∑L i=1 VW L−iH ′′i ,
where the second equality uses ψ(θ)X = V H ′L.

heading: B.3 PROOF OF LEMMA 5
text: Proof. Using Riesz-Thorin Theorem, we have ||H ′′t ||p ≤ ||H ′′t || 1/p 1 ||H ′′t || 1−1/p ∞ . And since H ′′t = ρ(Gt) − Gt, by the definition of the induced L1 and L∞ matrix norm, we know ||H ′′t ||1 ≤ ||Gt||1 and ||H ′′t ||∞ ≤ ||Gt||∞. Therefore,
||H ′′t ||p ≤ ||H ′′t || 1/p 1 ||H ′′t || 1−1/p ∞ ≤ ||Gt||1/p1 ||Gt|| 1−1/p ∞ ≤ m 1 p (1− 1 p )n 1 p (1− 1 p )||Gt||p ,
where the last inequality uses some basic facts about matrix norm that ||Gt||1 ≤ m1−1/p||Gt||p and ||Gt||∞ ≤ n1/p||Gt||p.

heading: B.4 PROOF OF LEMMA 6
text: Proof. For any y ∈ Y , by Hölder’s inequality, for any p, q ≥ 1 with 1p + 1 q = 1,
1 n [VW L−iH ′′i ]y,σ = 1 n [V ]y,W L−iH ′′i σ ≤ 1n ||H ′′ i T WT L−i [V ]y, T ||p||σ||q = ||[V ]y,T ||p||WT ||L−ip ||H ′′i T ||pn1/q−1 ≤ ||[V ]y,T ||p||WT ||L−ip m 1 p (1− 1 p )n − 1 p2 ||GiT ||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 1n [VW L−iH ′′i ]y,σ ≤ ||[V ]y, T ||1||WT ||L−i1 n−1||Gi T ||1 ≤ βV βL−iW n−1||Gi T ||1 ≤ βV β L−i W n −1(βU ||XiT ||1 + βW ||Hi−1T ||1). For ||Hi−1T ||1, we have
||Hi−1T ||1 = ||ρ(Xi−1TUT +Hi−1TWT )||1 ≤ ||Xi−1TUT +Hi−2TWT ||1 ≤ βU ||Xi−1T ||1 + βW ||Hi−2T ||1 ,
which by induction gives
||Hi−1T ||1 ≤ βU i−1∑ j=1 βi−1−jW ||Xj T ||1.
Therefore,
Eσ (
sup θ∈Ω,y∈Y
1 n [VWL−iH ′′i ]y,σ ) ≤ 1 n βV βU i∑ j=1 βL−jW ||Xj T ||1.

heading: B.5 PROOF OF THEOREM 1
text: 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[yLθ(xi)]yσi ) = Eσ ( sup
θ∈Ω,y∈Y
1 n [V HL]y,σ ) = Eσ ( sup
θ∈Ω,y∈Y
1 n [ ∑L i=1 VW L−iH ′′i + ψ(θ)X]y,σ )
≤ ∑L i=1 Eσ ( sup
θ∈Ω,y∈Y
1 n [VWL−iH ′′i ]y,σ
) + Eσ ( sup
θ∈Ω,y∈Y
1 n [ψ(θ)X]y,σ ) ≤ ∑L i=1 Eσ ( sup
θ∈Ω,y∈Y
1 n [VWL−iH ′′i ]y,σ
) + Eσ ( sup
||θ||fs≤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 Ω ⊆ {θ : ||θ||fs ≤ r}. For the last term, by Lemma 3, we have
Eσ (
sup ||θ||fs≤r,y∈Y
1 n [ψ(θ)X]y,σ
) ≤ r||X||F
2n
√ 1
λmin(E(xxT )) .
The other terms can be handled by Lemma 6 in the following way.∑L i=1 Eσ ( sup
θ∈Ω,y∈Y
1 n [VWL−iH ′′i ]y,σ
) ≤ ∑L i=1 ( 1 nβV βU ∑i j=1 β L−j W ||Xj T ||1 )
≤ ∑L i=1 ( 1 nβV βU ∑i j=1 β L−j W ||XT ||1 ) = 1
n βV βU ||XT ||1 1− βW (1− βLW 1− βW − LβLW )
for βW 6= 1, and ∑L i=1 Eσ ( sup
θ∈Ω,y∈Y
1 n [VWL−iH ′′i ]yσ ) ≤ 1nβV βUB2 L+L2 2 for βW = 1, where the
second inequality uses the definition of matrix norm || · ||1. Collecting all terms, we establish
Eσ (
sup θ∈Ω,y∈Y
1
n
∑n i=1[yLθ(xi)]yσi ) ≤ r||X||F
2n
√ 1
λmin(E(xxT )) +
1 n βV βU ||XT ||1Λ.

heading: C PROOFS IN SECTION 3.3
text: This section includes the full proofs of the generalization bound for training with random noise.

heading: C.1 LIPSCHITZ PROPERTIES OF RELU NONLINEARITIES AND MARGIN OPERATOR
text: We first establish the Lipschitz properties of the ReLU activation function and margin operator M(yL(x), y) :=MyL(x, y). Lemma 9. Let ρ : Rn → Rn be the coordinate-wise ReLU function, then it is 1-Lipschitz according to || · ||p for any p ≥ 1.
Proof. For any x, x′ ∈ Rn,
||ρ(x)− ρ(x′)||p = (∑ |ρ(x)i − ρ(x′)i|p )1/p ≤ (∑ |xi − 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 thatM(y, j) ≤M(y′, j) without loss of generality. Select coordinate i 6= j so thatM(y, j) = yj − yi. Then
M(y′, j)−M(y, j) = y′j−max l 6=j y′l−yj +yi ≤ (y′j−yj)+(yi−y′i) ≤ 2||y′−y||∞ ≤ 2||y−y′||p.

heading: C.2 PROOF OF LEMMA 8
text: Proof. We prove this Lemma by induction. Let x = (x1, x2, · · · , xL) and x′ = (x′1, x′2, · · · , x′L). Denote g′t := Ux ′ t +Wh ′ t−1, h ′ t := ρ(g ′ t) and y ′ t := V h ′ t. Then we have
||ht − h′t||∞ = ||ρ(gt)− ρ(g′t)||∞ ≤ ||gt − g′t||∞ = ||Uxt +Wht−1 − Ux′t −Wh′t−1||∞ ≤ ||UT ||1||xt − x′t||∞ + ||WT ||1||ht−1 − h′t−1||∞,
where the first inequality uses Lemma 9 and the second inequality uses basic properties of || · ||∞. By induction, we get
||hL − h′L||∞ ≤ ∑ i ||UT ||1||WT ||L−i1 ||xi − x′i||∞.
Therefore, ||yL−y′L||∞ = ||V hL−V h′L||∞ ≤ ||V ||∞||hL−h′L||∞ ≤ ∑ i ||V T ||1||UT ||1||WT ||L−i1 ||xi−x′i||∞.

heading: C.3 PROOF OF THEOREM 3
text: 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 = (x1, x2, · · · , xL) and y.
|E [Φα(MyL(x, y))− Φα(MyL(x+ , y))]| ≤ 2
α ∑ i ||V T ||1||UT ||1||WT ||L−i1 (E || i||∞).
Proof. For any fixed x and y,
|E [Φα(MyL(x, y))− Φα(MyL(x+ , y))]| ≤ E |Φα(MyL(x, y))− Φα(MyL(x+ , y))| ≤ 2 α E ||yL(x)− yL(x+ )||∞ ≤ 2 α E ( ∑ i ||V T ||1||UT ||1||WT || L−i 1 || i||∞) = 2
α
∑ i ||V T ||1||UT ||1||WT || 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. Lemma 12. Let { i}di=1 be an i.i.d sequence of N (0, σ2) variables, then E[maxi | i|] ≤ σ √ 2 log(2d).
Proof. Define Z = [maxi | i|]. For any t > 0, by Jensen’ inequality, we have
etE(Z) ≤ E(etZ) = E(max i et| i|) ≤ ∑ i E(et| i|) = 2dΦ(σ2t)eσ 2t2/2 ≤ 2deσ 2t2/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 + σ2t 2 .
Choosing t =
√ 2log(2d)
σ leads to the desired result, E(Z) ≤ σ √ 2 log(2d).
We now return to the proof of Theorem 3.
Proof. For any RNNs with weight matrices θ = (U,W, V ) satisfying ||V T ||1 ≤ βV , ||WT ||1 ≤ βW , ||UT ||1 ≤ βU , we have
|Ex,y[Φα(MyL(x, y))]− Ex, ,y[Φα(MyL(x+ , y))| = |Ex,y(Φα(MyL(x, y))− E [Φα(MyL(x+ , y))])| ≤ Ex,y|Φα(MyL(x, y))− E [Φα(MyL(x+ , y))]| ≤ 2
α
∑ 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.
Ex,y[Φα(MyL(x, y))] ≤ Ex, ,y[Φα(MyL(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: Ex, ,y[Φα(MyL(x+ , y))
≤ 4k α (r||X +X ||F 2n
√ 1
λmin(E((x+ )(x+ )T )) +
1 n βV βU ||XT +XT ||1Λ
) + 3 √ log 2δ 2n +
1
n
∑ Φα(MyL(xi + i, yi))
= 4k
α (r||X +X ||F 2n
√ 1
λmin(E(xxT ) + E( T )) +
1 n βV βU ||XT +XT ||1Λ
) + 3 √ log 2δ 2n +
1
n
∑ Φα(MyL(xi + i, yi))
= 4k
α (r||X +X ||F 2n
√ 1
λmin(E(xxT ) + σ2 I) +
1 n βV βU ||XT +XT ||1Λ
) + 3 √ log 2δ 2n +
1
n
∑ Φα(MyL(xi + i, yi))
= 4k
α (r||X +X ||F 2n
√ 1
λmin(E(xxT )) + σ2 +
1 n βV βU ||XT +XT ||1Λ
) + 3 √ log 2δ 2n +
1
n
∑ Φα(MyL(xi + i, yi))
.
Combining the above two inequalities together leads to
E[1MyL (x,y)≤0] ≤ Ex,y[Φα(MyL(x, y))] ≤ 1 n ∑ Φα(MyL(xi + i, yi)) + 2 α ∑ i βV βUβ L−i W (E || i||∞)+
4k
α (r||X +X ||F 2n
√ 1
λmin(E(xxT )) + σ2 +
1 n βV βU ||XT +XT ||1Λ
) + 3 √ log 2δ 2n ,
where the first inequality makes use of the fact that 1u ≤ Φα(u). Therefore, the desired result can be immediately obtained by substituting E || i||∞ with σ √ 2 log(2d) according to Lemma 12.

heading: D SUPPLEMENTARY FIGURES
text: 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.

Review summaries:
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.