Memory/Sample Tradeoffs in Linear Regression with Ill-Conditionned Data

Series
Stochastics Seminar
Time
Thursday, November 19, 2026 - 3:30pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Moïse Blanchard – Georgia Tech ISyE – mblanchard41@gatech.edu – https://moiseb.github.io/
Organizer
Dmitrii Ostrovskii

How much memory do learning algorithms need? In recent years, computational bottlenecks in machine learning (ML) have gradually been shifting from compute power to memory bandwidth limitations, especially due to GPU constraints. This shift raises the question of how memory usage trades off against the convergence rate of learning algorithms. Memory bottlenecks have been extensively studied for discrete learning problems; however, much less is known for continuous learning problems including linear regression, one of the fundamental ML primitives. Prior work for isotropic Gaussian data proved logarithmic separations in the memory/sample-complexity tradeoff [SSV19, OpenAI26]. However, when the data is anisotropic with condition number κ, standard practice suggests that low-memory algorithms, including Kaczmarz’s method, pay a polynomial price in κ, while the sample-complexity of memory-intensive methods, including Gaussian elimination, is independent of κ: O(d) samples suffice in dimension d. This suggests an exponential sample price for memory-constrained linear regression algorithms. In this work, we make some progress by proving a polynomial separation in the dimension d, in the non-iid setting where κ-conditioned distributions may be adaptively selected by an adversary. Formally, we show that any algorithm with at most O(d^{2−δ} log d) bits of memory requires at least d^{1+δ} samples for some polynomial condition number κ in d.