Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-060 | 4th June 2009 00:00

Learning parities in the mistake-bound model.

RSS-Feed




TR09-060
Authors: Harry Buhrman, David García Soriano, Arie Matsliah
Publication: 25th July 2009 12:13
Downloads: 5284
Keywords: 


Abstract:

We study the problem of learning parity functions that depend on at most k variables (k-parities) attribute-efficiently in the mistake-bound model.
We design simple, deterministic, polynomial-time algorithms for learning k-parities with mistake bound O(n^{1-\frac{c}{k}}), for any constant c > 0. These are the first polynomial-time algorithms that learn \omega(1)-parities in the mistake-bound model with mistake bound o(n).

Using the standard conversion techniques from the mistake-bound model to the PAC model, our algorithms can also be used for learning k-parities in the PAC model. In particular, this implies a slight improvement over the results of Klivans and Servedio
for learning k-parities in the PAC model.

We also show that the \widetilde{O}(n^{k/2}) time algorithm from
Klivans and Servedio's paper that PAC-learns k-parities with optimal sample complexity can be extended to the mistake-bound model.



ISSN 1433-8092 | Imprint