<p>The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier weights are concentrated on some modes can be PAC learnt in polynomial time. Also it trivially follows that in $2^n$ queries one can learn any Boolean function on the $n-$Hamming cube. </p>

<p>My question is two fold, </p>

<ul>
<li><p>For what concept classes do we know of high ($2^n$?) query lowerbound for PAC learning? If the proof is short then it would be very helpful if you could kindly type it in or give a reference. </p></li>
<li><p>For Boolean functions whose Fourier spectrum seems very evenly spread out over the modes it seems that it should be hard to learn them in a few queries. Is this intuition right and if yes then what is the most quantitative theorem we know of which captures this? </p></li>
</ul>

<hr>

<p>I am interchangeably using the words "query complexity" and "running time of the learning algorithm". I hope this is okay. If not then it would be helpful if you could point out the subtlety that I am missing.  </p>

CC BY-SA 3.0
2017-06-29T20:11:14.447Z
Do you want explicit, structured classes of functions? Clearly, if you take the class of *all* $n$-variate Boolean functions, you'll get what you want, otherwise. (Also, since you are talking about PAC learning, I assume that by "queries" you mean "samples" -- in which case you should have a $2^n/\varepsilon$ dependence in your complexity?) Finally, regarding the "subtlety" between sample/query complexity and time complexity: 3-term DNF formulae are not properly efficiently learnable (i.e., with polynomial time complexity) unless RP=NP, yet they can be "improperly" learned efficiently.
Clement C.
CC BY-SA 3.0
2017-06-29T20:15:12.773Z
(that is, the number of samples information-theoretically sufficient to is polynomial, but after that hell breaks loose in processing time if you want to output a hypothesis which is a 3-term DNF as well)
Clement C.
CC BY-SA 3.0
2017-06-29T20:20:46.537Z
Can you give me a reference for a proof about this result about $3-$term DNF? (Why is $3$ special?) About my first question I am thinking of examples of what might be the hardest Boolean functions to learn. What do we know best in this direction?
gradstudent
CC BY-SA 3.0
2017-06-29T20:23:47.620Z
For the 3-term DNF, look at [*An Introduction to Computational Learning Theory*](https://mitpress.mit.edu/books/introduction-computational-learning-theory), by Kearns and Vazirani (MIT Press, 1994). This is Section 1.4 (Theorem 1.3). (Incidentally, that is a great book to read.) The $3$ is special for a reduction to 3-coloring.
Clement C.
CC BY-SA 3.0
2017-06-29T20:35:04.887Z
Thanks! (About $k-$DNF there is an unanswered question lying here, https://cstheory.stackexchange.com/questions/12225/sample-complexity-of-pac-learning-all-k-dnfs-over-the-uniform-distribution?rq=1 ) So about the functions which are hardest to PAC learn, what is known? (..like shouldn't the inner-product-mod-2 be a very hard function to learn?..)
gradstudent
CC BY-SA 3.0
2017-06-29T20:37:33.630Z
I am not sure about what you are asking there. The inner product mod 2 is a *single* Boolean function (concept). Learning results are dealing with *classes* of functions (concept classes) -- PAC learning a class comprising only one function can be done with exactly 0 queries (you know immediately which function is the "unknown function" you are trying to learn: there is only one possibility).
Clement C.
CC BY-SA 3.0
2017-06-29T20:48:05.503Z
Sorry for my vagueness. Lets define the "concept class" as those Boolean functions whose all the Fourier weights are almost the same (parameterize it somehow).  Then is this class known to be hard to PAC learn?
gradstudent
CC BY-SA 3.0
2017-06-29T23:09:26.850Z
@ClementC. I clarified this in the question too.
gradstudent
CC BY-SA 3.0
2017-06-30T13:59:33.657Z
I believe the term you are looking for is "bent functions": all Fourier coefficients having magnitude $1/2^{n/2}$, of which IP is a specific example. (A generalization would be, I believe, $\epsilon$-regular functions in the terminology of O'Donnell's book, Chapter 6 -- for very small $\epsilon$.) I don't have, off the top of my head, any reference about PAC learnability of the class of bent functions, but they are definitely hard to SQ-learn (see e.g. https://www.cs.utexas.edu/~klivans/mlj07-sq.pdf, Theorem 4.2)
Clement C.
CC BY-SA 3.0
2017-06-30T14:08:30.057Z
For your first question, in light of the equivalence between sample size necessary for PAC learning and VC dimension, it boils down to finding a concept class with very high VC dimension (also, I reckon this equivalence may be the "most general theorem for PAC learning of Boolean functions" one could think of)
Clement C.
CC BY-SA 3.0
2017-06-30T14:13:27.393Z
Thanks for the references! Let me look them up. Recently Amit Daniely and Shai Shalev Schwartz showed new hardness lowerbounds for learning intesection of half spaces, https://arxiv.org/abs/1404.3378. This doesn't supersede the Klivans-Sherstov paper you linked to?
gradstudent
CC BY-SA 3.0
2017-06-30T14:15:17.123Z
most likely not, since I only was referring to the particular statement about bent functions (that the paper I linked then uses to prove lower bounds on other classes).
Clement C.
CC BY-SA 3.0
2017-07-03T02:24:07.110Z
@Clement C. It seems that the Klivans-Sherstov result shows hardness of learning bent functions in the "statistical query model". Does that imply hardness of learning in the PAC sense as the question asked? If it is so then it would be helpful if you could give some references which prove this implication!
Student
CC BY-SA 3.0
2017-07-03T02:25:54.517Z
AFAIK, it does not. Not in general in any case.
Clement C.
CC BY-SA 3.0
2017-07-03T03:24:25.123Z
Thanks! Any references to the best/strongest known implications between the two models?
Student
CC BY-SA 3.0
2017-07-03T03:59:06.477Z
SQ implies PAC learning (as you can simulate SQ queries given PAC access). The opposite does not work. For instance, PAC learning parities is easy, [SQ learning them is hard.](https://www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf)
Clement C.
CC BY-SA 3.0
2017-07-03T19:09:16.873Z
Thanks! So is there any special case known when SQDim lowerbound implies a PAC learning lowerbound?
Student
<machine-learning><boolean-functions><lg.learning><query-complexity><pac-learning>
Boolean functions with high query complexity for PAC learning
gradstudent
# Boolean functions with high query complexity for PAC learning

(Asked by: username_0 on 2017-06-29)

The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier weights are concentrated on some modes can be PAC learnt in polynomial time. Also it trivially follows that in $2^n$ queries one can learn any Boolean function on the $n-$Hamming cube.

My question is two fold,

* For what concept classes do we know of high ($2^n$?) query lowerbound for PAC learning? If the proof is short then it would be very helpful if you could kindly type it in or give a reference.
* For Boolean functions whose Fourier spectrum seems very evenly spread out over the modes it seems that it should be hard to learn them in a few queries. Is this intuition right and if yes then what is the most quantitative theorem we know of which captures this?

---

I am interchangeably using the words "query complexity" and "running time of the learning algorithm". I hope this is okay. If not then it would be helpful if you could point out the subtlety that I am missing.

**Tags:** machine-learning, boolean-functions, lg.learning, query-complexity, pac-learning
> **Comments:**
> **username_1**: Do you want explicit, structured classes of functions? Clearly, if you take the class of *all* $n$-variate Boolean functions, you'll get what you want, otherwise. (Also, since you are talking about PAC learning, I assume that by "queries" you mean "samples" -- in which case you should have a $2^n/\varepsilon$ dependence in your complexity?) Finally, regarding the "subtlety" between sample/query complexity and time complexity: 3-term DNF formulae are not properly efficiently learnable (i.e., with polynomial time complexity) unless RP=NP, yet they can be "improperly" learned efficiently.  
> **username_1**: (that is, the number of samples information-theoretically sufficient to is polynomial, but after that hell breaks loose in processing time if you want to output a hypothesis which is a 3-term DNF as well)  
> **username_0**: Can you give me a reference for a proof about this result about $3-$term DNF? (Why is $3$ special?) About my first question I am thinking of examples of what might be the hardest Boolean functions to learn. What do we know best in this direction?  
> **username_1**: For the 3-term DNF, look at [*An Introduction to Computational Learning Theory*](https://mitpress.mit.edu/books/introduction-computational-learning-theory), by Kearns and Vazirani (MIT Press, 1994). This is Section 1.4 (Theorem 1.3). (Incidentally, that is a great book to read.) The $3$ is special for a reduction to 3-coloring.  
> **username_0**: Thanks! (About $k-$DNF there is an unanswered question lying here, https://cstheory.stackexchange.com/questions/12225/sample-complexity-of-pac-learning-all-k-dnfs-over-the-uniform-distribution?rq=1 ) So about the functions which are hardest to PAC learn, what is known? (..like shouldn't the inner-product-mod-2 be a very hard function to learn?..)  
> **username_1**: I am not sure about what you are asking there. The inner product mod 2 is a *single* Boolean function (concept). Learning results are dealing with *classes* of functions (concept classes) -- PAC learning a class comprising only one function can be done with exactly 0 queries (you know immediately which function is the "unknown function" you are trying to learn: there is only one possibility).  
> **username_0**: Sorry for my vagueness. Lets define the "concept class" as those Boolean functions whose all the Fourier weights are almost the same (parameterize it somehow).  Then is this class known to be hard to PAC learn?  
> **username_0**: @ClementC. I clarified this in the question too.  
> **username_1**: I believe the term you are looking for is "bent functions": all Fourier coefficients having magnitude $1/2^{n/2}$, of which IP is a specific example. (A generalization would be, I believe, $\epsilon$-regular functions in the terminology of O'Donnell's book, Chapter 6 -- for very small $\epsilon$.) I don't have, off the top of my head, any reference about PAC learnability of the class of bent functions, but they are definitely hard to SQ-learn (see e.g. https://www.cs.utexas.edu/~klivans/mlj07-sq.pdf, Theorem 4.2)  
> **username_1**: For your first question, in light of the equivalence between sample size necessary for PAC learning and VC dimension, it boils down to finding a concept class with very high VC dimension (also, I reckon this equivalence may be the "most general theorem for PAC learning of Boolean functions" one could think of)  
> **username_0**: Thanks for the references! Let me look them up. Recently Amit Daniely and Shai Shalev Schwartz showed new hardness lowerbounds for learning intesection of half spaces, https://arxiv.org/abs/1404.3378. This doesn't supersede the Klivans-Sherstov paper you linked to?  
> **username_1**: most likely not, since I only was referring to the particular statement about bent functions (that the paper I linked then uses to prove lower bounds on other classes).  
> **username_2**: @Clement C. It seems that the Klivans-Sherstov result shows hardness of learning bent functions in the "statistical query model". Does that imply hardness of learning in the PAC sense as the question asked? If it is so then it would be helpful if you could give some references which prove this implication!  
> **username_1**: AFAIK, it does not. Not in general in any case.  
> **username_2**: Thanks! Any references to the best/strongest known implications between the two models?  
> **username_1**: SQ implies PAC learning (as you can simulate SQ queries given PAC access). The opposite does not work. For instance, PAC learning parities is easy, [SQ learning them is hard.](https://www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf)  
> **username_2**: Thanks! So is there any special case known when SQDim lowerbound implies a PAC learning lowerbound?  

---

## 0 answers

