Quasi-optimal predictors

post by Vanessa Kosoy (vanessa-kosoy) · 2015-12-25T14:17:05.000Z · LW · GW · 2 comments

Contents

  Definition 1
  Theorem 1
  Theorem 2
  Theorem 3
  Theorem 4
  Theorem 5
  Theorem 6
  Definition 2
  Theorem 7
  Definition 3
  Theorem 8
  Theorem 9
    Appendix
  Lemma 1
  Proof of Lemma 1
  Lemma 2
  Proof of Lemma 2
  Proof of Theorem 1
  Lemma 3
  Proof of Lemma 3
  Proof of Theorem 2
  Proof of Theorem 4
  Proof of Theorem 7
  Lemma 4
  Proof of Lemma 4
  Proof of Theorem 6
  Proof of Theorem 8
  Proof of Theorem 9
None
2 comments

In this post I define the concept of quasi-optimal predictors which is a weaker variant on the theme of optimal predictors. I explain the properties of quasi-optimal predictors that I currently understand (which are completely parallel to the properties of optimal predictors) and give an example where there is a quasi-optimal predictor but there is no optimal predictor.

All proofs are given in the appendix and are mostly analogous to proofs of corresponding theorems for optimal predictors.

Definition 1

Given $(D,\mu )$ a distributional decision problem, a quasi-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 ${lim}_{k\to \infty }\delta \left(k\right)=0$.

Theorem 1

Consider $(D,\mu )$ a distributional decision problem and $P$ a quasi-optimal predictor for $(D,\mu )$. Suppose $\{p_k\in [0,1]{\}}_{k\in N}$, $\{q_k\in [0,1]{\}}_{k\in N}$ are s.t.

$$\exists ϵ>0\forall k:{\mu }^k\{x\in \{0,1{\}}^{\ast }\mid p_k\le P^k\left(x\right)\le q_k\}\ge ϵ$$

Then:

$$\underset{k\to \infty }{lim}{E}_{{\mu }^k}\left[P^k\right(x)-{\chi }_D(x)\mid p_k\le P^k(x)\le q_k]=0$$

Theorem 2

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

Theorem 3

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

Theorem 4

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

Theorem 5

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

Theorem 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 quasi-optimal predictor for $(D,\mu )$ and $P_{C\cap D}$ is a quasi-optimal predictor for $(C\cap D,\mu )$. Define $P_{C\mid D}$ as the circuit family computing

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

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

Definition 2

Consider $\mu$ a word ensemble and $\{Q_{1,2}^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$ two circuit families. We say $Q_1$ is quasisimilar to $Q_2$ relative to $\mu$ (denoted $Q_1\stackrel{\mu }{\approx }{Q}_2$) when ${lim}_{k\to \infty }{E}_{{\mu }^k}\left[\right(Q_1^k\left(x\right)-Q_2^k\left(x\right){)}^2]=0$.

Theorem 7

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

Definition 3

Consider $(C,\mu )$, $(D,\nu )$ distributional decision problems, $\{f^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }\{0,1{\}}^{\ast }{\}}_{k\in N}$ a polynomial size family of circuits. $f$ is called a (non-uniform) strong pseudo-invertible reduction of $C$ to $D$ when there is a polynomial $p:N\to N$ s.t. the following conditions hold:

(i) $\forall k\in N,x\in \mathrm{supp}{\mu }^k:{\chi }_D\left(f^k\right(x\left)\right)={\chi }_C\left(x\right)$

(ii) There is $M\in R$ s.t.

$$\forall k\in N,y\in \{0,1{\}}^{\ast }:\frac{{\mu }^k\left(\right(f^k{)}^{-1}\left(y\right))}{{\nu }^{p\left(k\right)}\left(y\right)}\le M$$

(iii) There is a polynomial $q:N\to N$ and a family of polynomial size circuits $\{g^k:\mathrm{supp}{\nu }^{p\left(k\right)}\times \{0,1{\}}^{q\left(k\right)}\stackrel{circ}{\to }\{0,1{\}}^{\ast }{\}}_{k\in N}$ s.t.

$$\forall y\in f^k\left(\mathrm{supp}{\mu }^k\right),x^{\ast }\in \{0,1{\}}^{\ast }:P{r}_{U^{q\left(k\right)}}[g^k(y,r)=x^{\ast }]=P{r}_{{\mu }^k}[x=x^{\ast }|f^k\left(x\right)=y]$$

(iv) There are polynomial size circuits $\{R^k:\mathrm{supp}{\nu }^{p\left(k\right)}\stackrel{circ}{\to }{Q}^{\ge 0}{\}}_{k\in N}$ s.t.

