# Is there a gap between weak learning and PAC-learning?

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,

1. 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?

2. 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..)

• Can't you reduce multi-class learning to a binary classification task by looking bits of the label, and still use boosting? Dec 4, 2018 at 22:20
• @SashoNikolov wouldn't this approach also be true for regular $k$-class classification (just learn $\log k$ classifiers), and hence trivialize the whole problem? There are subtle issues involving how the labels interplay, combinatorial dimensions (Graph, Natarajan, etc), upper and lower sample complexity bounds... Dec 4, 2018 at 22:29
• So one interpretation of AdaBoost is that it says weak learning and pac-learning are the same for binary concept classes? Basically AdaBoost seems to say that any weak-learner for a binary valued class can be converted into a pac-learner for the same class, right? Or only "improper" pac-learner? Dec 4, 2018 at 22:38