Strong Memory Lower Bounds for Learning Natural Models

Gavin Brown, Mark Bun, Adam Smith

We give lower bounds on the amount of memory required by one-pass streaming algorithms for solving several natural learning problems. In a setting where examples lie in $\{0,1{\}}^d$…