Bounded Solomonoff induction using optimal predictor schemes

[Vanessa Kosoy]

Most of the content of this post was covered by the talk I gave in Los Angeles MIRIx in October, minus the proofs and a minor amendment of Theorem 1 (the role of ${\Delta }_{sqp,\varphi }^2$).

We define variants of the concept of generatable distributional estimation problem and show that these variants also admits a uniformly universal optimal predictor scheme. We show how to use this to implement a form of bounded Solomonoff induction.

Results

We have previously defined a “word ensemble” to be a collection $\{{\mu }^k{\}}_{k\in N}$ of probability measures on $\{0,1{\}}^{\ast }$ s.t. for some polynomial $p$, $\mathrm{supp}{\mu }^k\subseteq \{0,1{\}}^{\le p\left(k\right)}$. This was convenient when the formalism was based on Boolean circuits but unnecessary for Turing machines. It is enough to assume that the Turing machine is allowed to read only the beginning of the input and thus halt in time arbitrarily smaller than the length of the input. In the following we will use “word ensemble” to mean an arbitrary sequence of probability measures on $\{0,1{\}}^{\ast }$, allow such word ensembles in distributional estimation problems etc.

All proofs are in the Appendix.

We start by defining “$\Delta \left(log\right)$-sampler” and “$\Delta \left(log\right)$-generator” for $\Delta$ an error space of rank 2 (they were previously defined for an error space of rank 1). Fix such an error space.

Definition 1

Consider $\mu$ a word ensemble. A $(poly,log)$-bischeme $\hat{S}$ of signature $1\to \{0,1{\}}^{\ast }$ is called a $\Delta \left(log\right)$-sampler for $\mu$ when

$$\sum _{x\in \{0,1{\}}^{\ast }}|{\mu }^k\left(x\right)-Pr[{\hat{S}}^{kj}=x]|\in \Delta$$

When $\hat{S}$ has no advice, it is called a $\Delta$-sampler.

$\mu$ which admits such $\hat{S}$ is called $\Delta \left(log\right)$-sampleable or $\Delta$-sampleable correspondingly.

Definition 2

Consider $(f,\mu )$ a distributional estimation problem. A $(poly,log)$-bischeme $\hat{G}$ of signature $1\to \{0,1{\}}^{\ast }\times [0,1]$ is called a $\Delta \left(log\right)$-generator for $(f,\mu )$ when

(i) ${\hat{G}}_1$ is a $\Delta \left(log\right)$-sampler for $\mu$.

(ii) $$E_{U^{r_G(k,j)}}\left[\right({\hat{G}}^{kj}(y{)}_2-f({\hat{G}}^{kj}\left(y{)}_1\right){)}^2]\in \Delta$$

When $\hat{G}$ has no advice, it is called a $\Delta$-generator.

$(f,\mu )$ which admits such $\hat{G}$ is called $\Delta \left(log\right)$-generatable or $\Delta$-generatable correspondingly.

---

We now introduce a variant in which the generator matches $f$ on average but is allowed to have arbitrary variance.

Definition 3

Consider $(f,\mu )$ a distributional estimation problem. A $(poly,log)$-bischeme $\hat{G}$ of signature $1\to \{0,1{\}}^{\ast }\times [0,1]$ is called a weak $\Delta \left(log\right)$-generator for $(f,\mu )$ when

(i) ${\hat{G}}_1$ is a $\Delta \left(log\right)$-sampler for $\mu$.

(ii) $$E_{U^{r_G(k,j)}}\left[\right(E_{U^{r_G(k,j)}}\left[{\hat{G}}^{kj}\right(y^{\prime }{)}_2\mid {\hat{G}}^{kj}(y^{\prime }{)}_1={\hat{G}}^{kj}(y{)}_1]-f({\hat{G}}^{kj}\left(y{)}_1\right){)}^2]\in \Delta$$

When $\hat{G}$ has no advice, it is called a weak $\Delta$-generator.

$(f,\mu )$ which admits such $\hat{G}$ is called weakly $\Delta \left(log\right)$-generatable or weakly $\Delta$-generatable correspondingly.

Proposition 1

Consider $(f,\mu )$ a distributional estimation problem. Any $\Delta \left(log\right)$-generator for $(f,\mu )$ is in particular a weak $\Delta \left(log\right)$-generator for $(f,\mu )$.

---

We now show that weak generators enable an existence theorem for optimal predictor schemes of the same form as generators.

Construction 1

Given $\varphi \in \Phi$ we define ${\Delta }_{sqp,\varphi }^2$ to be the set of bounded functions $\delta :N^2\to R^{\ge 0}$ s.t. for any $\psi \in \Phi$, if $\psi \le \varphi$ then ${sup}_{j\ge t_{\psi }\left(k\right)}\delta (k,j)\in {\Delta }_{\psi }^1$. It is easy to see ${\Delta }_{sqp,\varphi }^2$ is an error space.

We define ${\Delta }_{sqp}^2:={\bigcap }_{\varphi \in \Phi }{\Delta }_{sqp,\varphi }^2$. ${\Delta }_{sqp}^2$ is also an error space.

Proposition 2

$${\Delta }_{sqp,\varphi }^2\subseteq {\Delta }_{ll,\varphi }^2$$

$${\Delta }_{sqp}^2\subseteq {\Delta }_{ll}^2$$

Construction 2

We describe an oracle machine $\hat{\Lambda }$ that accepts an oracle of signature $O:N^2\to \{0,1{\}}^{\ast }\times [0,1]$ and implements a $(poly,0{)}^O$-predictor scheme. Consider the computation of $\hat{\Lambda }\left[O{]}^{kj}\right(x)$.

We loop over the first $j$ words in lexicographic order. For each word $Q$, we loop over $j^2$ “test runs”. At test run $i$, we generate $(x_i\in \{0,1{\}}^{\ast },t_i\in [0,1\left]\right)$ by evaluating $O^{kj}$ (we treat $O$ as random, that is, we don’t expect repeated answers to the same query to coincide). We then sample $z_i$ from $U^j$ and compute $s_i:=e{v}^j(Q,x_i,z_i)$. At the end of the test runs, we compute the average error $ϵ\left(Q\right):=\frac{1}{jk}{\sum }_i(s_i-t_i{)}^2$. At the end of the loop over programs, the program $Q^{\ast }$ with the lowest error is selected and the output $e{v}^j(Q^{\ast },x)$ is produced.

Theorem 1

Consider $(f,\mu )$ a distributional estimation problem, $\varphi \in \Phi$ and $\hat{G}$ a weak ${\Delta }_{sqp,\varphi }^2\left(log\right)$-generator for $(f,\mu )$. Then, $\hat{\Lambda }\left[\hat{G}\right]$ is a ${\Delta }_{ll,\varphi }^2(poly,log)$-optimal predictor scheme for $(f,\mu )$.

Corollary 1

Consider $(f,\mu )$ a distributional estimation problem and $\hat{G}$ a weak ${\Delta }_{ll}^2\left(log\right)$-generator for $(f,\mu )$. Then, $\hat{\Lambda }\left[\hat{G}\right]$ is a ${\Delta }_{ll}^2(poly,log)$-optimal predictor scheme for $(f,\mu )$.

---

To demonstrate the difference between generators and weak generators, we give the following property of generators which weak generators don’t share.

Theorem 2

Consider $(f,\mu )$ a distributional estimation problem and $\hat{G}$ a corresponding $\Delta \left(log\right)$-generator. Suppose $\tau :[0,1]\to [0,1]$ is an $\alpha$-Hoelder continuous function for $\alpha \in (0,1]$ and $\hat{\tau }$ is a $[0,1]$-vallued $(poly,log)$-bischeme s.t.

$$\forall x\in \{0,1{\}}^{\ast }:E\left[\right({\hat{\tau }}^{kj}\left(x\right)-\tau \left(\beta \right(x\left)\right){)}^2]\in \Delta$$

Define ${\hat{G}}_{\tau }$ by

$${\hat{G}}_{\tau }^{kj}\left(y\right):=\left({\hat{G}}^{kj}\right(y{)}_1,{\hat{\tau }}^{kj}\left({\hat{G}}^{kj}\right(y{)}_2\left)\right)$$

Then, ${\hat{G}}_{\tau }$ is a $\Delta \left(log\right)$-generator for $(\tau \circ f,\mu )$.

---

This means that a generator yields an entire “logical probability distribution” for $f\left(x\right)$ whereas a weak generator yields only a “logical expectation value.”

The following constructions shows how to use Theorem 2 to implement a form of bounded Solomonoff induction.

Construction 3

Given $k\in N$, we define the probability distribution ${\sigma }^k$ on $N$ by

$$\forall j\in N:P{r}_{{\sigma }^k}[n\ge j]:=min(\frac{\log \log (k+3)}{\log \log (j+3)},1)$$

We define the probability distribution ${\mu }_{BSI}^k$ on $\{0,1{\}}^k\bigsqcup \left\{\perp \right\}$ by

$$\forall x\in \{0,1{\}}^k:{\mu }_{BSI}^k\left(x\right):=\sum _{n=0}^{\infty }{\sigma }^k\left(n\right)\frac{\#\left\{\right(y\in \{0,1{\}}^n,z\in \{0,1{\}}^n)\mid e{v}^n(y,z{)}_{<k}=x\}}{4^n}$$

$${\mu }_{BSI}^k\left(\perp \right):=\sum _{n=0}^{\infty }{\sigma }^k\left(n\right)\frac{\#\left\{\right(y\in \{0,1{\}}^n,z\in \{0,1{\}}^n)\mid |e{v}^n(y,z)|<k\}}{4^n}$$

Given $i\in \{0,1\}$, we define $f_{BSI\left(i\right)}:\{0,1{\}}^{\ast }\bigsqcup \left\{\perp \right\}\to [0,1]$ by

$$\forall x\in \{0,1{\}}^{\ast }:f_{BSI\left(i\right)}\left(x\right):=\sum _{n=0}^{\infty }{\sigma }^{|x|}\left(n\right)\frac{\#\left\{\right(y\in \{0,1{\}}^n,z\in \{0,1{\}}^n)\mid e{v}^n(y,z{)}_{\le |x|}=xi\}}{4^n}$$

$$f_{BSI\left(i\right)}\left(\perp \right):=0$$

Using an appropriate encoding $\{0,1{\}}^{\ast }\bigsqcup \left\{\perp \right\}$ can be identified with $\{0,1{\}}^{\ast }$ and $(f_{BSI\left(i\right)},{\mu }_{BSI})$ regarded as a distributional estimation problem.

Proposition 3

$(f_{BSI\left(i\right)},{\mu }_{BSI})$ is weakly ${\Delta }_{sqp}^2$-generatable.

---

The following claim is likely to be a theorem, but we haven’t worked out the details of the proof.

Claim

Consider a random Turing machine $M$ which produces an infinite sequence ${\omega }^M$ s.t. the time to compute the $k$-th bit is bounded by a quasi-polynomial in $k$. Given $k\in N$, define the probability measure ${\mu }_M^k$ on $\{0,1{\}}^{\ast }$ by

$${\mu }_M^k\left(x\right):=Pr[{\omega }_{<k}^M=x]$$

Given $i\in \{0,1\}$, define $f_{M\left(i\right)}:\{0,1{\}}^{\ast }\to [0,1]$ by

$$f_{M\left(i\right)}\left(x\right):=Pr[{\omega }_{|x|}^M=i\mid {\omega }_{<|x|}^M=x]$$

Then, the identity function is a ${\Delta }_{avg}^2$-pseudo-invertible reduction of $(f_{M\left(i\right)},{\mu }_M)$ to $(f_{BSI\left(i\right)},{\mu }_{BSI})$.

Corollary 2

Suppose ${\hat{G}}_{BSI\left(i\right)}$ is a weak ${\Delta }_{ll}^2$-generator for $(f_{BSI\left(i\right)},{\mu }_{BSI})$. Then, $\hat{\Lambda }\left[{\hat{G}}_{BSI\left(i\right)}\right]$ is not only a ${\Delta }_{ll}^2(poly,log)$-optimal predictor scheme for $(f_{BSI\left(i\right)},{\mu }_{BSI})$ but also a ${\Delta }_{avg}^2(poly,log)$-optimal predictor scheme for $(f_{M\left(i\right)},{\mu }_M)$, for any $M$ as above.

Note 1

It is straightforward to extend this approach to predicting functions of the several following bits rather than only the next bit.

Note 2

$M$ is computing ${\omega }^M$ directly rather than recursively (that is, ${\omega }_k^M$ can depend directly on the random coin flips used to generate the previous bits rather than only on the previous bits) which means this approach avoids the problem presented by Taylor. That is, if we construct an agent that uses $\hat{\Lambda }$ to compute expected reward as a function of action based on previous observations, then in Taylor’s example the correct action will be selected (since in that example the reward can be computed in polynomial time and by the reduction and uniqueness theorems $\hat{\Lambda }$ will produce an asymptotically exact prediction).

Appendix

Proof of Proposition 1

Suppose $\hat{G}$ is a $\Delta \left(log\right)$-generator for $(f,\mu )$. Define $\Sigma \subseteq N^2\times \{0,1{\}}^{\ast }$ by

$$\Sigma :=\bigcup _{k,j\in N}(k,j)\times {\hat{G}}_1\left(\{0,1{\}}^{r_G(k,j)}\right)$$

and $F:\Sigma \to [0,1]$ by

$$F^{kj}\left(x\right):=E_{U^{r_G(k,j)}}\left[{\hat{G}}^{kj}\right(y{)}_2\mid {\hat{G}}^{kj}(y{)}_1=x]$$

We have

$$E\left[\right({\hat{G}}_2-f\left({\hat{G}}_1\right){)}^2]=E[({\hat{G}}_2-F({\hat{G}}_1)+F({\hat{G}}_1)-f({\hat{G}}_1\left){)}^2\right]$$

$$E\left[\right({\hat{G}}_2-f\left({\hat{G}}_1\right){)}^2]=E[\left(F\right({\hat{G}}_1)-f({\hat{G}}_1\left){)}^2\right]-2E\left[\right(F\left({\hat{G}}_1\right)-f\left({\hat{G}}_1\right)\left)\right(F\left({\hat{G}}_1\right)-{\hat{G}}_2\left)\right]+E\left[\right(F\left({\hat{G}}_1\right)-{\hat{G}}_2{)}^2]$$

The middle term on the right hand side satisfies

$$E_{U^{r_G}}\left[\right(F\left(\hat{G}\right(y{)}_1)-f(\hat{G}\left(y{)}_1\right)\left)\right(F\left(\hat{G}\right(y{)}_1)-\hat{G}(y{)}_2\left)\right]=E_{U^{r_G}}\left[E_{U^{r_G}}\right[\left(F\right(\hat{G}\left(y{)}_1\right)-f\left(\hat{G}\right(y{)}_1\left)\right)\left(F\right(\hat{G}\left(y{)}_1\right)-\hat{G}\left(y^{\prime }{)}_2\right)\mid \hat{G}(y^{\prime }{)}_1=\hat{G}(y{)}_1\left]\right]$$

$$E_{U^{r_G}}\left[\right(F\left(\hat{G}\right(y{)}_1)-f(\hat{G}\left(y{)}_1\right)\left)\right(F\left(\hat{G}\right(y{)}_1)-\hat{G}(y{)}_2\left)\right]=E_{U^{r_G}}\left[\right(F\left(\hat{G}\right(y{)}_1)-f(\hat{G}\left(y{)}_1\right)\left)E_{U^{r_G}}\right[\left(F\right(\hat{G}\left(y{)}_1\right)-\hat{G}\left(y^{\prime }{)}_2\right)\mid \hat{G}(y^{\prime }{)}_1=\hat{G}(y{)}_1\left]\right]$$

$$E_{U^{r_G}}\left[\right(F\left(\hat{G}\right(y{)}_1)-f(\hat{G}\left(y{)}_1\right)\left)\right(F\left(\hat{G}\right(y{)}_1)-\hat{G}(y{)}_2\left)\right]=E_{U^{r_G}}\left[\right(F\left(\hat{G}\right(y{)}_1)-f(\hat{G}\left(y{)}_1\right)\left)\right(F\left(\hat{G}\right(y{)}_1)-F(\hat{G}\left(y{)}_1\right)\left)\right]$$

$$E_{U^{r_G}}\left[\right(F\left(\hat{G}\right(y{)}_1)-f(\hat{G}\left(y{)}_1\right)\left)\right(F\left(\hat{G}\right(y{)}_1)-\hat{G}(y{)}_2\left)\right]=0$$

We get

$$E\left[\right({\hat{G}}_2-f\left({\hat{G}}_1\right){)}^2]=E[\left(F\right({\hat{G}}_1)-f({\hat{G}}_1\left){)}^2\right]+E\left[\right(F\left({\hat{G}}_1\right)-{\hat{G}}_2{)}^2]$$

$$E\left[\right({\hat{G}}_2-f\left({\hat{G}}_1\right){)}^2]\ge E[\left(F\right({\hat{G}}_1)-f({\hat{G}}_1\left){)}^2\right]$$

$$E\left[\right(F\left({\hat{G}}_1\right)-f\left({\hat{G}}_1\right){)}^2]\in \Delta$$

Proof of Proposition 2

Consider $\delta \in {\Delta }_{sqp,\varphi }^2$. Consider $\psi \in \Phi$, $\psi \le \varphi$. We have

$$E_{{\lambda }_{\psi }^k}\left[\delta \right(k,j\left)\right]=P{r}_{{\lambda }_{\psi }^k}[j<t_{{\psi }^{\frac{1}{2}}}(k\left)\right]E_{{\lambda }_{\psi }^k}\left[\delta \right(k,j)\mid j<t_{{\psi }^{\frac{1}{2}}}(k\left)\right]+P{r}_{{\lambda }_{\psi }^k}[j\ge t_{{\psi }^{\frac{1}{2}}}(k\left)\right]E_{{\lambda }_{\psi }^k}\left[\delta \right(k,j)\mid j\ge t_{{\psi }^{\frac{1}{2}}}(k\left)\right]$$

$$E_{{\lambda }_{\psi }^k}\left[\delta \right(k,j\left)\right]\le \psi \left(k{)}^{-\frac{1}{2}}\right(sup\delta )+\underset{j\ge t_{{\psi }^{\frac{1}{2}}}\left(k\right)}{sup}\delta (k,j)$$

For $k>>0$, ${\psi }^{\frac{1}{2}}\le \varphi$ hence ${sup}_{j\ge t_{{\psi }^{\frac{1}{2}}}\left(k\right)}\delta (k,j)\in {\Delta }_{{\psi }^{\frac{1}{2}}}^1={\Delta }_{\psi }^1$. We conclude that $E_{{\lambda }_{\psi }^k}\left[\delta \right(k,j\left)\right]\in {\Delta }_{\psi }^1$ and therefore $\delta \in {\Delta }_{ll,\varphi }^2$.

Proposition 4

Suppose $\hat{G}$ is a weak $\Delta \left(log\right)$-generator for $(f,\mu )$. Then there is $\delta \in \Delta$ s.t. for any $k,j\in N$ and $g:\{0,1{\}}^{\ast }\to R$ bounded

$$|E_{U^{r_G(k,j)}}\left[g\right({\hat{G}}^{kj}\left(y{)}_1\right)\left({\hat{G}}^{kj}\right(y{)}_2-f\left({\hat{G}}^{kj}\right(y{)}_1\left)\right)]|\le (supg\left)\delta \right(k,j)$$

Proof of Proposition 4

$$E_{U^{r_G(k,j)}}\left[g\right({\hat{G}}^{kj}\left(y{)}_1\right)\left({\hat{G}}^{kj}\right(y{)}_2-f\left({\hat{G}}^{kj}\right(y{)}_1\left)\right)]=E_{U^{r_G(k,j)}\times U^{r_G(k,j)}}[g\left({\hat{G}}^{kj}\right(y{)}_1\left)\right({\hat{G}}^{kj}(y^{\prime }{)}_2-f({\hat{G}}^{kj}\left(y{)}_1\right))\mid {\hat{G}}^{kj}(y^{\prime }{)}_1={\hat{G}}^{kj}\left(y{)}_1\right]$$

$$E_{U^{r_G(k,j)}}\left[g\right({\hat{G}}^{kj}\left(y{)}_1\right)\left({\hat{G}}^{kj}\right(y{)}_2-f\left({\hat{G}}^{kj}\right(y{)}_1\left)\right)]=E_{U^{r_G(k,j)}}[g\left({\hat{G}}^{kj}\right(y{)}_1\left)E_{U^{r_G(k,j)}}\right[{\hat{G}}^{kj}(y^{\prime }{)}_2-f({\hat{G}}^{kj}\left(y{)}_1\right)\mid {\hat{G}}^{kj}(y^{\prime }{)}_1={\hat{G}}^{kj}(y{)}_1\left]\right]$$

$$E_{U^{r_G(k,j)}}\left[g\right({\hat{G}}^{kj}\left(y{)}_1\right)\left({\hat{G}}^{kj}\right(y{)}_2-f\left({\hat{G}}^{kj}\right(y{)}_1\left)\right)]=E_{U^{r_G(k,j)}}[g\left({\hat{G}}^{kj}\right(y{)}_1\left)\right(E_{U^{r_G(k,j)}}\left[{\hat{G}}^{kj}\right(y^{\prime }{)}_2\mid {\hat{G}}^{kj}(y^{\prime }{)}_1={\hat{G}}^{kj}(y{)}_1\left]\right]-f\left({\hat{G}}^{kj}\right(y{)}_1\left)\right)]$$

Property (ii) of $\hat{G}$ implies the result.

Proposition 5

Suppose $\hat{G}$ is a weak $\Delta \left(log\right)$-generator for $(f,\mu )$. Then there is $\delta \in \Delta$ s.t. for any $k,j\in N$, finite set $Z$, $\nu$ a probability measure on $Z$ and $h:\{0,1{\}}^{\ast }\times Z\to [0,1]$

$$|E_{U^{r_G(k,j)}\times \nu }\left[\right(h\left({\hat{G}}^{kj}\right(y{)}_1,z)-{\hat{G}}^{kj}(y{)}_2{)}^2]-E_{{\mu }^k\times \nu }[\left(h\right(x,z)-f(x\left){)}^2\right]-E_{U^{r_G(k,j)}}\left[\right({\hat{G}}^{kj}(y{)}_2-f({\hat{G}}^{kj}\left(y{)}_1\right){)}^2]|\le \delta (k,j)$$

Proof of Proposition 5

$$E_{U^{r_G(k,j)}\times \nu }\left[\right(h\left({\hat{G}}^{kj}\right(y{)}_1,z)-{\hat{G}}^{kj}(y{)}_2{)}^2]=E_{U^{r_G(k,j)}\times \nu }[\left(h\right({\hat{G}}^{kj}(y{)}_1,z)-f\left({\hat{G}}^{kj}\right(y{)}_1)+f({\hat{G}}^{kj}\left(y{)}_1\right)-{\hat{G}}^{kj}\left(y{)}_2{)}^2\right]$$

$$E\left[\right(h\left({\hat{G}}_1^{kj}\right)-{\hat{G}}_2^{kj}{)}^2]=E[\left(h\right({\hat{G}}_1^{kj})-f({\hat{G}}_1^{kj}\left){)}^2\right]+E\left[\right({\hat{G}}_2^{kj}-f\left({\hat{G}}_1^{kj}\right){)}^2]-2E[\left(h\right({\hat{G}}_1^{kj})-f({\hat{G}}_1^{kj}\left)\right)({\hat{G}}_2^{kj}-f({\hat{G}}_1^{kj}\left)\right)]$$

Since ${\hat{G}}_1$ is a $\Delta \left(log\right)$-sampler of $\mu$, the first term on the right hand side satisfies

$$|E_{U^{r_G(k,j)}\times \nu }\left[\right(h\left({\hat{G}}_1^{kj}\right)-f\left({\hat{G}}_1^{kj}\right){)}^2]-E_{{\mu }^k\times \nu }[\left(h\right(x)-f(x{)}^2]|\le {\delta }_1(k,j)$$

where ${\delta }_1\in \Delta$ doesn’t depend on $h$. Applying Proposition 4 to the last term on the right hand hands completes the desired result.

Proposition 6

Given $\varphi \in \Phi$ and $\delta \in {\Delta }_{sqp,\varphi }^2$, define ${\delta }_{mon}(k,j):={sup}_{m\ge j}\delta (k,m)$. Then, ${\delta }_{mon}\in {\Delta }_{sqp,\varphi }^2$.

Proof of Proposition 6

Consider $\psi \in \Phi$, $\psi \le \varphi$.

$$\underset{j\ge t_{\psi }\left(k\right)}{sup}{\delta }_{mon}(k,j)=\underset{j\ge t_{\psi }\left(k\right)}{sup}\underset{m\ge j}{sup}\delta (k,m)$$

$$\underset{j\ge t_{\psi }\left(k\right)}{sup}{\delta }_{mon}(k,j)=\underset{j\ge t_{\psi }\left(k\right)}{sup}\delta (k,j)$$

$$\underset{j\ge t_{\psi }\left(k\right)}{sup}{\delta }_{mon}(k,j)\in {\Delta }_{\psi }^1$$

Proof of Theorem 1

Consider $\hat{P}=(P,r,a)$ a $(poly,log)$-predictor scheme. Choose $p:N^2\to N$ a polynomial satisfying $p(k,j)\ge j$ s.t. evaluating $\Lambda [G{]}^{k,p(k,j)}$ involves running ${\hat{P}}^{kj}$ until it halts “naturally” (such $p$ exists because $\hat{P}$ runs in at most polynomial time and has at most logarithmic advice). Given $i,j\in N$, consider the execution of $\Lambda [G{]}^{k,p(k,j)+i}$. The standard deviation of $ϵ\left({\hat{P}}^{kj}\right)$ with respect to the internal coin tosses of $\Lambda$ is at most $\left(p\right(k,j)+i{)}^{-1}$. According to Proposition 5, the expectation value is $E\left[\right({\hat{P}}^{kj}-f{)}^2]+E[({\hat{G}}_2^{k,p(k,j)+i}-f({\hat{G}}_1^{k,p(k,j)+i}\left){)}^2\right]+{\gamma }_P(k,p(k,j)+i)$ where $|{\gamma }_P|\le \delta$ for $\delta \in {\Delta }_{sqp,\varphi }^2$ that doesn’t depend on $P$. Thanks to Proposition 6 we can assume without loss of generality that $\delta$ is non-increasing in the second argument, and in particular $\delta (k,p(k,j)+i)\le \delta (k,j)$. Denote ${\alpha }^{kj}:=E\left[\right({\hat{G}}_2^{k,p(k,j)+i}-f\left({\hat{G}}_1^{k,p(k,j)+i}\right){)}^2]$. By Chebyshev’s inequality,

$$Pr\left[ϵ\right({\hat{P}}^{kj})\ge E[({\hat{P}}^{kj}-f{)}^2]+{\alpha }^{kj}+\delta (k,j)+\left(p\right(k,j)+i{)}^{-\frac{1}{2}}]\le \left(p\right(k,j)+i{)}^{-1}$$

Hence

$$Pr\left[ϵ\right(Q^{\ast })\ge E[({\hat{P}}^{kj}-f{)}^2]+{\alpha }^{kj}+\delta (k,j)+\left(p\right(k,j)+i{)}^{-\frac{1}{2}}]\le \left(p\right(k,j)+i{)}^{-1}$$

The standard deviation of $ϵ\left(Q\right)$ for any $Q$ is also at most $\left(p\right(k,j)+i{)}^{-1}$. The expectation value is $E\left[\right(e{v}^{p(k,j)+i}\left(Q\right)-f{)}^2]+{\alpha }^{kj}+{\gamma }_Q$ where $|{\gamma }_Q|\le \delta (k,j)$. Therefore

$$Pr[\exists Q<p(k,j)+i:ϵ(Q)\le E[\left(e{v}^{p(k,j)+i}\right(Q)-f{)}^2]+{\alpha }^{kj}-\delta (k,j)-\left(p\right(k,j)+i{)}^{-\frac{1}{4}}]\le \left(p\right(k,j)+i)\left(p\right(k,j)+i{)}^{-\frac{3}{2}}=(p(k,j)+i{)}^{-\frac{1}{2}}$$

The extra $p(k,j)+i$ factor comes from summing probabilities over $p(k,j)+i$ programs. Combining we get

$$Pr\left[E\right[\left(e{v}^{p(k,j)+i}\right(Q^{\ast })-f{)}^2]\ge E\left[\right({\hat{P}}^{kj}-f{)}^2]+2\delta (k,j)+(p(k,j)+i{)}^{-\frac{1}{2}}+\left(p\right(k,j)+i{)}^{-\frac{1}{4}}]\le \left(p\right(k,j)+i{)}^{-1}+(p(k,j)+i{)}^{-\frac{1}{2}}$$

$$E\left[\right(\Lambda [G{]}^{k,p(k,j)+i}-f{)}^2]\le E\left[\right({\hat{P}}^{kj}-f{)}^2]+2\delta (k,j)+(p(k,j)+i{)}^{-1}+2\left(p\right(k,j)+i{)}^{-\frac{1}{2}}+(p(k,j)+i{)}^{-\frac{1}{4}}$$

$$E\left[\right(\Lambda [G{]}^{k,p(k,j)+i}-f{)}^2]\le E\left[\right({\hat{P}}^{kj}-f{)}^2]+2\delta (k,j)+p(k,j{)}^{-1}+2p(k,j{)}^{-\frac{1}{2}}+p(k,j{)}^{-\frac{1}{4}}$$

Using Proposition 2 and the Lemma about ${\Delta }_{ll,\varphi }^2$, we get the desired result.

Proof of Theorem 2

$$E_{U^{r_G(k,j)}}\left[\right({\hat{G}}_{\tau }(y{)}_2-(\tau \circ f\left)\right({\hat{G}}_{\tau }\left(y{)}_1\right){)}^2]=E_{U^{r_G(k,j)}}[\left(\tau \right(\hat{G}\left(y{)}_2\right)-\tau \left(f\right(\hat{G}\left(y{)}_1\right)\left){)}^2\right]$$

Since $\tau$ is $\alpha$-Hoelder continuous, there is a constant $c>0$ which doesn’t depend on $k,j$ s.t.

$$E_{U^{r_G(k,j)}}\left[\right({\hat{G}}_{\tau }(y{)}_2-(\tau \circ f\left)\right({\hat{G}}_{\tau }\left(y{)}_1\right){)}^2]\le c{E}_{U^{r_G(k,j)}}[\left(\hat{G}\right(y{)}_2-f\left(\hat{G}\right(y{)}_1\left){)}^{2\alpha }\right]$$

$$E_{U^{r_G(k,j)}}\left[\right({\hat{G}}_{\tau }(y{)}_2-(\tau \circ f\left)\right({\hat{G}}_{\tau }\left(y{)}_1\right){)}^2]\le c{E}_{U^{r_G(k,j)}}[\left(\hat{G}\right(y{)}_2-f\left(\hat{G}\right(y{)}_1){)}^2{]}^{\alpha }$$

$$E_{U^{r_G(k,j)}}\left[\right({\hat{G}}_{\tau }(y{)}_2-(\tau \circ f\left)\right({\hat{G}}_{\tau }\left(y{)}_1\right){)}^2]\in \Delta$$

Proposition 7

$$min(\frac{\log \log (k+3)}{\log \log (j+3)},1)\in {\Delta }_{sqp}^2$$

Proof of Proposition 7

Consider $\varphi \in \Phi$. We have

$$\underset{j\ge t_{\varphi }\left(k\right)}{sup}min(\frac{\log \log (k+3)}{\log \log (j+3)},1)=min(\frac{\log \log (k+3)}{\log \log \left(t_{\varphi }\right(k)+3)},1)$$

Choosing any $ϵ\in (0,1)$ we get

$$\underset{k\to \infty }{lim}\varphi (k{)}^{ϵ}\underset{j\ge t_{\varphi }\left(k\right)}{sup}min(\frac{\log \log (k+3)}{\log \log (j+3)},1)=\underset{k\to \infty }{lim}\varphi (k{)}^{ϵ-1}$$

$$\underset{k\to \infty }{lim}\varphi (k{)}^{ϵ}\underset{j\ge t_{\varphi }\left(k\right)}{sup}min(\frac{\log \log (k+3)}{\log \log (j+3)},1)=0$$

Proof of Proposition 3

Given $k,j\in N$, define ${\sigma }^{kj}$ to be the probability distribution on $N$ given by ${\sigma }^{kj}:={\sigma }^k\mid n\le max(k,j)$. We describe the execution of the weak generator ${\hat{G}}_{BSI\left(i\right)}^{kj}$.

$n$ is sampled from ${\sigma }^{kj}$ (more precisely from a probability distribution that differs from ${\sigma }^{kj}$ by a rounding error of $2^{-j}\in {\Delta }_{sqp}^2$). $y,z$ are sampled from $U^n$. $x:=e{v}^n(y,z)$ is computed. If $|x|<k$, $(\perp ,0)$ is produced. If $|x|>k$ and $x_k=i$, $(x_{<k},1)$ is produced. Otherwise, $(x_{<k},0)$ is produced.

It is easy to see ${\hat{G}}_{BSI\left(i\right)}$ generates $(f_{BSI\left(i\right)},{\mu }_{BSI})$ up to an error of order $P{r}_{{\sigma }^k}[n>max(k,j\left)\right]<min(\frac{\log \log (k+3)}{\log \log (j+3)},1)$. By Proposition 7, it is therefore a weak ${\Delta }_{sqp}^2$-generator for $(f_{BSI\left(i\right)},{\mu }_{BSI})$.