Vadim Kosoy edited The_following_theorem_is_the__.tex  about 8 years ago

Commit id: fd4d572b3b5ae2222fe912748cd699ab212e89e0

deletions | additions      

       

\begin{proof}  Assume $P$ is a $\Delta(poly,log)$-optimal predictor scheme. Fix $S: \Words \xrightarrow{\Gamma} \Rats$ with $\R_S \geq \R_P$.  Consider$k,j,s \in \Nats$, $Q: \Words^2 \xrightarrow{alg} \Rats$. Define  $t := \sigma 2^{-a}$ where $\sigma \in \{ \pm 1 \}$ and $a \in \Nats$. Choose $h: \Nats^2 \rightarrow \Nats$ a polynomial s.t. $2^{-h} \in \mathcal{E}$.  Define $R: \Words^2 \xrightarrow{alg} [0,1]$ to compute $\eta(P $Q: \Words \xrightarrow{\Gamma} \Rats$ s.t. given $k,j \in \Nats$, $x \in \Supp \mu^k$, $y \in \WordsLen{\R_P(k,j)}$ and $z \in \WordsLen{\R_P(k,j) - \R_S(k,j)}$, $\Abs{Q^{kj}(x,yz) - (P^{kj}(x,y)  + tQ)$ rounded within error $2^{-h}$. By Lemma B.1 t S^{kj}(x,yz))} \leq 2^{-h(k,j)}$.  $$ E_{\mu^k \times U^{r(k,j)}}[(P^{kj}-f)^2] \leq E_{\mu^k \times U^{r(k,j)} \times U^s}[(R-f)^2] + \tilde{\delta}(k,j,T_R^\mu(k,r(k,j)+s),2^{|R|}) $$