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

81–90 of 328 posts

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

#81

Post by ealexhudson »

xwdv wrote: post #77
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?

This is the killer app for me with AI. A way to get a non-copyrighted code for any program you already have binary code for.

That sounds obviously transformative and on any non-trivial scale I can't see why copyright would be avoided.

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

#82

Post by yunohn »

ralfn wrote: post #43
caturopath wrote: post #20

Earlier quoted context omitted.

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.

Parent said: > not going to find a general sorting algorithm

You said: > you have to sort is within a known domain you can definitely beat

Not sure why you framed your response this way?

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

#83

Post by bee_rider »

jacquesm wrote: post #55
thomasahle wrote: post #48

Earlier quoted context omitted.

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.

Ship the optimization framework in with the application, sample from the user data, and optimize for that? It isn’t overfitting if you overfit on the data you care about, right?

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

#85

Post by reaperman »

ealexhudson wrote: post #81
xwdv wrote: post #77

Earlier quoted context omitted.

This is the killer app for me with AI. A way to get a non-copyrighted code for any program you already have binary code for.

That sounds obviously transformative and on any non-trivial scale I can't see why copyright would be avoided.

I think you mean "non-transformative", although in this context I can see there's a bit of an ambiguity in how people would use the word "transform" to mean one thing w.r.t copyright and the "opposite" for code (really, orthogonal, but boolean evaluation would yield the opposite true/false).

In copyright, "transformative" refers to modifying or adapting a copyrighted work in a way that creates a new and original expression; resulting in a new work with a different purpose or meaning.

In terms of code, you'd "just be transforming" the assembly code to a systems language of your choice.

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

#86

Post by scns »

bee_rider wrote: post #83
jacquesm wrote: post #55

Earlier quoted context omitted.

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.

Ship the optimization framework in with the application, sample from the user data, and optimize for that? It isn’t overfitting if you overfit on the data you care about, right?

Sounds like the JVMs recompilation of hor paths to me.

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

#87

Post by jacquesm »

bee_rider wrote: post #83
jacquesm wrote: post #55

Earlier quoted context omitted.

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.

Ship the optimization framework in with the application, sample from the user data, and optimize for that? It isn’t overfitting if you overfit on the data you care about, right?

Data tends to change over time, and once a hash function is in use you can't really replace it easily without a lot of overhead, possibly quite a bit more overhead than what you saved in the first place. There are some examples of this in the sorting arena too, such as 'Timsort', personally I haven't found any that gave a substantial boost, but probably there are some cases where they do. Unless sorting or hashing (and lookup) are the main bottleneck for an application I would spend my time on other aspects of it.

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

#88

Post by reaperman »

utopcell wrote: post #72
xdavidliu wrote: post #63

Earlier quoted context omitted.

any sort that only uses comparisons is provably not better than n log n. Hence whatever Thorup is, it doesn't work for arbitrary input, and must assume something further, something like "all elements under 1000 or something"

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

This seems like a very valid point for iopq's clarifying point in the context of what still might exist to be discovered in the set of theoretically possible new algorithms, though doesn't change that dheera set the bar much, much higher than most people would agree with.

Thank you.

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

#89

Post by gumby »

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…

Your description makes the approach sound like applying ca 1980s simulated annealing, also a form of gradient descent. Am I missing something?

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

#90

Post by make3 »

cabalamat wrote: post #70
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…

> proves the point that optimal programs are very inhuman Maybe there should be an AI that produces optimally-readable/understandable programs? That's what I would want if I was adding the output to a codebase.

that's what LLMs can with rl from human (or ai) readability feedback & instruction tuning + prompting. we will 100% see this if gpt-4 doesn't already do this.
Post reply on HN