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

271–280 of 328 posts

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

#271

Post by crocowhile »

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.

I am a neuroscientist, not affiliated with Deepmind. I can´t speak for the other AlphaThings,but AlphaFold dramatically changed the way the biomedicine field deals with protein structures, shortening the gap between hypothesis and experiments by months if not years. You have no idea of what you're talking about.

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

#272

Post by whatever1 »

cabalamat wrote: post #249
whatever1 wrote: post #108

Earlier quoted context omitted.

Optimal routing of delivery vehicles for UPS/Fedex etc is also non-compressible to the drivers, so the planners often intentionally generate suboptimal solutions. A suboptimal implemented solution is a better than an optimal not implemented one.

> Optimal routing of delivery vehicles for UPS/Fedex etc is also non-compressible to the drivers, so the planners often intentionally generate suboptimal solutions. Really? That's the first time I've heard that (and I've worked on vehicle routing). Normally, the driver would get the next address they have to visit and would use satnav to work out how to get there. They don't need to "comprehend" the overall route.

Packages might have delivery time windows attached to them, so the optimal solution calls for multiple visits in the same neighborhood by the same van. This is bs from a driver’s perspective.

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

#273

Post by ska »

chaxor wrote: post #164
ska wrote: post #99

Earlier quoted context omitted.

I wouldn't classify any of the output I've seen so far as "optimally readable/understandable". Some if it looks pretty ok, especially where it overlaps with well established approaches.

It can do well with optimization and readability *if you ask it specifically for those things*. Especially if you have a particular paradigm and algorithm in mind (you obviously already should anyway). This is why these systems are helpful in programming: they allow developers to think more about the design paradigms, and algorithmic solutions, rather than the fine grained code syntax and typing. My hope (not predict…

> It can do well with optimization and readability if you ask it specifically for those things

My experience so far (including -4) this isn't really true, even when focusing on those aspects. I'm cautiously optimistic this will get better.

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

#274

Post by usmansk »

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

The claim "faster sorting algorithm" is wrong. They have to show the time-complexity. They have to prove that their algorithm is faster than linear sorting algorithms. Otherwise, they have to accept that their claim is wrong.

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

#275

Post by TaupeRanger »

bglazer wrote: post #268
TaupeRanger wrote: post #240

Earlier quoted context omitted.

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

And yet, even after 5 years there's no sign of any real, meaningful drugs, even just Phase I trials. In 5 - 10 years (which will be 10 to 15 years after AlphaFold was released) I am willing to bet real money that there will be zero drugs discovered by AlphaFold that meet the following criteria:

1) The drug couldn't have been discovered without AlphaFold 2) It has been proven to reduce all cause mortality (the thing real patients actually care about) in a randomized controlled clinical trial BETTER than the prior standard of care (or significantly more cheaply, or with significantly reduced side effects)

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

#276

Post by TaupeRanger »

crocowhile wrote: post #271
TaupeRanger wrote: post #240

Earlier quoted context omitted.

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.

I am a neuroscientist, not affiliated with Deepmind. I can´t speak for the other AlphaThings,but AlphaFold dramatically changed the way the biomedicine field deals with protein structures, shortening the gap between hypothesis and experiments by months if not years. You have no idea of what you're talking about.

Name one real human being that has benefited from this "shortened gap", aside from the CVs and H-Index of the researchers themselves?

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

#278

Post by [deleted] »

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…

[deleted]

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

#279

Post by graycat »

CyberDildonics wrote: post #259
graycat wrote: post #195

Earlier quoted context omitted.

Come on, guys: Early in my career, I had a really good career going. I paid a lot of attention to writing fast code. Some of that career was in a Navy lab, and some of the people there wrote fast code by going down to the assembly language and checking each instruction, load, store, etc. At times that career bumped into some math -- 0-1 integer linear programming, even ordinary linear programming, optimization, e.g.,…

This wall of text is very bizarre. First, I don't know where you got "gleason bound" from, but if you search for it on google, your comment in this thread is the only thing that comes up. Second, your "alternative speed" measures are a hallucination. Sooo, broadly that's two quite different ways to look at how to write fast code. No there isn't. The one that takes 1/10th the time of the other one is faster. You going…

> First, I don't know where you got "gleason bound" from,

For the answer and posted in this thread, I wrote:

The Gleason bound? That's in one of the D. Knuth volumes The Art of Computer Programming.

> Second, your "alternative speed" measures are a hallucination.

No. Instead, I wrote in this thread:

A short answer is, if win in the big-O comparison, then, no matter how sloppy the coding, for all sufficiently large n, still will win no matter how measure speed. In short, that's the reason people took big-O very seriously.

If you want to argue against heap sort, then you need to argue that in counting comparisons the big-O expression for heap sort is wrong and loses out to some other sorting algorithm.

The Gleason bound assumes that each comparison costs the same. So you may want to argue that for n keys, as n grows the issues of caches, locality of reference, parallel processors, etc. mean that the cost of each comparison grows so that in the big-O competition heap sort can be beat.

I'll let someone else calculate the big-O expressions again considering locality of reference, etc.

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

#280

Post by schaefer »

jart wrote: post #269
schaefer wrote: post #172

Earlier quoted context omitted.

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.

I thought I knew the story. But I'd never seen this graph. Thank you for breaking my heart all over again, jart.
Post reply on HN