Optimal predictors for global probability measures

post by Vanessa Kosoy (vanessa-kosoy) · 2015-10-06T17:40:19.000Z · LW · GW · 0 comments

Contents

    Results
  New notation
  Definition 1
  Definition 2
  Definition 3
  Theorem 1
  Theorem 2
  Theorem 3
  Definition 4
  Definition 5
  Theorem 4
  Theorem 5
  Theorem 6
  Definition 6
  Theorem 7
  Definition 7
  Note 1
  Theorem 8
  Defintion 8
  Theorem 9
  Theorem 10
    Appendix
  Definition 9
  Lemma 1
  Lemma 2
  Lemma 3
  Lemma 4
  Proof of Lemma 4
  Lemma 5
  Proof of Lemma 5
  Proposition 1
  Proof of Proposition 1
  Proof of Theorem 4
  Lemma 6
  Proof of Lemma 6
  Proposition 2
  Proof of Proposition 2
  Proof of Theorem 8
  Proposition 3
  Proof of Proposition 3
  Proposition 4
  Proof of Proposition 4
  Lemma 7
  Proof of Lemma 7
  Proposition 5
  Proof of Proposition 5
  Proof of Theorem 10
None
No comments

There are two commonly used formalisms in average case complexity theory: problems with a single global probability measure on parameter space or problems with a family of such probability measures. Previous posts about optimal predictors focused on the family approach. In this post we give the formalism for global measures.

Results

New notation

$1$ will denote the one-element set.

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

Definition 1

A unidistributional estimation problem is a pair $(f,\mu )$ where $\mu$ is a probability measure on $\{0,1{\}}^{\ast }$ and $f:\mathrm{supp}\mu \to [0,1]$ is an arbitrary function.

Definition 2

Given appropriate sets $X$, $Y$, consider $P:N\times X\times {\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }Y$, $r:N\to N$ polynomial and $a:N\to \{0,1{\}}^{\ast }$. The triple $\hat{P}=(P,r,a)$ is called a $(poly,log)$-scheme of signature $X\to Y$ when

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

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

A $(poly,log)$-scheme of signature $\{0,1{\}}^{\ast }\to [0,1]$ will also be called a $(poly,log)$-predictor.

Given $j\in N$, $x\in X$, ${\hat{P}}^j\left(x\right)$ will denote the $Y$-valued random variable $P(j,x,y,a(j\left)\right)$ where $y$ is sampled from the probability measure $U^{r\left(j\right)}$. We will also use the notation ${\hat{P}}^j(x,y):=P(j,x,y,a(j\left)\right)$.

---

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

Definition 3

Consider $(f,\mu )$ a unidistributional estimation problem and $\hat{P}=(P,r,a)$ a $(poly,log)$-predictor. $\hat{P}$ is called a $\Delta (poly,log)$-optimal predictor for $(f,\mu )$ when for any $(poly,log)$-predictor $\hat{Q}=(Q,s,b)$, there is $\delta \in \Delta$ s.t.

$$E_{\mu \times U^{r\left(j\right)}}\left[\right({\hat{P}}^j\left(x\right)-f\left(x\right){)}^2]\le E_{\mu \times U^{s\left(j\right)}}[\left({\hat{Q}}^j\right(x)-f(x\left){)}^2\right]+\delta \left(j\right)$$

---

$\Delta (poly,log)$-optimal predictors for unidistributional problems have properties and existence theorems analogical to $\Delta (poly,log)$-optimal predictor schemes, where the role of the rank 2 error space ${\Delta }_{avg}^2$ is taken by the rank 1 error space ${\Delta }_{ll}^1$ (see Definition 8). The theorems are listed below. The proofs of Theorem 4, Theorem 8 (which is stated stronger than previous analogues) and Theorem 10 are given in the appendix. Adapting the other proofs is straightforward.

Theorem 1

Suppose $(j+1{)}^{-1}\in \Delta$. Consider $(f,\mu )$ a unidistributional estimation problem and $\hat{P}=(P,r,a)$ a $\Delta (poly,log)$-optimal predictor for $(f,\mu )$. Suppose $\{p_j\in [0,1]{\}}_{j\in N}$, $\{q_j\in [0,1]{\}}_{j\in N}$ are s.t.

$$\exists ϵ>0\forall j:(\mu \times U^{r\left(j\right)})\left\{\right(x,y)\in {\{0,1{\}}^{\ast }}^2\mid p_j\le {\hat{P}}^j(x,y)\le q_j\}\ge ϵ$$

Define

$${\varphi }_j:=E_{\mu \times U^{r\left(j\right)}}\left[f\right(x)-{\hat{P}}^j(x,y)\mid p_j\le {\hat{P}}^j(x,y)\le q_j]$$

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

Theorem 2

