ML Anthology

Lower Bounds on Learning Random Structures with Statistical Queries

Dana Angluin, David Eisenstat, Leonid Kontorovich, Lev Reyzin
ALT 2010 pp. 194-208
doi:10.1007/978-3-642-16108-7_18 /alt/2010/angluin2010alt-lower/

Abstract

We show that random DNF formulas, random log-depth decision trees and random deterministic finite acceptors cannot be weakly learned with a polynomial number of statistical queries with respect to an arbitrary distribution on examples.

PDF ALT Semantic Scholar

Cite

Text

Angluin et al. "Lower Bounds on Learning Random Structures with Statistical Queries." International Conference on Algorithmic Learning Theory, 2010. doi:10.1007/978-3-642-16108-7_18

Markdown

[Angluin et al. "Lower Bounds on Learning Random Structures with Statistical Queries." International Conference on Algorithmic Learning Theory, 2010.](https://mlanthology.org/alt/2010/angluin2010alt-lower/) doi:10.1007/978-3-642-16108-7_18

BibTeX

@inproceedings{angluin2010alt-lower,
  title     = {{Lower Bounds on Learning Random Structures with Statistical Queries}},
  author    = {Angluin, Dana and Eisenstat, David and Kontorovich, Leonid and Reyzin, Lev},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2010},
  pages     = {194-208},
  doi       = {10.1007/978-3-642-16108-7_18},
  url       = {https://mlanthology.org/alt/2010/angluin2010alt-lower/}
}