6 ms·

Always caution someone who wants to follow in this research: When somebody promotes a fast algorithm there is often a catch. In this case the issue is numerical

Always caution someone who wants to follow in this research: When somebody promotes a fast algorithm there is often a catch. In this case the issue is numerical stability. There is a theorem that states that any algorithm for n-by-n matrix-matrix multiplication that is componentwise forward stable (as good as it gets in this situation) much necessarily use n^3 scalar multiplications. The authors will therefore waste their time if they carry out their plans and try to optimize for stability. The standard algorithm has the nice property and no faster algorithm can have this property. The question of fast matrix multiplication was raised recently on mathoverflow.net, see https://mathoverflow.net/q/421304/110176 https://mathoverflow.net/q/421304/110176 and the answers given there.

ekelsen 4y ago
In practice you don't need to recurse all the way down. 1 level of Strassen is enough to get real speeedups (if speedups are possible at all) and certainly for deep learning, the instability introduced by a single level will not matter.
- zekrioca 4y ago
  Do we need forward stability in the componentwise relative sense? This very much depends on the underlying real life application. If we ignore the question of accuracy and stability, then we just might endanger the people who depend on our software.
  - ekelsen 4y ago
    That's why I specified the application was deep learning.
KKKKkkkk1 4y ago
We're talking about algorithms for TPUs, which quietly quantize your float32 matrices to bfloat16 behind your back [0]. This is aimed at a crowd that doesn't care about stability. [0] https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus https://cloud.google.com/blog/products/ai-machine-learning/b...
- johndfsgdgdfg 4y ago
  I am not a fan of Google. But this is such a bizzare, deliberately misleading, snarky comment. Lower precision floating point arithmetic is very common in ML training. There's no 'behind your back' going on here.
- WithinReason 4y ago
  If there are in fact stability issues, I wonder which is cheaper: using this fancy algorithm or changing bfloat16 to something like bfloat14 and using a more stable matmul.
- why_only_15 4y ago
  bfloat16 is stable enough for ML training, which is what TPUs exist for
  - rubatuga 4y ago
    Not always though!
  - pfortuny 4y ago
    Be careful: 16 bits was quite a lot of colors around 20 years ago. Now we would laugh at it. Ditto for 640Kb of RAM (who would need more?) etc. Not trying to be dismissive just saying that... computational limits are limits on what can be done, in the end.
    - mjan22640 4y ago
      30 years ago. The time flies...
      - pfortuny 4y ago
        well, you are right and I grow old, I grow old, I shall wear the bottoms of my trousers rolled… I stand corrected.
    - omegalulw 4y ago
benreesman 4y ago
They’re obviously talking about bfloat on TPU. The day when a lot of wrong math adds up to a computer drawing a pretty picture. Who would have thought.
joppy 4y ago
When working over a finite field there are no stability issues though, since arithmetic is exact.
- zekrioca 4y ago
  It will always depend on the application.
chrisshroba 4y ago
Excuse my lack of knowledge here, but what is stability?
- zekrioca 4y ago
  Numerical stability is when you do operations on the matrix while still keeping an eye on the overflow and underflow flags, all the way during the algorithm execution. This means regardless of how big your matrix is, or how big or small your numbers are — or even the relation between them —, you algorithm is going to be stable and accurate. If it can't be (stable), the library must let you know. This is so you can keep the numbers scaled such that they are not too large, nor too small in order to keep them stable for the operations you need to execute.
