Predictor schemes with logarithmic advice

[Vanessa Kosoy]

We introduce a variant of optimal predictor schemes where optimality holds within the space of random algorithms with logarithmic advice. These objects are also guaranteed to exist for the error space ${\Delta }_{avg}^2$. We introduce the class of generatable problems and construct a uniform universal predictor scheme for this class which is optimal in the new sense with respect to the ${\Delta }_{avg}^2$ error space. This is achieved by a construction similar to Levin’s universal search.

Results

New notation

Given $n\in N$, $e{v}_n:N\times {\{0,1{\}}^{\ast }}^{n+1}\stackrel{alg}{\to }\{0,1{\}}^{\ast }$ is the following algorithm. When $e{v}_n^k(Q,x_1\dots x_n)$ is computed, $Q$ is interpreted as a program and $Q(x_1\dots x_n)$ is executed for time $k$. The resulting output is produced.

The notation $e{v}^k(Q,x_1\dots x_n)$ means $e{v}_n^k(Q,x_1\dots x_n)$.

$\beta :\{0,1{\}}^{\ast }\to [0,1]$ is the mapping from a binary expansion to the corresponding real number.

Given $\mu$ a word ensemble, $X$ a set, $Q:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }X$, $T_Q^{\mu }(k,s)$ stands for the maximal runtime of $Q(x,y)$ for $x\in \mathrm{supp}{\mu }^k$, $y\in \{0,1{\}}^s$.

---

Previous posts focused on prediction of distributional decision problems, which is the “computational uncertainty” analogue of probability. Here, we use the broader concept of predicting distributional estimation problems (functions), which is analogous to expectation value.

Definition 1

A distributional estimation problem is a pair $(f,\mu )$ where $f:\{0,1{\}}^{\ast }\to [0,1]$ is an arbitrary function (even irrational values are allowed) and $\mu$ is a word ensemble.

Definition 2

Given an appropriate set $X$, consider $P:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }X$, $r:N^2\to N$ polynomial and $a:N^2\to \{0,1{\}}^{\ast }$. The triple $(P,r,a)$ is called an $X$-valued $(poly,log)$-bischeme when

(i) The runtime of $P(k,j,x,y,z)$ is bounded by $p(k,j)$ with $p$ polynomial.

(ii) $|a(k,j)|\le c_1+c_2\log (k+1)+c_3\log (j+1)$ for some $c_1,c_2,c_3\in N$.

A $[0,1]$-valued $(poly,log)$-bischeme will also be called a $(poly,log)$-predictor scheme.

---

We think of $P$ as a random algorithm where the second word parameter represents its internal coin tosses. The third word parameter represents the advice and we usually substitute $a$ there.

We will use the notations $P^{kj}(x,y,z):=P(k,j,x,y,z)$, $a^{kj}:=a(k,j)$.

Definition 3

Fix $\Delta$ an error space of rank 2 and $(f,\mu )$ a distributional estimation problem. Consider $(P,r,a)$ a $(poly,log)$-predictor scheme.$(P,r,a)$ is called a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$ when for any $(poly,log)$-predictor scheme $(Q,s,b)$, there is $\delta \in \Delta$ s.t.

$$E_{{\mu }^k\times U^{r(k,j)}}\left[\right(P^{kj}(x,y,a^{kj})-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{s(k,j)}}[\left(Q^{kj}\right(x,y,b^{kj})-f(x\left){)}^2\right]+\delta (k,j)$$

Note 1

The notation $(poly,log)$ is meant to remind us that we allow a polynomial quantity of random bits $r(k,j)$ and a logarithmic quantity of advice $|a^{kj}|$. In fact, the definitions and some of the theorems can be generalized to other quantities of random and advice (see also Note B.1). Thus, predictor schemes from previous posts are $(poly,poly)$-predictor schemes, $(poly,O(1\left)\right)$-predictor schemes are limited to O(1) advice, $(log,0)$-predictor schemes use a logarithmic number of random bits and no advice and so on. As usual in complexity theory, it is redundant to consider more advice than random since advice is strictly more powerful.

---

$\Delta (poly,log)$-optimal predictor scheme satisfy properties analogical to $\Delta$-optimal predictor schemes. These properties are listed in Appendix A. The proofs of Theorem A.1 and A.4 are given in Appendix B. The other proofs are straightforward adaptions of corresponding proofs with polynomial advice.

We also have the following existence result:

Theorem 1

Consider $(f,\mu )$ a distributional estimation problem. Define ${\rm Y}:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }[0,1]$ by

$${{\rm Y}}^{kj}(x,y,Q):=\beta \left(e{v}^j\right(Q,x,y\left)\right)$$

Define ${\upsilon }_{f,\mu }:N^2\to \{0,1{\}}^{\ast }$ by

$${\upsilon }_{f,\mu }^{kj}:=\underset{|Q|\le \log j}{argmin}{E}_{{\mu }^k\times U^j}\left[\right({{\rm Y}}^{kj}(x,y,Q)-f\left(x\right){)}^2]$$

Then, $({\rm Y},j,{\upsilon }_{f,\mu })$ is a ${\Delta }_{avg}^2(poly,log)$-optimal predictor scheme for $(f,\mu )$.

Note 2

Consider a distributional decision problem $(D,\mu )$. Assume $(D,\mu )$ admits $n\in N$, $A:N\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }\{0,1\}$, $a:N\to \{0,1{\}}^{\ast }$ and a function $r:N\to N$ s.t.

(i) $A(k,x,y,z)$ runs in quasi-polynomial time ($O\left(2^{{\log }^{n}k}\right)$).

(ii) $$|a\left(k\right)|=O\left({\log }^{n}k\right)$$

(iii) $$\underset{k\to \infty }{lim}P{r}_{{\mu }^k\times U^{r\left(k\right)}}\left[A\right(k,x,y,a\left(k\right))\ne {\chi }_D(x\left)\right]=0$$

Then it is easy to see we can construct a $(poly,log)$-predictor scheme $P_A$ taking values in $\{0,1\}$ s.t. $E\left[\right(P_A-f{)}^2]\in {\Delta }_{avg}^2$. The implication doesn’t work for larger sizes of time or advice. Therefore, the uncertainty represented by ${\Delta }_{avg}^2(poly,log)$-optimal predictor schemes is associated with the resource gap between quasi-polynomial time plus advice $O\left({\log }^{n}k\right)$ and the resources needed to (heuristically) solve the problem in question.

