It's interesting how terms lose their original relevance. Nowadays it would seem silly to name a subfield of machine learning "probably approximately correct", since that describes all of machine learning.
From the article:
Successive contributions by Kearns, Schapire, and Freund not only resolved this question in the very unexpected positive direction, but yielded the boosting technique, perhaps the most powerful general learning method now known.
Valiant is talking specifically about the AdaBoost algorithm. I'm not sure boosting is the most powerful general learning method now known - the support vector machine seems more powerful - but it certainly has the best ratio of power:simplicity. Anyone with a passing interest in machine learning should implement AdaBoost and play around with it a bit.
I disagree with you. PAC is about how to analyse learning algorithms in terms of sample complexity. It is not about AdaBoost, nor Neural networks, or whatever. Actually, the learning algorithm is a black box in the PAC model (or metamodel if you prefer).
I think the name is perfect and evergreen. The same way we want to analyse the correctness of algorithms and know its time (or resource) complexity, for learning algorithms you also have another dimension which is how much data you need (sample complexity).
PAC is trying to answer what is the bound on the size of training dataset needed to achieve a certain prediction correctness with a certain confidence (probability).
http://cacm.acm.org/magazines/2011/6/108655-qa-a-lifelong-learner/fulltext
Wow, this is quite interesting. What are your thoughts?