License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09421.5
URN: urn:nbn:de:0030-drops-24178
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2417/
Go to the corresponding Portal

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

Learning Parities in the Mistake-Bound model

pdf-format:
09421.GarciaSorianoDavid.Paper.2417.pdf (0.2 MB)

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:DagSemProc.09421.5,
  author =	{Buhrman, Harry and Garcia-Soriano, David and Matsliah, Arie},
  title =	{{Learning Parities in the Mistake-Bound model}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2417},
  URN =		{urn:nbn:de:0030-drops-24178},
  doi =		{10.4230/DagSemProc.09421.5},
  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