7 ms·

Backpropogation Is Just Steepest Descent with Automatic Differentiation (2013)

122 points by adamnemecek 8y ago

jefft255 8y ago
The article seems good (although dated). See http://www.jmlr.org/papers/v18/17-468.html http://www.jmlr.org/papers/v18/17-468.html for an in depth survey from last year. But reading the title, I was like "well... sure?". Bad title for this article.
brilee 8y ago
This title is really confused - backpropagation is one implementation of automatic differentiation, and yields a gradient. What you do with that gradient next is up to you - you can just follow it (steepest descent), or try other fancier second order techniques.
- electricslpnsld 8y ago
  Can you get second order with only the gradient? Even fancy accelerated gradient descents are still first order. I suppose there are BFGS-like quasi Newton methods, but those are still building up estimates of the second order info over multiple iterations.
  - deleted 8y ago
    [deleted]
  - vbarrielle 8y ago
    You can get closer to second order if your error is a sum of squares of the form 0.5 * f^T * f, in which case you case compute the jacobian J of the fitness f, and approximate your hessian as J^T * J. That's the Gauss-Newton method and it's very effective if a linear approximation of f holds locally. That's an approximation but that's arguably a second order method, since it acknowledges the nonlinearity coming from the squared norm of f.
graycat 8y ago
I've always wondered how the neural network parameter fitting got away with using just steepest descent: In such fully or largely unconstrained optimization, going way back, decades, steepest descent was seen as often poor. The usual, first analogy was finding the bottom of a convex bowl that was long and narrow. Then steepest descent would keep going down hill parallel to essentially the short axis of the bowl and make nearly no progress along the long axis. So, sure, the idea was make a quadratic approximation to the bowl, find the orthogonal eigen vectors and values, and then make some rapid progress to the bottom. That could be conjugate gradients or Newton iteration. Then could build up an approximation to the quadratic approximation and get quasi-Newton iteration. And there were other ideas. I would guess that somewhere among the hundreds or more parameters to be adjusted, there would be at least two that would determine a bowl such as I described. But, but, okay, I can guess: The neural network has so many parameters that not doing well on a few of them doesn't make much difference.
- lawrenceyan 8y ago
  Local minima are basically equivalent to global minimum in the high dimensionalities achieved in deep learning. It's not even just a conjecture by the way. This has been mathematically proven.
  - pchiusano 8y ago
    Could you link to your source? I recall seeing some research on this topic but I got the impression (perhaps wrongly) it has to make so many simplifying assumptions to get a result that it’s not clear how much carries over to real systems where not all those assumptions hold.
  - MereInterest 8y ago
    Is there a name for this theorem? I'd be interested in reading more about it.
    - asplake 8y ago
      If I understand the Wikipedia page for SGD correctly, it’s the Robbins Siegmund theorem.
andbberger 8y ago
tangent: all the backprop mysticism drives me nuts. it's just the chain rule...
- bitL 8y ago
  Most people couldn't pass calculus 101 so it's mysticism for them. Operations research people on the other hand must be shaking their heads that somebody still uses it and probably can't believe whole state-of-art is based off their most stupid method.
  - adamnemecek 8y ago
    Ok what's state of the art OR?
  - jefft255 8y ago
    You known, ML researchers are aware of the enormous body of research in optimization. A lot of these methods simply do not work or scale well to deep neural networks. Second order methods have been tried and are not worth the cost.
    - siekmanj 8y ago
      I mean, don’t most researchers use Adam? As far as I know that is a second-order method.
      - jefft255 8y ago
        Nope! Sorry I can’t take more time to explain but there is no second derivative used in Adam.
        andbberger 8y ago
        From the paper > We propose Adam, a method for efficient stochastic optimization that only requires first-order gradients with little memory requirement. The method computes individual adaptive learning rates for different parameters from estimates of first and second moments of the gradients Most of the popular variants of SGD use approximations of the hessian in one way or another
m0zg 8y ago
To a practitioner the title sounds like "water is wet" or "air is breathable".
conjectures 8y ago
Here, lemme fix that for you: 'Backpropogation Is Just Steepest Descent'
xiaodai 8y ago
Interesting that at end of the blog there are mentiond of native support to AD which appearing in Julia and Swift

122 points by adamnemecek 8y ago

The article seems good (although dated). See http://www.jmlr.org/papers/v18/17-468.html http://www.jmlr.org/papers/v18/17-468.html for an in depth survey from last year. But reading the title, I was like "well... sure?". Bad title for this article.

brilee 8y ago

This title is really confused - backpropagation is one implementation of automatic differentiation, and yields a gradient. What you do with that gradient next is up to you - you can just follow it (steepest descent), or try other fancier second order techniques.

electricslpnsld 8y ago
Can you get second order with only the gradient? Even fancy accelerated gradient descents are still first order. I suppose there are BFGS-like quasi Newton methods, but those are still building up estimates of the second order info over multiple iterations.
- deleted 8y ago
  [deleted]
- vbarrielle 8y ago
  You can get closer to second order if your error is a sum of squares of the form 0.5 * f^T * f, in which case you case compute the jacobian J of the fitness f, and approximate your hessian as J^T * J. That's the Gauss-Newton method and it's very effective if a linear approximation of f holds locally. That's an approximation but that's arguably a second order method, since it acknowledges the nonlinearity coming from the squared norm of f.

graycat 8y ago

I've always wondered how the neural network parameter fitting got away with using just steepest descent: In such fully or largely unconstrained optimization, going way back, decades, steepest descent was seen as often poor. The usual, first analogy was finding the bottom of a convex bowl that was long and narrow. Then steepest descent would keep going down hill parallel to essentially the short axis of the bowl and make nearly no progress along the long axis. So, sure, the idea was make a quadratic approximation to the bowl, find the orthogonal eigen vectors and values, and then make some rapid progress to the bottom. That could be conjugate gradients or Newton iteration. Then could build up an approximation to the quadratic approximation and get quasi-Newton iteration. And there were other ideas. I would guess that somewhere among the hundreds or more parameters to be adjusted, there would be at least two that would determine a bowl such as I described. But, but, okay, I can guess: The neural network has so many parameters that not doing well on a few of them doesn't make much difference.

lawrenceyan 8y ago
Local minima are basically equivalent to global minimum in the high dimensionalities achieved in deep learning. It's not even just a conjecture by the way. This has been mathematically proven.
- pchiusano 8y ago
  Could you link to your source? I recall seeing some research on this topic but I got the impression (perhaps wrongly) it has to make so many simplifying assumptions to get a result that it’s not clear how much carries over to real systems where not all those assumptions hold.
- MereInterest 8y ago
  Is there a name for this theorem? I'd be interested in reading more about it.
  - asplake 8y ago
    If I understand the Wikipedia page for SGD correctly, it’s the Robbins Siegmund theorem.

andbberger 8y ago

tangent: all the backprop mysticism drives me nuts. it's just the chain rule...

bitL 8y ago
Most people couldn't pass calculus 101 so it's mysticism for them. Operations research people on the other hand must be shaking their heads that somebody still uses it and probably can't believe whole state-of-art is based off their most stupid method.
- adamnemecek 8y ago
  Ok what's state of the art OR?
- jefft255 8y ago
  You known, ML researchers are aware of the enormous body of research in optimization. A lot of these methods simply do not work or scale well to deep neural networks. Second order methods have been tried and are not worth the cost.
  - siekmanj 8y ago
    I mean, don’t most researchers use Adam? As far as I know that is a second-order method.
    - jefft255 8y ago
      Nope! Sorry I can’t take more time to explain but there is no second derivative used in Adam.
      - andbberger 8y ago
        From the paper > We propose Adam, a method for efficient stochastic optimization that only requires first-order gradients with little memory requirement. The method computes individual adaptive learning rates for different parameters from estimates of first and second moments of the gradients Most of the popular variants of SGD use approximations of the hessian in one way or another

m0zg 8y ago

To a practitioner the title sounds like "water is wet" or "air is breathable".

conjectures 8y ago

Here, lemme fix that for you: 'Backpropogation Is Just Steepest Descent'

xiaodai 8y ago

Interesting that at end of the blog there are mentiond of native support to AD which appearing in Julia and Swift