Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Time hierarchy theorems for distributional estimation problems, published by Paul Christiano on the AI Alignment Forum. Warning: mostly for fun / basic science
Hierarchy theorems The time hierarchy theorem is one of the simplest results in complexity theory. It says that if f n ≫ g n , then there are functions that we can compute in time f n that we can't compute in time g n . 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 μ n over pairs x y ∈ 0 1 n × 0 1 . The goal of an estimator is to approximate y given x . The score of a estimator A on μ n is the expected squared error, i.e. the expectation of A x − y 2 , for pairs x y drawn from μ 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 μ 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 μ n and an estimator A running in time O n 3 such that A is a better estimator on μ n than any estimator B running in time O n 2 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 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 n log n 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 n log n 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 x . 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 1 , 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 ∈...