zbMATH — the first resource for mathematics

On noise-tolerant learning of sparse parities and related problems. (English) Zbl 1348.68194
Kivinen, Jyrki (ed.) et al., Algorithmic learning theory. 22nd international conference, ALT 2011, Espoo, Finland, October 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24411-7/pbk). Lecture Notes in Computer Science 6925. Lecture Notes in Artificial Intelligence, 413-424 (2011).
Summary: We consider the problem of learning sparse parities in the presence of noise. For learning parities on $$r$$ out of $$n$$ variables, we give an algorithm that runs in time $\operatorname{poly} \left( \log \frac{1}{\delta}, \frac{1}{1-2\eta} \right) n^{ \left(1+(2\eta)^2+ o(1)\right)r/2}$ and uses only $$\frac{r \log(n/\delta) \omega(1)}{(1 - 2\eta)^2}$$ samples in the random noise setting under the uniform distribution, where $$\eta$$ is the noise rate and $$\delta$$ is the confidence parameter. From previously known results this algorithm also works for adversarial noise and generalizes to arbitrary distributions. Even though efficient algorithms for learning sparse parities in the presence of noise would have major implications to learning other hypothesis classes, our work is the first to give a bound better than the brute-force $$O(n ^{r })$$. As a consequence, we obtain the first nontrivial bound for learning $$r$$-juntas in the presence of noise, and also a small improvement in the complexity of learning DNF, under the uniform distribution.
For the entire collection see [Zbl 1223.68007].

MSC:
 68T05 Learning and adaptive systems in artificial intelligence
Full Text: