# 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? – Sasho Nikolov Dec 4 '18 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... – Aryeh Dec 4 '18 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? – gradstudent Dec 4 '18 at 22:38

I think you're confusing two notions of hardness: computational and statistical.

In Q1, you point out, essentially, that boosting produces an improper learner. I think what you're asking then, is: Is there a concept class which is (computationally) hard to learn properly but can be efficiently learned via boosting? I believe there should be such examples, but can't think of one off-hand.

In Q2, please note that SQDim refers to hardness in a statistical sense -- i.e., the minimal number of statistical queries required. (We don't have any unconditional computational hardness results but plenty of statistical ones.)

• Oh, I see. You should look at the original Freund-Schapire paper: sciencedirect.com/science/article/pii/… which discusses extensions to both the multiclass and the real-valued case. – Aryeh Dec 4 '18 at 22:26
• I haven't followed the multiclass literatature, but for real-valued, I believe we have a definite improvement: cs.bgu.ac.il/~mlt142/wiki.files/real-compression.pdf – Aryeh Dec 4 '18 at 22:26
• You literally have a paper on everything that comes to my mind! :D – gradstudent Dec 4 '18 at 22:33
• – Aryeh Dec 4 '18 at 22:38
• Of course, the origianl paper by Blum et al. is also quite readable: dl.acm.org/citation.cfm?id=195147 – Aryeh Dec 4 '18 at 22:39