<p>Yes, this upper bound is known.
Check Section 4 here
<a href="http://www.jmlr.org/papers/volume8/feldman07a/feldman07a.pdf" rel="nofollow">http://www.jmlr.org/papers/volume8/feldman07a/feldman07a.pdf</a>
The analysis there is for the noiseless case. But a look at the algorithm shows that is just checks the expectation of the condition $\chi_(x)=1$ and $x_i=1$ over some distribution. This expectation can be estimated in the presence of random persistent noise (at the expense of using $1/(1-2\eta)^2$ times more queries).
In fact, as shown later in the paper even worst-case noise can be tolerated with only slightly worse complexity (another k log n factor).</p>

CC BY-SA 3.0
2015-01-24T10:50:51.670Z
2015-01-24T10:50:51.670Z
Vitaly
<p>If I understand correctly, this is exactly equivalent to local decoding of the Hadamard code.</p>

<p>We can think of the oracle (with the noise) as being chosen beforehand, and after that we can view the oracle as a corrupted codeword of the Hadamard code. Learning the parity in this case is exactly the task of local decoding the original message from the corrupted codeword.</p>

<p>This is well-known to be possible using $O(n \log n/\delta)$ queries, using the Goldreich-Levin theorem, e.g.:
<a href="https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/" rel="nofollow">https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/</a></p>

<p>On the other hand, it clearly can not be done using $o(n)$ queries, since the algorithm has learn $n$ bits about the parity - i.e., its attributes.</p>

CC BY-SA 3.0
2015-01-24T06:51:55.917Z
My apologies. I forgot to mention that $k$, the number of relevant attributes is constant with respect to $n$. I've changed the question to reflect this. If $k$ is constant w.r.t. $n$, is the problem known to be solvable in $O(n \log(n/\delta))$ time and $O(\log(n/\delta))$ queries?
Keki Burjorjee
CC BY-SA 3.0
2015-01-23T20:23:52.230Z
2015-01-23T20:23:52.230Z
Or Meir
<p>Random <em>independent</em> misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta&lt;1/2$ one can eliminate noise to an arbitrary extent by simply querying the oracle $p(1/(1-2\eta))$ times with the same input for some polynomial $p(\cdot)$ and taking the majority label returned.  </p>

<p>The random <em>persistent</em> misclassification noise model of Goldman, Kearns, and Schapire, plugs this "loophole" by stipulating that an oracle that assigns a label $l$ to some sample $x$, <em>always</em> assigns label $l$ to sample $x$.</p>

<p>My question is: What are the known best upper bounds on the time and queries required to solve the learning parities problem with membership queries and random persistent misclassification noise for some constant value of $k$ (the number of relevant attributes)? Is the problem known to be solvable in $O(n \log (n/\delta))$ time and $O(\log (n/\delta))$ queries w.r.t. $n$, the number of attributes and $\delta$, the probability of error? </p>

CC BY-SA 3.0
2015-01-24T06:57:50.777Z
Note: The original question and question title did not stipulate that $k$, the number of relevant attributes, is constant with respect to $n$, the total number of attributes. This stipulation has now been added.
Keki Burjorjee
<boolean-functions><lg.learning>
Learning k-parities with Membership Queries and Persistent Noise
Keki Burjorjee
# Learning k-parities with Membership Queries and Persistent Noise

(Asked by: username_0 on 2015-01-23)

Random *independent* misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta<1/2$ one can eliminate noise to an arbitrary extent by simply querying the oracle $p(1/(1-2\eta))$ times with the same input for some polynomial $p(\cdot)$ and taking the majority label returned.

The random *persistent* misclassification noise model of Goldman, Kearns, and Schapire, plugs this "loophole" by stipulating that an oracle that assigns a label $l$ to some sample $x$, *always* assigns label $l$ to sample $x$.

My question is: What are the known best upper bounds on the time and queries required to solve the learning parities problem with membership queries and random persistent misclassification noise for some constant value of $k$ (the number of relevant attributes)? Is the problem known to be solvable in $O(n \log (n/\delta))$ time and $O(\log (n/\delta))$ queries w.r.t. $n$, the number of attributes and $\delta$, the probability of error?

**Tags:** boolean-functions, lg.learning
> **Comments:**
> **username_0**: Note: The original question and question title did not stipulate that $k$, the number of relevant attributes, is constant with respect to $n$, the total number of attributes. This stipulation has now been added.  

---

## 2 answers

### Answer by username_1 on 2015-01-24. Score: 1 | Accepted answer

Yes, this upper bound is known.
Check Section 4 here
<http://www.jmlr.org/papers/volume8/feldman07a/feldman07a.pdf>
The analysis there is for the noiseless case. But a look at the algorithm shows that is just checks the expectation of the condition $\chi\_(x)=1$ and $x\_i=1$ over some distribution. This expectation can be estimated in the presence of random persistent noise (at the expense of using $1/(1-2\eta)^2$ times more queries).
In fact, as shown later in the paper even worst-case noise can be tolerated with only slightly worse complexity (another k log n factor).


---

### Answer by username_2 on 2015-01-23. Score: 3

If I understand correctly, this is exactly equivalent to local decoding of the Hadamard code.

We can think of the oracle (with the noise) as being chosen beforehand, and after that we can view the oracle as a corrupted codeword of the Hadamard code. Learning the parity in this case is exactly the task of local decoding the original message from the corrupted codeword.

This is well-known to be possible using $O(n \log n/\delta)$ queries, using the Goldreich-Levin theorem, e.g.:
<https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/>

On the other hand, it clearly can not be done using $o(n)$ queries, since the algorithm has learn $n$ bits about the parity - i.e., its attributes.

> **Comments:**
> **username_0**: My apologies. I forgot to mention that $k$, the number of relevant attributes is constant with respect to $n$. I've changed the question to reflect this. If $k$ is constant w.r.t. $n$, is the problem known to be solvable in $O(n \log(n/\delta))$ time and $O(\log(n/\delta))$ queries?  

---

