Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T13:36:01.737Z
Answers.Text: 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)
Answers.UserDisplayName: Jeremiah England
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T12:50:58.757Z
Answers.LastActivityDate: 2020-04-19T12:56:22.363Z
Answers.LastEditDate: 2020-04-19T12:56:22.363Z
Answers.UserDisplayName: Jeremiah England
Body: <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>
  
Tags: <papers><vanishing-gradient-problem>
Title: Does the paper "On the difficulty of training Recurrent Neural Networks" (2013) assume, falsely, that spectral radii are $\ge$ square matrix norms?
UserDisplayName: Jeremiah England
ThreadText: # 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)  
  
  ---
  
  