$$\forall k\in N,y\in \mathrm{supp}{\nu }^{p\left(k\right)}:R^k\left(y\right)=\frac{{\mu }^k\left(\right(f^k{)}^{-1}\left(y\right))}{{\nu }^{p\left(k\right)}\left(y\right)}$$

Theorem 8

Consider $(C,\mu )$, $(D,\nu )$ distributional decision problems, $f$ a strong pseudo-invertible reduction of $(C,\mu )$ to $(D,\nu )$ and $P_D$ a quasi-optimal predictor for $(D,\nu )$. Define $\{P_C^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$ as the family of circuits computing $P_C^k\left(x\right):=P_D^{p\left(k\right)}\left(f^k\right(x\left)\right)$. Then, $P_C$ is a quasi-optimal predictor for $(C,\mu )$.

Theorem 9

Consider $f:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ a one-to-one non-uniformly hard one-way function. Define ${\tilde{\mu }}_f^k:=\frac{1}{k}{\sum }_{i<k}{\mu }_f^i$. Then, $P_f$ is a quasi-optimal predictor for $(D_f,{\tilde{\mu }}_f)$.

Appendix

Lemma 1

Consider $(D,\mu )$ a distributional decision problem and $$\{P^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$$ a family of polynomial size. Then, $P$ is a quasi-optimal predictor if and only if there is a function $\delta :N\times N\to [0,1]$ s.t.

(i) $\delta$ is non-decreasing in the second argument.

(ii) For any polynomial $p:N\to N$:

$$\underset{k\to \infty }{lim}\delta (k,p(k\left)\right)=0$$

In the following, we will call functions satisfying conditions (i) and (ii) quasinegligible.

(iii) for any $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]$ we have

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

Proof of Lemma 1

Define

$$\delta (k,q):=\underset{|Q|\le q}{max}\left\{E_{{\mu }^k}\right[\left(P^k\right(x)-{\chi }_D(x\left){)}^2\right]-E_{{\mu }^k}\left[\right(Q\left(x\right)-{\chi }_D\left(x\right){)}^2\left]\right\}$$

Lemma 2

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

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

(ii) For all polynomials $p,q:N\to N$:

$$\underset{k\to \infty }{lim}\delta (k,p(k),q(k\left)\right)=0$$

(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^k\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,|Q|,|w|)$$

Proof of Lemma 2

Given $t\in [0,maxw]$, denote

$$\alpha \left(t\right):=min\{s\ge t\mid \exists x\in \mathrm{supp}{\mu }^k:w(x)=s\}$$

Consider circuit $Q_t:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]$ computing the following function:

$$Q_t\left(x\right):=\{\begin{array}{cc}Q\left(x\right)& \text{if}w\left(x\right)\ge \alpha \left(t\right)\\ P^k\left(x\right)& \text{if}w\left(x\right)<\alpha \left(t\right)\end{array}$$

There is a polynomial $q$ s.t. $|Q_t|\le q(k,|Q|,|w|)$. By Lemma 1,

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

for $\delta$ quasinegligible.

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

$$E_{{\mu }^k}\left[\theta \right(w\left(x\right)-t\left)\right(P^k\left(x\right)-{\chi }_D\left(x\right){)}^2-\left(Q\right(x)-{\chi }_D(x\left){)}^2\right]\le \delta (k,q(k,|Q|,|w|\left)\right)$$

Integrating the inequality with respect to $t$ from $0$ to $maxw$, we get

$$E_{{\mu }^k}\left[{\int }_0^{maxw}\theta \right(w\left(x\right)-t\left)dt\right(\left(P^k\right(x)-{\chi }_D(x){)}^2-(Q\left(x\right)-{\chi }_D\left(x\right){)}^2]\le (maxw\left)\delta \right(k,q(k,|Q|,|w|))$$

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

Proof of Theorem 1

Define

$${\varphi }_k:=E_{{\mu }^k}\left[{\chi }_D\right(x)-P^k(x)\mid p_k\le P^k(x)\le q_k]$$

Assume to the contrary that there is $ϵ>0$ and an infinite set $I\subseteq N$ s.t.

$$\forall k\in I:|{\varphi }_k|\ge ϵ$$

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

$$w^k\left(x\right):=\theta \left(P^k\right(x)-p_k)\theta (q_k-P^k(x\left)\right)$$

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

We have

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

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

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

By the assumption, ${\psi }_k$ has binary notation of bounded size, therefore $|Q^k|$ is bounded by a polynomial.

Applying Lemma 2 we get

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

for $\delta$ vanishing at infinity.

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

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

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

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

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

The expression on the left hand side is a quadratic polynomial in ${\psi }_k$ which attains its maximum at ${\varphi }_k$ and has roots at $0$ and $2{\varphi }_k$. ${\psi }_k$ is between $0$ and ${\varphi }_k$, but not closer to $0$ than $\frac{{\varphi }_k}{2}$. Therefore, the inequality is preserved if we replace ${\psi }_k$ by $\frac{{\varphi }_k}{2}$.

$$\forall k\in I:\frac{{\varphi }_k}{2}{E}_{{\mu }^k}\left[w^k\right(x\left)\right(2\left({\chi }_D\right(x)-P^k(x\left)\right)-\frac{{\varphi }_k}{2}\left)\right]\le \delta \left(k\right)$$

Substituting the equation for ${\varphi }_k$ we get

$$\forall k\in I:\frac{1}{2}\frac{E_{{\mu }^k}\left[w^k\right(x\left)\right({\chi }_D\left(x\right)-P^k\left(x\right)\left)\right]}{E_{{\mu }^k}\left[w^k\right(x\left)\right]}{E}_{{\mu }^k}\left[w^k\right(x\left)\right(2\left({\chi }_D\right(x)-P^k(x\left)\right)-\frac{1}{2}\frac{E_{{\mu }^k}\left[w^k\right(x\left)\right({\chi }_D\left(x\right)-P^k\left(x\right)\left)\right]}{E_{{\mu }^k}\left[w^k\right(x\left)\right]}\left)\right]\le \delta \left(k\right)$$

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

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

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

$$\forall k\in I:{\varphi }_k^2\le \frac{4}{3}{\mu }^k\{x\in \{0,1{\}}^{\ast }\mid p_k\le P^k\left(x\right)\le q_k{\}}^{-1}\delta \left(k\right)$$

Thus ${\varphi }_k$ vanishes at infinity on $I$, which is a contradiction.

Lemma 3

Consider $(D,\mu )$ a distributional decision problem. If $\{P^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$ is a quasi-optimal predictor for $(D,\mu )$ then there are $c_1,c_2\in R$ and a quasinegligible function ${\delta }^{\ast }$ s.t. for any $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q$ we have

$$|E_{{\mu }^k}\left[Q\right(x\left)\right(P^k\left(x\right)-{\chi }_D\left(x\right)\left)\right]|\le (c_1+c_2{E}_{{\mu }^k}[Q\left(x{)}^2\right]\left){\delta }^{\ast }\right(k,|Q|)$$

Conversely, suppose $M\in Q$ and $\{P^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q\cap [-M,+M]{\}}_{k\in N}$ is a polynomial size family for which there is a quasinegligible function ${\delta }^{\ast }$ s.t. for any $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q\cap [-M-1,+M]{\}}_{k\in N}$ we have

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

Define $\{{\tilde{P}}^k:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]{\}}_{k\in N}$ to be s.t. computing ${\tilde{P}}^k\left(x\right)$ is equivalent to computing $\eta \left(P^k\right(x\left)\right)$ rounded to $k$ digits after the binary point. Then, $\tilde{P}$ is a quasi-optimal predictor.

Proof of Lemma 3

Assume $P$ is an optimal predictor. Consider $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q$ and $t=\sigma 2^{-a}$ where $\sigma \in \{\pm 1\}$ and $a\in N$. The function $\eta \left(P^k\right(x)+tQ(x\left)\right)$ can be approximated by a circuit of size $p(k,|Q|)$ for some fixed polynomial $p$, within rounding error ${ϵ}_k\left(x\right)$ s.t. $\forall x\in \mathrm{supp}{\mu }^k:|{ϵ}_k\left(x\right)|\le 2^{-k}$. By Lemma 1,

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

where $\delta$ is quasinegligible. $ϵ$ is bounded by a negligible function and therefore can be ignored by redefining $\delta$. As in the proof of Theorem 1, $\eta$ can be dropped.

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

The expression on the left hand side is a quadratic polynomial in $t$. Explicitly:

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

Moving $E_{{\mu }^k}\left[Q\right(x{)}^2]t^2$ to the right hand side and dividing both sides by $2|t|=2^{1-a}$ we get

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

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

Take $a:=-\frac{1}{2}\log \delta (k,|Q|)+\varphi \left(k\right)$ where $\varphi \left(k\right)\in [-\frac{1}{2},+\frac{1}{2}]$ is the rounding error. We get

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

Conversely, assume that for any $R:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q\cap [-M-1,+M]$

$$|E_{{\mu }^k}\left[R\right(x\left)\right(P^k\left(x\right)-{\chi }_D\left(x\right)\left)\right]|\le {\delta }^{\ast }(k,|R|)$$

Consider $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]$. We have

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

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

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

$P^k\left(x\right)-Q\left(x\right)$ can be computed by a circuit $R$ of size polynomial in $|Q|$ and $k$. Applying the assumption we get

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

