5 ms·

Beyond Gradient Averaging in Parallel Optimization

96 points by shinryudbz 2y ago

SubiculumCode 2y ago
Is this the paper that the cohost of 'Last Week in AI' said was the paper of the quarter to read back to front?
cgdl 2y ago
Very interesting. A related paper from a couple of years ago proposed a similar idea to understand generalization in deep learning: https://arxiv.org/abs/2203.10036 https://arxiv.org/abs/2203.10036
timmg 2y ago
As someone who only has a passing understanding of parallel training, I always found it wonderful that averaging gradients works at all. It seems non-intuitive to me. Pretty cool, imho, that there are finding better ways to train in parallel.
- d3m0t3p 2y ago
  Well, it's just like stochastic gradient descent, if you think about it. The normal gradient descent is computed using the whole training set. The stochastic gradient is trained on a batch (a subset of the training set), and in the distributed case, we compute two batches at once by doing the gradient on each in parallel. The intuition works IMO, but indeed, having the first batch update and then the second, is not equal to having the mean update. This is indeed super cool !
  - eru 2y ago
    Does anyone actually use the 'normal gradient descent' with the whole training set? I only ever see it as a sort of straw man to make explanation easier.
    - bravura 2y ago
      Full batch with L-BFGS, when possible, is wildly underappreciated.
    - jey 2y ago
      Generally yes, vanilla gradient descent gets plenty of use. But for LLMs: no, it’s not really used, and stochastic gradient descent provides a form of regularization, so it probably works better in addition to being more practical.
eru 2y ago
> We show this technique consistently outperforms validation accuracy, in some cases by up to 18.2\% compared to traditional training approaches while reducing the computation required nearly an order of magnitude because we can now rely on smaller microbatch sizes without destabilizing training. The accuracy improvement is great, but I'm really looking forward to the reduction in computation required!
- fchaubard 2y ago
  Yes it will allow stable training at much smaller batch sizes. Test it out and let us know if it works for your use case!
deddy 2y ago
Co-author here. Super excited to see this work posted on HN! Happy to answer questions.
- timmg 2y ago
  From a non-expert here (maybe a dumb question): does “batching” affect quality in a similar way as averaging parallel batches? (Like is there a difference between having a batch that is 10x the size versus averaging 10 batches that were calculated in parallel?)
  - deddy 2y ago
    Great question! There are a few different aspects to this. With gradient agreement filtering having a greater number of batches (generally) increases the likelihood of finding another microbatch that agrees with the gradient simply by virtue of having more gradient "samples" to compare. So having more batches increases the chance of success there. The algorithm as laid out in the paper is a simple approach to combining groups of batches where larger numbers batches doesn't necessarily improve you chances of success if the batch you're comparing against is an outlier itself. There are almost certainly better ways of combining greater numbers of batches to get a successful update. This is one of the exciting areas of future work. Increasing the batch size generally can be though of as "averaging" out the noise in your samples to find a consistent update. This has an interesting affect though where that as you increase the batch size, when using gradient agreement filtering you want to lower the filter threshold as your batch size increases to become "stricter" in terms of the level of agreement to look for to accept a gradient. This is Figure 9 of the paper. This is also consistent with what other researchers have found that simply increasing batch size isn't always better. There is a trade here with diminishing returns of increasing batch size as well (https://arxiv.org/abs/1812.06162 https://arxiv.org/abs/1812.06162). One interesting finding from the work was that smaller batch sizes actually improved training accuracy for CIFAR-100N, very roughly speaking this can be explained by having more "signal" in each batch with smaller batch sizes, at the cost of potentially throwing out batches/gradients if they disagree.
- fchaubard 2y ago
amarcheschi 2y ago
Not entirely related: I've just ended my internship at the Italian research council, where I worked on implementing federated learning algorithms on a simulator to make benchmarking easy. I couldn't finish my job because an algorithm I was trying to port developed by IBM had hardcoded values that prevented the algorithm from working with different models than the ones already coded by them in their code. There was also a comment like "this is hardcoded for now, will be changed later" yeah last commit was 4 years ago https://github.com/IBM/FedMA https://github.com/IBM/FedMA
- niemandhier 2y ago
  Can you link to the lines(s). I’d like to understand what the problem is.
- deleted 2y ago
  [deleted]
woadwarrior01 2y ago
Very interesting idea! Reminiscent of this robust learning paper[1] from 2020, where they do something even simpler: zero out elements in gradients with inconsistent signs, before averaging them. [1]: https://arxiv.org/abs/2009.00329 https://arxiv.org/abs/2009.00329
- fchaubard 2y ago
  Hey thanks! Ya we tried similar strategies to this and could not beat cosine distance < tau, average, else skip. It was too much to put in the paper and we may put it in the arxiv version but we tried Sign AND gating and zero’ing out if the signs don’t agree, we tried L2<tau, etc but nothing beat cosine distance.
- gwern 2y ago
  I'm also reminded of top-_k_ training/sampling, where you throw away the inconsistent samples: https://arxiv.org/abs/2002.06224 https://arxiv.org/abs/2002.06224 "Top-k Training of GANs: Improving GAN Performance by Throwing Away Bad Samples", Sinha et al 2020. Which seems like it would be roughly equivalent to throwing away gradients if they are inconsistent...?

96 points by shinryudbz 2y ago

Is this the paper that the cohost of 'Last Week in AI' said was the paper of the quarter to read back to front?

cgdl 2y ago

Very interesting. A related paper from a couple of years ago proposed a similar idea to understand generalization in deep learning: https://arxiv.org/abs/2203.10036 https://arxiv.org/abs/2203.10036

timmg 2y ago

As someone who only has a passing understanding of parallel training, I always found it wonderful that averaging gradients works at all. It seems non-intuitive to me. Pretty cool, imho, that there are finding better ways to train in parallel.

d3m0t3p 2y ago
Well, it's just like stochastic gradient descent, if you think about it. The normal gradient descent is computed using the whole training set. The stochastic gradient is trained on a batch (a subset of the training set), and in the distributed case, we compute two batches at once by doing the gradient on each in parallel. The intuition works IMO, but indeed, having the first batch update and then the second, is not equal to having the mean update. This is indeed super cool !
- eru 2y ago
  Does anyone actually use the 'normal gradient descent' with the whole training set? I only ever see it as a sort of straw man to make explanation easier.
  - bravura 2y ago
    Full batch with L-BFGS, when possible, is wildly underappreciated.
  - jey 2y ago
    Generally yes, vanilla gradient descent gets plenty of use. But for LLMs: no, it’s not really used, and stochastic gradient descent provides a form of regularization, so it probably works better in addition to being more practical.

eru 2y ago

> We show this technique consistently outperforms validation accuracy, in some cases by up to 18.2\% compared to traditional training approaches while reducing the computation required nearly an order of magnitude because we can now rely on smaller microbatch sizes without destabilizing training. The accuracy improvement is great, but I'm really looking forward to the reduction in computation required!

fchaubard 2y ago
Yes it will allow stable training at much smaller batch sizes. Test it out and let us know if it works for your use case!

deddy 2y ago

Co-author here. Super excited to see this work posted on HN! Happy to answer questions.

timmg 2y ago
From a non-expert here (maybe a dumb question): does “batching” affect quality in a similar way as averaging parallel batches? (Like is there a difference between having a batch that is 10x the size versus averaging 10 batches that were calculated in parallel?)
- deddy 2y ago
  Great question! There are a few different aspects to this. With gradient agreement filtering having a greater number of batches (generally) increases the likelihood of finding another microbatch that agrees with the gradient simply by virtue of having more gradient "samples" to compare. So having more batches increases the chance of success there. The algorithm as laid out in the paper is a simple approach to combining groups of batches where larger numbers batches doesn't necessarily improve you chances of success if the batch you're comparing against is an outlier itself. There are almost certainly better ways of combining greater numbers of batches to get a successful update. This is one of the exciting areas of future work. Increasing the batch size generally can be though of as "averaging" out the noise in your samples to find a consistent update. This has an interesting affect though where that as you increase the batch size, when using gradient agreement filtering you want to lower the filter threshold as your batch size increases to become "stricter" in terms of the level of agreement to look for to accept a gradient. This is Figure 9 of the paper. This is also consistent with what other researchers have found that simply increasing batch size isn't always better. There is a trade here with diminishing returns of increasing batch size as well (https://arxiv.org/abs/1812.06162 https://arxiv.org/abs/1812.06162). One interesting finding from the work was that smaller batch sizes actually improved training accuracy for CIFAR-100N, very roughly speaking this can be explained by having more "signal" in each batch with smaller batch sizes, at the cost of potentially throwing out batches/gradients if they disagree.
fchaubard 2y ago

amarcheschi 2y ago

Not entirely related: I've just ended my internship at the Italian research council, where I worked on implementing federated learning algorithms on a simulator to make benchmarking easy. I couldn't finish my job because an algorithm I was trying to port developed by IBM had hardcoded values that prevented the algorithm from working with different models than the ones already coded by them in their code. There was also a comment like "this is hardcoded for now, will be changed later" yeah last commit was 4 years ago https://github.com/IBM/FedMA https://github.com/IBM/FedMA

niemandhier 2y ago
Can you link to the lines(s). I’d like to understand what the problem is.
deleted 2y ago
[deleted]

woadwarrior01 2y ago

Very interesting idea! Reminiscent of this robust learning paper[1] from 2020, where they do something even simpler: zero out elements in gradients with inconsistent signs, before averaging them. [1]: https://arxiv.org/abs/2009.00329 https://arxiv.org/abs/2009.00329

fchaubard 2y ago
Hey thanks! Ya we tried similar strategies to this and could not beat cosine distance < tau, average, else skip. It was too much to put in the paper and we may put it in the arxiv version but we tried Sign AND gating and zero’ing out if the signs don’t agree, we tried L2<tau, etc but nothing beat cosine distance.
gwern 2y ago
I'm also reminded of top-_k_ training/sampling, where you throw away the inconsistent samples: https://arxiv.org/abs/2002.06224 https://arxiv.org/abs/2002.06224 "Top-k Training of GANs: Improving GAN Performance by Throwing Away Bad Samples", Sinha et al 2020. Which seems like it would be roughly equivalent to throwing away gradients if they are inconsistent...?