Consider $\mu$ a probability measure on $\{0,1{\}}^{\ast }$ and $f_1,f_2:\mathrm{supp}\mu \to [0,1]$ s.t. $f_1+f_2\le 1$. Suppose ${\hat{P}}_1$ is a $\Delta (poly,log)$-optimal predictor for $(f_1,\mu )$ and ${\hat{P}}_2$ is a $\Delta (poly,log)$-optimal predictor for $(f_2,\mu )$. Then $\eta ({\hat{P}}_1+{\hat{P}}_2)$ is a $\Delta (poly,log)$-optimal predictor for $(f_1+f_2,\mu )$.

Theorem 3

Consider $\mu$ a probability measure on $\{0,1{\}}^{\ast }$ and $f_1,f_2:\mathrm{supp}\mu \to [0,1]$ s.t. $f_1+f_2\le 1$. Suppose ${\hat{P}}_1$ is a $\Delta (poly,log)$-optimal predictor for $(f_1,\mu )$ and $\hat{P}$ is a $\Delta (poly,log)$-optimal predictor for $(f_1+f_2,\mu )$. Then, $\eta (\hat{P}-{\hat{P}}_1)$ is a $\Delta (poly,log)$-optimal predictor for $(f_2,\mu )$.

Definition 4

Fix $\Delta$ an error space of rank 1. A probability measure $\mu$ on $\{0,1{\}}^{\ast }$ is called $\Delta \left(log\right)$-sampleable when there is a $(poly,log)$-scheme $\hat{S}$ of signature $1\to \{0,1{\}}^{\ast }$ such that

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

$\hat{S}$ is called a $\Delta \left(log\right)$-sampler for $\mu$.

Definition 5

Consider $\Delta$ an error space of rank 1. A unidistributional estimation problem $(f,\mu )$ is called $\Delta \left(log\right)$-generatable when there is a $(poly,log)$-scheme of $\hat{G}$ of signature $1\to \{0,1{\}}^{\ast }\times [0,1]$ such that

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

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

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

Theorem 4

Consider $(f_1,{\mu }_1)$, $(f_2,{\mu }_2)$ unidistributional estimation problems with respective $\Delta (poly,log)$-optimal predictors ${\hat{P}}_1$ and ${\hat{P}}_2$. Assume ${\mu }_1$ is $\Delta \left(log\right)$-sampleable and $(f_2,{\mu }_2)$ is $\Delta \left(log\right)$-generatable. Define $\hat{P}$ by ${\hat{P}}^j\left(\right(x_1,x_2\left)\right):={\hat{P}}_1^j\left(x_1\right){\hat{P}}_2^j\left(x_2\right)$. Then, $\hat{P}$ is a $\Delta (poly,log)$-optimal predictor for $(f_1\times f_2,{\mu }_1\times {\mu }_2)$.

Theorem 5

Consider $\mu$ a probability measure on $\{0,1{\}}^{\ast }$ and $f:\mathrm{supp}\mu \to [0,1]$, $D\subseteq \mathrm{supp}\mu$. Assume ${\hat{P}}_D$ is a $\Delta (poly,log)$-optimal predictor for $({\chi }_D,\mu )$ and ${\hat{P}}_{f\mid D}$ is a $\Delta (poly,log)$-optimal predictor for $(f,\mu \mid D)$. Define $\hat{P}$ by ${\hat{P}}^j\left(x\right):={\hat{P}}_D^j\left(x\right){\hat{P}}_{f\mid D}^j\left(x\right)$. Then ${\hat{P}}^j\left(x\right)$ is a $\Delta (poly,log)$-optimal predictor for $({\chi }_{D}f,\mu )$.

Theorem 6

Fix $h$ a polynomial s.t. $2^{-h}\in \Delta$. Consider $\mu$ a probability measure on $\{0,1{\}}^{\ast }$, $f:\mathrm{supp}\mu \to [0,1]$ and $D\subseteq \mathrm{supp}\mu$ non-empty. Assume ${\hat{P}}_D$ is a $\Delta (poly,log)$-optimal predictor for $({\chi }_D,\mu )$ and ${\hat{P}}_{{\chi }_{D}f}$ is a $\Delta (poly,log)$-optimal predictor for $({\chi }_{D}f,\mu )$. Define ${\hat{P}}_{f\mid D}$ by

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

Then, ${\hat{P}}_{f\mid D}$ is a $\Delta (poly,log)$-optimal predictor for $(f,\mu \mid D)$.

Definition 6

