Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning
Where: Simons Foundation
160 Fifth Ave., 2nd Floor
646-654-0066 Price: Free
Buy tickets/get more info now
See other events in these categories:
Can one prove unconditional lower bounds on the number of samples needed for learning, under memory constraints? A recent line of works shows that for a large class of learning problems, any learning algorithm requires either a memory of super-linear size or a super-polynomial number of samples. For example, any algorithm for learning parities of size n, from a stream of samples, requires either a memory of quadratic size or an exponential number of samples.
A main message of these works is that for some learning problems, access to a relatively large memory is crucial. Ran Raz will tell about some of these works and discuss relations to computational complexity and applications in bounded-storage cryptography.
About the Speaker