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.
Raz is a professor of theoretical computer science at Princeton University. He received his B.Sc. in mathematics and physics in 1987 and his Ph.D. in mathematics in 1992 from the Hebrew University of Jerusalem. After spending two years as a postdoc at Princeton University, in 1994 he joined the Weizmann Institute of Science in Israel. He was a visiting professor at Microsoft Research (2006, 2009) and the Institute for Advanced Study (2012–2016). Raz’s main research area is computational complexity theory, with a focus on proving lower bounds for computational models.
TEA: 4:15-5:00pm
LECTURE: 5:00-6:15pm
When: Fri., May. 17, 2019 at 5:00 pm
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.
Raz is a professor of theoretical computer science at Princeton University. He received his B.Sc. in mathematics and physics in 1987 and his Ph.D. in mathematics in 1992 from the Hebrew University of Jerusalem. After spending two years as a postdoc at Princeton University, in 1994 he joined the Weizmann Institute of Science in Israel. He was a visiting professor at Microsoft Research (2006, 2009) and the Institute for Advanced Study (2012–2016). Raz’s main research area is computational complexity theory, with a focus on proving lower bounds for computational models.
TEA: 4:15-5:00pm
LECTURE: 5:00-6:15pm
Buy tickets/get more info now
