Fetching the paper…
Reading the bibliography…
We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least \emph{quadratic} in the dimension, in a natural streaming setting.
Spaces with large distance to ℓ ∞ n \ell^{n}_{\infty} and random matrices
Stanislaw J Szarek · 1990
Earlier work this paper cites.
The communication complexity of several problems in matrix computation
Jeff I Chu and Georg Schnitger · 1991
Earlier work this paper cites.
Communication complexity of matrix computation over finite fields
Jeff I Chu and Georg Schnitger · 1995
Earlier work this paper cites.
Random projection, margins, kernels, and feature-selection
Avrim Blum · 2006
Earlier work this paper cites.
Volume growth and general rate quantization on grassmann manifolds
Wei Dai, Brian C Rider, and Youjian Liu · 2007
Earlier work this paper cites.
Tight lower bounds for multi-pass stream computation via pass elimination
Sudipto Guha and Andrew McGregor · 2008
Earlier work this paper cites.
Numerical linear algebra in the streaming model
Kenneth L Clarkson and David P Woodruff · 2009
Earlier work this paper cites.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Earlier work this paper cites.
Randomized communication complexity for linear algebra problems over finite fields
Xiaoming Sun and Chengu Wang · 2012
Earlier work this paper cites.
On the communication complexity of linear algebraic problems in the message passing model
Yi Li, Xiaoming Sun, Chengu Wang, and David P Woodruff · 2014
Earlier work this paper cites.
Understanding machine learning: From theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Earlier work this paper cites.
Asymptotic geometric analysis, Part I , volume 202
Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D Milman · 2015
Cited alongside, same era.
Minimax rates for memory-bounded sparse linear regression
Jacob Steinhardt and John Duchi · 2015
Cited alongside, same era.
Distributed estimation of generalized matrix rank: Efficient algorithms and lower bounds
Yuchen Zhang, Martin Wainwright, and Michael Jordan · 2015
Cited alongside, same era.
Communication lower bounds for statistical estimation problems via a distributed data processing inequality
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff · 2016
Cited alongside, same era.
Optimal approximate matrix product in terms of stable rank
Michael B. Cohen, Jelani Nelson, and David P. Woodruff · 2016
Cited alongside, same era.
Fast learning requires good memory: A time-space lower bound for parity learning
Mixing implies lower bounds for space bounded learning
Dana Moshkovitz and Michal Moshkovitz · 2017
Later among the works it cites.
A time-space lower bound for a large class of learning problems
Ran Raz · 2017
Later among the works it cites.
Upper bound for intermediate singular values of random matrices
Feng Wei · 2017
Later among the works it cites.
Time-space tradeoffs for learning finite functions from random evaluations, with applications to polynomials
Paul Beame, Shayan Oveis Gharan, and Xin Yang · 2018
Later among the works it cites.
Matrix norms in data streams: Faster, multi-pass and row-order
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, and Lin F. Yang · 2018
Later among the works it cites.
Detecting correlations with little memory and communication
Yuval Dagan and Ohad Shamir · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Ran Raz · 2016
Cited alongside, same era.
Schubert varieties and distances between subspaces of different dimensions
Ke Ye and Lek-Heng Lim · 2016
Cited alongside, same era.
Time-space tradeoffs for learning from small test spaces: Learning low degree polynomial functions
Paul Beame, Shayan Oveis Gharan, and Xin Yang · 2017
Cited alongside, same era.
Extractor-based time-space lower bounds for learning
Sumegha Garg, Ran Raz, and Avishay Tal · 2017
Cited alongside, same era.
On communication complexity of classification problems
Daniel M Kane, Roi Livni, Shay Moran, and Amir Yehudayoff · 2017
Cited alongside, same era.
Time-space hardness of learning sparse parities
Gillat Kol, Ran Raz, and Avishay Tal · 2017
Cited alongside, same era.
Later among the works it cites.
Learning without interaction requires separation
Amit Daniely and Vitaly Feldman · 2018
Later among the works it cites.
Robust subspace approximation in a stream
Roie Levin, Anish Prasad Sevekari, and David P. Woodruff · 2018
Later among the works it cites.
Entropy samplers and strong generic lower bounds for space bounded learning
Dana Moshkovitz and Michal Moshkovitz · 2018
Later among the works it cites.
Testing matrix rank, optimally
Maria-Florina Balcan, Yi Li, David P. Woodruff, and Hongyang Zhang · 2019
Closest in time.
Memory-sample tradeoffs for linear regression with small error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant · 2019
Closest in time.