Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning

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.