Comment by srean
2 hours ago
Except for the fact that eventually we are all dead. So it is kind of important to get there faster.
For complicated hypotheses, where complicated is defined appropriately, it takes many many examples to realize that it was a wrong hypothesis all along. There lies the rub.
For a particular instance of a learning problem we can't tell much, however using a Occams razor over many instances, one would be correct more often than not. Provided, of course, the PAC assumptions are true or they are not very far from being true.
How far is not very far ? That gets very hairy to quantify.
To be clear, I was doing a reductio ad absurdum. PAC is precisely the kind of theoretical framework that concerns itself with asymptotic long-run behavior. An appropriate definition of simplicity certainly gets you to the goal much faster than the worst-case bound. For example, you could order hypotheses from most to less likely. But that would render the claim that simpler hypotheses are more likely rather tautological.
More typical definitions of simplicity, e.g. using the bit length of some kind of natural encoding, aren't guaranteed to offer any special advantages in terms of likelihood. So if you have prior knowledge that a particular hypothesis is more likely than another, but the less likely one is simpler in an intuitive sense, you shouldn't let that override you, but still prefer the more likely option. (And you don't need to take the circuitous route of coming up with a new encoding where the more likely hypothesis has a shorter bit length, either.)