Warning: mostly for fun / basic science

##Preliminaries

Hierarchy theorems

The time hierarchy theorem is one of the simplest results in complexity theory. It says that if $f\left(n\right)\gg g\left(n\right)$, then there are functions that we can compute in time $f\left(n\right)$ that we can't compute in time $g\left(n\right)$. For example, there are functions that you can compute in $n^2$ time that you can't compute in $n$ time.

Hierarchy theorems are proved by diagonalization---consider the problem, "does machine $M$ halt in time at most $n^{1.5}$?" This problem can be easily solved in $n^2$ time. But if any machine $M$ solves this problem in $n$ time then we can get a contradiction by asking $M$ about itself.

This proof strategy is very blunt. One way to formalize its bluntness is to introduce the notion of relative complexity. Rather than considering normal computers, we consider a computer that has access to a black box computing a particular function $f$. Hierarchy theorems hold relative to any function $f$.

Relativization is a hallmark of "easy" complexity theoretic results (i.e. those that we can prove). We can prove very few separations that don't relativize. (Scott Aaronson has introduced a slightly stronger notion of algebrization which more accurately captures what we can actually prove, and we can prove a few more lower bounds on low-depth circuits.)

Distributional estimation problems

A distributional estimation problem is a sequence of distributions ${\mu }_n$ over pairs $(x,y)\in {\{0,1\}}^n\times [0,1]$. The goal of an estimator is to approximate $y$ given $x$. The score of a estimator $A$ on ${\mu }_n$ is the expected squared error, i.e. the expectation of ${\left(A\right(x)-y)}^2$, for pairs $(x,y)$ drawn from ${\mu }_n$. If $A$ is a probabilistic estimator, then we also take an expectation over $A$'s internal randomness.

(This definition is due to Vadim Kosoy.)

Let's say that $A$ is a better estimator than $B$ on a distributional estimation problem if there is a constant $ϵ$ and an $N$ such that for every $n>N$, $A$'s score on ${\mu }_n$ is at least $ϵ$ higher than $B$'s score (i.e., such that the lim inf of $A$'s score minus $B$'s score is strictly positive).

Time hierarchy for distributional estimation problems

Now we can ask:

Is there a distributional estimation problem ${\mu }_n$ and an estimator $A$ running in time $O\left(n^3\right)$ such that $A$ is a better estimator on ${\mu }_n$ than any estimator $B$ running in time $O\left(n^2\right)$?

The answer is almost certainly "yes," and there is a very natural hard problem---sample a machine $A$ which runs in time $n^{2.5}$ and estimate the expected value of $A\left(\right)$.

Time hierarchy does not relativize for distributional estimation problems

We can construct a probabilistic oracle such that exactly the same set of distributional estimation problems can be solved in time $O\left(n\log n\right)$ as can be solved by any algorithm running in any amount of time.

Namely, consider the construction of reflective oracles from this paper. With this oracle in hand, for any estimator $A$ running in any amount of time, there is an estimator $B$ running in time $O\left(n\log n\right)$ which approximates the results of running $A$ up to error $1/n$, and in particular which is not a worse predictor than $A$.

On input $x$, $A$ queries the reflective oracle to estimate the expected value of $B\left(x\right)$. It starts by comparing this expected value to $1/2$, then performs a binary search to narrow down the value to an interval of length $1/n$. This gives us error of $o\left(1\right)$, and it works regardless of how expensive $B$ is to compute.

This argument is relative to a certain probabilistic oracle. It would be more convincing if the containment failed relative to some deterministic oracle. I'm not sure if it does.

A natural candidate deterministic oracle is one which takes as input a randomized (oracle) Turing machine $M$, a probability $p$, an accuracy $ϵ$, and an auxiliary input $x\in {\{0,1\}}^{1/ϵ}$. The oracle makes no guarantees at all about its behavior on any particular input $x$. But if $M$ accepts with probability strictly more than $p+ϵ$ in time $T$, then the oracle guarantees that it returns $1$ on at least $2/3$ of the possible tuples $(M,p,ϵ,x)$. And conversely, if $M$ accepts with probability strictly less than $p-ϵ$, then the oracle guarantees that it returns $1$ on at most $1/3$ of the possible tuples $(M,p,ϵ,x)$.

If such an oracle exists, then time hierarchy for distributional estimation problems certainly doesn't hold with respect to this oracle. I can't really tell whether such an oracle exists, my guess is that it does.

I think that the existence of such a deterministic oracle is itself an interesting question.

Conclusion

Hierarchy theorems are practically the only "easy" separation results in complexity theory. But they are easy to prove for reasons that seem morally unrelated to the real reasons that they are true.

In some sense distributional estimation problems are more natural than conventional decision problems. If we can't prove time hierarchy for these problems, it is arguably one of the most fundamental gaps in our understanding of complexity theory, even more glaring than (for example) P vs PSPACE.

Because time hierarchy doesn't seem to relativize for distributional estimation problems, I think there is a good chance that existing techniques can't prove it. That said, there may also be a simple argument for hierarchy that I overlooked.