From Dimension to Horizon: Krylov Coresets for Linear Regression

Classical coresets for linear regression preserve the objective over the full parameter space, leading to sizes that depend on the dimension $d$. We ask whether the optimization horizon can instead determine the amount of data needed. For any $T$-step gradient descent (GD) trajectory, all iterates lie in an affine Krylov space of dimension at most $T$. Since GD converges linearly in strongly convex settings, the required optimization horizon $T$ can be much smaller than $d$. Motivated by this structure, we construct a strong Krylov coreset of size $O(\frac{T}{{ϵ}^2}\log (\frac{T}{\delta }))$ that preserves the objective throughout the corresponding affine Krylov space. To further reduce the coreset size and construction cost, we develop a weak Krylov coreset based on a blockwise approximation of the GD trajectory. It has size $O(\frac{T}{ϵ}\log (\frac{T}{\delta }))$ and returns a solution whose loss is within a factor $1+ϵ$ of the best bounded affine combination of the exact GD iterates. With an appropriate block size, its construction requires only $O(\sqrt{T}+\log (\frac{1}{\delta }))$ full-data passes in expectation. Experiments show that Krylov coresets closely match the regression loss of full-data GD, while the weak construction further reduces coreset size and computational cost.