Title: STABILIZING GRADIENTS FOR DEEP NEURAL NET-WORKS VIA EFFICIENT SVD PARAMETERIZATION

Abstract: Vanishing and exploding gradients are two of the main obstacles in training deep neural networks, especially in capturing long range dependencies in recurrent neural networks (RNNs). In this paper, we present an efficient parametrization of the transition matrix of an RNN that allows us to stabilize the gradients that arise in its training. Specifically, we parameterize the transition matrix by its singular value decomposition (SVD), which allows us to explicitly track and control its singular values. We attain efficiency by using tools that are common in numerical linear algebra, namely Householder reflectors for representing the orthogonal matrices that arise in the SVD. By explicitly controlling the singular values, our proposed svdRNN method allows us to easily solve the exploding gradient problem and we observe that it empirically solves the vanishing gradient issue to a large extent. We note that the SVD parameterization can be used for any rectangular weight matrix, hence it can be easily extended to any deep neural network, such as a multi-layer perceptron. Theoretically, we demonstrate that our parameterization does not lose any expressive power, and show how it potentially makes the optimization process easier. Our extensive experimental results also demonstrate that the proposed framework converges faster, and has good generalization, especially in capturing long range dependencies, as shown on the synthetic addition and copying tasks.

1. INTRODUCTION:

Deep neural networks have achieved great success in various fields, including computer vision, speech recognition, natural language processing, etc. Despite their tremendous capacity to fit complex functions, optimizing deep neural networks remains a contemporary challenge. Two main obstacles are vanishing and exploding gradients, that become particularly problematic in Recurrent Neural Networks (RNNs) since the transition matrix is identical at each layer, and any slight change to it is amplified through recurrent layers (Bengio et al. (1994) ).

Several methods have been proposed to solve the issue, for example, Long Short Term Memory (LSTM) (Hochreiter & Schmidhuber (1997) ) and residual networks (He et al. (2016) ). Another recently proposed class of methods is designed to enforce orthogonality of the square transition matrices, such as unitary and orthogonal RNNs (oRNN) (Arjovsky et al. (2016) ; Mhammedi et al. (2017) ). However, while these methods solve the exploding gradient problem, they limit the expressivity of the network.

In this paper, we present an efficient parametrization of weight matrices that arise in a deep neural network, thus allowing us to stabilize the gradients that arise in its training, while retaining the desired expressive power of the network. In more detail we make the following contributions:

• We propose a method to parameterize weight matrices through their singular value decomposition (SVD). Inspired by (Mhammedi et al. (2017) ), we attain efficiency by using tools that are common in numerical linear algebra, namely Householder reflectors for representing the orthogonal matrices that arise in the SVD. The SVD parametrization allows us to retain the desired expressive power of the network, while enabling us to explicitly track and control singular values. • We apply our SVD parameterization to recurrent neural networks to exert spectral constraints on the RNN transition matrix. Our proposed svdRNN method enjoys similar space and time complexity as the vanilla RNN. We empirically verify the superiority of svdRNN over RNN/oRNN, in some case even LSTMs, over an exhaustive collection of time series classification tasks and the synthetic addition and copying tasks, especially when the network depth is large.

• Theoretically, we show how our proposed SVD parametrization can make the optimization process easier. Specifically, under a simple setting, we show that there are no spurious local minimum for the linear svdRNN in the population risk.

• Our parameterization is general enough to eliminate the gradient vanishing/exploding problem not only in RNNs, but also in various deep networks. We illustrate this by applying SVD parametrization to problems with non-square weight matrices, specifically multi-layer perceptrons (MLPs) and residual networks.

We now present the outline of our paper. In Section 2, we discuss related work, while in Section 3 we introduce our SVD parametrization and demonstrate how it spans the whole parameter space and does not limit expressivity. In Section 4 we propose the svdRNN model that is able to efficiently control and track the singular values of the transition matrices, and we extend our parameterization to non-square weight matrices and apply it to MLPs in Section 5. Section 6 provides the optimization landscape of svdRNN by showing that linear svdRNN has no spurious local minimum. Experimental results on MNIST and a popular time series archive are present in Section 7. Finally, we present our conclusions and future work in Section 8.

2. RELATED WORK:

Numerous approaches have been proposed to address the vanishing and exploding gradient problem.

Long short-term memory (LSTM) (Hochreiter & Schmidhuber (1997) ) attempts to address the vanishing gradient problem by adding additional memory gates. Residual networks (He et al. (2016) ) pass the original input directly to the next layer in addition to the original layer output. Mikolov (2012) performs gradient clipping, while Pascanu et al. (2013) applies spectral regularization to the weight matrices. Other approaches include introducing L 1 or L 2 penalization on successive gradient norm pairs in back propagation (Pascanu et al. (2013) ).

