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

41–50 of 328 posts

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

#41

Post by ajuc »

hexomancer wrote: post #13

> The confidence intervals are represented as latency ± (lower, upper), in which latency corresponds to the fifth percentile of latency measurements across 100 different machines. Lower and upper refer to the bounds of the 95% confidence interval for this percentile. Does anybody know why they chose fifth percentile? I though we should always choose the fastest time when measuring performance.

Usually you discard extreme values to reduce noise, and in fact they wrote that's why they did it:

> We then take the fifth percentile as our final measurement, because we assume that most noise sources are one-sided (for example, cache misses, pre-emptions and so on). During training we process the measurements across ten machines for computational efficiency.

> I though we should always choose the fastest time when measuring performance.

Depends. For games you usually do sth similar to what they did - exclude small percentage of worst results to reduce influence of noise and then optimize the worst scenario to make the game run consistent and smooth.

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

#42

Post by Filligree »

the_other wrote: post #39
Filligree wrote: post #26

Earlier quoted context omitted.

Intuition is the only thing we've figured out how to automate. Reason turns out to be higher hanging fruit.

Like humans’ “slow” and “fast” thinking, then?

There's likely a connection. Either way, I like to describe AIs like ChatGPT / diffusion models, etc. as operating 100% on intuition. It gives people a better intuition of their weaknesses...

For GPT you can kind of prompt it to do chain-of-thought reasoning, but it doesn't work very well; not if you compare it to what humans do.

Once again it seems like what we thought was hard, is easy; what we thought was easy and computer-like turns out to be hard.

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

#43

Post by ralfn »

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.

If the thing you have to sort is within a known domain you can definitely beat o(n log(n)). Just expect crazy memory usage.

And that's only not the case in theory. But nobody owns a real Turing machine with infinite tape and truly infinite numbers. It doesn't exist in reality.

You can always divide time by multiplying space with the same factor.

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

#44

Post by fwlr »

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 quite distinct like quicksort and mergesort are not that different - quicksort just does the "divide" step of divide-and-conquer in a smarter way.

In the end, no matter what divide-and-conquer sorting algorithm you pick, you will be doing lots of "small sorts". And it is those small sorts that DeepMind has optimized here.

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

#45

Post by blackbear_ »

finitestateuni wrote: post #5

The most interesting part of this paper to me is that they let the agent guess how efficient it’s own solutions were and only had the model experimentally verify it’s guesses in 0.002% of cases. This allowed the model to search much faster than another program that didn’t guess and had to run every program.

This is actually quite common to optimize stuff in several disciplines. You essentially fit a surrogate model (keyword if you want to look up more) to whatever you want to optimize, then use the model to guide the procedure, making sure that the model is correct every one in a while.

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

#46

Post by GreedClarifies »

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 attempt to replicate the “publish everything to support my brand” strategy of Deepmind.

I know Google is not a normal company in that Larry and Sergey have complete control of the company, but sooner or later they have to realize that Deepmind needs to be spun off, and further that Demis is entirely the wrong person to run Google’s AI. He doesn’t care a whit about Google, it is only a vessel to fund his research.

Products. A company is about products and customers not research papers. Academia or non-profits are about papers.

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

#48

Post by thomasahle »

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.

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

#49

Post by thomasahle »

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…

I'm surprised they only report results up to sort5. It seems at that level, you could just iterate through all possible programs. AI generated code seems more interested once you get to 10+ values, where classical methods break down.

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

#50

Post by jeffbee »

greenflag wrote: post #6

Does anyone have high level guidance on when (deep) RL is worth pursuing for optimization (e.g. optimizing algorithm design) rather than other approaches (e.g genetic)?

Start with a planet-scale computer that makes the marginal cost of RL be nearly zero, and at the same time spend a lot of money on hashing and sorting so the micro-optimization pays off.
Post reply on HN