where $\tilde{\delta }$ is quasinegligible. Noting that $E_{{\mu }^k}\left[\right(Q\left(x\right)-P^k\left(x\right){)}^2]\ge 0$ and $\left(\eta \right(P^k\left(x\right))-{\chi }_D(x){)}^2\le (P^k\left(x\right)-{\chi }_D\left(x\right){)}^2$ we get

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

Observing that $\tilde{P}-\eta \left(P\right)$ is bounded by a negligible function, we get the desired result.

Proof of Theorem 2

Consider $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q$. We have

$$E_{{\mu }^k}\left[Q\right(x\left)\right(P_1^k\left(x\right)+P_2^k\left(x\right)-{\chi }_{D_1\cup D_2}\left(x\right)\left)\right]=E_{{\mu }^k}\left[Q\right(x\left)\right(P_1^k\left(x\right)-{\chi }_{D_1}\left(x\right)\left)\right]+E_{{\mu }^k}\left[Q\right(x\left)\right(P_2^k\left(x\right)-{\chi }_{D_2}\left(x\right)\left)\right]$$

Using Lemma 3:

$$|E_{{\mu }^k}\left[Q\right(x\left)\right(P_1^k\left(x\right)-{\chi }_{D_1}\left(x\right)\left)\right]|\le (c_{11}+c_{12}{E}_{{\mu }^k}[Q\left(x{)}^2\right]\left){\delta }_1\right(k,|Q|)$$

$$|E_{{\mu }^k}\left[Q\right(x\left)\right(P_2^k\left(x\right)-{\chi }_{D_2}\left(x\right)\left)\right]|\le (c_{21}+c_{22}{E}_{{\mu }^k}[Q\left(x{)}^2\right]\left){\delta }_2\right(k,|Q|)$$

Therefore

$$|E_{{\mu }^k}\left[Q\right(x\left)\right(P_1^k\left(x\right)+P_2^k\left(x\right)-{\chi }_{D_1\cup D_2}\left(x\right)\left)\right]|\le (c_{11}+c_{21}+(c_{12}+c_{22}\left)E_{{\mu }^k}\right[Q\left(x{)}^2\right]\left)\right({\delta }_1(k,|Q|)+{\delta }_2(k,|Q|))$$

Using Lemma 3 again we get the desired result.

Proof of Theorem 4

We have

$$P^k\left(\right(x_1,x_2\left)\right)-{\chi }_{D_1\times D_2}\left(\right(x_1,x_2\left)\right)=\left(P_1^k\right(x_1)-{\chi }_{D_1}(x_1\left)\right){\chi }_{D_2}\left(x_2\right)+P_1^k\left(x_1\right)\left(P_2^k\right(x_2)-{\chi }_{D_2}(x_2\left)\right)$$

Therefore, for any $Q:\mathrm{supp}({\mu }_1\times {\mu }_2{)}^k\stackrel{circ}{\to }Q\cap [-1,+1]$

$$|E_{({\mu }_1\times {\mu }_2{)}^k}\left[Q\right(x\left)\right(P^k\left(x\right)-{\chi }_{D_1\times D_2}\left(x\right)\left)\right]|\le |E_{{\mu }_1^k\times {\mu }_2^k}\left[Q\right((x_1,x_2)\left)\right(P_1^k\left(x_1\right)-{\chi }_{D_1}\left(x_1\right)\left){\chi }_{D_2}\right(x_2\left)\right]|+|E_{{\mu }_1^k\times {\mu }_2^k}\left[Q\right((x_1,x_2)\left)P_1^k\right(x_1\left)\right(P_2^k\left(x_2\right)-{\chi }_{D_2}\left(x_2\right)\left)\right]|$$

By Lemma 3, it is sufficient to show an appropriate bound for each of the terms on the right hand side. For the first term, we have

$$|E_{{\mu }_1^k\times {\mu }_2^k}\left[Q\right((x_1,x_2)\left)\right(P_1^k\left(x_1\right)-{\chi }_{D_1}\left(x_1\right)\left){\chi }_{D_2}\right(x_2\left)\right]|\le E_{{\mu }_2^k}\left[|E_{{\mu }_1^k}\right[{\chi }_{D_2}\left(x_2\right)Q\left(\right(x_1,x_2\left)\right)\left(P_1^k\right(x_1)-{\chi }_{D_1}(x_1\left)\right)\left]|\right]$$

For any given $x_2$, ${\chi }_{D_2}\left(x_2\right)Q\left(\right(x_1,x_2\left)\right)$ can be computed by a circuit with input $x_1$ of size polynomial in $|x_2|$ and $|Q|$. Applying Lemma 3 to $P_1$, we get

