>An interesting and counter-intuitive consequence of Theorem 1, derived in Section 7, is that the fastest program that computes a certain function is also among the shortest
programs that provably computes this function. Looking for larger programs saves at most a finite number of computation steps, but cannot improve the time order.
Pretty cool paper, it's from 2002 that's amazing. I'm having trouble locating the factor of five explanation. Why 5? Is it just the safest lowest bound they could guarantee without too much prodding?
It's a purely arbitrary number, arising from the choice of an 80/20 division of CPU cycles between exploring and exploiting. You have to choose some number; pretty much any choice would work more or less equally well here, though there is a sense in which 2 would be the simplest/most natural choice.
From section 5:
The factor of 5 may be reduced to 4 + ε by assigning a larger fraction of time to algorithm C. The constants cp and dp will then be proportional to 1/ε. We were not able to further reduce this factor.
Will the ultimate search for asymptotically fastest programs typically lead to fast or slow programs for arguments of practical size? Levin search, matrix multiplication and the algorithm Mp∗ seem to support the latter, but this might be due to our inability to do better.
Asymptotic complexity analysis is kind of broken, there's more of a tradeoff in using different algorithms than "\Theta(n) is better than \Theta(n \log n)" would indicate.
I wonder if a better framework exists, but that's probably several open research topics bundled in a single question.
Yes, it offends my aesthetic sense when the asymptotically fastest algorithms for simple problems are complex monsters. It didn't used to be like that: early fast algorithms (like heapsort and FFT) are only very slightly more complex than the naive ones.
Cooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago:
def fft(x):
N = len(x)
if N == 1:
return x
assert N % 2 == 0
E = fft(x[::2])
O = fft(x[1::2])
X = [None] * N
for k in range(N // 2):
tf = np.exp(-2j * np.pi * k / N)
X[k] = E[k] + tf * O[k]
X[k + N//2] = E[k] - tf * O[k]
return X
Computer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems.
Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm.
Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).
I really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.
I remember showing a coworker a complexity analysis I did, where I'd written "0.002 n lg n + 3n". I was surprised when they asked "why did you put the insignificant one first?" but then realized... that's exactly right! Even for universe sized problems, 3n is more than 0.002 n lg n.
Basically, as soon as you care enough about constant factors to actually compute them, some of your habits from doing asymptotic analysis can be actively harmful.
M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes
I’m always surprised that more research doesn’t start from the mathematical “end” and work backwards to something that approximates it.
For instance, assuming our universe is computable (or at least can be approximated to a high degree as computable), we know that Solomonoff induction is in some sense a mathematical upper bound on the best we could do at predicting the future.
If we had a magical program that, given a sequence of data S, found the shortest (prefix free, non-halting) program that produced S, we would essentially have real AI (and the “best” AI, in some mathematical sense on general optimality over other algorithms).
We know this is uncomputable, but I’m surprised that this fact seems to totally throw a wrench into at least approximating it. I suppose some efforts in reinforcement learning could sort of be considered attempts at this, but not really in the sense of mathematically developing the best physical implementation to solving the problem.
One thing to keep in mind with all these "Universal AI" ideas (Hutter Search, Levin Search, Goedel Machines, etc.) is that they make very few assumptions about the task. That's their strength, but it's also what makes them hopelessly inefficient. We can get massive speedups by introducing a bit more structure, e.g. inverting differentiable functions rather than all functions makes it practical to use neural networks and their like; inverting convex functions lets us do simple hill climbing; etc.
In the case of Hutter Search specifically, we could get much more promising results if we're willing to throw away Turing Completeness. For example, it's easier to find provable optimisations if we're dealing with regexps rather than arbitrary programs. Of course, such "easy" systems tend to have fast approaches already.
I think there's definitely a role for these algorithms, but mostly as an "outer loop"; similar to using grid-search to find good hyperparameters of an ML model; or how we often throw genetic algorithms at tasks which have no 'obviously correct' solution (like choosing the architecture of a neural network)
I like to think of this as the "ultimate JIT compiler": when we start executing a program, we run an optimiser in parallel. Hence the longer the program takes, the longer we spend optimising it; this focuses our optimisation efforts, similar to how JITs only kick in after functions have been called a certain number of times.
The main difference between Hutter's algorithm and a JIT compiler is that JITs operate locally on small pieces of a program, like functions; whilst Hutter's optimisation is global. This causes an interesting problem: how do we switch to the optimised version? JITs don't bother switching calls which are already running; they just send any future calls to the optimised version. Whole-program optimisers can't do that, since there's nothing left to execute once the whole-program has finished. Exponential-restarting is an interesting hack to avoid this, but seems like a last-resort compared to local improvements.
I think it would be an interesting project to build an interpreter which works like Hutter Search, but allowing local improvements more like a normal JIT as well. It could keep track of a fixed number of search states (based on some longest-running/recently-used heuristic) to avoid having to always restart from scratch.
My guess is it would be pretty slow for "straightforward" tasks (assuming we don't bother to do much "manual" optimisation); long-running tasks with lots of iteration would see gradual speedups (as simple optimisations are found for their hottest loops); whilst a few very hard tasks, left running for a long time, may finish unexpectedly (when the optimiser stumbles across a much faster approach).
> An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof.
So this solves any problem that you can formally specify with the same complexity as the best algorithm?
This sounds too good to be true, what's the catch?
This prior discussion [1] on levin complexity might be relevant. I think the catch is basically that there's a huge constant out in front which makes this impractical. IIUC, in the case of levin search, the reason for this huge constant is that at a high-level that the algorithm functions as follows (for the specific case of solving 3-sat) for an input x of size n, enumerate all TMs 1..n and simulate each on x for a certain number of steps (fixed function of n). If any one of them produce a satisfying assignment, output that assignment.
You can see why this is a type of universal search: if the optimal algorithm is say polynomial (e.g. we assume that P=NP), then the above algorithm is also close to polynomial of one higher degree (as simulation is only a log factor) and by definition always outputs a satisfying assignment. The catch is that it only works if n is large enough to allow it to "discover" the right TM, and in the worst-case the minimum value of n for which the algorithm starts to work is the index of the encoding of a 3-sat algorithm, which is probably quite long. (A natural question to ask is that if such an TM index can be discovered, why not just use that TM directly? I believe it's because levin algorithm doesn't guarantee that the TM that we discover which produces a satisfying assignment is necessarily a valid TM for all inputs x. It could just be we got lucky and found a TM which worked only for this specific case.)
25 comments
[ 2.8 ms ] story [ 64.1 ms ] threadPretty cool paper, it's from 2002 that's amazing. I'm having trouble locating the factor of five explanation. Why 5? Is it just the safest lowest bound they could guarantee without too much prodding?
From section 5: The factor of 5 may be reduced to 4 + ε by assigning a larger fraction of time to algorithm C. The constants cp and dp will then be proportional to 1/ε. We were not able to further reduce this factor.
I wonder if a better framework exists, but that's probably several open research topics bundled in a single question.
Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm.
Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).
> This work could be viewed as another O() warning showing how important factors and even subdominant additive terms are.
Basically, as soon as you care enough about constant factors to actually compute them, some of your habits from doing asymptotic analysis can be actively harmful.
(for anyone who shares my pet hatred for researchgate)
For instance, assuming our universe is computable (or at least can be approximated to a high degree as computable), we know that Solomonoff induction is in some sense a mathematical upper bound on the best we could do at predicting the future.
If we had a magical program that, given a sequence of data S, found the shortest (prefix free, non-halting) program that produced S, we would essentially have real AI (and the “best” AI, in some mathematical sense on general optimality over other algorithms).
We know this is uncomputable, but I’m surprised that this fact seems to totally throw a wrench into at least approximating it. I suppose some efforts in reinforcement learning could sort of be considered attempts at this, but not really in the sense of mathematically developing the best physical implementation to solving the problem.
In the case of Hutter Search specifically, we could get much more promising results if we're willing to throw away Turing Completeness. For example, it's easier to find provable optimisations if we're dealing with regexps rather than arbitrary programs. Of course, such "easy" systems tend to have fast approaches already.
I think there's definitely a role for these algorithms, but mostly as an "outer loop"; similar to using grid-search to find good hyperparameters of an ML model; or how we often throw genetic algorithms at tasks which have no 'obviously correct' solution (like choosing the architecture of a neural network)
The main difference between Hutter's algorithm and a JIT compiler is that JITs operate locally on small pieces of a program, like functions; whilst Hutter's optimisation is global. This causes an interesting problem: how do we switch to the optimised version? JITs don't bother switching calls which are already running; they just send any future calls to the optimised version. Whole-program optimisers can't do that, since there's nothing left to execute once the whole-program has finished. Exponential-restarting is an interesting hack to avoid this, but seems like a last-resort compared to local improvements.
I think it would be an interesting project to build an interpreter which works like Hutter Search, but allowing local improvements more like a normal JIT as well. It could keep track of a fixed number of search states (based on some longest-running/recently-used heuristic) to avoid having to always restart from scratch.
My guess is it would be pretty slow for "straightforward" tasks (assuming we don't bother to do much "manual" optimisation); long-running tasks with lots of iteration would see gradual speedups (as simple optimisations are found for their hottest loops); whilst a few very hard tasks, left running for a long time, may finish unexpectedly (when the optimiser stumbles across a much faster approach).
Many JITs can do this. This is called "on-stack replacement" (OSR).
So this solves any problem that you can formally specify with the same complexity as the best algorithm?
This sounds too good to be true, what's the catch?
You can see why this is a type of universal search: if the optimal algorithm is say polynomial (e.g. we assume that P=NP), then the above algorithm is also close to polynomial of one higher degree (as simulation is only a log factor) and by definition always outputs a satisfying assignment. The catch is that it only works if n is large enough to allow it to "discover" the right TM, and in the worst-case the minimum value of n for which the algorithm starts to work is the index of the encoding of a 3-sat algorithm, which is probably quite long. (A natural question to ask is that if such an TM index can be discovered, why not just use that TM directly? I believe it's because levin algorithm doesn't guarantee that the TM that we discover which produces a satisfying assignment is necessarily a valid TM for all inputs x. It could just be we got lucky and found a TM which worked only for this specific case.)
[1] https://news.ycombinator.com/item?id=27045091