Recently the idea of restricting transition matrices to be orthogonal has drawn some attention. Le et al. (2015) proposed initializing recurrent transition matrices to be identity or orthogonal (IRNN). This strategy shows better performance when compared to vanilla RNN and LSTM. However, there is no guarantee that the transition matrix is close to orthogonal after a few iterations. The unitary RNN (uRNN) algorithm proposed in Arjovsky et al. (2016) parameterizes the transition matrix with reflection, diagonal and Fourier transform matrices. By construction, uRNN ensures that the transition matrix is unitary at all times. Although this algorithm performs well on several small tasks, Wisdom et al. (2016) showed that uRNN only covers a subset of possible unitary matrices and thus detracts from the expressive power of RNN. An improvement over uRNN, the orthogonal RNN (oRNN), was proposed by Mhammedi et al. (2017) . oRNN uses products of Householder reflectors to represent an orthogonal transition matrix, which is rich enough to span the entire space of orthogonal matrices. Meanwhile, Vorontsov et al. (2017) empirically demonstrate that the strong constraint of orthogonality limits the model's expressivity, thereby hindering its performance. Therefore, they parameterize the transition matrix by its SVD, W = U ΣV (factorized RNN) and restrict Σ to be in a range close to 1; however, the orthogonal matrices U and V are updated by geodesic gradient descent using the Cayley transform, thereby resulting in time complexity cubic in the number of hidden nodes which is prohibitive for large scale problems. Motivated by the shortcomings of the above methods, our work in this paper attempts to answer the following questions: Is there an efficient way to solve the gradient vanishing/exploding problem without hurting expressive power?

As brought to wide notice in He et al. (2016) , deep neural networks should be able to preserve features that are already good. Hardt & Ma (2016) consolidate this point by showing that deep linear residual networks have no spurious local optima. In our work, we broaden this concept and bring it to the area of recurrent neural networks, showing that each layer is not necessarily near identity, but being close to orthogonality suffices to get a similar result.

Generalization is a major concern in training deep neural networks. Bartlett et al. (2017) provide a generalization bound for neural networks by a spectral Lipschitz constant, namely the product of spectral norm of each layer. Thus, our scheme of restricting the spectral norm of weight matrices reduces generalization error in the setting of Bartlett et al. (2017) . As supported by the analysis in Cisse et al. (2017) , since our SVD parametrization allows us to develop an efficient way to constrain the weight matrix to be a tight frame (Tropp et al. (2005) ), we consequently are able to reduce the sensitivity of the network to adversarial examples.

3. SVD PARAMETERIZATION:

The SVD of the transition matrix W ∈ R n×n of an RNN is given by W = U ΣV T , where Σ is the diagonal matrix of singular values, and U, V ∈ R n×n are orthogonal matrices, i.e., U T U = U U T = I and Trefethen & Bau III (1997) ). During the training of an RNN, our proposal is to maintain the transition matrix in its SVD form. However, in order to do so efficiently, we need to maintain the orthogonal matrices U and V in compact form, so that they can be easily updated by forward and backward propagation. In order to do so, as in Mhammedi et al. (2017) , we use a tool that is commonly used in numerical linear algebra, namely Householder reflectors (which, for example, are used in computing the QR decomposition of a matrix).

