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

[Ofir Geri]

Reminder: Michal's talk is today at 3pm.
________________________________
From: Ofir Geri
Sent: Tuesday, May 28, 2019 1:33 PM
To: thseminar at cs.stanford.edu
Subject: Theory Seminar (5/31): Michal Moshkovitz

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:
http://theory.stanford.edu/seminar/

Hope to see you there!
Ofir

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: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20190531/8dbf012d/attachment.html>