---

The proof of Theorem 1 is given in Appendix C: it is a straightforward adaptation of the corresponding proof for polynomial advice. Evidently, the above scheme is non-uniform. We will now describe a class of problems which admits uniform ${\Delta }_{avg}^2(poly,log)$-optimal predictor schemes.

Definition 4

Consider ${\Delta }^1$ an error space of rank 1. A word ensemble $\mu$ is called ${\Delta }^1\left(log\right)$-sampleable when there is $S:N\times {\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1{\}}^{\ast }$ that runs in polynomial time in the 1st argument, $a^S:N\to \{0,1{\}}^{\ast }$ of logarithmic size and $r^S:N\to N$ a polynomial such that

$$\sum _{x\in \{0,1{\}}^{\ast }}|{\mu }^k\left(x\right)-P{r}_{U^{r^S\left(k\right)}}\left[S^k\right(y,a^S\left(k\right))=x]|\in {\Delta }^1$$

$(S,r^S,a^S)$ is called a ${\Delta }^1\left(log\right)$-sampler for $\mu$.

Definition 5

Consider ${\Delta }^1$ an error space of rank 1. A distributional estimation problem $(f,\mu )$ is called ${\Delta }^1\left(log\right)$-generatable when there are $S:N\times {\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1{\}}^{\ast }$ and $F:N\times {\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }[0,1]$ that run in polynomial time in the 1st argument, $a^S:N\to \{0,1{\}}^{\ast }$ of logarithmic size and $r^S:N\to N$ a polynomial such that

(i) $(S,r^S,a^S)$ is a ${\Delta }^1\left(log\right)$-sampler for $\mu$.

(ii) $$E_{U^{r^S\left(k\right)}}\left[\right(F^k(y,a^S(k\left)\right)-f\left(S^k\right(y,a^S\left(k\right)\left)\right){)}^2]\in {\Delta }^1$$

$(S,F,r^S,a^S)$ is called a ${\Delta }^1\left(log\right)$-generator for $(f,\mu )$.

When $a^S$ is the empty string, $(S,F,r^S)$ is called a ${\Delta }^1\left(0\right)$-generator for $(f,\mu )$. Such $(f,\mu )$ is called ${\Delta }^1\left(0\right)$-generatable.

Note 3

The class of ${\Delta }^1\left(0\right)$-generatable problems can be regarded as an average-case analogue of $NP\cap coNP$. If $f$ is a decision problem (i.e. its range is $\{0,1\}$), words $y\in \{0,1{\}}^{r^S\left(k\right)}$ s.t. $S^k\left(y\right)=x$, $F^k\left(y\right)=1$ can be regarded as “proofs” of $f\left(x\right)=1$ and words $y\in \{0,1{\}}^{r^S\left(k\right)}$ s.t. $S^k\left(y\right)=x$, $F^k\left(y\right)=0$ can be regarded as “proofs” of $f\left(x\right)=0$.

Theorem 2

There is an oracle machine $\Lambda$ that accepts an oracle of signature $SF:N\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }\times [0,1]$ and a polynomial $r:N\to N$ where the allowed oracle calls are $S{F}^k\left(x\right)$ for $|x|=r\left(k\right)$ and computes a function of signature $N^2\times {\{0,1{\}}^{\ast }}^2\to [0,1]$ s.t. for any $(f,\mu )$ a distributional estimation problem and $G:=(S,F,r^S,a^S)$ a corresponding ${\Delta }_0^1\left(log\right)$-generator, $\Lambda \left[G\right]$ is a ${\Delta }_{avg}^2(poly,log)$-optimal predictor scheme for $(f,\mu )$.

---

In particular if $(f,\mu )$ is ${\Delta }_0^1\left(0\right)$-generatable, we get a uniform ${\Delta }_{avg}^2(poly,log)$-optimal predictor scheme.

The following is the description of $\Lambda$. Consider $SF:N\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }\times [0,1]$ and a polynomial $r:N\to N$. We describe the computation of $\Lambda [SF,r{]}^{kj}(x)$ where the extra argument of $\Lambda$ is regarded as internal coin tosses.

We loop over the first $j$ words in lexicographic order. Each word is interpreted as a program $Q:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }[0,1]$. We loop over $jk$ “test runs”. At test run $i$, we generate $(x_i\in \{0,1{\}}^{\ast },t_i\in [0,1\left]\right)$ by evaluating $S{F}^k\left(y_i\right)$ for $y_i$ sampled from $U^{r\left(k\right)}$. 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.

The proof that this construction is ${\Delta }_{avg}^2(poly,log)$-optimal is given in Appendix C.

Appendix A

Fix $\Delta$ an error space of rank 2.

Theorem A.1

Suppose there is a polynomial $h:N^2\to N$ s.t. $h^{-1}\in \Delta$. Consider $(f,\mu )$ a distributional estimation problem and $(P,r,a)$ a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$. Suppose $\{p_{kj}\in [0,1]{\}}_{k,j\in N}$, $\{q_{kj}\in [0,1]{\}}_{k,j\in N}$ are s.t.

$$\exists ϵ>0\forall k,j:({\mu }^k\times U^{r(k,j)})\left\{\right(x,y)\in {\{0,1{\}}^{\ast }}^2\mid p_{kj}\le P^{kj}(x,y,a^{kj})\le q_{kj}\}\ge ϵ$$

Define

$${\varphi }_{kj}:=E_{{\mu }^k\times U^{r(k,j)}}\left[f\right(x)-P^{kj}(x,y,a^{kj})\mid p_{kj}\le P^{kj}(x,y,a^{kj})\le q_{kj}]$$

Assume that either $p_{kj},q_{kj}$ have a number of digits logarithmically bounded in $k,j$ or $P^{kj}$ produces outputs with a number of digits logarithmically bounded in $k,j$ (by Theorem A.7 if any $\Delta (poly,log)$-optimal predictor scheme exists for $(f,\mu )$ then a $\Delta (poly,log)$-optimal predictor scheme with this property exists as well). Then, $|\varphi |\in \Delta$.

Theorem A.2

Consider $\mu$ a word ensemble and $f_1,f_2:\{0,1{\}}^{\ast }\to [0,1]$ s.t. $f_1+f_2\le 1$. Suppose $(P_1,r_1,a_1)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_1,\mu )$ and $(P_2,r_2,a_2)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_2,\mu )$. Define $P:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }[0,1]$ by $P^{kj}(x,y_1{y}_2,(z_1,z_2\left)\right):=\eta \left(P_1^{kj}\right(x,y_1,z_1)+P_2^{kj}(x,y_2,z_2\left)\right)$ for $|y_i|=r_i(k,j)$. Then, $(P,r_1+r_2,a_1{a}_2)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_1+f_2,\mu )$.

Theorem A.3

Consider $\mu$ a word ensemble and $f_1,f_2:\{0,1{\}}^{\ast }\to [0,1]$ s.t. $f_1+f_2\le 1$. Suppose $(P_1,r_1,a_1)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_1,\mu )$ and $(P,r_2,a_2)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_1+f_2,\mu )$. Define $P_2:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }[0,1]$ by $P_2^{kj}(x,y_1{y}_2,(z_1,z_2\left)\right):=\eta \left(P^{kj}\right(x,y_1,z_1)-P_1^{kj}(x,y_2,z_2\left)\right)$ for $|y_i|=r_i(k,j)$. Then, $(P_2,r_1+r_2,a_1{a}_2)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_2,\mu )$.

Theorem A.4

Fix ${\Delta }^1$ an error space of rank 1 s.t. given ${\delta }^1\in {\Delta }^1$, the function $\delta (k,j):={\delta }^1\left(k\right)$ lies in $\Delta$. Consider $(f_1,{\mu }_1)$, $(f_2,{\mu }_2)$ distributional estimation problems with respective $\Delta (poly,log)$-optimal predictor schemes $(P_1,r_1,a_1)$ and $(P_2,r_2,a_2)$. Assume ${\mu }_1$ is ${\Delta }^1\left(log\right)$-sampleable and $(f_2,{\mu }_2)$ is ${\Delta }^1\left(log\right)$-generatable. Define $f_1\times f_2:\{0,1{\}}^{\ast }\to [0,1]$ by $(f_1\times f_2)(x_1,x_2)=f_1\left(x_1\right)f_2\left(x_2\right)$ and $(f_1\times f_2)\left(y\right)=0$ for $y$ not of this form. Define $P:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }[0,1]$ by $P^{kj}\left(\right(x_1,x_2),y_1{y}_2,(z_1,z_2\left)\right):=P_1^{kj}(x_1,y_1,z_1)P_2^{kj}(x_2,y_2,z_2)$ for $|y_i|=r_i(k,j)$. Then, $(P,r_1+r_2,(a_1,a_2\left)\right)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f_1\times f_2,{\mu }_1\times {\mu }_2)$.

Theorem A.5

Consider $f:\{0,1{\}}^{\ast }\to [0,1]$, $D\subseteq \{0,1{\}}^{\ast }$ and $\mu$ a word ensemble. Assume $(P_D,r_D,a_D)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(D,\mu )$ and $(P_{f\mid D},r_{f\mid D},a_{f\mid D})$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu \mid D)$. Define $P:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }[0,1]$ by $P^{kj}(x,y_1{y}_2,(z_1,z_2\left)\right):=P_D^{kj}(x,y_1,z_1)P_{f\mid D}^{kj}(x,y_2,z_2)$ for $|y_i|=r_i(k,j)$. Then $(P,r_D+r_{f\mid D},(a_D,a_{f\mid D}\left)\right)$ is a $\Delta (poly,log)$-optimal predictor scheme for $({\chi }_{D}f,\mu )$.

Theorem A.6

Fix $h$ a polynomial s.t. $2^{-h}\in \Delta$. Consider $f:\{0,1{\}}^{\ast }\to [0,1]$, $D\subseteq \{0,1{\}}^{\ast }$ and $\mu$ a word ensemble. Assume $\exists ϵ>0\forall k:{\mu }^k\left(D\right)\ge ϵ$. Assume $(P_D,r_D,a_D)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(D,\mu )$ and $(P_{{\chi }_{D}f},r_{{\chi }_{D}f},a_{{\chi }_{D}f})$ is a $\Delta (poly,log)$-optimal predictor scheme for $({\chi }_{D}f,\mu )$. Define $P_{f\mid D}:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }[0,1]$ by

$$P_{f\mid D}^{kj}(x,y_1{y}_2,(z_1,z_2\left)\right):=\{\begin{array}{cc}1& \text{if}{P}_D^{kj}(x,y_2,z_2)=0\\ \eta \left(\frac{P_{{\chi }_{D}f}^{kj}(x,y_1,z_1)}{P_D^{kj}(x,y_2,z_2)}\right)& \text{rounded to}h(k,j)\text{binary places if}{P}_D^{kj}(x,y_2,z_2)>0\end{array}$$

Then, $(P_{f\mid D},r_D+r_{{\chi }_{D}f},(a_{{\chi }_{D}f},a_D\left)\right)$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu \mid D)$.

Definition A.1

Consider $\mu$ a word ensemble and ${\hat{Q}}_1:=(Q_1,s_1,b_1)$, ${\hat{Q}}_2:=(Q_2,s_2,b_2)$ $(poly,log)$-predictor schemes. We say ${\hat{Q}}_1$ is $\Delta$-similar to ${\hat{Q}}_2$ relative to $\mu$ (denoted ${\hat{Q}}_1\underset{\Delta }{\stackrel{\mu }{\simeq }}{\hat{Q}}_2$) when $E_{{\mu }^k\times U^{s_1(k,j)}\times U^{s_2(k,j)}}\left[\right(Q_1^{kj}(x,y_1,b_1^{kj})-Q_2^{kj}(x,y_2,b_2^{kj}){)}^2]\in \Delta$.

Theorem A.7

Consider $(f,\mu )$ a distributional estimation problem, $\hat{P}$ a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$ and $\hat{Q}$ a $(poly,log)$-predictor scheme. Then, $\hat{Q}$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$ if and only if $\hat{P}\underset{\Delta }{\stackrel{\mu }{\simeq }}\hat{Q}$.

Note A.1

$\Delta$-similarity is not an equivalence relation on the set of arbitrary $(poly,log)$-predictor schemes. However, it is an equivalence relation on the set of $(poly,log)$-predictor schemes $\hat{Q}$ satisfying $\hat{Q}\underset{\Delta }{\stackrel{\mu }{\simeq }}\hat{Q}$ (i.e. the $\mu$-expectation value of the intrinsic variance of $\hat{Q}$ is in $\Delta$). In particular, for any $f:\{0,1{\}}^{\ast }\to [0,1]$ any $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$ has this property.

Appendix B

Definition B.1

Given $n\in N$, a function $\delta :N^{2+n}\to R^{\ge 0}$ is called $\Delta$-moderate when

(i) $\delta$ is non-decreasing in arguments $3$ to $2+n$.

(ii) For any collection of polynomials $\{p_i:N^2\to N{\}}_{i<n}$, $\delta (k,j,p_0(k,j)\dots p_{n-1}(k,j\left)\right)\in \Delta$

Lemma B.1

Fix $(f,\mu )$ a distributional estimation problem and $\hat{P}:=(P,r,a)$ a $(poly,log)$-predictor scheme. Then, $\hat{P}$ is $\Delta (poly,log)$-optimal iff there is a $\Delta$-moderate function $\delta :N^4\to [0,1]$ s.t. for any $k,j,s\in N$, $Q:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }[0,1]$

$$E_{{\mu }^k\times U^{r(k,j)}}\left[\right(P^{kj}(x,y,a^{kj})-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^s}[\left(Q\right(x,y)-f(x\left){)}^2\right]+\delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})$$

Proof of Lemma B.1

Define

$$\delta (k,j,t,u):=\underset{\begin{array}{c}{T}_Q^{\mu }(k,s)\le t\\ |Q|\le \log u\end{array}}{max}\left\{E_{{\mu }^k\times U^{r(k,j)}}\right[\left(P^{kj}\right(x,y,a^{kj})-f(x\left){)}^2\right]-E_{{\mu }^k\times U^s}\left[\right(Q(x,y)-f\left(x\right){)}^2\left]\right\}$$

Note B.1

Lemma B.1 shows that the error bound for $\Delta (poly,log)$-optimal predictor scheme is in some sense uniform with respect to $Q$. This doesn’t generalize to e.g. $\Delta (poly,O(1\left)\right)$-optimal predictor schemes. The latter still admit a weaker version of Theorems A.1 and direct analogues of Theorems A.2, A.3, A.5, A.6 and A.7. Theorem A.4 doesn’t seem to generalize.

Lemma B.2

Suppose there is a polynomial $h:N^2\to N$ s.t. $h^{-1}\in \Delta$. Fix $(f,\mu )$ a distributional estimation problem and $(P,r,a)$ a corresponding $\Delta (poly,log)$-optimal predictor scheme. Consider $(Q,s,b)$ a $(poly,log)$-predictor scheme, $M>0$, $w:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }Q\cap [0,M]$ with runtime bounded by a polynomial in the first two arguments, and $u:N^2\to \{0,1{\}}^{\ast }$ of logarithmic size. Then there is $\delta \in \Delta$ s.t.

$$E_{{\mu }^k\times U^{max\left(r\right(k,j),s(k,j\left)\right)}}\left[w^{kj}\right(x,y,u^{kj}\left)\right(P^{kj}(x,y_{\le r(k,j)},a^{kj})-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{max\left(r\right(k,j),s(k,j\left)\right)}}[w^{kj}(x,y,u^{kj})\left(Q^{kj}\right(x,y_{\le s(k,j)},b^{kj})-f(x\left){)}^2\right]+\delta (k,j)$$

Proof of Lemma B.2

Given $t\in [0,M]$, define ${\alpha }^{kj}\left(t\right)$ to be $t$ rounded within error $h(k,j{)}^{-1}$. Thus, the number of digits in ${\alpha }^{kj}\left(t\right)$ is logarithmic in $k$ and $j$. Denote $q(k,j):=max\left(r\right(k,j),s(k,j\left)\right)$. Consider ${\hat{Q}}_t:=(Q_t,r+s,b_t)$ the $(poly,log)$-predictor scheme defined by

$$Q_t^{kj}(x,y,b_t^{kj}):=\{\begin{array}{cc}{Q}^{kj}(x,y_{\le s(k,j)},b^{kj})& \text{if}{w}^{kj}(x,y_{\le q(k,j)},u^{kj})\ge {\alpha }^{kj}\left(t\right)\\ P^{kj}(x,y_{\le r(k,j)},a^{kj})& \text{if}{w}^{kj}(x,y_{\le q(k,j)},u^{kj})<{\alpha }^{kj}\left(t\right)\end{array}$$

${\hat{Q}}_t$ satisfies bounds on runtime and advice size uniform in $t$. Therefore, Lemma B.1 implies that there is $\delta \in \Delta$ s.t.

$$E_{{\mu }^k\times U^{r(k,j)}}\left[\right(P^{kj}(x,y,a^{kj})-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{r(k,j)+s(k,j)}}[\left(Q_t^{kj}\right(x,y,b^{kj})-f(x\left){)}^2\right]+\delta (k,j)$$

$$E_{{\mu }^k\times U^{r(k,j)+s(k,j)}}\left[\right(P^{kj}(x,y_{\le r(k,j)},a^{kj})-f\left(x\right){)}^2-\left(Q_t^{kj}\right(x,y,b^{kj})-f(x\left){)}^2\right]\le \delta (k,j)$$

$$E_{{\mu }^k\times U^{q(k,j)}}\left[\theta \right(w^{kj}(x,y,u^{kj})-{\alpha }^{kj}\left(t\right)\left)\right(\left(P^{kj}\right(x,y_{\le r(k,j)},a^{kj})-f(x){)}^2-(Q^{kj}(x,y_{\le s(k,j)},b^{kj})-f\left(x\right){)}^2\left)\right]\le \delta (k,j)$$

$$E_{{\mu }^k\times U^{q(k,j)}}\left[{\int }_0^M\theta \right(w^{kj}(x,y,z,u^{kj})-{\alpha }^{kj}\left(t\right)\left)dt\right(\left(P^{kj}\right(x,y_{\le r(k,j)},a^{kj})-f(x){)}^2-(Q^{kj}(x,y_{\le s(k,j)},b^{kj})-f\left(x\right){)}^2\left)\right]\le M\delta (k,j)$$

$$E_{{\mu }^k\times U^{q(k,j)}}\left[w^{kj}\right(x,y,z,u^{kj}\left)\right(\left(P^{kj}\right(x,y_{\le r(k,j)},a^{kj})-f(x){)}^2-(Q^{kj}(x,y_{\le s(k,j)},b^{kj})-f\left(x\right){)}^2\left)\right]\le M\delta (k,j)+h(k,j{)}^{-1}$$

---

In the following proofs we will use shorthand notations that omit most of the symbols that are clear for the context. That is, we will use $P$ to mean $P^{kj}(x,y,a^{kj})$, $f$ to mean $f\left(x\right)$, $E[\dots ]$ to mean $E_{{\mu }^k\times U^r(k,j)}[\dots ]$ etc.

Proof of Theorem A.1

Define $w:N^2\times {\{0,1{\}}^{\ast }}^3\stackrel{alg}{\to }\{0,1\}$ and $u:N^2\to \{0,1{\}}^{\ast }$ by

$$w:=\theta (P-p)\theta (q-P)$$

We have

$$\varphi =\frac{E\left[w\right(f-P\left)\right]}{E\left[w\right]}$$

Define $\psi$ to be $\varphi$ truncated to the first significant binary digit. Denote $I\subseteq N^2$ the set of $(k,j)$ for which $\left|{\varphi }_{kj}\right|>h(k,j{)}^{-1}$. Consider $(Q,s,b)$ a $(poly,log)$-predictor scheme satisfying

$$\forall (k,j)\in I:Q^{kj}=\eta (P^{kj}+{\psi }_{kj})$$

Such $Q$ exists since for $(k,j)\in I$, ${\psi }_{kj}$ has binary notation of logarithmically bounded size.

Applying Lemma B.2 we get

$$\forall (k,j)\in I:E\left[w^{kj}\right(P^{kj}-f{)}^2]\le E[w^{kj}(Q^{kj}-f{)}^2]+\delta (k,j)$$

for $\delta \in \Delta$.

$$\forall (k,j)\in I:E\left[w^{kj}\right((P^{kj}-f{)}^2-(Q^{kj}-f{)}^2\left)\right]\le \delta (k,j)$$

$$\forall (k,j)\in I:E\left[w^{kj}\right((P^{kj}-f{)}^2-(\eta (P^{kj}+{\psi }_{kj})-f{)}^2\left)\right]\le \delta (k,j)$$

Obviously $\left(\eta \right(P^{kj}+{\psi }_{kj})-f{)}^2\le (P^{kj}+{\psi }_{kj}-f{)}^2$, therefore

$$\forall (k,j)\in I:E\left[w^{kj}\right((P^{kj}-f{)}^2-(P^{kj}+{\psi }_{kj}-f{)}^2\left)\right]\le \delta (k,j)$$

$$\forall (k,j)\in I:{\psi }_{kj}E\left[w^{kj}\right(2(f-P^{kj})-{\psi }_{kj}\left)\right]\le \delta (k,j)$$

The expression on the left hand side is a quadratic polynomial in ${\psi }_{kj}$ which attains its maximum at ${\varphi }_{kj}$ and has roots at $0$ and $2{\varphi }_{kj}$. ${\psi }_{kj}$ is between $0$ and ${\varphi }_{kj}$, but not closer to $0$ than $\frac{{\varphi }_{kj}}{2}$. Therefore, the inequality is preserved if we replace ${\psi }_{kj}$ by $\frac{{\varphi }_{kj}}{2}$.

$$\forall (k,j)\in I:\frac{{\varphi }_{kj}}{2}E\left[w^{kj}\right(2(f-P^{kj})-\frac{{\varphi }_{kj}}{2}\left)\right]\le \delta (k,j)$$

Substituting the equation for ${\varphi }_{kj}$ we get

$$\forall (k,j)\in I:\frac{1}{2}\frac{E\left[w^{kj}\right(f-P^{kj}\left)\right]}{E\left[w^{kj}\right]}E\left[w^{kj}\right(2(f-P^{kj})-\frac{1}{2}\frac{E\left[w^{kj}\right(f-P^{kj}\left)\right]}{E\left[w^{kj}\right]}\left)\right]\le \delta (k,j)$$

$$\forall (k,j)\in I:\frac{3}{4}\frac{E\left[w^{kj}\right(f-P^{kj}){]}^2}{E\left[w^{kj}\right]}\le \delta (k,j)$$

$$\forall (k,j)\in I:\frac{3}{4}E\left[w^{kj}\right]{\varphi }_{kj}^2\le \delta (k,j)$$

$$\forall (k,j)\in I:{\varphi }_{kj}^2\le \frac{4}{3}E\left[w^{kj}{]}^{-1}\delta \right(k,j)$$

$$\forall (k,j)\in I:{\varphi }_{kj}^2\le \frac{4}{3}({\mu }^k\times U^{r(k,j)})\{p_{kj}\le P^{kj}\le q_{kj}{\}}^{-1}\delta (k,j)$$

Thus for all $k,j\in N$ we have

$$|{\varphi }_{kj}|\le h(k,j{)}^{-1}+\sqrt{\frac{4}{3}({\mu }^k\times U^{r(k,j)})\{p_{kj}\le P^{kj}\le q_{kj}{\}}^{-1}\delta (k,j)}$$

In particular, $|\varphi |\in \Delta$.

Lemma B.3

Consider $(f,\mu )$ a distributional estimation problem and $(P,r,a)$ a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$. Then there are $c_1,c_2\in R$ and a $\Delta$-moderate function $\delta :N^4\to [0,1]$ s.t. for any $k,j,s\in N$, $Q:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }Q$

$$|E_{{\mu }^k\times U^s\times U^{r(k,j)}}\left[Q\right(P^{kj}-f\left)\right]|\le (c_1+c_2{E}_{{\mu }^k\times U^s}[Q^2\left]\right)\delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})$$

Conversely, consider $M\in Q$ and $(P,r,a)$ a $Q\cap [-M,+M]$-valued $(poly,log)$-bischeme. Suppose that for any $Q\cap [-M-1,+M]$-valued $(poly,log)$-bischeme $(Q,s,b)$ we have $|E\left[Q\right(P-f\left)\right]|\in \Delta$.

Define $\tilde{P}$ to be s.t. computing ${\tilde{P}}^{kj}$ is equivalent to computing $\eta \left(P^{kj}\right)$ rounded to $h(k,j)$ digits after the binary point, where $2^{-h}\in \Delta$. Then, $\tilde{P}$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$.

Proof of Lemma B.3

Assume $P$ is a $\Delta (poly,log)$-optimal predictor scheme. Consider $k,j,s\in N$, $Q:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }Q$. Define $t:=\sigma 2^{-a}$ where $\sigma \in \{\pm 1\}$ and $a\in N$. Define $R:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }[0,1]$ to compute $\eta (P+tQ)$ rounded within error $2^{-h}$. By Lemma B.1

$$E_{{\mu }^k\times U^{r(k,j)}}\left[\right(P^{kj}-f{)}^2]\le E_{{\mu }^k\times U^{r(k,j)}\times U^s}[(R-f{)}^2]+\tilde{\delta }(k,j,T_R^{\mu }(k,r(k,j)+s),2^{|R|})$$

where $\tilde{\delta }$ is $\Delta$-moderate. It follows that

$$E_{{\mu }^k\times U^{r(k,j)}}\left[\right(P^{kj}-f{)}^2]\le E_{{\mu }^k\times U^{r(k,j)}\times U^s}[\left(\eta \right(P+tQ)-f{)}^2]+\delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})$$

where $\delta$ is $\Delta$-moderate ($a$ doesn’t enter the error bound because of the $2^{-h}$ rounding). As in the proof of Theorem A.1, $\eta$ can be dropped.

$$E_{{\mu }^k\times U^{r(k,j)}\times U^s}\left[\right(P^{kj}-f{)}^2-(P^{kj}+tQ-f{)}^2]\le \delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})$$

The expression on the left hand side is a quadratic polynomial in $t$. Explicitly:

$$-E_{{\mu }^k\times U^s}\left[Q^2\right]t^2-2E_{{\mu }^k\times U^{r(k,j)}\times U^s}\left[Q\right(P^{kj}-f\left)\right]t\le \delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})$$

Moving $E\left[Q\right]t^2$ to the right hand side and dividing both sides by $2|t|=2^{1-a}$ we get

$$-E_{{\mu }^k\times U^{r(k,j)}\times U^s}\left[Q\right(P^{kj}-f\left)\right]\sigma \le 2^{a-1}\delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})+E_{{\mu }^k\times U^s}\left[Q^2\right]2^{-a-1}$$

$$|E_{{\mu }^k\times U^{r(k,j)}\times U^s}\left[Q\right(P^{kj}-f\left)\right)]|\le 2^{a-1}\delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})+E_{{\mu }^k\times U^s}[Q^2]2^{-a-1}$$

Take $a:=-\frac{1}{2}\log \delta (k,j,T_Q^{\mu }(k,s),2^{|Q|})+\varphi (k,j)$ where $\varphi (k,j)\in [-\frac{1}{2},+\frac{1}{2}]$ is the rounding error. We get

$$|E_{{\mu }^k\times U^{r(k,j)}\times U^s}\left[Q\right(P^{kj}-f\left)\right]|\le 2^{\varphi (k,j)-1}\delta (k,j,T_Q^{\mu }(k,s),2^{|Q|}{)}^{\frac{1}{2}}+E_{{\mu }^k\times U^s}[Q^2\left]2^{-\varphi (k,j)-1}\delta \right(k,j,T_Q^{\mu }(k,s),2^{|Q|}{)}^{\frac{1}{2}}$$

Conversely, assume that for any $Q\cap [-M-1,+M]$-valued $(poly,log)$-bischeme $(R,t,c)$

$$|E\left[R\right(P-f\left)\right]|\le \delta$$

Consider $(Q,b,s)$ a $(poly,log)$-predictor scheme. We have

$$E\left[\right(Q-f{)}^2]=E[(Q-P+P-f{)}^2]$$

$$E\left[\right(Q-f{)}^2]=E[(Q-P{)}^2]+E\left[\right(P-f{)}^2]+2E[(Q-P)(P-f)]$$

$$2E\left[\right(P-Q\left)\right(P-f\left)\right]=E\left[\right(P-f{)}^2]-E[(Q-f{)}^2]+E\left[\right(Q-P{)}^2]$$

Taking $R$ to be $P-Q$ we get

$$E\left[\right(P-f{)}^2]-E[(Q-f{)}^2]+E\left[\right(Q-P\left){)}^2\right]\le \delta$$

where $\delta \in \Delta$. Noting that $E\left[\right(Q-P{)}^2]\ge 0$ and $\left(\eta \right(P)-f{)}^2\le (P-f{)}^2$ we get

$$E\left[\right(\eta \left(P\right)-f{)}^2]-E[(Q-f{)}^2]\le \delta$$

Observing that $\tilde{P}-\eta \left(P\right)$ is bounded by a function in $\Delta$, we get the desired result.

---

Theorems A.2 and A.3 follow trivially from Lemma B.3 and we omit the proof.

Proof of Theorem A.4

We have

$$P(x_1,x_2)-(f_1\times f_2)(x_1,x_2)=\left(P_1\right(x_1)-f_1(x_1\left)\right)f_2\left(x_2\right)+P_1\left(x_1\right)\left(P_2\right(x_2)-f_2(x_2\left)\right)$$

Therefore, for any $Q\cap [-1,+1]$-valued $(poly,log)$-bischeme $(Q,s,b)$

$$|E\left[Q\right(P-f_1\times f_2\left)\right]|\le |E\left[Q\right(x_1,x_2\left)\right(P_1\left(x_1\right)-f_1\left(x_1\right)\left)f_2\right(x_2\left)\right]|+|E\left[Q\right(x_1,x_2\left)P_1\right(x_1\left)\right(P_2\left(x_2\right)-f_2\left(x_2\right)\left)\right]|$$

By Lemma B.3, it is sufficient to show an appropriate bound for each of the terms on the right hand side. Suppose $(S_2,F_2,r_2^S,a_2^S)$ is a ${\Delta }^1\left(log\right)$-generator for $(f_2,{\mu }_2)$. For the first term, we have

