<p>It is an error. But it is also not the in final version of the paper (arxiv.) The final version of the paper can be found <a href="http://proceedings.mlr.press/v28/pascanu13.pdf" rel="nofollow noreferrer">here</a> where they replace "absolute value of the largest <a href="https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors" rel="nofollow noreferrer">eigenvalue</a>" with "largest <a href="https://en.wikipedia.org/wiki/Singular_value" rel="nofollow noreferrer">singular value</a>". </p>

<blockquote>
  <p>We first prove that it is sufficient for <span class="math-container">$\lambda_1 &lt; \frac{1}{\gamma}$</span>, where <span class="math-container">$\lambda_1$</span> is the largest singular value of <span class="math-container">$W_{rec}$</span>, for the vanishing gradient problem to occur.</p>
</blockquote>

CC BY-SA 4.0
2020-04-19T13:36:01.737Z
For a proof that their substitution works with the the maximum singular value and the 2-norm, see Theorem 4.2 of in chapter 4 of  [Lectures on Dynamic Systems and
 Control](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-241j-dynamic-systems-and-control-spring-2011/readings/MIT6_241JS11_chap04.pdf)
Jeremiah England
CC BY-SA 4.0
2020-04-19T12:50:58.757Z
2020-04-19T12:56:22.363Z
2020-04-19T12:56:22.363Z
Jeremiah England
<p>(<a href="https://arxiv.org/pdf/1211.5063.pdf" rel="nofollow noreferrer">link to paper in arxiv</a>)</p>

<p>In section <strong>2.1</strong> the authors define <span class="math-container">$\gamma$</span> as the maximum possible value of the derivative of the activation function (e.g. 1 for tanh.) Then they have this to say: </p>

<blockquote>
  <p>We first prove that it is sufficient for <span class="math-container">$\lambda_1 &lt; \frac{1}{\gamma}$</span>, where <span class="math-container">$\lambda_1$</span> is the absolute value of the largest eigenvalue of the recurrent weight matrix <span class="math-container">$W_{rec}$</span>, for the vanishing gradient problem to occur. </p>
</blockquote>

<p>Then they use the submultiplicity (<span class="math-container">$\|AB\| \le \|A\|\|B\|$</span>) of the 2-norm of the Jacobians to obtain the following inequality: </p>

<p><span class="math-container">$$ \forall x, \| \frac{\partial x_{k+1}}{\partial x_k} \| \le \| W_{rec}^\top \| \| diag(\sigma'(x_k))\| &lt; \frac{1}{\gamma} \gamma &lt; 1 $$</span></p>

<p>Here</p>

<ul>
<li><span class="math-container">$x_k$</span> is the pre-activated state vector of the RNN </li>
<li><span class="math-container">$W_{rec}$</span> is the weight matrix between states (i.e. <span class="math-container">$x_k = W_{rec} \times \sigma(x_{k-1}) + b$</span> ) </li>
<li><span class="math-container">$\sigma()$</span> is the activation function for the state vector </li>
<li><span class="math-container">$diag(v)$</span> is the diagonal matrix version of a vector <span class="math-container">$v$</span></li>
</ul>

<p>They appear to be either substituting the norm of the weight matrix <span class="math-container">$\|W_{rec}^\top\|$</span> for its largest eigenvalue <span class="math-container">$|\lambda_1|$</span> (eigenvalues are the same for transposes) or just assuming that this norm is less than or equal to the eigenvalue. This bothers me because the norm of a matrix is bounded <em>below</em>, not above, by this eigenvalue/spectral radius (<a href="https://www.math.drexel.edu/~foucart/TeachingFiles/F12/M504Lect6.pdf" rel="nofollow noreferrer">see lemma 10 here</a> and this <a href="https://math.stackexchange.com/questions/2583417/spectral-radius-is-not-matrix-norm">math SE question</a>)  </p>

<p>They seem to assume that </p>

<p><span class="math-container">$$\| W_{rec}^\top \| \le \lambda_1 &lt; \frac{1}{\gamma}  $$</span> </p>

<p>But really </p>

<p><span class="math-container">$$ \| W_{rec}^\top \| \ge \lambda_1 $$</span></p>

<papers><vanishing-gradient-problem>
Does the paper "On the difficulty of training Recurrent Neural Networks" (2013) assume, falsely, that spectral radii are $\ge$ square matrix norms?
Jeremiah England
# Does the paper "On the difficulty of training Recurrent Neural Networks" (2013) assume, falsely, that spectral radii are $\ge$ square matrix norms?

(Asked by: username_0 on 2020-04-18)

([link to paper in arxiv](https://arxiv.org/pdf/1211.5063.pdf))

In section **2.1** the authors define $\gamma$ as the maximum possible value of the derivative of the activation function (e.g. 1 for tanh.) Then they have this to say:

> We first prove that it is sufficient for $\lambda\_1 < \frac{1}{\gamma}$, where $\lambda\_1$ is the absolute value of the largest eigenvalue of the recurrent weight matrix $W\_{rec}$, for the vanishing gradient problem to occur.

Then they use the submultiplicity ($\|AB\| \le \|A\|\|B\|$) of the 2-norm of the Jacobians to obtain the following inequality:

$$ \forall x, \| \frac{\partial x\_{k+1}}{\partial x\_k} \| \le \| W\_{rec}^\top \| \| diag(\sigma'(x\_k))\| < \frac{1}{\gamma} \gamma < 1 $$

Here

* $x\_k$ is the pre-activated state vector of the RNN
* $W\_{rec}$ is the weight matrix between states (i.e. $x\_k = W\_{rec} \times \sigma(x\_{k-1}) + b$ )
* $\sigma()$ is the activation function for the state vector
* $diag(v)$ is the diagonal matrix version of a vector $v$

They appear to be either substituting the norm of the weight matrix $\|W\_{rec}^\top\|$ for its largest eigenvalue $|\lambda\_1|$ (eigenvalues are the same for transposes) or just assuming that this norm is less than or equal to the eigenvalue. This bothers me because the norm of a matrix is bounded *below*, not above, by this eigenvalue/spectral radius ([see lemma 10 here](https://www.math.drexel.edu/~foucart/TeachingFiles/F12/M504Lect6.pdf) and this [math SE question](https://math.stackexchange.com/questions/2583417/spectral-radius-is-not-matrix-norm))

They seem to assume that

$$\| W\_{rec}^\top \| \le \lambda\_1 < \frac{1}{\gamma} $$

But really

$$ \| W\_{rec}^\top \| \ge \lambda\_1 $$

**Tags:** papers, vanishing-gradient-problem


---

## 1 answers

### Answer by username_0 on 2020-04-19. Score: 1 | Accepted answer

It is an error. But it is also not the in final version of the paper (arxiv.) The final version of the paper can be found [here](http://proceedings.mlr.press/v28/pascanu13.pdf) where they replace "absolute value of the largest [eigenvalue](https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors)" with "largest [singular value](https://en.wikipedia.org/wiki/Singular_value)".

> We first prove that it is sufficient for $\lambda\_1 < \frac{1}{\gamma}$, where $\lambda\_1$ is the largest singular value of $W\_{rec}$, for the vanishing gradient problem to occur.

> **Comments:**
> **username_0**: For a proof that their substitution works with the the maximum singular value and the 2-norm, see Theorem 4.2 of in chapter 4 of  [Lectures on Dynamic Systems and  Control](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-241j-dynamic-systems-and-control-spring-2011/readings/MIT6_241JS11_chap04.pdf)  

---

