Optimal predictor schemes

[Vanessa Kosoy]

I introduce the concept of “optimal predictor scheme” which differs from (quasi)optimal predictors in depending on an additional parameter representing the amount of computing resources the predictor is allowed to use. For a certain flavor of optimal predictor scheme, I prove existence for arbitrary distributional decision problems.

Results

It is convenient to think of the concepts of “optimal predictor” and “quasi-optimal predictor” as special cases of the more general $\Delta$-optimal predictors corresponding to different choices of the “error space” $\Delta$.

Definition 1

Let $r$ be a positive integer. An error space of rank r $\Delta$ is a set 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 \Delta$.

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

(iii) Given $\alpha \in (0,1]$, if $\delta \in \Delta$ then ${\delta }^{\alpha }\in \Delta$.

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

Example 1.1

${\Delta }_0^1$ is the set of functions $\delta :N\to R^{\ge 0}$ s.t. ${lim}_{k\to \infty }\delta \left(k\right)=0$.

Example 1.2

${\Delta }_{neg}^1$ is the set of negligible functions $\delta :N\to R^{\ge 0}$.

Example 1.3

${\Delta }_{avg}^2$ is the set of bounded functions $\delta :N^2\to R^{\ge 0}$ s.t. for any $f:N\to N$, if

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

then

$$\underset{k\to \infty }{lim}\frac{\sum _{j=3}^{f\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j)}{\log \log f\left(k\right)-\log \log 3}=0$$

It is slightly non-obvious that condition (iii) holds in this example. To see this, note that the expression inside the limit can be regarded as $E_{{\lambda }_f^k}\left[\delta \right(k,j\left)\right]$ where ${\lambda }_f^k$ is a certain probability measure over $j$. ${lim}_{k\to \infty }{E}_{{\lambda }_f^k}\left[\delta \right(k,j\left)\right]=0$ implies that for any $ϵ>0$, ${lim}_{k\to \infty }P{r}_{{\lambda }_f^k}\left[\delta \right(k,j)>ϵ]=0$ since $E_{{\lambda }_f^k}\left[\delta \right(k,j\left)\right]\ge ϵP{r}_{{\lambda }_f^k}\left[\delta \right(k,j)>ϵ]$. For any $ϵ$, we have $E_{{\lambda }_f^k}\left[\delta \right(k,j{)}^{\alpha }]\le ϵ+P{r}_{{\lambda }_f^k}[\delta (k,j)>{ϵ}^{{\alpha }^{-1}}]sup\delta$, therefore ${lim}_{k\to \infty }{E}_{{\lambda }_f^k}\left[\delta \right(k,j{)}^{\alpha }]=0$.

Definition 2

