Improved error space for universal optimal predictor schemes
post by Vanessa Kosoy (vanessa-kosoy) · 2015-09-30T15:08:53.000Z · LW · GW · 0 commentsContents
Results Construction Proposition 1 Proposition 2 Lemma Theorem 1 Theorem 2 Appendix Proof of Proposition 1 Proof of Proposition 2 None No comments
We construct an error space which is smaller than but admits analogous existence theorems for optimal predictor schemes.
Results
Construction
Given we define to be the set of functions s.t. . It is easily seen is an error space.
Given , denote . We define to be the set of bounded functions s.t. for any , if then
We define .
Proposition 1
is an error space for any . is an error space.
Proposition 2
Consider a polynomial . There is a function s.t.
(i)
(ii) For any function we have
The proofs of Propositions 1 and 2 are in the Appendix. The following are proved using exactly like the analogous statements for and we omit the proofs.
Lemma
Consider a distributional estimation problem, , -predictor schemes. Suppose a polynomial and are s.t.
Then s.t.
Theorem 1
Consider a distributional estimation problem. Define by
Define by
Then, is a -optimal predictor scheme for .
Theorem 2
There is an oracle machine that accepts an oracle of signature and a polynomial where the allowed oracle calls are for and computes a function of signature s.t. for any , a distributional estimation problem and a corresponding -generator, is a -optimal predictor scheme for .
Appendix
Proof of Proposition 1
The only slightly non-obvious condition is (v). We have
Proof of Proposition 2
Given functions s.t. for , the proposition for implies the proposition for by setting
Therefore, it is enough to prove to proposition for functions of the form for .
Consider any . We have
Since takes values in
Similarly
The last two equations imply that
Raising to a power is equivalent to adding a constant to , therefore
Since we can choose satisfying condition (i) so that
It follows that
0 comments
Comments sorted by top scores.