When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24178
Go to the corresponding Portal

Buhrman, Harry ; Garcia-Soriano, David ; Matsliah, Arie

Learning Parities in the Mistake-Bound model

09421.GarciaSorianoDavid.Paper.2417.pdf (0.2 MB)


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 a simple, deterministic, polynomial-time algorithm for learning $k$-parities with mistake bound $O(n^{1-frac{c}{k}})$, for any constant $c > 0$. This is the first polynomial-time algorithms that learns $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 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
cite{rocco} for learning $k$-parities in the PAC model.

We also show that the $widetilde{O}(n^{k/2})$ time algorithm from cite{rocco} that PAC-learns $k$-parities with optimal sample complexity can be extended to the mistake-bound model.

BibTeX - Entry

  author =	{Harry Buhrman and David Garcia-Soriano and Arie Matsliah},
  title =	{Learning Parities in the Mistake-Bound model},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2010},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  number =	{09421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Attribute-efficient learning, parities, mistake-bound}

Keywords: Attribute-efficient learning, parities, mistake-bound
Collection: 09421 - Algebraic Methods in Computational Complexity
Issue Date: 2010
Date of publication: 19.01.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI