Logical counterfactuals for random algorithms

[Vanessa Kosoy]

Updateless decision theory was informally defined by Wei Dai in terms of logical conditional expected utility, where the condition corresponds to an algorithm (the agent) producing a given output (action or policy). This kind of conditional expected values can be formalised by optimal predictors. However, since optimal predictor systems which are required to apply optimal predictors to decision theory generally have random advice, we need counterfactuals well-defined for random algorithms i.e. algorithms that produce different outputs with different probabilities depending on internal coin tosses. We propose to define these counterfactuals by a generalization of the notion of conditional expected utility which amounts to linear regression of utility with respect to the probabilities of different outputs in the space of “impossible possible worlds.” We formalise this idea by introducing “relative optimal predictors,” prove the analogue of the conditional probability formula (which takes matrix form) and uniqueness theorems.

Motivation

We start by explaining the analogous construction in classical probability theory and proceed to defining the logical counterpart in the Results section.

Consider $\zeta$ a probability measure on some space, a random variable $u$ representing utility, a finite set $A$ representing possible actions and another random variable $p$ taking values in $[0,1{]}^A$ and satisfying ${\sum }_{a\in A}{p}_a=1$ representing the probabilities of taking different actions. For a deterministic algorithm, $p$ takes values $\{0,1{\}}^A$ allowing defining conditional expected utility as

$$u_a:=E_{\zeta }[u\mid p_a=1]=\frac{E_{\zeta }\left[u{p}_a\right]}{E_{\zeta }\left[p_a\right]}$$

In the general case, it is tempting to consider

$$E_{\zeta ⋉p}[u\mid a]=\frac{E_{\zeta }\left[u{p}_a\right]}{E_{\zeta }\left[p_a\right]}$$

where $\zeta ⋉p$ stands for the semidirect product of $\zeta$ with $p$, the latter regarded as a Markov kernel with target $A$. However, this would lead to behavior similar to EDT since conditioning by $a$ is meaningful even for a single “world” (i.e. completely deterministic $u$ and $p$). Instead, we select $u^{\ast }\in R^A$ that minimizes $E_{\zeta }\left[\right(u-p^t{u}^{\ast }{)}^2]$ (we regard elements of $R^A$ as column vectors so $p^t$ is a row vector). This means $u^{\ast }$ has to satisfy the matrix equation

$$E_{\zeta }\left[p{p}^t\right]u^{\ast }=E_{\zeta }\left[up\right]$$

The solution to this equation is only unique when $E_{\zeta }\left[p{p}^t\right]$ is non-degenerate. This corresponds to requiring positive probability of the condition for usual conditional expected values. In case $p$ takes values in $\{0,1{\}}^A$, $u^{\ast }$ is the usual conditional expected value.

Preliminaries

Notation

We will suppress the $k,j$ indices associated with word ensembles and bischemes whenever possible to reduce clutter. When we do show $k,j$ explicitly, evaluation of functions $\delta :N^2\to R$ will be written as ${\delta }^{kj}$ rather than $\delta (k,j)$ as before.

The concept of “proto-error space” is renamed to “error space” whereas the previous definition of “error space” is now called “radical error space”.

---

We slightly extend the definition of “distributional estimation problem” as follows.

Definition 1

A distributional estimation problem is a pair $(\mu ,f)$ where $\mu$ is a word ensemble and $f:\mathrm{supp}\mu \to R$ is bounded.

---

The corresponding notion of optimal predictor is the following.

Definition 2

Fix $E$ an space of rank 2 and $(\mu ,f)$ a distributional estimation problem. Consider $\hat{P}$ a $Q$-valued $(poly,rlog)$-bischeme taking bounded values.$\hat{P}$ is called an $E(poly,rlog)$-optimal predictor for $(\mu ,f)$ when for any $Q$-valued $(poly,rlog)$-bischeme $\hat{Q}$, there is $\delta \in E$ s.t.

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(\hat{P}-f{)}^2]\le E_{\mu \times {\hat{\sigma }}_Q}[(\hat{Q}-f{)}^2]+\delta$$

---

