Reflection with optimal predictors

[Vanessa Kosoy]

A change in terminology: It is convenient when important concepts have short names. The concept of an “optimal predictor scheme” seems much more important than its historical predecessor, the “optimal predictor”. Therefore “optimal predictor schemes” will be henceforth called just “optimal predictors” while the previous concept of “optimal predictor” might be called “flat optimal predictor”.

We study systems of computations which have access to optimal predictors for each other. We expect such systems to play an important role in decision theory (where self-prediction is required to define logical counterfactuals and mutual prediction is required for a collection of agents in a game) and Vingean reflection (where the different computations correspond to different successor agents). The previously known existence theorems for optimal predictors are not directly applicable to this case. To overcome this we prove new, specifically tailored existence theorems.

The Results section states the main novelties, Appendix A contains adaptations of old theorems, Appendix B proves selected claims from Appendix A and Appendix C proves the novel results.

Results

Notation

Given sets $X$ and $Y$, $X\to Y$ will denote the set of mappings from $X$ to $Y$.

---

Before taking on reflection, we introduce a stronger concept of optimal predictor, to which the previous existence theorems still apply.

Definition 1

Let $r$ be a positive integer. A proto-error space of rank $r$ is a set $E$ of bounded functions from $N^r$ to $R^{\ge 0}$ s.t.

(i) If ${\delta }_1,{\delta }_2\in \Delta$ then ${\delta }_1+{\delta }_2\in E$.

(ii) If ${\delta }_1\in \Delta$ and ${\delta }_2\le {\delta }_1$ then ${\delta }_2\in E$.

(iii) There is a polynomial $h:N^r\to R$ s.t. $2^{-h}\in E$.

Proposition 1

If $E$ is a proto-error space of rank $r$ and $\alpha \in R^{>0}$, then $E^{\alpha }:=\{{\delta }^{\alpha }\mid \delta \in E\}$ is also a proto-error space of rank $r$.

Proposition 2

If $E$ is a proto-error space of rank $r$, $\alpha ,\gamma \in R^{>0}$ and $\alpha <\gamma$ then $E^{\gamma }\subseteq E^{\alpha }$.

Definition 3

Fix $E$ a proto-error space of rank 2 and $(f,\mu )$ a distributional estimation problem. Consider $\hat{P}$ a $(poly,log)$-predictor.

$\hat{P}$ is called an $E(poly,log)$-optimal predictor for $(f,\mu )$ when for any $(poly,log)$-predictor $\hat{Q}$, there is $\delta \in E$ s.t.