Consider $\mu$ a probability measure on $\{0,1{\}}^{\ast }$ and ${\hat{Q}}_1=(Q_1,s_1,b_1)$, ${\hat{Q}}_2=(Q_2,s_2,b_2)$ $(poly,log)$-predictors. 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 \times U^{s_1(k,j)}\times U^{s_2(k,j)}}\left[\right({\hat{Q}}_1^j(x,y_1)-{\hat{Q}}_2^j(x,y_2{)}^2]\in \Delta$.

Theorem 7

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

Definition 7

Consider $(f,\mu )$, $(g,\nu )$ unidistributional estimation problems, $\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ a $(poly,log)$-scheme of signature $\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$. $\hat{\zeta }$ is called a $\Delta$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ when the following conditions hold:

(i) $$E_{\mu \times U^{r_{\zeta }\left(j\right)}}\left[\right(g\left({\hat{\zeta }}^j\right(x\left)\right)-f\left(x\right){)}^2]\in \Delta$$

(ii) $$P{r}_{\mu \times U^{r_{\zeta }\left(j\right)}}\left[\nu \right({\hat{\zeta }}^j\left(x\right))=0]\in \Delta$$

(iii) There is $M>0$ and $\hat{R}=(R,r_R,a_R)$ a $(poly,log)$-scheme of signature $\{0,1{\}}^{\ast }\to Q\cap [0,M]$ s.t.

$$E_{\nu \times U^{r_R\left(j\right)}}\left[\right({\hat{R}}^j\left(y\right)-\frac{P{r}_{\mu \times U^{r_{\zeta }\left(j\right)}}\left[{\hat{\zeta }}^j\right(x)=y]}{\nu \left(y\right)}{)}^2]\in \Delta$$

(iv) There is a $(poly,log)$-scheme $\hat{\xi }=(\xi ,r_{\xi },a_{\xi })$ of signature $\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ s.t.

$$E_{\mu \times U^{r_{\zeta }\left(k\right)}}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}|P{r}_{U^{r_{\xi }\left(k\right)}}\right[{\hat{\xi }}^k\left({\hat{\zeta }}^k\right(x,z),w)=x^{\prime }]-P{r}_{\mu \times U^{r_{\zeta }\left(k\right)}}[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^k(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^k(x,z)\left]|\right]\in \Delta$$

Such $\hat{\xi }$ is called a $\Delta$-pseudo-inverse of $\hat{\zeta }$.

Note 1

The conditions of Definition 7 are weaker than corresponding definitions in previous posts in the sense that exact equalities were replaced by approximate equalities with error bounds related to $\Delta$. However, analogous relaxations can be done in the "multidistributional" theory too.

Theorem 8

Suppose $(j+1{)}^{-1}\in \Delta$. Consider $(f,\mu )$, $(g,\nu )$ unidistributional estimation problems, $\hat{\zeta }$ a $\Delta$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ and ${\hat{P}}_g$ a $\Delta (poly,log)$-optimal predictor for $(g,\nu )$. Define ${\hat{P}}_f$ by ${\hat{P}}_f^j\left(x\right):={\hat{P}}_g^j\left({\hat{\zeta }}^j\right(x\left)\right)$. Then, ${\hat{P}}_f$ is a $\Delta (poly,log)$-optimal predictor for $(f,\mu )$.

Defintion 8

${\Delta }_{ll}^1$ is the set of bounded functions $\delta :N\to R^{\ge 0}$ s.t.

$$\exists ϵ>0:\underset{j\to \infty }{lim}\left(\log \log j{)}^{ϵ}\delta \right(j)=0$$

It is easily seen that ${\Delta }_{ll}^1$ is a rank 1 error space.

Theorem 9

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

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

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

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

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

Theorem 10

There is an oracle machine $\Lambda$ that accepts an oracle of signature $O: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 $O^k\left(x\right)$ for $|x|=r\left(k\right)$ and computes a function of signature $N\times {\{0,1{\}}^{\ast }}^2\to [0,1]$ s.t. for any $(f,\mu )$ a unidistributional estimation problem and $\hat{G}$ a corresponding ${\Delta }_{ll}^1\left(log\right)$-generator, $\Lambda \left[\hat{G}\right]$ is a ${\Delta }_{ll}^1(poly,log)$-optimal predictor for $(f,\mu )$.

---

The following is the description of $\Lambda$. Consider $O: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 [O,r{]}^j(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 $j^2$ "test runs". At test run $i$, we generate $(x_i\in \{0,1{\}}^{\ast },t_i\in [0,1\left]\right)$ by evaluating $O^j\left(y_i\right)$ for $y_i$ sampled from $U^{r\left(j\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}{j^2}{\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.

Appendix

Definition 9

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

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

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

Lemma 1

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

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

The proof is analogous to the case of $\Delta (poly,log)$-optimal predictor schemes and we omit it.

Lemma 2

Suppose $(j+1{)}^{-1}\in \Delta$. Fix $(f,\mu )$ a unidistributional estimation problem and $\hat{P}=(P,r,a)$ a corresponding $\Delta (poly,log)$-optimal predictor. Consider $\hat{Q}=(Q,s,b)$ a $(poly,log)$-predictor, $M>0$ and $\hat{w}=(w,r_w,a_w)$ a $(poly,log)$-scheme of signature $\{0,1{\}}^{\ast }\to Q\cap [0,M]$. Assume $r_w\left(j\right)\ge max\left(r\right(j),s(j\left)\right)$. Then there is $\delta \in \Delta$ s.t.

$$E_{\mu \times U^{r_w\left(j\right)}}\left[{\hat{w}}^j\right(x,y\left)\right({\hat{P}}^j(x,y_{\le r\left(j\right)})-f\left(x\right){)}^2]\le E_{\mu \times U^{r_w\left(j\right)}}[{\hat{w}}^j(x,y)\left({\hat{Q}}^j\right(x,y_{\le s\left(j\right)})-f(x\left){)}^2\right]+\delta \left(j\right)$$

The proof is analogous to the case of $\Delta (poly,log)$-optimal predictor schemes and we omit it.

Lemma 3

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

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

Conversely, consider $M\in Q$ and $\hat{P}$ a $(poly,log)$-scheme of signature $\{0,1{\}}^{\ast }\to Q\cap [-M,+M]$. Suppose that for any $(poly,log)$-scheme $\hat{Q}=(Q,s,b)$ of signature $\{0,1{\}}^{\ast }\to Q\cap [-M-1,+M]$ we have

$$|E_{\mu \times U^{s\left(j\right)}\times U^{r\left(j\right)}}\left[{\hat{Q}}^j\right({\hat{P}}^j-f\left)\right]|\in \Delta$$

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

The proof is analogous to the case of $\Delta (poly,log)$-optimal predictor schemes and we omit it.

Lemma 4

Consider $\mu$ a probability measure on $\{0,1{\}}^{\ast }$. Suppose $\hat{S}$ is a $\Delta \left(log\right)$-sampler for $\mu$. Then, $\exists \delta \in \Delta$ s.t. for any bounded function $f:\mathrm{supp}\mu \to R$

$$|E_{\mu }\left[f\right]-E\left[f\right({\hat{S}}^k\left)\right]|\le (sup|f|)\delta \left(k\right)$$

Proof of Lemma 4

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

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

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

$$|E_{\mu }\left[f\right]-E\left[f\right({\hat{S}}^k\left)\right]|\le (sup|f|)\sum _{x\in \{0,1{\}}^{\ast }}|\mu \left(x\right)-Pr[{\hat{S}}^k=x]|$$

Since $\hat{S}$ is a $\Delta \left(log\right)$-sampler, we get the desired result.

Lemma 5

Consider a family of sets $\{X^k{\}}_{k\in N}$ and family of probability measures $\{{\mu }^k{\}}_{k\in N}$ on $X^k$. Denote $Y:={\bigsqcup }_k\mathrm{supp}{\mu }^k$. Consider $f:Y\to R$ a function and $g:Y\to R$ a bounded function. Suppose that

$$E_{{\mu }^k}\left[f\right(x{)}^2]\in \Delta$$

Then it follows that

$$|E_{{\mu }^k}\left[g\right(x\left)f\right(x\left)\right]|\in \Delta$$

Proof of Lemma 5

$$|E_{{\mu }^k}\left[g\right(x\left)f\right(x\left)\right]|\le E_{{\mu }^k}\left[|g\right(x\left)f\right(x\left)|\right]$$

$$|E_{{\mu }^k}\left[g\right(x\left)f\right(x\left)\right]|\le (sup|g|)E_{{\mu }^k}\left[|f\right(x\left)|\right]$$

$$|E_{{\mu }^k}\left[g\right(x\left)f\right(x\left)\right]|\le (sup|g|)\sqrt{E_{{\mu }^k}\left[f\right(x{)}^2]}$$

Proposition 1

Consider $(f,\mu )$ a unidistributional estimation problem, $\hat{G}$ a $\Delta \left(log\right)$-generator for $(f,\mu )$ and $g:\mathrm{supp}\mu \to R$ a bounded function. Then

$$|E_{\mu }\left[gf\right]-E\left[g\right({\hat{G}}_1^k\left){\hat{G}}_2^k\right]|\in \Delta$$

Proof of Proposition 1

By Lemma 4 we have

$$|E_{\mu }\left[gf\right]-E\left[g\right({\hat{G}}_1^k\left)f\right({\hat{G}}_1^k\left)\right]|\in \Delta$$

By property (ii) of generators and Lemma 5 we have

$$|E\left[g\right({\hat{G}}_1^k\left){\hat{G}}_2^k\right]-E\left[g\right({\hat{G}}_1^k\left)f\right({\hat{G}}_1^k\left)\right]|\in \Delta$$

Combining the two we get the desired result.

Proof of Theorem 4

We have

$$\hat{P}\left(\right(x_1,x_2\left)\right)-(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 $(poly,log)$-scheme $\hat{Q}=(Q,s,b)$ of signature $\{0,1{\}}^{\ast }\to Q\cap [-1,+1]$

$$|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){\hat{P}}_1\right(x_1)-f_1(x_1\left)\right)f_2\left(x_2\right)]|+|E[\hat{Q}\left(\right(x_1,x_2\left)\right){\hat{P}}_1\left(x_1\right)\left({\hat{P}}_2\right(x_2)-f_2(x_2\left)\right)]|$$

By Lemma 3, it is sufficient to show an appropriate bound for each of the terms on the right hand side. Suppose $\hat{G}=(G,r_G,a_G)$ is a $\Delta \left(log\right)$-generator for $(f_2,{\mu }_2)$. Applying Proposition 1 to the first term, we get

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

where ${\delta }_2^1\in {\Delta }^1$.

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

Applying Lemma 3 for $P_1$, we get

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

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

Suppose $(S,r_S,a_S)$ is a $\Delta \left(log\right)$-sampler for ${\mu }_1$. Applying Lemma 4 to the second term, we get

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

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

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

Applying Lemma 3 for $P_2$, we get

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

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

Lemma 6

Consider a family of sets $\{X^k{\}}_{k\in N}$ and family of probability measures $\{{\mu }^k{\}}_{k\in N}$ on $X^k$. Denote $Y:={\bigsqcup }_k\mathrm{supp}{\mu }^k$. Consider $f_1,f_2:Y\to R$ bounded functions and $\{g_{\alpha }:Y\to R{\}}_{\alpha \in I}$ a uniformly bounded family of functions indexed by some set $I$. Suppose that

$$E_{{\mu }^k}\left[\right(f_1\left(x\right)-f_2\left(x\right){)}^2]\in \Delta$$

Then there is $\delta \in \Delta$ s.t.

$$\forall \alpha \in I:|E_{{\mu }^k}\left[\right(g_{\alpha }\left(x\right)-f_1\left(x\right){)}^2-\left(g_{\alpha }\right(x)-f_2(x\left){)}^2\right]|\le \delta \left(k\right)$$

Proof of Lemma 6

$$\left(g_{\alpha }\right(x)-f_1(x){)}^2-(g_{\alpha }\left(x\right)-f_2\left(x\right){)}^2=\left(2g_{\alpha }\right(x)-f_1(x)-f_2(x\left)\right)\left(f_2\right(x)-f_1(x\left)\right)$$

$$|E_{{\mu }^k}\left[\right(2g_{\alpha }\left(x\right)-f_1\left(x\right)-f_2\left(x\right)\left)\right(f_2\left(x\right)-f_1\left(x\right)\left)\right]|\le sup(|2g_{\alpha }-f_1-f_2|)\sqrt{E_{{\mu }^k}\left[\right(f_1\left(x\right)-f_2\left(x\right){)}^2]}$$

Proposition 2

Consider $(f,\mu )$, $(g,\nu )$ unidistributional estimation problems. Suppose $\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ is a $\Delta$-pseudo-invertible reduction of $(f,\mu )$ to $(g,\nu )$ and $\hat{\xi }=(\xi ,r_{\xi },a_{\xi })$ is it's $\Delta$-pseudo-inverse. Then there is $\delta \in \Delta$ s.t. for any bounded function $h:{\{0,1{\}}^{\ast }}^2\to R$

$$|E_{\mu \times U^{r_{\zeta }\left(j\right)}\times U^{r_{\xi }\left(j\right)}}\left[h\right({\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w),{\hat{\zeta }}^j(x,z)\left)\right]-E_{\mu \times U^{r_{\zeta }\left(j\right)}}\left[h\right(x,{\hat{\zeta }}^j(x,z)\left)\right]|\le (sup|h|)\delta \left(j\right)$$

Proof of Proposition 2

Denote ${\mu }_{\zeta }^j:=\mu \times U^{r_{\zeta }\left(j\right)}$. According to the definitive property of $\hat{\xi }$

$$E_{{\mu }_{\zeta }^j}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}|P{r}_{U^{r_{\xi }\left(j\right)}}\right[{\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w)=x^{\prime }]-P{r}_{{\mu }_{\zeta }^j}[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^j(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^j(x,z)\left]|\right]=\delta \left(j\right)$$

where $\delta \in \Delta$. Therefore

$$E_{{\mu }_{\zeta }^j}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}|\right(P{r}_{U^{r_{\xi }\left(j\right)}}\left[{\hat{\xi }}^j\right({\hat{\zeta }}^j(x,z),w)=x^{\prime }]-P{r}_{{\mu }_{\zeta }^j}[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^j(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^j(x,z\left)\right]\left)h\right(x^{\prime },{\hat{\zeta }}^j(x,z)\left)|\right]\le \left(sup|h|\right)\delta \left(j\right)$$

$$|E_{{\mu }_{\zeta }^j}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}\right(P{r}_{U^{r_{\xi }\left(j\right)}}\left[{\hat{\xi }}^j\right({\hat{\zeta }}^j(x,z),w)=x^{\prime }]-P{r}_{{\mu }_{\zeta }^j}[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^j(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^j(x,z\left)\right]\left)h\right(x^{\prime },{\hat{\zeta }}^j(x,z)\left)\right]|\le \left(sup|h|\right)\delta \left(j\right)$$

$$|E_{{\mu }_{\zeta }^j}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}Pr\right[{\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w)=x^{\prime }\left]h\right(x^{\prime },{\hat{\zeta }}^j(x,z)\left)\right]-E_{{\mu }_{\zeta }^j}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}P{r}_{{\mu }_{\zeta }^j}\right[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^j(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^j(x,z)\left]h\right(x^{\prime },{\hat{\zeta }}^j(x,z)\left)\right]|\le \left(sup|h|\right)\delta \left(j\right)$$

