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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#41

Post by YorkshireSeason » Wed, Oct 05, 2022, 4:56 PM UTC

dekhn wrote: post #39

brutusborn wrote: post #35

Earlier quoted context omitted.

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

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.

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.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#42

Post by elcomet » Wed, Oct 05, 2022, 4:56 PM UTC

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 ?

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#43

Post by WhitneyLand » Wed, Oct 05, 2022, 4:57 PM UTC

In general to speed up matrix operations how much is some sort of result caching applied?

For example if you profile calculations done when training a model, is there any significant repetition happening that would allow some kind of benefit from table lookups of certain solutions?

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#44

Post by optimalsolver » Wed, Oct 05, 2022, 5:02 PM UTC

Now, were these algorithms discovered, or invented?

I.e., have they always been there, just sitting in Platonic space waiting for a conscious mind to stumble across them, or have they just now popped into existence?

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#45

Post by ColinWright » Wed, Oct 05, 2022, 5:03 PM UTC

Quoting:

> ... AlphaTensor finds an algorithm for multiplying 4×4 matrices using 47 multiplications in Z_2 , thereby outperforming Strassen’s two-level algorithm, which involves 7^2 = 49 multiplications. By applying this algorithm recursively, one obtains a practical matrix multiplication algorithm in Z_2 with complexity O(N^2.778).

> Moreover, AlphaTensor discovers efficient algorithms for multiplying matrices in standard arithmetic; for example, AlphaTensor finds a rank-76 decomposition of T_{4,5,5}, improving over the previous state-of-the-art complexity of 80 multiplications.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#46

Post by ColinWright » Wed, Oct 05, 2022, 5:04 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…

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#47

Post by throwawaymaths » Wed, Oct 05, 2022, 5:05 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…

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#48

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

YorkshireSeason wrote: post #41

dekhn wrote: post #39

Earlier quoted context omitted.

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.

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#49

Post by aaaaaaaaaaab » Wed, Oct 05, 2022, 5:06 PM UTC

dgacmu wrote: post #28

boole1854 wrote: post #27

Earlier quoted context omitted.

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

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.

Modular multiplication over GF(2)… also known as AND?

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#50

Post by ColinWright » Wed, Oct 05, 2022, 5:08 PM UTC

pxx wrote: post #30

boole1854 wrote: post #27

Earlier quoted context omitted.

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

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