Consider $\Delta$ an error space of rank 1 and $(D,\mu )$ a distributional decision problem. A $\Delta$-optimal predictor for $(D,\mu )$ is a family of polynomial size Boolean circuits $$\{P^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$$ s.t. for any family of polynomial size Boolean circuits $$\{Q^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$$ we have

$$E_{{\mu }^k}\left[\right(P^k\left(x\right)-{\chi }_D\left(x\right){)}^2]\le E_{{\mu }^k}[\left(Q^k\right(x)-{\chi }_D(x\left){)}^2\right]+\delta \left(k\right)$$

where $\delta \in \Delta$.

In particular, optimal predictors are ${\Delta }_{neg}^1$-optimal predictors and quasi-optimal predictors are ${\Delta }_0^1$-optimal predictors.

Definition 3

Consider $\Delta$ an error space of rank 2 and $(D,\mu )$ a distributional decision problem. A $\Delta$-optimal predictor scheme for $(D,\mu )$ is a family of Boolean circuits $$\{P^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k,j\in N}$$ s.t.

(i) $|P^{kj}|\le p(k,j)$ for some polynomial $p$.

(ii) for any family of Boolean circuits $$\{Q^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k,j\in N}$$ that satisfies (i) we have

$$E_{{\mu }^k}\left[\right(P^{kj}\left(x\right)-{\chi }_D\left(x\right){)}^2]\le E_{{\mu }^k}[\left(Q^{kj}\right(x)-{\chi }_D(x\left){)}^2\right]+\delta (k,j)$$

where $\delta \in \Delta$.

It is straightforward to generalize Theorems 1-8 about quasi-optimal predictors to $\Delta$-optimal predictors and $\Delta$-optimal predictor schemes. The versions for optimal predictor schemes are stated in Appendix A without proof. The only theorem whose proof requires a slightly non-obvious tweak is Theorem 1. The amended proof is given in Appendix B.

The main technical novelty of this post is the following existence theorem.

Theorem 1

Consider $(D,\mu )$ a distributional decision problem. Define the circuit family $P_{D,\mu }^{\ast }$ by

$$P_{D,\mu }^{\ast kj}:=\underset{|Q|\le j}{argmin}{E}_{{\mu }^k}\left[\right(Q\left(x\right)-{\chi }_D\left(x\right){)}^2]$$

Then, $P_{D,\mu }^{\ast }$ is a ${\Delta }_{avg}^2$-optimal predictor scheme for $(D,\mu )$.

The proof is given in Appendix C.

The definition of $P^{\ast }$ is rather trivial, but the fact Theorems A.1-A.7 apply to $P^{\ast }$ with regard to the error space ${\Delta }_{avg}^2$ is non-trivial. For example, this can be applied to the “classical” setting of logical uncertainty by taking $D$ to be the set of true sentences in some formal logic $F$ (e.g. $PA$, $ZFC$). For a suitable choice of $\mu$, $P_{D,\mu }^{\ast }$ will satisfy an approximate version of the coherence conditions because of the considerations here.

Appendix A

Fix $\Delta$ an error space of rank 2, $h$ the polynomial from condition (iv).

Theorem A.1

Consider $(D,\mu )$ a distributional decision problem and $P$ a $\Delta$-optimal predictor scheme for $(D,\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\{x\in \{0,1{\}}^{\ast }\mid p_{kj}\le P^{kj}\left(x\right)\le q_{kj}\}\ge ϵ$$

Define

$${\varphi }_{kj}:=E_{{\mu }^k}\left[{\chi }_D\right(x)-P^{kj}(x)\mid p_{kj}\le P^{kj}(x)\le q_{kj}]$$

Then, $|\varphi |\in \Delta$.

Theorem A.2

Consider $\mu$ a word ensemble and $D_1$, $D_2$ disjoint languages. Suppose $P_1$ is a $\Delta$-optimal predictor scheme for $(D_1,\mu )$ and $P_2$ is a $\Delta$-optimal predictor scheme for $(D_2,\mu )$. Then, $P:=\eta (P_1+P_2)$ is a $\Delta$-optimal predictor scheme for $(D_1\cup D_2,\mu )$.

Theorem A.3

Consider $\mu$ a word ensemble and $D_1$, $D_2$ disjoint languages. Suppose $P_1$ is a $\Delta$-optimal predictor scheme for $(D_1,\mu )$ and $P$ is a $\Delta$-optimal predictor scheme for $(D_1\cup D_2,\mu )$. Then, $P_2:=\eta (P-P_1)$ is a $\Delta$-optimal predictor scheme for $(D_2,\mu )$.

Theorem A.4

Consider $(D_1,{\mu }_1)$, $(D_2,{\mu }_2)$ distributional decision problems with respective $\Delta$-optimal predictor schemes $P_1$ and $P_2$. Define $\{P^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$ as the family of circuits computing $P^{kj}\left(\right(x_1,x_2\left)\right):=P_1^{kj}\left(x_1\right)P_2^{kj}\left(x_2\right)$. Then, $P$ is a $\Delta$-optimal predictor scheme for $(D_1\times D_2,{\mu }_1\times {\mu }_2)$.

Theorem A.5

Consider $C,D\subseteq \{0,1{\}}^{\ast }$ and $\mu$ a word ensemble. Assume $P_D$ is a $\Delta$-optimal predictor scheme for $(D,\mu )$ and $P_{C\mid D}$ is a $\Delta$-optimal predictor scheme for $(C,\mu \mid D)$. Then $P_D{P}_{C\mid D}$ is a $\Delta$-optimal predictor scheme for $(C\cap D,\mu ).$

Theorem A.6

Consider $C,D\subseteq \{0,1{\}}^{\ast }$ and $\mu$ a word ensemble. Assume $\exists ϵ>0\forall k:{\mu }^k\left(D\right)\ge ϵ$. Assume $P_D$ is a $\Delta$-optimal predictor scheme for $(D,\mu )$ and $P_{C\cap D}$ is a $\Delta$-optimal predictor scheme for $(C\cap D,\mu )$. Define $P_{C\mid D}$ as the circuit family computing

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

Then, $P_{C\mid D}$ is a $\Delta$-optimal predictor scheme for $(C,\mu \mid D)$.

Definition A.1

Consider $\mu$ a word ensemble and $\{Q_{1,2}^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k,j\in N}$ two circuit families. We say $Q_1$ is $\Delta$-similar to $Q_2$ relative to $\mu$ (denoted $Q_1\underset{\Delta }{\stackrel{\mu }{\simeq }}{Q}_2$) when $E_{{\mu }^k}\left[\right(Q_1^k\left(x\right)-Q_2^k\left(x\right){)}^2]\in \Delta$.

Theorem A.7

Consider $(D,\mu )$ a distributional decision problem, $P$ a $\Delta$-optimal predictor scheme for $(D,\mu )$ and $\{Q^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$ a polynomial size family. Then, $Q$ is a $\Delta$-optimal predictor scheme for $(D,\mu )$ if and only if $P\underset{\Delta }{\stackrel{\mu }{\simeq }}Q$.

Appendix B

Lemma B.1

Consider $(D,\mu )$ a distributional decision problem and $P$ a corresponding $\Delta$-optimal predictor scheme. Then, there is a function $\delta :N^4\to [0,1]$ s.t.

(i) $\delta$ is non-decreasing in the third and fourth arguments.

(ii) For all polynomials $p,q:N^2\to N$, we have $\delta (k,j,p(k,j),q(k,j\left)\right)\in \Delta$.

(iii) for all $k\in N$, $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]$ and $w:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }{Q}^{\ge 0}$ we have

$$E_{{\mu }^k}\left[w\right(x\left)\right(P^{kj}\left(x\right)-{\chi }_D\left(x\right){)}^2]\le E_{{\mu }^k}[w\left(x\right)\left(Q\right(x)-{\chi }_D(x\left){)}^2\right]+(maxw)\delta (k,j,|Q|,|w|)$$

The proof of Lemma B.1 is completely analogous to the proof of Lemma 2 for quasi-optimal predictors and I omit it.

Proof of Theorem A.1

Define $\{w^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }\{0,1\}{\}}_{k,j\in N}$ as the circuits computing

$$w^{kj}\left(x\right):=\theta \left(P^{kj}\right(x)-p_{kj})\theta (q_{kj}-P^{kj}(x\left)\right)$$

$|w^{kj}|$ is bounded by a polynomial since $P^{kj}$ produces binary fractions of polynomial size therefore it is possible to compare them to the fixed numbers $p_{kj},q_{kj}$ using a polynomial size circuit even if the latter have infinite binary expansions.

We have

$${\varphi }_{kj}=\frac{E_{{\mu }^k}\left[w^{kj}\right(x\left)\right({\chi }_D\left(x\right)-P^{kj}\left(x\right)\left)\right]}{E_{{\mu }^k}\left[w^{kj}\right(x\left)\right]}$$

Define ${\psi }_{kj}$ to be ${\varphi }_{kj}$ truncated to the first significant binary digit. Define $\{Q^{kj}:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k,j\in N}$ as the circuits computing

$$Q^{kj}\left(x\right):=\eta \left(P^{kj}\right(x)+{\psi }_{kj})$$

Denote $I\subseteq N^2$ the set of $(k,j)$ for which ${\varphi }_{kj}>2^{-h(k,j)}$. For $(k,j)\in I$, ${\psi }_{kj}$ has binary notation of polynomially bounded size, therefore $|Q^{kj}|$ is bounded by a polynomial for such $(k,j)$.

Applying Lemma B.1 we get

$$\forall (k,j)\in I:E_{{\mu }^k}\left[w^{kj}\right(x\left)\right(P^{kj}\left(x\right)-{\chi }_D\left(x\right){)}^2]\le E_{{\mu }^k}[w^{kj}\left(x\right)\left(Q^{kj}\right(x)-{\chi }_D(x\left){)}^2\right]+\delta (k,j)$$

for $\delta \in \Delta$.

$$\forall (k,j)\in I:E_{{\mu }^k}\left[w^{kj}\right(x\left)\right(\left(P^{kj}\right(x)-{\chi }_D(x){)}^2-(Q^{kj}\left(x\right)-{\chi }_D\left(x\right){)}^2\left)\right]\le \delta (k,j)$$

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

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

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

$$\forall (k,j)\in I:{\psi }_{kj}{E}_{{\mu }^k}\left[w^{kj}\right(x\left)\right(2\left({\chi }_D\right(x)-P^{kj}(x\left)\right)-{\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}_{{\mu }^k}\left[w^{kj}\right(x\left)\right(2\left({\chi }_D\right(x)-P^{kj}(x\left)\right)-\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_{{\mu }^k}\left[w^{kj}\right(x\left)\right({\chi }_D\left(x\right)-P^{kj}\left(x\right)\left)\right]}{E_{{\mu }^k}\left[w^{kj}\right(x\left)\right]}{E}_{{\mu }^k}\left[w^{kj}\right(x\left)\right(2\left({\chi }_D\right(x)-P^{kj}(x\left)\right)-\frac{1}{2}\frac{E_{{\mu }^k}\left[w^{kj}\right(x\left)\right({\chi }_D\left(x\right)-P^{kj}\left(x\right)\left)\right]}{E_{{\mu }^k}\left[w^{kj}\right(x\left)\right]}\left)\right]\le \delta (k,j)$$

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

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

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

$$\forall (k,j)\in I:{\varphi }_{kj}^2\le \frac{4}{3}{\mu }^k\{x\in \{0,1{\}}^{\ast }\mid p_{kj}\le P^{kj}\left(x\right)\le q_{kj}{\}}^{-1}\delta (k,j)$$

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

$$|{\varphi }_{kj}|\le 2^{-h(k,j)}+\sqrt{\frac{4}{3}{\mu }^k\{x\in \{0,1{\}}^{\ast }\mid p_{kj}\le P^{kj}\left(x\right)\le q_{kj}{\}}^{-1}\delta (k,j)}$$

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

Appendix C

The following is a proof of Theorem 1.

Define $ϵ(k,j)$ by

$$ϵ(k,j):=E_{{\mu }^k}\left[\right(P_{D,\mu }^{\ast kj}\left(x\right)-{\chi }_D\left(x\right){)}^2]=\underset{|Q|\le j}{min}{E}_{{\mu }^k}[\left(Q\right(x)-{\chi }_D(x\left){)}^2\right]$$

To prove $P_{D,\mu }^{\ast }$ is ${\Delta }_{avg}^2$-optimal, it enough to consider families $Q$ of the form $Q^{kj}=P_{D,\mu }^{\ast k,q(k,j)}$ for polynomial $q$, since

$$ϵ(k,|Q^{kj}|)\le E_{{\mu }^k}\left[\right(Q^{kj}\left(x\right)-{\chi }_D\left(x\right){)}^2]$$

That is, we need to prove that for any polynomial $q$, $ϵ(k,j)-ϵ(k,max(q(k,j),j\left)\right)\in {\Delta }_{avg}^2$.

Without loss of generality, assume $q(k,j)=k^n{j}^m$ for $m>0$. We are interested in the function

$$\delta \left(k\right):=\frac{\sum _{j=3}^{f\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\left(ϵ\right(k,j)-ϵ(k,k^n{j}^m\left)\right)}{\log \log f\left(k\right)-\log \log 3}$$

This can be rewritten as

$$\delta \left(k\right)=\frac{\sum _{j=3}^{f\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\left(ϵ\right(k,j)-ϵ(k,j^{m+\frac{n\log k}{\log j}}\left)\right)}{\log \log f\left(k\right)-\log \log 3}$$

$$\delta \left(k\right)\le \frac{\sum _{j=3}^{f\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\left(ϵ\right(k,j)-ϵ(k,j^{m+\frac{n\log k}{\log 3}}\left)\right)}{\log \log f\left(k\right)-\log \log 3}$$

The numerator can be recast as an integral

$$\delta \left(k\right)\le \frac{\underset{x=3}{\overset{f\left(k\right)}{\int }}\left(ϵ\right(k,\lfloor x\rfloor )-ϵ(k,\lfloor x{\rfloor }^{m+\frac{n\log k}{\log 3}}\left)\right)d\left(\log \log x\right)}{\log \log f\left(k\right)-\log \log 3}$$

$$\delta \left(k\right)\le \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}$$

$$\delta \left(k\right)\le \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}$$

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

$$\delta \left(k\right)\le \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}$$

$$\delta \left(k\right)\le \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}$$

Since $ϵ\le 1$, we get

$$\delta \left(k\right)\le \frac{\log (m+\frac{n\log k}{\log 3})}{\log \log f\left(k\right)-\log \log 3}$$

Using the assumption on $f$, we conclude that ${lim}_{k\to \infty }\delta \left(k\right)=0$, as needed.