4 ms·

On the other hand, real world performance is really the only useful metric for matrix multiplication. I don’t really care about the theoretical performance, or

by atty 4y ago

On the other hand, real world performance is really the only useful metric for matrix multiplication. I don’t really care about the theoretical performance, or the number of operations. Not disagreeing with your take that the claim is grandiose, just pointing out that finding a generalizable way to automate the improvement of what is almost certainly the most important mathematical operation a computer can do is worth some attention. It also suggests other mathematical operations could be improved this way as well - potentially algorithms that haven’t gotten as much theoretical or practical attention as matrix multiplication. With all that said, they even point out that other people have worked on this before using other optimization strategies. I’d guess they got into Nature either by using the Deepmind name, because Nature really loves reinforcement learning because it’s a cool topic that draws views, or because they’re the first group to find their algorithm leads to real improvements. (Probably a mixture of all three, I’d guess)

psychphysic 4y ago
Surely theoretical improvement begets real world, especially in the context of highly specialised hardware. It was with theoretical performance improvement that motivated the creation of SIMD and led to real world speed ups.
- taeric 4y ago
  Not necessarily. In particular, this could have slower growth, but still higher cost on normal workloads.
- chrchang523 4y ago
  Sometimes. In the case of matrix multiplication, there is a pretty large backlog of "galactic algorithms" going down to ~O(n^2.373) that haven't yet led to real-world improvements. Strassen's ~O(n^2.807) algorithm is only considered over the basic O(n^3) strategy for n>1000.
  - HarHarVeryFunny 4y ago
    Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.
    - chrchang523 4y ago
      My understanding is that the Winograd minimal filtering algorithms used in cuDNN are different from the O(n^2.37) Coppersmith-Winograd-descended matrix multiplication algorithms. But I acknowledge that these can be considered cousins, produced by the same line of research.
      - HarHarVeryFunny 4y ago
        I'm pretty sure there's no difference. It does seem to be pretty hard to turn the theoretical win into a practical one - the GPU kernel needs to be coded extremely efficiently to match the underlying hardware. AFAIK it's only a win for 3x3 - maybe for one other size too. Originally Winograd wasn't supported by cuDNN on NVidia's Tensor Cores (matmul-specific hardware on more recentish GPUs), vs CUDA cores, but a Google search seems to indicate it can be done - not sure if that's in cuDNN though.
- fulafel 4y ago
  It's interesting how both SIMD and big-o have had so different reasons for being of limited but still significant relevance. SIMD, and vector processors like it was called in the 70s, delivered practical speedups in simple benchmarks right away but most applications dont't take advantage because of SW engineering reasons. Whereas big-O improvement ignores important components of performance per unit of time (memory access and constant factors) and is purely theoretical in an essential sense.
throwawaymaths 4y ago
> the number of operations This is a very good proxy for actual real world speed. It's pretty much "as good as it gets" for most straight computational tasks, though sometimes memory movement is your real bottleneck.
- sdenton4 4y ago
  This is questionable... The 'best' algorithms for matrix multiplication are galactic algorithms that provide no actual benefit. Raw operation counts are a good proxy for speed, but the big-O complexity that people actually chase hasn't been especially helpful for this problem in the last twenty+ years. https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
  - throwawaymaths 4y ago
    Probably the most common matrix multiplication is (nx9) x (9xm) (9 = 3x3 cells from a convnet) . If you can optimize the shit out of those you might be in business for something interesting. Though to be honest the real slow step in machine learning is training and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one. For non-ml/non-GF purposes, you might also worry about numerical stability of these matrix multiplications, which is not addressed in this paper.
    - a1369209993 4y ago
      > and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one. Well, there are several, but the obvious ones tend to require strange or unrealistic assumptions about the hardware. The most obvious such assumption, IMO, being that the hardware is arranged in 3D space in a manner roughly analogous to a human brain, which tends to be at odds with the common practice of mostly-planar photolithography, and with the preference to be able to change the network topology experimentally without building new hardware.
- 4y ago
dekhn 4y ago
Science proceeds at the rate by which linearly larger matrices can be decomposed in less than exponential time.
- matheusd 4y ago
  This is excellent! You should make a T-Shirt with this quote on it!

by atty 4y ago

psychphysic 4y ago

Surely theoretical improvement begets real world, especially in the context of highly specialised hardware. It was with theoretical performance improvement that motivated the creation of SIMD and led to real world speed ups.

taeric 4y ago
Not necessarily. In particular, this could have slower growth, but still higher cost on normal workloads.
chrchang523 4y ago
Sometimes. In the case of matrix multiplication, there is a pretty large backlog of "galactic algorithms" going down to ~O(n^2.373) that haven't yet led to real-world improvements. Strassen's ~O(n^2.807) algorithm is only considered over the basic O(n^3) strategy for n>1000.
- HarHarVeryFunny 4y ago
  Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.
  - chrchang523 4y ago
    My understanding is that the Winograd minimal filtering algorithms used in cuDNN are different from the O(n^2.37) Coppersmith-Winograd-descended matrix multiplication algorithms. But I acknowledge that these can be considered cousins, produced by the same line of research.
    - HarHarVeryFunny 4y ago
      I'm pretty sure there's no difference. It does seem to be pretty hard to turn the theoretical win into a practical one - the GPU kernel needs to be coded extremely efficiently to match the underlying hardware. AFAIK it's only a win for 3x3 - maybe for one other size too. Originally Winograd wasn't supported by cuDNN on NVidia's Tensor Cores (matmul-specific hardware on more recentish GPUs), vs CUDA cores, but a Google search seems to indicate it can be done - not sure if that's in cuDNN though.
fulafel 4y ago
It's interesting how both SIMD and big-o have had so different reasons for being of limited but still significant relevance. SIMD, and vector processors like it was called in the 70s, delivered practical speedups in simple benchmarks right away but most applications dont't take advantage because of SW engineering reasons. Whereas big-O improvement ignores important components of performance per unit of time (memory access and constant factors) and is purely theoretical in an essential sense.

throwawaymaths 4y ago

> the number of operations This is a very good proxy for actual real world speed. It's pretty much "as good as it gets" for most straight computational tasks, though sometimes memory movement is your real bottleneck.

sdenton4 4y ago
This is questionable... The 'best' algorithms for matrix multiplication are galactic algorithms that provide no actual benefit. Raw operation counts are a good proxy for speed, but the big-O complexity that people actually chase hasn't been especially helpful for this problem in the last twenty+ years. https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
- throwawaymaths 4y ago
  Probably the most common matrix multiplication is (nx9) x (9xm) (9 = 3x3 cells from a convnet) . If you can optimize the shit out of those you might be in business for something interesting. Though to be honest the real slow step in machine learning is training and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one. For non-ml/non-GF purposes, you might also worry about numerical stability of these matrix multiplications, which is not addressed in this paper.
  - a1369209993 4y ago
    > and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one. Well, there are several, but the obvious ones tend to require strange or unrealistic assumptions about the hardware. The most obvious such assumption, IMO, being that the hardware is arranged in 3D space in a manner roughly analogous to a human brain, which tends to be at odds with the common practice of mostly-planar photolithography, and with the preference to be able to change the network topology experimentally without building new hardware.
4y ago

dekhn 4y ago

Science proceeds at the rate by which linearly larger matrices can be decomposed in less than exponential time.

matheusd 4y ago
This is excellent! You should make a T-Shirt with this quote on it!