For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt) and also his notes on SQ-Learning (http://www.cs.cmu.edu/~avrim/ML12/lect0321.txt)
It seems to me that the following are true,
- That what is difficult to PAC-learn is also difficult to weak learn
- If a binary valued/classification concept class has a weak learner then AdaBoost can produce a PAC-learner for it.
My questions are two fold,
But its not clear if one can boost a weak learner for an arbitrary concept class into a PAC learner for the same class. Or what is the best known statement in this direction?
Why is SQDim presented as a measure of hardness of weak learning? Is that a limitation of theory that we cannot get hardness of PAC-learning from SQDim? (..except in the case of binary classification when AdaBoost will lift from weak to PAC..)