Random guessing for all values. For one, random guessing might be fast enough. For another, it doesn’t have to learn for all values, just for most. Mathematically, the implications are significantly different. The NFL doesn’t tell us that. The NFL tells us we can’t design a single algorithm which performs optimally for all inputs [1] [2]. 'Well' is relative. It doesn’t need to be optimal, it just needs to be fast enough. Just like O(n log n) is fast enough to sort several hundred million integers on your CPU in a second or so, there is a point of computing power for which O(q) is fast enough to generally learn, whatever q is, even if it’s no better than random. Now, if you can prove q = n! or some such, you can demonstrate it’s not achievable with the mass we have to work with in the universe. But nobody’s proved that, and the NFL certainly doesn’t. Furthermore, 'for all values' is misleading. Consider quicksort. Quicksort performs better than most other algorithms, at the price of a significantly worse worst-case (There exist analogous NFLs for sort). Likewise, there may (you might even be able to prove there does) exist a general-purpose learning algorithm which performs better than random for 99.99% of problems, at huge cost for the 0.01%. Unless the human brain is doing something odd with quantum physics, or has some unknown metaphysical component – unless it is strictly more powerful than an LBA – then there is, by definition, some level of FLOPS after which a computer can learn faster than a human brain, even for random guessing. I’m not making claims or predictions. I’m not saying we’ll have a sentient computer in the next ten, or hundred, or thousand years. I’m simply saying, it’s theoretically possible (1) given enough computing power and (2) assuming the human brain is an LBA.I know that there is no learning algorithm that is better than random guessing, because there is a theorem that tells me so.
We cannot now nor will we ever be able to devise a learning algorithm that performs well for every problem.