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

231–240 of 328 posts

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

#231

Post by pxeger1 »

fwlr wrote: post #44
bgirard wrote: post #22

The title implies it found an entirely new algorithmic approach to sorting (like quick sort) which would have been a fantastic discovery. But it feels a lot like micro-optimizing the control flow and codegen.

I'm not sure there is a new algorithmic approach to sorting like you're thinking of. From a high level you can divide sorting algorithms into roughly two camps, "those that use divide-and-conquer", and "those that do not". The divide-and-conquer (split into smaller sub-lists, sort the sub-lists, and merge them while preserving sort order) algorithms are better. From this perspective, algorithms that we think of as qu…

Indeed, it's easy to prove that any sorting algorithm that works by comparing elements (unlike e.g. radix sort) requires Ω(n log n) time in the worst case.

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

#232

Post by bamboozled »

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…

When one has a big fuck off hammer, everything becomes a nail. Seems to apply to ML too.

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

#233

Post by bamboozled »

chpatrick wrote: post #189
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…

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

To be fair I have read that while impressive, still has little practical application?

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

#234

Post by bamboozled »

gusennan wrote: post #220
malux85 wrote: post #126

Earlier quoted context omitted.

I thought the same thing - it smacks of desperation at the moment, any tiny win is exaggerated . It’s not hard to see why, with the emergence (ha) of OpenAI, Midjourney and all of this generative modelling, what has DeepMind done? I imagine the execs at Google are asking them some very probing questions on their mediocre performance over the last 5 years.

They solved an open challenge problem, Protein Structure Prediction, with AlphaFold, which has been nothing short of revolutionary in the structural biology and biochemistry fields. I do scientific research in these fields and the capabilities AlphaFold provides are used now everywhere.

Curious what this research has actually improved in a practical sense? I’m asking for a friend…

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

#235

Post by Maken »

congoe wrote: post #221
wsdookadr wrote: post #215

Earlier quoted context omitted.

What's surprising is that anyone would've expected an AI to come up with a brand-new algorithm with better complexity than pre-exsiting human-made solutions. How could it possibly come up with something better when it doesn't even understand how the original authors of qsort/mergesort/etc came up with their own.. Sure, it's great PR for the company, but.. the results just aren't there.

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

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

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

#236

Post by sundarurfriend »

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?

I don't understand WebAssembly much other than superficially, but if wasm is going to be a new, harder level obfuscation for websites, making them harder to customize locally, then I hope ML/AI can counteract that and preserve the Web as a user-customizable space.

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

#237

Post by tyingq »

13of40 wrote: post #60
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…

> something incomprehensible for humans This might be buggy whip talk, but I wonder if you could take the same system and apply it to smaller problems (e.g. computing an 8-bit hash) so the novel techniques could be identified and used by humans.

One of the examples from another comment[1] here was:

"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

Which isn't incomprehensible at all.

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

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

#238

Post by blitzar »

blazespin wrote: post #135
lurknot wrote: post #122

Earlier quoted context omitted.

ya bet it sucks making $500-800k/year comp getting access to the best hardware and google datasets

I've seen people who get promoted above their band, they are not happy campers.

Oh god, promoted as well, I for one am glad they are bearing the burden for me.

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

#240

Post by TaupeRanger »

chpatrick wrote: post #189
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…

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

Name one improvement. Just one thing that has ACTUALLY helped real life humans and been a net positive since AlphaFold's inception 5 years ago.
Post reply on HN