<p>I think you're confusing two notions of hardness: computational and statistical. </p>

<p>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.</p>

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

CC BY-SA 4.0
2018-12-04T22:22:13.003Z
@Areyh Thanks for the efforts. But I think I did not communicate my question well. In Q1 I am *not* thinking about any hardness. I am merely asking if in general for arbitrary concept classes (which need not be binary valued) can the "gamma-weak learner" (using Shai&Shai's book's notation from page 131 but lets say I use it for real valued concept classes too) always be lifted to a PAC-learner for the same hypothesis class? (..Isnt this what Boosting is doing for binary classes?..)
gradstudent
CC BY-SA 4.0
2018-12-04T22:26:01.250Z
Oh, I see. You should look at the original Freund-Schapire paper:
https://www.sciencedirect.com/science/article/pii/S002200009791504X?via%3Dihub
which discusses extensions to both the multiclass and the real-valued case.
Aryeh
CC BY-SA 4.0
2018-12-04T22:26:40.013Z
I haven't followed the multiclass literatature, but for real-valued, I believe we have a definite improvement:
https://www.cs.bgu.ac.il/~mlt142/wiki.files/real-compression.pdf
Aryeh
CC BY-SA 4.0
2018-12-04T22:26:48.980Z
Sure SQDim is a measure of the minimum number of queries required of a certain type. But In Q2 I am asking as to why does Blum claim that SQDim is a measure of hardness for a weak learner? (...His Theorem 2 says "if SQdim_D(C) > poly(n) then you *can't* weak-learn C over D by
SQ algorithms."...) Is that a theoretical limitation that he only talks of weak-learners or is it somehow true that if a weak-learner cant learn something by SQ algorithms then there cannot exist any PAC learner either using SQ-algorithms? Specific to binary classes is something like this true?
gradstudent
CC BY-SA 4.0
2018-12-04T22:32:22.827Z
"You can't weak-learn" meaning that you might need to make exponentially many queries. I think this holds for real-valued classes as well. For multiclass, you need to embed them into the real numbers for SQ to make sense. For example, here
https://www.cs.bgu.ac.il/~karyeh/shuff.pdf
we used 3-valued queries (Sec. 3.1)
Aryeh
CC BY-SA 4.0
2018-12-04T22:33:15.030Z
You literally have a paper on everything that comes to my mind! :D
gradstudent
CC BY-SA 4.0
2018-12-04T22:34:19.183Z
Feel free to email me for a more in-depth discussion.
Aryeh
CC BY-SA 4.0
2018-12-04T22:36:04.760Z
@Areyh So you think Blum's Theorem 2 is not tied to weak-learning or pac-learning per se but is a lowerbound on the number of statistical queries required for a SQ algorithm. And this SQ-algorithm can be doing weak or pac learning? Is there a book or paper reference for this theorem in Blum's notes?
gradstudent
CC BY-SA 4.0
2018-12-04T22:38:12.457Z
I'd start with these 2:
http://www.levreyzin.com/presentations/ALT2018_SQ_tutorial.pdf
https://www.sciencedirect.com/science/article/pii/S0022000012000232
Aryeh
CC BY-SA 4.0
2018-12-04T22:39:37.680Z
Of course, the origianl paper by Blum et al. is also quite readable: http://dl.acm.org/citation.cfm?id=195147
Aryeh
CC BY-SA 4.0
2018-12-04T20:56:54.867Z
2018-12-05T11:07:29.677Z
2018-12-05T11:07:29.677Z
Aryeh
<p>For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (<a href="http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt" rel="nofollow noreferrer">http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt</a>) and also his notes on SQ-Learning (<a href="http://www.cs.cmu.edu/~avrim/ML12/lect0321.txt" rel="nofollow noreferrer">http://www.cs.cmu.edu/~avrim/ML12/lect0321.txt</a>)</p>

<p>It seems to me that the following are true,</p>

<ul>
<li>That what is difficult to PAC-learn is also difficult to weak learn</li>
<li>If a binary valued/classification concept class has a weak learner then AdaBoost can produce a PAC-learner for it. </li>
</ul>

<p>My questions are two fold,</p>

<ol>
<li><p>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? </p></li>
<li><p>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..)</p></li>
</ol>

CC BY-SA 4.0
2018-12-04T22:20:21.753Z
Can't you reduce multi-class learning to a binary classification task by looking bits of the label, and still use boosting?
Sasho Nikolov
CC BY-SA 4.0
2018-12-04T22:29:28.633Z
@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
CC BY-SA 4.0
2018-12-04T22:38:57.557Z
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
<machine-learning><lg.learning>
Is there a gap between weak learning and PAC-learning?
gradstudent
# Is there a gap between weak learning and PAC-learning?

(Asked by: username_0 on 2018-12-04)

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

**Tags:** machine-learning, lg.learning
> **Comments:**
> **username_1**: Can't you reduce multi-class learning to a binary classification task by looking bits of the label, and still use boosting?  
> **username_2**: @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...  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_2 on 2018-12-04. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: @Areyh Thanks for the efforts. But I think I did not communicate my question well. In Q1 I am *not* thinking about any hardness. I am merely asking if in general for arbitrary concept classes (which need not be binary valued) can the "gamma-weak learner" (using Shai&Shai's book's notation from page 131 but lets say I use it for real valued concept classes too) always be lifted to a PAC-learner for the same hypothesis class? (..Isnt this what Boosting is doing for binary classes?..)  
> **username_2**: Oh, I see. You should look at the original Freund-Schapire paper: https://www.sciencedirect.com/science/article/pii/S002200009791504X?via%3Dihub which discusses extensions to both the multiclass and the real-valued case.  
> **username_2**: I haven't followed the multiclass literatature, but for real-valued, I believe we have a definite improvement: https://www.cs.bgu.ac.il/~mlt142/wiki.files/real-compression.pdf  
> **username_0**: Sure SQDim is a measure of the minimum number of queries required of a certain type. But In Q2 I am asking as to why does Blum claim that SQDim is a measure of hardness for a weak learner? (...His Theorem 2 says "if SQdim_D(C) > poly(n) then you *can't* weak-learn C over D by SQ algorithms."...) Is that a theoretical limitation that he only talks of weak-learners or is it somehow true that if a weak-learner cant learn something by SQ algorithms then there cannot exist any PAC learner either using SQ-algorithms? Specific to binary classes is something like this true?  
> **username_2**: "You can't weak-learn" meaning that you might need to make exponentially many queries. I think this holds for real-valued classes as well. For multiclass, you need to embed them into the real numbers for SQ to make sense. For example, here https://www.cs.bgu.ac.il/~karyeh/shuff.pdf we used 3-valued queries (Sec. 3.1)  
> **username_0**: You literally have a paper on everything that comes to my mind! :D  
> **username_2**: Feel free to email me for a more in-depth discussion.  
> **username_0**: @Areyh So you think Blum's Theorem 2 is not tied to weak-learning or pac-learning per se but is a lowerbound on the number of statistical queries required for a SQ algorithm. And this SQ-algorithm can be doing weak or pac learning? Is there a book or paper reference for this theorem in Blum's notes?  
> **username_2**: I'd start with these 2: http://www.levreyzin.com/presentations/ALT2018_SQ_tutorial.pdf https://www.sciencedirect.com/science/article/pii/S0022000012000232  
> **username_2**: Of course, the origianl paper by Blum et al. is also quite readable: http://dl.acm.org/citation.cfm?id=195147  

---

