Quasi-optimal predictors

[Vanessa Kosoy]

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.

[orthonormal]

So, to be clear, the difference between an optimal predictor and a quasi-optimal predictor is as follows: $\delta \left(k\right)$ is the amount by which some other polynomial-size circuit family is able to beat the current predictor. An optimal predictor cannot be beaten by any more than a $\delta$ such that $k^N\delta \left(k\right)\to 0$ for any $N$, while a quasi-optimal predictor can only assert it cannot be beaten by any more than a $\delta$ such that $\delta \left(k\right)\to 0$. Yes?

[Vanessa Kosoy]

Exactly. It’s such a simple tweak that it’s embarrassing I haven’t noticed it in the first place. It’s just that in average complexity theory negligible errors seem much more popular. The price to pay is that some theorems require stronger assumptions namely something that had to be bounded by a polynomial now has to be bounded by a constant. On the other hand Theorems 9 demonstrates that there is no chance optimal predictors cover all of $VerNP$ (for example) whereas quasi-optimal predictors might work. Also, I think that in $VerNP$ there is a universal construction for uniform quasi-optimal predictors (as opposed to optimal predictors) similar to Levin’s universal search although I haven’t fleshed out the details yet (anyhow such a construction would be theoretically valid but highly inefficient in practice).