Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Discovering faster matrix multiplication algorithms with reinforcement learning

nature.com

Post reply on HN
Print view View original

91–100 of 116 posts

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#91

Post by a1369209993 »

throwawaymaths wrote: post #62
sdenton4 wrote: post #58

Earlier quoted context omitted.

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

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…

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#92

Post by est31 »

Nihmie wrote: post #77
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,…

To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1). Talking about scaling for a problem that has no scaling factor is a bit odd.

Yeah the paper uses O notation for complexity, but never when N is constant. For constant N and M, the paper uses the number of scalar multiplication operations performed as complexity measure. According to Figure 3, their algorithm has decreased the best known value from 49 to 47 for 4x4 matrices, and from 98 to 96 for 5x5 matrices (as well as some further state of the art improvements).

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#93

Post by klyrs »

tlb wrote: post #85
throwawaymaths wrote: post #64

Earlier quoted context omitted.

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

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…

You missed the part where the "4x4 matrix multiplication" refers to multiplication of NxN matrices logically partitioned into sixteen blocks of size (N/4)x(N/4), done recursively.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#95

Post by puffoflogic »

323 wrote: post #80
puffoflogic wrote: post #70

Why the heck is a math paper in Nature? I'd put Nature somewhere just below vixra in terms of math credibility.

If you could find a way to train cats to solve integrals, wouldn't that be a Nature paper and not a math one?

Yes, but if those cats discovered a faster way to solve integrals than you initially taught them, their findings would have higher credibility if published in an actual mathematics journal.

Otherwise, you end up with things like the "rediscovery" [0] of the trapezoid rule. That wasn't actually published in Nature, but with the way Nature has gone downhill even in its own sphere, it could probably happen today. There's no reason to believe that someone publishing in a bio/chem journal is remotely capable of making math/CS judgements like "faster matrix multiplication"; nor that the referees (does Nature even bother with those any more? O.o) will recognize any issues.

[0] https://academia.stackexchange.com/questions/9602/rediscover... https://news.ycombinator.com/item?id=26384357 etc.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#96

Post by johndfsgdgdfg »

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…

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

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#97

Post by throwawaymaths »

Nihmie wrote: post #77
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,…

To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1). Talking about scaling for a problem that has no scaling factor is a bit odd.

To be pedantic, paper is very clear that O is calculated after decomposing arbitrarily large matrices to 4x4s.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#98

Post by julienchastang »

evmar wrote: post #22
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.

English is terrible for sure, but this comment is pretty funny to compare it to the language that spells /kɛs kə sɛ/ as "qu'est-ce que c'est".

Or quatre-vingt-dix-huit -> four-twenty-eighteen, for the number 98.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#99

Post by didibus »

bugzz wrote: post #76
didibus wrote: post #74

Can someone knowledgeable tell me if it discovered an algorithm we can understand and re-implement ourself, like is the pseudo-code for it known? Or is it kind of stuck in the infered function of the ML model?

yes, they implemented the resulting algorithms and have charts showing real world performance on GPUs and TPUs

That's really cool!

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#100

Post by nestorD »

KKKKkkkk1 wrote: post #69

Reinforcement learning is usually introduced as a technique to train an agent in simulation that would then be let loose in a real environment. Interesting that they choose to treat it is a search strategy.

To be fair, their work is based on alpha-zero which is itself deeplearning on top of monte-carlo tree search, a search strategy. Having played with those algorithms, I suspect that one could obtain similar results with a solid Monte-Carlo tree search implementation (a lot of them use ucb which is really suboptimal)
Post reply on HN