Right in the Short Run

A little bit of background on myself: I love computers, and I love economics. Unfortunately, the two disciplines mix pretty infrequently. That’s why I let out a little yelp when I found this paper, called “Fact-Free Learning” by Enriqueta Aragones, Itzhak Gilboa, Andrew Postlewaite, and David Schmeidler. The paper is trying to present a model of how we understand information that is already available to us. Sometimes, we figure out something new by looking at the data we have in a new light — fact-free learning!

But fact-free learning is tough. The real breakthroughs are often unexpected, and they may happen slowly. The authors argue that some familiar tools of economics and computer science, when brought together, can explain this phenomenon. Before I get into their argument, I need to explain something called complexity, because the central argument of the paper relies on it.

Computational complexity is the study of how computer algorithms scale as the size of the problem they are trying to solve increases. Usually we are looking for some sort of bound on the amount of time it will take the algorithm to finish, given a problem of size n.

Some algorithms may not scale so well. Seriously, they might not scale so well. We’re not entirely sure! (Why? Wikipedia explains.) This class of algorithms is called NP, and we are pretty sure that any implementation of an NP-hard problem will end up taking a few lifespans-of-the-universes to complete for even a small size input.

Now let’s get back to the paper. Remember how I said that it brought together tools of both computer science and economics? Well, the economic tool these fellows bring to the table is the regression. Say you have information on lots of variables, and you want to see which variables explain some phenomenon. If you pick out a few of these variables, you can regress the measure of the phenomenon on those variables to determine which variables are relevant.

But what if you can only use a few variables — say k — in the regression at once? Then you might want to run the regression with every possible combination of k variables, looking for the one that does the best job explaining the phenomenon. The authors argue that this process — finding the set of k variables that does the best job explaining a phenomenon in a regression — is a lot like fact-free learning. But there’s a catch:

Linear regression is a structured and relatively well-understood problem, and one may hope that, using clever algorithms that employ statistical analysis, the best set of k regressors can be found without actually testing all (mCk) subsets. Our main result is that this is not the case. Formally, we prove that finding whether k regressors can obtain a prespecified value of R2, r, is, in the language of computer science, NP-Complete. Moreover, we show that this problem is hard (NP-Complete) for every positive value of r.

The implication is that fact-free learning is really difficult for computers. And if it’s difficult for computers, it’s probably really difficult for people too!