Machine Dependence / Suboptimal Computation of the Data: Expected Loss Bounds

So far we have assumed the process computing the data is (asymptotically) optimally efficient, running on a particular universal computer, our reference machine. In general, however, we cannot know the machine used to run this process. Furthermore, the process may be nonoptimal even with respect to its machine. For such reasons we now relax our initial assumption, and show that $S$-based predictions on our reference machine still work well.

Consider a finite but unknown program $p$ computing $y \in B^{\infty}$. What if Postulate 1 holds but $p$ is not optimally efficient, and/or computed on a computer that differs from our reference machine? Then we effectively do not sample beginnings $y_k$ from $S$ but from an alternative semimeasure

$$S'(y_k) \leq 1/t$$

for any $y_k$ whose computation through $p$ costs more than $O(t)$ time. Can we still predict well? Yes, because the Speed Prior $S$ dominates $S'$: For all $x \in B^*$,

$$S(x) \geq c_{S'} S'(x),$$ (7)

where $c_{S'}$ is a constant depending on $S'$ but not on $x$, because FAST computes $y$ faster than $p$, and thus $S(y_k) \geq O(1/t)$. This dominance is all we need to apply Hutter's recent loss bounds [9]:

In practice we have to use $\bar{S}_{\epsilon}$ instead of $S$. Does that cost us a lot? Again the answer is no, since for any $\epsilon > 0$,

$$\bar{S}_{\epsilon}(x) \geq c_{S} S(x),$$ (8)

where $c_{S}$ is a constant independent of $x$. That is, in analogy to Corollary 1 (using analogous notation) we obtain

$$0 \;\leq\; L_{n\Lambda_{\bar{S}_{\epsilon}}}-L_{n\Lambda_{S'}} = O(\sqrt{L_{n\Lambda_{S'}}}).$$ (9)

To summarize: The loss that we are expected to receive by predicting according to computable $\bar{S}_{\epsilon}$ instead of the true but unknown $S'$ does not exceed the optimal loss by much.

Back to Speed Prior page