Search Mailing List Archives
[theory-seminar] Theory Seminar (5/31): Michal Moshkovitz
ofirgeri at stanford.edu
Tue May 28 13:33:06 PDT 2019
This week Michal Moshkovitz (UCSD) will give a theory seminar talk: On Bounded-Memory Learning (see abstract below). The talk will be as usual on Friday 3:00 PM in Gates 463A.
The abstracts of past and upcoming seminar talks are also available on the theory seminar webpage:
Hope to see you there!
On Bounded-Memory Learning
Speaker: Michal Moshkovitz (UCSD)
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. This motivates the question of how many labeled examples are needed in case the memory is bounded. One might wonder whether a general combinatorial condition exists for (un)learnability with bounded memory. In this talk we give a combinatorial condition for learnability with bounded memory and a combinatorial condition for unlearnability with bounded memory.
The talk is based on joint works with Dana Moshkovitz and Naftali Tishby.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar