Stability of optimal predictor schemes under a broader class of reductions

post by Vanessa Kosoy (vanessa-kosoy) · 2016-04-30T14:17:35.000Z · LW · GW · 0 comments

Contents

  Definition 1
  Definition 2
  Theorem
  Proposition 1
  Proposition 2
  Proof of Proposition 2
  Proof of Theorem
None
No comments

We define a new class of reductions which preserve optimal predictor schemes, generalizing the previous notion of pseudo-invertible reductions. These are reductions that preserve the estimation problem on average but allow for large variance.

Definition 1

Fix an error space $\Delta$ of rank 2. Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems, $\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ a $\{0,1{\}}^{\ast }$-valued $(poly,log)$-bischeme. $\hat{\zeta }$ is called a $\Delta$-pseudo-invertible weak reduction of $(f,\mu )$ to $(g,\nu )$ when there is a polynomial $p:N\to N$ s.t. the following conditions hold:

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

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

(iii) There is $M>0$ and $\hat{R}=(R,r_R,a_R)$ a $Q\cap [0,M]$-valued $(poly,log)$-bischeme s.t.

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

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

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

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

$\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ a $\{0,1{\}}^{\ast }$-valued $(poly,log)$-scheme is called a $\Delta$-pseudo-invertible weak reduction of $(f,\mu )$ to $(g,\nu )$ when it becomes such when adding trivial dependence on $j$.

Definition 2

An error space $\Delta$ of rank 2 is called stable when for any non-constant polynomial $p:N\to N$ and $\delta \in \Delta$, the function ${\delta }^{\prime }(k,j):=\delta \left(p\right(k),j)$ is in $\Delta$.

Theorem

Fix $\Delta$ a stable error space of rank 2. Suppose there is a polynomial $h:N^2\to N$ s.t. $h^{-1}\in \Delta$. Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems, $\hat{\zeta }$ a $\Delta$-pseudo-invertible weak reduction of $(f,\mu )$ to $(g,\nu )$ and ${\hat{P}}_g$ a $\Delta (poly,log)$-optimal predictor scheme for $(g,\nu )$. Define ${\hat{P}}_f$ by

$${\hat{P}}_f^{kj}(x,y_1{y}_2\dots y_{h(k,j)}{z}_1{z}_2\dots z_{h(k,j)}):=\frac{1}{h(k,j)}\sum _{i=1}^{h(k,j)}{\hat{P}}_g^{p\left(k\right),j}\left({\hat{\zeta }}^{kj}\right(x,y_i),z_i)$$

Here, we assume the lengths of the $y_i$ and $z_i$ are compatible with $\hat{\zeta }$ and ${\hat{P}}_g$ respectively. Then, ${\hat{P}}_f$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$.

Proposition 1

Consider $(f,\mu )$, $(g,\nu )$ distributional estimation problems. Suppose $\hat{\zeta }=(\zeta ,r_{\zeta },a_{\zeta })$ is a weak $\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 }^k\times U^{r_{\zeta }(k,j)}\times U^{r_{\xi }(k,j)}}\left[h\right({\hat{\xi }}^{kj}\left({\hat{\zeta }}^{kj}\right(x,z),w),{\hat{\zeta }}^{kj}(x,z)\left)\right]-E_{{\mu }^k\times U^{r_{\zeta }(k,j)}}\left[h\right(x,{\hat{\zeta }}^{kj}(x,z)\left)\right]|\le (sup|h|)\delta (k,j)$$

---

Proposition 1 proved exactly as Proposition 2 for unidistributional estimation problems.

Proposition 2

Consider $X$ a finite set, $\mu$ a probability measure on $X$, $h:X\to R$ and $s,t\in R$. Then

$$E_{\mu }\left[\right(h\left(x\right)-s{)}^2-\left(h\right(x)-t{)}^2]=\left(E_{\mu }\right[h\left(x\right)]-s{)}^2-(E_{\mu }\left[h\right(x\left)\right]-t{)}^2$$

Proof of Proposition 2

$$E_{\mu }\left[\right(h\left(x\right)-s{)}^2]=E_{\mu }[h\left(x{)}^2\right]-2E_{\mu }\left[h\right(x\left)\right]s+s^2$$

$$E_{\mu }\left[\right(h\left(x\right)-t{)}^2]=E_{\mu }[h\left(x{)}^2\right]-2E_{\mu }\left[h\right(x\left)\right]t+t^2$$

$$E_{\mu }\left[\right(h\left(x\right)-s{)}^2-\left(h\right(x)-t{)}^2]=2E_{\mu }\left[h\right(x\left)\right](t-s)+s^2-t^2$$

$$\left(E_{\mu }\right[h\left(x\right)]-s{)}^2=E_{\mu }[h\left(x\right){]}^2-2E_{\mu }\left[h\right(x\left)\right]s+s^2$$

$$\left(E_{\mu }\right[h\left(x\right)]-t{)}^2=E_{\mu }[h\left(x\right){]}^2-2E_{\mu }\left[h\right(x\left)\right]t+t^2$$

$$\left(E_{\mu }\right[h\left(x\right)]-s{)}^2-(E_{\mu }\left[h\right(x\left)\right]-t{)}^2=2E_{\mu }\left[h\right(x\left)\right](t-s)+s^2-t^2$$

Proof of Theorem

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

$${\hat{Q}}_g^{kj}(x,y_1{y}_2{y}_3{y}_4):={\hat{P}}_g^{kj}(x,y_1)+{\hat{Q}}_f^{kj}\left({\hat{\xi }}^{kj}\right(x,y_2),y_3)-{\hat{P}}_f^{kj}\left({\hat{\xi }}^{kj}\right(x,y_2),y_4)$$

We have

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

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

Applying the definitive property of $\hat{R}$ to the left hand side we get

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

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

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

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

$$E\left[{\hat{R}}^{kj}\right(y\left)\right({\hat{Q}}_g^{kj}\left(y\right)-g\left(y\right){)}^2]=E[\left({\hat{P}}_g^{p\left(k\right),j}\right({\hat{\zeta }}^{kj}\left(x\right))+{\hat{Q}}_f^{kj}({\hat{\xi }}^{kj}\left({\hat{\zeta }}^{kj}\right(x\left)\right))-{\hat{P}}_f^{kj}({\hat{\xi }}^{kj}\left({\hat{\zeta }}^{kj}\right(x\left)\right))-g({\hat{\zeta }}^{kj}\left(x\right)\left){)}^2\right]+{\gamma }_R^{\prime }(k,j)$$

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

$$E\left[{\hat{R}}^{kj}\right(y\left)\right({\hat{Q}}_g^{kj}\left(y\right)-g\left(y\right){)}^2]=E[\left({\hat{P}}_g^{p\left(k\right),j}\right({\hat{\zeta }}^{kj}\left(x\right))+{\hat{Q}}_f^{kj}(x)-{\hat{P}}_f^{kj}(x)-g({\hat{\zeta }}^{kj}\left(x\right)\left){)}^2\right]+{\gamma }_{\xi }(k,j)+{\gamma }_R^{\prime }(k,j)$$

where $|{\gamma }_{\xi }|\in \Delta$. Applying the stability of $\Delta$ to ${\delta }_0$ and putting everything together

$$E\left[\right({\hat{P}}_g^{p\left(k\right),j}\left({\hat{\zeta }}^{kj}\right(x\left)\right)-g\left({\hat{\zeta }}^{kj}\right(x\left)\right){)}^2]\le E[\left({\hat{P}}_g^{p\left(k\right),j}\right({\hat{\zeta }}^{kj}\left(x\right))+{\hat{Q}}_f^{kj}(x)-{\hat{P}}_f^{kj}(x)-g({\hat{\zeta }}^{kj}\left(x\right)\left){)}^2\right]+{\delta }_1(k,j)$$

for ${\delta }_1\in \Delta$. Applying Proposition 2

$$E_{{\mu }^k}\left[E\right[{\hat{P}}_g^{p\left(k\right),j}\left({\hat{\zeta }}^{kj}\right(x\left)\right)-g\left({\hat{\zeta }}^{kj}\right(x\left)\right){]}^2]\le E_{{\mu }^k\times U^{s_f(k,j)+r_f(k,j)}}[\left(E\right[{\hat{P}}_g^{p\left(k\right),j}\left({\hat{\zeta }}^{kj}\right(x\left)\right)-g\left({\hat{\zeta }}^{kj}\right(x\left)\right)]+{\hat{Q}}_f^{kj}(x)-{\hat{P}}_f^{kj}(x\left){)}^2\right]+{\delta }_1(k,j)$$

Applying property (i) of pseudo-invertible reductions

$$E_{{\mu }^k}\left[\right(E\left[{\hat{P}}_g^{p\left(k\right),j}\right({\hat{\zeta }}^{kj}\left(x\right)\left)\right]-f\left(x\right){)}^2]\le E_{{\mu }^k\times U^{s_f(k,j)+r_f(k,j)}}[\left(E\right[{\hat{P}}_g^{p\left(k\right),j}\left({\hat{\zeta }}^{kj}\right(x\left)\right)]-f(x)+{\hat{Q}}_f^{kj}(x)-{\hat{P}}_f^{kj}(x\left){)}^2\right]+{\delta }_2(k,j)$$

for ${\delta }_2\in \Delta$. Using the definition of ${\hat{P}}_f$ we get

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

for ${\delta }_3\in \Delta$. Finally we get

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

0 comments

Comments sorted by top scores.