Learning parities in the mistake-bound model

We study the problem of learning parity functions that depend on at most k variables (kparities) attribute-efficiently in the mistake-bound model. We design a simple, deterministic, polynomial-time algorithm for learning k-parities with mistake bound O(n1− k c ), for any constant c > 0. This is the first polynomial-time algorithms that learns ω(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 algorithm can also be used for learning k-parities in the PAC model. In particular, this implies a slight improvement on the results of Klivans and Servedio [KS04] for learning k-parities in the PAC model. We also show that the Oe(nk/2) time algorithm from [KS04] that PAC-learns k-parities with optimal sample complexity can be extended to the mistake-bound model.

• View at Publisher

Free Full Text ( Final Version , 196kb )