Quasi-optimal predictors

post by Vanessa Kosoy (vanessa-kosoy) · 2015-12-25T14:17:05.000Z · score: 2 (2 votes) · LW · GW · 2 comments

Contents

  Definition 1
  Theorem 1
  Theorem 2
  Theorem 3
  Theorem 4
  Theorem 5
  Theorem 6
  Definition 2
  Theorem 7
  Definition 3
  Theorem 8
  Theorem 9
    Appendix
  Lemma 1
  Proof of Lemma 1
  Lemma 2
  Proof of Lemma 2
  Proof of Theorem 1
  Lemma 3
  Proof of Lemma 3
  Proof of Theorem 2
  Proof of Theorem 4
  Proof of Theorem 7
  Lemma 4
  Proof of Lemma 4
  Proof of Theorem 6
  Proof of Theorem 8
  Proof of Theorem 9
2 comments

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 a distributional decision problem, a quasi-optimal predictor for is a family of polynomial size Boolean circuits s.t. for any family of polynomial size Boolean circuits we have

where .

Theorem 1

Consider a distributional decision problem and a quasi-optimal predictor for . Suppose , are s.t.

Then:

Theorem 2

Consider a word ensemble and , disjoint languages. Suppose is a quasi-optimal predictor for and is a quasi-optimal predictor for . Then, is a quasi-optimal predictor for .

Theorem 3

Consider a word ensemble and , disjoint languages. Suppose is a quasi-optimal predictor for and is a quasi-optimal predictor for . Then, is a quasi-optimal predictor for .

Theorem 4

Consider , distributional decision problems with respective quasi-optimal predictors and . Define as the family of circuits computing . Then, is a quasi-optimal predictor for .

Theorem 5

Consider and a word ensemble. Assume is a quasi-optimal predictor for and is a quasi-optimal predictor for . Then is a quasi-optimal predictor for

Theorem 6

Consider and a word ensemble. Assume . Assume is a quasi-optimal predictor for and is a quasi-optimal predictor for . Define as the circuit family computing

Then, is a quasi-optimal predictor for .

Definition 2

Consider a word ensemble and two circuit families. We say is quasisimilar to relative to (denoted ) when .

Theorem 7

Consider a distributional decision problem, a quasi-optimal predictor for and a polynomial size family. Then, is a quasi-optimal predictor for if and only if .

Definition 3

Consider , distributional decision problems, a polynomial size family of circuits. is called a (non-uniform) strong pseudo-invertible reduction of to when there is a polynomial s.t. the following conditions hold:

(i)

(ii) There is s.t.

(iii) There is a polynomial and a family of polynomial size circuits s.t.

(iv) There are polynomial size circuits s.t.

Theorem 8

Consider , distributional decision problems, a strong pseudo-invertible reduction of to and a quasi-optimal predictor for . Define as the family of circuits computing . Then, is a quasi-optimal predictor for .

Theorem 9

Consider a one-to-one non-uniformly hard one-way function. Define . Then, is a quasi-optimal predictor for .

Appendix

Lemma 1

Consider a distributional decision problem and a family of polynomial size. Then, is a quasi-optimal predictor if and only if there is a function s.t.

(i) is non-decreasing in the second argument.

(ii) For any polynomial :

In the following, we will call functions satisfying conditions (i) and (ii) quasinegligible.

(iii) for any we have

Proof of Lemma 1

Define

Lemma 2

Consider a distributional decision problem and a corresponding quasi-optimal predictor. Then, there is a function s.t.

(i) is non-decreasing in the second and third arguments.

(ii) For all polynomials :

(iii) for all , and we have

Proof of Lemma 2

Given , denote

Consider circuit computing the following function:

There is a polynomial s.t. . By Lemma 1,

for quasinegligible.

Integrating the inequality with respect to from to , we get

Proof of Theorem 1

Define

Assume to the contrary that there is and an infinite set s.t.

Define as the circuits computing

is bounded by a polynomial since produces binary fractions of polynomial size therefore it is possible to compare them to the fixed numbers using a polynomial size circuit even if the latter have infinite binary expansions.

We have

Define to be truncated to the first significant binary digit. Define as the circuits computing

By the assumption, has binary notation of bounded size, therefore is bounded by a polynomial.

Applying Lemma 2 we get

for vanishing at infinity.

Obviously , therefore

The expression on the left hand side is a quadratic polynomial in which attains its maximum at and has roots at and . is between and , but not closer to than . Therefore, the inequality is preserved if we replace by .

Substituting the equation for we get

Thus vanishes at infinity on , which is a contradiction.

Lemma 3

Consider a distributional decision problem. If is a quasi-optimal predictor for then there are and a quasinegligible function s.t. for any we have

Conversely, suppose and is a polynomial size family for which there is a quasinegligible function s.t. for any we have

Define to be s.t. computing is equivalent to computing rounded to digits after the binary point. Then, is a quasi-optimal predictor.

Proof of Lemma 3

Assume is an optimal predictor. Consider and where and . The function can be approximated by a circuit of size for some fixed polynomial , within rounding error s.t. . By Lemma 1,

where is quasinegligible. is bounded by a negligible function and therefore can be ignored by redefining . As in the proof of Theorem 1, can be dropped.

The expression on the left hand side is a quadratic polynomial in . Explicitly:

Moving to the right hand side and dividing both sides by we get

Take where is the rounding error. We get

Conversely, assume that for any

Consider . We have

can be computed by a circuit of size polynomial in and . Applying the assumption we get

where is quasinegligible. Noting that and we get

Observing that is bounded by a negligible function, we get the desired result.

Proof of Theorem 2

Consider . We have

Using Lemma 3:

Therefore

Using Lemma 3 again we get the desired result.

Proof of Theorem 4

We have

Therefore, for any

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

For any given , can be computed by a circuit with input of size polynomial in and . Applying Lemma 3 to , we get

where is a polynomial and is quasinegligible. Since is bounded by a polynomial in for , we get the bound we need.

For the second term, we have

For any given , can be computed by a circuit with input of size polynomial in , and . Applying Lemma 3 to , we get

Again, we got the required bound.

Proof of Theorem 7

Assume is a quasi-optimal predictor. Applying Lemma 3 to predictor and circuits computing , we get

for some vanishing at infinity. Applying Lemma 3 to predictor and circuits computing , we get

for some vanishing at infinity. We have

Conversely, assume . Consider some . We have