$$E_{{\mu }^k\times U^{r_P(k,j)}}\left[\right({\hat{P}}^{kj}\left(x\right)-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{r_Q(k,j)}}[\left({\hat{Q}}^{kj}\right(x)-f(x\left){)}^2\right]+\delta (k,j)$$

$\hat{P}$ is called an $E^{\ast }(poly,log)$-optimal predictor for $(f,\mu )$ when there is $\alpha >0$ s.t.$\hat{P}$ is an $E^{\alpha }(poly,log)$-optimal predictor for $(f,\mu )$.

---

$E^{\ast }(poly,log)$-optimal predictors have properties closely parallel to $\Delta (poly,log)$-optimal predictors. The corresponding theorems are listed in Appendix A. Most theorems are given without proof, as the proofs are closely analogous to before, with the exception of Theorem A.4 which is proven in Appendix B.

We now consider a generalization in which the advice is allowed to be random.

Definition 4

Given appropriate sets $X$ and $Y$, consider $Q:N^2\times X\times {\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }Y$, $r_Q:N^2\to N$ polynomial and $\{{\sigma }_Q^{kj}:\{0,1{\}}^{\ast }\to [0,1]{\}}_{k,j\in N}$ a family of probability measures. The triple $\hat{Q}=(Q,r_Q,{\sigma }_Q)$ is called $(poly,rlog)$-bischeme of signature $X\to Y$ when

(i) The runtime of $Q^{kj}(x,y,z)$ is bounded by $p(k,j)$ with $p$ polynomial.

(ii) $\mathrm{supp}{\sigma }_Q^{kj}\subseteq \{0,1{\}}^{\le c\lfloor \log (k+2)+\log (j+2)\rfloor }$ for some $c\in N$.

We will use the notation ${\hat{Q}}^{kj}(x,y)$ to stand for the obvious $Y$-valued ${\sigma }_Q^{kj}$-random variable and the notation ${\hat{Q}}^{kj}\left(x\right)$ to stand for the obvious $Y$-valued $U^{r_Q(k,j)}\times {\sigma }_Q^{kj}$-random variable.

A $(poly,rlog)$-bischeme of signature $\{0,1{\}}^{\ast }\to Y$ will also be called a $Y$-valued $(poly,rlog)$-bischeme.

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

Note 1

Conceptually advice corresponds to precomputation which might be expensive or even “hyperprecomputation”. Random advice corresponds to random precomputation. Random logarithmic advice can be always replaced by deterministic polynomial advice at the cost of a small rounding error.

Definition 5

Fix $E$ a proto-error space of rank 2 and $(f,\mu )$ a distributional estimation problem. Consider $\hat{P}$ a $(poly,rlog)$-predictor.$\hat{P}$ is called an $E(poly,rlog)$-optimal predictor for $(f,\mu )$ when for any $(poly,rlog)$-predictor $\hat{Q}$, there is $\delta \in E$ s.t.

$$E_{{\mu }^k\times U^{r_P(k,j)}\times {\sigma }_P^{kj}}\left[\right({\hat{P}}^{kj}\left(x\right)-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{r_Q(k,j)}\times {\sigma }_Q^{kj}}[\left({\hat{Q}}^{kj}\right(x)-f(x\left){)}^2\right]+\delta (k,j)$$

---

The concept of an $E(poly,rlog)$-optimal predictor is essentially of the same strength as an $E(poly,rlog)$-optimal predictors, as seen in the following two Propositions.

Proposition 3

Fix $E$ a proto-error space of rank 2 and $(f,\mu )$ a distributional estimation problem. Consider $\hat{P}$ an $E(poly,log)$-optimal predictor. Then it defines a $E(poly,rlog)$-optimal predictor by setting ${\sigma }_P^{kj}\left(a_P^{kj}\right)=1$.

Proposition 4

Fix $E$ a proto-error space of rank 2 and $(f,\mu )$ a distributional estimation problem. If $(f,\mu )$ admits a $E(poly,rlog)$-optimal predictor then it admits a $E(poly,log)$-optimal predictor.

---

We are now ready to introduce the key abstraction.

Definition 6

Given a set $\Sigma$, denote ${\Pi }_{\Sigma }:=\Sigma \times N^2\to \{0,1{\}}^{\ast }\times N$ equipped with the product topology.

A reflective system is a triple $(\Sigma ,f,\mu )$ where $\Sigma$ is a set, $\{{\mu }_n^k:\{0,1{\}}^{\ast }\to [0,1]{\}}_{n\in \Sigma ,k\in N}$ is a collection of probability measures where we regard each ${\mu }_n$ as a word ensemble and $\{f_n:\mathrm{supp}{\mu }_n\times {\Pi }_{\Sigma }\to [0,1]{\}}_{n\in \Sigma }$ is a collection of continuous functions (here $\mathrm{supp}{\mu }_n$ has the discrete topology or, equivalently, we only require continuity in the second variable).

---

The motivation behind this definition is regarding ${\Pi }_{\Sigma }$ as the space of possible predictor programs, where the first factor of $\{0,1{\}}^{\ast }\times N$ is the program itself (including advice) and the second factor is the number of intrinsic coin flips. Thus the $f_n$ represent a system of computations in which each has access to the source code of predictors for the entire system.

Definition 7

Consider a reflective system $R=(\Sigma ,f,\mu )$ and a collection of $(poly,rlog)$-predictors $\{{\hat{Q}}_n=(Q_n,r_n,{\sigma }_n){\}}_{n\in \Sigma }$.

Denote $A_{\Sigma }:=\Sigma \times N^2\to \{0,1{\}}^{\ast }$ equipped with the product $\sigma$-algebra. Denote $\sigma :={\prod }_{n,k,j}{\sigma }_n^{kj}$, a probability measure on $A_{\Sigma }$.

Given $n\in \Sigma$, $k,j\in N$ and $a\in \{0,1{\}}^{\ast }$ denote $Q_n^{kj}\left[a\right]\in \{0,1{\}}^{\ast }$ to be the program that computes $Q_n^{kj}(x,y,a)$ given input $x,y\in \{0,1{\}}^{\ast }$. Given $a\in A_{\Sigma }$, define $\hat{Q}\left[a\right]\in {\Pi }_{\Sigma }$ by $\hat{Q}[a{]}_n^{kj}:=(Q_n^{kj}\left[a_n^{kj}\right],r_n(k,j))$.

Given $n\in \Sigma$, $R[\hat{Q}{]}_n:\mathrm{supp}{\mu }_n\to [0,1]$ is defined as follows

$$R\left[\hat{Q}{]}_n\right(x):=E_{\sigma }[f_n(x,\hat{Q}[a\left]\right)]$$

The expectation value is well-defined thanks to the continuity of $f_n$.

Definition 8

Fix $E$ a proto-error space of rank 2 and $R=(\Sigma ,f,\mu )$ a reflective system. A collection $\{P_n{\}}_{n\in \Sigma }$ of $(poly,rlog)$-predictors is called an $E(poly,rlog)$-optimal predictor system for $R$ when for any $n\in \Sigma$, $P_n$ is a $E(poly,rlog)$-optimal predictor for $\left(R\right[P{]}_n,{\mu }_n)$.

Construction 1

Given $\varphi \in \Phi$, denote $E_{1\left(\varphi \right)}$ the set of bounded functions $\delta :N\to R^{\ge 0}$ s.t.

$$\forall ϵ\in (0,1):\underset{k\to \infty }{lim}\varphi \left(k{)}^{1-ϵ}\delta \right(k)=0$$

Given $\varphi \in \Phi$, denote $E_{2(ll,\varphi )}$ the set of bounded functions $\delta :N^2\to R^{\ge 0}$ s.t.

$$\forall \psi \in \Phi :\psi \le \varphi ⟹E_{{\lambda }_{\psi }^k}\left[\delta \right(k,j\left)\right]\in E_{1\left(\psi \right)}$$

Denote

$$E_{2\left(ll\right)}:=\bigcap _{\varphi \in \Phi }{E}_{2(ll,\varphi )}$$

Proposition 5

If $\varphi \in \Phi$ is s.t. $\exists n:{lim}_{k\to \infty }{2}^{-k^n}\varphi \left(k\right)=0$, $E_{1\left(\varphi \right)}$ is a proto-error space.

For any $\varphi \in \Phi$, $E_{2(ll,\varphi )}$ is a proto-error space.

$E_{2\left(ll\right)}$ is a proto-error space.

Note 2

$E_{2\left(ll\right)}^{\ast }$-optimality is strictly stronger than ${\Delta }_{ll}^2$-optimality. We exploit this strength in Theorem 2 below which is the main motivation for introducing $E$-optimality at this point.

Theorem 1 (general existence theorem)

Any reflective system has a $E_{2\left(ll\right)}(poly,rlog)$-optimal predictor system.

---

We also prove a more restricted existence theorem which allows deterministic advice.

Definition 9

Consider a set $\Sigma$ and $\{{\mu }_n^k:\{0,1{\}}^{\ast }\to [0,1]{\}}_{n\in \Sigma ,k\in N}$ a collection of probability measures. Denote $D_{\mu }:=\left\{\right(n\in \Sigma ,k\in N,j\in N,x\in \{0,1{\}}^{\ast })\mid {\mu }_n^k(x)>0\}$. Denote ${\Omega }_{\mu }:=D_{\mu }\to [0,1]$.

Fix a set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$. A $\varphi$-reflective system is a pair $(f,\mu )$ where $\mu$ is as above and $\{f_n:\mathrm{supp}{\mu }_n\times {\Omega }_{\mu }\to [0,1]{\}}_{n\in \Sigma }$ is a collection of functions s.t. there are collections $\{{\psi }_{nm}\in \Phi {\}}_{n,m\in \Sigma }$, $\{{\alpha }_n\in (0,1]{\}}_{n\in \Sigma }$, $\{c_n\in R^{>0}{\}}_{n\in \Sigma }$ and probability measures $\{{\rho }_n:\Sigma \to [0,1]{\}}_{n\in \Sigma }$ satisfying

$$\forall n,m\in \Sigma :{\psi }_{nm}\ge {\varphi }_n$$

$$\forall n\in \Sigma ,k\in N,q,\tilde{q}\in {\Omega }_{\mu }:E_{{\mu }_n^k}\left[\right(f_n(x,q)-f_n(x,\tilde{q}){)}^2]\le c_n(E_{{\rho }_n}\left[E_{{\lambda }_{{\psi }_{nm}}^k\times {\mu }_m^k}\right[\left(q_m^{kj}\right(x)-{\tilde{q}}_m^{kj}(x\left){)}^2\right]]{)}^{{\alpha }_n}$$

Note 3

The condition on $f$ is a kind of Hoelder condition, uniform over $k$.

Proposition 6

Fix a set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$. For any $\varphi$-reflective system $(f,\mu )$ and $n\in \Sigma$, $f_n$ is continuous with respect to the product topology on ${\Omega }_{\mu }$.

Definition 10

Fix a set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$.

Given $m\in N$, $x,y_1,y_2\dots y_m\in \{0,1{\}}^{\ast }$, we let $ev(x,y_1,y_2\dots y_m)\in \{0,1{\}}^{\le \omega }$ stand for the evaluation of program $x$ on inputs $y_1,y_2\dots y_m$ without a time limit (we assume that on the output tape the machine head moves right iff it produces a symbol in $\{0,1\}$ and cannot be moved left). We also extend $\beta$ to be defined on $\{0,1{\}}^{\le \omega }$ in the obvious way.

We define $e{x}_{\mu }:{\Pi }_{\Sigma }\to {\Omega }_{\mu }$ by $e{x}_{\mu }\left(\pi {)}_n^{kj}\right(x):=E_{U^{({\pi }_n^{kj}{)}_2}}[\beta \left(ev\right(({\pi }_n^{kj}{)}_1,x,y)\left)\right]$.

Consider a $\varphi$-reflective system $R=(f,\mu )$ and a collection of $(poly,rlog)$-predictors $\{{\hat{Q}}_n=(Q_n,r_n,{\sigma }_n){\}}_{n\in \Sigma }$. Given $n\in \Sigma$, $R[\hat{Q}{]}_n:\mathrm{supp}{\mu }_n\to [0,1]$ is defined as follows

$$R\left[\hat{Q}{]}_n\right(x):=E_{\sigma }[f_n(x,e{x}_{\mu }(\hat{Q}\left[a\right]\left)\right)]$$

The expectation value is well-defined due to Proposition 5.

Definition 11

Fix a set $\Sigma$, $\{E_n{\}}_{n\in \Sigma }$ a collection of proto-error spaces of rank 2, a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$ and $R=(f,\mu )$ a $\varphi$-reflective system. A collection $\{P_n{\}}_{n\in \Sigma }$ of $(poly,log)$-predictors is called an $E^{\ast }(poly,log)$-optimal predictor system for $R$ when for any $n\in \Sigma$ there is $\gamma \in R^{>0}$ s.t.$P_n$ is an $E_n^{\gamma }(poly,log)$-optimal predictor for $\left(R\right[P{]}_n,{\mu }_n)$.

Theorem 2

Consider a finite set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$. Any $\varphi$-reflective system has an $E_{2(ll,\varphi )}^{\ast }(poly,log)$-optimal predictor system.

Appendix A

Definition A.1

$E$, a proto-error space of rank $r$, is called ample when there is a polynomial $h:N^r\to R^{>0}$ s.t. $\frac{1}{h}\in E$.

---

Fix $E$, a proto-error space of rank 2.

Theorem A.1

Assume $E$ is ample. Consider $(f,\mu )$ a distributional estimation problem, $\hat{P}$ an $E(poly,rlog)$-optimal predictor for $(f,\mu )$ and $\{p_{kj}\in [0,1]{\}}_{k,j\in N}$, $\{q_{kj}\in [0,1]{\}}_{k,j\in N}$. Define $\gamma :N^2\to R^{>0}$ by

$$\gamma (k,j):=P{r}_{{\mu }^k\times U^{r_P(k,j)}\times {\sigma }_P^{kj}}[p_{kj}\le {\hat{P}}^{kj}\le q_{kj}{]}^{-1}$$

Define

$${\varphi }_{kj}:=E_{{\mu }^k\times U^{r_P(k,j)}\times {\sigma }_P^{kj}}[f-{\hat{P}}^{kj}\mid p_{kj}\le {\hat{P}}^{kj}\le q_{kj}]$$

Assume that either $p_{kj},q_{kj}$ have a number of digits logarithmically bounded in $k,j$ or ${\hat{P}}^{kj}$ produces outputs with a number of digits logarithmically bounded in $k,j$. Then, $|\varphi |\in (\gamma E{)}^{\frac{1}{2}}$.

Theorem A.2

Consider $\mu$ a word ensemble and $f_1,f_2:\mathrm{supp}\mu \to [0,1]$ s.t. $f_1+f_2\le 1$. Suppose ${\hat{P}}_1$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_1,\mu )$ and ${\hat{P}}_2$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_2,\mu )$. Then, ${\hat{P}}_1+{\hat{P}}_2$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_1+f_2,\mu )$.

Theorem A.3

Consider $\mu$ a word ensemble and $f_1,f_2:\mathrm{supp}\mu \to [0,1]$ s.t. $f_1+f_2\le 1$. Suppose ${\hat{P}}_1$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_1,\mu )$ and ${\hat{P}}_2$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_1+f_2,\mu )$. Then, ${\hat{P}}_2-{\hat{P}}_1$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_2,\mu )$.

Definition A.2

Given $E$ a proto-error space of rank $r$, the associated error space is $E^{\frac{1}{\infty }}:={\bigcup }_{ϵ>0}{E}^{ϵ}$.

Theorem A.4

Consider $(f_1,{\mu }_1)$, $(f_2,{\mu }_2)$ distributional estimation problems with respective $E^{\ast }(poly,rlog)$-optimal predictors ${\hat{P}}_1$ and ${\hat{P}}_2$. Assume ${\mu }_1$ is $E^{\frac{1}{\infty }}\left(log\right)$-sampleable and $(f_2,{\mu }_2)$ is $E^{\frac{1}{\infty }}\left(log\right)$-generatable. Then, ${\hat{P}}_1\times {\hat{P}}_2$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f_1\times f_2,{\mu }_1\times {\mu }_2)$.

Theorem A.5

Consider $\mu$ a word ensemble, $f:\mathrm{supp}\mu \to [0,1]$ and $D\subseteq \{0,1{\}}^{\ast }$. Assume ${\hat{P}}_D$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(D,\mu )$ and ${\hat{P}}_{f\mid D}$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f,\mu \mid D)$. Then ${\hat{P}}_D{\hat{P}}_{f\mid D}$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $({\chi }_{D}f,\mu )$.

Definition A.3

We define the stabilizer of $E$, denoted $\mathrm{stab}E$, to be the set of functions $\gamma :N^2\to R^{>0}$ s.t. for any $\delta \in E$ we have $\gamma \delta \in E$.

Theorem A.6

Fix $h$ a polynomial s.t. $2^{-h}\in \Delta$. Consider $\mu$ a word ensemble, $f:\mathrm{supp}\mu \to [0,1]$ and $D\subseteq \{0,1{\}}^{\ast }$. Assume ${\mu }^k(D{)}^{-1}\in \mathrm{stab}E$. Assume $\hat{P}$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(D,\mu )$ and ${\hat{P}}_{{\chi }_{D}f}$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $({\chi }_{D}f,\mu )$. Define ${\hat{P}}_{f\mid D}$ by

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

Then, ${\hat{P}}_{f\mid D}$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f,\mu \mid D)$.

Definition A.4

Consider $\mu$ a word ensemble, ${\hat{Q}}_1$, ${\hat{Q}}_2$ $(poly,rlog)$-predictors.

We say ${\hat{Q}}_1$ is $E$-similar to ${\hat{Q}}_2$ relative to $\mu$ (denoted ${\hat{Q}}_1\underset{E}{\stackrel{\mu }{\simeq }}{\hat{Q}}_2$) when $E_{{\mu }^k\times U^{r_1(k,j)}\times U^{r_2(k,j)}\times {\sigma }_1^{kj}\times {\sigma }_2^{kj}}\left[\right({\hat{Q}}_1^{kj}\left(x\right)-{\hat{Q}}_2^{kj}\left(x\right){)}^2]\in E$.

Let $\Delta$ be an error space.

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^{r_1(k,j)}\times U^{r_2(k,j)}\times {\sigma }_1^{kj}\times {\sigma }_2^{kj}}\left[\right({\hat{Q}}_1^{kj}\left(x\right)-{\hat{Q}}_2^{kj}\left(x\right){)}^2]\in \Delta$.

