I think PAC learning refers specifically to algorithms with rigorous bounds on their probability of error. There are theorems saying that Bayesian updaters get this automatically, but as far as I know they assume that (1) nature’s distribution coincides with your subjective distribution and (2) you are implementing inference exactly. Since both of these are pretty dubious, I don’t think most statistical machine learning is considered PAC. The examples that would come to mind in my view are things like boosting, multi-armed bandit, and sparse recovery, but I’m not really an expert in this area.
ETA: There are also still tons of people adopting the symbolic approach to AI, which is another reason why I’d be hesitant to label all of machine learning as PAC (even if the symbolic approach seems likely to be a dead end, I’d rather not pretend that it’s not still in use).
I agree that in practice PAC designates a specific subset of ideas and papers, my point is just that “probably approximately correct” doesn’t help to distinguish that subset (words like boosting and multi-armed bandit do). The VC-theory is totally based on PAC-style results (though it would be better to say PAC is based on VC-style results) and the MDL/MML people have similar generalization theorems as well.
I think PAC learning refers specifically to algorithms with rigorous bounds on their probability of error. There are theorems saying that Bayesian updaters get this automatically, but as far as I know they assume that (1) nature’s distribution coincides with your subjective distribution and (2) you are implementing inference exactly. Since both of these are pretty dubious, I don’t think most statistical machine learning is considered PAC. The examples that would come to mind in my view are things like boosting, multi-armed bandit, and sparse recovery, but I’m not really an expert in this area.
ETA: There are also still tons of people adopting the symbolic approach to AI, which is another reason why I’d be hesitant to label all of machine learning as PAC (even if the symbolic approach seems likely to be a dead end, I’d rather not pretend that it’s not still in use).
I agree that in practice PAC designates a specific subset of ideas and papers, my point is just that “probably approximately correct” doesn’t help to distinguish that subset (words like boosting and multi-armed bandit do). The VC-theory is totally based on PAC-style results (though it would be better to say PAC is based on VC-style results) and the MDL/MML people have similar generalization theorems as well.
I agree. What are MDL/MML though?
Minimum description length/minimum message length.