Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Seminar (5/31): Michal Moshkovitz

Ofir Geri ofirgeri at
Tue May 28 13:33:06 PDT 2019

Hi all,

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...
URL: <>

More information about the theory-seminar mailing list