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

Question

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).

Answer 1

The spectral radius of a matrix is not always equal to the matrix's norm.
$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$.

On the other hand, the largest singular value of a matrix is always equal to the matrix's norm, as shown here.

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}$.