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

261–270 of 328 posts

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

#261

Post by cubefox »

Dylan16807 wrote: post #210
bloppe wrote: post #186

Earlier quoted context omitted.

Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can't believe they discovered something better than O(N log N)" because that's usually what people mean when they say "better sorting algorithm". What they discovered here is effectively a new compiler optimization. They should present it as such instead of callin…

> because that's usually what people mean when they say "better sorting algorithm" Is it really? I've heard of a few "better sorting algorithms" and it's never meant that in my experience.

When people say "sorting algorithm" they mean something like bubble sort or merge sort.

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

#262

Post by Nimitz14 »

malux85 wrote: post #166
chaxor wrote: post #162

Earlier quoted context omitted.

Deepmind has done quite an enormous amount actually, but it's been in academia not in the commercial product sphere. Just because something is not on a little web page available to average Joe's does not mean there isn't value in it. For example, Deepmind's work towards estimating quantum properties of materials via density functional theory may not be the best toy for your grandma to play around with, but it certain…

I run atomictessellator.com and have been working on many different implementations of density functional theory for the last 10 years, as well as working closely with professors at Stanford university and Oxford university of using advanced, non-static geometry data structure for density functional theory for multiple years, this is a subject I know a LOT about, so I’m glad you brought it up. Deep minds work on Dens…

Love that you know enough to call him out haha

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

#263

Post by Dylan16807 »

thomasahle wrote: post #256
Dylan16807 wrote: post #219

Earlier quoted context omitted.

> Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not. Eh, that's how I usually see collision resistance described. The probability is based on generating fresh inputs with any method you want/the most effective attack method available. But I wouldn't say the hash you linked is nondeterministic ju…

> You can seed MD5, SHA-2, and BLAKE2 by tossing bytes in as a prefix. It'll prevent the same attacks and you can give it the same analysis. I'm curious if you can link to such an analysis. These functions are notoriously much harder to analyze than simple functions like "h(x) = ax+b mod p" which is all you need for the probabilistic guarantee. But even if you could analyze this, you would just end up with a universa…

By definition, if they're secure then they should meet the requirements, right?

> But even if you could analyze this, you would just end up with a universal hash function that's way slower than you need, because you didn't pick the right tool for the job.

I understand that, I'm just trying to figure out how a universal hash is easier to construct. But as you've gone through the descriptions here I think I understand how the collision resistance necessary is much much simpler, and there seems to be an assumption that the output of the hash will not be available to the attacker.

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

#264

Post by qumeric »

bloppe wrote: post #186
saiojd wrote: post #184

Earlier quoted context omitted.

While I agree that the claims are hyperbolic, I think you are approaching this paper from the point of view of someone who knows a lot about sorting. Because of this, its normal that the claims of these guys who probably don't know much about it are grating for you. But, at its core, this is really a RL paper. The objective is to see how far a generic approach can work while understanding as little as possible about…

Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can't believe they discovered something better than O(N log N)" because that's usually what people mean when they say "better sorting algorithm". What they discovered here is effectively a new compiler optimization. They should present it as such instead of callin…

Tbh people who majored in CS are supposed to know that it was proven long ago that better than O(N log N) sorting (in general case) is impossible.

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

#267

Post by qumeric »

mtlmtlmtlmtl wrote: post #222
chaxor wrote: post #160

Earlier quoted context omitted.

This is unbelievably wrong. Deepmind has probably the best academic group in RL. The difference between Deepmind and OpenAI is that Deepmind favors academic endeavours and novelty much more, while completely ignoring any commercialization or products, while OpenAI is the stark opposite in that they almost entirely focus on products first, and typically their academic endeavours are just slight modifications of other…

That's the thing with Deepmind though. They almost never actually end up advancing things because A) they don't release weights and B) they don't usually develop their ideas into useful tools themselves, forcing others to redo all their work. So yeah, it's essentially a PoC PR stunt factory. Just look at AlphaZero. They make a huge deal about a suspiciously set up match against Stockfish. Supposedly revolutionising c…

> Now, in AI, usually getting a proof of concept is the easy part. Developing that into an idea that actually works in real world situations is usually the hardest part.

I disagree. Of course there is a lot of engineering involved and it's also very important but it's much easier to rebuild things based on published research than develop novel ideas.

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

#268

Post by bglazer »

TaupeRanger wrote: post #240
chpatrick wrote: post #189

Earlier quoted context omitted.

Massive improvements in protein folding do nothing to improve the human condition? What?

Name one improvement. Just one thing that has ACTUALLY helped real life humans and been a net positive since AlphaFold's inception 5 years ago.

We're talking about biomedical science here. Things move slowly because the domain is exceptionally complex and human lives are in the balance.

AlphaFold catapulted protein structure prediction forward, and it's hard to overstate how important understanding protein structure is in modern drug development

As an example of how this will be used to help actual people, here's a paper that uses AlphaFold to identify the parts of cancer-associated proteins that interact with each other.

https://onlinelibrary.wiley.com/doi/full/10.1002/pro.4479

The obvious next step is to develop drugs that disrupt these interactions and thereby disrupt cancer. But, it's going to take years, maybe decades before any drug resulting from this research is in actual patients.

There are dozens of other papers like this.

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

#269

Post by jart »

schaefer wrote: post #172
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?

Lee Sedol retired in 2019 following his 2016 defeat by Alpha Go in a 5 round match. At the start of the match most people were confident an AI could never defeat a top human player at Go. By the end of the match, watching (arguable) world champ Sedol suffer lost game after lost game the story had changed dramatically. Sedol fans were championing his single win against the unstoppable AI. We (hacker news) discussed Le…

The story with Lee Sedol gets even sadder when you look at his rankings chart: https://www.goratings.org/en/players/5.html He immediately lost his heart for the game even though he officially kept playing another three years.

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

#270

Post by rep_movsd »

saiojd wrote: post #184
orlp wrote: post #177

Earlier quoted context omitted.

I am not cynical about the research itself, I am critical of claims such as "new sorting algorithm uncovered", "up to 70% faster", or "first change in a decade". The research is good. The achieved results are massively inflated. What they achieved: automatically generated good code. What they claim: automatically generated code that is revolutionary and an improvement on the state of the art. And as another commenter…

While I agree that the claims are hyperbolic, I think you are approaching this paper from the point of view of someone who knows a lot about sorting. Because of this, its normal that the claims of these guys who probably don't know much about it are grating for you. But, at its core, this is really a RL paper. The objective is to see how far a generic approach can work while understanding as little as possible about…

Anyone who does any basic algorithmic CS stuff would have been exposed to sorting algorithms, their variations, sorting networks and so on.

There are already superoptimizers who use genetic algorithms to find the most optimal code sequence for small easily verifiable tasks. That is also a form of reinforcement learning in a way

Post reply on HN