$$|E_{{\mu }_{\zeta }^j\times U^{r_{\xi }\left(j\right)}}\left[h\right({\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w),{\hat{\zeta }}^j(x,z)\left)\right]-E_{{\mu }_{\zeta }^j}\left[\sum _{x^{\prime }\in \{0,1{\}}^{\ast }}P{r}_{{\mu }_{\zeta }^j}\right[x^{\prime \prime }=x^{\prime }\mid {\hat{\zeta }}^j(x^{\prime \prime },z^{\prime })={\hat{\zeta }}^j(x,z)\left]h\right(x^{\prime },{\hat{\zeta }}^j(x,z)\left)\right]|\le \left(sup|h|\right)\delta \left(j\right)$$

$$|E_{{\mu }_{\zeta }^j\times U^{r_{\xi }\left(j\right)}}\left[h\right({\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w),{\hat{\zeta }}^j(x,z)\left)\right]-E_{{\mu }_{\zeta }^j}\left[E_{{\mu }_{\zeta }^j}\right[h(x^{\prime },{\hat{\zeta }}^j(x,z\left)\right)\mid {\hat{\zeta }}^j(x^{\prime },z^{\prime })={\hat{\zeta }}^j(x,z)\left]\right]|\le \left(sup|h|\right)\delta \left(j\right)$$

$$|E_{{\mu }_{\zeta }^j\times U^{r_{\xi }\left(j\right)}}\left[h\right({\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w),{\hat{\zeta }}^j(x,z)\left)\right]-E_{{\mu }_{\zeta }^j}\left[E_{{\mu }_{\zeta }^j}\right[h(x^{\prime },{\hat{\zeta }}^j(x^{\prime },z^{\prime }\left)\right)\mid {\hat{\zeta }}^j(x^{\prime },z^{\prime })={\hat{\zeta }}^j(x,z)\left]\right]|\le \left(sup|h|\right)\delta \left(j\right)$$

$$|E_{{\mu }_{\zeta }^j\times U^{r_{\xi }\left(j\right)}}\left[h\right({\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x,z),w),{\hat{\zeta }}^j(x,z)\left)\right]-E_{{\mu }_{\zeta }^j}\left[h\right(x,{\hat{\zeta }}^j(x,z)\left)\right]|\le \left(sup|h|\right)\delta \left(j\right))$$

Proof of Theorem 8

Consider ${\hat{Q}}_f=(Q_f,s_f,b_f)$ a $(poly,log)$-predictor. Let ${\hat{Q}}_g=(Q_g,s_g,b_g)$ be the $(poly,log)$-predictor defined by

$${\hat{Q}}_g^j\left(x\right):={\hat{Q}}_f^j\left({\hat{\xi }}^j\right(x\left)\right)$$

Applying Lemma 2 we get

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{r_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{P}}_g^j\left(y\right)-g\left(y\right){)}^2]\le E_{\nu \times U^{r_R\left(j\right)}\times U^{s_g\left(j\right)}}[{\hat{R}}^j\left(y\right)\left({\hat{Q}}_g^j\right(y)-g(y\left){)}^2\right]+\delta \left(j\right)$$

where $\delta \in \Delta$.

Using the definitive property of $\hat{R}$ we can apply Lemma 5 to the left hand side and get

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{r_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{P}}_g^j\left(y\right)-g\left(y\right){)}^2]=E_{\nu \times U^{r_g\left(j\right)}}[\frac{P{r}_{\mu \times U^{r_{\zeta }\left(j\right)}}\left[{\hat{\zeta }}^j\right(x)=y]}{\nu \left(y\right)}\left({\hat{P}}_g^j\right(y)-g(y\left){)}^2\right]+{\gamma }_R\left(j\right)$$

where $|{\gamma }_R|\in \Delta$. Using property (ii) of pseudo-invertible reductions, we get

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{r_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{P}}_g^j\left(y\right)-g\left(y\right){)}^2]=E_{\mu \times U^{r_g\left(j\right)}\times U^{r_{\zeta }\left(j\right)}}[\left({\hat{P}}_g^j\right({\hat{\zeta }}^j\left(x\right))-g({\hat{\zeta }}^j\left(x\right)\left){)}^2\right]+{\gamma }_R\left(j\right)$$

Using the definition of ${\hat{P}}_f$ and Lemma 6 applied via property (i) of pseudo-invertible reductions, we get

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{r_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{P}}_g^j\left(y\right)-g\left(y\right){)}^2]=E_{\mu \times U^{r_g\left(j\right)}\times U^{r_{\zeta }\left(j\right)}}[\left({\hat{P}}_f^j\right(x)-f(x\left){)}^2\right]+{\gamma }_{\zeta }\left(j\right)+{\gamma }_R\left(j\right)$$

where $|{\gamma }_{\zeta }|\in \Delta$.