The theory of optimal predictors remains intact with these new definitions (although some care is wish to consider reflective systems with range $R$ instead of $[0,1]$).

The following concept of “orthogonal predictor” is often more convenient than “optimal predictor”, since we no longer require our error spaces to be radical.

Definition 3

Fix $E$ an error space of rank 2 and $(\mu ,f)$ a distributional estimation problem. Consider $\hat{P}$ a $Q$-valued $(poly,rlog)$-bischeme taking bounded values.

$\hat{P}$ is called an $E(poly,rlog)$-orthogonal predictor for $(\mu ,f)$ when for any $Q$-valued $(poly,rlog)$-bischeme $\hat{Q}$ s.t.${\hat{\sigma }}_Q$ factors as ${\hat{\sigma }}_P\times \tau$, there is $\delta \in E$ s.t.

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[Q(x,y,z)\left(P\right(x,y)-f(x\left)\right)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[{\hat{Q}}^2]+1)\delta$$

---

The two concepts are tightly related due to the following

Theorem 1

Fix $E$ an error space of rank 2 and $(\mu ,f)$ a distributional estimation problem. Then any $E(poly,rlog)$-orthogonal predictor for $(\mu ,f)$ is an $E(poly,rlog)$-optimal predictor for $(\mu ,f)$. Conversely any $E(poly,rlog)$-optimal predictor for $(\mu ,f)$ is an $E^{\frac{1}{2}}(poly,rlog)$-orthogonal predictor for $(\mu ,f)$.

---

We skip the proof since it is almost identical to the orthogonality lemma.

Results

The proofs of the results are found in the Appendix.

Definition 4

A relative estimation problem is a quadruple $(A,\mu ,f,g)$ where $A$ is a finite set, $f:\mathrm{supp}\mu \to R$ bounded and $g:\mathrm{supp}\mu \to R^A$ bounded.

Definition 5

Fix $E$ an error space of rank 2. Consider $(A,\mu ,f,g)$ a relative estimation problem and $\hat{P}$ a $Q^A$-valued $(poly,rlog)$-bischeme.$\hat{P}$ is called an $E(poly,rlog)$-optimal predictor for $(A,\mu ,f,g)$ when for any $Q^A$-valued $(poly,rlog)$-bischeme $\hat{Q}$ s.t.${\hat{\sigma }}_Q$ factors as ${\hat{\sigma }}_P\times \tau$, there is $\delta \in E$ s.t.

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]\le E_{\mu \times {\hat{\sigma }}_Q}[(g^t\hat{Q}-f{)}^2]+\left(E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[\left(g^t\right(\hat{P}-\hat{Q}\left){)}^2\right]+1)\delta$$

---

The appearance of the $E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[\right(g^t(\hat{P}-\hat{Q}){)}^2]$ term might seem as making the condition substantially weaker. However, we the condition is still sufficient strong to produce the uniqueness theorem which appears as Theorem 1 below. Also, the novelty disappears in the corresponding orthogonality condition.

Definition 6

Fix $E$ an error space of rank 2. Consider $(A,\mu ,f,g)$ a relative estimation problem and $\hat{P}$ a $Q^A$-valued $(poly,rlog)$-bischeme.$\hat{P}$ is called an $E(poly,rlog)$-orthogonal predictor for $(A,\mu ,f,g)$ when for any $Q^A$-valued $(poly,rlog)$-bischeme $\hat{Q}$ s.t.${\hat{\sigma }}_Q$ factors as ${\hat{\sigma }}_P\times \tau$, there is $\delta \in E$ s.t.

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[g^{t}Q(x,y,z)\left(g^{t}P\right(x,y)-f(x\left)\right)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[\left(g^{t}Q{)}^2\right]+1)\delta$$

Theorem 2

Fix $E$ an error space of rank 2 and $(A,\mu ,f,g)$ a relative estimation problem. Then any $E(poly,rlog)$-orthogonal predictor for $(A,\mu ,f,g)$ is an $E(poly,rlog)$-optimal predictor for $(A,\mu ,f,g)$. Conversely any $E(poly,rlog)$-optimal predictor for $(A,\mu ,f,g)$ is an $E^{\frac{1}{2}}(poly,rlog)$-orthogonal predictor for $(A,\mu ,f,g)$.

