Can the relevant attributes of k-juntas be learned attribute efficiently given a membership query oracle? What's the best known lower bound for this problem?


2 Answers 2


Juntas can be tested in an attribute efficient manner given a membership query oracle: http://www.cs.cmu.edu/~eblais/papers/TestingJuntas.pdf Testing is an easier problem than learning, and the attribute efficient result is relatively recent. This might be a good place to start poking around.

Incidentally, the hard part about learning juntas is just identifying the set of $k$ relevant variables. Once that is done, you can learn the junta through exhaustive querying with $2^k$ queries (which might be "attribute efficient" since it is independent of $n$. In any case, you can't hope to do much better since the function can be arbitrary on these $k$ bits...). The testing algorithm linked to seems to work by trying to identify relevant variables, so it might solve your problem if you go through the details.

  • $\begingroup$ Thanks for the link. In the event that the function is a junta, the algorithm provided can, if I'm reading the paper right, be used to eliminate the majority of irrelevant attributes. So it probably wouldn't come as much of a surprise if someone harnessed this feature to show that the repeated application of the algorithm allows the relevant attributes of juntas to be learned attribute efficiently. Is there something to this, or am I way off? $\endgroup$ Jul 31, 2013 at 4:57
  • $\begingroup$ Yes. It makes sense: With ~ $2^k$ random queries, you can identify $k$ pairs of inputs $x,y$ for which $f(x) \neq f(y)$ and each of the k relevant variables is pivotal. By interpolating between them with binary search, you can find the relevant variable pivotal for each pair with log(n) queries. Once you find the relevant variables, you can learn the function with another $2^k$ queries, for a total of poly$(2^k, \log(n))$ queries. It shouldn't be hard to argue that poly$(k, \log(n))$ is impossible since the junta can be arbitrary. $\endgroup$
    – Aaron Roth
    Jul 31, 2013 at 12:09
  • $\begingroup$ If I understand you correctly, showing that juntas can be learned in $poly (2^k, \log n)$ queries is relatively straightforward. Any idea why no one has formally connected the dots? $\endgroup$ Aug 3, 2013 at 21:45
  • $\begingroup$ @KekiBurjorjee Quite a bit later... see e.g. Section 2.3 of these lecture notes. $\endgroup$
    – Clement C.
    May 13, 2016 at 15:26

According to [MOS04] (Section 5.2), the class of $k$-juntas over $\{-1,1\}^n$ can be learnt with membership queries in time $\operatorname{poly}(2^k, n)$ — cf. also footnote 8 of [BL97], p. 17.

Edit: as pointed out in the comment, this is probably not what you were looking for (in terms of attribute-efficiency).

  • 3
    $\begingroup$ I don't think this is attribute-efficient. I imagine attribute efficient learning of juntas would require bounds of poly$(k,\log n)$ on the number of queries/examples used.. $\endgroup$
    – Lev Reyzin
    Jul 30, 2013 at 14:28
  • $\begingroup$ I think you're right — I realized that I wasn't addressing the "attribute efficiency" part of the question at all. $\endgroup$
    – Clement C.
    Jul 30, 2013 at 14:50

Your Answer

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

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