6 ms·

Gradients Without Backpropagation

87 points by hcks 5y ago

hcks 5y ago
I would like to have some expert feedback on how meaningful this line of research is. The paper is quite straightforward, but the implications are unclear to me. Is there a chance that backpropagation is superseded by this method for some use cases ? Another question is, if this result is as interesting as it seems to me, how come this is only published in 2022 given the past research effort in the area of deep learning ?
- beecafe 5y ago
  It's not that novel, they're just computing the "directional derivative" in a random direction. It's similar to the research OpenAI has done on Evolution Strategies - basically, trading off a more noisy gradient but getting optimization with less inter process communication, achieving scale. This work is somewhere in between ES and normal backprop. Usually progress moves in a see-saw fashion, with scaling up (and the techniques needed) bringing improvement, then they becoming compressed/found unnecessary as the real cause is found, etc..
  - iandanforth 5y ago
    I'm sure you know this but for others ES is gradient free. Population sampling for optimization is distinct from 'gradient based' techniques in the literature.
l33tman 5y ago
Already discussed a few days ago on HN (don't have the link...)
- MaysonL 5y ago
  Click the "past" link under the article title above to search for previous discussions.
  - melling 5y ago
    Looks like it was submitted a couple of times but without traction or comments https://hn.algolia.com/?dateRange=pastMonth&page=0&prefix=true&query=gradient%20back&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=pastMonth&page=0&prefix=tr...
mdp2021 5y ago
Copy of the abstract for quick local reference: > Using backpropagation to compute gradients of objective functions for optimization has remained a mainstay of machine learning. Backpropagation, or reverse-mode differentiation, is a special case within the general family of automatic differentiation algorithms that also includes the forward mode. We present a method to compute gradients based solely on the directional derivative that one can compute exactly and efficiently via the forward mode. We call this formulation the forward gradient, an unbiased estimate of the gradient that can be evaluated in a single forward run of the function, entirely eliminating the need for backpropagation in gradient descent. We demonstrate forward gradient descent in a range of problems, showing substantial savings in computation and enabling training up to twice as fast in some cases. -- They have an implementation of the "forward gradient" for PyTorch. Is any implementation in C available?
- GistNoesis 5y ago
  You can use Tapenade in tangent mode if you want to generate forward derivative in the desired direction. http://www-tapenade.inria.fr:8080/tapenade/ http://www-tapenade.inria.fr:8080/tapenade/
- Fronzie 5y ago
  http://ceres-solver.org/ http://ceres-solver.org/ works well, in my experience. It does require code to be templated, which might increase computation time. It is possible to explicitly define derivatives for individual functions, this can help preventing numerical instabilities in corner cases.
- cyber_kinetist 5y ago
  Forward-mode differentiation is easy to implement in C++ with templates, operator overloading, and dual numbers (https://en.wikipedia.org/wiki/Automatic_differentiation#Automatic_differentiation_using_dual_numbers https://en.wikipedia.org/wiki/Automatic_differentiation#Auto...). Some libraries such as autodiff (https://github.com/autodiff/autodiff https://github.com/autodiff/autodiff) and CppAD (https://github.com/coin-or/CppAD https://github.com/coin-or/CppAD) use this method to calculate gradients and Jacobians.
murbard2 5y ago
I skimmed the paper, so I'm not sure I got this right, but my understanding is the following: 1. pick a random direction 2. compute the derivative along that direction using forward-mode differentiation 3. update the parameters along that direction based on the derivative The idea being that this gives an unbiased (albeit noisy) approximation of the actual gradient. You thus need a smaller learning rate, but you also need less memory and computation and, net net, they argue it's a win. Is this correct?
- murbard2 5y ago
  I wonder if there's any value in picking not one but a couple random directions, and then finding the update in their span. Increases memory consumption but reduces the noise. It could be that the trade-off is best when picking a single direction, but who knows? If you pick 2 directions at each pass, one of them could be the direction of the last update and the other a random one, allowing for some kind of momentum.
  - WithinReason 5y ago
    Choosing the direction of travel to measure he gradient in or sampling around it makes sense to me too.
  - GistNoesis 5y ago
    Yes there is value, but there is also some cost, and this value can be grabbed naturally by using an optimizer that can make use of multiple direction. Optimizer like O-LBFGS maintain internally a low-dimension quadratic approximation of the cost function, that is updated with each noisy gradient evaluation, and then the optimizer consist of taking a step in the direction that would minimize that approximation. In the same line of thought, one can ask whether a line-search like in usual optimization algorithms is worth it or not. The memory cost is usually storing the parameters multiple times and an increase computing cost per iteration. Whether the tradeoff is worth it or not is usually problem dependent. Using a quadratic approximation is more costly than using a linear interpolation but it often pays off when encountering saddle points. There are also technique like Polyak averaging (parameter tracking, Teacher-Student...) that have some success in Reinforcement Learning, where they help to regularize the energy landscape. OpenAI "Evolution Strategy" used a low number of random directions, and they found that they needed roughly ~100 (= implicit dimension of the problem) directions to have equivalent performance than backprop, but they were computing the derivative with finite difference instead of forward differentiation.
mrfusion 5y ago
Could this be closer to how the brain works? Have we ruled it brains using back propagation?
- WithinReason 5y ago
  I think there's a chance it's similar, I'm not a neuroscientist though. The paper says: "This could potentially change the computational complexity of typical ML training pipelines, reduce the time and energy costs of training, influence ML hardware design, and even have implications regarding the biological plausibility of backpropagation in the brain (Bengio et al., 2015; Lillicrap et al., 2020)."
- tommiegannert 5y ago
  This paper from a couple of weeks ago suggested that neurons may learn as part of maximizing their energy efficiency. Which suggests that each neuron learns on its own, but also helps neurons by giving some feedback. I don't think it fully answered how that feedback happens (backprop or multiple forward passes), but it may be of interest to you nonetheless. https://www.nature.com/articles/s42256-021-00430-y https://www.nature.com/articles/s42256-021-00430-y
p1esk 5y ago
The idea is interesting. Unfortunately the authors didn’t bother to test it, and haven’t published the code. So until they do, or someone implements and tries it with something like resnet-50 and imagenet we don’t know how well it works.
WithinReason 5y ago
Whenever I see an ML paper with surprising results I'm usually sceptical, as the results often come down to one of the following: 1. The assumptions don't generalize 2. The observations don't imply the conclusions from the paper 3. Hyper-parameter shenanigans: It's usually possible to choose hyper-parameters where method A is better than B, even if generally B is better. In this case the lower-left part of figure 4 makes me suspicious, since forward mode seems to be better than reverse mode even on a per-iteration basis, which makes me suspect that they chose hyper-parameters where reverse mode has a disadvantage.
- koningrobot 5y ago
  Yes, I've worked with this exact algorithm before, and others like it, and it should be much worse. Better than finite diffs or reinforce, but way worse than backprop's exact gradients, to the point of being unusable. Moreover the variance of the estimate grows with the number of parameters, so it gets worse still on bigger problems.
nicholast 5y ago
They cited some of LeCun's solo work from the 80's on related matters, note that he also collaborated with Geoffrey Hinton on a related paper from NIPS 89 in which they used random perturbations to derive a gradient signal. One of the limitations of that approach was that it required each layer to have fewer units than the preceding one. Gemini: Gradient Estimation Through Matrix Inversion After Noise Injection Yann Le Cun and Conrad C. Galland and Geoffrey E. Hinton https://proceedings.neurips.cc/paper/1988/file/a0a080f42e6f13b3a2df133f073095dd-Paper.pdf https://proceedings.neurips.cc/paper/1988/file/a0a080f42e6f1... I cited this in a recent paper because it was representative of different cases for stochastic injections in neural networks. Interesting to see that similar lines of inquiry are continuing to this day.
The_rationalist 5y ago
cyber_kinetist 5y ago
Seems to be almost identical to the previous paper for ICLR 2022: Learning by Directional Gradient Descent (by Silver et al.) (https://openreview.net/pdf?id=5i7lJLuhTm https://openreview.net/pdf?id=5i7lJLuhTm) The paper has some additional experimental analysis of the properties of the algorithms (including how many samples you should estimate per epoch), and also extends the method for training RNNs or reinforcement learning.
credit_guy 5y ago
Quite smart. No perpetual motion machine here. This forward differentiation method is not as powerful as the backward one, it does not give you the gradient of a function. Instead, you choose a direction, and it gives you the derivative along that direction. You could essentially get that by “bump and recalc”, at the cost of an additional function evaluation. I even doubt this comes at a cheaper compute cost than the brute force bump and recalculate. How about the stochastic gradient descent, if you don’t know the gradient? Well, you know the sign of the directional derivative, so you know which way is up and which is down. At each step you pick a random direction, and you move down along it. That’s it. Edit: I just implemented this descent algorithm, let’s call it Random Direction Descent. I was sure that the gradient descent outperforms it more and more for higher and higher dimensions. The exact oposite happens: this one outperforms the gradient descent, and the higher dimension, the more. This is a huge surprise for me. This descent algorithm might revolutionize ML.
- deleted 5y ago
  [deleted]
- mjburgess 5y ago
  The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. I'd expect "random direction" grad desc to improve the more dimensionality the data has, as in that space, the data surface itself is simple.
  - cracker_jacks 5y ago
    > The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. Even assuming this statement were true (which is a big if). That does not explain how it would outperform gradient descent.
    - mjburgess 5y ago
      As dimensionality grows, data is more linearly sperable, so fewer dimensions are signficant in distinguishing the data (though for any pair of points, those dimensions will be different). Grad desc, as an exhaustive search over all those dimensions "maybe" less performant in very high dimensions, where we have enough data to be "right some of the time" when randomly choosing which dim to discriminate on. If we force zero loss, ie., an interpolation regime, then we're getting interpolation as usual. Can we get there faster when dimensionality increases? It's plausible if count(relevant dimensions) << count(dimensions), and if they discriminating dimensions for any two random points is itself random.
singularity2001 5y ago
How does this approach relate to the astonishing Hinton results from 3-5 years ago?

87 points by hcks 5y ago

hcks 5y ago

I would like to have some expert feedback on how meaningful this line of research is. The paper is quite straightforward, but the implications are unclear to me. Is there a chance that backpropagation is superseded by this method for some use cases ? Another question is, if this result is as interesting as it seems to me, how come this is only published in 2022 given the past research effort in the area of deep learning ?

beecafe 5y ago
It's not that novel, they're just computing the "directional derivative" in a random direction. It's similar to the research OpenAI has done on Evolution Strategies - basically, trading off a more noisy gradient but getting optimization with less inter process communication, achieving scale. This work is somewhere in between ES and normal backprop. Usually progress moves in a see-saw fashion, with scaling up (and the techniques needed) bringing improvement, then they becoming compressed/found unnecessary as the real cause is found, etc..
- iandanforth 5y ago
  I'm sure you know this but for others ES is gradient free. Population sampling for optimization is distinct from 'gradient based' techniques in the literature.

l33tman 5y ago

Already discussed a few days ago on HN (don't have the link...)

MaysonL 5y ago
Click the "past" link under the article title above to search for previous discussions.
- melling 5y ago
  Looks like it was submitted a couple of times but without traction or comments https://hn.algolia.com/?dateRange=pastMonth&page=0&prefix=true&query=gradient%20back&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=pastMonth&page=0&prefix=tr...

mdp2021 5y ago

Copy of the abstract for quick local reference: > Using backpropagation to compute gradients of objective functions for optimization has remained a mainstay of machine learning. Backpropagation, or reverse-mode differentiation, is a special case within the general family of automatic differentiation algorithms that also includes the forward mode. We present a method to compute gradients based solely on the directional derivative that one can compute exactly and efficiently via the forward mode. We call this formulation the forward gradient, an unbiased estimate of the gradient that can be evaluated in a single forward run of the function, entirely eliminating the need for backpropagation in gradient descent. We demonstrate forward gradient descent in a range of problems, showing substantial savings in computation and enabling training up to twice as fast in some cases. -- They have an implementation of the "forward gradient" for PyTorch. Is any implementation in C available?

GistNoesis 5y ago
You can use Tapenade in tangent mode if you want to generate forward derivative in the desired direction. http://www-tapenade.inria.fr:8080/tapenade/ http://www-tapenade.inria.fr:8080/tapenade/
Fronzie 5y ago
http://ceres-solver.org/ http://ceres-solver.org/ works well, in my experience. It does require code to be templated, which might increase computation time. It is possible to explicitly define derivatives for individual functions, this can help preventing numerical instabilities in corner cases.
cyber_kinetist 5y ago
Forward-mode differentiation is easy to implement in C++ with templates, operator overloading, and dual numbers (https://en.wikipedia.org/wiki/Automatic_differentiation#Automatic_differentiation_using_dual_numbers https://en.wikipedia.org/wiki/Automatic_differentiation#Auto...). Some libraries such as autodiff (https://github.com/autodiff/autodiff https://github.com/autodiff/autodiff) and CppAD (https://github.com/coin-or/CppAD https://github.com/coin-or/CppAD) use this method to calculate gradients and Jacobians.

murbard2 5y ago

I skimmed the paper, so I'm not sure I got this right, but my understanding is the following: 1. pick a random direction 2. compute the derivative along that direction using forward-mode differentiation 3. update the parameters along that direction based on the derivative The idea being that this gives an unbiased (albeit noisy) approximation of the actual gradient. You thus need a smaller learning rate, but you also need less memory and computation and, net net, they argue it's a win. Is this correct?

murbard2 5y ago
I wonder if there's any value in picking not one but a couple random directions, and then finding the update in their span. Increases memory consumption but reduces the noise. It could be that the trade-off is best when picking a single direction, but who knows? If you pick 2 directions at each pass, one of them could be the direction of the last update and the other a random one, allowing for some kind of momentum.
- WithinReason 5y ago
  Choosing the direction of travel to measure he gradient in or sampling around it makes sense to me too.
- GistNoesis 5y ago
  Yes there is value, but there is also some cost, and this value can be grabbed naturally by using an optimizer that can make use of multiple direction. Optimizer like O-LBFGS maintain internally a low-dimension quadratic approximation of the cost function, that is updated with each noisy gradient evaluation, and then the optimizer consist of taking a step in the direction that would minimize that approximation. In the same line of thought, one can ask whether a line-search like in usual optimization algorithms is worth it or not. The memory cost is usually storing the parameters multiple times and an increase computing cost per iteration. Whether the tradeoff is worth it or not is usually problem dependent. Using a quadratic approximation is more costly than using a linear interpolation but it often pays off when encountering saddle points. There are also technique like Polyak averaging (parameter tracking, Teacher-Student...) that have some success in Reinforcement Learning, where they help to regularize the energy landscape. OpenAI "Evolution Strategy" used a low number of random directions, and they found that they needed roughly ~100 (= implicit dimension of the problem) directions to have equivalent performance than backprop, but they were computing the derivative with finite difference instead of forward differentiation.

mrfusion 5y ago

Could this be closer to how the brain works? Have we ruled it brains using back propagation?

WithinReason 5y ago
I think there's a chance it's similar, I'm not a neuroscientist though. The paper says: "This could potentially change the computational complexity of typical ML training pipelines, reduce the time and energy costs of training, influence ML hardware design, and even have implications regarding the biological plausibility of backpropagation in the brain (Bengio et al., 2015; Lillicrap et al., 2020)."
tommiegannert 5y ago
This paper from a couple of weeks ago suggested that neurons may learn as part of maximizing their energy efficiency. Which suggests that each neuron learns on its own, but also helps neurons by giving some feedback. I don't think it fully answered how that feedback happens (backprop or multiple forward passes), but it may be of interest to you nonetheless. https://www.nature.com/articles/s42256-021-00430-y https://www.nature.com/articles/s42256-021-00430-y

p1esk 5y ago

The idea is interesting. Unfortunately the authors didn’t bother to test it, and haven’t published the code. So until they do, or someone implements and tries it with something like resnet-50 and imagenet we don’t know how well it works.

WithinReason 5y ago

Whenever I see an ML paper with surprising results I'm usually sceptical, as the results often come down to one of the following: 1. The assumptions don't generalize 2. The observations don't imply the conclusions from the paper 3. Hyper-parameter shenanigans: It's usually possible to choose hyper-parameters where method A is better than B, even if generally B is better. In this case the lower-left part of figure 4 makes me suspicious, since forward mode seems to be better than reverse mode even on a per-iteration basis, which makes me suspect that they chose hyper-parameters where reverse mode has a disadvantage.

koningrobot 5y ago
Yes, I've worked with this exact algorithm before, and others like it, and it should be much worse. Better than finite diffs or reinforce, but way worse than backprop's exact gradients, to the point of being unusable. Moreover the variance of the estimate grows with the number of parameters, so it gets worse still on bigger problems.

nicholast 5y ago

They cited some of LeCun's solo work from the 80's on related matters, note that he also collaborated with Geoffrey Hinton on a related paper from NIPS 89 in which they used random perturbations to derive a gradient signal. One of the limitations of that approach was that it required each layer to have fewer units than the preceding one. Gemini: Gradient Estimation Through Matrix Inversion After Noise Injection Yann Le Cun and Conrad C. Galland and Geoffrey E. Hinton https://proceedings.neurips.cc/paper/1988/file/a0a080f42e6f13b3a2df133f073095dd-Paper.pdf https://proceedings.neurips.cc/paper/1988/file/a0a080f42e6f1... I cited this in a recent paper because it was representative of different cases for stochastic injections in neural networks. Interesting to see that similar lines of inquiry are continuing to this day.

The_rationalist 5y ago

cyber_kinetist 5y ago

Seems to be almost identical to the previous paper for ICLR 2022: Learning by Directional Gradient Descent (by Silver et al.) (https://openreview.net/pdf?id=5i7lJLuhTm https://openreview.net/pdf?id=5i7lJLuhTm) The paper has some additional experimental analysis of the properties of the algorithms (including how many samples you should estimate per epoch), and also extends the method for training RNNs or reinforcement learning.

credit_guy 5y ago

Quite smart. No perpetual motion machine here. This forward differentiation method is not as powerful as the backward one, it does not give you the gradient of a function. Instead, you choose a direction, and it gives you the derivative along that direction. You could essentially get that by “bump and recalc”, at the cost of an additional function evaluation. I even doubt this comes at a cheaper compute cost than the brute force bump and recalculate. How about the stochastic gradient descent, if you don’t know the gradient? Well, you know the sign of the directional derivative, so you know which way is up and which is down. At each step you pick a random direction, and you move down along it. That’s it. Edit: I just implemented this descent algorithm, let’s call it Random Direction Descent. I was sure that the gradient descent outperforms it more and more for higher and higher dimensions. The exact oposite happens: this one outperforms the gradient descent, and the higher dimension, the more. This is a huge surprise for me. This descent algorithm might revolutionize ML.

deleted 5y ago
[deleted]
mjburgess 5y ago
The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. I'd expect "random direction" grad desc to improve the more dimensionality the data has, as in that space, the data surface itself is simple.
- cracker_jacks 5y ago
  > The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. Even assuming this statement were true (which is a big if). That does not explain how it would outperform gradient descent.
  - mjburgess 5y ago
    As dimensionality grows, data is more linearly sperable, so fewer dimensions are signficant in distinguishing the data (though for any pair of points, those dimensions will be different). Grad desc, as an exhaustive search over all those dimensions "maybe" less performant in very high dimensions, where we have enough data to be "right some of the time" when randomly choosing which dim to discriminate on. If we force zero loss, ie., an interpolation regime, then we're getting interpolation as usual. Can we get there faster when dimensionality increases? It's plausible if count(relevant dimensions) << count(dimensions), and if they discriminating dimensions for any two random points is itself random.

singularity2001 5y ago

How does this approach relate to the astonishing Hinton results from 3-5 years ago?