V T V = V V T = I (

Given a vector u ∈ R k , k ≤ n, the n × n Householder reflector H n k (u) is defined as:

H n k (u) =    I n-k I k -2 uu u 2 , u = 0 I n , otherwise.

(1)

The Householder reflector is clearly a symmetric matrix, and it can be shown that it is orthogonal, i.e., H 2 = I (Householder (1958)). Further, when u = 0, it has n-1 eigenvalues that are 1, and one eigenvalue which is -1 (hence the name that it is a reflector) . In practice, to store a Householder reflector, we only need to store u ∈ R k rather than the full matrix.

Given a series of vectors {u i } n i=k where u k ∈ R k , we define the map:

M k : R k × ... × R n → R n×n (u k , ..., u n ) → H n (u n )...H k (u k ),

(2) where the right hand side is a product of Householder reflectors, yielding an orthogonal matrix (to make the notation less cumbersome, we remove the superscript from H n k for the rest of this section). Theorem 1. The image of M 1 is the set of all n × n orthogonal matrices.

The proof of Theorem 1 is an easy extension of the Householder QR factorization Theorem, and is presented in Appendix A. Although we cannot express all n × n matrices with M k , any W ∈ R n×n can be expressed as the product of two orthogonal matrices U, V and a diagonal matrix Σ, i.e. by its SVD:

W = U ΣV . Given σ ∈ R n and {u i } n i=k1 , {v i } n i=k2 with u i , v i ∈ R i , we finally define our proposed SVD parametrization: M k1,k2 :R k1 × ... × R n × R k2 × ... × R n × R n → R n×n (u k1 , ..., u n , v k2 , ..., v n , σ) → H n (u n )...H k1 (u k1 )diag(σ)H k2 (v k2 )...H n (v n ). (3) Theorem 2. The image of M 1,1 is the set of n × n real matrices. i.e. R n×n = M 1,1 R 1 × ... × R n × R 1 × ... × R n × R n

The proof of Theorem 2 is based on the singular value decomposition and Theorem 1, and is presented in Appendix A. The astute reader might note that M 1,1 seemingly maps an input space of n 2 + 2n dimensions to a space of n 2 dimensions; however, since H n k (u k ) is invariant to the norm of u k , the input space also has exactly n 2 dimensions. Although Theorems 1 and 2 are simple extensions of well known linear algebra results, they ensure that our parameterization has the ability to represent any matrix and so the full expressive power of the RNN is retained.

Theorem 3. The image of M k1,k2 includes the set of all orthogonal n×n matrices if k 1 +k 2 ≤ n+2.

Theorem 3 indicates that if the total number of reflectors is greater than n:

(n -k 1 + 1) + (n -k 2 + 1) ≥ n, then the parameterization covers all orthogonal matrices. Note that when fixing σ = 1, M k1,k2 ({u i } n i=k1 , {v i } n i=k2 , 1) ∈ O(n), where O(n) is the set of n × n orthogonal matrices. Thus when k 1 + k 2 ≤ n + 2, we have O(n) = M k1,k2 R k1 × ... × R n × R k2 × ... × R n × 1 .

4. SVD-RNN:

In this section, we apply our SVD parameterization to RNNs and describe the resulting svdRNN algorithm in detail. Given a hidden state vector from the previous step h (t-1) ∈ R n and input x (t-1) ∈ R ni , RNN computes the next hidden state h (t) and output vector o (t) ∈ R no as:

EQUATION

In svdRNN we parametrize the transition matrix W ∈ R n×n using m 1 + m 2 Householder reflectors as:

W = M n-m1+1,n-m2+1 (u n-m1+1 , ..., u n , v n-m2+1 , ..., v n , σ) (6) = H n (u n )...H n-m1+1 (u n-m1+1 )diag(σ)H n-m2+1 (v n-m2+1 )...H n (v n ) (7)

This parameterization gives us several advantages over the regular RNN. First, we can select the number of reflectors m 1 and m 2 to balance expressive power versus time and space complexity. By Theorem 2, the choice m 1 = m 2 = n gives us the same expressive power as vanilla RNN. Notice oRNN could be considered a special case of our parametrization, since when we set m 1 + m 2 ≥ n and σ = 1, we can represent all orthogonal matrices, as proven by Theorem 3. Most importantly, we are able to explicitly control the singular values of the transition matrix. In most cases, we want to constrain the singular values to be within a small interval near 1. The most intuitive method is to clip the singular values that are out of range. Another approach would be to initialize all singular values to 1, and add a penalty term σ -1 2 to the objective function. Here, we have applied another parameterization of σ proposed in Vorontsov et al. (2017) :

σ i = 2r(f (σ i ) -0.5) + σ * , i ∈ [n] (8)

where f is the sigmoid function and σi is updated from u i , v i via stochastic gradient descent. The above allows us to constrain σ i to be within [σ * -r, σ * + r]. In practice, σ * is usually set to 1 and r 1. Note that we are not incurring more computation cost or memory for the parameterization. For regular RNN, the number of parameters is

EQUATION

. In the extreme case where m 1 = m 2 = n, it becomes (n o + n i + n + 3)n. Later we will show that the computational cost of svdRNN is also of the same order as RNN in the worst case.

4.1. FORWARD/BACKWARD PROPAGATION:

In forward propagation, we need to iteratively evaluate h (t) from t = 0 to L using (4). The only different aspect from a regular RNN in the forward propagation is the computation of W h (t-1) . Note that in svdRNN, W is expressed as product of m 1 + m 2 Householder matrices and a diagonal matrix.Thus W h (t-1) can be computed iteratively using (m 1 + m 2 ) inner products and vector additions. Denoting ûk = 0 n-k u k , we have:

H k (u k )h = I n - 2û k û k û k ûk h = h -2 û k h û k ûk ûk (9)

Thus, the total cost of computing W h (t-1) is O((m 1 + m 2 )n) floating point operations (flops). Detailed analysis can be found in Section 4.2. Let L({u i }, {v i }, σ, M, Y, b) be the loss or objective function,

C (t) = W h (t) , Σ = diag(σ). Given ∂L ∂C (t) , we define: ∂L ∂u (t) k := ∂C (t) ∂u (t) k ∂L ∂C (t) ; ∂L ∂v (t) k := ∂C (t) ∂v (t) k ∂L ∂C (t) ; (10) ∂L ∂Σ (t) := ∂C (t) ∂Σ (t) ∂L ∂C (t) ; ∂L ∂ Σ(t) := ∂Σ (t) ∂ Σ(t) ∂L ∂Σ (t) ; (11) ∂L ∂h (t-1) := ∂C (t) ∂h (t-1) ∂L ∂C (t) (12)

Back propagation for svdRNN requires

∂C (t) ∂u (t) k , ∂C (t) ∂v (t) k , ∂C (t) ∂ Σ(t)

and ∂C (t) ∂h (t-1) . These partial gradients can also be computed iteratively by computing the gradient of each Householder matrix at a time. We drop the superscript (t) now for ease of exposition. Given ĥ = H k (u k )h and g = ∂L ∂ ĥ , we have

EQUATION

)

Details of forward and backward propagation can be found in Appendix (B). One thing worth noticing is that the oRNN method in Mhammedi et al. (2017) actually omitted the last term in (15) by assuming that u k are fixed. Although the scaling of u k in the Householder transform does not affect the transform itself, it does produce different gradient update for u k even if it is scaled to norm 1 afterwards.

4.2. COMPLEXITY ANALYSIS:

Table 1 gives the time complexity of various algorithms. Hprod and Hgrad are defined in Algorithm 2 3 (see Appendix (B)). Algorithm 2 needs 6k flops, while Algorithm 3 uses (3n + 10k) flops. Since u k 2 only needs to be computed once per iteration, we can further decrease the flops to 4k and (3n + 8k). Also, in back propagation we can reuse α in forward propagation to save 2k flops.

flops

Hprod(h, u k ) 4k Hgrad(h, u k , g) 3n + 6k svdRNN-Local FP(n, m 1 , m 2 ) 4n(m 1 + m 2 ) -2m 2 1 -2m 2 2 + O(n) svdRNN-Local BP(n, m 1 , m 2 ) 6n(m 1 + m 2 ) -1.5m 2 1 -1.5m 2 2 + O(n) oRNN-Local FP(n, m) 4nm -m 2 + O(n) oRNN-Local BP(n, m) 7nm -2m 2 + O(n)

Table 1 : Time complexity across algorithms

5. EXTENDING SVD PARAMETERIZATION TO GENERAL WEIGHT MATRICES:

In this section, we extend the parameterization to non-square matrices and use Multi-Layer Perceptrons(MLP) as an example to illustrate its application to general deep networks. For any weight matrix W ∈ R m×n (without loss of generality m ≤ n), its reduced SVD can be written as:

EQUATION

U ∈ R m×m , Σ ∈ diag(R m ),V L ∈ R n×m . There exist u n , ..., u k1 and v n , ..., v k2 s.t. U = H m m (u m )...H m k1 (u k1 ), V = H n n (v n )...H n k2 (v k2 ), where k 1 ∈ [m], k 2 ∈ [n].

Thus we can extend the SVD parameterization for any non-square matrix: 

EQUATION

1. Given {v i } n i=1 , define V (k) = H n n (v n )...H n k (v k ) for k ∈ [n]. We have: V (k1) * ,i = V (k2) * ,i , ∀k 1 , k 2 ∈ [n], i ≤ min(n -k 1 , n -k 2 ).

Here V * ,i indicates the ith column of matrix V . According to Lemma 1, we only need at most first m Householder vectors to express V L , which results in the following Theorem: Theorem 4. If m ≤ n, the image of M m,n 1,n-m+1 is the set of all m × n matrices; else the image of M m,n n-m+1,1 is the set of all m × n matrices. Similarly if we constrain u i , v i to have unit length, the input space dimensions of M m,n 1,n-m+1 and M m,n m-n+1,1 are both mn, which matches the output dimension. Thus we extend Theorem 2 to the non-square case, which enables us to apply SVD parameterization to not only the RNN transition matrix, but also to general weight matrices in various deep learning models. For example, the Multilayer perceptron (MLP) model is a class of feedforward neural network with fully connected layers:

h (t) = f (W (t-1) h (t-1) + b (t-1) ) (18) Here h (t) ∈ R nt , h (t-1) ∈ R nt-1 and W (t) ∈ R nt×nt-1 .

Applying SVD parameterization to W (t) say n t < n t-1 , we have:

W (t) = H nt nt (u nt )...H nt 1 (u 1 )ΣH nt-1 nt-1-nt+1 (v nt-1-nt+1 )...H nt-1 nt-1 (v nt-1

). We can use the same forward/backward propagation algorithm as described in Algorithm 1. Besides RNN and MLP, SVD parameterization method also applies to more advanced frameworks, such as Residual networks and LSTM, which we will not describe in detail here.

6. THEORETICAL ANALYSIS:

Since we can control and upper bound the singular values of the transition matrix in svdRNN, we can clearly eliminate the exploding gradient problem. In this section, we now analytically illustrate the advantages of svdRNN with lower-bounded singular values from the optimization perspective. For the theoretical analysis in this section, we will limit ourselves to a linear recurrent neural network, i.e., an RNN without any activation.

6.1. REPRESENTATIONS OF RNN WITHOUT ACTIVATION:

Linear recurrent neural network. For simplicity, we follow a setting similar to Hardt & Ma (2016) . For compact presentation, we stack the input data as X ∈ R n×t , where X = x (0) |x (1) | • • • |x (t-1) , and transition weights as W ∈ R n×nt where W = W |W 2 | • • • |W t . Then we can simplify the output as:

o (t) (X ) = Y (W t h (0) + t i=1 W i (M x (t) + b))

By absorbing M and b in each data x (t) and assuming h (0) = 0, we further simplify the output as:

o (t) (X ) = Y t i=1 W i x (t-1)

