All reports by Author Michal Moshkovitz:

__
TR17-116
| 5th July 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Strong Lower Bounds for Space Bounded Learning

__
TR17-017
| 5th February 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Lower Bounds for Space Bounded Learning

Michal Moshkovitz, Dana Moshkovitz

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 ... more >>>

Michal Moshkovitz, Dana Moshkovitz

One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>>