Hacker News Reader

Comment by telotortium | Hacker News Reader

Abstract: "In response to a recent Nature article which announced an algorithm for multiplying 5×5-matrices over ℤ2 with only 96 multiplications, two fewer than the previous record, we present an algorithm that does the job with only 95 multiplications."

The "recent Nature article" is, of course, Deepmind's reinforcement learning-guided search for better matrix multiplication algorithms: https://news.ycombinator.com/item?id=33096580.

They improved upon Deepmind's algorithms by applying a method of their own, which is not described in this paper, but which they will publish in an upcoming paper: "Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. in preparation."

View on HN

Deep-learning-hype-hater-quick-take: Based on that title (and a glance at the paper), my guess is that rather than brute force and megawatts of GPU power, they found a first-principles solution.

Their result is "We found a slightly better method after someone told us where to look."

It's very common in mathematics for simpler proofs and extensions of results to follow an initial ground-breaking paper. People looking at this preprint as a refutation of the ML techniques have it exactly backwards.

This seems to be a typical case of the following scenario:

You have been working on a topic for a while. Then, one day, you learn that someone has managed to get a paper on the topic into Nature/Science/whatever. And not because their results are that impressive but because they are from a famous institute and are using fashionable methods. Of course, the first thing you do is checking if you can improve the results with the tools you already have. If you can, you post the results online and start working on a paper.

That happens all the time.

On that Google Nature paper, I'm not sure if the 5x5 matrix improvement is the more significant result, or that they figured out a way to optimize directly to SIMD/AVX instructions, resulting in faster execution even if not necessarily fewer operations

The result is not interesting for ordinary numbers, where the classical ("slower") method is faster. When each element of the 5x5 matrix is itself a matrix, it could be important.

So AVX ops for the method are not interesting.

No... using divide and conquer matrix multiplication with this gives n^2.83. Strassens algorithm is n^2.79. This is good fir 5 by 5 matrices... which are not terribly interesting.

It uses many more additions. When the elements are themselves matrices, additions are a lot cheaper than multiplications, so that is OK. But with ordinary numbers, additions cost about the same as multiplications, so trading off a few multiplications for a lot more additions loses.

I thought it was when you were multiplying two matrices where the elements are 5x5 rather than a 5x5 matrix containing embedded matrices of arbitrary length, no?

The technique works for either

But usefully for only one.

A machine or any algorithm, by definition cannot be first principals. This term was coined with Richard Feynman, and ever since then, in all instances, it has been mis-used.

"No official code found."

There are known faster methods, that as yet are unproven, that will save giga-watts of power.

Hope they get a nature article as well.

So it's a teaser paper?

I wouldn't exactly call it a teaser. The formulas they published stand on their own, and putting them out there in the wake of all the press of the AlphaTensor paper, is just a good idea.

Of course, these formulas are not super interesting on their own, and so the forthcoming paper on HOW they developed these formulas is in some sense the "real" paper.

I think the point is to publish before anyone else does. If they wait until they're full paper is ready, they might be scooped.

I'm not sure how to feel about this. If the purpose of science research is to build the understanding we have, teaser articles seem more like a way to put a name on a creation without actually contributing to our understanding of something.

I guess this is an artifact of how cutthroat academia is and how vital it is to have credit for being first.

> If the purpose of science research is to build the understanding we have.

It's not. It never was. It's always been "to build the understanding that I or this small group I am part of has, that gives us an edge for a while until we share it with the world because it looks like someone else might otherwise pretend to have discovered it".

The idea of a noble science, diligently working towards the betterment of mankind, has always been a romantic fantasy at best.

"The Double Helix" by James Watson is still a surprisingly accessible read that's very relevant here.

I think I'm alright with it in this case. Here, they've given the result and a full proof that a keen undergrad could follow. The future reference is about the method they used to find it. People can hit the ground running with their accelerated matrix multiplication today, should they want to. But if they want to apply that method to find 17x17 multiplication formulae, they'll have to wait.

> I guess this is an artifact of how cutthroat academia is and how vital it is to have credit for being first.

In fairness, academia has improved much in this regards since the days of Newton. That man was such an arse... even the Wikipedia article about his feud with Leibniz glosses over... everything.

Basically, not only was he a donkey about things, he used all sorts of underhanded tactics to win and reveled in devastating his rival's good standing.

But it is a long principle of academia to avoid being scooped by putting out priority-proving work. Consider US patents; or, further back, I read here yesterday that Galileo published anagrams of his results and Kepler took great delight in reverse-engineering them, accidentally finding other true facts other than Galileo's intended discovery.

So long as it doesn't slow or otherwise impede the dissemination of the full paper I don't mind personally.

If they were able to complete it in a week then it is a big deal… especially about wording if that they would be scooped.

Three days! The Deep Mind paper came out on the 5th of October; the first version of this on the 8th.

Are we calling dibs on research now? Is this a kindergarten?

Now?!

Sorry, but someone called dibs on the idea of “priority” long, long ago. The oldest dispute on this list is in the 1500s: https://en.wikipedia.org/wiki/List_of_scientific_priority_di...

Science/academia has been for as long as I can remember.

Read some of the history around natural philosophy some few hundred years ago. It’s a real hoot, how petty and ego-driven some of these people were. Leibniz’s attempts at taking credit for Newton’s hard work come to mind. (Tongue somewhat planted in cheek here.)

Research has always been about getting credit for first discovering something, to some extent.

But now that people know the solution exists, other people can find a justification for it.

Reply on news.ycombinator.com