License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24178
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2417/
Buhrman, Harry ; Garcia-Soriano, David ; Matsliah, Arie

Learning Parities in the Mistake-Bound model

pdf-format:
Dokument 1.pdf (197 KB)

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

@InProceedings{buhrman_et_al:DSP:2010:2417,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2010/2417},
  annote =	{Keywords: Attribute-efficient learning, parities, mistake-bound}
}

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

DROPS-Home | Fulltext Search | Imprint Published by LZI