$$|E_{{\mu }_1^k\times {\mu }_2^k\times U^{s(k,j)+r_1(k,j)}}\left[Q^{kj}\right(x_1,x_2\left)\right(P_1^{kj}\left(x_1\right)-f_1\left(x_1\right)\left)f_2\right(x_2\left)\right]|\le |E_{{\mu }_1^k\times U^{r_2^S\left(k\right)}\times U^{s(k,j)+r_1(k,j)}}\left[Q^{kj}\right(x_1,S_2^k\left)\right(P_1^{kj}\left(x_1\right)-f_1\left(x_1\right)\left)F_2^k\right]|+{\delta }_2^1\left(k\right)$$

where ${\delta }_2^1\in {\Delta }^1$. Applying Lemma B.3 for $P_1$, we get

$$|E_{{\mu }_1^k\times {\mu }_2^k\times U^{s(k,j)+r_1(k,j)}}\left[Q^{kj}\right(x_1,x_2\left)\right(P_1^{kj}\left(x_1\right)-f_1\left(x_1\right)\left)f_2\right(x_2\left)\right]|\le {\delta }_1(k,j)+{\delta }_2^1\left(k\right)$$

where ${\delta }_1\in \Delta$.

Suppose $(S_1,r_1^S,a_1^S)$ is a ${\Delta }^1\left(log\right)$-sampler for ${\mu }_1$. For the second term, we have

$$|E_{{\mu }_1^k\times {\mu }_2^k\times U^{s(k,j)+r_1(k,j)}}\left[Q^{kj}\right(x_1,x_2\left)P_1\right(x_1\left)\right(P_2^{kj}\left(x_2\right)-f_2\left(x_2\right)\left)\right]|\le |E_{U^{r_1^S\left(k\right)}\times {\mu }_2^k\times U^{s(k,j)+r_1(k,j)}}\left[Q^{kj}\right(S_1^k,x_2\left)P_1\right(S_1^k\left)\right(P_2^{kj}\left(x_2\right)-f_2\left(x_2\right)\left)\right]|+{\delta }_1^1\left(k\right)$$

where ${\delta }_1^1\in {\Delta }^1$. Applying Lemma B.3 for $P_2$, we get

$$|E_{{\mu }_1^k\times {\mu }_2^k\times U^{s(k,j)+r_1(k,j)}}\left[Q^{kj}\right(x_1,x_2\left)P_1\right(x_1\left)\right(P_2^{kj}\left(x_2\right)-f_2\left(x_2\right)\left)\right]|\le {\delta }_2(k,j)+{\delta }_1^1\left(k\right)$$

where ${\delta }_2\in \Delta$. Again, we got the required bound.

Appendix C

Proposition C.1

Consider a polynomial $q:N^2\to N$. There is a function ${\lambda }_q:N^3\to [0,1]$ s.t.

(i) $$\forall k,j\in N:\sum _{i\in N}{\lambda }_q(k,j,i)=1$$

(ii) For any function $ϵ:N^2\to [0,1]$ we have

$$ϵ(k,j)-\sum _{i\in N}{\lambda }_q(k,j,i)ϵ(k,q(k,j)+i)\in {\Delta }_{avg}^2$$

Proof of Proposition C.1

Given functions $q_1,q_2:N^2\to N$ s.t.$q_1(k,j)\ge q_2(k,j)$ for $k,j\gg 0$, the proposition for $q_1$ implies the proposition for $q_2$ by setting