$$|E_{{\mu }_1^k\times {\mu }_2^k}\left[Q\right((x_1,x_2)\left)\right(P_1^k\left(x_1\right)-{\chi }_{D_1}\left(x_1\right)\left){\chi }_{D_2}\right(x_2\left)\right]|\le E_{{\mu }_2^k}\left[{\delta }_1\right(k,p_1(|x_2|,|Q|)\left)\right]$$

where $p_1$ is a polynomial and ${\delta }_1$ is quasinegligible. Since $|x_2|$ is bounded by a polynomial in $k$ for $x_2\in \mathrm{supp}{\mu }_2^k$, we get the bound we need.

For the second term, we have

$$|E_{{\mu }_1^k\times {\mu }_2^k}\left[Q\right((x_1,x_2)\left)P_1^k\right(x_1\left)\right(P_2^k\left(x_2\right)-{\chi }_{D_2}\left(x_2\right)\left)\right]|\le E_{{\mu }_1^k}\left[|E_{{\mu }_2^k}\right[Q\left(\right(x_1,x_2\left)\right)P_1^k\left(x_1\right)\left(P_2^k\right(x_2)-{\chi }_{D_2}(x_2\left)\right)\left]|\right]$$

For any given $x_1$, $Q\left(\right(x_1,x_2\left)\right)P_1^k\left(x_1\right)$ can be computed by a circuit with input $x_1$ of size polynomial in $k$, $|x_1|$ and $|Q|$. Applying Lemma 3 to $P_2$, we get

$$|E_{{\mu }_1^k\times {\mu }_2^k}\left[Q\right((x_1,x_2)\left)P_1^k\right(x_1\left)\right(P_2^k\left(x_2\right)-{\chi }_{D_2}\left(x_2\right)\left)\right]|\le E_{{\mu }_1^k}\left[{\delta }_2\right(k,p_2(k,|x_1|,|Q|)\left)\right]$$

Again, we got the required bound.

Proof of Theorem 7

Assume $Q$ is a quasi-optimal predictor. Applying Lemma 3 to predictor $P$ and circuits computing $P^k-Q^k$, we get

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

for some $\delta$ vanishing at infinity. Applying Lemma 3 to predictor $Q$ and circuits computing $P^k-Q^k$, we get

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

for some $ϵ$ vanishing at infinity. We have

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

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

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

Conversely, assume $P\stackrel{\mu }{\approx }Q$. Consider some $R:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]$. We have

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

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

$$|E_{{\mu }^k}\left[R\right(x\left)\right(Q^k\left(x\right)-P^k\left(x\right)\left)\right]|\le E_{{\mu }^k}\left[|Q^k\right(x)-P^k(x\left)|\right]\le \sqrt{E_{{\mu }^k}\left[\right(Q^k\left(x\right)-P^k\left(x\right){)}^2]}\le \delta \left(k\right)$$

for some $\delta$ vanishing at infinity, since $P\stackrel{\mu }{\approx }Q$.

$$|E_{{\mu }^k}\left[R\right(x\left)\right(P^k\left(x\right)-{\chi }_D\left(x\right)\left)\right]|\le {\delta }^{\ast }(k,|R|)$$

for some quasinegligible ${\delta }^{\ast }$, using Lemma 3. Combining both inequalities we get

$$|E_{{\mu }^k}\left[R\right(x\left)\right(Q^k\left(x\right)-{\chi }_D\left(x\right)\left)\right]|\le \delta \left(k\right)+{\delta }^{\ast }(k,|R|)$$

Using Lemma 3 again we conclude $Q$ is a quasi-optimal predictor.

Lemma 4

Consider $C\subseteq D\subseteq \{0,1{\}}^{\ast }$ and $\mu$ a word ensemble. Assume $P_C$ is a quasi-optimal predictor for $(C,\mu )$ and $P_D$ is a quasi-optimal predictor for $(D,\mu )$. Define

$${ϵ}^k\left(x\right):=\theta \left(P_C^k\right(x)-P_D^k(x\left)\right)\left(P_C^k\right(x)-P_D^k(x\left)\right)$$

Then, ${lim}_{k\to \infty }{E}_{{\mu }^k}\left[{ϵ}^k\right(x\left)\right]=0$.

Proof of Lemma 4

By Theorem 3 and Lemma 3 there is a quasinegligible function $\delta$ such that for any $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q\cap [-2,+1]$ we have

$$|E_{{\mu }^k}\left[Q\right(x\left)\right(P_D^k\left(x\right)-P_C^k\left(x\right)-{\chi }_{D\setminus C}\left(x\right)\left)\right]|\le \delta (k,|Q|)$$

Take $Q$ to be the circuit computing $\theta \left(P_C^k\right(x)-P_D^k(x\left)\right)$. Its size is polynomial in $k$ therefore

