Towards reflection with relative optimal predictor schemes

We construct a family or oracles relative to which all estimation problems which have approximate solutions in exponential time are generatable. Relatively to these oracles, we can use the optimal predictor scheme for assigning expectation values to arbitrary deterministic computations within time that is superquasipolynomial in the logarithm of the computation time. In particular, this should allow reflection in the sense of Garrabrant once we succeed to derandomize relative to the same oracle.

Results

New notation

Given and appropriate sets and , denotes a pair consisting of and an oracle machine that, supplied with oracle , halts on every input in and produces an output in . In particular, it defines a function from to in the obvious way.

For every , we fix a prefix free universal oracle machine with one program tape, input tapes and one output tape (we are only going to use a finite number of s). Given , is the following. When is computed, is interpreted as a program for and is executed with oracle for time . The resulting output is produced.

The notation means .

Given and , will denote the maximal runtime of on elements of . will denote the set of queries made to the oracle when applying to elements of .

All the theory of predictors with logarithmic advice can be relativized with respect to an arbitrary oracle. We denote the corresponding concepts using the oracle as a superscript. For example, the relativized version of a -optimal predictor schemes is -optimal predictor schemes etc.

Given a word ensemble, denotes . We previously defined a distributional estimation problem to be a pair where is a word ensemble and is a function from to . From now on, we allow to be defined only on . This doesn’t affect any of the previous results.

Omitting parentheses after an error space will mean zero advice. For example a -sampler is a -sampler.


We start by constructing an exponential time estimation problem which is complete in the class of exponential time estimation problem with samplable word ensembles with respect to -pseudo-invertible reductions (the concept of -pseudo-invertible reductions was previously introduced for unidistributional problems but it is defined in the same day for distributional problems, see Appendix A). Everything is relative to an arbitrary fixed oracle.

Construction 1

Fix .

Define to be the following word ensemble. Sampling is equivalent to sampling , and independently from and producing .

Define by

Theorem 1

Fix error spaces , of ranks 1 and 2 respectively. Assume that for any the function is in . Consider a distributional estimation problem. Suppose is a polynomial, and is a -sampler for s.t.

(i)

(ii)

(iii)

(iv)

(v)

It is possible to choose a polynomial and a -scheme of signature s.t.

(i)

(i)

(ii)

Denote to the -valued -scheme defined by

Then, is a -pseudo-invertible reduction of to .


The proofs of this and subsequent results are in Appendix B.

In particular, if has a uniform -optimal predictor scheme then we can construct a -optimal predictor scheme for any -samplable distributional estimation problem which has an exponential time approximation with error in . We don’t expect this to be true for reasonable error spaces and , but as the following construction (drawing heavily from Heller) shows it is true for some oracles.

Construction 2

Consider , a polynomial and . We give a recursive definition of for .

Recursion base:

Denote

Recursion step:

Finally, we define

Construction 3

Define to be the set of functions s.t.

It is easy to see is an error space.

Theorem 2

Consider and s.t. is a bijection on . Then, for any sufficiently large polynomial , is -generatable.

Note 1

For the identity function, admits a Monte Carlo algorithm. This is too strong for our purposes since it means there is no logical uncertainty in exponential time problems. Such oracles can be regarded as bounded analogues of reflective oracles.

Note 2

It is easy to see that .


Theorem 2 is insufficient by itself to enable reflection with optimal predictor schemes relative to since is a random algorithm. Potentially this can be solved by derandomization but at present we don’t know whether under what conditions derandomization with respect to is possible.

Appendix A

Fix an error space of rank 2.

Definition A

Consider , distributional estimation problems, a -valued -bischeme. is called a -pseudo-invertible reduction of to when there is a polynomial s.t. the following conditions hold:

(i)

(ii)

(iii) There is and a -valued -bischeme s.t.

(iv) There is a -valued -scheme s.t.

Such is called a -pseudo-inverse of .

a -valued -scheme is called a -pseudo-invertible reduction of to when it becomes such when adding trivial dependence on .

Theorem A

Suppose there is a polynomial s.t. . Consider , distributional estimation problems, a -pseudo-invertible reduction of to and a -optimal predictor scheme for . Define by . Then, is a -optimal predictor scheme for .


Theorem A.1 is proved exactly the same way as Theorem 8 for unidistributional problems and we leave out the details.

Appendix B

Proof of Theorem 1

We need to show the 4 defining conditions of -pseudo-invertible reductions.

(i)

Using assumption (i), we get the required result.

(ii)

Since is a -sampler for , we get

(iii) Define by

Consider , , , .

(iv) Define by

Proposition B

Consider , a polynomial and . Then

(i)

(ii)

(iii)

(iv)

(v)

Proof of Proposition B

(i) By induction: implies .

(ii) If then since all words in begin with . If then by (i).

(iii) If then and by (i) . If then there is s.t. and because any word in has length .

(iv) All oracle queries made in return the same values when addressed to for : queries that return keep returning since they are included in and queries that return keep returning by (i).

(v) Note that (iv) implies and apply the same argument as in (iv) to .

Proof of Theorem 2

We describe the -generator for . is the -scheme of signature defined as follows. Consider the computation of .

is computed, where . is computed. For each , we compute defined as rounded to binary digits. is computed within binary digits. The output is .

reproduces precisely since preserves .

It is easy to see that there is a polynomial s.t. for any we have . Take any polynomial s.t. . By Lemma C, (iii) we have

The first term approximates within error by the construction of . By Lemma C, (v) it approximates within the same error. The second terms vanishes for all but a negligible fraction of the -s by the properties of and .

No comments.