Low-Rank Thinning
This work addresses the problem of dataset summarization for machine learning practitioners by providing more general and efficient thinning algorithms, though it appears incremental as it builds on existing sub-Gaussian thinning methods.
The paper tackles limitations in existing sub-Gaussian thinning algorithms by introducing a low-rank analysis that applies to any distribution and kernel, guaranteeing high-quality compression when the kernel or data matrix is approximately low-rank. The result includes practical approaches that improve guarantees for approximating attention in transformers, accelerating stochastic gradient training, and distinguishing distributions in near-linear time.
The goal in thinning is to summarize a dataset using a small set of representative points. Remarkably, sub-Gaussian thinning algorithms like Kernel Halving and Compress can match the quality of uniform subsampling while substantially reducing the number of summary points. However, existing guarantees cover only a restricted range of distributions and kernel-based quality measures and suffer from pessimistic dimension dependence. To address these deficiencies, we introduce a new low-rank analysis of sub-Gaussian thinning that applies to any distribution and any kernel, guaranteeing high-quality compression whenever the kernel or data matrix is approximately low-rank. To demonstrate the broad applicability of the techniques, we design practical sub-Gaussian thinning approaches that improve upon the best known guarantees for approximating attention in transformers, accelerating stochastic gradient training through reordering, and distinguishing distributions in near-linear time.