$$|E_{{\mu }^k}\left[\theta \right(P_C^k\left(x\right)-P_D^k\left(x\right)\left)\right(P_D^k\left(x\right)-P_C^k\left(x\right)-{\chi }_{D\setminus C}\left(x\right)\left)\right]|\le {\delta }^{\ast }\left(k\right)$$

where ${\delta }^{\ast }$ vanishes at infinity.

$$|E_{{\mu }^k}\left[{ϵ}^k\right(x\left)\right]+E_{{\mu }^k}\left[\theta \right(P_C^k\left(x\right)-P_D^k\left(x\right)\left){\chi }_{D\setminus C}\right(x\left)\right]|\le {\delta }^{\ast }\left(k\right)$$

Since both terms inside the absolute value are non-negative we get the desired result.

Proof of Theorem 6

When $P_D^k\left(x\right)>0$ we have

$$P_{C\mid D}^k\left(x\right)=\frac{min\left(P_{C\cap D}^k\right(x),P_D^k(x\left)\right)}{P_D^k\left(x\right)}$$

Define ${\tilde{P}}_{C\cap D}^k$ to be the circuit computing $min\left(P_{C\cap D}^k\right(x),P_D^k(x\left)\right)$. Since $C\cap D\subseteq D$, Lemma 4 implies that ${lim}_{k\to \infty }{E}_{{\mu }^k}\left[P_{C\cap D}^k\right(x)-{\tilde{P}}_{C\cap D}^k(x\left)\right]=0$. This implies ${lim}_{k\to \infty }{E}_{{\mu }^k}\left[\right(P_{C\cap D}^k\left(x\right)-{\tilde{P}}_{C\cap D}^k\left(x\right){)}^2]=0$ and by Theorem 7 ${\tilde{P}}_{C\cap D}$ is a quasi-optimal predictor for $(C\cap D,\mu )$.

We have ${\tilde{P}}_{C\cap D}^k\left(x\right)=P_{C\mid D}^k\left(x\right)P_D^k\left(x\right)$ (whether $P_D^k\left(x\right)>0$ or $P_D^k\left(x\right)=0$) and therefore

$${\tilde{P}}_{C\cap D}^k\left(x\right)-{\chi }_{C\cap D}\left(x\right)=\left(P_{C\mid D}^k\right(x)-{\chi }_C(x\left)\right){\chi }_D\left(x\right)+P_{C\mid D}^k\left(x\right)\left(P_D^k\right(x)-{\chi }_D(x\left)\right)$$

$$\left(P_{C\mid D}^k\right(x)-{\chi }_C(x\left)\right){\chi }_D\left(x\right)={\tilde{P}}_{C\cap D}^k\left(x\right)-{\chi }_{C\cap D}\left(x\right)-P_{C\mid D}^k\left(x\right)\left(P_D^k\right(x)-{\chi }_D(x\left)\right)$$

Consider $Q:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }Q\cap [-1,+1]$.

$$E_{{\mu }^k\mid D}\left[Q\right(x\left)\right(P_{C\mid D}^k\left(x\right)-{\chi }_C\left(x\right)\left)\right]={\mu }^k\left(D{)}^{-1}{E}_{{\mu }^k}\right[Q\left(x\right)\left(P_{C\mid D}^k\right(x)-{\chi }_C(x\left)\right){\chi }_D\left(x\right)]$$

By Lemma 3 it is sufficient to prove appropriate bounds on $|E_{{\mu }^k}\left[Q\right(x\left)\right({\tilde{P}}_{C\cap D}^k\left(x\right)-{\chi }_{C\cap D}\left(x\right)\left)\right]|$ and $|E_{{\mu }^k}\left[Q\right(x\left)P_{C\mid D}^k\right(x\left)\right(P_D^k\left(x\right)-{\chi }_D\left(x\right)\left)\right]|$. Both bounds follow from Lemma 3 using the facts ${\tilde{P}}_{C\cap D}$ and $P_D$ are quasi-optimal predictors and $|P_{C\mid D}^k|$ is bounded by a polynomial.

Proof of Theorem 8

Consider $k\in N$, $Q_C:\mathrm{supp}{\mu }^k\stackrel{circ}{\to }[0,1]$. Define $Q_D:\mathrm{supp}{\nu }^{p\left(k\right)}\times \{0,1{\}}^{q\left(k\right)}\stackrel{circ}{\to }[0,1]$ to be the circuit computing $Q_D(y,r):=Q_C\left(g^k\right(y,r\left)\right)$. Applying Lemma 2, treating $r$ as a constant and using $R$ as the weight circuit, we get

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]\le E_{{\nu }^{p\left(k\right)}}[R^k\left(y\right)\left(Q_D\right(y,r)-{\chi }_D(y\left){)}^2\right]+\delta (k,|Q_C|)$$

