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

171–180 of 328 posts

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

#171

Post by ryao »

blazespin wrote: post #115
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.…

Yeah, this type of grifting is very proforma for Researchers. I used to stress about it, but realize it just sort of goes with the territory. It's also worth noting that the paper is blindingly obvious and everyone started doing this a long time ago but didn't want to tip their cards. And that's the real contribution here - Google is tipping their cards. We now have a rough baseline to compare our results against.

It is likely meant to help secure further research funds.

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

#172

Post by schaefer »

vosper wrote: post #121
TaupeRanger wrote: post #114

Earlier quoted context omitted.

This is DeepMind's modus operandi. Every press release is just utterly hyperbolic nonsense that doesn't withstand the slightest scrutiny. AlphaGo, AlphaFold, AlphaDev... they've done literally nothing to improve the human condition, and may have actually made things worse. Go players have DECREASED their Elo after playing AlphaGo (or just quit the game altogether). I would be embarrassed to be associated with DeepMin…

> 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 Lee Sedol's retirement here: [1]

To active go players at the time, Alpha Go and Alpha Zero really were as shocking as the debut of Chat GTP was recently.

[1]: https://news.ycombinator.com/item?id=21649495

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

#173

Post by as4296 »

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

Lol I was about to say that would be incredibly crazy if they found a new sorting algorithm. My time complexity in USACO bout to go crazy.

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

#174

Post by saiojd »

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 approach can be applied to many other routines).

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

#175

Post by smeagull »

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…

A thing that is also not novel. People have done search for optimisations for at least the past decade.

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

#176

Post by dataflow »

as4296 wrote: post #173
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.…

Lol I was about to say that would be incredibly crazy if they found a new sorting algorithm. My time complexity in USACO bout to go crazy.

I get your sentiment but note that discovering a new algorithm doesn't have to imply a better time complexity. Bubble Sort and Insertion Sort have the same time complexity but are different algorithms.

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

#177

Post by orlp »

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 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 noted, superoptimizers are also already a thing: https://en.wikipedia.org/wiki/Superoptimization

There's also automatic searching being done on faster sorting networks that actually recently produced better than state of the art sorting networks: https://github.com/bertdobbelaere/SorterHunter

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

#178

Post by touisteur »

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…

I somehow agree that I'd be far more impressed by something that would find optimal or even just better sorting (or selection) networks for sizes higher than 17 (last time I looked at SOTA).

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

#179

Post by orlp »

touisteur wrote: post #178
orlp wrote: post #177

Earlier quoted context omitted.

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…

I somehow agree that I'd be far more impressed by something that would find optimal or even just better sorting (or selection) networks for sizes higher than 17 (last time I looked at SOTA).

Please check my edit right as you commented :)

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

#180

Post by dekhn »

xdavidliu wrote: post #157
dekhn wrote: post #80

Earlier quoted context omitted.

I had a long discussion with Rob Pike once that ended with me saying "you know, I don't think people actually use Strassen on supercomputers" (we were discussing how somebody had managed to show an N*2.37 algorithm or something like that and "it was a new world's record").

nit: ^, not *. ** for Python, but never *

Unfortunately Hacker News editor converts double-asterisk to single which is what caused the problem.

I never use ^ for "to the power of" due to its use in C for bitwise OR.

Post reply on HN