Answers.Body: <p>Second-order optimization algorithms like Hessian optimization have more information on the curvature of the loss function, so converge much, much faster than first-order optimization algorithms like gradient descent. I remember reading somewhere that if you have <span class="math-container">$n$</span> weights in the neural network, one iteration of a second-order optimization algorithm will reduce the loss function at approximately the same rate as <span class="math-container">$n$</span> iterations of a standard first-order optimization algorithm. However, with recent advancements to gradient descent (momentum, adaptive rates, etc), the difference isn't as large anymore -- @EmmanuelMess pointed out a <a href="https://core.ac.uk/download/pdf/187245955.pdf" rel="nofollow noreferrer">paper</a> that states:</p>
  <blockquote>
  <p>The performance of the proposed first order and second order methods with adaptive gain (BP-AG, CGFR-AG, BFGS-AG) with standard second order methods without gain (BP, CGFR, BFGS) in terms of speed of convergence evaluated in the number of epochs and CPU time. Based on some simulation results, it’s showed that the proposed algorithm had shown improvements in the convergence rate with 40% faster than other standard algorithms without losing their accuracy.</p>
  </blockquote>
  <p><a href="https://stats.stackexchange.com/a/145446/303597">Here</a> is a great post explaining the background behind the math of why this is the case.</p>
  <p>Also, second-order gradients can help the optimizer identify states like saddle points, and help the solver get out of those states. Saddle points give standard gradient descent a lot of issues, as the gradient descent has difficulty and is slow to move out of the saddle point. Fixing the saddle point issue is one of the motivations for improving gradient descent over the last two decades (SDG with momentum, adaptive learning rates, ADAM, etc). <a href="https://stats.stackexchange.com/a/279094/303597">More info</a>.</p>
  <p><a href="https://i.sstatic.net/gjDzm.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gjDzm.gif" alt="enter image description here" /></a></p>
  <p>The issue though is that to compute the second-order derivative requires a matrix <span class="math-container">$n^2$</span> in size, as opposed to gradient descent which requires a matrix <span class="math-container">$n$</span> in size. The memory and computation become intractable for large networks, especially if you have millions of weights.</p>
  <p>Some approaches exist which efficiently approximates the second-order optimizations, solving the tractability problem. A popular one is <a href="http://users.iems.northwestern.edu/%7Enocedal/PDFfiles/limited.pdf" rel="nofollow noreferrer">L-BFGS</a>. I haven't played around with it much, but I believe L-BFGS is not as popular as gradient descent algorithms (such as SGD-M, ADAM) because it is still very memory demanding (requires storing about 20-100 previous gradient evaluations), and cannot work in a stochastic context (you cannot sample mini-batches to train on; you must train the entire dataset in one pass per iteration). If those two are not an issue for you, then L-BFGS works pretty well I believe.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-11T10:56:44.547Z
Answers.Text: The info in this answer seems to be consistent with my knowledge, which is not very extensive though. I would maybe add 1-2 papers that have attempted to apply second-order methods to train NNs and you could _briefly_ describe their results in terms of convergence and memory requirements (to confirm your claims). This would make your answer more reliable. You can also point to (Python) libraries that support the training of NNs with second-order methods (e.g, does TensorFlow support them?). Although this was not the question, this would allow people to play with these methods more rapidly.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-11T12:10:38.443Z
Answers.Text: I found a paper analizing the time of first order vs second order bp: https://core.ac.uk/download/pdf/187245955.pdf
Answers.UserDisplayName: EmmanuelMess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-11T12:13:21.723Z
Answers.Text: "The  performance  of  the  proposed  first  order  and second  order  methods  with  adaptive  gain  (BP-AG,  CGFR-AG,   BFGS-AG)   with   standard   second   order   methods without  gain  (BP,  CGFR,  BFGS)  in  terms  of  speed  of convergence  evaluated  in  the  number  of  epochs  and  CPU time. Based on some simulation results, it’s showed that the proposed   algorithm    had   shown   improvements   in   the convergence   rate   with   40%   faster   than   other   standard algorithms without losing their accuracy."
Answers.UserDisplayName: EmmanuelMess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-11T12:40:33.740Z
Answers.Text: @EmmanuelMess Although the paper may be valuable, it has not been cited many times. Maybe when you look for a paper you should also take a look _where_ or _if_ it's been published and _how many_ times it's been cited. That's something that I had to learn too (and that my advisor also had told me). You can probably find more papers on Google Scholar with keywords such as "second order" and "backpropagation". Anyway, thanks for sharing that paper. If I have time, I will take a look at it and other papers and maybe also provide an answer.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-12T11:41:52.673Z
Answers.Text: I have found [this article](https://www.tensorflow.org/guide/advanced_autodiff#hessian) that describes how higher-order derivatives could be computed in TensorFlow. [This article](https://www.tensorflow.org/probability/examples/Optimizers_in_TensorFlow_Probability) talks about BFGS and L-BFGS in the context of TensorFlow Probability. You also have [`tf.hessians`](https://www.tensorflow.org/api_docs/python/tf/hessians). There are probably other implementations of other specific methods around, such as [`psgd_tf`](https://github.com/lixilinx/psgd_tf) (which I never tried though).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-11T07:25:21.743Z
Answers.LastActivityDate: 2020-12-12T11:26:57.727Z
Answers.LastEditDate: 2020-12-12T11:26:57.727Z
Answers.UserDisplayName: user3667125
Body: <p>Raul Rojas's book on Neural Networks dedicates <a href="http://page.mi.fu-berlin.de/rojas/neural/chapter/K8.pdf" rel="nofollow noreferrer">section 8.4.3</a> to explaining how to do second-order backpropagation, that is, computing the Hessian of the error function with respect to two weights at a time.</p>
  <p>What problems are easier to solve using this approach rather than first-order backpropagation?</p>
  
Tags: <neural-networks><backpropagation><optimization><numerical-algorithms>
Title: Why is second-order backpropagation useful?
UserDisplayName: EmmanuelMess
ThreadText: # Why is second-order backpropagation useful?
  
  (Asked by: username_0 on 2020-12-10)
  
  Raul Rojas's book on Neural Networks dedicates [section 8.4.3](http://page.mi.fu-berlin.de/rojas/neural/chapter/K8.pdf) to explaining how to do second-order backpropagation, that is, computing the Hessian of the error function with respect to two weights at a time.
  
  What problems are easier to solve using this approach rather than first-order backpropagation?
  
  **Tags:** neural-networks, backpropagation, optimization, numerical-algorithms
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-11. Score: 6 | Accepted answer
  
  Second-order optimization algorithms like Hessian optimization have more information on the curvature of the loss function, so converge much, much faster than first-order optimization algorithms like gradient descent. I remember reading somewhere that if you have $n$ weights in the neural network, one iteration of a second-order optimization algorithm will reduce the loss function at approximately the same rate as $n$ iterations of a standard first-order optimization algorithm. However, with recent advancements to gradient descent (momentum, adaptive rates, etc), the difference isn't as large anymore -- @EmmanuelMess pointed out a [paper](https://core.ac.uk/download/pdf/187245955.pdf) that states:
  
  > The performance of the proposed first order and second order methods with adaptive gain (BP-AG, CGFR-AG, BFGS-AG) with standard second order methods without gain (BP, CGFR, BFGS) in terms of speed of convergence evaluated in the number of epochs and CPU time. Based on some simulation results, it’s showed that the proposed algorithm had shown improvements in the convergence rate with 40% faster than other standard algorithms without losing their accuracy.
  
  [Here](https://stats.stackexchange.com/a/145446/303597) is a great post explaining the background behind the math of why this is the case.
  
  Also, second-order gradients can help the optimizer identify states like saddle points, and help the solver get out of those states. Saddle points give standard gradient descent a lot of issues, as the gradient descent has difficulty and is slow to move out of the saddle point. Fixing the saddle point issue is one of the motivations for improving gradient descent over the last two decades (SDG with momentum, adaptive learning rates, ADAM, etc). [More info](https://stats.stackexchange.com/a/279094/303597).
  
  [![enter image description here](https://i.sstatic.net/gjDzm.gif)](https://i.sstatic.net/gjDzm.gif)
  
  The issue though is that to compute the second-order derivative requires a matrix $n^2$ in size, as opposed to gradient descent which requires a matrix $n$ in size. The memory and computation become intractable for large networks, especially if you have millions of weights.
  
  Some approaches exist which efficiently approximates the second-order optimizations, solving the tractability problem. A popular one is [L-BFGS](http://users.iems.northwestern.edu/%7Enocedal/PDFfiles/limited.pdf). I haven't played around with it much, but I believe L-BFGS is not as popular as gradient descent algorithms (such as SGD-M, ADAM) because it is still very memory demanding (requires storing about 20-100 previous gradient evaluations), and cannot work in a stochastic context (you cannot sample mini-batches to train on; you must train the entire dataset in one pass per iteration). If those two are not an issue for you, then L-BFGS works pretty well I believe.
  
  > **Comments:**
  > **username_2**: The info in this answer seems to be consistent with my knowledge, which is not very extensive though. I would maybe add 1-2 papers that have attempted to apply second-order methods to train NNs and you could _briefly_ describe their results in terms of convergence and memory requirements (to confirm your claims). This would make your answer more reliable. You can also point to (Python) libraries that support the training of NNs with second-order methods (e.g, does TensorFlow support them?). Although this was not the question, this would allow people to play with these methods more rapidly.  
  > **username_0**: I found a paper analizing the time of first order vs second order bp: https://core.ac.uk/download/pdf/187245955.pdf  
  > **username_0**: "The  performance  of  the  proposed  first  order  and second  order  methods  with  adaptive  gain  (BP-AG,  CGFR-AG,   BFGS-AG)   with   standard   second   order   methods without  gain  (BP,  CGFR,  BFGS)  in  terms  of  speed  of convergence  evaluated  in  the  number  of  epochs  and  CPU time. Based on some simulation results, it’s showed that the proposed   algorithm    had   shown   improvements   in   the convergence   rate   with   40%   faster   than   other   standard algorithms without losing their accuracy."  
  > **username_2**: @EmmanuelMess Although the paper may be valuable, it has not been cited many times. Maybe when you look for a paper you should also take a look _where_ or _if_ it's been published and _how many_ times it's been cited. That's something that I had to learn too (and that my advisor also had told me). You can probably find more papers on Google Scholar with keywords such as "second order" and "backpropagation". Anyway, thanks for sharing that paper. If I have time, I will take a look at it and other papers and maybe also provide an answer.  
  > **username_2**: I have found [this article](https://www.tensorflow.org/guide/advanced_autodiff#hessian) that describes how higher-order derivatives could be computed in TensorFlow. [This article](https://www.tensorflow.org/probability/examples/Optimizers_in_TensorFlow_Probability) talks about BFGS and L-BFGS in the context of TensorFlow Probability. You also have [`tf.hessians`](https://www.tensorflow.org/api_docs/python/tf/hessians). There are probably other implementations of other specific methods around, such as [`psgd_tf`](https://github.com/lixilinx/psgd_tf) (which I never tried though).  
  
  ---
  
  