ML Anthology

A Query Algorithm for Agnostically Learning DNF?

Parikshit Gopalan, Adam Kalai, Adam R. Klivans
COLT 2008 pp. 515-516
/colt/2008/gopalan2008colt-query/

Abstract

We pose the open problem of whether polynomial-size DNF formulas are agnostically learnable with membership queries under the uniform distribution. We formally define the question, discuss its relation to weakly learning polynomial-size depth-3 circuits and to agnostic learning of halfspaces, and survey current partial results.

PDF Semantic Scholar

Cite

Text

Gopalan et al. "A Query Algorithm for Agnostically Learning DNF?." Annual Conference on Computational Learning Theory, 2008.

Markdown

[Gopalan et al. "A Query Algorithm for Agnostically Learning DNF?." Annual Conference on Computational Learning Theory, 2008.](https://mlanthology.org/colt/2008/gopalan2008colt-query/)

BibTeX

@inproceedings{gopalan2008colt-query,
  title     = {{A Query Algorithm for Agnostically Learning DNF?}},
  author    = {Gopalan, Parikshit and Kalai, Adam and Klivans, Adam R.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2008},
  pages     = {515-516},
  url       = {https://mlanthology.org/colt/2008/gopalan2008colt-query/}
}