ECCC-Report TR09-060https://eccc.weizmann.ac.il/report/2009/060Comments and Revisions published for TR09-060en-usSat, 25 Jul 2009 12:13:17 +0300
Paper TR09-060
| Learning parities in the mistake-bound model. |
Harry Buhrman,
David GarcĂa Soriano,
Arie Matsliah
https://eccc.weizmann.ac.il/report/2009/060We 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.
Sat, 25 Jul 2009 12:13:17 +0300https://eccc.weizmann.ac.il/report/2009/060