# Condition for RNN vanishing gradients and eigenvalues of the matrix of weights

In this article on recurrent neural networks by Razvan Pascanu, $$\mathbf x_t$$ is the state at time $$t;$$ $$\mathbf u_t$$ the input at time $$t$$; and $$\mathcal E$$ is the cost function: A proof is given of the fact that if the absolute value of the main eigenvalue of the matrix of recurrent weights is $$\rho < 1$$ then the vanishing gradient problem would occur:

If we consider a linear version of the model (i.e. set $$\sigma$$ to the identity function in eq. (2)) we can use the power iteration method to formally analyze this product of Jacobian matrices and obtain tight conditions for when the gradients explode or vanish. It is sufficient for $$\rho < 1$$, where $$\rho$$ is the spectral radius of the recurrent weight matrix $$\mathbf W_{rec}$$ for long term components to vanish (as $$t \to\infty$$) and necessary for $$\rho >1$$ for them to explode.

We generalize this result for nonliner functions $$\sigma$$ where $$\lvert \sigma'(x)\rvert$$ is bounded, $$\lVert diag(\sigma'(\mathbf x_k )) \rVert \leq \gamma \in \mathcal R$$, by relying on singular values.

We first prove that it is sufficient for $$\lambda_1 <\frac{1}{\gamma}$$, where $$\lambda_1$$ is the largest singular value of $$\mathbf W_{rec}$$, for the vanishing gradient problem to occur. Note that we assume the parametrization given by eq. (2). The Jacobian matrix $$\frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k}$$ is given by $$\mathbf W_{rec}^T\, diag(\sigma'(\mathbf x_k)).$$ The 2-norm of this Jacobian is bounded by the product of the norms of the the two matrices (see eq. (6)). Due to our assumption, this implies that it is smaller than $$1.$$

$$\forall k, \; \left\lVert \frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k} \right\rVert \leq \left \lVert \mathbf W_{rec}^T \right \rVert \, \left \lVert diag(\sigma'(\mathbf x_k)) \right \rVert < \frac{1}{\gamma}\gamma <1 \tag{6}$$

Let $$\eta \in \mathrm R$$ be such that $$\forall k, \, \left\lVert \frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k} \right \rVert \leq \eta < 1.$$ The existence of $$\eta$$ is given by eq. (6). By induction over $$i$$, we can now show that

$$\left \lVert \frac{\partial \mathcal{E}_t}{\partial \mathbf x_t} \left( \prod_{i=k}^{t-1} \frac{\partial \mathbf x_{i+1}}{\partial \mathbf x_i} \right) \right \rVert \leq \eta^{t-k}\; \left\lVert \frac{\partial \mathcal{E}_t}{\partial \mathbf x_t}\right \rVert \tag 7$$

As $$\eta < 1,$$ it follows that, according to eq. (7), long term contributions (for which $$t-k$$ is large) go to $$0$$ exponentially fast with $$t-k.$$ $$\tag*{\square}$$

Can I get some help explaining Eq.6?

In particular, I understand that if $$\lambda_1$$ is the largest singular value of $$\mathbf W_{\text{rec}}$$, and $$\lambda_1 < \frac{1}{\gamma}$$, the absolute value of the largest eigenvalue $$\lambda_1^2 < \frac{1}{\gamma^2}$$. This latter value (spectral radius) corresponding to the norm of $$\mathbf W_{\text{rec}}$$, i.e. $$\left\lVert \mathbf{W}_{\text{rec}} \right\rVert$$.

Therefore

$$\left\lVert \frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k} \right\rVert \leq \left \lVert \mathbf W_{\text{rec}}^\top \right \rVert \, \left \lVert \text{diag}(\sigma'(\mathbf x_k)) \right \rVert < \frac{1}{\gamma^2}\gamma = \frac{1}{\gamma}$$

If $$\gamma>1 \implies \lambda_1^2 < 1$$ (and $$\lambda_1 < 1)$$, exponentiating this $$\frac{1}{\gamma}$$ will result in vanishing gradients. If $$\gamma < 1$$ the gradients will explode.

It makes sense, but it is different from eq. (6).

• Also, I am not sure whether Eq.5 is right, see this question. (Though this paper was cited 1250 times, so I am probably missing something...) Sep 28 '18 at 11:13
• @Oren I haven't pursued the study of this topic farther. If you think the question has some value, I would ask you to answer with corrections. Otherwise, I will consider just deleting it. Sep 28 '18 at 11:47
• I am sorry for the previous comments. ISTM that I was wrong once again, and the paper that you quoted in the original question is indeed the most up to date version. Sep 28 '18 at 16:56
• @OrenMilman No sweat! I really appreciate your dedication. Let me leave your answer up for referendum - I haven't touched on the topic in forever; so if you get upvotes, I'll come back to it and happily accept it. Remind me if I forget, please. Sep 28 '18 at 17:00
• In equation 6, it appears that $\frac{1}{\gamma}\gamma < 1$ a typo for something else.
– Sycorax
Sep 3 at 4:17

$$A=\left(\begin{matrix}0 & 1\\ 0 & 0 \end{matrix}\right)$$ is a counterexample, as $$0$$ is the only eigenvalue of $$A$$, and so the spectral radius of $$A$$ is $$0$$.
The paper assumes that $$W_{rec}$$ is a square matrix, and thus $$||W_{rec}||=||W_{rec}^T||$$, as shown here (which uses what is shown here).
$$\lambda_1$$ is the largest singular value of $$W_{rec}$$. Therefore, we get that $$\lambda_1=||W_{rec}^T||$$, and so $$||W_{rec}^T||<\frac{1}{\gamma}$$.