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

51–60 of 328 posts

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

#51

Post by bgirard »

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…

There's lot of accepted sorting algorithms [1]. I'm sure we can come up with novel new algorithms, even if they're not optimal. Like Wikipedia mentions, they all fall within some small number of higher level categories (eg. Partitioning, Merging, Selection, Insertion). I'm still not convinced that the optimizations presented in the article amount to the discovery of NEW sorting algorithms but merely optimizations of existing ones.

[1] https://en.wikipedia.org/wiki/Sorting_algorithm

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

#52

Post by EGreg »

Almost all ML is basically searching through a (latent) space of possible answers and indexing the results. So it outperform most known methods. Like when AlphaGo using MCTS beat Rybka, etc.

I would be interested to know if ML can be used to reverse hashes, such as to more quickly solve the numbers that satisfy the Bitcoin Hash challenge. Maybe it can even get P and NP closer together!

Are there theoretical results on SHA-256 or something that preclude finding an ML algorithm that, with a billion parameters, can speed up the search for a Bitcoin Hash input?

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

#53

Post by iopq »

caturopath wrote: post #20
dheera wrote: post #15

Earlier quoted context omitted.

> up to 70% faster So O(0.3(N log N))? That's still O(N log N)

They're not going to find a general sorting algorithm faster than O(n log n), but that doesn't mean all O(n log n) sorts are created equal.

That's not true because Thorup's algorithm is O(n log log n)

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

#54

Post by benlivengood »

GreedClarifies wrote: post #46

Deepmind shouldn’t be part of a for profit entity. There I said it. They are clearly focused on moving technology forward and helping humanity. That’s great. However, pulling down 1M+ salaries (for L6+ developers) and using hundreds of millions or billions in borg resources while adding nothing to the bottom line is not in the interest of Google. Not to mention the negative effects on productivity as other Googlers a…

I think Google's biggest net positives in the world at this point are Waymo and DeepMind. Way better than spending money on new chat apps.

Google's history has been having a very lucrative bottom line that allows for very beneficial research with absolutely no hardships on anyone. Supremely better than lining shareholder pockets; shareholders can't think enough quarters ahead for long-term human benefit. Salaries are just the way to attract and retain quality folks.

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

#55

Post by jacquesm »

thomasahle wrote: post #48
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'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.

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

#56

Post by ozr »

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 think this is still super interesting. It's something humans are unable to do/there's few humans that can. I very much like the pattern of writing basic logic myself and then using a coding model to optimize it. It's effectively what we do with compilers already, this just makes it better.

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

#57

Post by cypherpunks01 »

This was educational because I learned about Sorting Networks.

I didn't hear of them in CS undergrad algorithms, perhaps because they can be thought of as a special case or optimization, rather than fundamental and generic variable-length sort algos.

It's a simple concept, and forms the basis of all the sort optimizations described here.

https://en.wikipedia.org/wiki/Sorting_network

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

#58

Post by ComputerGuru »

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…

Interesting that it took AI to pull this off. I think mutagen testing would have discovered the first (by virtue of checking which code isn’t necessary globally) though likely not the second (which needs a new branch, unless that branch was already there?).

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

#59

Post by ozr »

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…

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

I think the sci-fi-but-possibly-real hope is that for sorting (among other things), we may have the perspective that there isn't any new algorithmic approach available, but an AI finds one for us.

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

#60

Post by 13of40 »

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.

Post reply on HN