Improved error space for universal optimal predictor schemes

[Vanessa Kosoy]

We construct an error space which is smaller than ${\Delta }_{avg}^2$ but admits analogous existence theorems for optimal predictor schemes.

Results

Construction

Given $\varphi \in \Phi$ we define ${\Delta }_{\varphi }^1$ to be the set of functions $\delta :N\to R^{\ge 0}$ s.t. $\exists ϵ>0:{lim}_{k\to \infty }\varphi \left(k{)}^{ϵ}\delta \right(k)=0$. It is easily seen ${\Delta }_{\varphi }^1$ is an error space.

Given $\varphi \in \Phi$, denote $t_{\varphi }\left(k\right):=\lfloor 2^{(\log k{)}^{\varphi \left(k\right)}}\rfloor$. We define ${\Delta }_{ll,\varphi }^2$ to be the set of bounded functions $\delta :N^2\to R^{\ge 0}$ s.t. for any ${\varphi }^{\prime }\in \Phi$, if ${\varphi }^{\prime }\le \varphi$ then

$$\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j)}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\in {\Delta }_{{\varphi }^{\prime }}^1$$

We define ${\Delta }_{ll}^2:={\bigcap }_{\varphi \in \Phi }{\Delta }_{ll,\varphi }^2$.

Proposition 1

${\Delta }_{ll,\varphi }^2$ is an error space for any $\varphi \in \Phi$. ${\Delta }_{ll}^2$ is an error space.

Proposition 2

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 }_{ll}^2$$

---

The proofs of Propositions 1 and 2 are in the Appendix. The following are proved using exactly like the analogous statements for ${\Delta }_{avg}^2$ and we omit the proofs.

Lemma

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 }_{ll}^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)$$

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

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 $\varphi \in \Phi$, $(f,\mu )$ a distributional estimation problem and $G:=(S,F,r^S,a^S)$ a corresponding ${\Delta }_{\varphi }^1\left(log\right)$-generator, $\Lambda \left[G\right]$ is a ${\Delta }_{ll,\varphi }^2(poly,log)$-optimal predictor scheme for $(f,\mu )$.

Appendix

Proof of Proposition 1

The only slightly non-obvious condition is (v). We have

$$\underset{k\to \infty }{limsup}\varphi \left(k{)}^{ϵ\alpha }{E}_{{\kappa }_{\varphi }^k}\right[\delta (k,j{)}^{\alpha }]\le \underset{k\to \infty }{limsup}\varphi \left(k{)}^{ϵ\alpha }{E}_{{\kappa }_{\varphi }^k}\right[\delta (k,j){]}^{\alpha }$$

$$\underset{k\to \infty }{limsup}\varphi \left(k{)}^{ϵ\alpha }{E}_{{\kappa }_{\varphi }^k}\right[\delta (k,j{)}^{\alpha }]\le \left(\underset{k\to \infty }{limsup}\varphi \right(k{)}^{ϵ}{E}_{{\kappa }_{\varphi }^k}\left[\delta \right(k,j\left)\right]{)}^{\alpha }$$

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

Proof of Proposition 2

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+n\log k}$ for $m>0$.

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

$$\underset{k\to \infty }{lim}\varphi (k{)}^{-\frac{1}{2}}=0$$

$$\underset{k\to \infty }{lim}\varphi (k{)}^{\frac{1}{2}}\frac{\log \log k}{\varphi \left(k\right)\log \log k}=0$$

$$\underset{k\to \infty }{lim}\varphi (k{)}^{\frac{1}{2}}\frac{\log (m+n\log k)}{\varphi \left(k\right)\log \log k}=0$$

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

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

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

Similarly

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

The last two equations imply that

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

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

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

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

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

$$\underset{x=j}{\overset{j+1}{\int }}ϵ(k,\lfloor x^{m+n\log k}\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+n\log k}+i)$$

It follows that

$$\underset{x=j}{\overset{j+1}{\int }}ϵ(k,\lfloor x^{m+n\log k}\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+n\log k}+i)d\left(\log \log x\right)$$

$$\underset{k\to \infty }{lim}\varphi (k{)}^{\frac{1}{2}}\frac{\underset{x=2}{\overset{t_{\varphi }\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+n\log k}+i\left)\right)d\left(\log \log x\right)}{\varphi \left(k\right)\log \log k}=0$$

$$\underset{k\to \infty }{lim}\varphi (k{)}^{\frac{1}{2}}\frac{{\sum }_{j=2}^{t_{\varphi }\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+n\log k}+i\left)\right)}{\varphi \left(k\right)\log \log k}=0$$

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