Theorem A.7 (uniqueness theorem)

Consider $(f,\mu )$ a distributional estimation problem, $\hat{P}$ an $E(poly,rlog)$-optimal predictor for $(f,\mu )$ and $\hat{Q}$ an $(poly,rlog)$-predictor.

If $\hat{Q}$ is a $E(poly,rlog)$-optimal predictor for $(f,\mu )$ then $\hat{P}\underset{E^{\frac{1}{2}}}{\stackrel{\mu }{\simeq }}\hat{Q}$.

Conversely, if $\hat{P}\underset{E^{\frac{1}{\infty }}}{\stackrel{\mu }{\simeq }}\hat{Q}$ then $\hat{Q}$ is a $E^{\ast }(poly,rlog)$-optimal predictor for $(f,\mu )$.

Definition A.5

$E$ is called stable when for any non-constant polynomial $p:N\to N$ there is ${\alpha }_p>0$ s.t. for any $\delta \in E$, the function ${\delta }^{\prime }(k,j):=\delta \left(p\right(k),j)$ is in $E^{{\alpha }_p}$.

Proposition A.1

$E_{2\left(ll\right)}$ is stable.

Theorem A.8

Assume $E$ is ample and stable. Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems, $\hat{\zeta }$ a $E^{\frac{1}{\infty }}$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ and ${\hat{P}}_g$ an $E^{\ast }(poly,rlog)$-optimal predictor for $(g,\nu )$. Define ${\hat{P}}_f$ by ${\hat{P}}_f^{kj}\left(x\right):={\hat{P}}_g^{kj}\left({\hat{\zeta }}^{kj}\right(x\left)\right)$. Then, ${\hat{P}}_f$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f,\mu )$.

Theorem A.9

Assume $E$ is ample and stable. Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems, $\hat{\zeta }$ a $E^{\frac{1}{\infty }}$-pseudo-invertible weak reduction of $(f,\mu )$ to $(g,\nu )$ and ${\hat{P}}_g$ an $E^{\ast }(poly,rlog)$-optimal predictor for $(g,\nu )$. Choose $h:N^2\to N$ a polynomial with $\frac{1}{h}\in E$ and define ${\hat{P}}_f$ by

$${\hat{P}}_f^{kj}\left(x\right):=\frac{1}{h(k,j)}\sum _{i=1}^{h(k,j)}{\hat{P}}_g^{kj}\left({\hat{\zeta }}^{kj}\right(x\dots )\dots )$$

Here, the ellipses signify that each term corresponds to an independent sampling of $U^{r_{\zeta }(k,j)}\times U^{r_g(k,j)}\times {\sigma }_g^{kj}$. Then, ${\hat{P}}_f$ is an $E^{\ast }(poly,rlog)$-optimal predictor for $(f,\mu )$.

Theorem A.10

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 an $E_{2(ll,\varphi )}(poly,log)$-optimal predictor for $(f,\mu )$.

Appendix B

Definition B.1

Given $n\in N$, a function $\delta :N^{2+n}\to R^{\ge 0}$ is called $E$-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 E$

---

Lemmas B.1 and B.2 below are given only for future reference (and as an aid in spelling out the proofs of other Theorems in Appendix A).

Lemma B.1