where $\delta$ is quasinegligible. We used condition (ii) to get a constant bound on $max{R}^k$ and condition (iv) to get a polynomial bound on $|R^k|$.

We take the expectation value of both sides with respect to the uniform measure over $r$:

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]\le E_{{\nu }^{p\left(k\right)}\times U^{q\left(k\right)}}[R^k\left(y\right)\left(Q_D\right(y,r)-{\chi }_D(y\left){)}^2\right]+\delta (k,|Q_C|)$$

The left hand side can be rewritten as follows

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]=\sum _{y\in \{0,1{\}}^{\ast }}{\nu }^{p\left(k\right)}(y\left)\frac{{\mu }^k\left(\right(f^k{)}^{-1}\left(y\right))}{{\nu }^{p\left(k\right)}\left(y\right)}\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2$$

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]=\sum _{y\in \{0,1{\}}^{\ast }}{\mu }^k(\left(f^k{)}^{-1}\right(y\left)\right)\left(P_D^{p\left(k\right)}\right(y)-{\chi }_D(y){)}^2$$

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]=\sum _{y\in \{0,1{\}}^{\ast }}\sum _{\begin{array}{c}x\in \mathrm{supp}{\mu }^k\\ f^k\left(x\right)=y\end{array}}{\mu }^k(x\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2$$

Grouping the sum by $x$, we get

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]=\sum _{x\in \mathrm{supp}{\mu }^k}{\mu }^k(x\left)\right(P_C^k\left(x\right)-{\chi }_C\left(x\right){)}^2$$

$$E_{{\nu }^{p\left(k\right)}}\left[R^k\right(y\left)\right(P_D^{p\left(k\right)}\left(y\right)-{\chi }_D\left(y\right){)}^2]=E_{{\mu }^k}[\left(P_C^k\right(x)-{\chi }_C(x\left){)}^2\right]$$

The first term on the right hand side can be rewritten as

$$E_{{\nu }^{p\left(k\right)}\times U^{q\left(k\right)}}\left[R^k\right(y\left)\right(Q_D(y,r)-{\chi }_D\left(y\right){)}^2]=\sum _{y\in \{0,1{\}}^{\ast }}\sum _{r\in \{0,1{\}}^{q\left(k\right)}}{2}^{-q\left(k\right)}{\mu }^k(\left(f^k{)}^{-1}\right(y\left)\right)\left(Q_D\right(y,r)-{\chi }_D(y){)}^2$$

Grouping the sum by $x:=g(y,r)$ we get:

$$E_{{\nu }^{p\left(k\right)}\times U^{q\left(k\right)}}\left[R^k\right(y\left)\right(Q_D(y,r)-{\chi }_D\left(y\right){)}^2]=\sum _{x\in \{0,1{\}}^{\ast }}\sum _{y\in \{0,1{\}}^{\ast }}\sum _{\begin{array}{c}r\in \{0,1{\}}^{q\left(k\right)}\\ g^k(y,r)=x\end{array}}{2}^{-q\left(k\right)}{\mu }^k(\left(f^k{)}^{-1}\right(y\left)\right)\left(Q_C\right(x)-{\chi }_C(x){)}^2$$

Condition (iii) tells us that ${\sum }_{\begin{array}{c}r\in \{0,1{\}}^{q\left(k\right)}\\ g^k(y,r)=x\end{array}}{2}^{-q\left(k\right)}$ is only non-vanishing when $y=f^k\left(x\right)$ and that in this case it equals $\frac{{\mu }^k\left(x\right)}{{\mu }^k\left(\right(f^k{)}^{-1}\left(y\right))}$. Therefore

$$E_{{\nu }^{p\left(k\right)}\times U^{q\left(k\right)}}\left[R^k\right(y\left)\right(Q_D(y,r)-{\chi }_D\left(y\right){)}^2]=\sum _{x\in \{0,1{\}}^{\ast }}{\mu }^k(x\left)\right(Q_C\left(x\right)-{\chi }_C\left(x\right){)}^2$$

$$E_{{\nu }^{p\left(k\right)}\times U^{q\left(k\right)}}\left[R^k\right(y\left)\right(Q_D(y,r)-{\chi }_D\left(y\right){)}^2]=E_{{\mu }^k}[\left(Q_C\right(x)-{\chi }_C(x\left){)}^2\right]$$

Putting everything together, we get

$$E_{{\mu }^k}\left[\right(P_C^k\left(x\right)-{\chi }_C\left(x\right){)}^2]\le E_{{\mu }^k}[\left(Q_C\right(x)-{\chi }_C(x\left){)}^2\right]+\delta (k,|Q_C|)$$

Proof of Theorem 9

Assume to the contrary that $P_f$ is not quasi-optimal. Then there is an infinite set $I\subseteq N$, a polynomial size family of circuits $\{Q^k:\mathrm{supp}{\tilde{\mu }}_f^k\stackrel{circ}{\to }[0,1]{\}}_{k\in I}$ and $ϵ>0$ s.t.

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[\right(P_f^k\left(x\right)-{\chi }_{D_f}\left(x{)}^2\right)]\ge E_{{\tilde{\mu }}_f^k}[\left(Q^k\right(x)-{\chi }_{D_f}(x\left){)}^2\right]+ϵ$$

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[\right(Q^k\left(x\right)-{\chi }_{D_f}\left(x\right){)}^2]\le \frac{1}{4}-ϵ$$

Define the functions $\{q^k:\mathrm{supp}{\tilde{\mu }}_f^k\times [0,1]\to \{0,1\}{\}}_{k\in I}$ by $q^k(x,t):=\theta \left(Q^k\right(x)-t)$. We have

$$\forall k\in I,x\in \mathrm{supp}{\tilde{\mu }}_f^k:Q^k\left(x\right)={\int }_0^1{q}^k(x,t)dt$$

Substituting into the inequality above

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[\right({\int }_0^1{q}^k(x,t)dt-{\chi }_{D_f}\left(x\right){)}^2]\le \frac{1}{4}-ϵ$$

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[|{\int }_0^1{q}^k\right(x,t)dt-{\chi }_{D_f}(x)|{]}^2\le \frac{1}{4}-ϵ$$

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[|{\int }_0^1\right(q^k(x,t)-{\chi }_{D_f}\left(x\right)\left)dt|\right]\le \sqrt{\frac{1}{4}-ϵ}$$

For every given $x$, $q^k(x,t)-{\chi }_{D_f}\left(x\right)$ is either non-negative for all $t$ or non-positive for $t$. Hence we can move the absolute value inside the integral:

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[{\int }_0^1|q^k\right(x,t)-{\chi }_{D_f}(x\left)|dt\right]\le \sqrt{\frac{1}{4}-ϵ}$$

$$\forall k\in I:{\int }_0^1{E}_{{\tilde{\mu }}_f^k}\left[|q^k\right(x,t)-{\chi }_{D_f}(x\left)|\right]dt\le \sqrt{\frac{1}{4}-ϵ}$$

This implies that we can choose $\{t_k\in Q^k(\mathrm{supp}{\tilde{\mu }}_f^k)\cup \{0,1\}{\}}_{k\in I}$ s.t.

$$\forall k\in I:E_{{\tilde{\mu }}_f^k}\left[|q^k\right(x,t_k)-{\chi }_{D_f}(x\left)|\right]\le \sqrt{\frac{1}{4}-ϵ}$$

$$\forall k\in I:P{r}_{{\tilde{\mu }}_f^k}\left[q^k\right(x,t_k)\ne {\chi }_{D_f}(x\left)\right]\le \sqrt{\frac{1}{4}-ϵ}$$

$$\forall k\in I:P{r}_{{\tilde{\mu }}_f^k}\left[q^k\right(x,t_k)={\chi }_{D_f}(x\left)\right]\ge 1-\sqrt{\frac{1}{4}-ϵ}$$

Using the fact that the graph of the square root lies below its tangent at any point, this leads to

$$\forall k\in I:P{r}_{{\tilde{\mu }}_f^k}\left[q^k\right(x,t_k)={\chi }_{D_f}(x\left)\right]\ge \frac{1}{2}+ϵ$$

Define $\{g^k:f(\{0,1{\}}^k)\times \{0,1{\}}^k\stackrel{circ}{\to }\{0,1\}{\}}_{k\in N}$ as the circuits computing $g^k(y,r):=1-q^k\left(\right(y,r),t_k)$. The definitions of $q^k$ and $t_k$ imply that $|g^k|$ is bounded by a polynomial. The inequality above and the definitions of $D_f$ and ${\tilde{\mu }}_f$ imply

$$\forall k\in I:\frac{1}{k}\sum _{i<k}P{r}_{U^i\times U^i}\left[g^i\right(f\left(x\right),r)=x\cdot r]\ge \frac{1}{2}+ϵ$$

But this contradicts the assumption on $f$.

Note that this argument doesn't show $P_f$ is optimal since while the averaging over $i$ preserves the property of vanishing at infinity, it doesn't preserve the property of negligibility. Moreover, it is possible to show that no optimal predictor for $(D_f,{\tilde{\mu }}_f)$ exists.

2 comments

Comments sorted by top scores.