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

141–150 of 328 posts

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

#141

Post by choppaface »

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

A decade ago Google had people with breadth and context who could have adjusted the framing of the result of this work (and maybe even re-targeted it yo something useful). Today however Google is a mix of hyper-narrow expert ICs and leaders who lack domain expertise. Paper in Nature? Sure let’s take it!

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

#142

Post by CaptainNegative »

graycat wrote: post #94

"Faster sorting"? Heap sort achieves the Gleason bound and, thus, is the fastest possible sort by comparing pairs of keys. For keys not too long, radix sort can be faster. These facts have been very well known for decades. There might be more to do in sorting with some different records, keys, computer architecture, concerns about caches and locality of reference , but otherwise, thankfully, sorting is a well solved…

Heap sort's worst- and average-case running time are both provably within a constant factor of optimality (both in running time and number of comparisons), but it's either likely or straight up provably not actually optimal in any of the four categories.

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

#143

Post by gdy »

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…

"may have actually made things worse. Go players..."

Go players are using AI to get better at Go.

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

#144

Post by TaupeRanger »

gdy wrote: post #143
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…

"may have actually made things worse. Go players..." Go players are using AI to get better at Go.

That claim is often made, and never substantiated.

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

#145

Post by dundarious »

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

Yes, I believe what they're doing already exists in the literature as "supercompilation", though good to see its application under any name.

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

#146

Post by 29athrowaway »

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…

Around the time of the AlphaGo challenge and afterwards...

1) you could see increased activity in go clubs and online go servers

2) the analysis of the games published by Deepmind has resulted in interesting "discoveries" (or rediscoveries) and changes to what is considered joseki.

3) many people started analyzing their kifus using AI, to find fluctuations in estimated win rate across moves.

So I disagree entirely

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

#147

Post by nahstra »

TaupeRanger wrote: post #144
gdy wrote: post #143

Earlier quoted context omitted.

"may have actually made things worse. Go players..." Go players are using AI to get better at Go.

That claim is often made, and never substantiated.

https://www.amazon.com/How-Play-Way-Explained-illustrative/d...

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

#148

Post by 29athrowaway »

dfan wrote: post #127
vosper wrote: post #121

Earlier quoted context omitted.

> Go players have DECREASED their ELO after playing AlphaGo (or just quit the game altogether) Can you explain this for someone unfamiliar with the game?

I am familiar with the game and I cannot explain it. Go is not typically rated with the Elo system, and the quality of top-level human play has increased since 2016.

That is correct but in game servers, ranks (e.g.: 1 kyu, 1 dan) are computed via Elo-like means.

https://forums.online-go.com/t/how-does-the-rating-system-wo...

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

#149

Post by 29athrowaway »

jimsimmons wrote: post #139
blazespin wrote: post #135

Earlier quoted context omitted.

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

Why not. It’s not like they have deadlines

They still have to publish something in major journals and have presence in major conferences.

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

#150

Post by Someone »

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…

> I'm not sure what security properties are really "proven" about existing cryptographic hash functions

AFAIK, we don’t even know whether trapdoor functions exist.

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

“As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions”

Also note that the ‘examples’ section starts with:

“In the following two examples, we always assume it is difficult to factorize a large composite number (see Integer factorization).”

Post reply on HN