<p>Juntas can be <em>tested</em> in an attribute efficient manner given a membership query oracle: <a href="http://www.cs.cmu.edu/~eblais/papers/TestingJuntas.pdf">http://www.cs.cmu.edu/~eblais/papers/TestingJuntas.pdf</a> 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. </p>

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

CC BY-SA 3.0
2013-07-31T04:57:37.640Z
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?
Keki Burjorjee
CC BY-SA 3.0
2013-07-31T12:09:47.323Z
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.
Aaron Roth
CC BY-SA 3.0
2013-08-03T21:45:56.407Z
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?
Keki Burjorjee
CC BY-SA 3.0
2016-05-13T15:26:47.133Z
@KekiBurjorjee Quite a bit later... see e.g. Section 2.3 of these [lecture notes](http://www.cs.columbia.edu/~rocco/Teaching/S14/Scribe/lectures_full.pdf).
Clement C.
CC BY-SA 3.0
2013-07-30T16:04:22.623Z
2013-07-30T17:07:45.940Z
2013-07-30T17:07:45.940Z
Aaron Roth
<p>According to <a href="http://www.cs.columbia.edu/~rocco/papers/stoc03juntas.html" rel="nofollow" title="&quot;Learning functions of k relevant variables.&quot;, E. Mossel and R. O'Donnell and R. Servedio.">[MOS04]</a> (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 <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.7659" rel="nofollow" title="&quot;Selection of relevant features and examples in machine learning. Avrim L. Blum&quot; , Pat Langley">[BL97]</a>, p. 17. </p>

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

CC BY-SA 3.0
2013-07-30T14:28:22.633Z
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..
Lev Reyzin
CC BY-SA 3.0
2013-07-30T14:50:31.807Z
I think you're right — I realized that I wasn't addressing the "attribute efficiency" part of the question at all.
Clement C.
CC BY-SA 3.0
2013-07-30T14:06:42.653Z
2013-07-30T14:41:16.720Z
2013-07-30T14:41:16.720Z
Clement C.
<p>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? </p>

<lg.learning><boolean-functions>
Attribute efficiently learning the relevant attributes of juntas with membership queries
Keki Burjorjee
# Attribute efficiently learning the relevant attributes of juntas with membership queries

(Asked by: username_0 on 2013-07-28)

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?

**Tags:** lg.learning, boolean-functions


---

## 2 answers

### Answer by username_1 on 2013-07-30. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_2**: @KekiBurjorjee Quite a bit later... see e.g. Section 2.3 of these [lecture notes](http://www.cs.columbia.edu/~rocco/Teaching/S14/Scribe/lectures_full.pdf).  

---

### Answer by username_2 on 2013-07-30. Score: 2

According to [[MOS04]](http://www.cs.columbia.edu/~rocco/papers/stoc03juntas.html) (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]](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.7659), p. 17.

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

> **Comments:**
> **username_3**: 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..  
> **username_2**: I think you're right — I realized that I wasn't addressing the "attribute efficiency" part of the question at all.  

---