Using the definitive property of $\hat{R}$, Lemma 5 and property (ii) of pseudo-invertible reductions on the right-hand side, we get

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{s_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{Q}}_g^j\left(y\right)-g\left(y\right){)}^2]=E_{\mu \times U^{s_f\left(j\right)}\times U^{r_{\zeta }\left(j\right)}\times U^{r_{\xi }\left(j\right)}}[\left({\hat{Q}}_f^j\right({\hat{\xi }}^j\left({\hat{\zeta }}^j\right(x\left)\right))-g({\hat{\zeta }}^j\left(x\right)\left){)}^2\right]+{\gamma }_R^{\prime }\left(j\right)$$

where $|{\gamma }_R^{\prime }|\in \Delta$. Applying Proposition 2

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{s_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{Q}}_g^j\left(y\right)-g\left(y\right){)}^2]=E_{\mu \times U^{s_f\left(j\right)}\times U^{r_{\zeta }\left(j\right)}}[\left({\hat{Q}}_f^j\right(x)-g({\hat{\zeta }}^j\left(x\right)\left){)}^2\right]+{\gamma }_{\xi }\left(j\right)+{\gamma }_R^{\prime }\left(j\right)$$

where $|{\gamma }_{\xi }|\in \Delta$. Applying Lemma 6 via property (i) of pseudo-invertible reductions

$$E_{\nu \times U^{r_R\left(j\right)}\times U^{s_g\left(j\right)}}\left[{\hat{R}}^j\right(y\left)\right({\hat{Q}}_g^j\left(y\right)-g\left(y\right){)}^2]=E_{\mu \times U^{s_f\left(j\right)}}[\left({\hat{Q}}_f^j\right(x)-f(x\left){)}^2\right]+{\gamma }_{\zeta }^{\prime }\left(j\right)+{\gamma }_{\xi }\left(j\right)+{\gamma }_R^{\prime }\left(j\right)$$

Putting everything together

$$E_{\mu \times U^{r_g\left(j\right)}\times U^{r_{\zeta }\left(j\right)}}\left[\right({\hat{P}}_f^j\left(x\right)-f\left(x\right){)}^2]\le E_{\mu \times U^{s_f\left(j\right)}}[\left({\hat{Q}}_f^j\right(x)-f(x\left){)}^2\right]+{\delta }^{\prime }\left(j\right)$$

for ${\delta }^{\prime }\in \Delta$.

Proposition 3

Consider $a>1$ and $\delta :[a,\infty )\to R^{\ge 0}$ a non-increasing function. Suppose that

$${\int }_a^{\infty }\frac{\delta \left(x\right)}{x\log x}dx<\infty$$

Then

$$\underset{x\to \infty }{lim}\left(\log \log x\right)\delta \left(x\right)=0$$

Proof of Proposition 3

Assume to the contrary that there is $ϵ>0$ and an unbounded sequence $\{x_i\in [a,\infty ){\}}_{i\in N}$ s.t.

$$\left(\log \log x_i\right)\delta \left(x_i\right)\ge ϵ$$

Define $y_i:=2^{\sqrt{\log x_i}}$. For any $x\in [y_i,x_i]$ we have

$$\delta \left(x\right)\ge \delta \left(x_i\right)\ge \frac{ϵ}{\log \log x_i}=\frac{ϵ}{2\log \log y_i}\ge \frac{ϵ}{2\log \log x}$$

Therefore

$${\int }_{y_i}^{x_i}\frac{\delta \left(x\right)}{x\log x}dx\ge \frac{ϵ}{2}{\int }_{y_i}^{x_i}\frac{dx}{x\log x\log \log x}=\frac{ϵ}{2}(\log \log \log x_i-\log \log \log y_i)=\frac{ϵ}{2}$$

Since we can choose an infinite number of non-overlapping intervals of the form $[y_i,x_i]$, we reach the contradiction

$${\int }_a^{\infty }\frac{\delta \left(x\right)}{x\log x}dx=\infty$$

Proposition 4

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

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

(ii)For any non-increasing function $ϵ:N\to [0,1]$ we have

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

Proof of Proposition 4

Given polynomials $q_1,q_2:N\to N$ s.t. $q_1\left(j\right)\ge q_2\left(j\right)$ for $j\gg 0$, the proposition for $q_1$ implies the proposition for $q_2$ by setting

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

Therefore, it is enough to prove to proposition for polynomials of the form $q\left(j\right)=j^m$ for $m>0$.

We have

$${\int }_{x=3}^{3^m}ϵ(\lfloor x\rfloor )d\left(\log \log x\right)\le {\int }_{x=3}^{3^m}d\left(\log \log x\right)=\log m$$

For any $M>0$

$${\int }_{x=3}^{3^m}ϵ(\lfloor x\rfloor )d\left(\log \log x\right)-{\int }_{x=M}^{M^m}ϵ(\lfloor x\rfloor )d\left(\log \log x\right)\le \log m$$

$${\int }_{x=3}^Mϵ(\lfloor x\rfloor )d\left(\log \log x\right)-{\int }_{x=3^m}^{M^m}ϵ(\lfloor x\rfloor )d\left(\log \log x\right)\le \log m$$

