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

Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

nature.com

Post reply on HN
Print view View original

201–210 of 328 posts

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#201

Post by fastball »

schaefer wrote: post #172
vosper wrote: post #121

Earlier quoted context omitted.

> Go players have DECREASED their ELO after playing AlphaGo (or just quit the game altogether) Can you explain this for someone unfamiliar with the game?

Lee Sedol retired in 2019 following his 2016 defeat by Alpha Go in a 5 round match. At the start of the match most people were confident an AI could never defeat a top human player at Go. By the end of the match, watching (arguable) world champ Sedol suffer lost game after lost game the story had changed dramatically. Sedol fans were championing his single win against the unstoppable AI. We (hacker news) discussed Le…

This is correct history, but not the point TaupeRanger was trying to make (I believe).

I think their assertion is that the release of AlphaGo has actually made human Go players worse at the game, contrasted with chess where most agree that the introduction of Superhuman chess engines has elevated the (human) state of play.

But I don't think there is actually much evidence for that. I'm sure the introduction of AlphaGo did take the wind out of some players sails, who thought of themselves as superior to our best computers, but for everyone else it seems to have elevated the overall level of play just the same as the chess engines have done.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#202

Post by fastball »

TaupeRanger wrote: post #144
gdy wrote: post #143

Earlier quoted context omitted.

"may have actually made things worse. Go players..." Go players are using AI to get better at Go.

That claim is often made, and never substantiated.

Assuming a total lack of evidence on either side, I think your assertion is the counter-intuitive one and therefore has the greater burden of proof. Why would Go be any different than Chess?

A rising tide floats all ships – if the best in the world becomes better, others can look at the best and learn from it. What difference does it make if the best player is an AI or a human? The better moves and strategies are still better moves and strategies.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#203

Post by x86x87 »

saiojd wrote: post #174
orlp wrote: post #91

> AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements. They found a sequence of assembly that saves.…

I feel like your take is overly cynical. The fact that humans can do the same thing by hand is not really the point. The contribution lies in the fact that their method derived this improvement *automatically*, which is where the impact lies. No one cares all that much if a human can make a sorting routine 2% faster, but if a program can do it, it suddenly becomes interesting (since it suggests that a similar approac…

i don't read it as cynical. It's fair game to call bullshit on bullshit. If an approach exists and is known the "insert your favorite AI here" does not discover anything.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#204

Post by matteoraso »

jacquesm wrote: post #55
thomasahle wrote: post #48

Earlier quoted context omitted.

I'm disappointed a the hashing is just based on training on microbenchmarks and SMHasher, rather than designing a fast _provably_ universal hash. Suites like SMHasher are never complete. They are just trying to catch the most common weaknesses. If you train on the test cases you'll only get an algorithm that passes the tests, but people can always find a set of values on which you will do badly.

Indeed, and this has been the case for quite a while now. You can always improve on some general algorithm by taking advantage of knowledge of the data but that never generalizes and usually leads to either worse performance on other data and/or new pathological cases that result in results that are unusable. It's an instance of overfitting.

>Indeed, and this has been the case for quite a while now. You can always improve on some general algorithm by taking advantage of knowledge of the data but that never generalizes and usually leads to either worse performance on other data and/or new pathological cases that result in results that are unusable.

Deepmind did the exact same thing with AlphaTensor. While they do some geniunely incredible things, there's always a massive caveat that the media ignores. Still, I think it's great that they figured out a way to search a massive space where most of the solutions are wrong, and with only 16 TPUs running for 2 days max. Hopefully this can be repurposed into a more useful program, like one that finds proofs for theorems.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#205

Post by bawolff »

girvo wrote: post #198
chpatrick wrote: post #189

Earlier quoted context omitted.

Massive improvements in protein folding do nothing to improve the human condition? What?

I think it's fair to say that it (where "it" is defined as "DeepMind's contribution to the protein folding problem") hasn't yet given us massive improvements to the human condition. It might, and in fact I think it probably will. But it hasn't yet.

When the biggest criticism of deep mind is it hasn't literally saved the world yet, i think that is pretty telling about how impressive it really is.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#206

Post by riwsky »

dools wrote: post #199
fwlr wrote: post #34

Some very cool improvements found in already highly optimized algorithms. They found that in a sorting network handling 3 inputs, the AI found a way to save an instruction by reducing a "min(A, B, C)" operation to just "min(A, B)" by taking advantage of the fact that previous operations guaranteed that B = min(A, C) in this case) that can be taken advantage of to remove an instruction as well. The compiler may not be…

“ The compiler may not be able to compete with hand-written assembly, but it seems an AI can hand-write assembly code that's even better in some cases.” This made me think “imagine if AI was the compiler”, that is to say you went from C or whatever to assembly via AI directly so it was “hand writing” the equivalent assembly for your instructions instead of using generic compilation. We might find everything runs much…

Everything except the compiler, that is

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#207

Post by runsWphotons »

orlp wrote: post #177
saiojd wrote: post #174

Earlier quoted context omitted.

I feel like your take is overly cynical. The fact that humans can do the same thing by hand is not really the point. The contribution lies in the fact that their method derived this improvement *automatically*, which is where the impact lies. No one cares all that much if a human can make a sorting routine 2% faster, but if a program can do it, it suddenly becomes interesting (since it suggests that a similar approac…

I am not cynical about the research itself, I am critical of claims such as "new sorting algorithm uncovered", "up to 70% faster", or "first change in a decade". The research is good. The achieved results are massively inflated. What they achieved: automatically generated good code. What they claim: automatically generated code that is revolutionary and an improvement on the state of the art. And as another commenter…

how automatically generated was the code that wrote the code

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#208

Post by tlringer »

orlp wrote: post #91

> AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements. They found a sequence of assembly that saves.…

Every DeepMind press release is like this.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#210

Post by Dylan16807 »

bloppe wrote: post #186
saiojd wrote: post #184

Earlier quoted context omitted.

While I agree that the claims are hyperbolic, I think you are approaching this paper from the point of view of someone who knows a lot about sorting. Because of this, its normal that the claims of these guys who probably don't know much about it are grating for you. But, at its core, this is really a RL paper. The objective is to see how far a generic approach can work while understanding as little as possible about…

Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can't believe they discovered something better than O(N log N)" because that's usually what people mean when they say "better sorting algorithm". What they discovered here is effectively a new compiler optimization. They should present it as such instead of callin…

> because that's usually what people mean when they say "better sorting algorithm"

Is it really? I've heard of a few "better sorting algorithms" and it's never meant that in my experience.

Post reply on HN