# Learning k-parities with Membership Queries and Persistent Noise

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?

• 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 Jan 24 '15 at 6:57

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).
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.
• 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 Jan 24 '15 at 6:51