6 ms·

The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our k

by svnt 4y ago

The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical complexity as Strassen-square, it outperforms it in practice, as it is optimized for the considered hardware. Interestingly, AlphaTensor finds algorithms with a larger number of additions compared with Strassen-square (or equivalently, denser decompositions), but the discovered algorithms generate individual operations that can be efficiently fused by the specific XLA33 grouping procedure and thus are more tailored towards the compiler stack we use. The algorithms found by AlphaTensor also provide gains on matrix sizes larger than what they were optimized for. Finally, Fig. 5c shows the importance of tailoring to particular hardware, as algorithms optimized for one hardware do not perform as well on other hardware. So they improved on Strassen’s 50-year-old algorithm by optimizing it for hardware that has only existed for a few years and de-optimizing it for human use? There is so much cool stuff here without claiming to do something you really didn’t.

dekhn 4y ago
That's the DeepMind modus operandi- and why they publish in Nature. It's in their best interest to claim as much covered ground as possible so they can keep working towards their end-goal. But most people who read Nature already know that results in that journal are overhyped. You just have to apply a specific prior/translator when you read their papers.
- noobermin 4y ago
  This really is a depressingly true sentiment. Nature is both the most important publication but so often, the big shots publish overhyped stuff there that doesn't deserve it but get away with it since they are bigshots. Underscore here for another piece of evidence of the dysfunction in science.
  - brutusborn 4y ago
    I don't doubt the sentiment is true, but hasn't this kind of science always been this way? By that I mean authors inflating the importance of their work; everyone wants to be seen as having the biggest breakthroughs. When I think of dysfunction in 'science' I usually think of unfalsifiable hypothesis, the repeatability crisis in Psychology, p-hacking in Medicine, misuse of statistical methods in Economics and other epistemic issues, but I don't think of exaggerations like this.
    - dekhn 4y ago
      Scientists have long been self-promoters who desire that their theories become the dominant ones and they use many techniques to achieve this. However, the trend towards maximizing the predicted outcomes of your research really took off during the human genomics project.
      - YorkshireSeason 4y ago
        I would imagine that it's the metrics universities and funding agencies apply in promotion decisions. For example, my (well-known) university decided to measure impact, and takes "Twitter engagement" as one proxy metric for impact -- against my explicit recommendations. I'll leave the consequences to everybody's imagination.
        dekhn 4y ago
        Yes. In fact many scientists post to twitter but don't look at the replies (Emily Bender is an example) or even block you if you disagree with them. That's not engagement and I wonder what the dean would do about a promotion where the scientist just sort of blathered on twitter and had lots of followers, but wasn't actually providing any real scientific value (again, Emily Bender is an example).
        YorkshireSeason 4y ago
        Deans typically lack detailed technical knowledge to evaluate candidates (not to mention time), they just go with the flow, and want to run the department smoothly. I think the real mechanism is this: those who make the decision (those with the most power, i.e. those who bring in the most funding and can threaten to leave if they don't get their way) already know whom they want and they cherry-pick data, eg "impact" figures, to bolster their case. That enables the dean then to justify the decision in public with those cherry-picked figures ... (the dean can hardly say we are hiring X because otherwise top funding getter Y will leave) I think Twitter is less important in STEM subjects than in social sciences or humanities, as STEM has more clearcut results.
chabons 4y ago
Maybe I'm mis-reading the paper, but my interpretation was that the algorithm discovered using a reward which scales with HW performance matches the theoretical complexity of Strassen, but is more performant on the HW. They also identified algorithms which do fewer matrix multiplications than Strassen, improving the lower bound of matrix multiplies required (They highlight this in Fig 3). In that light, I thought their claim was fair. They've discovered (different) algorithms which are both theoretically and practically better than Strassen's.
- deleted 4y ago
  [deleted]
boole1854 4y ago
This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence: > Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. That is, note that the improvement cited in the latter part of the sentence is for the 4 x 4 matrix case. But then your next quote is not in reference to 4 x 4 matrices. That is, for larger matrix sizes, the best algorithm AlphaTensor discovered had the same theoretical complexity as Strassen-square, but better performance. EDIT: my next comments are confused and best ignored. See reply from pxx below. For the 4 x 4 matrix case, the theoretical complexity of AlphaTensor's algorithm was O(N^2.778) compared with the Strassen algorithm's complexity of O(N^2.8074), which is an improvement.
- dgacmu 4y ago
  In Z_2 - modular matrix multiplication, not conventional matrix multiplication. And in this case, modular over what I assume is GF(2), i.e., single bits.
  - aaaaaaaaaaab 4y ago
    Modular multiplication over GF(2)… also known as AND?
- pxx 4y ago
  what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that you can use this primitive on the block matrices recursively to possibly improve the asymptotic complexity. the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware. [0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.
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.
ColinWright 4y ago
How can I reconcile your comment here with the comment in https://news.ycombinator.com/item?id=33098192 https://news.ycombinator.com/item?id=33098192 ??
throwawaymaths 4y ago
No, they count multiplications, 47 vs 49 in the 4x4 case. This assumes that multiplications are the heavy lift relative to additions, memory moves, etc. this is not a bad assumption, and is hardware independent, although there are some proposed 'exotic' hardware solutions where addition and multiplication are equally difficult (via lookup table, limited to about 8-bit x 8-bit) or where addition is harder than multiplication (log space number systems) but I don't think these have been deployed
- lifthrasiir 4y ago
  That assumption didn't age very well. In many if not most modern architectures multiplication still does take more cycles than addition but can have a higher throughput if scheduled well, and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.
  - throwawaymaths 4y ago
    > but can have a higher throughput if scheduled well Unlikely to be true for matrix multiplications, which have well-defined data dependencies. > and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition. Yes, this supports the assumption that multiplication is the heavy lift.
    - tlb 4y ago
      With sufficiently parallel hardware, you can do an entire mat4 * mat4 multiplication in 3 cycles. First do all 64 multiplications in parallel, then do 32 adds, then 16 adds to get the final answer. For operations in GF(2) where they claim a result, a multiply is just an AND gate and an add is an XOR gate. So the fully parallel hardware version is 64 AND gates and 48 XOR gates, with a total gate delay of 3. This is a trivial amount of hardware and could easily be an instruction in some alternate universe where it was useful.
      - klyrs 4y ago
letitgo12345 4y ago
I think they find a N^2.778 complexity algorithm (obtained by applying their 4x4 discovered algorithm recursively) so this is not correct.
Ar-Curunir 4y ago
You’re wrong. They discovered an algorithm with fewer multiplications for 4x4 matrices. They also discovered better algorithms for other dimensions.
johndfsgdgdfg 4y ago
What do you expect from an ad company? Not the truth.
- oittaa 4y ago
  Hey, you haven't chosen the betting site yet. Which one do you prefer? https://news.ycombinator.com/item?id=33102761 https://news.ycombinator.com/item?id=33102761

by svnt 4y ago

dekhn 4y ago

That's the DeepMind modus operandi- and why they publish in Nature. It's in their best interest to claim as much covered ground as possible so they can keep working towards their end-goal. But most people who read Nature already know that results in that journal are overhyped. You just have to apply a specific prior/translator when you read their papers.

noobermin 4y ago
This really is a depressingly true sentiment. Nature is both the most important publication but so often, the big shots publish overhyped stuff there that doesn't deserve it but get away with it since they are bigshots. Underscore here for another piece of evidence of the dysfunction in science.
- brutusborn 4y ago
  I don't doubt the sentiment is true, but hasn't this kind of science always been this way? By that I mean authors inflating the importance of their work; everyone wants to be seen as having the biggest breakthroughs. When I think of dysfunction in 'science' I usually think of unfalsifiable hypothesis, the repeatability crisis in Psychology, p-hacking in Medicine, misuse of statistical methods in Economics and other epistemic issues, but I don't think of exaggerations like this.
  - dekhn 4y ago
    Scientists have long been self-promoters who desire that their theories become the dominant ones and they use many techniques to achieve this. However, the trend towards maximizing the predicted outcomes of your research really took off during the human genomics project.
    - YorkshireSeason 4y ago
      I would imagine that it's the metrics universities and funding agencies apply in promotion decisions. For example, my (well-known) university decided to measure impact, and takes "Twitter engagement" as one proxy metric for impact -- against my explicit recommendations. I'll leave the consequences to everybody's imagination.
      - dekhn 4y ago
        Yes. In fact many scientists post to twitter but don't look at the replies (Emily Bender is an example) or even block you if you disagree with them. That's not engagement and I wonder what the dean would do about a promotion where the scientist just sort of blathered on twitter and had lots of followers, but wasn't actually providing any real scientific value (again, Emily Bender is an example).
        YorkshireSeason 4y ago
        Deans typically lack detailed technical knowledge to evaluate candidates (not to mention time), they just go with the flow, and want to run the department smoothly. I think the real mechanism is this: those who make the decision (those with the most power, i.e. those who bring in the most funding and can threaten to leave if they don't get their way) already know whom they want and they cherry-pick data, eg "impact" figures, to bolster their case. That enables the dean then to justify the decision in public with those cherry-picked figures ... (the dean can hardly say we are hiring X because otherwise top funding getter Y will leave) I think Twitter is less important in STEM subjects than in social sciences or humanities, as STEM has more clearcut results.

chabons 4y ago

Maybe I'm mis-reading the paper, but my interpretation was that the algorithm discovered using a reward which scales with HW performance matches the theoretical complexity of Strassen, but is more performant on the HW. They also identified algorithms which do fewer matrix multiplications than Strassen, improving the lower bound of matrix multiplies required (They highlight this in Fig 3). In that light, I thought their claim was fair. They've discovered (different) algorithms which are both theoretically and practically better than Strassen's.

deleted 4y ago
[deleted]

boole1854 4y ago

This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence: > Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. That is, note that the improvement cited in the latter part of the sentence is for the 4 x 4 matrix case. But then your next quote is not in reference to 4 x 4 matrices. That is, for larger matrix sizes, the best algorithm AlphaTensor discovered had the same theoretical complexity as Strassen-square, but better performance. EDIT: my next comments are confused and best ignored. See reply from pxx below. For the 4 x 4 matrix case, the theoretical complexity of AlphaTensor's algorithm was O(N^2.778) compared with the Strassen algorithm's complexity of O(N^2.8074), which is an improvement.

dgacmu 4y ago
In Z_2 - modular matrix multiplication, not conventional matrix multiplication. And in this case, modular over what I assume is GF(2), i.e., single bits.
- aaaaaaaaaaab 4y ago
  Modular multiplication over GF(2)… also known as AND?
pxx 4y ago
what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that you can use this primitive on the block matrices recursively to possibly improve the asymptotic complexity. the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware. [0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.

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.

ColinWright 4y ago

How can I reconcile your comment here with the comment in https://news.ycombinator.com/item?id=33098192 https://news.ycombinator.com/item?id=33098192 ??

throwawaymaths 4y ago

No, they count multiplications, 47 vs 49 in the 4x4 case. This assumes that multiplications are the heavy lift relative to additions, memory moves, etc. this is not a bad assumption, and is hardware independent, although there are some proposed 'exotic' hardware solutions where addition and multiplication are equally difficult (via lookup table, limited to about 8-bit x 8-bit) or where addition is harder than multiplication (log space number systems) but I don't think these have been deployed

lifthrasiir 4y ago
That assumption didn't age very well. In many if not most modern architectures multiplication still does take more cycles than addition but can have a higher throughput if scheduled well, and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.
- throwawaymaths 4y ago
  > but can have a higher throughput if scheduled well Unlikely to be true for matrix multiplications, which have well-defined data dependencies. > and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition. Yes, this supports the assumption that multiplication is the heavy lift.
  - tlb 4y ago
    With sufficiently parallel hardware, you can do an entire mat4 * mat4 multiplication in 3 cycles. First do all 64 multiplications in parallel, then do 32 adds, then 16 adds to get the final answer. For operations in GF(2) where they claim a result, a multiply is just an AND gate and an add is an XOR gate. So the fully parallel hardware version is 64 AND gates and 48 XOR gates, with a total gate delay of 3. This is a trivial amount of hardware and could easily be an instruction in some alternate universe where it was useful.
    - klyrs 4y ago

letitgo12345 4y ago

I think they find a N^2.778 complexity algorithm (obtained by applying their 4x4 discovered algorithm recursively) so this is not correct.

Ar-Curunir 4y ago

You’re wrong. They discovered an algorithm with fewer multiplications for 4x4 matrices. They also discovered better algorithms for other dimensions.

johndfsgdgdfg 4y ago

What do you expect from an ad company? Not the truth.

oittaa 4y ago
Hey, you haven't chosen the betting site yet. Which one do you prefer? https://news.ycombinator.com/item?id=33102761 https://news.ycombinator.com/item?id=33102761