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

111–120 of 328 posts

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

#111

Post by CyberDildonics »

graycat wrote: post #101
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"

The Gleason bound is n log(n) and says that no sorting algorithm based on comparing pairs of keys can be faster. Heap sort meets the Gleason bound so is the fastest possible in this context. Actually the usual versions of quick sort are slower. If the keys are not too long, radix sort is O(n) and faster. All this has been well known for decades. I explained a little more in another post in this thread.

I think you are getting your information mixed up. Here is a comparison that shows quicksort running in 1/10th the time as heapsort.

https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...

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

#112

Post by sidibe »

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…

Both of these contribute a lot to Google's infra by giving it new challenges. It's not a one-way street, Google wouldn't know what to build towards in their data center/hardware pipeline without these really ambitious projects with huge requirements.

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

#113

Post by tga_d »

eklitzke wrote: post #107
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.

I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function, but outside of cryptographic applications that is rarely the requirement. And (huge caveat, this isn't my domain expertise) I'm not sure what security properties are really "proven" about existing cryptog…

>If you really need a collision resistant hash you need to use a cryptographic hash function, but outside of cryptographic applications that is rarely the requirement.

There are reasons to use (strongly) collision resistant hashes outside of cryptographic settings. E.g., the default Rust hash function, used in hash maps and sets, has strong collision resistance, because otherwise you could open up applications to DoS attacks (the attacker uses lots of inserts with collisions to kill performance of accesses and further inserts at those buckets).[0]

>I'm not sure what security properties are really "proven" about existing cryptographic hash functions, AFAIK existing cryptographic hash functions are considered secure because we don't know how to break them, not because of some fundamental mathematical property about them.

There are provably secure hash functions[1] (typically using the same sort of primitives as public key crypto), but they're generally only used when certain properties need to be composed, and are often less secure than the non-provable ones in practice anyway. This is pretty similar to the state of symmetric vs. asymmetric cryptography in general: primitives like RSA, DH, etc. have much stronger proofs than AES, but algorithms built using AES for security are generally viewed as a lot less likely to be broken any time soon than algorithms built using typical asymmetric primitives for security, even ignoring things like quantum advantage.

[0] https://doc.rust-lang.org/std/collections/struct.HashMap.htm...

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

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

#114

Post by TaupeRanger »

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

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

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

#115

Post by blazespin »

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

Yeah, this type of grifting is very proforma for Researchers. I used to stress about it, but realize it just sort of goes with the territory.

It's also worth noting that the paper is blindingly obvious and everyone started doing this a long time ago but didn't want to tip their cards.

And that's the real contribution here - Google is tipping their cards. We now have a rough baseline to compare our results against.

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

#116

Post by blazespin »

TaupeRanger wrote: post #114
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.…

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…

It's a bit surprising how poorly DeepMind has lived up to their hype. But they're an OK lab, maybe a bit overly vain.

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

#117

Post by [deleted] »

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?

[deleted]

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

#119

Post by TaupeRanger »

blazespin wrote: post #116
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…

It's a bit surprising how poorly DeepMind has lived up to their hype. But they're an OK lab, maybe a bit overly vain.

It's probably very fun to be at DeepMind, I just don't think I'd want to be a part of the cringey hype machine.

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

#120

Post by blazespin »

TaupeRanger wrote: post #119
blazespin wrote: post #116

Earlier quoted context omitted.

It's a bit surprising how poorly DeepMind has lived up to their hype. But they're an OK lab, maybe a bit overly vain.

It's probably very fun to be at DeepMind, I just don't think I'd want to be a part of the cringey hype machine.

I bet it really sucks, tbh. They did all this over promising and now the only way they can deliver is by grifting like this. That sounds really stressful to me.
Post reply on HN