Fix $(f,\mu )$ a distributional estimation problem and $\hat{P}$ a $(poly,rlog)$-predictor. Then, $\hat{P}$ is $E(poly,rlog)$-optimal iff there is a $E$-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_P(k,j)}\times {\sigma }_P^{kj}}\left[\right(P^{kj}(x,y,z)-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}max\left(E_{{\mu }^k\times U^{r_P(k,j)}\times {\sigma }_P^{kj}}\right[\left(P^{kj}\right(x,y,z)-f(x\left){)}^2\right]-E_{{\mu }^k\times U^s}\left[\right(Q(x,y)-f\left(x\right){)}^2],0)$$

Lemma B.2

Assume $E$ is ample. Fix $(f,\mu )$ a distributional estimation problem and $\hat{P}$ a corresponding $E(poly,rlog)$-optimal predictor. Consider $\hat{Q}$ a $(poly,rlog)$-predictor, $M>0$, $\hat{w}$ a $Q\cap [0,M]$-valued $(poly,rlog)$-bischeme. Assume $r_w\ge max(r_P,r_Q)$ and $u_P,u_Q:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ are s.t.$u_{P\ast }\left({\sigma }_w\right)={\sigma }_P$ and $u_{Q\ast }\left({\sigma }_w\right)={\sigma }_Q$. Then there is $\delta \in E$ s.t.

$$E_{{\mu }^k\times U^{r_w(k,j)}\times {\sigma }_w^{kj}}\left[w^{kj}\right(x,y,z\left)\right(P^{kj}(x,y_{\le r_P(k,j)},u_P(z\left)\right)-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{r_w(k,j)}\times {\sigma }_w^{kj}}[w^{kj}(x,y,z)\left(Q^{kj}\right(x,y_{\le r_Q(k,j)},u_Q\left(z\right))-f(x\left){)}^2\right]+\delta (k,j)$$

Proof of Lemma B.2

Suppose $h:N^2\to N$ is a polynomial s.t. $\frac{1}{h}\in E$. 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$. Consider ${\hat{Q}}_t:=(Q_t,r_w,{\sigma }_u)$ the $(poly,rlog)$-predictor defined by

$${\sigma }_u:=(1\times u_P\times u_Q{)}_{\ast }{\sigma }_w$$

$$Q_t^{kj}(x,y,(a,b,c\left)\right):=\{\begin{array}{cc}{Q}^{kj}(x,y_{\le r_Q(k,j)},c)& \text{if}{w}^{kj}(x,y,a)\ge {\alpha }^{kj}\left(t\right)\\ P^{kj}(x,y_{\le r_P(k,j)},b)& \text{if}{w}^{kj}(x,y,a)<{\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 E$ s.t.

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

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

$$E\left[\theta \right({\hat{w}}^{kj}\left(x\right)-{\alpha }^{kj}\left(t\right)\left)\right(\left({\hat{P}}^{kj}\right(x)-f(x){)}^2-({\hat{Q}}^{kj}\left(x\right)-f\left(x\right){)}^2\left)\right]\le \delta (k,j)$$

$$E\left[{\int }_0^M\theta \right({\hat{w}}^{kj}\left(x\right)-{\alpha }^{kj}\left(t\right)\left)dt\right(\left({\hat{P}}^{kj}\right(x)-f(x){)}^2-({\hat{Q}}^{kj}\left(x\right)-f\left(x\right){)}^2\left)\right]\le M\delta (k,j)$$

$$E\left[{\hat{w}}^{kj}\right(x\left)\right(\left({\hat{P}}^{kj}\right(x)-f(x){)}^2-({\hat{Q}}^{kj}\left(x\right)-f\left(x\right){)}^2\left)\right]\le M\delta (k,j)+h(k,j{)}^{-1}$$

Lemma B.3 (orthogonality lemma)

Consider $(f,\mu )$ a distributional estimation problem and $\hat{P}$ an $E(poly,rlog)$-optimal predictor for $(f,\mu )$. Then there are $c_1,c_2\in R$ and an $E^{\frac{1}{2}}$-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_P(k,j)}\times {\sigma }_P^{kj}}\left[Q\right({\hat{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 $\hat{P}$ a $Q\cap [-M,+M]$-valued $(poly,rlog)$-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 E$.

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

---

We ommit the proofs of Lemma B.3 and Lemma B.4 below since they are closely analogous to before.

Lemma B.4

Consider $(f,\mu )$ a distributional estimation problem, $\hat{P}$, $\hat{Q}$ $(poly,rlog)$-predictors. Suppose $p:N^2\to N$ a polynomial, $\varphi \in \Phi$ and $\delta \in E_{2(ll,\varphi )}$ are s.t.

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

Then $\exists {\delta }^{\prime }\in E_{2(ll,\varphi )}$ s.t.

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

Proof of Theorem A.4

Denote $\hat{P}:={\hat{P}}_1\times {\hat{P}}_2$. We have

$$\hat{P}(x_1,x_2)-(f_1\times f_2)(x_1,x_2)=\left({\hat{P}}_1\right(x_1)-f_1(x_1\left)\right)f_2\left(x_2\right)+{\hat{P}}_1\left(x_1\right)\left({\hat{P}}_2\right(x_2)-f_2(x_2\left)\right)$$

Therefore, for any $Q\cap [-1,+1]$-valued $(poly,log)$-bischeme $\hat{Q}$

$$|E\left[\hat{Q}\right(\hat{P}-f_1\times f_2\left)\right]|\le |E\left[\hat{Q}\right(x_1,x_2\left)\right({\hat{P}}_1\left(x_1\right)-f_1\left(x_1\right)\left)f_2\right(x_2\left)\right]|+|E\left[\hat{Q}\right(x_1,x_2\left){\hat{P}}_1\right(x_1\left)\right({\hat{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 $\hat{G}$ is a $E^{\frac{1}{\infty }}\left(log\right)$-generator for $(f_2,{\mu }_2)$. For the first term, we have

$$|E\left[{\hat{Q}}^{kj}\right(x_1,x_2\left)\right({\hat{P}}_1^{kj}\left(x_1\right)-f_1\left(x_1\right)\left)f_2\right(x_2\left)\right]|\le |E\left[{\hat{Q}}^{kj}\right(x_1,{\hat{G}}_1^{kj}\left)\right({\hat{P}}_1^{kj}\left(x_1\right)-f_1\left(x_1\right)\left){\hat{G}}_2^{kj}\right]|+{\delta }_2(k,j)$$

where ${\delta }_2\in E^{\frac{1}{\infty }}$ doesn’t depend on $Q$. Applying Lemma B.3 for ${\hat{P}}_1$, we get

$$|E\left[{\hat{Q}}^{kj}\right(x_1,x_2\left)\right({\hat{P}}_1^{kj}\left(x_1\right)-f_1\left(x_1\right)\left)f_2\right(x_2\left)\right]|\le {\delta }_{Q,1}(k,j)+{\delta }_2(k,j)$$

where ${\delta }_{Q,1}\in E^{{\alpha }_1}$ for some ${\alpha }_1\in R^{>0}$ that doesn’t depend on $Q$.

Suppose $\hat{S}$ is a $E^{\frac{1}{\infty }}\left(log\right)$-sampler for ${\mu }_1$. For the second term, we have

$$|E\left[{\hat{Q}}^{kj}\right(x_1,x_2\left){\hat{P}}_1\right(x_1\left)\right({\hat{P}}_2^{kj}\left(x_2\right)-f_2\left(x_2\right)\left)\right]|\le |E\left[{\hat{Q}}^{kj}\right({\hat{S}}^{kj},x_2\left){\hat{P}}_1\right({\hat{S}}^{kj}\left)\right({\hat{P}}_2^{kj}\left(x_2\right)-f_2\left(x_2\right)\left)\right]|+{\delta }_1(k,j)$$

where ${\delta }_1\in E^{\frac{1}{\infty }}$ doesn’t depend on $Q$. Applying Lemma B.3 for ${\hat{P}}_2$, we get

$$|E\left[{\hat{Q}}^{kj}\right(x_1,x_2\left){\hat{P}}_1\right(x_1\left)\right({\hat{P}}_2^{kj}\left(x_2\right)-f_2\left(x_2\right)\left)\right]|\le {\delta }_{Q,2}(k,j)+{\delta }_1(k,j)$$

where ${\delta }_{Q,2}\in E^{{\alpha }_2}$ for some ${\alpha }_2\in R^{>0}$ that doesn’t depend on $Q$. Again, we got the required bound.

Proof of Proposition A.1

Consider a non-constant polynomial $p:N\to N$ and $\delta \in E_{2\left(ll\right)}$. Define ${\delta }^{\prime }(k,j):=\delta \left(p\right(k),j)$. To get the desired condition for ${\delta }^{\prime }$ and $\varphi \in \Phi$, consider any ${\varphi }^{\prime }\in \Phi$ s.t. for sufficiently large $k$ we have ${\varphi }^{\prime }\left(p\right(k\left)\right)=\varphi \left(k\right)$. For any $ϵ\in (0,1)$ we have

$$\underset{k\to \infty }{lim}{\varphi }^{\prime }\left(k{)}^{ϵ}{E}_{{\lambda }_{{\varphi }^{\prime }}^k}\right[\delta (k,j)]=0$$

In particular

$$\underset{k\to \infty }{lim}{\varphi }^{\prime }\left(p\right(k\left){)}^{ϵ}{E}_{{\lambda }_{{\varphi }^{\prime }}^{p\left(k\right)}}\right[\delta \left(p\right(k),j)]=0$$

$$\underset{k\to \infty }{lim}\varphi \left(k{)}^{ϵ}{E}_{{\lambda }_{\varphi }^k}\right[{\delta }^{\prime }(k,j)]=0$$

Appendix C

Proof of Proposition 1

To check condition (i), consider ${\delta }_1,{\delta }_2\in E$.

If $\alpha >1$, $({\delta }_1^{\alpha }+{\delta }_2^{\alpha }{)}^{\frac{1}{\alpha }}\le {\delta }_1+{\delta }_2\in E$ hence $({\delta }_1^{\alpha }+{\delta }_2^{\alpha }{)}^{\frac{1}{\alpha }}\in E$ and ${\delta }_1^{\alpha }+{\delta }_2^{\alpha }\in E^{\alpha }$.

If $\alpha \le 1$, $({\delta }_1^{\alpha }+{\delta }_2^{\alpha }{)}^{\frac{1}{\alpha }}=2^{\frac{1}{\alpha }}(\frac{{\delta }_1^{\alpha }+{\delta }_2^{\alpha }}{2}{)}^{\frac{1}{\alpha }}\le 2^{\frac{1}{\alpha }}\frac{{\delta }_1+{\delta }_2}{2}\in E$ hence $({\delta }_1^{\alpha }+{\delta }_2^{\alpha }{)}^{\frac{1}{\alpha }}\in E$ and ${\delta }_1^{\alpha }+{\delta }_2^{\alpha }\in E^{\alpha }$.

Conditions (ii) and (iii) are obvious.

Proof of Proposition 2

Consider $\delta \in E$. We need to show that ${\delta }^{\gamma }\in E^{\alpha }$ i.e. that ${\delta }^{\frac{\gamma }{\alpha }}\in E$. But $\frac{\gamma }{\alpha }>1$ hence ${\delta }^{\frac{\gamma }{\alpha }}=(sup\delta {)}^{\frac{\gamma }{\alpha }}(\frac{\delta }{sup\delta }{)}^{\frac{\gamma }{\alpha }}\le (sup\delta {)}^{\frac{\gamma }{\alpha }}\frac{\delta }{sup\delta }\in E$.

Proof of Proposition 3

Follows immediately from Lemma B.1.

Proof of Proposition 4

Suppose $\hat{P}$ is a $E(poly,rlog)$-optimal predictor. Set $a^{kj}:=\arg {min}_{z\in \mathrm{supp}{\sigma }_P^{kj}}{E}_{{\mu }^k\times U^{r_P(k,j)}}\left[\right(P^{kj}(x,y,z)-f\left(x\right){)}^2]$. Replacing $\sigma$ by $a$ we get the desired $E(poly,log)$-optimal predictor.

Proposition C.1

For any $\psi \in \Phi$, $min(\frac{\log \log (k+3)}{\log \log (j+3)},1{)}^{\psi \left(k\right)}\in E_{2\left(ll\right)}$

In particular, this implies $\frac{1}{j+1}\in E_{2\left(ll\right)}$ so $E_{2\left(ll\right)}$ is ample.

Proof of Proposition C.1

Denote ${\delta }_{\psi }(k,j):=min(\frac{\log \log (k+3)}{\log \log (j+3)},1{)}^{\psi \left(k\right)}$. Consider $\varphi \in \Phi$, $ϵ\in (0,1)$. We have

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

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

$$\underset{k\to \infty }{limsup}\varphi \left(k{)}^{1-ϵ}{E}_{{\lambda }_{\varphi }^k}\right[\delta (k,j)]\le \underset{k\to \infty }{limsup}\varphi (k{)}^{1-ϵ}\left(\varphi \right(k{)}^{\frac{ϵ}{2}-1}+\varphi \left(k{)}^{-\frac{ϵ}{2}\psi \left(k\right)}\right)$$

$$\underset{k\to \infty }{limsup}\varphi \left(k{)}^{1-ϵ}{E}_{{\lambda }_{\varphi }^k}\right[\delta (k,j)]\le \underset{k\to \infty }{limsup}(\varphi (k{)}^{-\frac{ϵ}{2}}+\varphi (k{)}^{1-ϵ-\frac{ϵ}{2}\psi \left(k\right)})$$

$$\underset{k\to \infty }{lim}\varphi \left(k{)}^{1-ϵ}{E}_{{\lambda }_{\varphi }^k}\right[\delta (k,j)]=0$$

Proof of Proposition 5

The only not entirely obvious part is condition (iii) for $E_{2\left(ll\right)}$ which follows from Proposition C.1 (since $2^{-j}\in E_{2\left(ll\right)}$).

Construction C.1

Fix $R=(\Sigma ,f,\mu )$ a reflective system.

For any $j\in N$, denote $W^j\subseteq \{0,1{\}}^{\ast }$ the set of the first $j$ words in lexicographic order. Denote ${\Delta }^j$ the space of probability distributions on $W^j$. Denote ${\Delta }_{\Sigma }:={\prod }_{\begin{array}{c}k,j\in N\\ n\in \Sigma \end{array}}{\Delta }^j$. Denote $W_{\Sigma }:=\left\{\right(n\in \Sigma ,k\in N,j\in N,x\in W^j\left)\right\}$. Let $V_{\Sigma }$ be the locally convex topological vector space $W_{\Sigma }\to R$, where the topology is the product topology.

${\Delta }_{\Sigma }$ is a compact (by Tychonoff’s theorem) convex subset of $V_{\Sigma }$. Each $\vartheta \in {\Delta }_{\Sigma }$ can be regarded as a probability measure on $A_{\Sigma }$.

Given $a\in A_{\Sigma }$, we define $\overline{a}\in {\Pi }_{\Sigma }$ by ${\overline{a}}_n^{kj}:=(a_n^{kj},j)$.

Given $k,j\in N$ and $n\in \Sigma$, define ${ϵ}_{R,n}^{kj}:{\Delta }_{\Sigma }\times {\Delta }^j\to [0,1]$ as follows

$${ϵ}_{R,n}^{kj}(\vartheta ,\zeta ):=E_{\zeta \times {\mu }_n^k\times U^j\times \vartheta }\left[\right(e{v}^j(x,y,z)-f_n(y,\overline{{\rm Y}\left[w\right]}){)}^2]$$

Define ${\kappa }_R\subseteq {\Delta }_{\Sigma }\times {\Delta }_{\Sigma }$ by

$${\kappa }_R=\left\{\right({\vartheta }_1,{\vartheta }_2)\mid \forall k,j\in N,n\in \Sigma ,\zeta \in {\Delta }^j:{ϵ}_{R,n}^{kj}({\vartheta }_1,\left({\vartheta }_2{)}_n^{kj}\right)\le {ϵ}_{R,n}^{kj}({\vartheta }_1,\zeta )\}$$

Proposition C.2

${\kappa }_R$ is a Kakutani map.

Proof of Proposition C.2

${ϵ}_{R,n}^{kj}$ is continuous in the 2nd argument and ${\Delta }^j$ is compact for any $j\in N$. Therefore, for any $\vartheta \in {\Delta }_{\Sigma }$, ${\kappa }_R\left(\vartheta \right)\subseteq {\Delta }_{\Sigma }$ is non-empty by the extreme value theorem. It is compact by Tychonoff’s theorem and it is obviously convex.

Given $Y\subseteq \mathrm{supp}{\mu }_n^k$ finite, define ${ϵ}_{R,Y,n}^{kj}:{\Delta }_{\Sigma }\times {\Delta }^j\to [0,1]$ by

$${ϵ}_{R,Y,n}^{kj}(\vartheta ,\zeta ):=\sum _{y\in Y}{\mu }_n^k\left(y\right)E_{\zeta \times U^j\times \vartheta }\left[\right(e{v}^j(x,y,z)-f_n(y,\overline{{\rm Y}\left[w\right]}){)}^2]$$

${ϵ}_{R,Y,n}^{kj}$ is continuous since $f$ is continuous. Regarding the $Y$s as a net by set inclusion, ${ϵ}_{R,Y,n}^{kj}$ uniformly converges to ${ϵ}_{R,n}^{kj}$, therefore ${ϵ}_{R,n}^{kj}$ is continuous.

Given $n\in \Sigma$, $k,j\in N$, define ${\kappa }_{R,n}^{kj}\subseteq {\Delta }_{\Sigma }\times {\Delta }_{\Sigma }$ by

$${\kappa }_{R,n}^{kj}=\left\{\right({\vartheta }_1,{\vartheta }_2)\mid \forall \zeta \in {\Delta }^j:{ϵ}_{R,n}^{kj}({\vartheta }_1,\left({\vartheta }_2{)}_n^{kj}\right)\le {ϵ}_{R,n}^{kj}({\vartheta }_1,\zeta )\}$$

${\kappa }_{R,n}^{kj}$ is closed since ${ϵ}_{R,n}^{kj}$ is continuous. Therefore ${\kappa }_R={\bigcap }_{\begin{array}{c}k,j\in N\\ n\in \Sigma \end{array}}{\kappa }_{R,n}^{kj}$ is also closed.

Proof of Theorem 1

Using Proposition C.2, we apply the Kakutani-Glicksberg-Fan theorem to get $(\sigma ,\sigma )\in {\kappa }_R$. Define ${\hat{P}}_n:=({\rm Y},j,\sigma )$.

Consider $n\in \Sigma$, $\hat{Q}$ a $(poly,log)$-predictor. Choose $p:N^2\to N$ a polynomial and $\{q^{kj}\in W^{p(k,j)}{\}}_{k,j\in N}$ s.t.$p\ge r_Q$ and

$$\forall i,k,j\in N,x\in \mathrm{supp}{\mu }_n^k,y\in \{0,1{\}}^{p(k,j)+i}:e{v}^{p(k,j)+i}(q^{kj},x,y)=Q^{kj}(x,y_{<r_Q(k,j)},a_Q^{kj})$$

By definition of ${\kappa }_R$, we have

$$\forall i,k,j\in N:{ϵ}_{R,n}^{k,p(k,j)+i}(\sigma ,{\sigma }_n^{k,p(k,j)+i})\le {ϵ}_{R,n}^{k,p(k,j)+i}(\sigma ,q^{kj})$$

Here we implicitly used the natural injection $W^m\to {\Delta }^m$.

$$\forall i,k,j\in N:E_{{\sigma }_n^{k,p(k,j)+i}\times {\mu }_n^k\times U^{p(k,j)+i}\times \sigma }\left[\right(e{v}^{p(k,j)+i}(x,y,z)-f_n(y,\overline{{\rm Y}\left[w\right]}){)}^2]\le E_{{\mu }_n^k\times U^{p(k,j)+i}\times \sigma }[\left(e{v}^{p(k,j)+i}\right(q^{kj},y,z)-f_n(y,\overline{{\rm Y}\left[w\right]}\left){)}^2\right]$$

$$\forall i,k,j\in N:E_{{\sigma }_n^{k,p(k,j)+i}\times {\mu }_n^k\times U^{p(k,j)+i}\times \sigma }\left[\right(P_n^{k,p(k,j)+i}(y,z,x)-f_n(y,{\hat{P}}_n[w\left]\right){)}^2]\le E_{{\mu }_n^k\times U^{r_Q(k,j)}\times \sigma }[\left({\hat{Q}}^{kj}\right(y,z)-f_n(y,{\hat{P}}_n\left[w\right]\left){)}^2\right]$$

Denoting ${\hat{\sigma }}_n^{k,p(k,j)+i}:={\sigma }_n^{k,p(k,j)+i}\times {\mu }_n^k\times U^{p(k,j)+i}$, The left hand side satisfies

$$E_{{\hat{\sigma }}_n^{k,p(k,j)+i}\times \sigma }\left[\right(P_n^{k,p(k,j)+i}(y,z,x)-f_n(y,{\hat{P}}_n[w\left]\right){)}^2]=E_{{\hat{\sigma }}_n^{k,p(k,j)+i}}[\left(P_n^{k,p(k,j)+i}\right(y,z,x)-E_{\sigma }[f_n(y,{\hat{P}}_n[w\left]\right)\left]{)}^2\right]+Va{r}_{\sigma }\left[f_n\right(y,{\hat{P}}_n\left[w\right]\left)\right]$$

Similarly, for the right hand side we have

$$E_{{\mu }_n^k\times U^{r_Q(k,j)}\times \sigma }\left[\right({\hat{Q}}^{kj}(y,z)-f_n(y,{\hat{P}}_n[w\left]\right){)}^2]=E_{{\mu }_n^k\times U^{r_Q(k,j)}}[\left({\hat{Q}}^{kj}\right(y,z)-E_{\sigma }[f_n(y,{\hat{P}}_n[w\left]\right)\left]{)}^2\right]+Va{r}_{\sigma }\left[f_n\right(y,{\hat{P}}_n\left[w\right]\left)\right]$$

Combining the two together, we get

$$E_{{\hat{\sigma }}_n^{k,p(k,j)+i}}\left[\right(P_n^{k,p(k,j)+i}(y,z,x)-E_{\sigma }\left[f_n\right(y,{\hat{P}}_n\left[w\right]\left)\right]{)}^2]\le E_{{\mu }_n^k\times U^{r_Q(k,j)}}[\left({\hat{Q}}^{kj}\right(y,z)-E_{\sigma }[f_n(y,{\hat{P}}_n[w\left]\right)\left]{)}^2\right]$$

$$E_{{\hat{\sigma }}_n^{k,p(k,j)+i}}\left[\right({\hat{P}}_n^{k,p(k,j)+i}\left(y\right)-R\left[\hat{P}{]}_n\right(y\left){)}^2\right]\le E_{{\mu }_n^k\times U^{r_Q(k,j)}}\left[\right({\hat{Q}}^{kj}\left(y\right)-R\left[\hat{P}{]}_n\right(y\left){)}^2\right]$$

Applying Lemma B.4 we conclude that there is $\delta \in E_{2\left(ll\right)}$ s.t.

$$E_{{\hat{\sigma }}_n^{kj}}\left[\right({\hat{P}}_n^{kj}\left(y\right)-R\left[\hat{P}{]}_n\right(y\left){)}^2\right]\le E_{{\mu }_n^k\times U^{r_Q(k,j)}}\left[\right({\hat{Q}}^{kj}\left(y\right)-R\left[\hat{P}{]}_n\right(y\left){)}^2\right]+\delta (k,j)$$

Proof of Proposition 6

We need to show that for every $n\in \Sigma$, $x\in \mathrm{supp}{\mu }_n$, $q\in {\Omega }_{\mu }$ and $ϵ>0$, there is a finite set $X\subseteq D_{\mu }$ and $\delta >0$ s.t. for every $\tilde{q}\in {\Omega }_{\mu }$ with $\forall (n,k,j,y)\in X:|q_n^{kj}\left(y\right)-{\tilde{q}}_n^{kj}\left(y\right)|<\delta$ we have $|f(x,q)-f(x,\tilde{q})|<ϵ$.

Choose $k\in N$ s.t. $x\in \mathrm{supp}{\mu }_n^k$, $Z\subseteq \Sigma$ finite and $Y\subseteq \{0,1{\}}^{\ast }$ finite. Define $X:=\left\{\right(k,j\in N,m\in Z,y\in Y)\mid j<t_{{\psi }_{nm}}(k\left)\right\}$. We get

$$E_{{\mu }_n^k}\left[\right(f_n(y,q)-f_n(y,\tilde{q}){)}^2]\le c_n(E_{{\rho }_n}\left[E_{{\lambda }_{{\psi }_{nm}}^k\times {\mu }_m^k}\right[\left(q_m^{kj}\right(y)-{\tilde{q}}_m^{kj}(y\left){)}^2\right]]{)}^{{\alpha }_n}$$

$${\mu }_n^k\left(x\right)\left(f_n\right(x,q)-f_n(x,\tilde{q}){)}^2\le c_n({\rho }_n(\Sigma \setminus Z)+{\delta }^2{)}^{{\alpha }_n}$$

By choosing $Z$ with ${\rho }_n(\Sigma \setminus Z)$ sufficiently small and $\delta$ sufficiently small we get the desired condition.

Proposition C.3

Fix a finite set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$. Consider $R=(f,\mu )$ a $\varphi$-reflective system and two collections of $(poly,rlog)$-predictors $\{{\hat{Q}}_{1n}{\}}_{n\in \Sigma }$ and $\{{\hat{Q}}_{2n}{\}}_{n\in \Sigma }$. Assume that for some $\gamma \in (0,1]$, $\forall n\in \Sigma :{\hat{Q}}_{1n}\underset{E_{2\left(ll\right)}^{\gamma }}{\stackrel{{\mu }_n}{\simeq }}{\hat{Q}}_{2n}$. Then

$$\forall n\in \Sigma :E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\in E_{1\left({\varphi }_n\right)}^{\frac{1}{\infty }}$$

Proof of Proposition C.3

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]=E_{{\mu }_n^k}[\left(E_{{\sigma }_1}\right[f_n(x,e{x}_{\mu }({\hat{Q}}_1\left[a\right]\left)\right)]-E_{{\sigma }_2}[f_n(x,e{x}_{\mu }({\hat{Q}}_2\left[a\right]\left)\right)\left]{)}^2\right]$$

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\le E_{{\mu }_n^k\times {\sigma }_1\times {\sigma }_2}[\left(f_n\right(x,e{x}_{\mu }\left({\hat{Q}}_1\right[a_1\left]\right))-f_n(x,e{x}_{\mu }\left({\hat{Q}}_2\right[a_2\left]\right)\left){)}^2\right]$$

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\le E_{{\sigma }_1\times {\sigma }_2}[c_n\left(E_{{\rho }_n}\right[E_{{\lambda }_{{\psi }_{nm}}^k\times {\mu }_m^k}\left[\right(E_{U^{r_1(k,j)}}\left[Q_{1m}^{kj}\right(x,y,a_1\left)\right]-E_{U^{r_2(k,j)}}\left[Q_{2m}^{kj}\right(x,y,a_2\left)\right]{)}^2\left]\right]{)}^{{\alpha }_n}]$$

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\le E_{{\sigma }_1\times {\sigma }_2}[c_n\left(E_{{\rho }_n}\right[E_{{\lambda }_{{\psi }_{nm}}^k}\left[E_{{\mu }_m^k\times U^{r_1(k,j)}\times U^{r_2(k,j)}}\right[\left(Q_{1m}^{kj}\right(x,y,a_1)-Q_{2m}^{kj}(x,y,a_2\left){)}^2\right]\left]\right]{)}^{{\alpha }_n}]$$

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\le c_n(E_{{\rho }_n}\left[E_{{\lambda }_{{\psi }_{nm}}^k}\right[E_{{\mu }_m^k\times U^{r_1(k,j)}\times U^{r_2(k,j)}\times {\sigma }_1\times {\sigma }_2}\left[\right(Q_{1m}^{kj}(x,y,a_1)-Q_{2m}^{kj}(x,y,a_2){)}^2\left]\right]]{)}^{{\alpha }_n}$$

Using the similarity of ${\hat{Q}}_1$ and ${\hat{Q}}_2$ there are $\{{\delta }_n:N^2\to [0,1]\in E_{2\left(ll\right)}{\}}_{n\in \Sigma }$ s.t.

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\le c_n(E_{{\rho }_n}\left[E_{{\lambda }_{{\psi }_{nm}}^k}\right[{\delta }_m(k,j{)}^{\gamma }]]{)}^{{\alpha }_n}$$

$$E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\le c_n(E_{{\rho }_n}\left[E_{{\lambda }_{{\psi }_{nm}}^k}\right[{\delta }_m(k,j)\left]\right]{)}^{{\alpha }_n\gamma }$$

${\delta }_m\in E_{2\left(ll\right)}$ hence $E_{{\lambda }_{{\psi }_{nm}}^k}\left[{\delta }_m\right(k,j\left)\right]\in E_{1\left({\psi }_{nm}\right)}\subseteq E_{1\left({\varphi }_n\right)}$. This implies $E_{{\rho }_n}\left[E_{{\lambda }_{{\psi }_{nm}}^k}\right[{\delta }_m(k,j)\left]\right]\in E_{1\left({\varphi }_n\right)}$ and $E_{{\mu }_n^k}\left[\right(R\left[{\hat{Q}}_1{]}_n\right(x)-R[{\hat{Q}}_1{]}_n\left(x\right){)}^2]\in E_{1\left({\varphi }_n\right)}^{{\alpha }_n\gamma }$

Definition C.1

Fix a set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$. Given $R=(f,\mu )$ a $\varphi$-reflective system, the associated reflective system $e{x}^{-1}R=(\Sigma ,e{x}^{-1}f,\mu )$ is defined by

$$\left(e{x}^{-1}{f}_n\right)(x,\pi ):=f_n(x,e{x}_{\mu }(\pi \left)\right)$$

$f_n$ is continuous thanks to Proposition 6 since $e{x}_{\mu }$ is continuous.

Proof of Theorem 2

Fix a finite set $\Sigma$ and a collection $\{{\varphi }_n\in \Phi {\}}_{n\in \Sigma }$. Consider $R$ a $\varphi$-reflective system. By Theorem 1, there is $\hat{R}$ an $E_{2\left(ll\right)}(poly,rlog)$-optimal predictor system for $e{x}^{-1}R$. For each $n\in \Sigma$ we can use Proposition 4 to choose ${\hat{P}}_n$, an $E_{2\left(ll\right)}(poly,log)$-optimal predictor for $\left(e{x}^{-1}R\right)[\hat{R}{]}_n=R[\hat{R}{]}_n$. By Theorem A.7, we have ${\hat{P}}_n\underset{E_{2\left(ll\right)}^{\frac{1}{2}}}{\stackrel{{\mu }_n}{\simeq }}{\hat{R}}_n$. By Proposition C.3 this implies $E_{{\mu }_n^k}\left[\right(R\left[\hat{P}{]}_n\right(x)-R[\hat{R}{]}_n\left(x\right){)}^2]\in E_{1\left({\varphi }_n\right)}^{\frac{1}{\infty }}$. This means ${\hat{P}}_n$ is an $E_{2(ll,{\varphi }_n)}^{\ast }(poly,log)$-optimal predictor for $R[\hat{P}{]}_n$ and $\hat{P}$ is an $E_{2(ll,\varphi )}^{\ast }(poly,log)$-optimal predictor system for $R$.