RL: Reinforcement Learning
Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
11–20 of 328 posts
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#12The most interesting part of this paper to me is that they let the agent guess how efficient it’s own solutions were and only had the model experimentally verify it’s guesses in 0.002% of cases. This allowed the model to search much faster than another program that didn’t guess and had to run every program.
That sounds like intuition.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#13> The confidence intervals are represented as latency ± (lower, upper), in which latency corresponds to the fifth percentile of latency measurements across 100 different machines. Lower and upper refer to the bounds of the 95% confidence interval for this percentile.
Does anybody know why they chose fifth percentile? I though we should always choose the fastest time when measuring performance.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#14Can anyone explain how this worked? as per the paper (which I TLDRed): "A single incorrect instruction in the AssemblyGame can potentially invalidate the entire algorithm, making exploration in this space of games incredibly challenging."
What did it do if it didn't have a useful partial score function? How did it avoid brute force?
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#15"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."
> up to 70% faster
So O(0.3(N log N))? That's still O(N log N)
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#16*Google DeepMind
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#17Not general or universal. Only for pre-trained data and with abysmal worst cases.
I'm not positive what you mean here. Are you saying the discovered algorithm isn't actually good? Didn't LLVM accept it?
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#18It is astounding how something as well as studied as sorting still has opportunities for further improvements!
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#19"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."
> up to 70% faster So O(0.3(N log N))? That's still O(N log N)
In the real world, we care about runtime as much as, if not more than, computational complexity.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#20"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."
> up to 70% faster So O(0.3(N log N))? That's still O(N log N)
They're not going to find a general sorting algorithm faster than O(n log n), but that doesn't mean all O(n log n) sorts are created equal.