Memory-sample tradeoffs for linear regression with small error

DOI10.1145/3313276.3316403zbMath1437.62265arXiv1904.08544OpenAlexW2963951786MaRDI QIDQ5212830

Gregory Valiant, Aaron Sidford, Vatsal Sharan

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.08544

zbMATH Keywords

lower bounds for optimizationmemory-bounded learning

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Linear regression; mixed models (62J05) Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Statistical-computational trade-offs in tensor PCA and related problems via communication complexity, Unnamed Item