ML Anthology

Improved Learning of AC0 Functions

Merrick L. Furst, Jeffrey C. Jackson, Sean W. Smith
COLT 1991 pp. 317-325
doi:10.1016/B978-1-55860-213-7.50032-8 /colt/1991/furst1991colt-improved/

Abstract

Two extensions of the Linial, Mansour, Nisan AC 0 learning algorithm are presented. The LMN method works when input examples are drawn uniformly. The new algorithms improve on theirs by performing well when given inputs drawn from unknown, mutually independent distributions. A variant of the one of the algorithms is conjectured to work in an even broader setting.

PDF COLT Semantic Scholar

Cite

Text

Furst et al. "Improved Learning of AC0 Functions." Annual Conference on Computational Learning Theory, 1991. doi:10.1016/B978-1-55860-213-7.50032-8

Markdown

[Furst et al. "Improved Learning of AC0 Functions." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/furst1991colt-improved/) doi:10.1016/B978-1-55860-213-7.50032-8

BibTeX

@inproceedings{furst1991colt-improved,
  title     = {{Improved Learning of AC0 Functions}},
  author    = {Furst, Merrick L. and Jackson, Jeffrey C. and Smith, Sean W.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1991},
  pages     = {317-325},
  doi       = {10.1016/B978-1-55860-213-7.50032-8},
  url       = {https://mlanthology.org/colt/1991/furst1991colt-improved/}
}