Loss Bounds and Time Complexity for Speed Priors


Daniel Filan, Jan Leike, Marcus Hutter ;
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1394-1402, 2016.


This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002), and show that our prior can predict sequences drawn from probability measures that are estimable in polynomial time. Our speed prior is computable in doubly-exponential time, but not in polynomial time. On a polynomial time computable sequence our speed prior is computable in exponential time. We show that Schmidhuber’s speed prior has better complexity under the same conditions; however, the question of its predictive properties remains open.

Related Material