Computational vs Statistical Limits of Learning

There are two entirely different reasons a learning problem can be hard, and it is easy to conflate them. A statistical limit means the data itself simply doesn't contain enough information — no algorithm, however powerful or clever, could reliably learn the right answer from that few examples, because many different underlying truths are equally consistent with the data observed. A computational limit means the opposite: the data contains plenty of information to determine the answer in principle, but no algorithm running in a reasonable amount of time is known (or believed) to exist that can extract it.

The distinction matters because the fix is completely different in each case. A statistical limit is solved by collecting more data — there is no algorithm, however clever, that gets around too little information. A computational limit is not solved by more data at all; a problem that is SQ-hard or NP-hard under a cryptographic-style hardness assumption stays just as hard with a billion more examples, because the bottleneck was never the information content of the data, it was the cost of searching through it.

The classic illustration is learning parity functions with noisy labels. Information-theoretically, a small number of examples already pins down the true parity function uniquely — the statistical problem is easy. But every known algorithm for finding it in the presence of noise takes time exponential in the number of variables, and this is believed (though not proven) to be a genuine computational barrier, not a lack of cleverness — the same hardness underlies certain cryptographic constructions, which rely on exactly this: easy to state, hard to search, given enough noise.

Recognizing which kind of limit a problem hits determines whether the right move is "get more data" or "this needs a fundamentally different, and possibly nonexistent, algorithm," and conflating the two leads teams to throw data at a problem that data alone cannot fix.