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

311–320 of 328 posts

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

#311

Post by elcomet »

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…

I hope people majoring in CS will not think that, as they learned that n log n is the theorically best complexity for a sort algorithm. They will rather think that they found an algorithm with better constants in front of n log n.

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

#312

Post by elcomet »

wsdookadr wrote: post #302
congoe wrote: post #221

Earlier quoted context omitted.

How could AlphaZero possibly play better chess than humans when it doesn’t even understand the history of chess theory? RL doesn’t stop at human levels

Even if AlphaZero does play better chess, there's absolutely zero it can do in terms of explaining why it played that way. AlphaZero is zero in terms of explainability. Humans have to explain to themselves and to others what they do, this is key in understanding what's happening, in communicating what's happening, in human decision-making, in deciding between what works and what doesn't and how well or how bad it wor…

It cannot explain because (1) it is not necessary to become good and (2) it wasn't explicitly trained to explain.

But it's reasonable to imagine a later model trained to explain things. The issue is that some positions might not be explainable, as they require branching too much and a lot of edge cases, so the explanation is not understandable by the human.

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

#313

Post by ks84 »

danlark wrote: post #37

You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sort... , https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It…

I haven’t read the paper, but it sounds like this is a sort of similar approach to genetic algorithms? Create lots of agents with random changes and pick the ones that produce the most promising results? Is my impression wrong?

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

#314

Post by wsdookadr »

lupire wrote: post #289
Maken wrote: post #235

Earlier quoted context omitted.

Because the entire history of chess theory is really a set of heuristics to optimize a tree search.

So is computer science.

You make it sound so simple. Why don't we let an AI try to come up with all of CS on its own? I doubt it would/could.

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

#315

Post by chpatrick »

TaupeRanger wrote: post #307
hugopenmir wrote: post #305

Earlier quoted context omitted.

Send them your resume or ideas about how to do it faster and better, it could help !

There is no way to do it faster or better with these techniques. It is a waste of money - that's the entire point. My advice would be: stop wasting time, money, and human brainpower. Go off and try entirely new approaches to AI that might actually work!

This is such a bizarre take. AlphaFold is faster and better - but it still takes years to develop anything in the life sciences.

It's like pointing to special relativity in 1905 and saying it'll never be useful for anything.

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

#316

Post by usmansk »

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

Can anyone refute the claim of orlp that it is unrolled insertion sort

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

#317

Post by wsdookadr »

elcomet wrote: post #312
wsdookadr wrote: post #302

Earlier quoted context omitted.

Even if AlphaZero does play better chess, there's absolutely zero it can do in terms of explaining why it played that way. AlphaZero is zero in terms of explainability. Humans have to explain to themselves and to others what they do, this is key in understanding what's happening, in communicating what's happening, in human decision-making, in deciding between what works and what doesn't and how well or how bad it wor…

It cannot explain because (1) it is not necessary to become good and (2) it wasn't explicitly trained to explain. But it's reasonable to imagine a later model trained to explain things. The issue is that some positions might not be explainable, as they require branching too much and a lot of edge cases, so the explanation is not understandable by the human.

It's unreasonable to give up on explanations and deem something "not understandable" when we've been doing this thing for 3000+ years called mathematics, where it's exactly explainability that we seek and the removal of doubt. The only other entities that we know of who can't communicate or explain what they're doing are animals.

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

#318

Post by Zacharias030 »

elcomet wrote: post #311
bloppe wrote: post #186

Earlier quoted context omitted.

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…

I hope people majoring in CS will not think that, as they learned that n log n is the theorically best complexity for a sort algorithm. They will rather think that they found an algorithm with better constants in front of n log n.

true that

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

#319

Post by Zacharias030 »

saiojd wrote: post #182
smeagull wrote: post #175

Earlier quoted context omitted.

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.

sometimes one has to wonder how RL can be both so generic and still be qualification to publich in nature again and again and again ;)

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

#320

Post by thraidh »

Can someone explain why the sort3 function produced by Alphadev is correct?

The instruction that was removed was: `P=min(A,C)`, which means that `P=A` at that point.

The next instructions:

    cmp S Q
    cmovg Q P
with `S=min(A,C)` and `Q=B` can be translated into

    if S>Q: P=Q
or

    if min(A,C)>B: P=B
which means: if B is the smallest, then `P=B`. Otherwise P stays as before, meaning `P=A` for Alphadev and `P=min(A,C)` for the original.

So, the end result for sorting A,B,C=3,2,1 would be 3,2,3 for Alphadev's code.

I can't believe, I'm the first one to notice, so I'm probably wrong, but I cannot see where.

Post reply on HN