$${\lambda }_{q_2}(k,j,i):=\{\begin{array}{cc}{\lambda }_{q_1}(k,j,i-q_1(k,j)+q_2(k,j\left)\right)& \text{if}i-q_1(k,j)+q_2(k,j)\ge 0\\ 0& \text{if}i-q_1(k,j)+q_2(k,j)<0\end{array}$$

Therefore, it is enough to prove to proposition for functions of the form $q(k,j)=j^{m+\frac{n\log k}{\log 3}}$ for $m>0$.

Consider $F:N\to N$ s.t.

$$\underset{k\to \infty }{lim}\frac{\log \log k}{\log \log F\left(k\right)}=0$$

Observe that

$$\underset{k\to \infty }{lim}\frac{\log (m+\frac{n\log k}{\log 3})}{\log \log F\left(k\right)-\log \log 3}=0$$

$$\underset{k\to \infty }{lim}\frac{\underset{x=3}{\overset{3^{m+\frac{n\log k}{\log 3}}}{\int }}d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

Since $ϵ$ takes values in $[0,1]$

$$\underset{k\to \infty }{lim}\frac{\underset{x=3}{\overset{3^{m+\frac{n\log k}{\log 3}}}{\int }}ϵ(k,\lfloor x\rfloor )d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

Similarly

$$\underset{k\to \infty }{lim}\frac{\underset{x=F\left(k\right)}{\overset{F(k{)}^{m+\frac{n\log k}{\log 3}}}{\int }}ϵ(k,\lfloor x\rfloor )d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

The last two equations imply that

$$\underset{k\to \infty }{lim}\frac{\underset{x=3}{\overset{F\left(k\right)}{\int }}ϵ(k,\lfloor x\rfloor )d\left(\log \log x\right)-\underset{x=3^{m+\frac{n\log k}{\log 3}}}{\overset{F(k{)}^{m+\frac{n\log k}{\log 3}}}{\int }}ϵ(k,\lfloor x\rfloor )d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

Raising $x$ to a power is equivalent to adding a constant to $\log \log x$, therefore

$$\underset{k\to \infty }{lim}\frac{\underset{x=3}{\overset{F\left(k\right)}{\int }}ϵ(k,\lfloor x\rfloor )d\left(\log \log x\right)-\underset{x=3}{\overset{F\left(k\right)}{\int }}ϵ(k,\lfloor x^{m+\frac{n\log k}{\log 3}}\rfloor )d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

$$\underset{k\to \infty }{lim}\frac{\underset{x=3}{\overset{F\left(k\right)}{\int }}\left(ϵ\right(k,\lfloor x\rfloor )-ϵ(k,\lfloor x^{m+\frac{n\log k}{\log 3}}\rfloor \left)\right)d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

Since $\lfloor x^{m+\frac{n\log k}{\log 3}}\rfloor \ge \lfloor x{\rfloor }^{m+\frac{n\log k}{\log 3}}$ we can choose ${\lambda }_q$ satisfying condition (i) so that

$$\underset{x=j}{\overset{j+1}{\int }}ϵ(k,\lfloor x^{m+\frac{n\log k}{\log 3}}\rfloor )d\left(\log \log x\right)=\left(\log \log \right(j+1)-\log \log j)\sum _i{\lambda }_q(k,j,i)ϵ(k,j^{m+\frac{n\log k}{\log 3}}+i)$$

It follows that

$$\underset{x=j}{\overset{j+1}{\int }}ϵ(k,\lfloor x^{m+\frac{n\log k}{\log 3}}\rfloor )d\left(\log \log x\right)=\underset{x=j}{\overset{j+1}{\int }}\sum _i{\lambda }_q(k,\lfloor x\rfloor ,i)ϵ(k,\lfloor x{\rfloor }^{m+\frac{n\log k}{\log 3}}+i)d\left(\log \log x\right)$$

$$\underset{k\to \infty }{lim}\frac{\underset{x=3}{\overset{F\left(k\right)}{\int }}\left(ϵ\right(k,\lfloor x\rfloor )-{\sum }_i{\lambda }_q(k,\lfloor x\rfloor ,i\left)ϵ\right(k,\lfloor x{\rfloor }^{m+\frac{n\log k}{\log 3}}+i\left)\right)d\left(\log \log x\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

$$\underset{k\to \infty }{lim}\frac{{\sum }_{j=3}^{F\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\left(ϵ\right(k,j)-{\sum }_i{\lambda }_q(k,j,i\left)ϵ\right(k,j^{m+\frac{n\log k}{\log 3}}+i\left)\right)}{\log \log F\left(k\right)-\log \log 3}=0$$

$$ϵ(k,j)-\sum _{i\in N}{\lambda }_q(k,j,i)ϵ(k,q(k,j)+i)\in {\Delta }_{avg}^2$$

Lemma C.1

Consider $(f,\mu )$ a distributional estimation problem, $(P,r,a)$, $(Q,s,b)$ $(poly,log)$-predictor schemes. Suppose $p:N^2\to N$ a polynomial and $\delta \in {\Delta }_{avg}^2$ are s.t.

$$\forall i,k,j\in N:E\left[\right(P^{k,p(k,j)+i}-f{)}^2]\le E[(Q^{kj}-f{)}^2]+\delta (k,j)$$

Then $\exists {\delta }^{\prime }\in {\Delta }_{avg}^2$ s.t.

$$E\left[\right(P^{kj}-f{)}^2]\le E[(Q^{kj}-f{)}^2]+{\delta }^{\prime }(k,j)$$

Proof of Lemma C.1

By Proposition C.1 we have

$$\tilde{\delta }(k,j):=E\left[\right(P^{kj}-f{)}^2]-\sum _i{\lambda }_p(k,j,i\left)E\right[(P^{k,p(k,j)+i}-f{)}^2]\in {\Delta }_{avg}^2$$

$$E\left[\right(P^{kj}-f{)}^2]=\sum _i{\lambda }_p(k,j,i\left)E\right[(P^{k,p(k,j)+i}-f{)}^2]+\tilde{\delta }(k,j)$$

$$E\left[\right(P^{kj}-f{)}^2]\le \sum _i{\lambda }_p(k,j,i\left)\right(E\left[\right(Q^{kj}-f{)}^2]+\delta (k,j\left)\right)+\tilde{\delta }(k,j)$$

$$E\left[\right(P^{kj}-f{)}^2]\le E[(Q^{kj}-f{)}^2]+\delta (k,j)+\tilde{\delta }(k,j)$$

Proof of Theorem 1

Define $ϵ(k,j)$ by

$$ϵ(k,j):=E_{{\mu }^k\times U^j}\left[\right({{\rm Y}}^{kj}(x,y,{\upsilon }_{f,\mu }^{kj})-f\left(x\right){)}^2]$$

It is easily seen that

$$ϵ(k,j)\le \underset{\begin{array}{c}|Q|\le \log j\\ T_Q^{\mu }(k,j)\le j\end{array}}{min}{E}_{{\mu }^k\times U^j}\left[\right(Q(x,y)-f\left(x\right){)}^2]$$

Therefore, there is a polynomial $p:N^3\to N$ s.t. for any $(poly,log)$-predictor scheme $(Q,s,b)$

$$\forall i,j,k\in N:ϵ(k,p(s(k,j),T_{Q^{kj}}^{\mu }(k,s(k,j\left)\right),2^{|Q|+|b^{kj}|})+i)\le E_{{\mu }^k\times U^{s(k,j)}}\left[\right(Q^{kj}-f{)}^2]$$

Applying Lemma C.1, we get the desired result.

Proof of Theorem 2

Consider $(P,r,a)$ a $(poly,log)$-predictor scheme. Choose $p:N^2\to N$ a polynomial s.t. evaluating $\Lambda [G{]}^{k,p(k,j)}$ involves running $P^{kj}$ until it halts “naturally” (such $p$ exists because $P$ runs in at most polynomial time and has at most logarithmic advice). Given $i,j,k\in N$, consider the execution of $\Lambda [G{]}^{k,p(k,j)+i}$. The standard deviation of $ϵ\left(P^{kj}\right)$ with respect to the internal coin tosses of $\Lambda$ is at most $\left(\right(p(k,j)+i)k{)}^{-\frac{1}{2}}$. The expectation value is $E\left[\right(P^{kj}-f{)}^2]+{\gamma }_P$ where $|{\gamma }_P|\le \delta \left(k\right)$ for $\delta \in {\Delta }_0^1$ which doesn’t depend on $i,k,j,P$. By Chebyshev’s inequality,

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

Hence

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

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

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

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

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

Applying Lemma C.1 we get the desired result.

[Vanessa Kosoy]

EDIT: Deleted examples of generatable problems since they are wrong. They are in fact examples of a weaker notion which I think also admits uniform OPS but this should be explored elsewhere.

[Vanessa Kosoy]

EDIT: Corrected Example 5.2 and added Note 2 (previous Note 2 renamed to Note 3)