Definition 7

Consider $E$ an error space space of rank $n$. A set $I\subseteq N^n$ is called $E$-negligible when ${\chi }_I\in E$.

---

Note 1

The $E$-negligible sets form a set-theoretic ideal on $N^n$.

All finite sets are $E$-negligible (thanks to the the condition $2^{-h}\in E$).

Definition 8

Fix $E$ an error space of rank 2. Consider $A$ a finite set, $\mu$ a word ensemble, $g:\mathrm{supp}\mu \to R^A$ and ${\hat{Q}}_1,{\hat{Q}}_2$ $Q^A$-valued $(poly,rlog)$-bischemes. We say ${\hat{Q}}_1$ is $E$-similar to ${\hat{Q}}_2$ relative to $g$ (denoted ${\hat{Q}}_1\underset{E}{\stackrel{g}{\simeq }}{\hat{Q}}_2$) when there is an $E$-negligible set $I$ and $\delta \in E$ s.t.

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\left[\right(g^t({\hat{Q}}_1^{kj}-{\hat{Q}}_2^{kj}){)}^2]={\delta }^{kj}$$

Note 2

It’s impossible to remove $I$ from the definition since $E_{{\mu }^k\times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\left[\right(g^t({\hat{Q}}_1^{kj}-{\hat{Q}}_2^{kj}){)}^2]$ doesn’t have to be bounded.

Theorem 3

Fix $E$ an error space of rank 2. Consider $(A,\mu ,f,g)$ a relative estimation problem and ${\hat{P}}_1,{\hat{P}}_2$ $E(poly,rlog)$-orthogonal predictors for $(A,\mu ,f,g)$. Then ${\hat{P}}_1\underset{E}{\stackrel{g}{\simeq }}{\hat{P}}_2$.

---

Theorem 4 below is the orthogonal predictor analogue of the matrix equation from the previous section.

Proposition 1

Consider $E$ an error space of rank $n$, $ϵ>0$ and $\gamma :N^n\to [ϵ,\infty )$. Then $\gamma E:=\{\gamma \delta \mid \delta \in E\}$ is an error space.

Theorem 4

Fix $E$ an error space of rank 2. Consider $(A,\mu ,f,g)$ a relative estimation problem, ${\hat{P}}_{gg}$ an $\mathrm{End}\left(Q^A\right)$-valued $(poly,rlog)$-bischeme, ${\hat{P}}_{fg}$ a $Q^A$-valued bischeme, $ϵ>0$ and $\gamma :N^2\to [ϵ,\infty )$. Assume that for any $x\in \mathrm{supp}{\mu }^k$, ${\hat{P}}_{gg}^{kj}\left(x\right)$ is always invertible and the operator norm of ${\hat{P}}_{gg}^{kj}(x{)}^{-1}$ is at most ${\gamma }^{kj}$. Assume further that ${\hat{P}}_{gg}$ is an $E(poly,rlog)$-orthogonal predictor for $g{g}^t$ (componentwise) and ${\hat{P}}_{fg}$ is a ${\gamma }^{2}E(poly,rlog)$-orthogonal predictor for $fg$ (componentwise). Define the $Q^A$-valued bischeme ${\hat{P}}_{f\mid g}$ by ${\hat{P}}_{f\mid g}:={\hat{P}}_{gg}^{-1}{\hat{P}}_{fg}$. Then, ${\hat{P}}_{f\mid g}$ is a ${\gamma }^{2}E(poly,rlog)$-orthogonal predictor for $(A,\mu ,f,g)$.

Note 3

It is always possible to choose ${\hat{P}}_{gg}$ to be symmetric in which case the operator norm of ${\hat{P}}_{gg}^{-1}$ is the inverse of the lowest absolute value of an eigenvalue of ${\hat{P}}_{gg}$.

---

Finally, we extend the stability result for usual conditional probabilities to the matrix setting.

Definition 9

Fix $E$ an error space of rank 2. Consider $A$ a finite set, $\mu$ a word ensemble and ${\hat{Q}}_1,{\hat{Q}}_2$ $Q^A$-valued $(poly,rlog)$-bischemes. We say ${\hat{Q}}_1$ is $E$-similar to ${\hat{Q}}_2$ relative to $\mu$ (denoted ${\hat{Q}}_1\underset{E}{\stackrel{\mu }{\simeq }}{\hat{Q}}_2$) when there is an $E$-negligible set $I$ and $\delta \in E$ s.t.

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}[\parallel {\hat{Q}}_1^{kj}-{\hat{Q}}_2^{kj}{\parallel }^2]={\delta }^{kj}$$