$${\int }_{x=3}^Mϵ(\lfloor x\rfloor )d\left(\log \log x\right)-{\int }_{x=3}^Mϵ(\lfloor x^m\rfloor )d\left(\log \log x\right)\le \log m$$

$${\int }_{x=3}^M\left(ϵ\right(\lfloor x\rfloor )-ϵ(\lfloor x^m\rfloor \left)\right)d\left(\log \log x\right)\le \log m$$

$${\int }_{x=3}^{\infty }\left(ϵ\right(\lfloor x\rfloor )-ϵ(\lfloor x^m\rfloor \left)\right)d\left(\log \log x\right)\le \log m$$

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

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

It follows that

$${\int }_{x=3}^{\infty }\left(ϵ\right(\lfloor x\rfloor )-\sum _i{\lambda }_q(\lfloor x\rfloor ,i\left)ϵ\right(\lfloor x{\rfloor }^m+i\left)\right)d\left(\log \log x\right)\le \log m$$

$${\int }_3^{\infty }\frac{ϵ(\lfloor x\rfloor )-{\sum }_i{\lambda }_q(\lfloor x\rfloor ,i)ϵ(\lfloor x{\rfloor }^m+i)}{x\log x}dx\le \log m$$

Applying Proposition 3, we get the desired result.

Lemma 7

Consider $(f,\mu )$ a unidistributional estimation problem, $\hat{P}=(P,r,a)$, $\hat{Q}=(Q,s,b)$ $(poly,log)$-predictors. Suppose $p:N\to N$ a polynomial and $\delta \in {\Delta }_{ll}^1$ are s.t.

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

Then $\exists {\delta }^{\prime }\in {\Delta }_{ll}^1$ s.t.

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

Proof of Lemma 7

Define $ϵ\left(j\right):={sup}_{k\ge j}E\left[\right({\hat{P}}^k-f{)}^2]$.

By Proposition 4 we have

$$\tilde{\delta }\left(j\right):=ϵ\left(j\right)-\sum _i{\lambda }_p(j,i)ϵ\left(p\right(j)+i)\in {\Delta }_{ll}^1$$

$$ϵ\left(j\right)=\sum _i{\lambda }_p(j,i)ϵ\left(p\right(j)+i)+\tilde{\delta }\left(j\right)$$

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

$$ϵ\left(j\right)\le E\left[\right({\hat{Q}}^j-f{)}^2]+\delta (j)+\tilde{\delta }(j)$$

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

Proposition 5

Consider $\delta \in {\Delta }_{ll}^1$. Define ${\delta }^{\prime }\left(j\right):={sup}_{k\ge j}\delta \left(k\right)$. Then, ${\delta }^{\prime }\in {\Delta }_{ll}^1$.

Proof of Proposition 5

Suppose $\alpha$ is s.t. ${lim}_{j\to \infty }\left(\log \log j{)}^{\alpha }\delta \right(j)=0$. We claim that ${lim}_{j\to \infty }\left(\log \log j{)}^{\alpha }{\delta }^{\prime }\right(j)=0$. Assume to the contrary that for some $ϵ>0$ we have an unbounded sequence $\{n_i{\}}_{i\in N}$ s.t. $\left(\log \log n_i{)}^{\alpha }{\delta }^{\prime }\right(n_i)\ge ϵ$. We can then choose $\{m_i{\}}_{i\in N}$ s.t. $m_i\ge n_i$ and $\left(\log \log n_i{)}^{\alpha }\delta \right(m_i)\ge \frac{ϵ}{2}$. But this implies $\left(\log \log m_i{)}^{\alpha }\delta \right(m_i)\ge \frac{ϵ}{2}$ which is a contradiction.

Proof of Theorem 10

Consider $\hat{P}=(P,r,a)$ a $(poly,log)$-predictor. Choose $p:N\to N$ a non-constant polynomial s.t. evaluating $\Lambda [G{]}^{p\left(j\right)}$ involves running ${\hat{P}}^j$ until it halts "naturally" (such $p$ exists because $\hat{P}$ runs in at most polynomial time and has at most logarithmic advice). Given $i,j\in N$, consider the execution of $\Lambda [G{]}^{p\left(j\right)+i}$. The standard deviation of $ϵ\left({\hat{P}}^j\right)$ with respect to the internal coin tosses of $\Lambda$ is at most $\left(p\right(j)+i{)}^{-1}$. Applying Lemma 6 followed by Lemma 4, the expectation value is $E\left[\right({\hat{P}}^j-f{)}^2]+{\gamma }_P$ where $|{\gamma }_P|\le \delta \left(p\right(j)+i)$ for $\delta \in {\Delta }_{ll}^1$. By Chebyshev's inequality,

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

Hence

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

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

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

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

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

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

By Proposition 5, we can assume $\delta$ is non-increasing without loss of generality. Therefore

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

Applying Lemma 7 we get the desired result.

0 comments

Comments sorted by top scores.