News for hackers. Stuff that matters.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by orlp on Wednesday June 07, 2023 @02:25PM (#36231147)
> 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... one MOV. That's it. And it's not even novel, it's simply an unrolled insertion sort on three elements. That their patch for libc++ is 70% faster for small inputs is only due to the library not having an efficient implementation with a *branchless* sorting network beforehand. Those are not novel either, they already exist, made by humans.

> By open sourcing our new sorting algorithms in the main C++ library, millions of developers and companies around the world now use it on AI applications across industries from cloud computing and online shopping to supply chain management. This is the first change to this part of the sorting library in over a decade and the first time an algorithm designed through reinforcement learning has been added to this library. We see this as an important stepping stone for using AI to optimise the world’s code, one algorithm at a time.

I'm happy for the researchers that the reinforcement learning approach worked, and that it gave good code. But the paper and surrounding press release is self-aggrandizing in both its results and impact. That this is the first change to 'this part' of the sorting routine in a decade is also just completely cherry-picked. For example, I would say that my 2014 report and (ignored patch of) the fact that the libc++ sorting routine was QUADRATIC (https://bugs.llvm.org/show_bug.cgi?id=20837) finally being fixed late 2021 https://reviews.llvm.org/D113413 is quite the notable change. If anything it shows that there wasn't a particularly active development schedule on the libc++ sorting routine the past decade.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Wednesday June 07, 2023 @03:26PM (#36232145)
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 u... by blazespin on Wednesday June 07, 2023 @03:32PM (#36232241)
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 u... by TaupeRanger on Wednesday June 07, 2023 @03:36PM (#36232307)
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 u... by blazespin on Wednesday June 07, 2023 @03:43PM (#36232422)
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.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by lurknot on Wednesday June 07, 2023 @03:54PM (#36232578)
ya bet it sucks making $500-800k/year comp getting access to the best hardware and google datasets
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by blazespin on Wednesday June 07, 2023 @04:36PM (#36233173)
I've seen people who get promoted above their band, they are not happy campers.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by jimsimmons on Wednesday June 07, 2023 @04:47PM (#36233324)
Why not. It’s not like they have deadlines
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by 29athrowaway on Wednesday June 07, 2023 @05:21PM (#36233756)
They still have to publish something in major journals and have presence in major conferences.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by jprd on Wednesday June 07, 2023 @05:40PM (#36233988)
a.k.a. - they still care enough to have some semblance of shame. There's the rub.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by 29athrowaway on Wednesday June 07, 2023 @06:08PM (#36234311)
At least they've produced tangible value unlike black holes of money like the Human Brain project which has delivered close to nothing in multiple decades despite billions of dollars in investment.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by blitzar on Thursday June 08, 2023 @07:36AM (#36240171)
Oh god, promoted as well, I for one am glad they are bearing the burden for me.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by hugopenmir on Friday June 09, 2023 @03:31PM (#36262914)
I can’t believe this
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by vosper on Wednesday June 07, 2023 @03:45PM (#36232455)
> 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?

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by dfan on Wednesday June 07, 2023 @04:09PM (#36232805)
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.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by nahstra on Wednesday June 07, 2023 @04:50PM (#36233350)
I also play some, and yeah that's incorrect. Also, there was recently a bunch of hype about an adversarial strategy that could beat AIs w/o deep readout (i.e. only using the 'policy network' nonlinear ML stuff and not enough actual calculation). Here's a vid of an amateur doing it.

https://www.youtube.com/watch?v=H4DvCj4ySKM

EDIT:

Also, if you want to get into it, Micheal Redmond's Go TV on youtube has an amazing beginner playlist, watch some of that then maybe blacktoplay.com and if you likey play :)

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by 29athrowaway on Wednesday June 07, 2023 @05:19PM (#36233735)
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 u... by scotty79 on Wednesday June 07, 2023 @03:55PM (#36232586)
Maybe they just lost so their ELO went down? Or do loses against AI not count?
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by rcxdude on Wednesday June 07, 2023 @04:28PM (#36233094)
Either way, in ELO it depends on the ELO of your opponent, and so a loss against an AI with an accurate (very high) ELO is not going to lose you much unless you're one of the best players in the world (heck, in chess, Magnus Carlsen's ELO would still go down by literally nothing from losing against stockfish).
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by schaefer on Wednesday June 07, 2023 @06:58PM (#36234848)
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 Lee Sedol's retirement here: [1]

To active go players at the time, Alpha Go and Alpha Zero really were as shocking as the debut of Chat GTP was recently.

[1]: https://news.ycombinator.com/item?id=21649495

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by fastball on Wednesday June 07, 2023 @10:58PM (#36236626)
This is correct history, but not the point TaupeRanger was trying to make (I believe).

I think their assertion is that the release of AlphaGo has actually made human Go players worse at the game, contrasted with chess where most agree that the introduction of Superhuman chess engines has elevated the (human) state of play.

But I don't think there is actually much evidence for that. I'm sure the introduction of AlphaGo did take the wind out of some players sails, who thought of themselves as superior to our best computers, but for everyone else it seems to have elevated the overall level of play just the same as the chess engines have done.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:36AM (#36241665)
I don't think that AlphaGo has made players worse. My point is that there's no evidence that anything USEFUL or IMPORTANT has come from a system that has gotten so much hype (and cost ungodly amounts of money). If players aren't getting better (there's no evidence they are) or are quitting the game after playing, it's simply a net negative, along with DeepMind's other ventures.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by _hark on Thursday June 08, 2023 @10:31AM (#36242486)
Sorry, but this is just incorrect. Go players have gotten stronger over time overall [0][1], and AI discovered many new ideas that all top pros have incorporated into their game-play (idk how to give a source for this, it's just very well known in the Go community that the style of play changed drastically in response to AlphaGo, and absolutely everyone trains with AI these days).

[0]: "The sudden overall increase in agreement in 2016 also reinforces the belief that the introduction of powerful AI opponents has boosted the skills of professional players." https://ai.facebook.com/blog/open-sourcing-new-elf-opengo-bo...

[1]: https://www.goratings.org/en/

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @11:11AM (#36243167)
It's not incorrect. The fact that Go players have gotten stronger over 300 years of recorded data does not in any way show that AlphaGo has made players better. The fact that players are suddenly memorizing AI moves in 2016 and beyond also does not mean they're getting better. This system does not measure how good the players are. It measures how much they copy AI moves (which is rather convenient, since the article is written by AI researchers). The phrase you quoted is so hilariously worded that I initially thought it might be satire. Indeed it does "reinforce the belief" that AI has boosted the skills of players - apparently the researchers themselves are not immune to this "reinforcement of belief"!
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by krisoft on Thursday June 08, 2023 @10:41AM (#36242640)
> My point is that there's no evidence that anything USEFUL or IMPORTANT has come from a system that has gotten so much hype

Geez. We are talking about pebbles on a wooden plank. They are not even colourful!

Go is super cool game, but it is that. Just a game. We are not talking about curing cancer, or solving world hunger, or reversing climate change here. So by the very formulation a Go playing AI can be cool, or interesting, or promising. But could it really be useful/important with all-caps? It sounds like you have too high expectations here.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by hugopenmir on Friday June 09, 2023 @03:34PM (#36262963)
IT TAKES TIME to solve HUGE CHALLANGES.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by jart on Thursday June 08, 2023 @12:53PM (#36244978)
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 u... by schaefer on Thursday June 08, 2023 @05:01PM (#36248983)
I thought I knew the story. But I'd never seen this graph. Thank you for breaking my heart all over again, jart.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by malux85 on Wednesday June 07, 2023 @04:01PM (#36232702)
I thought the same thing - it smacks of desperation at the moment, any tiny win is exaggerated .

It’s not hard to see why, with the emergence (ha) of OpenAI, Midjourney and all of this generative modelling, what has DeepMind done? I imagine the execs at Google are asking them some very probing questions on their mediocre performance over the last 5 years.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by chaxor on Wednesday June 07, 2023 @06:11PM (#36234351)
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 certainly does move academia way further ahead of where it once was.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by dr_dshiv on Wednesday June 07, 2023 @06:39PM (#36234653)
How so? Legitimately interested.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by malux85 on Wednesday June 07, 2023 @06:30PM (#36234545)
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 Density functional theory was complete rubbish, and everyone in computational chemistry knows it. They simply modelled static geometry and overfit their data, we wanted this methodology to work, computing DFT is expensive, and we did multiple months of rigorous work and the reality of the situation is that a bunch of machine learning engineers with a glancing amount of chemistry knowledge, made approximations that were way too naive, and announced it as a huge success in their typical fashion.

What they then count on is people not having enough knowledge of DFT / Quantum property prediction to query their work and make claims like “it certainly does move academia way further ahead” - which is total rubbish. In what way? Why aren’t these models being used in ab initio simulators now? The answer to that is simple: they are not revolutionary, in fact they are not even useful.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Nimitz14 on Thursday June 08, 2023 @12:29PM (#36244585)
Love that you know enough to call him out haha
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by hugopenmir on Friday June 09, 2023 @02:06AM (#36253903)
Right! Finally, thanks!
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:46AM (#36241824)
Yes, people often mention the number scientific citations that mention AlphaFold as "proof" of its value. Unfortunately, padding researcher CVs is not a net positive for humanity, and so "moving academia further ahead" (by what metric?) is not necessarily a desirable or worthwhile goal if your definition of "ahead" is sufficiently warped as such. Perhaps, one day, the first real human being will be helped by medicine that couldn't have been found/created without AlphaFold. Unless a scientific endeavor is actually useful to humanity, who cares if it "moves ahead"?
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by gusennan on Thursday June 08, 2023 @02:43AM (#36238132)
They solved an open challenge problem, Protein Structure Prediction, with AlphaFold, which has been nothing short of revolutionary in the structural biology and biochemistry fields. I do scientific research in these fields and the capabilities AlphaFold provides are used now everywhere.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bamboozled on Thursday June 08, 2023 @06:29AM (#36239634)
Curious what this research has actually improved in a practical sense? I’m asking for a friend…
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:49AM (#36241870)
Yes, many research papers have been written, and many CVs have added lines which include the word "AlphaFold". But has the human condition been improved one iota from the "discovery"? Has anything real actually happened? Not at all. Only "maybes" and "possibilities" after more than 5 years of work. "Revolutionary" at padding researcher CVs indeed.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by hugopenmir on Friday June 09, 2023 @02:08AM (#36253922)
Man, with al respect why your “hate” with the good guys working at DeepMind? Everybody loves and respect Demis Hassabis, he is truly a genius. He really wants the best for the world/humanity and that takes a ton of time, so let’s wait and see.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by rcxdude on Wednesday June 07, 2023 @04:27PM (#36233076)
I think this is a bit far in the other direction. Deepmind's stuff is often deeply impressive, they just have a tendency to exaggerate on top of that.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by jprd on Wednesday June 07, 2023 @05:46PM (#36234050)
+1

There must be a "demonstrate (1) DeepMind #Win per <interval>" requirement somewhere that gets the once-over from the marketing dept. to meet some MBOs.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by programmer_dude on Wednesday June 07, 2023 @04:43PM (#36233259)
BTW Elo is not an abbreviation it is a persons name: https://en.wikipedia.org/wiki/Arpad_Elo
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by gdy on Wednesday June 07, 2023 @04:54PM (#36233416)
"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 u... by TaupeRanger on Wednesday June 07, 2023 @04:57PM (#36233450)
That claim is often made, and never substantiated.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by nahstra on Wednesday June 07, 2023 @05:15PM (#36233693)
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by gdy on Wednesday June 07, 2023 @05:33PM (#36233872)
Just ask any professional Go player.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:42AM (#36241748)
Anecdotes are not data. Look at the game statistics. There is zero evidence that players are playing at a higher level since the inception of AlphaGo.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by digging on Wednesday June 07, 2023 @06:19PM (#36234433)
It's made here in response to a claim that Go players are made worse by practicing with AlphaGo, which is also unsubstantiated.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:40AM (#36241719)
Wrong. The claim was never made that players got worse, only that their ratings dropped, which is empirically true. After playing AlphaGo, for example, Ke Jie dropped in the rankings and was quickly taken out of 1st place overall. The overall point though, is that AlphaGo produced nothing of value for humans, since there's also no evidence that players have improved since AlphaGo's creation. Factoring in the immense cost and human brainpower wasted on creating a superhuman perfect-information-game-playing program, and it's easily a net negative for humanity.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by gdy on Thursday June 08, 2023 @10:12AM (#36242181)
"there's also no evidence that players have improved since AlphaGo's creation"

Read this for example. The author is Korean pro.

"The upside is that we sometimes see a player who was somewhat past his prime suddenly climb back to the top, having trained with AI more intensely. There are a growing number of young and new pros who demonstrate surprising strength. This change gives hope to all pros who dream to become number one, and also makes competitions more interesting to fans as well." [0]

There are serious downsides too.

Also [1]

[0] https://hajinlee.medium.com/impact-of-go-ai-on-the-professio...

[1] https://www.newscientist.com/article/2364137-humans-have-imp...

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by digging on Thursday June 08, 2023 @11:23AM (#36243433)
> Factoring in the immense cost and human brainpower wasted on creating a superhuman perfect-information-game-playing program, and it's easily a net negative for humanity.

Hear me out - what if we learned something about creating AI by creating a new AI?

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by fastball on Wednesday June 07, 2023 @11:03PM (#36236664)
Assuming a total lack of evidence on either side, I think your assertion is the counter-intuitive one and therefore has the greater burden of proof. Why would Go be any different than Chess?

A rising tide floats all ships – if the best in the world becomes better, others can look at the best and learn from it. What difference does it make if the best player is an AI or a human? The better moves and strategies are still better moves and strategies.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Shorel on Thursday June 08, 2023 @01:27AM (#36237603)
Not AlphaGo, but there are newer neural networks tailored not to crush players, but to teach and explain their playing style, such as Lizzie with Leela Zero.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by ipaddr on Wednesday June 07, 2023 @10:05PM (#36236257)
That's like wearing a baseball glove on your dominate hand and taking it off to throw the ball. It's easier but at some point you need to relearn how to play to make it to the next level
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by 29athrowaway on Wednesday June 07, 2023 @05:15PM (#36233688)
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 u... by chaxor on Wednesday June 07, 2023 @06:06PM (#36234292)
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 works scaled up.

Don't get me wrong, Sutskyver (et al) has done incredibly good work previously, but when it comes to the products, they're much more engineering and marketing polish than scientific endeavours.

Botvinick's work on metaRL for example is an interesting direction that Deepmind has shown that few other companies that are only interested in engineering would venture towards.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by mtlmtlmtlmtl on Thursday June 08, 2023 @02:53AM (#36238204)
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 computer chess. But the problem is the computer chess community had to redo all of the work, including all the training to build Leela Chess Zero. Due to lack of Google-sized datacentres the training took years to catch up to the weights in AlphaZero. Same thing with AlphaGo, same thing with transformers.

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 completely reject your idea that somehow the work by OpenAI is less worthy of recognition. I think that's just nonsense.

And surely, Google created Deepmind to actually make them product ideas, not create new competitors, which is what has happened.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by qumeric on Thursday June 08, 2023 @12:44PM (#36244806)
> 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 u... by chpatrick on Wednesday June 07, 2023 @08:16PM (#36235469)
Massive improvements in protein folding do nothing to improve the human condition? What?
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by girvo on Wednesday June 07, 2023 @10:08PM (#36236280)
I think it's fair to say that it (where "it" is defined as "DeepMind's contribution to the protein folding problem") hasn't yet given us massive improvements to the human condition.

It might, and in fact I think it probably will. But it hasn't yet.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bawolff on Wednesday June 07, 2023 @11:40PM (#36236891)
When the biggest criticism of deep mind is it hasn't literally saved the world yet, i think that is pretty telling about how impressive it really is.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:34AM (#36241631)
That isn't the criticism at all. The criticism is that it hasn't done ANYTHING, and has probably been a net negative since human brainpower and energy costs are being spent on (so far) useless technology for 5 years. It's not that it hasn't saved the world, it's that it's worse than useless.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bamboozled on Thursday June 08, 2023 @06:24AM (#36239588)
To be fair I have read that while impressive, still has little practical application?
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Thursday June 08, 2023 @09:33AM (#36241600)
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.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bglazer on Thursday June 08, 2023 @12:49PM (#36244913)
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 u... by TaupeRanger on Thursday June 08, 2023 @02:17PM (#36246263)
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 u... by hugopenmir on Friday June 09, 2023 @03:32PM (#36262939)
Send them your resume or ideas about how to do it faster and better, it could help !
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by TaupeRanger on Friday June 09, 2023 @04:41PM (#36263894)
There is no way to do it faster or better with these techniques. It is a waste of money - that's the entire point. My advice would be: stop wasting time, money, and human brainpower. Go off and try entirely new approaches to AI that might actually work!
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by chpatrick on Saturday June 10, 2023 @08:35AM (#36269957)
This is such a bizarre take. AlphaFold is faster and better - but it still takes years to develop anything in the life sciences.

It's like pointing to special relativity in 1905 and saying it'll never be useful for anything.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by hugopenmir on Friday June 09, 2023 @03:32PM (#36262927)
Exactly !
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by crocowhile on Thursday June 08, 2023 @01:14PM (#36245311)
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 u... by TaupeRanger on Thursday June 08, 2023 @02:18PM (#36246287)
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 u... by blazespin on Wednesday June 07, 2023 @03:28PM (#36232190)
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 u... by ryao on Wednesday June 07, 2023 @06:56PM (#36234830)
It is likely meant to help secure further research funds.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by aldousd666 on Thursday June 08, 2023 @11:31PM (#36252771)
Well. I feel grifted too because being a developer, yet not into the state of the art in algorithms (at that level,) i was inclined to buy their BS
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by scotty79 on Wednesday June 07, 2023 @03:58PM (#36232631)
Shouldn't libc++ be kinda good? Since it's the standard and all? Why isn't/wasn't it?
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by petschge on Wednesday June 07, 2023 @04:16PM (#36232904)
The LLVM implementation of libc++ is very young compared to other implementations (it was started 5 years ago or so), so there is still a lot of things missing and a lot of things that can be improved.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bigcheesegs on Wednesday June 07, 2023 @04:38PM (#36233201)
libc++ was open sourced May 11th 2010. 13 years ago. https://blog.llvm.org/2010/05/new-libc-c-standard-library.ht...
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by danlark on Wednesday June 07, 2023 @04:33PM (#36233139)
I agree on the sorting front. Removing one cmov is not likely to improve much.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by orlp on Wednesday June 07, 2023 @04:45PM (#36233291)
It's not even a cmov. Look at Figure 3 in the paper: https://www.nature.com/articles/s41586-023-06004-9

They eliminated a register-register mov.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by choppaface on Wednesday June 07, 2023 @04:50PM (#36233362)
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 u... by dundarious on Wednesday June 07, 2023 @05:07PM (#36233581)
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 u... by as4296 on Wednesday June 07, 2023 @07:02PM (#36234882)
Lol I was about to say that would be incredibly crazy if they found a new sorting algorithm. My time complexity in USACO bout to go crazy.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by dataflow on Wednesday June 07, 2023 @07:16PM (#36235009)
I get your sentiment but note that discovering a new algorithm doesn't have to imply a better time complexity. Bubble Sort and Insertion Sort have the same time complexity but are different algorithms.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by saiojd on Wednesday June 07, 2023 @07:04PM (#36234903)
I feel like your take is overly cynical. The fact that humans can do the same thing by hand is not really the point. The contribution lies in the fact that their method derived this improvement *automatically*, which is where the impact lies. No one cares all that much if a human can make a sorting routine 2% faster, but if a program can do it, it suddenly becomes interesting (since it suggests that a similar approach can be applied to many other routines).
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by orlp on Wednesday June 07, 2023 @07:21PM (#36235057)
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 noted, superoptimizers are also already a thing: https://en.wikipedia.org/wiki/Superoptimization

There's also automatic searching being done on faster sorting networks that actually recently produced better than state of the art sorting networks: https://github.com/bertdobbelaere/SorterHunter

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by touisteur on Wednesday June 07, 2023 @07:25PM (#36235088)
I somehow agree that I'd be far more impressed by something that would find optimal or even just better sorting (or selection) networks for sizes higher than 17 (last time I looked at SOTA).
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by orlp on Wednesday June 07, 2023 @07:25PM (#36235091)
Please check my edit right as you commented :)
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by touisteur on Wednesday June 07, 2023 @07:39PM (#36235213)
Oh very, very cool thanks a bunch.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by saiojd on Wednesday June 07, 2023 @07:59PM (#36235354)
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 the actual domain. After AlphaGo exceeded expectations, the question becomes: "What else can RL do, and can it do anything actually useful?", and this paper seems to suggest that it can optimize code pretty well! I'm really not sure they are self-aggrandizing in terms of impact. The impact of an approach like this could potentially be very large (although I'm not saying that it actually is, I don't know enough).

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bloppe on Wednesday June 07, 2023 @08:10PM (#36235434)
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 calling it a new sorting algorithm.

But ya, discovering a new compiler optimization automatically is kinda cool.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by recursive on Wednesday June 07, 2023 @08:26PM (#36235529)
70% better than O(N log N) is still O(N log N).
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by ummonk on Wednesday June 07, 2023 @08:55PM (#36235775)
It's 70% better than O(1). The algorithms it found are for sort3, sort4, and sort5, which were poorly optimized in LLVM's libc++.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by pclmulqdq on Thursday June 08, 2023 @12:10PM (#36244270)
It may have also laundered those from open-source code that wanted to optimize sort3, sort4, and sort5.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by saiojd on Wednesday June 07, 2023 @09:16PM (#36235925)
I see your point. I just went over the abstract again and I totally agree.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Dylan16807 on Thursday June 08, 2023 @01:07AM (#36237471)
> 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.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by cubefox on Thursday June 08, 2023 @12:26PM (#36244540)
When people say "sorting algorithm" they mean something like bubble sort or merge sort.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by qumeric on Thursday June 08, 2023 @12:37PM (#36244700)
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 u... by elcomet on Saturday June 10, 2023 @04:09AM (#36268661)
I hope people majoring in CS will not think that, as they learned that n log n is the theorically best complexity for a sort algorithm. They will rather think that they found an algorithm with better constants in front of n log n.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Zacharias030 on Saturday June 10, 2023 @04:27PM (#36274742)
true that
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bamboozled on Thursday June 08, 2023 @06:18AM (#36239553)
When one has a big fuck off hammer, everything becomes a nail. Seems to apply to ML too.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by rep_movsd on Thursday June 08, 2023 @01:03PM (#36245149)
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

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by runsWphotons on Thursday June 08, 2023 @12:15AM (#36237111)
how automatically generated was the code that wrote the code
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by smeagull on Wednesday June 07, 2023 @07:12PM (#36234978)
A thing that is also not novel. People have done search for optimisations for at least the past decade.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by saiojd on Wednesday June 07, 2023 @07:43PM (#36235241)
Sure, but the whole point is to reduce this kind of search to RL, which is a very general framework. Their paper shows that such a generic approach can solve a very specific problem, and solve it well. But, their paper is about improving RL, not about improving sorting.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Zacharias030 on Saturday June 10, 2023 @04:30PM (#36274780)
sometimes one has to wonder how RL can be both so generic and still be qualification to publich in nature again and again and again ;)
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by x86x87 on Wednesday June 07, 2023 @11:12PM (#36236707)
i don't read it as cynical. It's fair game to call bullshit on bullshit. If an approach exists and is known the "insert your favorite AI here" does not discover anything.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by mtlmtlmtlmtl on Thursday June 08, 2023 @02:25AM (#36238012)
Automatic tuning and optimisation of code is not new.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by neximo64 on Wednesday June 07, 2023 @08:47PM (#36235697)
What you're saying is a certain perspective which seeks to look at it from first principles.

To the brutalist, the algorithm change is faster, and thats all that matters. A human didn't previously come up with the optimisation. You might as well say a computer sorting an algorithm is bullshit vs a person because the difference is just a bloated chip does it instead, and thats it.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by tlringer on Thursday June 08, 2023 @12:30AM (#36237219)
Every DeepMind press release is like this.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by hugopenmir on Friday June 09, 2023 @02:28AM (#36254059)
You know people at Google, tell Demis about this.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by wsdookadr on Thursday June 08, 2023 @01:38AM (#36237669)
What's surprising is that anyone would've expected an AI to come up with a brand-new algorithm with better complexity than pre-exsiting human-made solutions. How could it possibly come up with something better when it doesn't even understand how the original authors of qsort/mergesort/etc came up with their own..

Sure, it's great PR for the company, but.. the results just aren't there.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by congoe on Thursday June 08, 2023 @02:50AM (#36238176)
How could AlphaZero possibly play better chess than humans when it doesn’t even understand the history of chess theory?

RL doesn’t stop at human levels

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by Maken on Thursday June 08, 2023 @06:37AM (#36239710)
Because the entire history of chess theory is really a set of heuristics to optimize a tree search.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by lupire on Thursday June 08, 2023 @08:15PM (#36251272)
So is computer science.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by wsdookadr on Saturday June 10, 2023 @07:33AM (#36269630)
You make it sound so simple. Why don't we let an AI try to come up with all of CS on its own? I doubt it would/could.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by wsdookadr on Friday June 09, 2023 @03:25PM (#36262833)
Even if AlphaZero does play better chess, there's absolutely zero it can do in terms of explaining why it played that way. AlphaZero is zero in terms of explainability. Humans have to explain to themselves and to others what they do, this is key in understanding what's happening, in communicating what's happening, in human decision-making, in deciding between what works and what doesn't and how well or how bad it works.

Returning back to the original DeepMind press release, it's misinforming the public about the alleged progress, in fact no fundamental progress was made, DeepMind did not come up with an entirely new sorting algorithm, the improvement was marginal at best.

I maintain my opinion that Alphadev does not understand any of the existing sorting algorithms at all.

Even if AI comes up with a marginal improvement to something, it's incapable of explaining what it has done. Humans (unless they're a politician or a dictator) always have to explain their decisions, how they got there, they have to argue their decisions and their thought-process.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by elcomet on Saturday June 10, 2023 @04:12AM (#36268670)
It cannot explain because (1) it is not necessary to become good and (2) it wasn't explicitly trained to explain.

But it's reasonable to imagine a later model trained to explain things. The issue is that some positions might not be explainable, as they require branching too much and a lot of edge cases, so the explanation is not understandable by the human.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by wsdookadr on Saturday June 10, 2023 @03:21PM (#36274065)
It's unreasonable to give up on explanations and deem something "not understandable" when we've been doing this thing for 3000+ years called mathematics, where it's exactly explainability that we seek and the removal of doubt. The only other entities that we know of who can't communicate or explain what they're doing are animals.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by elcomet on Sunday June 11, 2023 @07:46PM (#36286926)
Can you explain your tastes? Why you prefer an apple to an orange for instance? Not really.

Can you explain how you had the intuition for a certain idea ? No you can explain why it works but not how the intuition came.

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by wsdookadr on Tuesday June 13, 2023 @01:09PM (#36313319)
This isn't a question of taste. The topic can't be trivialized to a choice between apples and oranges. I actually reject your entire last message.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by elcomet on Wednesday June 14, 2023 @11:55AM (#36327848)
My point is that most of our actions are intuitive and cannot be explained. maybe this is similar to system 1 vs system 2.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by wsdookadr on Thursday June 15, 2023 @11:54PM (#36350983)
It's fine if you want to refer to Kahneman's classification [1] of instinctual and thorough thinking. Explainability is a separate topic. Also when the amount of energy and compute used are as high as they are.. the results, the return on investment really isn't that high. Hopefully there are better days ahead.

[1] https://en.wikipedia.org/wiki/Thinking,_Fast_and_Slow

Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by usmansk on Thursday June 08, 2023 @02:03PM (#36246046)
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 u... by usmansk on Saturday June 10, 2023 @01:27PM (#36272582)
Can anyone refute the claim of orlp that it is unrolled insertion sort