Discovering faster matrix multiplication algorithms with reinforcement learning • Hacker News Board

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#51

Post by throwawaymaths » Wed, Oct 05, 2022, 5:09 PM UTC

atty wrote: post #29

svnt wrote: post #15

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 comple…

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 wort…

> 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.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#52

Post by dekhn » Wed, Oct 05, 2022, 5:12 PM UTC

atty wrote: post #29

svnt wrote: post #15

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 comple…

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 wort…

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#53

Post by taeric » Wed, Oct 05, 2022, 5:12 PM UTC

psychphysic wrote: post #36

atty wrote: post #29

Earlier quoted context omitted.

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 wort…

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.

Not necessarily. In particular, this could have slower growth, but still higher cost on normal workloads.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#54

Post by YorkshireSeason » Wed, Oct 05, 2022, 5:15 PM UTC

dekhn wrote: post #48

YorkshireSeason wrote: post #41

Earlier quoted context omitted.

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.

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).

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.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#55

Post by ogogmad » Wed, Oct 05, 2022, 5:18 PM UTC

elcomet wrote: post #42

loufe wrote: post #4

This is completely besides the matter, but reading "provably" in the abstract is a frank reminder of how terrible English spelling/pronounciation is. I can't imagine I'm the only well-read native English speaker who read this as "prov-ably" on first take. I don't know about most languages, but you just don't get nonsense like this in French, at least.

I don't understand your point, provably means which can be proven, is there another meaning I'm missing ?

He's talking about the spelling not matching the pronunciation

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#56

Post by sdenton4 » Wed, Oct 05, 2022, 5:25 PM UTC

ColinWright wrote: post #50

pxx wrote: post #30

Earlier quoted context omitted.

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…

I thought that savings on the number of multiplications leads to savings in complexity. For example, multiplying 2x2 matrices using 7 multiplications instead of 8 gives an improvement in complexity. See my comment here: https://news.ycombinator.com/item?id=33098192 It's possible that my understanding is completely wrong, but your comment is at odds with my other reading, so it would be useful to get some clarificatio…

This is correct, as I understand it.

Most complexity measures are defined in terms of asymptotic behavior, so any specific finite algorithm has 'constant' complexity. This is an obviously unhelpful bit of pedantry in the theory side.

In fact, it's as you say; we can compute a 'raw' complexity for a finite operation (eg, raw count of arithmetic ops), and then use that operation as a primitive to create an algorithm with an asymptotic complexity which depends directly on the finite operation's 'raw' complexity.

(complexity theory, and specifically for matrix multiplication, is a great example of metrics becoming targets becoming bad incentives, a la Goodhart's Law. The so-called best algorithms are 'galactic' and therefore of no use to anyone. There's some fuzzy-headed hope that one day the people chasing the big-O exponent metric will come up with something practically useful, buuuuuut... you actually gotta work practical problem to solve the practical problem, and that requires different metrics. This seems to be what's motivating the work under discussion here.)

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#57

Post by [deleted] » Wed, Oct 05, 2022, 5:25 PM UTC

chabons wrote: post #26

svnt wrote: post #15

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 comple…

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 the…

[deleted]

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#58

Post by sdenton4 » Wed, Oct 05, 2022, 5:29 PM UTC

throwawaymaths wrote: post #51

atty wrote: post #29

Earlier quoted context omitted.

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 wort…

> 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.

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_algorith...

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#59

Post by letitgo12345 » Wed, Oct 05, 2022, 5:29 PM UTC

svnt wrote: post #15

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 comple…

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#60

Post by pxx » Wed, Oct 05, 2022, 5:32 PM UTC

ColinWright wrote: post #50

pxx wrote: post #30

Earlier quoted context omitted.

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…

I thought that savings on the number of multiplications leads to savings in complexity. For example, multiplying 2x2 matrices using 7 multiplications instead of 8 gives an improvement in complexity. See my comment here: https://news.ycombinator.com/item?id=33098192 It's possible that my understanding is completely wrong, but your comment is at odds with my other reading, so it would be useful to get some clarificatio…

sorry; whoops, I don't know why I said multiplications there. I somehow thought the "more additions" somehow meant "fewer multiplications," but no, it's just "more additions but faster performance on target." edited.

your other comment notes that for some shapes, even in standard arithmetic, they have found algorithms with fewer multiplications than best-known. but those don't seem to extend to an algorithm with better asymptotic complexity for multiplying general matrices. otherwise I'd assume they'd claim them :)