Suppose the input data X ∼ D, and assume its underlying relation to the output is y = Avec(X )+η, where A ∈ R n×nt and residue η ∈ R n satisfies E X ∼D [η|X ] = 0. We consider the individual loss:

f (W ; X , y) = o (t) (X ) -y 2 2 = Y Wvec(X ) -y 2 2 . Claim 1. With linear recurrent neural networks, the population risk R[W ] = E X ∼D [f (W ; X , y)] = (Y W -A)Σ 1/2 2 F + C, where Σ = E X ∼D [vec(X )vec(X ) ], and C = E[ η 2 2 ]. Meanwhile ∇ W R[W ] = (Y W -A)Σ I d |2W |3W 2 | • • • |tW t-1

6.2 ALL CRITICAL POINTS ARE GLOBAL MINIMUM Theorem 5. With linear recurrent neural networks, if transition matrix W satisfies σ min (W ) ≥ e > 0, all critical points in the population risk are global minimum. Proof. Write Y W -A as

(E 1 |E 2 | • • • |E t ) , where each E i ∈ R d×d . By Claim 1, ∇ W R[W ] 2 F = (Y W -A)Σ I d |2W |3(W ) 2 | • • • |t(W ) t-1 2 F ≥ σ 2 min (Σ) (Y W -A) I d |2W |3(W ) 2 | • • • |t(W ) t-1 2 F ≥ σ 2 min (Σ) t i=1 i 2 e 2(i-1) E i 2 F ≥ σ 2 min (Σ) min 1≤i≤t {i 2 e 2(i-1) } Y W -A 2 F ≥ σ 2 min (Σ) min 1≤i≤t {i 2 e 2(i-1) }(R(W ) -R * ) Therefore when ∇ W R[W ] = 0 suffices R(W ) = R * , meaning W reaches the global minimum.

Theorem 5 potentially explains why our system is easier to optimize, since with our scheme of SVD parametrization, we have the following corollary. Corollary 1. With the update rule in (8), linear svdRNNs have no spurious local minimum.

While the above analysis lends further credence to our observed experimental results, we leave it to future work to perform a similar analysis in the presence of non-linear activation functions.

7. EXPERIMENTAL RESULTS:

In this section, we provide empirical evidence that shows the advantages of SVD parameterization in both RNNs and MLPs. For RNN models, we compare our svdRNN algorithm with (vanilla) RNN, IRNN(Le et al. (2015) ), oRNN (Mhammedi et al. (2017) ) and LSTM (Hochreiter & Schmidhuber (1997) ). The transition matrix in IRNN is initialized to be orthogonal while other matrices are initialized by sampling from a Gaussian distribution. For MLP models, we implemented vanilla MLP, Residual Network (ResNet) (He et al. (2016) ) and used SVD parameterization for both of them. We used a residual block of two layers in ResNet. In most cases leaky Relu is used as activation function, except for LSTM, where leaky Relu will drastically harm the performance. To train these models, we applied Adam optimizer with stochastic gradient descent (Kingma & Ba (2014) ). These models are implemented with Theano (Al-Rfou et al. ( 2016)).1 

7.1. TIME SERIES CLASSIFICATION:

In this experiment, we focus on the time series classification problem, where time series are fed into RNN sequentially, which then tries to predict the right class upon receiving the sequence end (Hüsken & Stagge (2003) ). The dataset we choose is the largest public collection of classlabeled time-series with widely varying length, namely, the UCR time-series collection from Chen et al. ( 2015)2 . We present the test accuracy on 20 datasets with RNN, LSTM, oRNN and svdRNN in Table 3 (Appendix C) and Figure 1 . In all experiments, we used hidden dimension n h = 32, and chose total number of reflectors for oRNN and svdRNN to be m = 16 (for svdRNN m 1 = m 2 = 8).

We choose proper depth t as well as input size n i . Given sequence length L, since tn i = L, we choose n i to be the maximum divisor of L that satisfies depth ≤ √ L. To have a fair comparison of how the proposed principle itself influences the training procedure, we did not use dropout in any of these models. As illustrated in the optimization process in Figure 1 , this resulted in some overfitting (see (a) CBF), but on the other hand it shows that svdRNN is able to prevent overfitting. This supports our claim that since generalization is bounded by the spectral norm of the weights Bartlett et al. (2017) , svdRNN will potentially generalize better than other schemes. This phenomenon is more drastic when the depth is large (e.g. ArrowHead(251 layers) and FaceAll(131 layers)), since regular RNN, and even LSTM, have no control over the spectral norms. Also note that there are substantially fewer parameters in oRNN and svdRNN as compared to LSTM.

7.2. MNIST:

In this experiment, we compare different models on the MNIST image dataset. The dataset was split into a training set of 60000 instances and a test set of 10000 instances. The 28 × 28 MNIST pixels are flattened into a vector and then traversed by the RNN models. Table 2 shows accuracy scores across multiple We tested different models with different network depth as well as width. Figure 2 (a)(b) shows the test accuracy on networks with 28 and 112 layers (20 and 128 hidden dimensions) respectively. It can be seen that the svdRNN algorithms have the best performance and the choice of r (the amount that singular values are allowed to deviate from 1) does not have much influence on the final precision. Also we explored the effect of different spectral constraints and explicitly tracked the spectral margin (max i |σ i -1|) of the transition matrix. Intuitively, the influence of large spectral margin should increase as the network becomes deeper. Figure 2(d) shows the spectral margin of different RNN models. Although IRNN has small spectral margin at first few iterations, it quickly deviates from orthogonal and cannot match the performance of oRNN and svdRNN. Figure 2(e) shows the magnitude of first layer gradient ∂L ∂h (0) 2 . RNN suffers from vanishing gradient at first 50k iterations while oRNN and svdRNN are much more stable. Note that LSTM can perform relatively well even though it has exploding gradient in the first layer. We also tested RNN and svdRNN with different amount of non-linearity, as shown in Figure 2(c) . This is achieved by adjusting the leak parameter in leaky Relu: f (x) = max(leak • x, x). With leak = 1.0, it reduces to the identity map and when leak = 0 we are at the original Relu function. From the figures, we show that svdRNN is resistant to different amount of non-linearity, namely converge faster and achieve higher accuracy invariant to the amount of the leak factor. To explore the reason underneath, we illustrate the gradient in Figure 2 (f), and find out svdRNN could eliminate the gradient vanishing problem on all circumstances, while RNN suffers from gradient vanishing when non-linearity is higher. Table 2 : Results for the pixel MNIST dataset across multiple algorithms.

For the MLP models, each instance is flattened to a vector of length 784 and fed to the input layer.

After the input layer there are 40 layers with hidden dimension 32 (Figure 3 

8. CONCLUSIONS:

In this paper, we have proposed an efficient SVD parametrization of various weight matrices in deep neural networks, which allows us to explicitly track and control their singular values. This parameterization does not restrict the network's expressive power, while simultaneously allowing fast forward as well as backward propagation. The method is easy to implement and has the same time and space complexity as compared to original methods like RNN and MLP. The ability to control singular values helps in avoiding the gradient vanishing and exploding problems, and as we have empirically shown, gives good performance. Although we only showed examples in the RNN and MLP framework, our method is applicable to many more deep networks, such as Convolutional Networks etc. However, further experimentation is required to fully understand the influence of using different number of reflectors in our SVD parameterization. Also, the underlying structures of the image of M k1,k2 when k 1 , k 2 = 1 is a subject worth investigating.

APPENDIX B DETAILS OF FORWARD AND BACKWARD PROPAGATION ALGORITHMS:

Algorithm 1 Local forward/backward propagation

Input: h (t-1) , ∂L ∂C (t) , U = (u n |...|u n-m1+1 ), Σ, V = (v n |...|v n-m2+1 ) Output: C (t) = W h (t-1) , ∂L ∂U , ∂L ∂V , ∂L ∂ σ , ∂L ∂h (t-1)

// Begin forward propagation h 

(v) n+1 ← h (t-1) for k = n, n -1, ..., n -m 2 + 1 do h (v) k ← Hprod(h (v) k+1 , v k ) // Compute V h end for h (u) k1-1 ← Σh (v) k2 // Compute Σ V h for k = n -m 1 + 1, ..., n do h (u) k ← Hprod(h (u) k-1 , u k ) // Compute Û Σ V h end for C (t) ← h (u) n //Begin backward propagation g ← ∂L ∂C (t) for k = n, n -1, ..., n -m 1 + 1 do g, G (u) * ,n-k+1 ← Hgrad(h (u) k , u k , g) // Compute ∂L ∂u k end for Σ ← diag(g • h (v) k2 ), g ← Σg // Compute ∂L ∂Σ g (σ) ← ∂diag(Σ) ∂ σ • diag( Σ) // Compute ∂L ∂ σ for k = n -m 2 + 1, ..., n do g, G (v) * ,n-k+1 ← Hgrad(h (u) k+1 , v k , g) // Compute ∂L ∂v k end for ∂L ∂U ← G (u) , ∂L ∂V ← G (v) , ∂L ∂ σ ← g (σ) , ∂L ∂h (t-1) ← g Algorithm 2 ĥ = Hprod(h, u k ) Input: h, u k Output: ĥ = H k (u k )h // Compute ĥ = (I - 2u k u k u k u k )h α ← 2 u k 2 u k h ĥ ← h -αu k Algorithm 3 h, ūk = Hgrad(h, u k , g) Input: h, u k , g = ∂L ∂C where C = H k (u k )h Output: h = ∂L ∂h , ūk = ∂L ∂u k α = 2 u k 2 u k h β = 2 u k 2 u k g h ← g -βu k ūk ← -αg -βh + αβu k APPENDIX C MORE EXPERIMENTAL DETAILS

C.2.1 ADDING TASK:

The Adding task requires the network to remember two marked numbers in a long sequence and add them. Each input data includes two sequences: top sequence whose values are sampled uniformly from [0, 1] and bottom sequence which is a binary sequence with only two 1's. The network is asked to output the sum of the two values. From the empirical results in Figure 4 , we can see that when the network is not deep (number of layers L=30 in (a)(d)), every model outperforms the baseline of 0.167 (always output 1 regardless of the input). Also, the first layer gradients do not vanish for all models. However, on longer sequences (L=100 in (b)(e)), IRNN failed and LSTM converges much slower than svdRNN and oRNN. If we further increase the sequence length (L=300 in (c)(f)), only svdRNN and oRNN are able to beat the baseline within reasonable number of iterations. We can also observe that the first layer gradient of oRNN/svdRNN does not vanish regardless of the depth, while IRNN/LSTM's gradient vanish as L becomes lager. 

C.2.2 COPYING TASK:

Let A = {a i } 9 i=0 be the alphabet. The input data sequence x ∈ A T +20 where T is the time lag. x 1:10 are sampled uniformly from i{a i } 7 i=0 and x T +10 is set to a 9 . Rest of x i is set to a 8 . The network is asked to output x 1:10 after seeing a 9 . That is to copy x 1:10 from the beginning to the end with time lag T .

A baseline strategy is to predict a 8 for T +10 entrees and randomly sample from {a i } 7 i=1 for the last 10 digits. From the empirical results in Figure 5 , svdRNN consistently outperforms all other models. IRNN and LSTM models are not able to beat the baseline with large time lag. In fact, the loss of RNN/LSTM is very close to the baseline (memoryless strategy) indicates that they do not memorize any useful information throughout the time lag. 

:

we thank Mhammedi for providing their code for oRNN(Mhammedi et al. (2017))

Details of the data sets, including how to split into train/vaildiation/test sets, are given in Appendix C

Figures and Tables:

) where Σ = (diag(σ)|0) if m < n and (diag(σ)|0) otherwise. Next we show that we only need 2 min(m, n) reflectors (rather than m + n) to parametrize any m × n matrix. By the definition of H n k , we have the following lemma: Lemma