Theorem 5

Fix $E$ an error space of rank 2. Consider $ϵ>0$ and $\gamma :N^2\to [ϵ,\infty )$, $(A,\mu ,f,g)$ a relative estimation problem, ${\hat{P}}_{gg}$ a positive-definite $E(poly,log)$-orthogonal predictor for $g{g}^t$ and ${\hat{P}}_1$, ${\hat{P}}_2$ ${\gamma }^{4}E(poly,log)$-orthogonal predictors for $(A,\mu ,f,g)$. Assume that for any $x\in \mathrm{supp}{\mu }^k$, the lowest eigenvalue of ${\hat{P}}_{gg}^{kj}\left(x\right)$ is always at least $({\gamma }^{kj}{)}^{-1}$ and $\parallel {\hat{P}}_{1,2}^{kj}\left(x\right)\parallel \le {\gamma }^{kj}$. Then, ${\hat{P}}_1\underset{{\gamma }^{5}E}{\stackrel{\mu }{\simeq }}{\hat{P}}_2$.

---

The Corollary below shows that in simple situations these counterfactuals produce the values we expect.

Definition 10

Fix $E$ an space of rank 2 and $(\mu ,f)$ a distributional estimation problem. Consider $\hat{P}$ a $Q$-valued $(poly,rlog)$-bischeme taking bounded values.$\hat{P}$ is called an $E(poly,rlog)$-perfect predictor for $(\mu ,f)$ when $E_{\mu \times {\hat{\sigma }}_P}\left[\right(\hat{P}-f{)}^2]\in E$.

Corollary

Fix $E$ an error space of rank 2. Consider $ϵ>0$ and $\gamma :N^2\to [ϵ,\infty )$, $(A,\mu ,f^{\ast },g)$ a relative estimation problem and $f:\mathrm{supp}\mu \to R^A$ bounded s.t. $f^{\ast }=g^{t}f$. Suppose ${\hat{P}}_f$ is a ${\gamma }^8{E}^2(poly,rlog)$-perfect predictor for $(\mu ,f)$. Suppose ${\hat{P}}_{gg}$ is a positive-definite $E(poly,rlog)$-orthogonal predictor for $g{g}^t$ s.t. for any $x\in \mathrm{supp}{\mu }^k$, the lowest eigenvalue of ${\hat{P}}_{gg}^{kj}\left(x\right)$ is always at least $({\gamma }^{kj}{)}^{-1}$. Suppose ${\hat{P}}_{fg}$ is a ${\gamma }^{2}E(poly,rlog)$-orthogonal predictor for $fg$. Then, ${\hat{P}}_{gg}^{-1}{\hat{P}}_{fg}\underset{{\gamma }^{5}E}{\stackrel{\mu }{\simeq }}{\hat{P}}_f$.

Appendix

Proof of Theorem 2

Consider $\hat{P}$ an $E(poly,rlog)$-optimal predictor for $(A,\mu ,f,g)$. Consider $\hat{R}$ a $Q^A$-valued $(poly,rlog)$-bischeme with ${\hat{\sigma }}_R={\hat{\sigma }}_P\times \tau$. For any $\zeta :N^2\to \{-1,+1\}$ and $n:N^2\to Z$ s.t.$\left|n\right|$ can be bounded by a polynomial (and hence its number of digits is logarithmic), we can define $t^{kj}:={\zeta }^{kj}{2}^{-n^{kj}}$ and the $Q^A$-valued $(poly,rlog)$-bischeme $\hat{Q}$ with ${\hat{\sigma }}_Q:={\hat{\sigma }}_R$ and $Q(x,y,z):=P(x,y)+tR(x,y,z)$. We have $\delta \in E$ s.t.

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]\le E_{\mu \times {\hat{\sigma }}_Q}[(g^t\hat{Q}-f{)}^2]+\left(E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[\left(g^t\right(\hat{P}-\hat{Q}\left){)}^2\right]+1)\delta$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]\le E_{\mu \times {\hat{\sigma }}_P\times \tau }[\left(g^t\right(\hat{P}+t\hat{R})-f{)}^2]+\left(E_{\mu \times {\hat{\sigma }}_R}\right[\left(g^t\hat{R}{)}^2\right]t^2+1)\delta$$

$$E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[\right(g^t\hat{P}-f{)}^2-\left(g^t\right(\hat{P}+t\hat{R})-f{)}^2]\le \left(E_{\mu \times {\hat{\sigma }}_R}\right[\left(g^t\hat{R}{)}^2\right]t^2+1)\delta$$

$$-E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2]t^2-2E_{\mu \times {\hat{\sigma }}_P\times \tau }[g^t\hat{R}(g^t\hat{P}-f)]t\le (E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2]t^2+1)\delta$$

$$-2E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[g^t\hat{R}\right(g^t\hat{P}-f\left)\right]t\le E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2\left]\right(1+sup\delta )t^2+\delta$$

By choosing $\zeta :=-\mathrm{sgn}{E}_{\mu \times {\hat{\sigma }}_P\times \tau }\left[g^t\hat{R}\right(g^t\hat{P}-f\left)\right]$ we get

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[g^t\hat{R}(g^t\hat{P}-f)\left]\right|2^{-n+1}\le E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2\left]\right(1+sup\delta )4^{-n}+\delta$$

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[g^t\hat{R}(g^t\hat{P}-f)\left]\right|\le E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2\left]\right(1+sup\delta )2^{-n}+\delta 2^n$$

Take $n:=min(-\lfloor \frac{1}{2}\log \delta \rfloor ,h)$ where $h:N^2\to N$ is a polynomial s.t. $2^{-h}\in E$. We get

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[g^t\hat{R}(g^t\hat{P}-f)\left]\right|\le E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2\left]\right(1+sup\delta )max({\delta }^{\frac{1}{2}},2^{-h})+\delta min(2{\delta }^{-\frac{1}{2}},2^h)$$

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[g^t\hat{R}(g^t\hat{P}-f)\left]\right|\le E_{\mu \times {\hat{\sigma }}_R}\left[\right(g^t\hat{R}{)}^2\left]\right(1+sup\delta )max({\delta }^{\frac{1}{2}},2^{-h})+2{\delta }^{\frac{1}{2}}$$

$$\left|E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[g^t\hat{R}(g^t\hat{P}-f)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_R}\right[\left(g^t\hat{R}{)}^2\right]+1\left)\right(1+sup\delta )max(2{\delta }^{\frac{1}{2}},2^{-h})$$

Conversely, suppose $\hat{P}$ an $E(poly,rlog)$-orthogonal predictor for $(A,\mu ,f,g)$. Consider $\hat{Q}$ a $Q^A$-valued $(poly,rlog)$-bischeme with ${\hat{\sigma }}_Q={\hat{\sigma }}_P\times \tau$. We have

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]-E_{\mu \times {\hat{\sigma }}_Q}[(g^t\hat{Q}-f{)}^2]=E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[g^t\right(\hat{P}-\hat{Q}\left)\right(g^t(\hat{P}+\hat{Q})-2f\left)\right]$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]-E_{\mu \times {\hat{\sigma }}_Q}[(g^t\hat{Q}-f{)}^2]=E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[g^t\right(\hat{P}-\hat{Q}\left)\right(2g^t\hat{P}+g^t(\hat{Q}-\hat{P})-2f\left)\right]$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]-E_{\mu \times {\hat{\sigma }}_Q}[(g^t\hat{Q}-f{)}^2]=2E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[g^t\right(\hat{P}-\hat{Q}\left)\right(g^t\hat{P}-f\left)\right]-E_{\mu \times {\hat{\sigma }}_P\times \tau }\left[\right(g^t(\hat{P}-\hat{Q}){)}^2]$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]-E_{\mu \times {\hat{\sigma }}_Q}[(g^t\hat{Q}-f{)}^2]\le \left(E_{\mu \times {\hat{\sigma }}_P\times \tau }\right[\left(g^t\right(\hat{P}-\hat{Q}\left){)}^2\right]+1)\delta$$

