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

101–110 of 116 posts

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#101

Post by MichaelBurge »

optimalsolver wrote: post #44

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?

The dovetail over all possible programs solves every problem with at most a constant slowdown.

So if it was invented, it was invented 100 years ago along with every other algorithm since the inventor of the dovetail incorporated it by reference. And there are no more algorithms to invent.

And if it was discovered, you would want to compare the efficiency of your discovery process with the dovetail.

So I tend to say "discovered with X bits of optimization power", where 0 bits reduces to the dovetail over some enumeration process, infinity bits reduces to "invention"(i.e. you consider one(or zero) object from the stream, constructing it directly), and everything in-between grades the search process.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#103

Post by brutusborn »

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.

Any more info on the changes from the human genomics project?

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#104

Post by lawrenceyan »

> Leveraging this diversity, we adapted AlphaTensor to specifically find algorithms that are fast on a given hardware, such as Nvidia V100 GPU, and Google TPU v2. These algorithms multiply large matrices 10-20% faster than the commonly used algorithms on the same hardware, which showcases AlphaTensor’s flexibility in optimising arbitrary objectives.

10-20% performance improvement in matrix multiplications is pretty amazing[0]!

[0]: https://www.nature.com/articles/s41586-022-05172-4/figures/5

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#105

Post by TheRealNGenius »

WFHRenaissance wrote: post #87
optimalsolver wrote: post #44

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?

Discovered. I'd go as far to say that all "invention" is actually just discovery that we find useful.

No post body was provided.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#106

Post by oittaa »

johndfsgdgdfg wrote: post #96
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.

Hey, you haven't chosen the betting site yet. Which one do you prefer?

https://news.ycombinator.com/item?id=33102761

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#107

Post by mirekrusin »

f1shy wrote: post #9
mirekrusin wrote: post #5

Earlier quoted context omitted.

Unless it provides or simply works within formal verification?

Formal verification does not prove lack of bugs. In best case, can only catch one certain type of bugs. https://smartech.gatech.edu/handle/1853/62855

If you navigate within algebraic structures with well known properties (which are also verified for example), formal verification is all you need, you can be certain of being bug free.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#108

Post by wbhart »

The new 4x4 matrix multiplication over F_2 has practical applications as many matrix operations over F_2 can be reduced to matrix multiplication.

For anyone looking for the algorithm itself, it is actually given in in one of the extended data sections at the very end of the paper.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#109

Post by scotty79 »

haolez wrote: post #20
iKlsR wrote: post #11

Earlier quoted context omitted.

Whenever I see stuff about automated algorithms it reminds me of a movie, can't remember the name or plot exactly but they create a being or upload someones consciousness and the "ai" is solving all the problems the world faces until it reaches the last one, humans. It then begins to synthesize some airborne virus or nukes that would scour us from the earth. We basically created tech that would eventually optimize us…

Transendence is one of the few movies that present an almighty AI that's benevolent in nature.

You might watch "I am mother". Greater good was always an interesting concept.
Post reply on HN