4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Can't you reduce multi-class learning to a binary classification task by looking bits of the label, and still use boosting? $\endgroup$
    – Sasho Nikolov
    Dec 4, 2018 at 22:20
  • $\begingroup$ @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... $\endgroup$
    – Aryeh
    Dec 4, 2018 at 22:29
  • $\begingroup$ 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? $\endgroup$
    – gradstudent
    Dec 4, 2018 at 22:38

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.