ML Anthology

An O(nlog Log N) Learning Algorithm for DNF Under the Uniform Distribution

Yishay Mansour
COLT 1992 pp. 53-61
doi:10.1145/130385.130391 /colt/1992/mansour1992colt-o/

Abstract

We show that a DNF with terms of size at most d can be approximated by a function with at most dO(d log 1/ε))non zero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most ε. This property is used to derive a learning algorithm for DNF, under the uniform distribution.

PDF COLT Semantic Scholar

Cite

Text

Mansour. "An O(nlog Log N) Learning Algorithm for DNF Under the Uniform Distribution." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130391

Markdown

[Mansour. "An O(nlog Log N) Learning Algorithm for DNF Under the Uniform Distribution." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/mansour1992colt-o/) doi:10.1145/130385.130391

BibTeX

@inproceedings{mansour1992colt-o,
  title     = {{An O(nlog Log N) Learning Algorithm for DNF Under the Uniform Distribution}},
  author    = {Mansour, Yishay},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1992},
  pages     = {53-61},
  doi       = {10.1145/130385.130391},
  url       = {https://mlanthology.org/colt/1992/mansour1992colt-o/}
}