Proof of Theorem 3

Since ${\hat{P}}_1$ is orthogonal, we have ${\delta }_1\in E$ s.t.

$$\left|E_{\mu \times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\right[g^t({\hat{P}}_1-{\hat{P}}_2)(g^t{\hat{P}}_1-f)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\right[\left(g^t\right({\hat{P}}_1-{\hat{P}}_2\left){)}^2\right]+1){\delta }_1$$

Since ${\hat{P}}_2$ is orthogonal, we have ${\delta }_2\in E$ s.t.

$$\left|E_{\mu \times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\right[g^t({\hat{P}}_1-{\hat{P}}_2)(g^t{\hat{P}}_2-f)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\right[\left(g^t\right({\hat{P}}_1-{\hat{P}}_2\left){)}^2\right]+1){\delta }_2$$

It follows that

$$E_{\mu \times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\left[\right(g^t({\hat{P}}_1-{\hat{P}}_2){)}^2]\le (E_{\mu \times {\hat{\sigma }}_1\times {\hat{\sigma }}_2}\left[\right(g^t({\hat{P}}_1-{\hat{P}}_2){)}^2]+1)({\delta }_1+{\delta }_2)$$

Define $I:=\left\{\right(k,j)\mid {\delta }_1^{kj}+{\delta }_2^{kj}\ge \frac{1}{2}\}$. ${\chi }_I\le 2({\delta }_1+{\delta }_2)$ so $I$ is $E$-negligible. We get

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\left[\right(g^t({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}){)}^2]\le \frac{{\delta }_1^{kj}+{\delta }_2^{kj}}{1-{\delta }_1^{kj}-{\delta }_2^{kj}}$$

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\left[\right(g^t({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}){)}^2]\le 2({\delta }_1^{kj}+{\delta }_2^{kj})$$

Proof of Proposition 1

Given ${\delta }_1,{\delta }_2\in E$

$$\gamma {\delta }_1+\gamma {\delta }_2=\gamma ({\delta }_1+{\delta }_2)\in \gamma E$$

Given ${\delta }_1\in E$

$${\delta }_2\le \gamma {\delta }_1⟹{\gamma }^{-1}{\delta }_2\le {\delta }_1⟹{\gamma }^{-1}{\delta }_2\in E⟹{\delta }_2\in \gamma E$$

Given $h$ polynomial s.t. $2^{-h}\in E$

$$2^{-h}\le \gamma {ϵ}^{-1}{2}^{-h}\in \gamma E$$

Proof of Theorem 4

We know that ${\hat{\sigma }}_{f\mid g}={\hat{\sigma }}_{gg}\times {\hat{\sigma }}_{fg}$ and

$$P_{fg}(x,z)-f\left(x\right)g\left(x\right)=\left(g\right(x{)}^t{P}_{f\mid g}(x,y,z)-f\left(x\right)\left)g\right(x)+(P_{gg}(x,y)-g\left(x\right)g\left(x{)}^t\right)P_{f\mid g}(x,y,z)$$

Consider a $Q^A$-valued $(poly,rlog)$-bischeme $\hat{Q}$ s.t.${\hat{\sigma }}_Q$ factors as ${\hat{\sigma }}_{gg}\times {\hat{\sigma }}_{fg}\times \tau$. We get

$$\left|E_{\mu \times {\hat{\sigma }}_Q}\right[g^{t}Q(g^t{\hat{P}}_{f\mid g}-f)\left]\right|\le \left|E_{\mu \times {\hat{\sigma }}_Q}\right[Q^t({\hat{P}}_{fg}-fg)\left]\right|+\left|E_{\mu \times {\hat{\sigma }}_Q}\right[Q^t({\hat{P}}_{gg}-g{g}^t){\hat{P}}_{f\mid g}\left]\right|$$

Since ${\hat{P}}_{fg}$ is a ${\gamma }^{2}E(poly,rlog)$-orthogonal predictor for $fg$, there is ${\delta }_{fg}\in E$ s.t.

$$\left|E_{\mu \times {\hat{\sigma }}_Q}\right[Q^t({\hat{P}}_{fg}-fg)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[\parallel Q{\parallel }^2]+1){\gamma }^2{\delta }_{fg}$$

Since ${\hat{P}}_{gg}$ is an $E(poly,rlog)$-orthogonal predictor for $g{g}^t$, there is ${\delta }_{gg}\in E$ s.t.

$$\left|E_{\mu \times {\hat{\sigma }}_Q}\right[Q^t({\hat{P}}_{gg}-g{g}^t){\hat{P}}_{f\mid g}\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[\parallel Q{\parallel }^2\parallel {\hat{P}}_{f\mid g}{\parallel }^2]+1){\delta }_{gg}$$

${\hat{P}}_{fg}$ is bounded and the operator norm of ${\hat{P}}_{gg}^{-1}$ is at most $\gamma$, therefore there is $c>0$ s.t.$\parallel {\hat{P}}_{f\mid g}{\parallel }^2\le c{\gamma }^2$ and

$$\left|E_{\mu \times {\hat{\sigma }}_Q}\right[Q^t({\hat{P}}_{gg}-g{g}^t){\hat{P}}_{f\mid g}\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[\parallel Q{\parallel }^2]c{\gamma }^2+1){\delta }_{gg}$$

$$\left|E_{\mu \times {\hat{\sigma }}_Q}\right[Q^t({\hat{P}}_{gg}-g{g}^t){\hat{P}}_{f\mid g}\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[\parallel Q{\parallel }^2]+1)max({ϵ}^{-2},c){\gamma }^2{\delta }_{gg}$$

Putting everything together we get

$$\left|E_{\mu \times {\hat{\sigma }}_Q}\right[g^{t}Q(g^t{\hat{P}}_{f\mid g}-f)\left]\right|\le \left(E_{\mu \times {\hat{\sigma }}_Q}\right[\parallel Q{\parallel }^2]+1){\gamma }^2({\delta }_{fg}+max({ϵ}^{-2},c\left){\delta }_{gg}\right)$$

Proof of Theorem 5

According to Theorem 3, there is ${\delta }_1\in E$ and $I\subseteq N^2$ which is ${\gamma }^{4}E$-negligible s.t.

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\left[\right(g^t({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}){)}^2]\le ({\gamma }^{kj}{)}^4{\delta }_1^{kj}$$

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\left[\right({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{)}^{t}g{g}^t({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj})]\le ({\gamma }^{kj}{)}^4{\delta }_1^{kj}$$

On the other hand, since ${\hat{P}}_{gg}$ is an $E(poly,rlog)$-orthogonal predictor for $g{g}^t$, there is ${\delta }_2\in E$ s.t.

$$\left|E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\right[({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{)}^t({\hat{P}}_{gg}^{kj}-g{g}^t\left)\right({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}\left)\right]|\le (E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}[\parallel {\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{\parallel }^4]+1){\delta }_2^{kj}$$

Since $\parallel {\hat{P}}_{1,2}^{kj}\left(x\right)\parallel \le {\gamma }^{kj}$, there is $c>0$ s.t.

$$\left|E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\right[({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{)}^t({\hat{P}}_{gg}^{kj}-g{g}^t\left)\right({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}\left)\right]|\le (c({\gamma }^{kj}{)}^4+1){\delta }_2^{kj}$$

$$\left|E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\right[({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{)}^t({\hat{P}}_{gg}^{kj}-g{g}^t\left)\right({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}\left)\right]|\le (c+{ϵ}^{-4}\left)\right({\gamma }^{kj}{)}^4{\delta }_2^{kj}$$

Combining the two together, we conclude that

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\left[\right({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{)}^t{\hat{P}}_{gg}^{kj}({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj})]\le ({\gamma }^{kj}{)}^4({\delta }_1^{kj}+(c+{ϵ}^{-4}\left){\delta }_2^{kj}\right)$$

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}[\parallel ({\hat{P}}_{gg}^{kj}{)}^{\frac{1}{2}}({\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}){\parallel }^2]\le ({\gamma }^{kj}{)}^4({\delta }_1^{kj}+(c+{ϵ}^{-4}\left){\delta }_2^{kj}\right)$$

$$\forall (k,j)\in N^2\setminus I:\left({\gamma }^{kj}{)}^{-1}{E}_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}\right[\parallel {\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{\parallel }^2]\le ({\gamma }^{kj}{)}^4({\delta }_1^{kj}+(c+{ϵ}^{-4}\left){\delta }_2^{kj}\right)$$

$$\forall (k,j)\in N^2\setminus I:E_{{\mu }^k\times {\hat{\sigma }}_1^{kj}\times {\hat{\sigma }}_2^{kj}}[\parallel {\hat{P}}_1^{kj}-{\hat{P}}_2^{kj}{\parallel }^2]\le \left({\gamma }^{kj}{)}^5\right({\delta }_1^{kj}+(c+{ϵ}^{-4}){\delta }_2^{kj})$$

Definition 11

Fix $E$ an space of rank 2 and $(A,\mu ,f,g)$ a relative estimation problem. Consider $\hat{P}$ a $Q^A$-valued $(poly,rlog)$-bischeme.$\hat{P}$ is called an $E(poly,rlog)$-perfect predictor for $(A,\mu ,f,g)$ when $E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f{)}^2]\in E$.

Proposition 2

Fix $E$ an error space of rank 2. Consider $(A,\mu ,f^{\ast },g)$ a relative estimation problem and $f:\mathrm{supp}\mu \to R^A$ bounded s.t. $f^{\ast }=g^{t}f$. Suppose ${\hat{P}}_f$ is an $E(poly,rlog)$-perfect predictor for $(\mu ,f)$. Then ${\hat{P}}_f$ is an $E(poly,rlog)$-perfect predictor for $(A,\mu ,f^{\ast },g)$.

Proof of Proposition 2

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f^{\ast }{)}^2]=E_{\mu \times {\hat{\sigma }}_P}[(g^t\hat{P}-g^{t}f{)}^2]$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f^{\ast }{)}^2]=E_{\mu \times {\hat{\sigma }}_P}[\left(g^t\right(\hat{P}-f\left){)}^2\right]$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f^{\ast }{)}^2]\le E_{\mu \times {\hat{\sigma }}_P}[\parallel g{\parallel }^2\parallel \hat{P}-f{\parallel }^2]$$

$$E_{\mu \times {\hat{\sigma }}_P}\left[\right(g^t\hat{P}-f^{\ast }{)}^2]\le sup\parallel g{\parallel }^2{E}_{\mu \times {\hat{\sigma }}_P}[\parallel \hat{P}-f{\parallel }^2]$$

Proof of Corollary

By Proposition 2, ${\hat{P}}_f$ is a ${\gamma }^8{E}^2(poly,rlog)$-perfect predictor for $(A,\mu ,f^{\ast },g)$ and in particular a ${\gamma }^8{E}^2(poly,rlog)$-optimal predictor for $(A,\mu ,f^{\ast },g)$. By Theorem 2 it is a ${\gamma }^{4}E(poly,rlog)$-orthogonal predictor for $(A,\mu ,f^{\ast },g)$. By Theorem 4, ${\hat{P}}_{gg}^{-1}{\hat{P}}_{fg}$ is a ${\gamma }^{2}E(poly,rlog)$-orthogonal predictor for $(A,\mu ,f^{\ast },g)$. Applying Theorem 5, we get the desired result (the condition $\parallel {\hat{P}}_{gg}^{-1}{\hat{P}}_{fg}\parallel \le \gamma$ holds because ${\hat{P}}_{fg}$ is bounded and ${\hat{P}}_{gg}$’s lowest eigenvalue is at most ${\gamma }^{-1}$).