Performance comparisons of the RNN based models on three UCR datasets.

RNN models on MNIST Models Hidden dimension Number of parameters Test accuracy svdRNN 256(m 1 , m 2 = 16) ≈ 13k 97.6 oRNN(Mhammedi et al. (2017)) 256(m = 32) ≈ 11k 97.2 RNN(Vorontsov et al. (2017)) 128 ≈ 35k 94.1 uRNN(Arjovsky et al. (2016)) 512 ≈ 16k 95.1 RC uRNN(Wisdom et al. (2016)) 512 ≈ 16k 97.5 FC uRNN(Wisdom et al. (2016

(a)) or 30 to 100 layers with hidden dimension 128 (Figure 3(b)). On a 40-layer network, svdMLP and svdResNet achieve similar performance as ResNet while MLP's convergence is slower. However, when the network is deeper, both MLP and ResNet start to fail. With n h = 128, MLP is not able to function with L > 35 and ResNet with L > 70. On the other hand, the SVD based methods are resilient to increasing depth and thus achieve higher precision. MLP models on MNIST with L layers n h hidden dimension

RNN models on the adding task with L layers and n h hidden dimension. The top plots show the test MSE, while the bottom plots show the magnitude of the gradient at the first layer.

Figure 5: RNN models on the Copying task with T time lag and n h hidden dimension.

.1 DETAILS ON THE TIME SERIES CLASSIFICATION TASK For the time series classification task, we use the training and testing sets directly from the UCR time series archive http://www.cs.ucr.edu/ ˜eamonn/time_series_data/, and randomly choose 20% of the training set as validation data. We provide the statistical descriptions of the datasets and experimental results in Table3.

Table content: <table><tr><td>Datasets</td><td colspan="3">Data Descriptions training/testing size length</td><td>#class</td><td>Depth</td><td>RNN acc (nparam)</td><td>LSTM acc (nparam)</td><td>oRNN acc (nparam)</td><td>svdRNN acc (nparam)</td></tr><tr><td>50words</td><td>450</td><td>455</td><td>270</td><td>50</td><td>27</td><td colspan="3">0.492 (3058) 0.598 (7218) 0.642 (2426) 0.651 (2850)</td></tr><tr><td>Adiac</td><td>390</td><td>391</td><td>176</td><td>37</td><td>16</td><td colspan="3">0.552 (2694) 0.706 (6950) 0.668 (2062) 0.726 (2486)</td></tr><tr><td>ArrowHead</td><td>36</td><td>175</td><td>251</td><td>3</td><td>251</td><td colspan="3">0.509 (1219) 0.537 (4515) 0.669 (587)</td><td>0.800 (1011)</td></tr><tr><td>Beef</td><td>30</td><td>30</td><td>470</td><td>5</td><td>47</td><td colspan="3">0.600 (1606) 0.700 (5766) 0.733 (974)</td><td>0.733 (1398)</td></tr><tr><td>BeetleFly</td><td>20</td><td>20</td><td>512</td><td>2</td><td>32</td><td colspan="3">0.950 (1699) 0.850 (6435) 0.900 (1067) 0.950 (1491)</td></tr><tr><td>CBF</td><td>30</td><td>900</td><td>128</td><td>3</td><td>16</td><td colspan="3">0.702 (1476) 0.967 (5444) 0.881 (844)</td><td>0.948 (1268)</td></tr><tr><td>Coffee</td><td>28</td><td>28</td><td>286</td><td>2</td><td>22</td><td colspan="3">1.000 (1570) 1.000 (6018) 1.000 (938)</td><td>1.000 (1362)</td></tr><tr><td>Cricket X</td><td>390</td><td>390</td><td>300</td><td>12</td><td>20</td><td colspan="3">0.310 (1997) 0.456 (6637) 0.495 (1365) 0.500 (1789)</td></tr><tr><td>DistalPhalanxOutlineCorrect</td><td>276</td><td>600</td><td>80</td><td>2</td><td>10</td><td colspan="3">0.790 (1410) 0.798 (5378) 0.830 (778)</td><td>0.840 (1202)</td></tr><tr><td>DistalPhalanxTW</td><td>154</td><td>399</td><td>80</td><td>6</td><td>10</td><td colspan="3">0.815 (1641) 0.795 (5609) 0.807 (1009) 0.815 (1433)</td></tr><tr><td>ECG200</td><td>100</td><td>100</td><td>96</td><td>2</td><td>12</td><td colspan="3">0.640 (1410) 0.640 (5378) 0.640 (778)</td><td>0.640 (1202)</td></tr><tr><td>ECG5000</td><td>500</td><td>4500</td><td>140</td><td>5</td><td>14</td><td colspan="3">0.941 (1606) 0.936 (5766) 0.940 (974)</td><td>0.945 (1398)</td></tr><tr><td>ECGFiveDays</td><td>23</td><td>861</td><td>136</td><td>2</td><td>17</td><td colspan="3">0.947 (1443) 0.790 (5411) 0.976 (811)</td><td>0.948 (1235)</td></tr><tr><td>FaceAll</td><td>560</td><td>1690</td><td>131</td><td>14</td><td>131</td><td colspan="3">0.549 (1615) 0.455 (4911) 0.714 (983)</td><td>0.714 (1407)</td></tr><tr><td>FaceFour</td><td>24</td><td>88</td><td>350</td><td>4</td><td>25</td><td colspan="3">0.625 (1701) 0.477 (6245) 0.511 (1069) 0.716 (1493)</td></tr><tr><td>FacesUCR</td><td>200</td><td>2050</td><td>131</td><td>14</td><td>131</td><td colspan="3">0.449 (1615) 0.629 (4911) 0.710 (983)</td><td>0.727 (1407)</td></tr><tr><td>Gun Point</td><td>50</td><td>150</td><td>150</td><td>2</td><td>15</td><td colspan="3">0.947 (1507) 0.920 (5667) 0.953 (875)</td><td>0.960 (1299)</td></tr><tr><td>InsectWingbeatSound</td><td>220</td><td>1980</td><td>256</td><td>11</td><td>16</td><td colspan="3">0.534 (1996) 0.515 (6732) 0.598 (1364) 0.586 (1788)</td></tr><tr><td>ItalyPowerDemand</td><td>67</td><td>1029</td><td>24</td><td>2</td><td>6</td><td colspan="3">0.970 (1315) 0.969 (4899) 0.972 (683)</td><td>0.973 (1107)</td></tr><tr><td>Lighting2</td><td>60</td><td>61</td><td>637</td><td>2</td><td>49</td><td colspan="3">0.541 (1570) 0.541 (6018) 0.541 (938)</td><td>0.541 (1362)</td></tr><tr><td colspan="2">MiddlePhalanxOutlineCorrect 291</td><td>600</td><td>80</td><td>2</td><td>10</td><td colspan="3">0.793 (1410) 0.783 (5378) 0.712 (778)</td><td>0.820 (1202)</td></tr></table>

Test accuracy (number of parameters) on UCR datasets. For each dataset, we present the testing accuracy when reaching the smallest validation error. The highest precision is in bold, and lowest two are colored gray.C.2 EXPERIMENTAL RESULTS ON THE ADDING AND COPYING TASKSWe tested RNN models on the Adding and Copying tasks with the same settings asArjovsky et al. (2016).

Table content: <table/>

Peer review (iclr2018):
 This paper proposed a new parametrization scheme for weight matrices in neural network based on the Householder reflectors to solve the gradient vanishing and exploding problems in training. The proposed method improved two previous papers: 1) stronger expressive power than Mahammedi et al. (2017), 2) faster gradient update than Vorontsov et al. (2017). The proposed parametrization scheme is natrual from numerical linear algebra point of view and authors did a good job in Section 3 in explaining the corresponding expressive power. The experimental results also look promising. It would be nice if the authors can analyze the spectral properties of the saddle points in linear RNN (nonlinear is better but it*s too difficult I believe). If the authors can show the strict saddle properties then as a corollary, (stochastic) gradient descent finds a global minimum. Overall this is a strong paper and I recommend to accept.