1 Search Results for "Moshkovitz, Michal"


Document
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning

Authors: Dana Moshkovitz and Michal Moshkovitz

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)


Abstract
With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses graph. We prove that any hypothesis class whose hypotheses graph is mixing cannot be learned using less than Omega(log^2 |H|) memory bits unless the learner uses at least a large number |H|^Omega(1) labeled examples. Our work builds on a combinatorial framework that we suggested in a previous work for proving lower bounds on space bounded learning. The strong lower bound is obtained by defining a new notion of pseudorandomness, the entropy sampler. Raz obtained a similar result using different ideas.

Cite as

Dana Moshkovitz and Michal Moshkovitz. Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{moshkovitz_et_al:LIPIcs.ITCS.2018.28,
  author =	{Moshkovitz, Dana and Moshkovitz, Michal},
  title =	{{Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.28},
  URN =		{urn:nbn:de:0030-drops-83374},
  doi =		{10.4230/LIPIcs.ITCS.2018.28},
  annote =	{Keywords: learning, space bound, mixing, certainty, entropy sampler}
}
  • Refine by Author
  • 1 Moshkovitz, Dana
  • 1 Moshkovitz, Michal

  • Refine by Classification

  • Refine by Keyword
  • 1 certainty
  • 1 entropy sampler
  • 1 learning
  • 1 mixing
  • 1 space bound

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail