Space lower bounds for linear prediction in the streaming model

2019/02/09 by Yuval Dagan, Gil Kur, Dagan, Yuval +3 · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1902.03498

openalex publication_date 2019/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least quadratic in the dimension, in a natural streaming setting. This implies that such problems cannot be solved (at least in this setting) by scalable memory-efficient streaming algorithms. Our results build on a memory lower bound for a simple linear-algebraic problem -- finding orthogonal vectors -- and utilize the estimates on the packing of the Grassmannian, the manifold of all linear subspaces of fixed dimension.

Cited by

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

Related

• Strong Memory Lower Bounds for Learning Natural Models
• Distributed and Streaming Linear Programming in Low Dimensions
• Tight Time-Space Lower Bounds for Constant-Pass Learning
• Asymptotically exact streaming algorithms
• Spiking Neural Networks Through the Lens of Streaming Algorithms