Abstract
A recent line of work studied the efficiency of learning under memory constraints. This was highlighted in the celebrated result of Raz [FOCS, 2016] who showed that efficient parity learning requires a quadratic memory. The model of computation in these works is the streaming model: a bounded memory learner tries to learn a concept from a stream of random labeled examples. We would survey lower bounds for learning parities, sparse parities, low-degree polynomials, as well as more general results based on properties of the matrix associated with the learning problem.