4 ms·

Fantastic work. They do rely on floating point numbers for the weight updates (I was secretly hoping that they would have binarized gradient descent).

karmacondon 11y ago
What would be the advantage of binarized gradient descent?
- jimfleming 11y ago
  For one, more compression during parameter transfer in data parallelism scenarios.
  - tachyonbeam 11y ago
    And maybe the possibility of building more efficient hardware. Floating point units take up a lot of transistors (in the ~100K transistor range AFAIK), whereas boolean logic is tiny.
    - Scaevolus 11y ago
      Going to 1-bit precision is probably overkill, but papers have shown how neural networks with 8 bits of precision and simple ALUs can give results equivalent to full FPUs.
li-ch 11y ago
Seems that CNTK already implemented this. https://github.com/Microsoft/CNTK/wiki/Enabling-1bit-SGD https://github.com/Microsoft/CNTK/wiki/Enabling-1bit-SGD
- modeless 11y ago
  That quantizes the gradient for compression of the communication between nodes, which is cool, but each node must still calculate a 32 bit floating point gradient locally. What GP is asking for is a way to avoid having any floating point math at all. If you could implement training with only single-bit operations rather than floating point math, a hardware implementation could be several orders of magnitude faster and more efficient than current CPUs/GPUs. That would certainly usher in a revolution in computer architecture.
nl 11y ago
The Nervana 16bit floating point implementations is probably worth noting in this context. They perform (speed-wise) pretty well: https://github.com/soumith/convnet-benchmarks https://github.com/soumith/convnet-benchmarks
Houshalter 11y ago
It can't work with gradient descent, which requires about 16 bits of precision. The problem is the gradients are small, and so are rounded down to zero. Then when added together they get zero, even though the number should be higher. However it's been shown this can be solved by using stochastic rounding. But I believe that would require specialized hardware to implement. I'm not sure.
- hacker42 11y ago
  > It can't work with gradient descent, which requires about 16 bits of precision. Has this been mathematically proven, can you provide a source?
  - mjw 11y ago
    It's more an empirically-verified thing than a mathematical fact, there's nothing magic about 16 bits AFAIK. Empirically 16 bits seems to work well enough for some tasks, taking it down to 8 bits is usually taking it too far, and performance-wise there's not a lot of point playing with values in between e.g. 12 bits. (Half-float arithmetic is implemented natively in recent CUDA CC5 architectures and is quite convenient, in particular it reduces memory bandwidth by 1/2 which is often the bottleneck.) Stochastic gradient descent is fairly robust to noisy gradients -- any numerical or quantisation error that you can model approximately as independent zero-mean noise can be 'rolled into the noise term' for SGD without affecting the theory around convergence [0]. It will increase the variance of course, which when taken too far could in practise mean divergence or slow convergence under a reduced learning rate, perhaps to a poorer local minimum. Extreme quantisation (like binarisation) the error can't really be modelled as independent zero-mean, UNLESS you do the kind of stochastic quantisation mentioned. From what I hear this works well enough to allow convergence, but accuracy can take quite a hit. I don't think it has to be 'implemented natively', although no doubt that would speed it up, a large part of the benefit of quantisation during training is not so much to speed up arithmetic as to reduce memory bandwidth and communication latency. [0] https://en.wikipedia.org/wiki/Stochastic_approximation#Robbins.E2.80.93Monro_algorithm https://en.wikipedia.org/wiki/Stochastic_approximation#Robbi...
- 11y ago

karmacondon 11y ago

What would be the advantage of binarized gradient descent?

jimfleming 11y ago
For one, more compression during parameter transfer in data parallelism scenarios.
- tachyonbeam 11y ago
  And maybe the possibility of building more efficient hardware. Floating point units take up a lot of transistors (in the ~100K transistor range AFAIK), whereas boolean logic is tiny.
  - Scaevolus 11y ago
    Going to 1-bit precision is probably overkill, but papers have shown how neural networks with 8 bits of precision and simple ALUs can give results equivalent to full FPUs.

li-ch 11y ago

Seems that CNTK already implemented this. https://github.com/Microsoft/CNTK/wiki/Enabling-1bit-SGD https://github.com/Microsoft/CNTK/wiki/Enabling-1bit-SGD

modeless 11y ago
That quantizes the gradient for compression of the communication between nodes, which is cool, but each node must still calculate a 32 bit floating point gradient locally. What GP is asking for is a way to avoid having any floating point math at all. If you could implement training with only single-bit operations rather than floating point math, a hardware implementation could be several orders of magnitude faster and more efficient than current CPUs/GPUs. That would certainly usher in a revolution in computer architecture.

nl 11y ago

The Nervana 16bit floating point implementations is probably worth noting in this context. They perform (speed-wise) pretty well: https://github.com/soumith/convnet-benchmarks https://github.com/soumith/convnet-benchmarks

Houshalter 11y ago

It can't work with gradient descent, which requires about 16 bits of precision. The problem is the gradients are small, and so are rounded down to zero. Then when added together they get zero, even though the number should be higher. However it's been shown this can be solved by using stochastic rounding. But I believe that would require specialized hardware to implement. I'm not sure.

hacker42 11y ago
> It can't work with gradient descent, which requires about 16 bits of precision. Has this been mathematically proven, can you provide a source?
- mjw 11y ago
  It's more an empirically-verified thing than a mathematical fact, there's nothing magic about 16 bits AFAIK. Empirically 16 bits seems to work well enough for some tasks, taking it down to 8 bits is usually taking it too far, and performance-wise there's not a lot of point playing with values in between e.g. 12 bits. (Half-float arithmetic is implemented natively in recent CUDA CC5 architectures and is quite convenient, in particular it reduces memory bandwidth by 1/2 which is often the bottleneck.) Stochastic gradient descent is fairly robust to noisy gradients -- any numerical or quantisation error that you can model approximately as independent zero-mean noise can be 'rolled into the noise term' for SGD without affecting the theory around convergence [0]. It will increase the variance of course, which when taken too far could in practise mean divergence or slow convergence under a reduced learning rate, perhaps to a poorer local minimum. Extreme quantisation (like binarisation) the error can't really be modelled as independent zero-mean, UNLESS you do the kind of stochastic quantisation mentioned. From what I hear this works well enough to allow convergence, but accuracy can take quite a hit. I don't think it has to be 'implemented natively', although no doubt that would speed it up, a large part of the benefit of quantisation during training is not so much to speed up arithmetic as to reduce memory bandwidth and communication latency. [0] https://en.wikipedia.org/wiki/Stochastic_approximation#Robbins.E2.80.93Monro_algorithm https://en.wikipedia.org/wiki/Stochastic_approximation#Robbi...
11y ago