hackpert 4y ago
While your point about numerical stability is correct in general, there are no numerical stability issues here and I think this conception, which I've seen in more than one place now, stems from a fundamental misunderstanding of the paper's results. While they _did_ come up with a faster TPU/GPU algorithm too, the primary result is not a fast matmul approximation, it is an exact algorithm comprising of stepwise addition/multiplication operations, and hence is numerically stable and should work for any ring (https://ncatlab.org/nlab/show/ring https://ncatlab.org/nlab/show/ring). AlphaTensor itself does not do the matrix multiplication, it was used to perform an (efficiently pruned) tree search over the space of operations to find an efficient, stable algorithm.
- zekrioca 4y ago
  Directly from the paper’s "Discussion" section: > One important strength of AlphaTensor is its flexibility to support complex stochastic and non-differentiable rewards (from the tensor rank to practical efficiency on specific hardware), in addition to finding algorithms for custom operations in a wide variety of spaces (such as finite fields). We believe this will spur applications of AlphaTensor towards designing algorithms that optimize metrics that we did not consider here, such as numerical stability or energy usage.
  - hackpert 4y ago
    Right, but doesn't that mean that it could potentially be used for designing algorithms that have componentwise numerical stability over some kind of floating point standard, but this, by definition being a result over finite fields, should be numerically stable? (apologies if I misunderstood, I wasn't calling you out specifically but a generalized misconception I've noticed in a lot of other discussions so far)

ekelsen 4y ago

In practice you don't need to recurse all the way down. 1 level of Strassen is enough to get real speeedups (if speedups are possible at all) and certainly for deep learning, the instability introduced by a single level will not matter.

zekrioca 4y ago
Do we need forward stability in the componentwise relative sense? This very much depends on the underlying real life application. If we ignore the question of accuracy and stability, then we just might endanger the people who depend on our software.
- ekelsen 4y ago
  That's why I specified the application was deep learning.

KKKKkkkk1 4y ago

We're talking about algorithms for TPUs, which quietly quantize your float32 matrices to bfloat16 behind your back [0]. This is aimed at a crowd that doesn't care about stability. [0] https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus https://cloud.google.com/blog/products/ai-machine-learning/b...

johndfsgdgdfg 4y ago
I am not a fan of Google. But this is such a bizzare, deliberately misleading, snarky comment. Lower precision floating point arithmetic is very common in ML training. There's no 'behind your back' going on here.
WithinReason 4y ago
If there are in fact stability issues, I wonder which is cheaper: using this fancy algorithm or changing bfloat16 to something like bfloat14 and using a more stable matmul.
why_only_15 4y ago
bfloat16 is stable enough for ML training, which is what TPUs exist for
- rubatuga 4y ago
  Not always though!
- pfortuny 4y ago
  Be careful: 16 bits was quite a lot of colors around 20 years ago. Now we would laugh at it. Ditto for 640Kb of RAM (who would need more?) etc. Not trying to be dismissive just saying that... computational limits are limits on what can be done, in the end.
  - mjan22640 4y ago
    30 years ago. The time flies...
    - pfortuny 4y ago
      well, you are right and I grow old, I grow old, I shall wear the bottoms of my trousers rolled… I stand corrected.
  - omegalulw 4y ago

benreesman 4y ago

They’re obviously talking about bfloat on TPU. The day when a lot of wrong math adds up to a computer drawing a pretty picture. Who would have thought.

joppy 4y ago

When working over a finite field there are no stability issues though, since arithmetic is exact.

zekrioca 4y ago
It will always depend on the application.

chrisshroba 4y ago

Excuse my lack of knowledge here, but what is stability?

zekrioca 4y ago
Numerical stability is when you do operations on the matrix while still keeping an eye on the overflow and underflow flags, all the way during the algorithm execution. This means regardless of how big your matrix is, or how big or small your numbers are — or even the relation between them —, you algorithm is going to be stable and accurate. If it can't be (stable), the library must let you know. This is so you can keep the numbers scaled such that they are not too large, nor too small in order to keep them stable for the operations you need to execute.

hackpert 4y ago

While your point about numerical stability is correct in general, there are no numerical stability issues here and I think this conception, which I've seen in more than one place now, stems from a fundamental misunderstanding of the paper's results. While they _did_ come up with a faster TPU/GPU algorithm too, the primary result is not a fast matmul approximation, it is an exact algorithm comprising of stepwise addition/multiplication operations, and hence is numerically stable and should work for any ring (https://ncatlab.org/nlab/show/ring https://ncatlab.org/nlab/show/ring). AlphaTensor itself does not do the matrix multiplication, it was used to perform an (efficiently pruned) tree search over the space of operations to find an efficient, stable algorithm.

zekrioca 4y ago
Directly from the paper’s "Discussion" section: > One important strength of AlphaTensor is its flexibility to support complex stochastic and non-differentiable rewards (from the tensor rank to practical efficiency on specific hardware), in addition to finding algorithms for custom operations in a wide variety of spaces (such as finite fields). We believe this will spur applications of AlphaTensor towards designing algorithms that optimize metrics that we did not consider here, such as numerical stability or energy usage.
- hackpert 4y ago
  Right, but doesn't that mean that it could potentially be used for designing algorithms that have componentwise numerical stability over some kind of floating point standard, but this, by definition being a result over finite fields, should be numerically stable? (apologies if I misunderstood, I wasn't calling you out specifically but a generalized misconception I've noticed in a lot of other discussions so far)