3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Keki Burjorjee
    Commented Jan 24, 2015 at 6:57

2 Answers 2

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Keki Burjorjee
    Commented Jan 24, 2015 at 6:51

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.