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

181–190 of 328 posts

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

#181

Post by touisteur »

orlp wrote: post #179
touisteur wrote: post #178

Earlier quoted context omitted.

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 :)

Oh very, very cool thanks a bunch.

Edit: compiling the hunter code Right Away and hopefully in some weeks I'll have better networks. Selection networks are even harder to find optimizers for, hopefully one can hack this new thing to get some.

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

#182

Post by saiojd »

smeagull wrote: post #175
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…

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

Sure, but the whole point is to reduce this kind of search to RL, which is a very general framework. Their paper shows that such a generic approach can solve a very specific problem, and solve it well. But, their paper is about improving RL, not about improving sorting.

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

#184

Post by saiojd »

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…

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 the actual domain. After AlphaGo exceeded expectations, the question becomes: "What else can RL do, and can it do anything actually useful?", and this paper seems to suggest that it can optimize code pretty well! I'm really not sure they are self-aggrandizing in terms of impact. The impact of an approach like this could potentially be very large (although I'm not saying that it actually is, I don't know enough).

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

#185

Post by optimalsolver »

VikingCoder wrote: post #67

Dumb question - Where are the machine learning de-compilers? Given an executable program, give me human-readable code that generates the executable exactly. With machine learning guessed function, type, variable names...? I get that it's a very hard problem. But... Does it just not work? Or have people not done it yet? Or have I missed it?

https://arxiv.org/abs/2010.00770

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

#186

Post by bloppe »

saiojd wrote: post #184
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…

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 calling it a new sorting algorithm.

But ya, discovering a new compiler optimization automatically is kinda cool.

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

#187

Post by utopcell »

xdavidliu wrote: post #158
utopcell wrote: post #72

Earlier quoted context omitted.

I think the parent's argument is that, since they only evaluated their algorithms on sorting arrays of 32-bit or 64-bit integers, it is fair game to compare against integer sorting algorithms for which we have better complexities than O(nlgn).

but the number of elements in the array is also a 32 or 64 bit integer, so you still cannot do better than O(n log n) even with fancy radix sort or whatever

not with radix sort, but you can do better when your elements are integers, even if there there are a lot of them, i.e. even when n ~ 2^32.

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

#189

Post by chpatrick »

TaupeRanger wrote: post #114
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.…

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…

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

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

#190

Post by recursive »

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…

70% better than O(N log N) is still O(N log N).
Post reply on HN